ECHO通过高阶算子实现高效社区检测，克服了图神经网络的语义过平滑与内存瓶颈。
ECHO: Encoding Communities via High-order Operators
- 设计拓扑感知路由机制，动态选择最优归纳偏置以应对异质性网络
- 提出分块相似性提取方法，将内存开销从O(N²)降至O(N·K)
- 在百万级节点网络上实现分钟级聚类，速度超2800节点/秒
属性网络中的社区检测面临根本性挑战：拓扑算法忽略语义特征，而图神经网络则遭遇严重的计算瓶颈。具体而言，GNN在密集或异质性网络中存在语义过平滑问题，同时受制于成对聚类带来的O(N²)内存限制。为此，本文提出ECHO（Encoding Communities via High-order Operators），一种可扩展的自监督架构，将社区检测重构为自适应多尺度扩散过程。ECHO包含拓扑感知路由模块，可自动分析稀疏性、密度和同质性等结构特性，引导数据通过最优归纳偏置，防止异质性污染并确保语义稠密化。结合内存分片的全批量对比目标与新型分块O(N·K)相似性提取方法，ECHO完全规避传统O(N²)内存瓶颈，且不牺牲全局梯度的数学精度。大量实验表明，该拓扑-语义协同策略持续突破经典分辨率极限。在扩展至100万节点的合成LFR基准上，即便存在严重拓扑噪声，仍保持尺度不变的准确性。在超过160万节点、3000万边的真实社交网络上，可在数分钟内完成聚类，吞吐量超过2800节点/秒，媲美高度优化的纯拓扑基线。实现采用统一框架，自动启用内存分片优化，支持不同硬件条件下的部署。
原文摘要 · Abstract (English)
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
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。