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 methods based on smoothed topology can lose classification-relevant boundary information in heterophilic graphs. HERALD addresses this with heterophily-aware feature selection and exemplar scoring, achieving its largest improvements on heterophilic benchmarks while remaining competitive on homophilic networks.

  • Problem

    WL-smoothed node-selection criteria treat structurally similar nodes as redundant, which can discard class-boundary information needed by heterophilic GNNs.

    Source: §1 · pp. 2–3

  • Method

    HERALD is a gradient-free, heterophily-adaptive condenser combining discriminability–activation-density feature selection with prototype, boundary, and LID-based node scoring.

    Source: §1 · p. 3, §3.2 · p. 7

  • Results

    HERALD achieves its largest improvements on heterophilic datasets while remaining competitive on homophilic networks across multiple GNN architectures and storage budgets.

    Source: §1 · p. 4, §7 · p. 21

  • Takeaways & Limitations

    HERALD provides competitive condensed graphs across architectures and budgets, including large-scale Reddit, without bilevel optimization or repeated GNN training during condensation.

    Source: §7 · p. 21

    HERALD assumes static attributed graphs and uses a global heterophily estimate that may miss local structural variation.

    Source: §6.6 · p. 20

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 optimization-based methods are expensive and architecture-specific, while BONSAI’s WL-based selection is biased toward homophilic structure. HERALD addresses this limitation with gradient-free, homophily-adaptive exemplar and feature selection while retaining BONSAI’s architecture-agnostic condensation pipeline.

Prior limitations

  • Optimization-based condensers can achieve extreme compression, but often require repeated full-graph GNN training and re-condensation when downstream architectures or hyperparameters change.These costs can make condensation slower than simply training on the full dataset.Source: §1 · p. 2

Prior work

  • BONSAI avoids GNN training through WL-based computation-tree selection, reverse-k-nearest-neighbor coverage, and submodular greedy selection, yielding a scalable and architecture-agnostic alternative.It is described as provably linear-time in the numbers of nodes and edges.Source: §1 · p. 2

Motivation

  • WL-based redundancy is well suited to homophilic graphs but can blur class-boundary information on heterophilic graphs, where structurally similar smoothed neighborhoods may support different classification roles.This can discard information used by heterophily-aware GNNs such as H2GCN.Source: §1 · pp. 2–3

HERALD

  • HERALD replaces BONSAI’s WL-based exemplar scoring with homophily-adaptive weights over class-prototype, decision-boundary, and local-intrinsic-dimensionality signals while retaining gradient-free condensation.The weights are derived from a lightweight edge-level estimate of graph homophily.Source: §1 · p. 3
  • As heterophily increases, HERALD shifts from prototype selection toward boundary and structural-diversity signals, while reusing BONSAI’s storage budget, BFS expansion, PageRank pruning, and class rebalancing.On strongly homophilic graphs, its weighting instead favors prototype selection; the method remains architecture-independent and avoids gradient-based bilevel optimization.Source: §1 · p. 3

Contributions and evaluation

  • HERALD also uses a budget-compatible discriminativeness × activation-density feature criterion and is evaluated against Random, Herding, GDEM, and BONSAI across eight homophilic and heterophilic datasets and four GNN architectures.The reported evaluation shows improved accuracy on heterophilic benchmarks while remaining competitive on homophilic ones and preserving optimization-free condensation.Source: §1 · pp. 3–4

2 Related Work

Graph condensation has progressed from model-agnostic coreset heuristics to gradient-, trajectory-, distribution-, structure-, spectrum-, and gradient-free approaches. HERALD most directly extends BONSAI’s efficient pipeline by replacing its homophily-biased selection components with adaptive information-theoretic criteria.

2.1 Coreset selection.

  • Random sampling, Herding, and K-Center provide training-free, model-agnostic coresets but ignore graph structure and downstream task dynamics, limiting their performance.Random sampling and Herding use uniform sampling or greedy feature-space mean matching, whereas K-Center minimizes maximum distance to a selected center.Source: §2.1 · p. 4

2.2 Gradient-matching condensation.

  • Gradient-matching methods optimize synthetic graphs against real-graph training signals, progressing from costly bi-level GCond to faster one-step DosCond, structural SGDD, and efficient EXGC.DosCond reports 15×–40× speedups over GCond, SGDD adds graphon and Laplacian-energy matching, and EXGC reduces parameter and node redundancy through variational reformulation and information bottlenecks.Source: §2.2 · pp. 4–5

2.3 Trajectory- and distribution-matching condensation.

  • Trajectory- and distribution-matching methods replace direct gradient matching with expert-trajectory alignment or receptive-field distribution matching, trading computational demands against reduced second-order optimization.SFGC matches graph-free synthetic training trajectories, GEOM corrects trajectory bias toward difficult low-homophily nodes, and GCDM matches receptive-field distributions.Source: §2.3 · p. 5

2.4 Structure-aware and spectrum-aware condensation.

  • Structure- and spectrum-aware methods preserve topology more explicitly: GCSR reconstructs interpretable adjacencies, while GDEM matches eigenbases to improve cross-architecture generalization, though both retain full-graph computation.GCSR uses self-expression with class-wise probabilistic and historical regularization; GDEM addresses spectrum bias caused by architecture-specific GNN filters.Source: §2.4 · p. 5

2.5 Gradient-free condensation.

  • BONSAI is a linear-time, fully model-agnostic gradient-free condenser that selects exemplar computation trees, expands and prunes an induced subgraph, and achieves competitive or superior accuracy on mainly homophilic benchmarks.HERALD retains BONSAI’s feature reduction, budget-constrained BFS, PageRank pruning, and class rebalancing, but replaces WL/Rev-k-NN selection and decision-tree features with homophily-adaptive information-theoretic scoring and joint discriminativeness-density selection.Source: §2.5 · pp. 5–6

3 HERALD

HERALD is a gradient-free graph-condensation framework that adapts feature selection, node scoring, and graph assembly to measured heterophily while preserving a storage-budget constraint. Its design combines discriminative dense features, prototype/boundary/diversity-aware ranking, and budget-controlled BFS, PPR pruning, and class rebalancing.

3.1 Problem Formulation

  • HERALD targets a condensed graph whose GNN classification performance remains competitive with the original graph under a prescribed storage fraction.The condensed graph is substantially smaller than the input and must satisfy C(Gc) ≤ r · C(G).Source: §3.1 · p. 6

3.2 Motivation

  • HERALD addresses heterophily by replacing aggregation-dependent selection with heterophily-aware features and node scores that preserve boundary information.WL aggregation can mix class information across heterophilic boundaries and under-represent discriminative boundary nodes; HERALD uses multi-hop Fisher weighting, prototype/boundary/LID scoring, and a shared BONSAI-style assembly pipeline.Source: §3.2 · pp. 6–7

3.3 Method Overview

  • The seven-stage pipeline measures heterophily, derives adaptive weights, selects features, ranks training nodes, then assembles the condensed graph through BFS, PPR pruning, and class rebalancing.Only feature selection and node scoring differ from BONSAI; the budget formula and assembly stages are reused to isolate heterophily-aware selection.Source: §3.3 · p. 7

3.4 Stage 1: Heterophily Measurement

  • HERALD defines heterophily h as the fraction of cross-class training-node edges, spanning h = 0 for perfect homophily to h = 1 for perfect heterophily.The reported examples are Cora with h ≈ 0.002 and Roman-empire with h ≈ 0.97.Source: §3.4 · p. 7

3.5 Stage 2: Adaptive Weight Computation

  • A sigmoid of h adapts prototype, boundary, and LID weights: homophily emphasizes prototype representativeness, whereas heterophily increases boundary influence while retaining diversity.The transition passes through t = 0.5 at h = 0.4; the base weights are (α0, β0, γ0) = (0.4, 0.4, 0.2), and γ remains bounded below at 0.5γ0.Source: §3.5 · pp. 8–9

3.6.1 Budget anchor.

  • Feature selection retains exactly BONSAI’s k∗ feature count but ranks features by joint Fisher discriminability and activation density, with higher-hop Fisher contributions decayed by (1 − h)^k.This suppresses aggregated representations when h is high, allows raw-space Fisher scores to dominate, and prevents rarely active or universally active uninformative features from scoring well.Source: §3.6.1 · pp. 9–10, §3.6.2 · p. 10, §3.6.3 · p. 10

3.7 Stage 4: Node Scoring

  • Node ranking combines cosine similarity to class prototypes, neighbour-label boundary fraction, and LID-based diversity after min-max normalization.Prototype scores favor canonical exemplars, boundary scores capture inter-class interaction patterns, and large LID values select nodes from high-dimensional feature-manifold regions.Source: §3.7.1 · p. 11, §3.7.2 · p. 11, §3.7.3 · p. 11

3.8 Stage 5: BFS Expansion

  • Assembly expands ranked roots by BFS within an upscaled 1.9B budget, prunes non-root nodes with PPR to the exact target size, and rebalances class counts using scored candidates.PPR uses αpr = 0.85 and removes nodes with the lowest structural centrality; under-represented classes are augmented and over-represented classes are trimmed.Source: §3.8 · p. 12, §3.9 · pp. 12–13, §3.10 · p. 13

4 Experimental Setup

HERALD is evaluated on eight diverse homophilic and heterophilic benchmarks against four condensation baselines under matched compression budgets. Performance is measured across four GNN architectures using fixed data splits, repeated initializations, and mean test accuracy with standard deviation.

4.1 Datasets

  • The benchmark suite contains eight datasets spanning graph sizes, feature dimensions, class distributions, and homophily levels.Table 3 summarizes the dataset statistics.Source: §4.1 · p. 14

4.1.1 Homophilic datasets.

  • Homophilic datasets comprise Cora, CiteSeer, PubMed, and the large-scale inductive Reddit benchmark.Source: §4.1.1 · p. 14

4.1.2 Heterophilic datasets.

  • Heterophilic datasets comprise Roman-empire, Amazon-ratings, Chameleon, and Squirrel.Roman-empire and Amazon-ratings are large heterophilic benchmarks, while Chameleon and Squirrel are strongly heterophilic Wikipedia page graphs.Source: §4.1.2 · p. 14

4.2 Baselines

  • HERALD is compared with four representative graph condensation methods, including Random, Herding, BONSAI, and GDEM.The baselines cover uniform sampling, class-wise centroid matching, reverse-k-nearest-neighbour coverage with BFS and Personalized PageRank pruning, and spectral eigenspace matching.Source: §4.2 · pp. 14–15

4.3.1 Data splits.

  • All datasets use fixed 56%, 24%, and 20% training, validation, and test splits generated once with a fixed random seed.Only model initialization varies across runs.Source: §4.3.1 · p. 15

4.3.2 Compression ratios.

  • Every condensation method is evaluated at identical storage budgets r ∈ {0.0001, 0.005, 0.01, 0.03} relative to the original graph.Using the same budget enables fair comparison across methods.Source: §4.3.2 · p. 15

4.3.3 Evaluation models.

  • Condensed graphs are evaluated with GCN, GAT, GIN, and H2GCN for 200 epochs using Adam at learning rate 10^-3.Weight decay is 5 × 10^-4; hidden representations use 128 dimensions except for Reddit, which uses 1024.Source: §4.3.3 · p. 15

4.3.4 Evaluation metric.

  • Each experiment uses five random initializations, reporting mean test classification accuracy with standard deviation.For each compression ratio and GNN architecture, the best-performing condensed graph is highlighted in the corresponding result tables.Source: §4.3.4 · pp. 15–16

5 Results

Across seven medium-scale datasets, HERALD is strongest at larger compression budgets, with its aggregate gains driven almost entirely by heterophilic graphs while remaining close to BONSAI on homophilic graphs. Its main exception is H2GCN at the tightest budget, especially on homophilic datasets.

5.2 Homophilic Datasets

  • On homophilic citation networks, HERALD and BONSAI remain close; HERALD is best on all four backbones at r = 0.03, but its H2GCN accuracy falls to 36.72% at r = 0.0001.At the tightest budget, HERALD leads BONSAI on GCN, GAT, and GIN, while H2GCN trails BONSAI’s 55.33% and GDEM’s 58.22%; this weakness does not appear at r ≥0.005 or on heterophilic datasets.Source: §5.2 · p. 16

5.3 Heterophilic Datasets

  • On heterophilic datasets, HERALD is best in fifteen of sixteen cells, with BONSAI ahead only on GCN at r = 0.0001, 35.13% versus 34.12%.At r = 0.03, HERALD reaches 51.36% on H2GCN, 38.59% on GCN, 36.89% on GAT, and 33.84% on GIN, exceeding BONSAI’s corresponding results.Source: §5.3 · pp. 16–17

5.1 Overall Performance

  • At r = 0.03, HERALD reaches 57.62% on GCN, 56.16% on GAT, 54.75% on GIN, and 64.18% on H2GCN, improving on BONSAI by 1.6, 1.0, 1.4, and 2.7 points, respectively.Across all seven datasets, HERALD is best on every backbone at the three larger budgets; at r = 0.0001 it leads GCN, GAT, and GIN but trails BONSAI on H2GCN, 42.60% versus 50.11%.Source: §5.1 · p. 16, Table 4 · p. 17

5.4 Reproducibility

  • The experimental code is publicly available in the HERALD GitHub repository.The reported procedures can be found at https://github.com/SujanChakraborty/HERALD.Source: §5.4 · p. 17

6 Discussion

HERALD remains effective across homophilic and heterophilic graphs by adapting feature and node selection, preserving representative, boundary, and structurally diverse information under a fixed budget. Its gradient-free construction is efficient, but current limitations include global heterophily estimates, extreme-budget behavior, manual hyperparameters, and restricted task scope.

6.1 Performance across different graph structures

  • HERALD adapts selection from prototype representativeness on homophilic graphs toward boundary preservation and structural diversity as heterophily increases, retaining effectiveness across graph regimes.This adaptation preserves informative cross-class interactions while avoiding the trade-off between class representation and structural diversity.Source: §6.1 · p. 18

6.2 Effect of adaptive feature selection

  • Adaptive multi-hop Fisher feature selection preserves discriminative attributes and structural context, freeing storage for representative nodes and edges without exceeding the budget.The method selects features before graph construction and incorporates information propagated through multiple graph neighborhoods.Source: §6.2 · pp. 18–19

6.3 Importance of boundary and diversity preservation

  • Combining prototype representativeness, boundary importance, and LID-based local diversity preserves both class exemplars and complex topology, improving generalization across GNN architectures.Boundary nodes retain informative class transitions, while LID identifies locally complex regions that prototypes may miss.Source: §6.3 · p. 19

6.4 Role of the graph construction strategy

  • Budget-respecting BFS expansion retains important local neighborhoods, while Personalized PageRank removes redundant nodes and edges without sacrificing global connectivity.The construction avoids directly connecting selected nodes or learning synthetic structures through optimization.Source: §6.4 · p. 20

6.5 Gradient-free

  • HERALD is entirely gradient-free: analytical scoring, feature ranking, graph traversal, and PageRank replace repeated backpropagation and expensive bilevel optimization.This design eliminates optimization through graph neural networks during condensation.Source: §6.5 · p. 20

6.6 Limitations

  • The framework assumes static attributed graphs, uses a global rather than locally adaptive heterophily estimate, and relies on manually selected BFS and feature-weighting hyperparameters.Future work could learn parameters from graph statistics and vary weighting across graph regions.Source: §6.6 · p. 20
  • At r = 0.0001 on homophilic citation networks, HERALD falls below BONSAI and GDEM with H2GCN, although it leads on the other three backbones and is unaffected at larger budgets or on heterophilic data.The isolated failure suggests a trade-off between HERALD’s feature and node selection and H2GCN’s ego-neighbour separation when very few nodes remain.Source: §6.6 · p. 20

7 Conclusion … Appendix B Theoretical Analysis

HERALD provides an efficient, heterophily-aware, gradient-free condensation framework that performs strongly across graph regimes and GNN architectures, while its theory supports robustness, adaptive aggregation, class separation, and submodular coverage. The appendices define the notation, formulation, methodology symbols, and algorithm-specific symbols used throughout the paper.

7 Conclusion

  • HERALD improves condensation by combining heterophily-aware feature selection with node scoring based on prototype representativeness, decision-boundary importance, and local structural diversity.The feature criterion retains discriminative, frequently active features, allowing more storage for representative nodes and edges.Source: §7 · p. 21
  • HERALD consistently produces high-quality condensed graphs across homophilic and heterophilic benchmarks, with its largest gains on heterophilic datasets and competitive performance on citation networks and Reddit.The method remains practical because condensation avoids expensive bilevel optimization and repeated GNN training.Source: §7 · p. 21
  • HERALD incurs additional preprocessing cost for Local Intrinsic Dimensionality and adaptive node scoring, but this one-time cost can be amortized across repeated downstream training.Future work targets approximate nearest-neighbour search, scalable traversal, dynamic and heterogeneous graphs, graph-level learning, and locally adaptive heterophily estimation.Source: §7 · p. 21

Appendix A Notation Summary; A.1 Graph and Problem Formulation; A.2 HERALD Methodology; A.3 Algorithm-specific Symbols

  • Appendix A summarizes the mathematical symbols used throughout the paper, including graph, condensation, storage-budget, and feature-length notation.Tables A1–A3 organize the notation across the graph formulation, HERALD methodology, and algorithm-specific components.Source: Appendix A · p. 24, Table A1 · p. 24, §A.1 · p. 24

A.1 Graph and Problem Formulation

  • The graph formulation defines the original and condensed attributed graphs, node and edge sets, features, labels, classes, training subsets, compression ratio, storage cost, and budget.These definitions establish the objects and constraints used to describe graph condensation.Source: Table A1 · p. 24, §A.1 · p. 24

A.2 HERALD Methodology

  • HERALD’s methodology notation covers adaptive weights, adjacency and degree matrices, propagated features, Fisher scores, activation density, selected features, centroids, and node-importance quantities.The notation also defines LID distances, neighbourhoods, and the combined node importance score used by the framework.Source: Table A2 · p. 24, §A.2 · p. 25

A.3 Algorithm-specific Symbols

  • Algorithm-specific notation is catalogued separately from the graph formulation and core HERALD methodology.Table A3 identifies symbols appearing specifically in Algorithms 1 and 2.Source: Table A3 · p. 26

Appendix B Theoretical Analysis

  • Theoretical analysis establishes robustness to heterophily-estimation perturbations, adaptive suppression of higher-order aggregation, prototype-preserved inter-class separation, and monotone submodular score-weighted BFS coverage.The analysis targets HERALD’s adaptive scoring and assembly pipeline rather than inherited components such as Personalized PageRank.Source: Appendix B · p. 26

B.1 Robustness to heterophily estimation … C.1 Ablation Variants

HERALD’s theoretical analysis establishes robustness of adaptive node scoring to heterophily-estimation error and fidelity of prototype-dominant selection to class geometry. Its ablation protocol isolates individual design components under controlled heterophilic settings while preserving the shared graph-assembly pipeline.

B.1 Robustness to heterophily estimation

  • Adaptive node scores change proportionally and continuously with estimated heterophily when the feature representation is fixed.The score is Lipschitz continuous in the estimated heterophily, so small estimation errors produce proportionally small score changes.Source: §B.1 · p. 27
  • The robustness guarantee follows because sigmoid-derived adaptive weights are Lipschitz, component scores lie in [0, 1], and the resulting bound is node-independent.The derivative of the sigmoid transition is bounded, and normalization uses a strictly positive quantity.Source: §B.1 · p. 27

B.2 Centroid Fidelity for Prototype-Dominant Selection

  • Selecting the top-m prototype-scored nodes yields an empirical class centroid within distance ρ_m of the original normalized centroid.This result applies when nodes are ranked solely by prototype score and establishes centroid fidelity for prototype-dominant selection.Source: §B.2 · pp. 27–28
  • Prototype-dominant selection therefore preserves class separation, with condensed centroids remaining sufficiently close to their originals relative to minimum inter-class centroid separation.The preservation result follows from the centroid-fidelity theorem and triangle-inequality bounds.Source: §B.2 · pp. 28–29

Appendix C Ablation Study

  • The ablation study evaluates HERALD at r = 0.005 on Amazon-ratings and Squirrel, spanning moderate and strong heterophily with GCN and H2GCN.Results are averaged over five random seeds; the compression regime leaves sufficient freedom for structurally distinct condensed graphs.Source: Appendix C · p. 29
  • Amazon-ratings has h ≈0.62 and Squirrel h ≈0.78, providing complementary heterophily profiles for testing HERALD’s design objective.GCN represents a conventional homophily-biased architecture, whereas H2GCN is heterophily-aware.Source: Appendix C · p. 29

C.1 Ablation Variants

  • Table C4 defines an ablation matrix in which full HERALD is configuration A and each variant changes exactly one design axis.Storage budget, BFS expansion, PPR pruning, and class rebalancing remain fixed across variants, isolating component-specific effects on downstream accuracy.Source: §C.1 · p. 29

C.2 Results … D.1.2 Experimental protocol.

The ablations identify feature selection as HERALD’s largest performance determinant, while adaptive and component-wise node scoring provide context-dependent complementary benefits. Hyperparameter sensitivity is evaluated across datasets spanning the heterophily spectrum under a fixed compression budget.

C.2 Results

  • Table C5 reports five-seed mean accuracy and standard deviation for each ablation, with differences interpreted relative to full HERALD; Table C6 shows that ranking criteria alter condensed-graph size, edges, and SR at r = 0.005.The shared assembly pipeline therefore preserves a common comparison budget while allowing ranking choices to change the resulting graph.Source: §C.2 · p. 29

C.3.1 A1: Adaptive weighting.

  • The A1 ablation finds no uniformly positive benefit from adaptive weighting: fixed weights change Amazon-ratings accuracy by −0.02% for GCN and +0.04% for H2GCN, while Squirrel changes are architecture-dependent.Because both tested datasets have h > 0.4, the ablation provides only limited coverage of the full heterophily range.Source: §C.3.1 · pp. 29–30

C.3.2 A2: Node-scoring components are complementary.

  • The A2 variants show that prototype, boundary, and LID criteria are individually competitive but not uniformly superior, while their combined score provides a stable compromise across dataset–GNN combinations.Removing LID improves H2GCN by 0.12% on Amazon-ratings and 0.61% on Squirrel but decreases GCN accuracy by 0.05% and 0.11%, respectively.Source: §C.3.2 · p. 31

C.3.3 A3: Feature selection is the dominant design axis.

  • Replacing Fisher×density feature selection with WL+DT produces Squirrel losses of 1.58% for GCN and 1.16% for H2GCN, making feature selection the dominant design axis.Amazon-ratings is unchanged because both procedures retain 300 dense float features, whereas sparse high-dimensional Squirrel exposes the advantage of raw-space discriminative selection.Source: §C.3.3 · p. 32

C.3.4 A4: Random ranking confirms the contribution of node scoring.

  • Random ranking produces modest accuracy changes—GCN decreases by 0.04% on Amazon-ratings and 0.27% on Squirrel—showing that learned scoring contributes beyond shared graph assembly.On Amazon-ratings, random ranking yields 18,240 nodes and SR=74.30%, versus 19,132 nodes and SR=77.97% for full HERALD.Source: §C.3.4 · p. 32

C.4 Summary

  • A3 causes the largest observed degradations, reducing Squirrel accuracy by 1.58% for GCN and 1.16% for H2GCN, whereas A4 causes only small GCN losses.The ablation summary attributes the dominant contribution to feature selection, with node-scoring effects smaller and architecture-dependent.Source: §C.3.3 · p. 32, §C.3.4 · p. 32, §C.4 · p. 33

Appendix D Hyperparameter Sensitivity Analysis

  • Appendix D tests whether headline results depend on precise tuning by sweeping each of four continuous hyperparameters independently while holding the remaining defaults fixed.The one-at-a-time protocol is intended to assess robustness and whether defaults are broadly sensible rather than dataset-specifically optimized.Source: Appendix D · p. 33

D.1.1 Hyperparameters swept.; D.1.2 Experimental protocol.

  • Sensitivity sweeps use r = 0.005 on Cora, Amazon-ratings, and Roman-empire, spanning h ≈0.00, 0.62, and 0.97, with GCN and H2GCN averaged over five seeds and robustness measured by accuracy swing.The tested budget is non-saturating for Cora and Amazon-ratings but near-saturating for Roman-empire; defaults and sweep grids are specified in Table D8.Source: §D.1.1 · p. 33, §D.1.2 · p. 34

D.2 Results … E.3 Class entropy

HERALD is robust to reasonable hyperparameter changes, with the largest observed accuracy swing of 1.07% and median swing of 0.16%. Structural statistics additionally evaluate storage use, feature-variance retention, and class balance in condensed graphs across representative heterophilic datasets.

D.2 Results

  • The results section reports accuracy swings across hyperparameter axes, datasets, and GNN architectures using Table D9 and full accuracy curves in Figures D1–D4.Table D9 evaluates robustness at r = 0.005 over five seeds, with Roman-empire serving as a saturated control.Source: §D.2 · p. 34, Table D9 · p. 34, §D.3 · p. 35

D.3.1 Roman-empire is invariant to all hyperparameters.

  • Roman-empire produces the same condensed graph and accuracy at every hyperparameter value because its approximately 99.5% storage ratio saturates the available budget.This saturation makes Roman-empire a control for detecting unintended pipeline sensitivity.Source: Table D9 · p. 34, §D.3.1 · pp. 35–36

D.3.2 BFS depth L is the most structurally consequential parameter.

  • BFS depth L is the most structurally consequential parameter: on Amazon-ratings, increasing L from 1 to 4 reduces the condensed graph from 21,755 to 17,048 nodes and storage ratio from 88.7% to 69.4%.The resulting 0.71% GCN and 0.70% H2GCN swings reflect changed BFS tree sizes and admitted roots, not scoring sensitivity; L = 2 matches the two-hop context of two-layer GNNs.Source: Figure D3 · p. 36, §D.3.2 · p. 37

D.3.3 The adaptive weight parameters (c, α0) are stable.

  • The adaptive parameters are stable: sigmoid steepness c reaches a maximum swing of 1.07% for Cora GCN, while prototype base weight α0 reaches 0.66% on Cora.Neither parameter changes accuracy monotonically, and both produce swings of at most 0.36% on Amazon-ratings.Source: Figure D2 · p. 35, Figure D1 · p. 35, §D.3.3 · p. 37

D.3.4 LID neighbourhood size k is robustly insensitive.

  • LID neighbourhood size k is robustly insensitive, with swings no greater than 0.59% and nearly flat accuracy curves across dataset–GNN pairs.LID rankings stabilize even at k = 5, supporting the default k = 10 as a conservative choice with limited overhead.Source: Figure D4 · p. 36, §D.3.4 · p. 37

D.3.5 Overall robustness.

  • 1.07% is the largest accuracy swing across all axes, datasets, and architectures, while 19 of 24 combinations remain below 0.7%.The median swing is 0.16%, indicating that the defaults provide a stable operating point rather than a narrowly tuned optimum.Source: §D.3.5 · p. 37

Appendix E Condensed Graph Statistics

  • HERALD and BONSAI are compared structurally on Roman-empire, Amazon-ratings, and Squirrel using diagnostic metrics summarized in Figure E5 and detailed in Tables E10–E12.The datasets span strong, moderate, and high-density heterophily, respectively.Source: Appendix E · p. 38

E.1 Storage ratio; E.2 Feature variance; E.3 Class entropy

  • The appendix evaluates storage ratio, normalized feature variance, and class entropy alongside node, edge, degree, and compression statistics across four compression fractions.Storage ratio measures budget consumption and can saturate under greedy BFS; feature-variance values near 1 indicate preserved feature spread, while higher class entropy indicates better balance.Source: §E.1 · p. 38, §E.2 · p. 38, §E.3 · p. 38

E.4 Discussion · Appendix F Results on Large-Scale Graphs

HERALD’s budget-aware feature selection fits more nodes while producing sparser, more diverse, and better-balanced condensed graphs, with effects shaped by graph density and compression. A Reddit study extends the evaluation to a 232,965-node, 57.3-million-edge graph under matched budgets and downstream GNN protocols.

E.4 Discussion

  • On Roman-empire, both condensers saturate below the target compression fraction, producing identical graphs at r = 0.01 and r = 0.03 with SR = 95.20% and 99.54%.The node budget is exhausted before the edge budget on sparse graphs, whereas dense Squirrel caps SR near 17% because edge storage dominates.Source: §E.4 · pp. 39–40
  • HERALD fits 0.99–1.25 times as many nodes as BONSAI at equivalent budgets by selecting lower-density features, with added nodes concentrated near class boundaries and high-LID regions.Lower per-node feature storage leaves more budget for representative nodes and helps explain HERALD’s heterophilic accuracy gains.Source: §E.4 · p. 40
  • HERALD’s condensed graphs are consistently sparser than BONSAI’s because boundary- and high-LID-rooted BFS expansions form chains and trees rather than dense same-class cliques.The resulting lower edge count reduces over-smoothing risk during condensed-graph aggregation.Source: §E.4 · p. 40
  • On Amazon-ratings at r = 0.0001, HERALD achieves Hc = 1.463 versus BONSAI’s Hc = 1.404, while class rebalancing closes the gap at larger budgets.Boundary-rooted BFS naturally draws neighbours from multiple classes, improving balance in the most constrained regime.Source: §E.4 · p. 40
  • At r = 0.0001 on Squirrel, HERALD raises feature diversity to bσ2 = 0.801 versus BONSAI’s 0.751, a gain of +0.050.The LID-driven term prevents collapse onto near-duplicate prototype nodes, preserving feature-manifold geometry most strongly under severe compression.Source: §E.4 · pp. 40–41

Appendix F Results on Large-Scale Graphs

  • The Reddit study tests HERALD on 232,965 nodes, 57.3M edges, 602 input features, and 41 classes using r ∈ {0.0001, 0.005, 0.01, 0.03}.All methods use identical splits, hyperparameters, evaluation procedures, storage budgets, and four downstream architectures: GCN, GAT, GIN, and H2GCN.Source: Appendix F · p. 41
  • On Reddit, HERALD retains all 500 raw features like BONSAI before PCA compresses the condensed matrix to preserve 90% of feature variance.This reallocates more storage toward representative nodes while following the same downstream evaluation pipeline.Source: Appendix F · p. 41

F.1 Accuracy at Scale · Appendix G Dataset wise results · G.1 Homophilic Datasets

On Reddit, HERALD largely preserves its advantage under extreme compression, winning most evaluated condenser–architecture–budget cells, while homophilic-dataset results are reported for Cora, CiteSeer, and PubMed. Its main weaknesses arise at the smallest node budgets rather than from systematic scoring failures.

F.1 Accuracy at Scale

  • HERALD outperforms every competing condenser for GAT and GIN at every storage budget, reaching 42.09% on GAT and 45.10% on GIN.At r = 0.0001, GAT exceeds BONSAI, Herding, and Random; on GIN, HERALD peaks at r = 0.01 versus BONSAI’s 42.36%.Source: §F.1 · p. 41
  • HERALD wins three of four H2GCN budgets and reaches 45.83% at r = 0.03, but trails Random at the smallest budget with 32.93% versus 42.15%.The smallest-budget exception is attributed to condensed graphs containing as few as 44–51 nodes after PPR pruning, leaving too little material to stabilize H2GCN training.Source: §F.1 · pp. 41–42
  • HERALD wins three of four GCN budgets, including 38.46% at r = 0.0001 and 47.30% at r = 0.03, but BONSAI leads at r = 0.01.HERALD’s 47.30% at the largest budget exceeds BONSAI’s 36.99%, whereas BONSAI records 42.20% versus HERALD’s 38.32% at r = 0.01.Source: §F.1 · p. 42
  • Reddit-scale results indicate that HERALD’s node-scoring strategy generalizes beyond medium-sized benchmarks, with its two weakest points linked to very small node budgets.The cited weaknesses are H2GCN at the most extreme compression and GCN at r = 0.01, rather than a systematic method weakness.Source: §F.1 · p. 42
  • HERALD wins 13 of 16 condenser/GNN/budget cells on Reddit across four architectures under extremely aggressive compression.Table F13 summarizes node-classification accuracy on Reddit, with the best condensed result highlighted for each architecture and compression ratio.Source: §F.1 · p. 41, Table F13 · p. 42

G.1 Homophilic Datasets

  • Tables G14–G16 report node-classification results for the homophilic datasets Cora, CiteSeer, and PubMed.Table G14 specifically presents Cora accuracy, highlighting the best condensed result for each GNN column and compression ratio.Source: §G.1 · p. 42, Table G14 · p. 43

G.2 Heterophilic Datasets

This section reports node-classification results on four heterophilic benchmarks and compares BONSAI with HERALD on condensed-graph structure and diversity. The supplied passages identify the benchmark tables and show HERALD’s structural advantages at matched budgets.

Benchmark results

  • Tables G17–G20 report node-classification accuracy (%) on Roman-empire, Amazon-ratings, Chameleon, and Squirrel.Amazon-ratings, Chameleon, and Squirrel have heterophily ratios h = 0.620, 0.770, and 0.776, respectively.Source: §G.2 · p. 43, Table G17 · p. 48, Table G18 · p. 49

Structural comparison

  • HERALD consistently selects more nodes than BONSAI at the same budget while preserving equal or greater feature diversity across all budget points.Fisher×density feature selection lowers per-node storage, and the LID diversity term prevents collapse onto a narrow feature cluster; on Squirrel at r = 10^-4, variance is 0.05 higher than BONSAI.Source: Figure E5 · p. 45
  • At matched node counts, HERALD produces sparser condensed graphs and achieves higher class-balance entropy at tight budgets than BONSAI.On Roman-empire and Amazon-ratings, HERALD reaches storage saturation earlier; on Squirrel, both methods saturate near SR ≈17% because edge storage dominates.Source: Figure E5 · p. 45, Figure E6 · p. 46

Related papers

Loading 2609.11123v1…