Simple Graph Condensation

Zhenbang Xiao, Yu Wang, Shunyu Liu, Huiqiong Wang, Mingli Song, Tongya Zheng

Introduction

Graph Neural Networks (GNNs) have demonstrated remarkable success in processing structured data, yet their application to industrial-scale graphs—often containing millions of nodes and edges—remains computationally prohibitive. To address this, Graph Condensation has emerged as a promising technique. The goal is to synthesize a small, representative "condensed" graph that serves as a proxy for the original. Training a GNN on this tiny fraction of data should ideally yield performance comparable to training on the full dataset.

However, the condensation process itself has historically been a bottleneck. Existing state-of-the-art methods, such as GCOND or SFGC, rely on complex alignment metrics like gradient matching, output distribution alignment, or training trajectory matching. These approaches require maintaining external trainable parameters and performing high-order computations, leading to a process that is often slow, memory-intensive, and unstable.

The SimGC Framework

SimGC (Simple Graph Condensation) is a streamlined framework designed to eliminate the overhead of traditional condensation methods. Instead of aligning intricate GNN gradients, SimGC focuses on direct representation alignment guided by a pre-trained Simple Graph Convolution (SGC) model.

Key Methodological Components

  1. SGC Guidance: The framework utilizes a pre-trained SGC—a minimalist GNN that removes non-linearities between layers—to capture the essential semantics of the original graph without the noise of complex parameter interactions.
  2. Representation Alignment: Rather than matching gradients, SimGC matches the statistical distribution (mean and standard deviation) of node features at every aggregation step (from layer 0 to $K$). This ensures the condensed graph preserves the structural hierarchy of the original data.
  3. Logit Alignment: The framework ensures that predictions (logits) generated from the condensed graph match the labels of the original graph when processed through the pre-trained SGC "teacher."
  4. Feature Smoothness Regularizer: To maintain the "homophily" (the tendency of similar nodes to connect) typical of real-world graphs, SimGC employs a Radial Basis Function (RBF) kernel to regularize feature similarity between connected nodes.
  5. Efficient Optimization: SimGC treats only the condensed graph's features and its adjacency matrix (parameterized by a simple MLP) as learnable parameters, drastically reducing optimization overhead.

Experimental Evaluation

The authors evaluated SimGC across seven diverse benchmark datasets, ranging from small citation networks to massive product-co-occurrence graphs:

  • Transductive: Cora, Citeseer, Ogbn-arxiv, and Ogbn-products (2.4M nodes).
  • Inductive: Flickr, Reddit, and Reddit2.

Key Results and Insights

  • Significant Speedups: SimGC consistently outperforms baselines in efficiency. It achieved a 10.5x speedup on Ogbn-arxiv and a 6.2x speedup on Ogbn-products compared to the previous standard, GCOND.
  • Competitive Accuracy: On the massive Ogbn-products dataset, SimGC achieved 67.0% accuracy at a 0.08% reduction rate, surpassing existing condensation methods.
  • The "Simplicity" Hypothesis: The results suggest that complex gradient-matching is not strictly necessary. Aligning basic statistical moments across layers is sufficient to transfer knowledge from a large graph to a small one.
  • Denoising Properties: On smaller datasets like Cora and Citeseer, SimGC occasionally outperforms training on the full dataset. This indicates that the condensation process may act as a form of denoising, capturing essential structures while discarding redundant or distracting information.
  • Cross-Architecture Generalization: Graphs condensed via SimGC successfully trained various architectures, including GCN, GraphSAGE, GIN, and JKNet, demonstrating that the condensed data is not overfitted to the SGC teacher.
  • NAS Acceleration: In Neural Architecture Search (NAS) experiments, searching for optimal GNN architectures on a SimGC-condensed graph was 6 times faster than searching on the original graph, with negligible loss in final performance.

Limitations and Future Directions

While SimGC is highly effective, it does face challenges with homophily bias. The feature smoothness regularizer, while beneficial for graphs like Reddit, can slightly degrade performance on graphs where connected nodes are less similar (e.g., Ogbn-products).

Future work involves extending the SimGC framework to heterogeneous graphs (containing multiple node and edge types) and hypergraphs. Additionally, exploring more sophisticated methods for adjacency parameterization beyond the current MLP-based approach could further refine the quality of the condensed topology.

Summary updated

BibTeX
@inproceedings{xiao2024simple,
  author = {Zhenbang Xiao and Yu Wang and Shunyu Liu and Huiqiong Wang and Mingli Song and Tongya Zheng},
  title = {{Simple Graph Condensation}},
  booktitle = {ECML/PKDD},
  year = {2024},
  url = {https://openreview.net/forum?id=1Kl9Eh6OLw},
}
Figure