提出新型谱图神经网络L2G-Net,实现局部到全局的高效长程依赖建模。
L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations
- 通过柯西矩阵组合子图谱表示,避免全图特征分解
- 在大规模图上实现长程依赖建模,参数量少于现有方法数个数量级
- 适合处理需要全局信息但又不依赖昂贵特征分解的图学习任务
尽管基于图傅里叶变换(GFT)的谱方法具有理论优势,但由于需计算完整特征基且表示缺乏顶点域局部性,很少被用于图神经网络(GNN)。因此,多数GNN依赖多项式拉普拉斯滤波器或消息传递等局部近似,限制了对长程依赖的建模能力。本文提出一种精确的GFT分解方法,将变换分解为作用于子图上的算子,并通过一系列柯西矩阵组合。基于此,我们提出一类新的谱GNN——L2G-Net(Local to Global Net)。与传统谱方法(完全全局或局部)不同,L2G-Net先处理子图的谱表示,再通过结构化矩阵融合。该算法避免了全图特征分解,利用图拓扑以节点数的平方复杂度构造分解,系数取决于子图间最大割大小。实验表明,在强调长程依赖的大规模图上,L2G-Net可扩展至标准GFT无法处理的规模,且在性能上媲美最先进方法,同时参数量减少数个数量级。
原文摘要 · Abstract (English)
Despite their theoretical advantages, spectral methods based on the graph Fourier transform (GFT) are seldom used in graph neural networks (GNNs) due to the cost of computing the eigenbasis and the lack of vertex-domain locality in the resulting representations. As a result, most GNNs rely on local approximations such as polynomial Laplacian filters or message passing, which limit their ability to model long-range dependencies. In this paper, we introduce an exact factorization of the GFT into operators acting on subgraphs, which are then combined via a sequence of Cauchy matrices. Building on this factorization, we propose a new class of spectral GNNs, termed L2G-Net (Local to Global Net). Unlike existing spectral methods, which are either fully global (when using the GFT) or local (when using polynomial filters), L2G-Net operates by processing the spectral representations of subgraphs and then combining them via structured matrices. Our algorithm avoids full eigendecompositions, exploiting graph topology to construct the factorization with quadratic complexity in the number of nodes, scaled by the maximum cut size between subgraphs. Experiments stressing long-range dependencies on large graphs show that L2G-Net scales to regimes out of reach for the standard GFT, and is competitive with state-of-the-art methods with orders of magnitude fewer learnable parameters.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。