Source-linked AI summary
Learning Discrete Structures for Graph Neural Networks
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, Xiao He
TL;DR
GNNs require graph structures that may be missing, incomplete, or noisy. The paper jointly learns a discrete probabilistic graph structure and GCN parameters through an approximate bilevel program, and reports competitive or superior results to related methods.
Problem
GNNs depend on graph structures, but real-world graphs may be missing, incomplete, or noisy.
Method
The method jointly learns GCN parameters and a discrete sparse graph distribution by modeling edges with Bernoulli variables within a bilevel program and using approximate gradient estimation.
Results
The method is competitive with and often outperforms existing approaches, including accuracy gains of up to 7 percentage points and accuracies of 84.1% on Cora and 75.0% on Citeseer.
Takeaways & Limitations
The learned graph generator provides meaningful probabilistic edge interpretations while supporting GCN use with incomplete, corrupted, or unavailable graphs.
Takeaways & Limitations
LDS cannot currently scale to large datasets, is evaluated only transductively, and requires retraining to add nodes after training.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) are a popular class of machine learning models whose major advantage is their ability to incorporate a sparse and discrete dependency structure between data points. Unfortunately, GNNs can only be used when such a graph-structure is available. In practice, however, real-world graphs are often noisy and incomplete or might not be available at all. With this work, we propose to jointly learn the graph structure and the parameters of graph convolutional networks (GCNs) by approximately solving a bilevel program that learns a discrete probability distribution on the edges of the graph. This allows one to apply GCNs not only in scenarios where the given graph is incomplete or corrupted but also in those where a graph is not available. We conduct a series of experiments that analyze the behavior of the proposed method and demonstrate that it outperforms related methods by a significant margin.
1. Introduction
Relational learning models dependencies between data points, making graphs a natural representation for GNNs. The paper addresses missing, incomplete, or noisy graphs by jointly learning sparse graph structure and GCN parameters.
- Relational learning uses both data-point attributes and relationships rather than assuming independence between data points.
- When graphs are unavailable, kNN construction depends heavily on the choices of neighborhood size and feature similarity measure.
- Graph creation and parameter learning are typically separate processes requiring heuristics and trial and error.
- The proposed approach jointly learns discrete sparse dependencies and GCN parameters using a generative probabilistic model for graphs.Samples from the graph model are used during training and prediction.
- The method simultaneously learns GNN graph structure and parameters for semi-supervised classification, and often outperforms existing approaches.The learned graph models also produce meaningful edge probabilities.
2. Background
The background introduces graph representations, GCN inputs and computation, and bilevel optimization. It motivates iterative optimization dynamics for handling inner problems whose solutions are not available in closed form.
- Graph theory: A graph consists of vertices and edges, represented by an adjacency matrix whose entries indicate whether vertex pairs are connected.The graph Laplacian is defined from the degree matrix and adjacency matrix.
- Graph neural networks: GNNs take a node-feature matrix and graph adjacency matrix as inputs, using labeled training nodes to learn a prediction function.
- Graph neural networks: GCN parameters are learned by minimizing regularized empirical loss over labeled training nodes.
- Graph neural networks: A two-hidden-layer GCN computes class probabilities through normalized adjacency propagation, ReLU transformation, and trainable weight matrices.
- Bilevel programming: Bilevel programs constrain outer-objective variables through an inner optimization problem and are used in hyperparameter, adversarial, multi-task, and meta-learning.
- Bilevel programming: Because inner solutions are usually unavailable in closed form, bilevel optimization can approximate them with repeated iterative dynamics such as gradient descent.When objectives and dynamics are smooth, reverse-mode differentiation through unrolled iterations computes hypergradients in O(T(d + m)).
3. Learning Discrete Graph Structures
The paper learns a discrete, sparse graph distribution jointly with GCN parameters by recasting graph-structure learning as a bilevel optimization problem. Bernoulli edge probabilities make the objectives continuous, while approximate hypergradient methods enable optimization despite intractable expectations and discrete sampling.
- Jointly Learning the Structure and Parameters: The outer variables parameterize a graph generator, while the inner variables are GCN parameters optimized for classification.The bilevel formulation jointly minimizes classification error by optimizing both the graph generator and GCN parameters.
- Jointly Learning the Structure and Parameters: Each possible edge is modeled as an independent Bernoulli variable, allowing graphs to be sampled from a distribution parameterized by θ.The resulting model represents uncertainty over discrete graph structures rather than learning only a dense adjacency matrix.
- Jointly Learning the Structure and Parameters: Taking expectations over graph structures converts the inner and outer objectives into continuous functions of the Bernoulli parameters, but exact optimization remains difficult.The inner GCN problem is non-convex, and the expectations are intractable to compute exactly.
- Jointly Learning the Structure and Parameters: The final prediction samples S graphs from Pθ and averages the corresponding GCN outputs.This empirical mean estimates the expected GCN prediction under the learned graph distribution.
- Structure Learning via Hypergradient Descent: Discrete graph sampling makes ordinary pathwise gradients inapplicable, so the method uses a biased straight-through estimator to obtain approximate hypergradients.The estimator replaces the discontinuous sampling path with an inexact smooth reparameterization.
- Structure Learning via Hypergradient Descent: The algorithm alternates between sampling graphs and optimizing GCN weights, then updating θ by projected outer-gradient descent.It returns the best-found weights together with the learned graph probability distribution.
- Structure Learning via Hypergradient Descent: To reduce the cost of fully unrolling inner optimization, hypergradients are truncated and estimated every τ iterations using warm restarts.The truncation adapts truncated back-propagation through time and addresses time and memory costs.
- Structure Learning via Hypergradient Descent: Although the hypergradients are biased by straight-through estimation and truncation, experiments find that the algorithm makes reasonable progress toward useful graph distributions.The bias is attributed to both the estimator and the truncated reverse-mode procedure.
4. Experiments
Experiments evaluate LDS on incomplete and absent graphs, comparing it with graph-based, supervised, and semi-supervised baselines. LDS achieves competitive or superior accuracy while learning sparse, non-uniform edge probabilities that reflect class membership.
- Setup and Baselines: LDS is evaluated on incomplete graphs by randomly retaining 25%, 50%, or 75% of edges in Cora and Citeseer.The experiments compare LDS with vanilla GCNs and a GCN variant that adds randomly sampled edges during optimization.
- Setup and Baselines: When no graph is available, kNN-LDS is compared with supervised, semi-supervised, and GCN baselines using induced random, dense, RBF, or k-nearest-neighbor graphs.The evaluation covers seven classification datasets and includes a dense LDS counterpart.
- Results: Up to 7 percentage-point accuracy gains are reported for LDS on incomplete graphs, including improvements when all original edges are retained.The reported result indicates that LDS can learn additional helpful edges beyond the supplied graph.
- Results: Adding random edges does not improve generalization: GCN and GCN-RND perform similarly.This comparison distinguishes learned edge probabilities from simply injecting random connectivity.
- Results: Using multiple STE hypergradient steps outperforms alternating optimization, while increasing τ to 20 adds computational cost without significant benefits.The comparison is conducted on Citeseer; τ = 0 denotes alternating minimization.
- Results: The learned graphs remain very sparse, with fewer than 0.2% of Cora edges present on average in sampled graphs.The paper links this sparsity to efficient learning in the GCN’s inner optimization loop.
- Results: kNN-LDS significantly outperforms kNN-GCN on 4 of 7 datasets and is among the most competitive methods across the evaluated datasets.Its highest gains occur on datasets with underlying graphs, and it performs slightly better than dense LDS.
- Results: LDS learns highly non-uniform edge probabilities, assigning 10 to 100 times more probability on average to edges between samples sharing the same class label.It often also assigns higher probability to edges present in the true held-out adjacency matrix.
6. Conclusion
LDS jointly learns graph structure and GNN parameters, with probabilistic edge parameters and applicability beyond the specific GCN variant used experimentally. The method remains limited by scalability, transductive-only evaluation, and unconstrained graph connectivity.
- LDS simultaneously learns graph structure and GNN parameters while maintaining reasonable computational cost.
- Although experiments use a specific GCN variant, LDS is more generally applicable to other GNNs.
- The learned graph generative model gives edge parameters a probabilistic interpretation.
- LDS currently cannot scale to large datasets, supports only the transductive setting, and does not enforce sampled graphs to be connected.Scaling would require mini-batches of nodes; adding nodes after training would require retraining from scratch.
A. Extended algorithm
The extended algorithm replaces the inner objective with iterative dynamics and explicitly computes the STE hypergradient using truncated reverse-mode differentiation. It also resamples adjacency matrices during the backward procedure.
- Algorithm 2 computes the STE hypergradient by truncated reverse-mode algorithmic differentiation.The inner objective is replaced by iterative dynamics such as stochastic gradient descent.
- The iterative dynamics Φ generates parameter iterates from an initial point w0.
- Dt and Et denote the Jacobians of the dynamics used in the extended algorithm.
- For τ = 0, the algorithm skips the loop at line 15.
- At line 16, the algorithm resamples adjacency matrices instead of reusing those computed in the forward pass.
- Algorithm 2 was implemented in TensorFlow as an extension of Far-HO.
B. On the Straight-through Estimator
LDS uses a straight-through estimator for discrete random variables by replacing hard sampling with a smooth backward-pass reparameterization. This produces generally nonzero but biased gradient estimates that can be sampled through the estimator’s randomness.
- The straight-through estimator provides a heuristic solution for discrete optimization at the cost of biased hypergradient estimates.
- For z ∼ Pθ, the estimator approximates gradients of ℓ(θ) = E_z∼Pθ h(z) using an inexact smooth reparameterization.
- When z is Bernoulli distributed, the reparameterization can be chosen as z = sp(θ, ε) = θ.
- If h is smooth in z, the estimator is well defined and generally yields nonzero quantities.
- The backward pass can be viewed as setting ∂z/∂θ to the identity or ignoring hard thresholds.
- The true gradient can be estimated by drawing one or more samples from the random estimator ĝ.
C. Additional Tables
The additional tables summarize the datasets and report numerical results for experiments with varying retained-edge percentages on Citeseer and Cora. Figure 6 visualizes the corresponding Citeseer output activations before classification.
- Table 3 lists relevant statistics for the datasets used in the experimental section.
- Table 4 reports numerical results for Citeseer and Cora across various percentages of retained edges.
- Figure 6 shows T-SNE visualizations of output activations before the classification layer on Citeseer.
D. Visualization of Embeddings
Figure 6 visualizes Citeseer embeddings from Dense-GCN, kNN-GCN, and kNN-LDS using T-SNE, with kNN-LDS achieving the best class separation.
- D. Visualization of Embeddings: The visualization compares embeddings learned by GCN and LDS-based models.
- D. Visualization of Embeddings: Figure 6 uses T-SNE to visualize Citeseer embeddings learned by Dense-GCN, kNN-GCN, and kNN-LDS.The methods appear in the figure from left to right as Dense-GCN, kNN-GCN, and kNN-LDS.
- D. Visualization of Embeddings: kNN-LDS provides the best separation among different classes in the Citeseer embedding visualization.