arXiv:2605.25662cs.LG2026-05

用闭式解法实现图神经网络的精确节点分类与可解释删改,速度提升百倍以上。

Closed-Form Node Classification with Exact Graph Unlearning

论文配图:Closed-Form Node Classification with Exact Graph Unlearning
图 1 · 摘自论文原文
  • 根据图同质性选择不同闭式求解器:同质图用SGC+岭回归,异质图用LCF-Net逐层闭式优化
  • 在14个基准上9个超过或持平最佳2层GNN,大图上超越OGB基准纯GCN模型
  • 支持精确图结构删改,局部更新比全重解快21-45倍,比梯度训练快百万倍

图神经网络进行节点分类通常需经数百至数千轮梯度下降训练。近期研究显示,经恰当调优的经典GCN/SAGE/GAT架构可在多数节点分类基准上媲美图变压器。本文提出互补问题:能否通过确定性闭式求解器恢复部分性能,并带来何种理论保证?我们引入基于调整同质性选择的路由闭式框架:对同质图采用SGC式传播后接岭回归;对异质图提出LCF-Net,一种逐层闭式特征精炼网络,每层岭回归由高斯核岭回归头约束。在14个基准(含ogbn-arxiv、ogbn-proteins)上,闭式预测器在9个数据集上匹配或超越最佳的2层GCN/SAGE/GAT,12个小型基准中有9个与调优深层模型差距在1个标准差内,大图上超越OGB排行榜上的纯GCN。剩余异质图性能差距与2层到深层SAGE的增益紧密对应,表明差异主要源于架构。由于预测器是确定性线性系统的显式解,修改图输入后可重新求解获得等效参数。我们形式化了标签、特征、边、节点和子图修改的精确图对象删去,证明岭回归组件具有K跳局部性,并在109种配置中验证了精确性。在ogbn-arxiv上,局部更新比全重解快21–45倍,约比梯度重训快10^6倍。结构反演实验进一步量化了精确重训的隐私下限及近似删去方法的额外泄露。

原文摘要 · Abstract (English)

Graph neural networks for node classification are typically trained by gradient descent over hundreds or thousands of epochs. Recent work has shown that, when properly tuned, classic GCN/SAGE/GAT architectures can match graph transformers on many node-classification benchmarks. We ask a complementary question: how much of this performance can be recovered by deterministic closed-form solvers, and what guarantees does this enable? We introduce a routed closed-form framework selected by adjusted homophily. For assortative graphs, we use SGC-style propagation followed by Ridge regression; for heterophilous graphs, we introduce LCF-Net, a layer-wise closed-form graph feature-refinement network whose per-layer Ridge solves are capped by a Gaussian kernel-Ridge head. Across 14 benchmarks, including ogbn-arxiv and ogbn-proteins, our closed-form predictors match or beat the best vanilla 2-layer GCN/SAGE/GAT on 9 of 9 measured datasets, tie tuned deep recipes within one standard deviation on 9 of 12 small benchmarks, and exceed the OGB-leaderboard plain GCN on both large graphs. The remaining heterophilous gap closely tracks the gain from vanilla 2-layer to deep SAGE, suggesting that the residual difference is primarily architectural. Because our predictors are explicit solutions of deterministic linear systems, modified graph inputs can be re-solved to obtain retrain-equivalent parameters. We formalize exact graph-object unlearning for label, feature, edge, node, and subgraph modifications, prove K-hop locality for Ridge components, and verify exactness across 109 configurations. On ogbn-arxiv, localized updates give $21$--$45\times$ speedups over full re-solving and roughly $10^{6}\times$ speedups over gradient retraining. Structural-inversion experiments further quantify the privacy floor of exact retraining and the additional leakage of approximate graph-unlearning methods.

图神经网络闭式求解图删去高效推理

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。