Skip to content

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

Sep 2026 · arXiv.org · Vol abs/2609.11123 · 0 citations
Computer Science

TL;DR

HerALD (High-fidelity Exemplar Retrieval with Adaptive Landmark Distillation 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, is proposed.

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.

View source

Similar papers

Learning the Graph and the Embedding Together: Classifier-Independent Rewiring for Heterophilic Node Classification

An affinity-guided rewiring method that estimates the graph and the node representation together and alternates, in the spirit of expectation maximisation, between training a lightweight graph neural network on the current graph and re-weighting candidate edges under a modularity objective with a pseudo-label homophily...

Harshit Kumar, Sujan Chakraborty, Priyanka Saha et al. · 0 citations
Preprint Oct 2026

Graph Representation Learning via Adaptive Expectile Aggregation

Graph neural networks (GNNs) rely critically on neighborhood aggregation, yet conventional mean aggregation may fail to capture class-relevant distributional information, particularly in heterophilic graphs. We propose ExpectileGCN, an adaptive graph aggregation framework that introduces a learnable expectile level to...

Tian-Yi Zhu, Wei Lan · 0 citations

Beyond Fixed Features: Architecture-Dependent Sensitivity to Node Representations under Heterophily

Graph Neural Networks perform well on homophilic graphs but struggle in heterophilic settings, where connected nodes often carry dissimilar labels, so architecture and representation cannot be treated as independent evaluation factors.

Priyanath Maji, Sidharth Gaur, Rajavinoth Paul Durai · 0 citations
Open access 2026

AUGKD: Adaptive Universal Graph Knowledge Distillation

Graph data distillation frameworks have shown great potential in compressing graph representations and improving learning efficiency. Nevertheless, their robustness and generalization remain limited when applied to different graph neural network architectures. To address these limitations, we propose Adaptive Universal...

Jun-Qi Liu, Yu Xie, Tian-Jun Ma et al. · 0 citations
Book Open access Nov 2026

LNAHC: Lightweight Neural Attributed Hypergraph Clustering via Multi-hop Attributed HNCut

Attributed hypergraph clustering (AHC) is crucial for uncovering meaningful communities in complex relational data that exhibit both multi-way interactions and rich node attributes. While recent learning-based AHC methods have achieved notable advances, they suffer from three major limitations: (1) most methods decoupl...

Yi-Han Wang, Long-Long Lin, Jin Zhao et al. · 0 citations
Book Open access Nov 2026

Beyond Locality: Multi-scale Structural Tokenization for Unsupervised Community Search

Community Search (CS) aims to retrieve query-dependent cohesive subgraphs from networks, playing a crucial role in modern applications such as computing power networks and biological systems. Given the high cost of labeling, unsupervised CS has emerged as a scalable paradigm. However, existing approaches often suffer f...

Xi Yue, Chuan-Hou Sun, Ying Yin et al. · 0 citations

Related blog posts

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.