Sujan Chakraborty, Priyanka Saha, Saptarshi Bej
5 min
Graph condensation aims to compress large graphs into small, representative subgraphs that preserve node-classification performance. Existing methods often rely on Weisfeiler-Lehman (WL) neighborhood aggregation, which assumes homophily—the tendency for connected nodes to share labels. This assumption fails on heterophilic graphs, where neighbors often belong to different classes, causing traditional condensation methods to discard critical boundary information. This paper asks: can we design a gradient-free condensation framework that adapts its exemplar selection to the graph's measured heterophily?
The authors introduce HERALD (High-fidelity Exemplar Retrieval with Adaptive Landmark Distillation). HERALD replaces the static, topology-based scoring of previous methods (like BONSAI) with an information-theoretic criterion that adapts to the graph's heterophily ratio. The pipeline consists of three main components:
HERALD consistently outperforms state-of-the-art gradient-free condensers on heterophilic benchmarks (e.g., Roman-empire, Amazon-ratings, Chameleon, Squirrel) across four GNN architectures (GCN, GAT, GIN, H2GCN). While remaining competitive on homophilic datasets, HERALD achieves substantial accuracy gains in heterophilic settings by explicitly preserving boundary nodes and informative structural patterns. The method is entirely gradient-free, avoiding the expensive bilevel optimization required by gradient-matching approaches, and scales effectively to large graphs like Reddit.
As graph learning benchmarks increasingly incorporate heterophilic datasets, condensation methods biased toward homophilic structure risk under-serving a large share of real-world applications. HERALD provides a practical, architecture-agnostic, and scalable solution that bridges the performance gap between homophilic and heterophilic graph condensation, offering a robust tool for researchers seeking to reduce computational bottlenecks without sacrificing model fidelity.
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.
Alex: So it's not picking features that look good before the GNN sees them — it's picking features that stay useful after the graph structure has done its work.
Sam: Exactly. And because feature selection happens before the condensed graph is constructed, it frees up the storage budget for more nodes rather than redundant dimensions. That's the mechanism behind maintaining performance under tight compression ratios.
Alex: You mentioned this is gradient-free. Does that come with a computational cost somewhere else? [[RP_SECTION:computational-costs-and-scalability|Computational Costs and Scalability]]
Sam: There's a preprocessing cost, yes — particularly the LID computation, which scales quadratically in both nodes and features. That's the primary bottleneck. But it's a one-time cost. Unlike gradient-based condensation, which requires repeated backpropagation through the condensed graph, HERALD's pipeline is purely analytical: compute scores, rank, construct. The cost is front-loaded rather than distributed across training, which is what makes it more scalable in practice.
Alex: Though quadratic scaling still puts a ceiling on graph size.
Sam: It does, and the authors are candid about that. For truly large graphs, you'd need approximations — probably something like locality-sensitive hashing for the LID step. That's an acknowledged limitation, not a solved problem.
Alex: So where does the evidence actually land? What do the main results support? [[RP_SECTION:performance-and-limitations|Performance and Limitations]]
Sam: The load-bearing finding is that HERALD outperforms existing condensation methods on heterophilic benchmarks while remaining competitive on homophilic ones — tested across four GNN architectures. That cross-architecture consistency matters because it suggests the condensed graphs are capturing something about graph structure that generalizes, not just something that happens to fit one particular aggregation scheme. The ablations show that removing any one of the three node scores degrades performance, which supports the claim that all three components are doing distinct work rather than one carrying the others.
Alex: What's the limitation that most constrains how far you can generalize from this?
Sam: The global heterophily ratio. It's a single scalar summary of the entire graph's structural character, and real networks are rarely that uniform. You can have dense homophilic clusters embedded within a heterophilic backbone, or the reverse. HERALD applies one weighting across the whole graph, so it's making a global decision about a local problem. The authors flag this explicitly — moving toward locally adaptive scoring, where the condensation strategy shifts across neighborhoods rather than across graphs, is the natural next step. That would let the framework handle mixed-regime graphs, which is where most interesting real-world networks actually live.
Alex: So the contribution is real, but it's solving a cleaner version of the problem than the messiest real-world cases present.
Sam: That's a fair read. What HERALD establishes is that awareness of structural regime — even at a coarse global level — is enough to avoid the bias that topology-based condensation consistently falls into. It's a meaningful step toward condensation methods that don't implicitly assume homophily. The open question is whether local adaptation can be made computationally tractable, because that's where the framework would need to go to handle the full complexity of real networks. Thanks for listening to ResearchPod.