Source-linked AI summary
Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings
Yu Chen, Lingfei Wu, Mohammed J. Zaki
TL;DR
Existing graph structures may not reflect task-relevant topology, limiting graph neural networks when inputs are noisy or unavailable. IDGL jointly and iteratively learns graph structure and node embeddings, with metric learning, regularization, and an anchor-based scalable variant. Across nine benchmarks, the models consistently outperform or match state-of-the-art baselines, while IDGL-ANCH reduces complexity without compromising performance and IDGL handles adversarial, transductive, and inductive settings.
Problem
Raw graph structures may be noisy or suboptimal for downstream tasks, while graph neural networks require graph-structured data.
Method
IDGL jointly and iteratively learns graph structure and GNN parameters, using similarity metric learning, adaptive graph regularization, and anchor-based approximation.
Results
Across nine benchmarks, IDGL models consistently outperform or match state-of-the-art baselines, with IDGL-ANCH reducing complexity without compromising performance.
Takeaways & Limitations
IDGL supports more robust graph learning for adversarial graphs and both transductive and inductive learning.
Abstract
from arXiv · showhide
In this paper, we propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL), for jointly and iteratively learning graph structure and graph embedding. The key rationale of IDGL is to learn a better graph structure based on better node embeddings, and vice versa (i.e., better node embeddings based on a better graph structure). Our iterative method dynamically stops when the learned graph structure approaches close enough to the graph optimized for the downstream prediction task. In addition, we cast the graph learning problem as a similarity metric learning problem and leverage adaptive graph regularization for controlling the quality of the learned graph. Finally, combining the anchor-based approximation technique, we further propose a scalable version of IDGL, namely IDGL-Anch, which significantly reduces the time and space complexity of IDGL without compromising the performance. Our extensive experiments on nine benchmarks show that our proposed IDGL models can consistently outperform or match the state-of-the-art baselines. Furthermore, IDGL can be more robust to adversarial graphs and cope with both transductive and inductive learning.
1 Introduction
IDGL jointly learns graph structure and node embeddings for downstream prediction, addressing noisy or task-misaligned input graphs. Its iterative, regularized, and scalable variants are designed to improve performance and efficiency across graph-learning settings.
- Framework: IDGL jointly and iteratively learns graph structure and GNN parameters optimized for downstream prediction tasks.The framework alternates between improving graph structure from node embeddings and improving embeddings from graph structure.
- Framework: The method dynamically stops each mini-batch when the learned graph approaches the downstream-task-optimized graph.
- Graph construction: Multi-head self-attention with epsilon-neighborhood sparsification constructs the learned graph.
- Graph construction: IDGL learns graph metrics using a joint task-prediction and graph-regularization loss, unlike methods that optimize adjacency without downstream-task consideration.
- Scalability: IDGL-ANCH uses anchor-based approximation to reduce time and memory complexity from quadratic to linear in the number of graph nodes.
- Empirical scope: Across downstream tasks, the models consistently outperform or match state-of-the-art baselines and support adversarial, transductive, and inductive settings.
2 Iterative Deep Graph Learning Framework
IDGL jointly and iteratively learns graph structure and GNN parameters, using task-optimized embeddings to refine the graph and the graph to refine embeddings. It combines similarity metric learning, graph regularization, and anchor-based approximation to construct scalable learned graphs.
- Motivation: Noisy or incomplete graph topology may be poorly aligned with downstream prediction tasks, limiting GNN node embeddings.Existing methods often assume perfect connectivity or rely on raw feature-space graphs.
- Iterative framework: IDGL alternates graph-structure learning and GNN embedding learning so each uses the other’s improved representation.The learned structure augments the initial graph, or a kNN graph when no graph is available.
- Similarity metric learning: The framework casts graph construction as learnable similarity metric learning using weighted cosine similarity and multi-head perspectives.A learnable weight vector highlights dimensions, while multiple perspectives are averaged into the final similarity.
- Graph construction: Epsilon-neighborhood sparsification converts similarity scores into a symmetric sparse non-negative adjacency matrix by removing scores below ε.This reduces unnecessary edges and avoids potential noise from a fully connected graph.
- Scalability: Anchor-based metric learning replaces all-pairs node similarity with node-anchor affinities, reducing scalability costs for large graphs.It samples s anchors, typically with s much smaller than n, and constructs an n × s affinity matrix.
- Joint optimization: IDGL jointly minimizes task prediction loss and graph regularization loss to control learned-graph smoothness, connectivity, and sparsity.The smoothness term encourages adjacent nodes to have similar features, while additional constraints prevent the trivial zero graph.
3 Experiments
Experiments evaluate IDGL across transductive and inductive benchmarks, scalability, ablations, adversarial robustness, and convergence. IDGL generally outperforms or matches baselines, while IDGL-ANCH improves scalability and dynamic stopping performs better than fixed iteration counts.
- Experimental results: IDGL outperforms all baselines on 4 of 5 transductive benchmarks and performs well on inductive 20News and MRD tasks.IDGL-ANCH achieves comparable or better results, while IDGL demonstrates inductive capability unavailable to LDS.
- Experimental results: IDGL consistently achieves much better results than graph-learning baselines when graph topology is unavailable.On available graphs, the models achieve significantly better or competitive results despite using a vanilla GCN component.
- Ablation study: Turning off iterative learning causes a significant performance drop across datasets for both IDGL and IDGL-ANCH.The ablation also reports benefits from jointly training with graph regularization loss.
- Model analysis: IDGL remains better or comparable to GCN and LDS under random edge deletions or additions on Cora, while those baselines fail under edge additions.Lowering λ reduces reliance on the initial noisy graph through the skip-connection formulation.
- Model analysis: Both the learned adjacency matrix and accuracy converge quickly during iterative learning, without relying on oversmoothing from the two-layer GCN.The convergence analysis tracks consecutive adjacency-matrix differences across iterations.
- Training efficiency: IDGL-ANCH provides a large speedup over IDGL, while IDGL could not run on Pubmed because of memory limitations.IDGL is consistently faster than LDS overall and has comparable model size.
4 Related Work
Related work includes robust GNNs for adversarial graphs and graph construction methods for non-graph data. Existing approaches differ in assumptions, task optimization, inductive capability, and focus on graph learning.
- Robust GNNs address adversarial graphs using attention, Bayesian, graph diffusion, low-rank, or sparsity-based approaches.
- Graph construction methods have been applied to objects and words when graph-structured data is unavailable.These methods are described as optimizing graphs toward downstream tasks without explicit control of learned-graph quality.
- LDS jointly learns graphs and GNN parameters with bilevel optimization but cannot handle inductive learning.Transformer-like methods learn object relationships with multi-head attention but were not designed specifically for graph learning.
5 Conclusion
IDGL jointly and iteratively learns graph structure and embeddings optimized for the downstream task. Experiments demonstrate the proposed models’ effectiveness and efficiency.
- IDGL jointly and iteratively learns graph structure and node embeddings optimized for the downstream task.
- Experimental results demonstrate the effectiveness and efficiency of the proposed models.
Broader Impact
The paper targets applications that require jointly learning graph structures and embeddings for downstream tasks, including settings with noisy, incomplete, or non-graph-structured data. It also identifies adversarial robustness and broader real-world validation as important considerations.
- The framework is intended for applications including social network analysis, natural language processing, drug discovery, and community detection.
- The method can apply GNNs to non-graph-structured data without manual graph construction.
- The research may improve learning meaningful graphs from noisy or incomplete graphs and non-graph-structured data.
- The paper encourages applying similar approaches to specific real-world applications and studying adversarial robustness in safety- and security-critical GNN applications.
A.2 Theoretical Convergence Analysis
The iterative procedure alternates between updating the learned adjacency matrix from node embeddings and updating node embeddings from the resulting graph. Although formal convergence is difficult to prove, the paper gives a conceptual explanation based on progressively smaller changes across iterations.
- Formal convergence is challenging to prove because the proposed model can have arbitrary complexity.
- At iteration t, the adjacency matrix A^(t) is computed from the previous node embeddings Z^(t−1).
- The updated node embeddings Z^(t) are computed from a refined adjacency matrix derived from A^(t).
- The conceptual convergence argument assumes that smaller embedding changes produce smaller subsequent adjacency changes when model parameters remain fixed.
- Figures 5 shows the information flow between learned adjacency matrices and updated node embeddings during iteration.
- The first embedding update can differ more from raw features than later updates because raw features may be sparse while the first embeddings are typically dense.
A.3 Model Complexity Analysis
IDGL has quadratic scaling in the number of nodes, whereas IDGL-ANCH uses anchor-based approximations to reduce computational and memory requirements. The learned adjacency matrix and accuracy also converge quickly in the reported Cora and Citeseer studies.
- Complexity: IDGL’s overall time complexity is O(Tdn^2) under d « h and n » d.
- Complexity: IDGL-ANCH learns a node-anchor affinity matrix with O(nsh) time and space complexity.
- Complexity: IDGL-ANCH reduces space complexity from O(n^2) to O(ns) by storing an n × s affinity matrix.
- Convergence: The learned adjacency matrix and accuracy converge quickly during iterative learning in the testing phase.
- Convergence: Figure 6 reports a convergence study on Cora using single-run results.
- Convergence: Figure 7 reports a convergence study on Citeseer using single-run results.
B.2 Stopping Strategy Analysis
IDGL’s dynamic stopping criterion performs better than using a globally fixed iteration count, with the advantage becoming clearer in mini-batch training. Learned graphs also tend to connect nodes within the same class.
- Stopping strategy: Dynamic stopping outperforms using a fixed number of iterations in practice.The comparison evaluates fixed iterations against a convergence-based stopping criterion.
- Stopping strategy: The dynamic stopping advantage becomes more pronounced during mini-batch training.
- Stopping strategy: Figures 8 and 9 compare test accuracy in percent for the two stopping strategies on Cora and Citeseer.
- Learned graph visualization: IDGL mainly forms connections among same-class nodes, complementing the initial graph structure.The learned adjacency is computed from updated node embeddings optimized for downstream prediction.
B.4 Hyperparameter Analysis
The hyperparameter analysis examines λ as a trade-off between learned and initial graphs and s as the number of anchors in IDGL-ANCH. Anchor counts below an optimal value can hurt performance, while further increases may not help.
- λ analysis: λ controls the trade-off between using the learned graph structure and the initial or kNN graph structure.Its effect is evaluated on Cora in Table 5.
- s analysis: Lower s values can degrade IDGL-ANCH performance, whereas increasing s beyond an optimal value may not improve it.Here, s denotes the number of anchors, with results reported on Cora and Pubmed.
- Graph visualization: Figures 10 and 11 visualize initial or kNN graphs alongside learned graphs, with colors indicating node labels.
C.1 Data Statistics
The experiments use nine benchmarks, with data statistics summarized in Table 7 and hyperparameters for IDGL and IDGL-ANCH reported separately in Tables 8 and 9. Hyperparameters are tuned on development sets.
- Data statistics: The evaluation covers nine benchmarks spanning classification and regression tasks.Table 7 provides their data statistics; “clf.” denotes classification and “reg.” denotes regression.
- Hyperparameters: All hyperparameters are tuned on the development set.IDGL-ANCH uses the number of anchors as a transductive hyperparameter and the anchor ratio as an inductive hyperparameter.
- Hyperparameters: Tables 8 and 9 report hyperparameters for IDGL and IDGL-ANCH across all benchmarks.