Efficient Learning on Large Graphs using a Densifying Regularity Lemma¶

会议: ICLR 2026
OpenReview: https://openreview.net/forum?id=kK7PbRzqGk
代码: https://anonymous.4open.science/r/IBGNN
领域: 图学习 / 大规模图神经网络
关键词: 弱正则引理, 低秩图近似, 有向图, 稀疏图致密化, 加权 cut 范数, IBG-NN

一句话总结¶

本文提出"相交块图"(IBG)——一种把有向稀疏大图用 \(K\ll N\) 个相交二部块叠加表示的低秩分解，并证明了一个"致密化"版本的弱正则引理，使所需块数 \(K\) 只依赖近似精度而与图规模/稀疏度无关，从而让基于 IBG 的神经网络以 \(O(N)\)（而非 \(O(E)\)）的时空复杂度在节点分类、时空预测和知识图谱补全上达到 SOTA。

研究背景与动机¶

领域现状：消息传递神经网络(MPNN)是图学习的主力，但其计算/显存开销随边数 \(E\) 线性增长。社交网络等场景常有 \(10^8\sim10^9\) 个节点、边数是节点数的 \(10^2\sim10^3\) 倍，使得 MPNN 难以扩展。图约简方法（稀疏化、凝聚、粗化）试图缓解，但除稀疏化外大多无法解决"整图放不进显存"的根本问题。
现有痛点：前作 ICG（Intersecting Community Graph，Finkelshtein et al. 2024a）用低秩图近似把复杂度从 \(O(E)\) 降到 \(O(N)\)，但有两个硬伤：(1) 只能处理无向图，丢掉了天气预报、因果推理等场景中至关重要的边方向性；(2) 用的是未加权 cut 范数，在稀疏图上非边数量碾压边，近似质量随稀疏度急剧退化——而欺诈检测、推荐、知识图谱恰恰都是大而稀疏的图。
核心矛盾：cut 范数能给出"秩与节点数无关"的稠密图近似保证，但稀疏图上它被海量非边主导；若直接降权非边，又要重新证明正则引理在新度量下仍成立。如何在有向 + 稀疏的一般图上，同时拿到"块数与图规模无关"的理论保证和可梯度下降优化的实用算法，是空白。
本文目标：构造一个能逼近任意有向稀疏图的相似性度量，并证明其对应的弱正则引理给出"块数仅依赖精度 \(\epsilon\)"的界，进而设计 \(O(N)\) 复杂度的网络架构。
核心 idea：通过加权 cut 范数主动给非边降权（致密化）——把稀疏图"逼成"稠密低秩图来近似，使所需块数 \(K=1/\epsilon^2\) 彻底摆脱对节点数与稀疏度的依赖；并把 NP-hard 的 cut 范数最小化巧妙转化为可梯度下降的加权 Frobenius 范数最小化。

方法详解¶

整体框架¶

方法分三层：(1) 用一个加权 cut 相似度（致密化度量）重新定义"两个图有多像"，给非边降权；(2) 把目标图分解成 \(K\) 个相交二部块的叠加即 IBG，并证明一个致密化弱正则引理保证小秩 IBG 即可逼近任意图——关键是把不可优化的 cut 误差用可优化的加权 Frobenius 误差来 bound；(3) 在拟合好的 IBG 上跑 IBG-NN，每层 \(O(NK)\) 操作完成下游任务。整个流水线"先一次性拟合 IBG（\(O(E)\)），再在低秩表示上反复训练下游任务（\(O(N)\)）"。

graph LR
    A["有向稀疏图 A<br/>N节点, E边"] -->|加权cut相似度<br/>给非边降权| B["拟合目标:<br/>加权Frobenius损失"]
    B -->|梯度下降<br/>O(E) 一次| C["K-IBG 表示<br/>C=U·diag(r)·Vᵀ<br/>K≪N"]
    C -->|致密化弱正则引理<br/>保证 cut误差≤O(1/√K)| C
    C -->|每层 O(NK)| D["IBG-NN<br/>源/目标社区合成"]
    D --> E["下游任务:<br/>节点分类/时空/KG补全"]

关键设计¶

1. 致密化 cut 相似度：给非边降权，把"逼近稀疏图"变成可处理问题。 标准 cut 范数在稀疏图上失效，是因为非边数量远超边数，误差被非边主导。作者定义一个权重矩阵 \(Q_A = e_{E,\Gamma}\mathbf{1} + (1-e_{E,\Gamma})A\)，对边赋权 1、对非边赋一个小权 \(e_{E,\Gamma}=\frac{\Gamma E/N^2}{1-(E/N^2)}\)，由超参 \(\Gamma\) 控制边与非边的相对重要性。致密化 cut 相似度即 \(\sigma_\square(A\|B):=(1+\Gamma)\|A-B\|_{\square;Q_A}\)。这个权重的精妙之处在于它被恰当归一化（\((1+\Gamma)\|A\|_{F;Q_A}=1\)），使得相似度天然在 \(O(1)\) 量级：坏近似接近 1、好近似 \(\ll 1\)；并且当 \(\Gamma=N^2/E-1\) 时退化回标准 cut 度量。给非边降权的直接后果就是逼出来的近似图会"致密化"——把稀疏图的连接模式补强，这反而有利于下游节点分类。

2. 相交块图 (IBG)：有向图的低秩二部块叠加表示。 一个 \(K\)-IBG 由 \(K\) 对节点社区 \((U_j, V_j)\) 构成，每对定义一个加权二部块——把 \(U_j\) 中每个节点以权重 \(r_j\)（可为负）连到 \(V_j\) 中每个节点。整图邻接矩阵写成低秩形式 \(C=\sum_{j=1}^{K} r_j \mathbf{1}_{U_j}\mathbf{1}_{V_j}^\top = U\,\mathrm{diag}(r)\,V^\top\)，信号写成 \(P=UF+VB\)。其中源社区矩阵 \(V\) 与目标社区矩阵 \(U\) 解耦，正是这一点让 IBG 能表达有向性（前作 ICG 中两者相同，只能无向）。为可微优化，把硬指示函数 \(\mathbf{1}_U\in\{0,1\}^N\) 松弛成软隶属向量 \(U,V\in[0,1]^{N\times K}\)（实现上对可学习矩阵套 Sigmoid）。

3. 致密化弱正则引理：把 NP-hard 的 cut 误差用可优化的 Frobenius 误差 bound 住。 直接最小化 cut 相似度是含 max 的 min-max 问题、NP-hard。Theorem 4.1 给出"半构造"出路：定义 \(\eta_k=(1+\delta)\min_{(C,P)\in[Q]^k}\|(A,X)-(C,P)\|^2_{F;Q_A,\dots}\)（前 \(k\) 块的最优加权 Frobenius 误差），则任何接近最优的 Frobenius 近似 \((C^*,P^*)\) 满足 cut 相似度误差 \(\sigma_\square\big((A,X)\|(C^*,P^*)\big)\le(\sqrt{\alpha(1+\Gamma)}+\sqrt{\beta})\sqrt{\tfrac{\eta_m-\eta_{m+1}}{1+\delta}}\)；当 \(m\) 从 \([K]\) 随机采样时，以概率 \(1-1/R\) 有 \(\sigma_\square\le\sqrt{2+\Gamma}\sqrt{\tfrac{\delta+R(1+\delta)}{K}}\)。关键结论是这个界只依赖块数 \(K\) 而与节点数 \(N\)、稀疏度无关——所需块数 \(K=O(1/\epsilon^2)\)，这正是"致密化"的理论根源。引理相比前作在三处推广：支持有向 IBG、给出高概率事件的确定性证书、以及界与图规模解耦。

4. 可梯度下降的高效拟合：用稀疏 + 低秩结构把 \(O(N^2)\) 降到 \(O(K^2N+KE)\)。 直接算 \(\|A-U\mathrm{diag}(r)V^\top\|^2_{F;Q_A}\) 需 \(O(N^2)\)（差矩阵既不稀疏也不低秩）。Proposition 4.2 把损失展开成三项：\(\|A\|^2_{F;Q_A}\)、利用低秩结构的 \(\mathrm{Tr}\big((V^\top V)\mathrm{diag}(r)(U^\top U)\mathrm{diag}(r)\big)\)、以及只在边集 \(\mathcal{N}(i)\) 上求和的稀疏修正项，从而分别利用 \(A\) 的稀疏性和 \(U\mathrm{diag}(r)V^\top\) 的低秩性，把时间降到 \(O(K^2N+KE)\)、空间 \(O(KN+E)\)，与消息传递同阶。IBG 拟合用 SVD 初始化加速收敛，显存不够时还配套了随机化 SVD 与子图 SGD 采样方案。拟合后的 IBG-NN 用源/目标合成（\(F\mapsto UF\), \(B\mapsto VB\)）与分析操作处理信号，每层 \(O(NK)\)。

实验关键数据¶

主实验表格（有向节点分类，ROC AUC / Accuracy）¶

Model	Squirrel	Chameleon	Tolokers
GCN	53.43	64.82	83.64
GAT	40.72	66.82	83.70
DirGNN（有向专用）	75.13	79.74	–
FaberNet	76.71	80.33	–
ICG-NN（前作）	64.02	63.9	83.73
IBG-NN	77.63	80.15	83.76

IBG-NN 超越了为有向图专门设计、却需二次复杂度的 GNN，并大幅领先前作 ICG-NN。

消融实验表格（方向性 vs 致密化的贡献分解）¶

变体	Squirrel	Chameleon	说明
ICG-NN	64.02	63.9	无向 + 未加权
IBG-NN (undirected)	70.02	75.15	+致密化（+6%, +11.2%）
IBG-NN	77.63	80.15	+方向性（再 +7.6%, +5%）

致密化与方向性各自贡献显著；Tolokers 上两者提升都小，因其本身已很稠密、方向模式不明显。

关键发现¶

效率：在稀疏 ER 图上对比 DirGNN，\(K=10/100\) 时分别加速 \(5.68\times/5.26\times\)；稠密图上 IBG-NN 运行时间相对 DirGNN 呈平方根关系，与 \(O(N)\) vs \(O(E)\) 的理论吻合。即便 \(K=100\) 超过平均度 25，仍更快。
大图凝聚（Flickr/Reddit/Arxiv/Products）：子图 SGD 版 IBG-NN 在极低凝聚率下达 SOTA，全面超越 GCOND/SFGC/SimGC 等需整图入显存的凝聚/粗化方法，且一致优于 ICG-NN（如 Reddit 0.1% 达 92.3 vs ICG-NN 89.7）。
IBG 仅需一次拟合（\(O(E)\)），下游可反复以 \(O(N)\) 训练；时空预测中图固定、信号随时间变，拟合开销与时间步数无关，效率优势随训练信号增多更明显。

亮点与洞察¶

理论洞察反直觉但深刻：稀疏图最难近似，作者却反其道而行——主动"致密化"它，用稠密低秩图去逼稀疏图，关键是给非边降权后正则引理的块数界彻底与图规模脱钩（\(K=O(1/\epsilon^2)\)）。这把"低秩近似只对稠密图有效"的旧认知打破了。
把不可优化变可优化：cut 范数 NP-hard，但通过"Frobenius 最小者也是好的 cut 近似"这一引理，绕开 min-max 直接梯度下降，且即便 Frobenius 误差本身大、cut 误差也小。
解耦 \(U,V\) 自然支持有向：仅靠源/目标社区矩阵分离这一改动就把无向 ICG 推广到有向 IBG，简洁而有效。
复杂度的实用性：\(O(K^2N+KE)\) 拟合 + \(O(NK)\) 推理，且 IBG 一次拟合可复用，特别适合超参搜索（\(O(SN)\) vs \(O(SE)\)）和时空任务。

局限与展望¶

非凸优化无全局保证：拟合 IBG 用梯度下降，损失非凸，理论只保证"接近最优 Frobenius 解"即可，实际是否落在好解上依赖初始化（SVD 初始化缓解但不消除）。
超参 \(\Gamma\) 的选择：致密化程度由 \(\Gamma\) 控制，论文未深入讨论如何自适应选取，不同稀疏度的图可能需要调。
稠密图收益有限：Tolokers 上致密化与方向性几乎无增益，方法的优势主要体现在稀疏/有向场景。
块数 \(K\) 与表达力的权衡：虽然理论上 \(K=O(1)\) 即可，但实际任务中增加社区数仍能提升性能与近似质量，最优 \(K\) 仍需经验调。
展望：把致密化思想推广到更一般的图相似度/图核、与时序动态图结合、以及在更大规模工业图（\(10^9\) 节点）上验证随机化 SVD + 子图 SGD 的端到端可行性。

评分¶

新颖性: ⭐⭐⭐⭐⭐ — 致密化弱正则引理（块数与图规模/稀疏度无关）是对经典正则引理的实质性理论贡献，IBG 对有向稀疏图的低秩表示也很新。
实验充分度: ⭐⭐⭐⭐ — 覆盖效率、节点分类、大图凝聚、时空、KG 补全多任务并有方向性/致密化消融；但主表数据集规模偏小，工业级超大图（\(10^9\)）仅理论支撑。
写作质量: ⭐⭐⭐⭐ — 理论严谨、动机清晰、术语命名（半构造/软/有向/致密化）自洽；但定理与加权范数推导密集，对非理论读者门槛较高。
价值: ⭐⭐⭐⭐⭐ — 把大稀疏有向图学习从 \(O(E)\) 降到 \(O(N)\) 且达 SOTA，对推荐/社交/知识图谱等大规模稀疏场景有直接实用价值。