PaperlayerView exact revision on arXiv

Source-linked AI summary

Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data

Xin Zheng, Miao Zhang, Chunyang Chen, Quoc Viet Hung Nguyen, Xingquan Zhu, Shirui Pan

arXiv:2306.02664v2cs.LGcs.SI

TL;DR

Existing graph condensation methods jointly optimize nodes and structures, raising concerns about effectiveness and generalization. SFGC creates graph-free node sets using trajectory meta-matching and a graph neural feature score, and it achieves the best node-classification performance in 13 of 15 cases against other baselines.

  • Problem

    Existing graph condensation jointly optimizes GNN parameters, distilled node attributes, and topology, while short-range matching and architecture-dependent structures limit effectiveness and generalization.

    Source: §1 · p. 1

  • Method

    SFGC encodes topology in node attributes with identity topology, aligns long-term GNN learning behavior through training trajectory meta-matching, and dynamically evaluates data with a graph neural feature score.

    Source: §1 · p. 2, §2.3 · p. 6, §2.4 · p. 7

  • Results

    13 of 15 node-classification cases: SFGC achieves the best performance compared with all other baseline methods across five datasets and three condensation ratios.

    Source: §3.2 · p. 8

  • Takeaways & Limitations

    Across seven tested GNN architectures, SFGC's graph-free node sets perform outstandingly and are not influenced by different graph-structure convolution operations.

    Source: §3.2 · p. 9

Abstract

from arXiv · show

Graph condensation, which reduces the size of a large-scale graph by synthesizing a small-scale condensed graph as its substitution, has immediate benefits for various graph learning tasks. However, existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph, and overlook critical issues in effectiveness and generalization ability. In this paper, we advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set without explicit graph structures, i.e., graph-free data. Our idea is to implicitly encode topology structure information into the node attributes in the synthesized graph-free data, whose topology is reduced to an identity matrix. Specifically, SFGC contains two collaborative components: (1) a training trajectory meta-matching scheme for effectively synthesizing small-scale graph-free data; (2) a graph neural feature score metric for dynamically evaluating the quality of the condensed data. Through training trajectory meta-matching, SFGC aligns the long-term GNN learning behaviors between the large-scale graph and the condensed small-scale graph-free data, ensuring comprehensive and compact transfer of informative knowledge to the graph-free data. Afterward, the underlying condensed graph-free data would be dynamically evaluated with the graph neural feature score, which is a closed-form metric for ensuring the excellent expressiveness of the condensed graph-free data. Extensive experiments verify the superiority of SFGC across different condensation ratios.

1 Introduction

Large-scale graphs make repeated GNN training costly, while existing graph reduction and condensation methods face limits in what they preserve and how effectively they synthesize data. SFGC instead condenses graphs into structure-free node sets, using trajectory meta-matching and a graph neural feature score to synthesize and evaluate them.

1 Introduction

  • Large real-world graphs can contain millions of nodes and edges, making repeated GNN training through message passing computationally intensive and time-consuming.Repeated training is needed to adjust hyperparameters and construct model architectures.Source: §1 · p. 1
  • Conventional graph reduction limits derived data to information in the original graph and may preserve properties that are not optimal for downstream GNN training.These methods include sampling, coresets, sparsification, and coarsening.Source: §1 · p. 2
  • Existing graph condensation jointly optimizes GNN parameters, node attributes, and topology, while short-range gradient matching and architecture-dependent structures limit effectiveness and generalization.Different GNN convolution operations can make condensed graphs vulnerable to overfitting specific architectures.Source: §1 · p. 2
  • SFGC synthesizes graph-free node sets by encoding topology in node attributes and reducing the condensed topology to an identity matrix.Its two components are training trajectory meta-matching and a graph neural feature score for dynamic evaluation.Source: §1 · pp. 2–3
  • SFGC uses trajectory meta-matching to align long-term GNN learning behavior and a closed-form graph neural feature score to evaluate condensed data and select a representative.The feature score is derived from GNTK ridge-regression solutions.Source: §1 · pp. 2–3

2 Structure-Free Graph Condensation

SFGC condenses a large graph into a node set with identity topology, implicitly encoding structural information in node attributes. It combines long-term training-trajectory matching for synthesis with a GNTK-based score for selecting condensed data.

2.1 Preliminaries

  • Conventional graph condensation jointly optimizes condensed nodes, learned structure, and GNN parameters, creating a complex nested objective that challenges convergence and expressiveness.The condensed graph includes nodes, adjacency, and labels; SFGC removes the learned structure component.Source: §2.1 · pp. 3–4

2.2 Overview of SFGC Framework

  • SFGC synthesizes node attributes that implicitly encode topology, fixes the condensed topology to identity, and selects the candidate with the smallest graph neural feature score.The framework couples graph-free data synthesis with dynamic evaluation.Source: §2.2 · p. 5

2.3 Training Trajectory Meta-matching

  • Offline expert parameter trajectories guide long-term matching between large-graph and condensed-data GNN learning behaviors across different parameter initializations.The expert trajectories are pretrained on the large graph, stored as a parameter distribution, and sampled during condensation.Source: §2.3 · pp. 5–6
  • Long-term meta-matching avoids short-range fitting to particular optimization steps, while offline parameter sampling reduces gradient-computation and storage costs during condensation.The method replaces learnable condensed adjacency with fixed identity, reducing the optimization from triple-level to bi-level.Source: §2.3 · p. 6

2.4 Graph Neural Feature Score

  • The graph neural feature score is a closed-form GNTK ridge-regression error measuring prediction fit on a large-graph validation subgraph, without iterative GNN training.SFGC uses the score to evaluate and select condensed graph-free data.Source: §2.4 · p. 7

3 Experiments

Experiments compare SFGC with graph-size-reduction baselines and structure-synthesizing variants, then assess its evaluation efficiency and performance across GNN architectures. SFGC leads in most node-classification cases and performs well across the tested architectures.

3.1 Experimental Settings

  • Evaluation uses five datasets under transductive or inductive settings, three condensation ratios, and repeated testing with a default two-layer GNN.The reported metric is average node-classification ACC% with standard deviation.Source: §3.1 · p. 7

3.2 Experimental Results

  • SFGC achieves the best node-classification performance in 13 of 15 cases across five datasets and three condensation ratios.It also exceeds the full-dataset performance on Cora and Citeseer.Source: §3.2 · p. 8, Table 1 · p. 8
  • SFGC outperforms the tested structure-synthesizing variants; the best kNN neighbor count varies by dataset and condensation ratio.The comparison includes kNN variants at k = 1, 2, and 5, a continuous-structure variant, and a parameterized-structure variant.Source: Figure 3 · p. 8, §3.2 · p. 9
  • For Flickr at r = 0.1%, γgnf evaluation takes 0.015s versus 0.845s for iterative training; for Ogbn-arxiv at r = 0.05%, it takes 0.042s versus 4.264s.The iterative comparison includes all training epochs up to the best test performance.Source: §3.2 · p. 9
  • Condensed on GCN, SFGC data achieves outstanding performance across seven tested GNN architectures, including MLP.The authors attribute this generalization to reducing the graph structure to the identity matrix.Source: §3.2 · p. 9, Table 2 · p. 9

4 Conclusion

The conclusion presents SFGC as a structure-free way to condense large graphs into compact node sets, with reported effectiveness and generalization across large condensation ratios. The appendix reviews related reduction methods and outlines potential application scenarios.

4 Conclusion

  • SFGC combines training-trajectory meta-matching and graph neural feature score evaluation to synthesize graph-free node sets, with experiments reporting effectiveness and generalization at large condensation ratios.The authors identify extending condensation from nodes in one graph to graph sets as future work.Source: §4 · p. 10

Appendix

  • The appendix supplies additional related-work, application, dataset, method-analysis, and experimental details.It also includes additional results.Source: Appendix · p. 16

A Related Works

  • Prior graph-size reduction methods sample or select nodes, or preserve selected graph properties; the paper contrasts these approaches with directly optimizing condensed data.The related-work discussion notes that sampled information is constrained by the original graph and preserved properties may not suit downstream GNN tasks.Source: A Related Works · p. 16

B Potential Application Scenarios

  • Potential application scenarios include graph neural architecture search, privacy protection, adversarial robustness, and continual learning.The paper describes these as potential benefits rather than experimental demonstrations in this section.Source: B Potential Application Scenarios · pp. 16–17

C Dataset Details

The dataset-statistics discussion reports that SFGC removes graph edges while retaining topology-related context in node attributes.

C Dataset Details

  • SFGC reduces the condensed data's edge count to zero while its node attributes retain topology information.The passage says both SFGC and GCOND reduce nodes, edges, and storage compared with large-scale graphs.Source: C Dataset Details · p. 17, Table A1 · p. 17

D More Analysis of Structure-free Paradigm

The analysis argues that structure-free condensation preserves the relevant prediction target while transferring graph information through GNN parameters. SFGC therefore represents the condensed data as nodes without explicitly condensed structures.

Comparisons

  • The section includes a statistic comparison of GCOND [27] condensed graphs and SFGC condensed graph-free data.It also includes a dynamic-tensor memory comparison between online GCOND [27] and SFGC.Source: Table A2 · p. 18, Figure A1 · p. 19

Statistical Learning

  • Learning structures as A′ ∈ ψ(X′) leaves the target posterior Q(Y′ | X′) unchanged, supporting structure-free condensation.The statistical-learning analysis presents this as a rationale for directly synthesizing graph-free data.Source: D More Analysis of Structure-free… · p. 18

Information Flow

  • SFGC transfers large-graph node and topology information through GNN parameter trajectories into a compact node set without structures.The paper argues that condensing structures does not inherit more information and that topology is implicitly encoded in discriminative node attributes.Source: D More Analysis of Structure-free… · p. 18

E.1 Time Complexity Analysis & Dynamic Memory Cost Comparison

SFGC has lower stated time complexity than GCOND, attributed to avoiding adjacency-matrix calculations. The comparison also reports reduced online memory and computation costs from offline parameter matching.

Time Complexity

  • SFGC’s stated time complexity is TKO(LN′d^2 + LN′d), versus GCOND’s at least TKO(LN′^2d + LN′d) + TKO(N′^2d^2).Both methods also incur an extra TKO(LEd + LNd^2) offline expert-training cost; the paper attributes SFGC’s lower complexity mainly to avoiding O(LN′^2d) adjacency-matrix calculations.Source: §E.1 · p. 19

Running-Time Comparison

  • The paper reports that SFGC has smaller time complexity than GCOND, mainly because its structure-free paradigm avoids adjacency-matrix-related O(LN′2d) calculations, and says Table A3’s condensation-time comparison supports SFGC’s superiority.Source: §E.1 · p. 19

Dynamic Memory Cost

  • SFGC’s offline parameter-matching scheme significantly alleviates heavy online memory and computation costs compared with GCOND.The comparison considers memory across stages before, during, and after outer optimization.Source: §E.1 · p. 19

E.2 Effectiveness of Graph Neural Feature Score in SFGC

The graph neural feature score γgnf selects condensed data at effective meta-matching steps. Its GNTK-based closed-form evaluation saves learning time relative to iterative GNN training across datasets.

Evaluation Setup

  • The fixed-interval evaluation uses long meta-matching runs, with 1000, 2000, and 3000 steps selected empirically to allow sufficient learning of the expert-training-trajectory parameter distribution.These interval-step results are compared with data selected by γgnf.Source: §E.2 · p. 19, Table A4 · p. 20

Selection Effectiveness

  • γgnf selects condensed graph-free data with superior effectiveness at the best meta-matching steps.The evaluation compares metric-selected checkpoints with fixed intervals of 1000, 2000, and 3000 steps.Source: §E.2 · pp. 19–20, Table A4 · p. 20

Evaluation Time

  • The GNTK-based closed-form γgnf evaluation significantly saves learning time across all datasets versus iterative GNN training.For Flickr at r = 0.1%, iterative training takes 0.845s for 200 epochs, the optimal parameter setting under that condensation ratio.Source: §E.2 · p. 20, Figure A2 · p. 20

E.3 Analysis of Different Meta-matching Ranges

On Ogbn-arxiv at r = 0.05%, the tested student–expert step combinations have an optimum, and the reported best node-classification performance occurs at 600 student and 1800 expert steps.

Step-Combination Results

  • On Ogbn-arxiv at r = 0.05%, 600 student steps and 1800 expert steps yield the best node-classification performance among the tested combinations.Data quality and expressiveness vary moderately across the tested step combinations, without drastic variance.Source: §E.3 · p. 20, Figure A3 · p. 21
  • The analysis varies q student steps in GNNS and p expert steps in GNNT to assess long-term meta-matching ranges.The tested combinations are shown for Ogbn-arxiv at r = 0.05%.Source: §E.3 · p. 20, Figure A3 · p. 21

Hyperparameters

  • Table A5 lists p and q step settings, outer-level meta-matching learning rate, and inner-level GNNS learning rate ζ.The inner-level rate is identified as the step size.Source: §E.3 · p. 20, Table A5 · p. 21

E.4 Performance on Graph Node Clustering Task

SFGC-generated graph-free data supports graph node clustering on Cora and Citeseer, with results comparable to many clustering baselines despite no clustering-specific condensation objective.

E.4 Performance on Graph Node Clustering Task

  • Classification-task condensed data trains a GCN that then clusters the original large-scale graph on Cora and Citeseer.The clustering results are reported using C-ACC, NMI, F1, and ARI.Source: §E.4 · p. 21
  • SFGC-condensed data achieves results comparable to many graph node clustering baselines without a clustering-specific condensation objective.The performance comparisons cover Cora and Citeseer.Source: §E.4 · pp. 21–22, Table A6 · p. 21, Table A7 · p. 22
  • The authors interpret the clustering results as evidence that classification-derived graph-free data transfers to other tasks and represents the original graph informatively.Source: §E.4 · p. 22

E.5 Visualization of Our Condensed Graph-free Data

t-SNE visualizations show clustered patterns in SFGC's condensed graph-free data, with the observed pattern varying by dataset scale and condensation ratio.

E.5 Visualization of Our Condensed Graph-free Data

  • On Cora and Citeseer, condensed graph-free data shows a well-clustered t-SNE pattern; larger datasets show implicit clusters within the same class.Source: §E.5 · p. 22
  • The visualizations support the authors' characterization of the synthesized node attributes as discriminative and representative of large-scale graph information.Source: §E.5 · p. 22

Related papers

Loading 2306.02664v2…