ECHO: Encoding Communities via High-order Operators

Emilio Ferrara

cs.LGFeb 25, 2026

ECHO: Encoding Communities via High-order Operators

Authors: Emilio Ferrara

Organizations: Thomas Lord Department of Computer Science, University of Southern California, Los Angeles, CA, USA

Abstract

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

Panel of Figure 1 — 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\cdot N\cdot d\cdot K_{clus})$	$O(N\cdot d)$
LPA ( Raghavan et al., 2007 )	$O(I\cdot\|E\|)$	$O(N)$
Leiden ( Traag et al., 2019 )	$O(N\log N)$	$O(\|E\|)$
LINE ( Tang et al., 2015 )	$O(I\cdot\|E\|)$	$O(N\cdot d)$
DGI ( Veličković et al., 2019 )	$O(K\cdot\|E\|\cdot d)$	$O(N^{2})^{*}$
MVGRL ( Hassani and Khasahmadi, 2020 )	$O(N^{2})$	$O(N^{2})$

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 (

\mu=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

Dataset	Nodes ( $N$ )	Edges ( $\|E\|$ )	Time (s)	Throughput
YouTube (Synth)	1,134,890	2,987,624	347.4	3,266.6 n/s
Pokec (Sharded)	1,632,803	30,622,564	582.1	2,805.0 n/s

Table 5. Massive-Scale Throughput (Single A100 GPU)

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).

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Dataset	Auto-Architecture	Temp ( $\tau$ )	LR	Sparsity ( $\lambda$ )	Threshold ( $\delta$ )
Chameleon	Isolating (MLP)	0.20	5e-4	1e-3	0.15
Actor	Isolating (MLP)	0.05	5e-4	1e-4	0.15
Amazon Photo	Isolating (MLP)	0.05	5e-4	1e-4	0.15
Amazon Computers	Isolating (MLP)	0.10	5e-4	1e-4	0.15
Coauthor CS	Densifying (SAGE)	0.04	5e-4	5e-4	0.10
CoraFull	Densifying (SAGE)	0.20	1e-3	1e-3	0.15

Appendix

Table 6. Discovered Champion Hyperparameter Configurations (ECHO v3.0.0)

Graph Clustering

Graph clustering groups network nodes by connectivity, attributes, or shared roles to reveal communities and other mesoscale structure.

See all 76 papers

Diffusion-Induced Spatial Attention Overlapping Community Detection
Sep 22, 2026Kosti Koistinen, Vesa Kuikka, Joni Herttuainen +3Graph Attention Networks Graph Clustering
Aalto University School of Science Computer Science Department P.O.Box 11000, 00076 AALTO, Finland · Lockheed Martin USA
Not Just Oversmoothing: Detecting the Echo Chamber Effect in Graph Neural Networks
Sep 6, 2026Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe +1Over-Smoothing in GNNs Graph Neural Networks
Department of Mechanical Engineering University of Melbourne Melbourne, Australia · School of Computing Australian National University Canberra, Australia · Data61, CSIRO Canberra, Australia
Alcmean's: Unsupervised community detection using local Laplacian, automatic detection of the number of centers
Jun 8, 2026Shahin Momenzadeh, Rojiar Pir MohammadianiCluster Number Estimation Clustering
Department of Computer Engineering, University of Kurdistan, Sanandaj, Iran

Sep 22, 2026J/K move · Enter open · S save

Diffusion-Induced Spatial Attention Overlapping Community Detection

Kosti Koistinen, Vesa Kuikka, Joni Herttuainen, Matthew Hendren+2

Aalto University School of Science Computer Science Department P.O.Box 11000, 00076 AALTO, Finland · Lockheed Martin USA

Graph Attention Networks Graph Clustering

Open paper AskPDF arXiv

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.

Abstract

Graph Clustering

Explore similar work

Diffusion-Induced Spatial Attention Overlapping Community Detection

Not Just Oversmoothing: Detecting the Echo Chamber Effect in Graph Neural Networks

Alcmean's: Unsupervised community detection using local Laplacian, automatic detection of the number of centers