Graph condensation improved for diverse node label patterns in networks
HERALD: High-Fidelity Exemplar Retrieval with Adaptive Landmark Distillation for Heterophily-Aware Graph Condensation
Machine Learning
Summary
Graphs are used to represent networks like social media or molecules, but large graphs can be slow to analyze. One goal is to shrink these big graphs while keeping important information intact. Traditional methods assume connected nodes usually share the same label, which isn’t always true in many real-world graphs. The authors present HERALD, a new way to shrink graphs that adjusts how it picks important nodes and features based on whether connected nodes tend to differ in their labels. HERALD performs well across different types of graphs, including those with mixed or similar node labels.
What this means in practice
- •For network analysts: Create smaller graph summaries that maintain node classification accuracy even when connected nodes have different categories.
- •For data engineers: Reduce the size of large graph datasets for faster processing while preserving predictive performance on diverse graph structures.
Authors
Sujan Chakraborty, Priyanka Saha, Saptarshi Bej
Abstract
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.