ATLAS无需消息传递,用多尺度社区特征提升异质图与同质图的性能。
ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphs
- 用多分辨率社区特征替代传统消息传播,避免邻居膨胀问题。
- 在13个基准上表现优异,异质图上比GCN高20分,同质图上比MLP高12分。
- 自动选择最优社区粒度,支持批量训练和无邻接矩阵推理,适合大规模图学习。
图神经网络在同质图(相连节点标签相似)上表现良好,但在异质图(边不表示相似性)上效果差,且迭代消息传递因邻居膨胀导致可扩展性受限。本文提出ATLAS(自适应拓扑学习框架),通过多分辨率社区特征编码图结构,而非依赖消息传递。我们证明社区细化存在根本权衡:更细的划分虽提升标签-社区互信息,但也增加熵。我们形式化了互信息提升的条件,解释为何中等粒度通常最具预测力。ATLAS采用模量引导的自适应搜索,自动识别有信息量的社区尺度,将其一热编码后投影为可学习嵌入,并与节点属性拼接用于MLP分类。该方法支持标准小批量训练和一次预处理后的无邻接矩阵推理。在包含百万节点图的13个基准测试中,ATLAS达到竞争性或更优准确率,异质图上相比GCN最高提升20个百分点,同质图上相比MLP提升12个百分点。通过将拓扑作为显式特征,ATLAS智能适配:结构有信息时利用,弱相关时保持鲁棒,结构误导时不传播,兼具可扩展性能与可解释性拓扑洞察。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) excel on homophilic graphs where connected nodes share labels, but struggle with heterophilic graphs where edges do not imply similarity. Moreover, iterative message passing limits scalability due to neighborhood expansion overhead. We introduce ATLAS (Adaptive Topology-based Learning at Scale), a propagation-free framework that encodes graph structure through multi-resolution community features rather than message passing. We first prove that community refinement involves a fundamental trade-off: finer partitions increase label-community mutual information but also increase entropy. We formalize when refinement improves normalized mutual information, explaining why intermediate granularities are often most predictive. ATLAS employs modularity-guided adaptive search to automatically identify informative community scales, which are one-hot encoded, projected into learnable embeddings, and concatenated with node attributes for MLP classification. This enables standard mini-batch training and adjacency-free inference after one-time preprocessing. Across 13 benchmarks including million-node graphs, ATLAS achieves competitive or superior accuracy, up to 20-point gains over GCN on heterophilic datasets and 12-point gains over MLPs on homophilic graphs. By treating topology as explicit features, ATLAS adapts intelligently: leveraging structure when informative, remaining robust when weakly aligned, and avoiding propagation when structure misleads, providing both scalable performance and interpretable structural insights.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。