GraphPDHG：对齐PDHG的消息传递网络在图上求解鞍点问题，加速收敛并改善规模泛化
核心概要
作者提出GraphPDHG，一种受Chambolle-Pock原始-对偶混合梯度（PDHG）启发的节点-边消息传递图神经网络，用于求解一般图鞍点问题；理论上证明单层可精确实现一步预条件PDHG，线性化动力学在无记忆时化为预条件图拉普拉斯动力学、在带边记忆时恢复重球加速；在凸聚类上，该模型为二阶求解器SSNAL提供更优热启动，并在图规模增大时比GCN、GAT等基线取得更低原始目标值。
Figure 1 : Tracking the primal–dual gap and the distance between the predicted and optimal primal variables throughout training. The iterate error shrinks as the gap shrinks.
arXiv深度剖析
提出GraphPDHG：一个节点-边消息传递层，直接对应预条件PDHG的一次迭代，节点状态向边发送差分、边状态向节点回传校正消息，从而在稀疏图算子上实现可扩展的局部更新，避免昂贵的全局内层求解。 此前的原始-对偶神经算法推理工作（如PDNAR、PDHG-Net）分别面向离散原始-对偶近似算法或线性规划；本文面向点云与图上的连续原始-对偶复合目标，覆盖线性、非线性与非光滑图结构鞍点问题。 附录Lemma B.2给出构造性表示证明：在特定参数配置与激活函数下，单层输出精确恢复PDHG迭代；Theorem 3.1进一步给出与加权关联矩阵谱范数相关的深度上界，使遍历原始-对偶间隙任意小。
刻画了GraphPDHG的线性化前馈动力学：在无记忆情形下，更新退化为预条件图拉普拉斯动力学，每层可消除一个特征方向上的误差；在保留边记忆时，原始误差满足Polyak重球二阶递推，从而具备学习加速算法的容量。 这为“对齐算法为何带来泛化”提供了谱视角的解释，把学习到的更新与经典加速思想（重球动量）联系起来，而不仅是经验观察。 Proposition 3.4、3.5与Corollary 3.6、3.7在“线性区域”假设（恒等激活、投影在非活跃边上为恒等）下给出构造性参数化与收敛率；对条件数有界的图族，收敛率与图规模无关。
在凸聚类上，GraphPDHG作为学习到的热启动显著降低SSNAL达到目标原始-对偶间隙所需迭代数，并在图规模增大时比GCN、GAT等基线取得更低原始目标值。 与仅输出节点状态的GNN基线不同，GraphPDHG显式维护边对偶状态；消融显示去掉边投影或去掉边记忆都会降低初始化质量，说明收益并非仅来自通用消息传递或固定展开。 在层级高斯合成数据与MNIST、Fashion-MNIST、CIFAR-10的k近邻图上评测；所有模型共享编码器-处理器-解码器模板与同一原始-对偶间隙目标，训练500轮、1000张100节点图、Adam、学习率0.001。
训练目标为无监督的原始-对偶间隙最小化：当节点目标强凸时，间隙上界约束原始迭代到唯一最优解的距离，因此无需真值解或逐步算法监督。 相较需要中间层提示或算法监督的NAR工作，这一目标降低了监督需求，并直接对应最优性条件。 Corollary B.1给出间隙与迭代误差关系的证明；实验观察到该理论关系在经验上成立，但理论结果假设遍历迭代，而实验使用最后一层读出。
启示与展望
该结果面向可写成节点目标加边罚项、且近端映射可分离的图结构复合鞍点问题，典型场景是需要在紧计算预算下反复求解大量相关图问题、或设计良好预条件器代价高昂时。适用对象包括凸聚类、网络Lasso、图上全变差去噪等任务，以及希望用学习到的原始-对偶变量为PDHG或SSNAL等经典求解器提供热启动的研究者与工程师。理论保证在“线性区域”假设下成立，即激活为恒等且投影在非活跃边上为恒等；加速结论针对条件数有界的图族。
理论分析依赖线性区域假设与遍历迭代，而实验使用最后一层读出，二者之间的差距值得留意。加速收益随深度增加出现平台期，作者将其归因于深层GNN的过平滑、过挤压与优化困难，这一解释仍是开放问题。附录中部分表格数值在文本中未完整呈现，因此具体迭代数与间隙数值只能依据正文描述判断。此外，边记忆消融在正则化参数增大时差异缩小，作者指出此时目标塌缩为全局均值，这一退化情形下的比较意义有限。