PaperlayerView exact revision on arXiv

Source-linked AI summary

EXGC: Bridging Efficiency and Explainability in Graph Condensation

Junfeng Fang, Xinglin Li, Yongduo Sui, Yuan Gao, Guibin Zhang, Kun Wang, Xiang Wang, Xiangnan He

arXiv:2402.05962v1cs.LG

TL;DR

Large-scale graph condensation faces computational and storage burdens, while existing methods update many parameters and retain redundancy. EXGC uses a Mean-Field approximation and Gradient Information Bottleneck with explanation methods; extensive experiments report that it outperforms baselines.

  • Problem

    Existing GCond updates many synthetic-node parameters concurrently and retains redundant nodes, amid the computational and storage burdens of large-scale graphs.

    Source: §1 · pp. 1–2

  • Method

    EXGC uses an EM-based reformulation and Mean-Field approximation for E-step efficiency, then applies GDIB with explanation methods to prioritize informative synthetic nodes.

    Source: §1 · p. 2

  • Results

    Across extensive experiments, EXGC outperforms baselines by a large margin; it is 11.3 times faster than baselines on Citeseer.

    Source: §1 · p. 2

  • Takeaways & Limitations

    EXGC is presented as a graph-condensation method that boosts efficiency while making synthetic-node selection explainable.

    Source: §5 · p. 8

    EXGC mitigates synthetic-graph redundancy during training but does not improve downstream inference speed.

    Source: F LIMITATION & FUTURE WORK · p. 13

Abstract

from arXiv · show

Graph representation learning on vast datasets, like web data, has made significant strides. However, the associated computational and storage overheads raise concerns. In sight of this, Graph condensation (GCond) has been introduced to distill these large real datasets into a more concise yet information-rich synthetic graph. Despite acceleration efforts, existing GCond methods mainly grapple with efficiency, especially on expansive web data graphs. Hence, in this work, we pinpoint two major inefficiencies of current paradigms: (1) the concurrent updating of a vast parameter set, and (2) pronounced parameter redundancy. To counteract these two limitations correspondingly, we first (1) employ the Mean-Field variational approximation for convergence acceleration, and then (2) propose the objective of Gradient Information Bottleneck (GDIB) to prune redundancy. By incorporating the leading explanation techniques (e.g., GNNExplainer and GSAT) to instantiate the GDIB, our EXGC, the Efficient and eXplainable Graph Condensation method is proposed, which can markedly boost efficiency and inject explainability. Our extensive evaluations across eight datasets underscore EXGC's superiority and relevance. Code is available at https://github.com/MangoKiller/EXGC.

1 INTRODUCTION

The introduction frames graph condensation as a way to retain information in a compact graph, but says current methods remain inefficient on large graphs because their parameters scale with node count and include redundancy. It proposes mean-field acceleration and GDIB-based node selection in EXGC.

1 INTRODUCTION

  • On Reddit, GCond’s 154-node synthetic graph reaches 91.2% test accuracy versus 93.5% for the 153,932-node original.Source: §1 · p. 1
  • Current GCond methods remain inefficient on large graphs because they concurrently update many parameters and introduce node redundancy, reaching 92.7% in some cases.Source: §1 · pp. 1–2
  • MGCond applies a Mean-Field variational approximation to the E-step’s intricate posterior probabilities to accelerate convergence.Source: §1 · p. 2
  • EXGC uses Gradient Information Bottleneck with explanation strategies such as GNNExplainer and GSAT to prioritize informative synthetic-graph nodes and exclude redundant ones.Source: §1 · p. 2
  • EXGC outperforms baselines by a large margin and is 11.3 times faster than baselines on Citeseer.Source: §1 · p. 2
  • EXGC’s performance across explainers also supports the use of graph explanation methods in downstream graph tasks, an application the authors describe as rarely explored.Source: §1 · p. 2

2 PROBLEM FORMULATION

Graph condensation seeks a compact, informative synthetic graph on which GNNs perform comparably to models trained on the original graph. The paper describes gradient matching as a way to align model training on the synthetic and real graphs.

2 PROBLEM FORMULATION

  • The target is a synthetic graph S with far fewer nodes than the original graph T, while retaining comparable GNN performance.Source: §2 · p. 2
  • T is represented by adjacency matrix A, node features X, and labels Y; S uses corresponding synthetic components A′, X′, and Y′.Source: §2 · p. 2
  • Gradient matching reduces the difference between model gradients on T and S so models trained on S converge to similar states and test performance.Source: §2 · pp. 2–3

3 METHODOLOGY

The method recasts graph condensation as EM-style gradient matching, then uses mean-field approximation to accelerate feature updates and GDIB with explanation methods to target redundancy. EXGC integrates these ideas to focus training on important synthetic-graph nodes.

3.1 The Unified Paradigm of GCond

  • Graph condensation alternates feature estimation and model-parameter optimization as E- and M-steps in an EM formulation of gradient matching.The framework seeks similar training trajectories and converged parameters for GNNs trained on real and synthetic graphs.Source: §3.1 · p. 3

3.2 Boost Efficiency: MGCond

  • Mean-field approximation treats node features as independent variables, allowing MGCond to optimize subsets across iterations instead of updating all features together.The authors identify feature estimation in the E-step as an efficiency bottleneck because the number of updated parameters scales with node count and feature dimensions.Source: §3.2 · pp. 3–4, §3.1 · p. 3

3.3 Node Redundancy and GDIB

  • At 20% of node features covered, test-accuracy improvement reaches 93.7% of its total on average, while random subsets can differ by more than 25 percentage points.The reported example range is 72.4% to 98.8%.Source: §3.3 · pp. 4–5
  • GDIB seeks a maximally informative yet compact subgraph to identify key synthetic-graph nodes for training rather than selecting nodes randomly.The objective is motivated by observed node redundancy and the limited contribution of later-trained features.Source: §3.3 · p. 5

3.4 Prune Redundancy: EXGC

  • EXGC uses post-hoc explanation methods to score node importance and forms the informative subgraph from nodes with higher scores.The method integrates this GDIB instantiation into MGCond's training paradigm.Source: §3.4 · pp. 5–6
  • EXGC reportedly often converges when only 20% of synthetic-graph nodes participate, improving computational efficiency and test accuracy.The authors attribute this to identifying pivotal nodes during early training.Source: §3.4 · p. 6

4 EXPERIMENTS

The experiments assess EXGC across benchmark graphs, condensation methods, explainers, and test architectures. They report consistent performance gains, faster training, and transferability, while comparing efficiency trade-offs among node-selection strategies.

4.1 Experimental Settings

  • The experiments cover six node-classification graphs and three graph-classification benchmarks, using GCN for gradient matching and evaluating several explainers and condensation baselines.The settings include transductive and inductive node-classification graphs.Source: §4 · p. 6, §4.1 · pp. 6–7
  • EXGC reaches optimal performance 507, 1097, 832, and 366 epochs earlier than GCond on Cora, Citeseer, Ogbn-Arxiv, and Ogbn-Product, respectively.Training can be terminated at those earlier optima.Source: Figure 3 · p. 7

4.2 Main Results (RQ1)

  • EXGC and EXGC-X consistently outperform baselines and retain original-graph performance at 0.05%–5% of graph size while accelerating inference.The reported comparisons cover six datasets.Source: §4.2 · p. 7

4.3 Generalizability on DosGCond (RQ2)

  • Across eight datasets, explainer-based selection accelerates training without evident performance decline, with 2.08%–9.26% gains reported on Cora and Citeseer.Applying the approach to DosGCond also yields substantial efficiency gains.Source: §4.3 · pp. 7–8

4.4 Selection Guidelines of EXGC (RQ3)

  • Explainer choice involves a runtime trade-off: random and gradient-based selection have similar convergence times, while explainable algorithms require extra explainer training.GSAT offers the best balance of efficiency and results; GNNExplainer is least efficient, while SA outperforms random at similar efficiency.Source: §4.4 · p. 8

4.5 Transferability of EXGC (RQ4)

  • Across five datasets, EXGC consistently outperforms GCond with lower variance across test architectures, including gains of nearly 6.0%–7.0% on Cora and about 5%–6% on Citeseer.The transferability evaluation tests APPNP, SGC, and GraphSAGE after training with a 2-layer GCN.Source: §4.5 · p. 8, Table 5 · p. 8

5 CONCLUSION

The conclusion attributes graph-condensation inefficiency to large parameter updates and redundancy. EXGC combines Mean-Field approximation with explanation-based node selection to target these issues.

5 CONCLUSION

  • Current graph-condensation inefficiency is attributed to concurrent updates of many parameters and pronounced parameter redundancy.The proposed response applies Mean-Field approximation for convergence acceleration and explanation techniques to select important training nodes.Source: §5 · p. 8
  • EXGC instantiates Gradient Information Bottleneck with leading explainers such as GNNExplainer and GSAT to select important nodes during training.The conclusion presents this as the explainable component of the method.Source: §5 · p. 8
  • The authors conclude that EXGC can markedly boost efficiency and inject explainability into graph condensation.Source: §5 · p. 8

A RELATED WORK

Related work situates EXGC among approaches to graph efficiency, explainability, sampling, distillation, and pruning. It reviews representative methods and how graph condensation differs from sampling.

A RELATED WORK

  • Large or dense graphs make GNNs inefficient, motivating research into graph sampling and graph distillation.GNNs learn representations through iterative transfer, transformation, and aggregation over graph neighbors.Source: A RELATED WORK · p. 11
  • Graph-explanation methods include causal or probabilistic models, Shapley-based substructure identification, linked explanations, and OOD-oriented explanation assessment.The cited examples include Gem, PGMExplainer, SubgraphX, CGE, and OAR.Source: A RELATED WORK · p. 11
  • Sampling selects subgraphs or prunes nodes and edges but can lose information; graph condensation instead trains on an informative synthetic set using gradient matching.The section places graph distillation in the broader lineage of dataset distillation.Source: A RELATED WORK · p. 11
  • Graph Lottery Ticket research couples pivotal core subgraphs with sparse subnetworks extracted from the original graph and GNN.The section traces this line from the Lottery Ticket Hypothesis to subsequent algorithms.Source: A RELATED WORK · p. 11

B DERIVATION OF THE EQUATION 4 AND 5

The appendix derives the objectives for optimizing model parameters and condensed features. It uses a lower bound and ELBO equivalence to relate the derivation to the existing M-step.

B DERIVATION OF THE EQUATION 4 AND 5

C DERIVATION OF THE MF APPROXIMATION

The appendix derives an optimized E-step under a mean-field approximation, working through the ELBO terms and concluding that the ELBO is maximized when KL is zero.

C DERIVATION OF THE MF APPROXIMATION

D DERIVATION OF THE GDIB

This appendix details the GDIB derivation, including a variational approximation for an intractable marginal and an instantiation that connects node selection to an l1 penalty.

D DERIVATION OF THE GDIB

  • The GDIB derivation introduces a variational approximation because the marginal distribution P(S_sub) is intractable.The approximation R(S_sub) is used to obtain an upper bound on I(S, S_sub).Source: D DERIVATION OF THE GDIB · p. 12
  • The instantiation assigns each synthetic-graph node an importance score p_i as its probability of selection into S_sub.R is specified as a Bernoulli distribution with parameter r, the per-node selection probability.Source: D DERIVATION OF THE GDIB · p. 13
  • As r approaches zero, the information constraint l_I can be instantiated as the l1-norm of p_i.The passage links this limit to the proportionality between Equation 52 and p_i.Source: D DERIVATION OF THE GDIB · p. 13

E EXPERIMENTAL SETTINGS

The experiments use several condensation, coreset, explainer, and GNN-backbone comparisons, with repeated runs to assess runtime and performance.

E EXPERIMENTAL SETTINGS

  • The evaluation uses GCN for gradient matching and compares coreset methods and condensation models, including GCond and DosGCond.Other settings assess explainer selection and transferability across APPNP, SGC, GraphSAGE, and MLP.Source: E EXPERIMENTAL SETTINGS · p. 13
  • The protocol trains methods under identical settings and measures condensed-graph informativeness by testing trained classifiers on real-graph nodes or whole graphs.Three condensed graphs are generated from distinct random seeds; GNN training on each graph is repeated three times, with mean runtime recorded.Source: E EXPERIMENTAL SETTINGS · p. 13
  • Experiments are run three times, and the reported performance is the mean with its variance.The runtime measure is also recorded as a mean across repeated training cycles.Source: E EXPERIMENTAL SETTINGS · p. 13

F LIMITATION & FUTURE WORK

EXGC reduces synthetic-graph redundancy during training but does not improve downstream inference speed; the authors identify direct node pruning and broader evaluation as future work.

F LIMITATION & FUTURE WORK

  • EXGC's redundancy reduction during training does not benefit downstream inference speed.The authors aim to prune redundant nodes directly from the synthetic-graph initialization to accelerate both training and application.Source: F LIMITATION & FUTURE WORK · p. 13
  • Future work proposes using more advanced explainers to probe EXGC's performance boundaries.Source: F LIMITATION & FUTURE WORK · p. 13
  • The authors anticipate extending EXGC to additional downstream tasks, including OOD, anomaly detection, graph generation, and recommendation.Other named areas include graph prompts learning and graph learning for science.Source: F LIMITATION & FUTURE WORK · p. 13

Related papers

Loading 2402.05962v1…