Source-linked AI summary
Graph Condensation for Graph Neural Networks
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, Neil Shah
TL;DR
Large graphs make GNN training and repeated retraining costly, creating a need for compact graphs that retain downstream performance. The paper introduces GCOND, which learns synthetic graph structure and node information through gradient matching. Across datasets, it reports comparable performance with graph-size reductions exceeding 99.9%.
Problem
Large-scale graphs make GNN training, storage, and repeated retraining expensive, motivating a way to reduce graph size while preserving sufficient information for GNN training.
Method
GCOND learns synthetic graph structure and node attributes by using a gradient matching objective, with sampling and mini-batch training to make optimization practical.
Results
GCOND achieves comparable performance across graph datasets and GNN architectures while reducing graph size by more than 99.9%.
Takeaways & Limitations
Condensed graphs take much less storage and can be used to train various GNN architectures efficiently.
Takeaways & Limitations
The formulation is presented for inductive node classification with all nodes labeled, though it can be generalized to transductive learning with partially labeled nodes.
Abstract
from arXiv · showhide
Given the prevalence of large-scale graphs in real-world applications, the storage and time for training neural models have raised increasing concerns. To alleviate the concerns, we propose and study the problem of graph condensation for graph neural networks (GNNs). Specifically, we aim to condense the large, original graph into a small, synthetic and highly-informative graph, such that GNNs trained on the small graph and large graph have comparable performance. We approach the condensation problem by imitating the GNN training trajectory on the original graph through the optimization of a gradient matching loss and design a strategy to condense node futures and structural information simultaneously. Extensive experiments have demonstrated the effectiveness of the proposed framework in condensing different graph datasets into informative smaller graphs. In particular, we are able to approximate the original test accuracy by 95.3% on Reddit, 99.8% on Flickr and 99.0% on Citeseer, while reducing their graph size by more than 99.9%, and the condensed graphs can be used to train various GNN architectures.Code is released at https://github.com/ChandlerBang/GCond.
1 INTRODUCTION
Large-scale graphs make GNN training, storage, and repeated retraining costly, motivating graph condensation: learning a tiny synthetic graph that preserves GNN performance. GCOND learns synthetic structure and node information, achieving substantial reductions while retaining performance across datasets and architectures.
- Motivation: Millions of graph nodes and edges create major computational costs for GNN training, especially during repeated retraining.The paper also identifies storage, visualization, and retrieval as graph-analysis concerns.
- Motivation: Graph sparsification reduces edges and graph coarsening reduces nodes, but neither directly addresses the need to preserve attributed-graph information for GNN performance.The paper notes that sparsification does not reduce nodes and that structural objectives may not optimize downstream GNN performance.
- Graph Condensation: Graph condensation learns a small synthetic graph, features, and labels whose trained GNNs aim to match performance on the original graph.The paper focuses on attributed graphs and node classification.
- Graph Condensation: 154 synthetic nodes replace Reddit’s 153,932 training nodes, illustrating reduction to 0.1% of the original node count.The synthetic nodes retain their learned connections.
- GCOND Contributions: GCOND parameterizes condensed graph structure from condensed node features and uses gradient matching as its condensation objective.The framework addresses both tractable objective design and parameterization of node features and graph structure.
- Results: 95.3% of Reddit, 99.8% of Flickr, and 99.0% of Citeseer original test accuracy is approximated with graph-size reductions exceeding 99.9%.The condensed graphs also generalize across different GNN test models and support architecture-search experiments.
2 RELATED WORK
Prior graph-reduction methods simplify edges or nodes, while dataset distillation and condensation learn small synthetic image datasets. This work connects those ideas to graph data, where both structure and node attributes must be condensed for GNN training.
- Dataset Distillation & Condensation: Dataset distillation and condensation learn small synthetic datasets intended to preserve downstream model performance.Dataset condensation improves efficiency by matching gradients on real and synthetic training data.
- Positioning: Graph condensation learns both graph structure and node attributes, extending synthetic-data condensation to attributed graphs.The paper identifies both components explicitly as part of its condensation task.
- Dataset Distillation & Condensation: These dataset methods were designed for image data and are not directly applicable to non-image graph data.The paper motivates a graph-specific condensation formulation.
- Graph Sparsification & Coarsening: Graph sparsification reduces edges while approximating distances, cuts, or eigenvalues; graph coarsening reduces nodes, typically by grouping them into super-nodes.Both approaches reduce graph size through structural approximations or node grouping.
- Graph Neural Networks: GNNs enhance node-level inference by using graph information from neighboring nodes.This neighborhood dependence distinguishes graph learning from ordinary independent-sample settings.
- Graph Structure Learning: Graph structure learning methods learn graphs from data under structural constraints, but the cited approaches do not target graphs with smaller size.The paper positions graph condensation as learning a compact graph rather than only learning connectivity.
3 METHODOLOGY
GCOND learns a small synthetic graph whose GNN training behavior matches that of the original graph. It combines gradient matching with feature-conditioned structure modeling, class-wise sampling, alternating optimization, and sparsification.
- Graph condensation: GCOND formulates condensation as learning a synthetic graph S={A′, X′, Y′}, with N′≪N, whose trained GNN matches performance on the original graph T.The framework targets attributed graphs and can extend from inductive to transductive learning with partially labeled nodes.
- Gradient matching: To avoid expensive nested-loop trajectory optimization, GCOND matches gradients from large-real and small-synthetic data at each training step.The distance aggregates layer-wise gradient discrepancies and thereby approximates step-by-step parameter matching.
- Gradient matching: GCOND fixes synthetic labels Y′ to preserve the original class distribution, reducing the difficulty of jointly learning labels, features, and structure.The three variables are interdependent, motivating this simplification.
- Graph Sampling: Class-wise mini-batch sampling uses real nodes with sampled neighbors but synthetic nodes without sampled neighbors, reducing aggregation cost and memory usage.Matching gradients separately by class is presented as easier than matching all classes jointly.
- Modeling Condensed Graph Data: The condensed adjacency A′ is parameterized from condensed features X′ through an MLP, avoiding O(N′2) free structural parameters and enabling connection inference for added nodes.The formulation can enforce symmetry for symmetric graphs and adapt to asymmetric graphs.
- Optimization and sparsification: GCOND alternates updates to X′ and the structure-generating parameters Φ, then removes adjacency entries below threshold δ to promote sparsity.The paper reports empirically better optimization from alternating Φ and X′ updates and little performance degradation for suitable δ.
4 EXPERIMENTS
Experiments show that GCOND can produce highly compressed graphs that retain strong downstream performance, outperform simpler reduction methods, and transfer across architectures. Additional analyses examine feature-only condensation, graph-size effects, and preserved structural properties.
- Comparison with Baselines: GCOND and related condensation methods outperform coreset and graph-coarsening baselines at the lowest condensation ratio on each dataset.The result is attributed to learning synthetic data with guidance from downstream tasks.
- Comparison with Baselines: 79.8%, 80.1% and 79.3% test accuracy are achieved by GCOND at 1.3%, 2.6% and 5.2% condensation ratios on Cora, versus 81.2% for the whole dataset.GCOND variants also perform well on Cora, Flickr and Reddit, while retaining a larger gap on Ogbn-arxiv.
- Comparison with Baselines: GCOND-X achieves close performance to GCOND in 11 of 15 cases while learning only condensed node features with identity adjacency.The learned features can encode node and structural information, although explicit structure remains useful for some architectures and analysis.
- Comparison with Baselines: Learning condensed node features and structural information simultaneously generally outperforms DC-Graph.On Reddit, however, DC-Graph reaches 90.5% at 0.2% condensation ratio versus 93.9% on the whole dataset, and structure-free training reaches 92.5%.
- Analysis on Condensed Data: Larger condensed graphs do not strictly yield better performance because additional parameters can increase optimization difficulty and model complexity.Performance stabilizes beyond a threshold, whereas coreset and graph-coarsening methods are more sensitive to the reduction ratio.
- Generalizability of Condensed Graphs: GCOND condensed graphs generalize well across APPNP, GCN, SGC, GraphSAGE, Cheby, GAT and MLP architectures.The paper attributes transferability across different GNN architectures to similar filtering behaviors.
- Generalizability of Condensed Graphs: Graphs condensed using different GNNs show strong transfer performance on other architectures, and neural architecture search finds reliable condensed-versus-whole-dataset performance correlations.The reported correlations for Cora, Citeseer and Ogbn-arxiv are 0.76/0.79/0.64.
- Analysis on Condensed Data: Condensed graphs contain fewer nodes, require less storage, and are less sparse than their original counterparts.For Citeseer, Cora and Flickr, homophily information is well preserved.
5 CONCLUSION
The paper studies graph condensation to reduce large graph size while preserving GNN performance. Its framework produces condensed graphs that require less storage and support efficient training across GNN architectures.
- Graph condensation targets large-real graphs and aims to maintain GNN performance on small-synthetic graphs.
- GCOND significantly reduces graph size while approximating the original performance.
- Condensed graphs take much less storage space and can efficiently train various GNN architectures.
- Future work includes improving transferability, extending condensation to graph classification, and addressing multi-label datasets.
ACKNOLWEDGEMENT
The authors acknowledge financial and institutional support for the work.
- Wei Jin and Jiliang Tang received support from the NSF, ARO, Home Depot, Cisco Systems Inc., and SNAP Inc.
- The NSF support is identified through multiple grant numbers spanning graph learning and related research.
- The acknowledgement lists both public-agency and corporate sources of support.
ETHICS STATEMENT
The paper reports no ethical issues associated with the research.
- The authors state that, to their knowledge, the paper has no ethical issues.
- The ethics statement is qualified by the authors’ stated level of knowledge.
- No additional ethical concern is identified in the statement.
A.1 DATASETS
The appendix describes datasets, experimental settings, condensation initialization, and evaluation procedures for GCOND and related variants. Experiments cover transductive and inductive node classification with synthetic graphs evaluated against original data.
- Datasets: The evaluation uses three transductive datasets—Cora, Citeseer, and Ogbn-arxiv—and two inductive datasets—Flickr and Reddit.
- Datasets: Table 6 reports dataset statistics and separates the first three datasets as transductive from the last two as inductive.
- Condensation settings: GCOND uses a 2-layer SGC with 256 hidden units for gradient matching unless otherwise specified.
- Condensation settings: GCOND models the condensed graph structure as a function of condensed node features through an MLP.
- Condensation settings: For transductive datasets, condensation ratios are selected relative to labeling rates, including 1.3%, 2.6%, and 5.2% for Cora.
- Condensation variants: GCOND produces condensed graph data (A′, X′), whereas GCOND-X and DC train using condensed features with an identity matrix as graph structure.
C.1 ABLATION STUDY
The ablations show that parameterizing the condensed adjacency matrix from node features improves optimization, while joint optimization performs worse than alternating updates.
- Different Parameterization: Modeling A′ as a function of X′ significantly improves results over treating A′ as free parameters.The relationship between condensed structure and features can ease optimization and produce better condensed graph data.
- Joint optimization versus alternate optimization: Joint optimization of Φ and X′ performs worse than alternate optimization.Joint optimization also has substantially higher standard deviation in the reported results.
- Joint optimization versus alternate optimization: Alternate optimization provides more stable performance than joint optimization.The reported standard deviation is much higher for joint optimization.
C.2 NEURAL ARCHITECTURE SEARCH
This section evaluates architecture search, computational cost, and threshold selection for GCOND. It reports APPNP search settings, scaling behavior, running time, and the sparsity–accuracy trade-off controlled by δ.
- Neural Architecture Search: 480 APPNP architectures are searched per dataset across propagation, residual coefficient, hidden dimension, and activation-function choices.The search is conducted on Cora, Citeseer, and Ogbn-arxiv, using validation accuracy to select the final architecture.
- Neural Architecture Search: Architecture search compares validation-accuracy correlation and test accuracy between models trained on condensed and original graphs.The table also distinguishes searches using the whole dataset.
- Time Complexity and Running Time: The forward pass on the original graph has complexity O(rLNd2), while the condensed-model forward process has complexity O(N′2d2).Here, N is the original node count, N′ the condensed node count, L the number of MLP layers, and r the sampled neighbors per node.
- Time Complexity and Running Time: The time complexity increases linearly with the number of nodes in the original graph.This summarizes the stated complexity analysis for gradient matching loss calculation.
- Time Complexity and Running Time: 2.4 hours are required to generate a 0.5% condensed Ogbn-arxiv graph using 1000 epochs on one A100-SXM4 GPU.The reported cost is presented as acceptable relative to the benefits of the condensed graph.
- Threshold Selection: Increasing δ increases adjacency sparsity without substantially affecting performance.The threshold is varied from 0.01 to 0.8, with test accuracy and sparsity reported in Figure 3.
C.5 DIFFERENT DEPTH AND HIDDEN UNITS.
Experiments examine depth, hidden units, propagation, transformation, and feature organization across condensed graphs. Model depth has stronger effects than hidden width, while structure remains important when features are less discriminative.
- Depth Versus Hidden Units: Changing the number of GCN layers affects model performance substantially, whereas changing the number of hidden units does not.The study varies layers from 1 to 4 and hidden units from 16 to 256 on condensed Cora and Citeseer graphs.
- Propagation Versus Transformation: Condensed Cora graphs retain good SGC performance with 3 and 4 propagation layers.The experiment varies propagation and transformation layers from 1 to 5.
- Cross-depth Performance: Deeper GNNs do not consistently produce better condensed graphs in cross-depth evaluation.Stacking more layers can involve more nodes during optimization and does not necessarily improve learned condensed graphs.
- Feature Visualization: Condensed node features are well clustered in Cora and Citeseer, with some same-class clustering in Ogbn-arxiv and Reddit.The condensed features are less discriminative in Flickr, where condensed structure information can be essential for training GNNs.
- Reference Results: The original-graph performances of various GNNs are provided as reference results.Table 14 includes GraphSAGE among the referenced architectures.
C.8 EXPERIMENTS ON PUBMED.
On Pubmed at a 0.3% condensation ratio, GCOND closely approximates original performance and generalizes across GNN architectures. The comparison indicates that leveraging condensed graph structure is important.
- Pubmed Results: 77.92% versus 79.32% test accuracy is reported for GCOND and the original graph on GCN, respectively.These results use a 0.3% condensation ratio.
- Pubmed Results: GCOND generalizes well to different GNN architectures on Pubmed.It outperforms GCOND-X and DC-Graph in the reported comparison.
- Pubmed Results: The Pubmed comparison supports leveraging graph structure information when learning a condensed structure.The authors identify this as important relative to GCOND-X and DC-Graph.