ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphs
cs.LG
Submitted: 2025-12-16
Updated: 2026-08-26
Comments: Preprint
Code: https://github.com/atlaspaper16/ATLAS
License: http://creativecommons.org/licenses/by/4.0/
The gist: Graph neural networks (GNNs) excel on homophilic graphs where connected nodes share labels, but struggle with heterophilic graphs where edges do not imply similarity.
Terminology
Abstract
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.
Sources
- Layer-Neighbor Sampling -- Defusing Neighborhood Explosion in GNNs
- Adaptive Universal Generalized PageRank Graph Neural Network
- Inductive Representation Learning on Large Graphs
- Open Graph Benchmark: Datasets for Machine Learning on Graphs
- A Survey on Explainability of Graph Neural Networks
- Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods
- Revisiting Heterophily For Graph Neural Networks
- Improving Graph Neural Networks with Simple Architecture Design
- Geom-GCN: Geometric Graph Convolutional Networks
- Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond
- A critical look at the evaluation of GNNs under heterophily: Are we really making progress?
- GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring
- Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training
- Graph Attention Networks
- A Comprehensive Survey on Graph Neural Networks
- A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks