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

📄 arXiv: 2609.11123v1 📥 PDF

作者: Sujan Chakraborty, Priyanka Saha, Saptarshi Bej

分类: cs.LG

发布日期: 2026-09-10

💡 一句话要点

提出HERALD以解决异质图的图凝聚问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 图凝聚 异质图 节点分类 无梯度方法 特征选择 Fisher可分性 局部内在维度 图神经网络

📋 核心要点

  1. 现有图凝聚方法假设相邻节点共享相同标签，但在异质图中这一假设不成立，导致性能下降。
  2. HERALD通过无梯度的方法，根据图的异质性调整节点评分和特征选择，提供了一种新的图凝聚框架。
  3. 在八个基准数据集上的实验表明，HERALD在异质图上匹配或超越了最先进的凝聚方法，并在同质图上表现出竞争力。

📝 摘要（中文）

图凝聚旨在生成一个小型代理图，以保留较大原始图的下游节点分类性能。现有方法依赖于Weisfeiler-Lehman邻域聚合或基于梯度的分布匹配，这些方法假设相邻节点共享相同标签，但在异质性情况下这一假设失效。我们提出了HERALD（高保真样本检索与自适应地标蒸馏），这是一个无梯度的图凝聚框架，能够根据图的异质性调整节点评分和特征选择。HERALD通过联合Fisher可分性和激活密度标准选择特征，并通过原型代表性、决策边界接近度和局部内在维度的加权组合对节点进行评分。实验结果表明，HERALD在异质图上与最先进的凝聚方法相当或优于其性能，并在同质图上保持竞争力。

🔬 方法详解

问题定义：本论文旨在解决图凝聚中的异质性问题，现有方法在处理异质图时假设相邻节点标签相同，导致性能下降。

核心思路：HERALD通过无梯度的图凝聚框架，根据图的异质性动态调整节点评分和特征选择，旨在提高异质图的节点分类性能。

技术框架：该方法包括特征选择、节点评分、子图组装等主要模块。特征选择基于Fisher可分性和激活密度，节点评分结合了原型代表性、决策边界接近度和局部内在维度。

关键创新：HERALD的创新在于其无梯度的设计和对异质性动态响应的能力，显著区别于依赖于邻域聚合的传统方法。

关键设计：在特征选择中，采用联合Fisher可分性和激活密度标准，节点评分通过平滑的sigmoid函数调整权重，确保在异质图中有效地选择和评分节点。整个过程在相同存储预算下进行，便于与BONSAI进行直接比较。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在八个基准数据集上的实验结果显示，HERALD在异质图上与最先进的凝聚方法相当或超越其性能，且在同质图上也保持了竞争力，展示了其广泛的适用性和有效性。

🎯 应用场景

该研究的潜在应用领域包括社交网络分析、生物信息学和推荐系统等，能够有效处理异质性数据，提升节点分类和图分析的性能。未来，HERALD可能在大规模图数据处理和复杂网络分析中发挥重要作用。

📄 摘要（原文）

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.