Community Detection as Adaptive Diffusion

Abstract

Community detection in attributed networks faces a structural tension: classical graph algorithms scale efficiently but ignore semantic attributes, while Graph Neural Networks (GNNs) integrate semantics yet collapse under noise and quadratic memory bottlenecks. We introduce ECHO (Encoding Communities via High-Order Operators), a scalable, self-supervised framework that treats communities as regions of adaptive diffusion on semantic manifolds. ECHO couples a topology-aware encoder router, an attention-modulated diffusion operator, a memory-sharded contrastive objective, and a chunked \(\mathcal{O}(|E|+N\!\cdot\!k_{\max})\) extraction step. Across six standard attributed benchmarks, ECHO attains the best normalized mutual information on every assortative graph, improving over the strongest of nine recent baselines (including heterophily-specific GNNs and a graph transformer) by 5–29 NMI points on Amazon Photo/Computers, Coauthor-CS, and the 70-class CoraFull. Through a controlled feature-strength study we show precisely when the diffusion operator is decisive—it recovers communities from topology when node features are weak, while feature isolation is preferable when features are strong—and that the topology-aware router is what lets a single model span both regimes. Code: https://github.com/emilioferrara/ECHO-GNN