通过负向修正提升图频谱信息，实现无需训练的高效图划分。
InfraredGP: Efficient Graph Partitioning via Spectral Graph Neural Networks with Negative Corrections
- 基于谱图神经网络与负向修正机制提取超范围低频特征。
- 仅用随机输入单次前向传播即生成可区分嵌入，效率提升16-23倍。
- 适合追求高效率且无需训练的图划分场景，如实时流数据处理。
图划分（GP）又称社区检测，旨在将图中节点划分为内部连接紧密的块。从图信号处理视角出发，我们发现带负向修正的图拉普拉斯矩阵可产生超出传统范围[0, 2]的图频率。为探究该范围外的低频信息是否蕴含更丰富的社区结构特征，我们提出InfraredGP：(1) 采用谱图神经网络作为主干，结合低通滤波器与负向修正机制；(2) 仅输入随机数据至该主干；(3) 通过一次前向传播（FFP）生成图嵌入，无需任何训练；(4) 将所得嵌入输入BIRCH算法获得可行划分结果。实验表明，仅依赖负向修正放大[0, 2]外的低频信息，InfraredGP即可为某些标准聚类模块（如BIRCH）生成可区分嵌入，并在无训练条件下取得高质量图划分结果。基于IEEE HPEC图挑战基准，我们在静态与流式图划分任务上评估，InfraredGP在效率上显著优于各类基线（最快达16x-23x），同时保持竞争性质量。代码已开源：https://github.com/KuroginQin/InfraredGP。
原文摘要 · Abstract (English)
Graph partitioning (GP), a.k.a. community detection, is a classic problem that divides nodes of a graph into densely-connected blocks. From a perspective of graph signal processing, we find that graph Laplacian with a negative correction can derive graph frequencies beyond the conventional range $[0, 2]$. To explore whether the low-frequency information beyond this range can encode more informative properties about community structures, we propose InfraredGP. It (\romannumeral1) adopts a spectral GNN as its backbone combined with low-pass filters and a negative correction mechanism, (\romannumeral2) only feeds random inputs to this backbone, (\romannumeral3) derives graph embeddings via one feed-forward propagation (FFP) without any training, and (\romannumeral4) obtains feasible GP results by feeding the derived embeddings to BIRCH. Surprisingly, our experiments demonstrate that based solely on the negative correction mechanism that amplifies low-frequency information beyond $[0, 2]$, InfraredGP can derive distinguishable embeddings for some standard clustering modules (e.g., BIRCH) and obtain high-quality results for GP without any training. Following the IEEE HPEC Graph Challenge benchmark, we evaluate InfraredGP for both static and streaming GP, where InfraredGP can achieve much better efficiency (e.g., 16x-23x faster) and competitive quality over various baselines. We have made our code public at https://github.com/KuroginQin/InfraredGP
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。