标题： 红外GP：通过带有负修正的谱图神经网络进行高效图划分 显示英文标题

标题： InfraredGP: Efficient Graph Partitioning via Spectral Graph Neural Networks with Negative Corrections

摘要： 图划分（GP），也称为社区检测，是一个经典问题，它将图的节点划分为紧密连接的块。从图信号处理的角度来看，我们发现带有负校正的图拉普拉斯矩阵可以推导出超出传统范围$[0, 2]$的图频率。为了探索这个范围之外的低频信息是否能编码更多关于社区结构的信息，我们提出了InfraredGP。它（\romannumeral 1）采用谱GNN作为其骨干，结合低通滤波器和负校正机制，（\romannumeral 2）仅将随机输入提供给这个骨干，（\romannumeral 3）通过一次前向传播（FFP）获得图嵌入，而无需任何训练，并且（\romannumeral 4）通过将得到的嵌入输入BIRCH来获得可行的GP结果。令人惊讶的是，我们的实验表明，仅基于放大超出$[0, 2]$的低频信息的负校正机制，InfraredGP就可以为一些标准聚类模块（例如BIRCH）生成可区分的嵌入，并在没有任何训练的情况下获得高质量的GP结果。根据IEEE HPEC图挑战基准，我们评估了InfraredGP在静态和流式GP中的表现，其中InfraredGP在效率（例如快16倍-23倍）和竞争力方面优于各种基线。我们已将代码公开在https://github.com/KuroginQin/InfraredGP 显示英文摘要

摘要： 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