LLM2D
凯莱图传播
Cayley Graph Propagation
作者: JJ Wilson, Maya Bechler-Speicher, Petar Veli\v{c}kovi\'c
发布日期: 10/7/2024
arXiv ID: oai:arXiv.org:2410.03424v1

摘要

尽管图神经网络 (GNN) 在对图结构数据进行建模方面取得了众多成功案例,但它们却臭名昭著地容易受到过度压缩的影响,在这种情况下,任务需要在距离较远的节点对之间混合信息。为了解决这个问题,之前的工作建议重新连接图结构以改善信息流。或者,大量研究致力于发现和预计算无瓶颈的图结构以改善过度压缩。在数学界,一类广受认可的无瓶颈图是扩展图,之前的工作——扩展图传播 (EGP)——建议使用一类众所周知的扩展图——$\mathrm{SL}(2,\mathbb{Z}_n)$ 特殊线性群的凯莱图——作为 GNN 的计算模板。然而,在 EGP 中,所使用的计算图被截断以与给定的输入图对齐。在这项工作中,我们表明截断对令人垂涎的扩展特性有害。相反,我们提出了 CGP,一种在完整的凯莱图结构上传播信息的方法,从而确保它没有瓶颈,以更好地缓解过度压缩。我们跨多个真实世界数据集的实证证据不仅表明 CGP 与 EGP 相比取得了显著的改进,而且它也与计算复杂度高的图重连技术相当或优于它们。