Community detection in attributed networks faces a fundamental divide: topological algorithms ignore semantic features, while Graph Neural Networks (GNNs) encounter devastating computational bottlenecks. Specifically, GNNs suffer from a Semantic Wall of feature over smoothing in dense or heterophilic networks, and a Systems Wall driven by the O(N^2) memory constraints of pairwise clustering. To dismantle these barriers, we introduce ECHO (Encoding Communities via High order Operators), a scalable, self supervised architecture that reframes community detection as an adaptive, multi scale diffusion process. ECHO features a Topology Aware Router that automatically analyzes structural heuristics sparsity, density, and assortativity to route graphs through the optimal inductive bias, preventing heterophilic poisoning while ensuring semantic densification. Coupled with a memory sharded full batch contrastive objective and a novel chunked O(N \cdot K) similarity extraction method, ECHO completely bypasses traditional O(N^2) memory bottlenecks without sacrificing the mathematical precision of global gradients. Extensive evaluations demonstrate that this topology feature synergy consistently overcomes the classical resolution limit. On synthetic LFR benchmarks scaled up to 1 million nodes, ECHO achieves scale invariant accuracy despite severe topological noise. Furthermore, on massive real world social networks with over 1.6 million nodes and 30 million edges, it completes clustering in mere minutes with throughputs exceeding 2,800 nodes per second matching the speed of highly optimized purely topological baselines. The implementation utilizes a unified framework that automatically engages memory sharded optimization to support adoption across varying hardware constraints. GitHub Repository: https://github.com/emilioferrara/ECHO-GNN
Figures & tables
Figure 1. The ECHO architecture pipeline. Phase 1 actively prevents heterophilic poisoning and semantic starvation by routing the graph based on structural heuristics. Phase 2 extracts multi-scale representations and bypasses training memory limits via tensor sharding, while Phase 3 extracts communities via chunked topological filtering.
Algorithm
Time Complexity
Space Complexity
K-Means ( MacQueen, 1967 )
O(I⋅N⋅d⋅Kclus)
O(N⋅d)
LPA ( Raghavan et al., 2007 )
O(I⋅∣E∣)
O(N)
Leiden ( Traag et al., 2019 )
O(NlogN)
O(∣E∣)
LINE ( Tang et al., 2015 )
O(I⋅∣E∣)
O(N⋅d)
DGI ( Veličković et al., 2019 )
O(K⋅∣E∣⋅d)
O(N2)∗
MVGRL ( Hassani and Khasahmadi, 2020 )
O(N2)
O(N2)
Table 1. Complexity Comparison: ECHO vs. Benchmark Baselines
Dataset
Domain
Nodes
Edges
Features
Classes
Ref.
Chameleon
Wikipedia
2,277
31,421
2,325
5
( Pei et al., 2020 )
Actor
Co-occurrence
7,600
26,659
932
5
( Pei et al., 2020 )
Amazon Photo
E-commerce
7,650
119,081
745
8
( Shchur et al., 2018 )
Amazon Computers
E-commerce
13,752
491,722
767
10
( Shchur et al., 2018 )
Coauthor CS
Collaboration
18,333
81,894
6,805
15
( Shchur et al., 2018 )
CoraFull
Citation
19,793
63,421
8,710
70
( Bojchevski and Günnemann, 2018 )
Table 2. Summary of Real-World Attributed Networks
Size ( N )
Edges ( ∣E∣ )
LPA
LINE
DGI
MVGRL
SDCN
ECHO
500
4,962
0.1492
0.2126
0.1264
0.1188
0.2794
0.2947
1,000
9,943
0.1784
0.2924
0.1693
0.1723
0.2241
0.3749
2,500
24,917
0.1561
0.1897
0.1078
0.1247
0.2342
0.3277
5,000
49,856
0.1912
0.3463
0.1607
0.1677
0.1737
0.3663
Table 3. SOTA LFR Synergy Results at the Critical Boundary ( μ=0.5 ): NMI and Network Statistics
Dataset
N
∣E∣
LPA
LINE
DGI
ECHO
Chameleon
2,277
31,421
0.1460
0.1011
0.0515
0.1701
Actor
7,600
26,659
0.0084
0.0009
0.0147
0.0151
Amazon Photo
7,650
119,081
0.5484
0.5608
0.5401
0.7290
Amazon Computers
13,752
491,722
0.4521
0.4081
0.2647
0.5957
Coauthor CS
18,333
81,894
0.5281
0.4447
0.7071
0.7042
CoraFull
19,793
63,421
0.4521
0.3431
0.4356
0.5114
Table 4. Comprehensive Benchmark Performance (NMI) and Network Statistics
Figure 2. Evolution of Cluster Geometry on Cora. Left: Raw bag-of-words features exhibit significant overlap, explaining the poor performance of feature-only methods. Right: ECHO embeddings demonstrate clear manifold separation, where the academic disciplines are pulled into distinct, cohesive islands with minimal inter-class noise.
Figure 3. High-Density Manifold Separation on Amazon Computers. Despite an average degree of 36, ECHO identifies distinct product categories. The use of a topology-constrained MLP ( K=0 ) prevents feature collapse, maintaining sharp boundaries between disparate product clusters (e.g., Laptops vs. Desktops).
Detection of overlapping communities is essential for modelling networks in which nodes participate simultaneously in multiple structural or functional groups. Existing graph neural network approaches commonly rely on local message passing, which can obscure community boundaries through smoothing and limit the representation of structurally relevant long-range dependencies. We introduce Diffusion-Induced Spatial Attention Community Detection (DISCO), a deep-learning framework that combines a structural prior derived from influence spreading dynamics, sparse multi-head attention, and non-negative community-affiliation learning. The prior identifies candidate interactions beyond immediate graph neighbours and biases attention according to their structural proximity, while a Bernoulli-Poisson edge-reconstruction objective enables overlapping community inference from node attributes and structural profiles, or both. Benchmark experiments show that DISCO performs competitively against established graph convolutional and graph attention approaches across different input configurations. To demonstrate its practical applicability, we present a proof-of-concept cybersecurity use case in which changes between community assignments inferred from consecutive communication-network snapshots provide an interpretable anomaly signal. Temporal community similarity identifies structural deviations, while node-level contributions help locate the devices associated with them. DISCO therefore provides both a flexible method for overlapping community detection and a foundation for analysing structural change in dynamic networks.
Kosti Koistinen, Vesa Kuikka, Joni Herttuainen +3
Aalto University School of Science Computer Science Department P.O.Box 11000, 00076 AALTO, Finland · Lockheed Martin USA
Oversmoothing is a well-known failure mode of Graph Neural Networks (GNNs). However, most existing diagnostics rely on global aggregation measures that fail to capture the heterogeneous dynamics of message passing. Real-world graphs exhibit pronounced community structure, and message passing operates on two timescales, with representations collapsing rapidly within communities and slowly across them. This creates a critical gap in which intra-community representations can become indistinguishable while inter community separation persists, a failure mode that we refer to as the Echo Chamber Effect. To quantify this effect, we introduce the Echo Chamber Index (ECI), which stratifies pairwise distances by community membership and reveals when global energy diminishes while inter-community separation persists. ECI further shows that feature retention mechanisms can preserve the echo chamber under the conditions of our theoretical analysis. The consequences depend on label structure: when communities align with classes, the echo chamber can sharpen node classification, whereas when they do not, the same collapse makes classification provably harder. Motivated by this analysis, we propose Community-Aware Split Propagation (CASP), a lightweight plugin that decouples intra- and inter-community aggregation and learns their balance from label structure. CASP improves diverse backbone GNNs across most evaluated homophilic and heterophilic settings.
Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe +1
Department of Mechanical Engineering University of Melbourne Melbourne, Australia · School of Computing Australian National University Canberra, Australia · Data61, CSIRO Canberra, Australia
Community detection is a fundamental problem in the analysis of complex networks. It has applications across social, biological, and financial domains. Traditional algorithms such as Louvain, LPA, and modularity optimization often require manual parameter tuning. They also suffer from inaccurate cluster center selection and struggle with scalability. To address these challenges, we propose Automatic Laplacian Centrality Means (ALCMeans), a novel community detection algorithm. ALCMeans combines Laplacian energy-based automatic center identification with DeepWalk embeddings for robust node representation. Unlike existing Laplacian-based and clustering methods, ALCMeans eliminates the need to predefine the number of communities, enhances cluster center selection using structural importance, and leverages representation learning for more accurate and stable assignments. Experimental results on benchmark datasets demonstrate 10 to 20 percent higher NMI and ARI scores compared to Louvain, Newman-Girvan, LPA, Fast-Greedy, and a recent GNN-based competitor (MAGI, KDD 2024). Additional evaluations with modularity and F1-scores confirm the superiority of ALCMeans. Ablation studies highlight the critical contributions of each component. Despite its reliance on DeepWalk parameters and increased runtime relative to lightweight heuristics, ALCMeans consistently outperforms state-of-the-art methods. This makes it a promising tool for real-world network analysis.
Shahin Momenzadeh, Rojiar Pir Mohammadiani
Department of Computer Engineering, University of Kurdistan, Sanandaj, Iran