PaperlayerView exact revision on arXiv

Source-linked AI summary

HERALD: High-Fidelity Exemplar Retrieval with Adaptive Landmark Distillation for Heterophily-Aware Graph Condensation

Sujan Chakraborty, Priyanka Saha, Saptarshi Bej

arXiv:2609.11123v1cs.LG

TL;DR

Graph condensation seeks compact graphs that preserve node-classification performance, but WL aggregation and gradient-based approaches are poorly matched to heterophilic structure. HERALD adapts feature and node selection to measured heterophily within a gradient-free pipeline, and experiments report its strongest gains on heterophilic graphs while remaining competitive on homophilic ones.

  • Problem

    WL-based condensation can blur class-boundary information on heterophilic graphs because neighboring nodes often have different labels.

  • Method

    HERALD uses heterophily-adaptive feature selection and node scoring, then assembles exemplars with a gradient-free BONSAI-style pipeline.

  • Results

    Across eight benchmarks and four GNN architectures, HERALD achieves its largest improvements on heterophilic datasets while remaining competitive on homophilic citation networks.

  • Takeaways & Limitations

    Heterophily-aware exemplar and feature selection can preserve representative and boundary information without gradient-based bilevel condensation.

  • Takeaways & Limitations

    The framework assumes static attributed graphs, uses a global heterophily estimate, and can underperform BONSAI and GDEM for H2GCN at r = 0.0001 on homophilic citation networks.

Abstract

from arXiv · show

Graph condensation aims to produce a small surrogate graph that preserves the downstream node-classification performance of a much larger original graph. Existing methods rely on Weisfeiler-Lehman neighbourhood aggregation or gradient-based distribution matching, both of which assume that adjacent nodes share the same label, an assumption that breaks down under heterophily. We propose HERALD (High-fidelity Exemplar Retrieval with Adaptive Landmark Distillation), a gradient-free graph condensation framework that adapts the node scoring and feature selection in the condensation pipeline to the graph's measured heterophily. HERALD selects features via a joint Fisher-discriminability and activation-density criterion that down-weights aggregated representations on heterophilic graphs, and scores nodes by a weighted combination of prototype representativeness, decision-boundary proximity, and Local Intrinsic Dimensionality (LID), where the weights are driven by a smooth sigmoid function of the heterophily ratio. Nodes are then assembled into a condensed subgraph through score-ordered BFS expansion, Personalised PageRank pruning, and class rebalancing, all at an identical storage budget to BONSAI, enabling direct comparison. Experiments on eight benchmark datasets spanning homophilic and heterophilic settings show that HERALD matches or outperforms state-of-the-art condensers on heterophilic graphs and remains competitive on homophilic ones across four GNN architectures.

1 Introduction

Graph condensation reduces the cost of repeatedly training GNNs, but topology-based selection can lose discriminative boundary information under heterophily. HERALD adapts feature and node selection to heterophily while retaining a gradient-free, architecture-agnostic condensation pipeline.

  • Motivation: HERALD targets the heterophily bias in WL-based selection, where smoothing can merge structurally similar nodes with different classification roles.This can under-represent boundary nodes that heterophily-aware GNNs use for prediction.
  • HERALD: HERALD combines prototype representativeness, decision-boundary proximity, and local intrinsic dimensionality through weights adapted to graph homophily.Its feature selector jointly considers class discriminability and activation density.
  • HERALD: HERALD preserves BONSAI’s architecture-agnostic, gradient-free pipeline while replacing WL-based exemplar scoring with information-theoretic, heterophily-aware selection.The shared pipeline includes budget estimation, BFS expansion, PageRank pruning, and class rebalancing.
  • Empirical scope: Across eight homophilic and heterophilic datasets and four GNN architectures, HERALD improves heterophilic accuracy while remaining competitive on homophilic graphs.The comparison includes Random, Herding, GDEM, and BONSAI under the described evaluation.

2 Related Work

Graph condensation has progressed from heuristic and gradient-based reduction toward model-agnostic exemplar selection, but existing approaches differ in how they represent structure and preserve informative nodes. BONSAI provides the closest foundation for HERALD through WL-based exemplar coverage and graph sparsification.

  • Random sampling, Herding, and K-Center reduce datasets through representative or coverage-based heuristics without training, but they are not graph-specific condensation frameworks.Their selection criteria range from uniform sampling and class-wise mean matching to minimizing nearest-center distance.
  • Gradient-matching methods optimize synthetic graphs to reproduce training signals, while later variants address convergence, redundancy, trajectory bias, or structural limitations.GCond, EXGC, SFGC, GEOM, GCSR, and GDEM target different weaknesses in gradient- or trajectory-based condensation.
  • BONSAI selects exemplar computation trees using a submodular reverse-k-nearest-neighbour coverage objective, expands them into an induced subgraph, and sparsifies it with Personalized PageRank.The method requires no GNN training and is described as model-agnostic.
  • HERALD is most directly comparable to BONSAI because it retains the same overall gradient-free pipeline while adapting feature and exemplar selection for heterophilic graphs.The supplied passage introduces HERALD as adopting BONSAI’s overall pipeline; the detailed adaptations are developed in the HERALD section.

3 HERALD

HERALD is a budget-controlled, gradient-free condensation framework that replaces homophily-dependent selection with heterophily-aware feature and node scoring. It retains BONSAI’s assembly stages while adapting selection weights to measured cross-class connectivity.

  • Motivation: WL aggregation can mix class information across heterophilic boundaries, causing WL-space prototype selection to under-represent discriminative boundary nodes.The paper identifies this as the failure mode motivating HERALD’s feature and node-selection changes.
  • HERALD contributions: HERALD addresses heterophily with joint discriminability–density feature selection, adaptive prototype/boundary/LID scoring, and a budget-controlled assembly pipeline.Multi-hop Fisher scores are down-weighted by (1 − h)^k, while node-scoring weights depend on measured heterophily.
  • Budget-controlled assembly: HERALD uses exactly k∗ selected features and reuses BONSAI’s budget formula, BFS expansion, PPR pruning, and class rebalancing for direct storage-matched comparison.The retained feature count is anchored by BONSAI’s WL+Decision-Tree pipeline, while HERALD chooses the feature identities using its discriminativeness×density criterion.
  • Heterophily measurement: The heterophily ratio h is the fraction of cross-class edges among training nodes, with h = 0 denoting perfect homophily and h = 1 perfect heterophily.The paper gives Cora at approximately 0.002 and Roman-empire at approximately 0.97 as reference values.
  • Adaptive scoring: A sigmoid mapping of heterophily shifts scoring from prototype representativeness toward boundary proximity while retaining a lower-bounded LID diversity weight.As heterophily increases, β grows toward β0, α returns toward α0, and γ remains at least 0.5γ0.
  • Complexity: Exact LID computation is the main scalability bottleneck, requiring O(N^2F) arithmetic despite batching; approximate nearest-neighbour indexing is proposed as a possible reduction.The overall complexity is O(N^2F + NF + E), plus budget-controlled BFS and PPR costs.

4 Experimental Setup

The evaluation spans eight datasets across homophilic and heterophilic regimes, four condensation budgets, four GNN architectures, and multiple random initializations. Methods are compared under fixed splits and identical storage budgets using mean test accuracy and standard deviation.

  • Datasets: HERALD is evaluated on eight benchmark datasets covering citation, inductive, large heterophilic, and strongly heterophilic Wikipedia graphs.The benchmark suite includes Cora, CiteSeer, PubMed, Reddit, Roman-empire, Amazon-ratings, Chameleon, and Squirrel.
  • Baselines: The comparison includes Random, Herding, BONSAI, and GDEM as representative graph condensation methods.The baselines span uniform sampling, class-wise centroid matching, WL-based exemplar coverage, and spectral eigenspace matching.
  • Protocol: Each experiment keeps a fixed 56%/24%/20% train-validation-test split, varies model initialization, and reports mean test accuracy with standard deviation over five runs.Result tables highlight the best-performing condensed graph for each compression ratio and GNN architecture.
  • Budgets: All methods use the same four storage ratios, r ∈ {0.0001, 0.005, 0.01, 0.03}, relative to the original graph’s storage cost.The shared budgets are intended to ensure a fair comparison across condensation methods.
  • Evaluation models: Condensed graphs are tested with GCN, GAT, GIN, and H2GCN using 200 training epochs, Adam optimization, and architecture-specific hidden dimensions.Standard benchmarks use 128 hidden dimensions, while Reddit uses 1024.

5 Results

HERALD delivers its strongest aggregate gains at larger compression budgets, driven primarily by heterophilic datasets while remaining close to BONSAI on homophilic graphs.

  • At r = 0.03, HERALD improves on BONSAI by 1.6, 1.0, 1.4, and 2.7 points for GCN, GAT, GIN, and H2GCN, respectively.It is the best condensed method on every backbone at the three larger budgets.
  • At r = 0.0001, HERALD leads GCN, GAT, and GIN overall but trails BONSAI on H2GCN, 42.60% versus 50.11%.
  • The aggregate advantage is driven almost entirely by heterophilic datasets, while homophilic performance stays close to BONSAI.
  • Homophilic datasets: On homophilic citation networks, HERALD and BONSAI remain close, with HERALD best on all four backbones at r = 0.03.For GCN at r = 0.03, HERALD reaches 82.99% against BONSAI’s 82.01%.
  • Heterophilic datasets: HERALD is best in fifteen of sixteen heterophilic dataset-backbone cells, with BONSAI ahead only for GCN at r = 0.0001.At r = 0.03, HERALD reaches 51.36% on H2GCN versus BONSAI’s 48.62%.

6 Discussion

HERALD combines heterophily-adaptive selection, multi-hop feature filtering, complementary node signals, and gradient-free graph construction to preserve useful information across graph regimes.

  • Adaptive selection: HERALD shifts from prototype representativeness toward boundary preservation and structural diversity as heterophily increases.This adaptive weighting is intended to retain informative cross-class interactions while avoiding the homophily-specific trade-off between prototypes and structural diversity.
  • Feature selection: Multi-hop Fisher-based feature selection preserves discriminative attributes and structural context while freeing storage for additional representative nodes and edges.
  • Node scoring: Combining prototypes, decision-boundary nodes, and LID-based structural diversity preserves both representative examples and difficult classification regions.
  • Graph construction: Breadth-first expansion followed by Personalized PageRank pruning retains important local neighborhoods without unnecessary graph complexity.
  • Optimization-free condensation: HERALD is entirely gradient-free, using analytical scoring, feature ranking, graph traversal, and PageRank instead of repeated GNN backpropagation.
  • Limitations: The framework assumes static attributed graphs and uses a global heterophily estimate that may miss local structural variation.The authors suggest locally adaptive weighting for future work.
  • Limitations: At r = 0.0001 on homophilic citation networks with H2GCN, HERALD falls below BONSAI and GDEM, indicating a trade-off when very few nodes are retained.This limitation is confined to that budget-architecture combination.
  • Limitations: BFS expansion depth and feature-selection weighting remain manually selected, and broader tasks beyond node classification are left for future research.

7 Conclusion

HERALD is a gradient-free condensation framework that adapts feature selection and node scoring to heterophily while preserving efficient exemplar-based condensation. Experiments show strong cross-setting performance, with additional preprocessing cost and scope limitations remaining.

  • HERALD jointly uses prototype representativeness, decision-boundary importance, and local structural diversity to preserve representative class information and informative graph patterns.Its feature selection retains discriminative, frequently active features so more storage can support representative nodes and edges.
  • HERALD consistently produces high-quality condensed graphs across homophilic and heterophilic benchmarks, multiple GNN architectures, and varied storage budgets.The largest improvements occur on heterophilic datasets, while performance remains competitive on strongly homophilic citation networks.
  • Reddit experiments indicate that HERALD remains practical beyond medium-sized benchmarks without bilevel optimization or repeated GNN training during condensation.The method produces competitive condensed graphs at larger scale.
  • HERALD adds preprocessing cost through Local Intrinsic Dimensionality and adaptive node scoring, although this one-time cost can be amortized over repeated downstream training.Future acceleration directions include approximate nearest-neighbour search and scalable graph traversal.

B.1 Robustness to heterophily estimation

The analysis establishes that HERALD’s adaptive node scores change smoothly with estimated heterophily and that prototype-dominant selection preserves class-centroid fidelity. The section also situates these guarantees within controlled heterophilic ablations.

  • B.1 Robustness to heterophily estimation: Small heterophily-estimation errors produce proportionally small changes in final node scores when the selected feature set is fixed.The adaptive node score is Lipschitz continuous with respect to estimated heterophily.
  • B.1 Robustness to heterophily estimation: The sigmoid transition has bounded derivative, making each normalized adaptive weight Lipschitz continuous in the heterophily estimate.The proof uses |t′(h)| ≤ 2 and bounded component scores.
  • B.2 Centroid Fidelity for Prototype-Dominant Selection: Selecting the top-m prototype nodes yields an empirical centroid within distance ρ_m of the true normalized class centroid.This result supports preservation of homophilic class geometry when prototype similarity dominates the adaptive score.
  • Ablation study: The ablation study fixes storage and graph-assembly procedures while varying one design axis on moderately and strongly heterophilic datasets.Experiments use Amazon-ratings and Squirrel at r = 0.005.

C.2 Results

The ablations show that feature selection contributes most strongly to HERALD’s performance, while node-scoring components provide complementary, architecture- and heterophily-dependent information. Sensitivity experiments further assess whether results are robust to the paper’s default hyperparameters.

  • C.3.1 A1: Adaptive weighting: Adaptive weighting is not uniformly beneficial at the tested Amazon-ratings and Squirrel operating points, with effects depending on heterophily regime and architecture.On Amazon-ratings, changes are −0.02% for GCN and +0.04% for H2GCN; on Squirrel, fixed weights reduce GCN accuracy by 0.27% but increase H2GCN accuracy by 0.32%.
  • C.3.2 A2: Node-scoring components are complementary: The combined prototype, boundary, and LID score provides a stable compromise, although each component’s benefit varies by dataset and downstream architecture.Prototype similarity favors class-central exemplars, boundary scoring emphasizes inter-class transitions, and LID promotes structurally distinctive nodes.
  • C.3.2 A2: Node-scoring components are complementary: Removing LID improves H2GCN accuracy by 0.12% on Amazon-ratings and 0.61% on Squirrel but decreases GCN accuracy by 0.05% and 0.11%.The results indicate that LID-based diversity is not universally advantageous but can complement prototype and boundary information when selected-node diversity is useful.
  • C.3.4 A4: Random ranking: Random ranking produces small GCN degradations of 0.04% on Amazon-ratings and 0.27% on Squirrel, indicating that ranking contributes beyond the shared assembly pipeline.The graph structure also changes: on Amazon-ratings, random ranking yields 18,240 condensed nodes and SR=74.30%, versus 19,132 nodes and SR=77.97% for full HERALD.
  • C.3.3 A3: Feature selection: A3 causes the largest reported degradations: 1.58% for GCN and 1.16% for H2GCN on Squirrel.Replacing HERALD’s Fisher×density feature selection with BONSAI’s WL+DT procedure changes both the selected features and, on Squirrel, the condensed graph.
  • D.1 Sensitivity analysis: The sensitivity protocol fixes r = 0.005 and evaluates Cora, Amazon-ratings, and Roman-empire across GCN and H2GCN using five model seeds, with accuracy swing measuring robustness.The fixed budget is non-saturating for Cora and Amazon-ratings but near-saturating for Roman-empire; smaller swings indicate less sensitivity to hyperparameter choice.

D.2 Results

HERALD is broadly robust to reasonable hyperparameter changes, with the largest sensitivity arising from BFS depth because it changes the number of nodes admitted under the storage budget.

  • Roman-empire is saturated at SR≈99.5%, so every hyperparameter setting produces the same condensed graph and identical accuracy.Its all-axis swings are ≤0.16%, making it a control for unintended pipeline sensitivity.
  • BFS depth is the most structurally impactful parameter, reducing Amazon-ratings from 21,755 nodes at L = 1 to 17,048 at L = 4.The corresponding storage ratio falls from 88.7% to 69.4%, producing a 0.71% GCN accuracy swing.
  • Sigmoid steepness produces the largest single swing, 1.07% for Cora GCN, by changing the ranking of marginal nodes near the budget boundary.The effect is not monotonic, and Amazon-ratings swings remain at or below 0.36%.
  • LID neighbourhood size is nearly insensitive, with swings at or below 0.59% and stable node rankings even at k = 5.The default k = 10 is therefore a conservative stable choice.
  • The maximum accuracy swing is 1.07% across all tested axes, datasets, and architectures, while the median swing is 0.16%.Nineteen of 24 dataset–GNN–axis combinations have swings below 0.7%.
  • The structural analysis compares node counts, storage ratios, feature variance, class entropy, and graph statistics across condensed graphs.The supplied passages define storage ratio, normalized feature variance, class entropy, and the reported table scope.

E.4 Discussion

HERALD changes the structure of condensed graphs relative to BONSAI under matched budgets, selecting more and sparser nodes while improving diversity and, at tight budgets, class balance.

  • Storage-ratio saturation depends strongly on graph structure: Roman-empire approaches the full training subgraph, whereas dense Squirrel caps SR around 17%.At Roman-empire r = 0.01 and r = 0.03, both methods produce identical graphs with SR values of 95.20% and 99.54%.
  • HERALD selects more nodes than BONSAI at equivalent compression fractions because lower per-node feature storage leaves more budget for nodes.The reported node-count ratio ranges from 0.99 to 1.25 for HERALD relative to BONSAI.
  • HERALD’s condensed graphs are consistently sparser despite containing more nodes, because boundary and high-LID roots generate peripheral chains and trees rather than dense cliques.The text links this sparsity to reduced over-smoothing risk during neighbourhood aggregation.
  • At Amazon-ratings r = 0.0001, HERALD reaches class entropy Hc = 1.463 versus BONSAI’s 1.404, with the gap closing at larger budgets.The higher entropy is attributed to boundary-node selection and class rebalancing.
  • At Squirrel r = 0.0001, HERALD retains normalized feature variance bσ2 = 0.801 versus BONSAI’s 0.751, a gain of +0.050.The gap narrows as the budget grows, consistent with the LID term being most important for small selective subsets.

F.1 Accuracy at Scale

At Reddit scale, HERALD remains strong under aggressive compression, winning most condenser/GNN/budget comparisons while showing weaknesses at extremely small node budgets.

  • HERALD wins 13 of 16 condenser/GNN/budget cells on Reddit across four GNN architectures.The result is reported for the largest graph considered, with 232,965 nodes and 57.3M edges.
  • HERALD outperforms every competing condenser for GAT and GIN at every storage budget.For GAT it reaches 42.09% at r = 0.0001 and 43.79% at r = 0.03; for GIN it peaks at 45.10% at r = 0.01 versus BONSAI’s 42.36%.
  • HERALD is best for H2GCN at three of four ratios, reaching 45.83% at r = 0.03, but trails Random at r = 0.0001 with 32.93% versus 42.15%.The exception occurs when PPR leaves as few as 44–51 nodes.
  • For GCN, HERALD wins three of four budgets, including 47.30% at r = 0.03 versus BONSAI’s 36.99%, but BONSAI leads at r = 0.01.The r = 0.03 result is a 10.3-point margin over BONSAI.
  • The two weakest Reddit results are attributed to very small node budgets rather than a systematic weakness of HERALD.These are H2GCN at the most extreme compression and GCN at r = 0.01.

G.2 Heterophilic Datasets

The heterophilic-dataset evaluation compares HERALD and BONSAI across four benchmarks, while structural figures emphasize matched-budget node counts, density, and class balance.

  • Tables G17–G20 report node-classification accuracy for the four heterophilic benchmarks: Roman-empire, Amazon-ratings, Chameleon, and Squirrel.The supplied passages identify the corresponding result tables but do not provide their cell values.
  • Across compression fractions, HERALD consistently selects more nodes than BONSAI at the same budget because Fisher×density feature selection lowers per-node storage cost.The comparison is summarized for compression fractions r ∈ {10^-4, 5 × 10^-3, 10^-2, 3 × 10^-2}.
  • HERALD’s condensed graphs are consistently sparser at matched node count and achieve higher class entropy at tight budgets.Figure E6 compares graph density, average degree, and class-balance entropy.
Loading 2609.11123v1…