让图神经网络输出满足动态约束，提升实际应用可行性
Enforcing convex constraints in Graph Neural Networks
- 用稀疏向量裁剪+CAD算法实现输入相关约束
- 支持大规模图数据，训练效率高且收敛可靠
- 适合需严格约束的优化问题，如无线功率控制
许多机器学习应用需要输出满足复杂、动态的约束条件。这一任务在图神经网络中尤为困难，因为图结构数据的输出尺寸可变。本文提出ProjNet，一种满足输入相关约束的图神经网络框架。ProjNet结合稀疏向量裁剪与分量平均Dykstra（CAD）算法，该算法是求解最优逼近问题的迭代方法。我们建立了CAD的收敛性结果，并开发了基于GPU的高效实现，可处理大规模输入。为支持端到端训练，引入一种计算高效的代理梯度，其优化性能优于精确梯度。在四类约束优化问题上验证：线性规划、两类非凸二次规划及无线电发射功率优化，证明了其在多样化场景下的有效性。
原文摘要 · Abstract (English)
Many machine learning applications require outputs that satisfy complex, dynamic constraints. This task is particularly challenging in Graph Neural Network models due to the variable output sizes of graph-structured data. In this paper, we introduce ProjNet, a Graph Neural Network framework which satisfies input-dependant constraints. ProjNet combines a sparse vector clipping method with the Component-Averaged Dykstra (CAD) algorithm, an iterative scheme for solving the best-approximation problem. We establish a convergence result for CAD and develop a GPU-accelerated implementation capable of handling large-scale inputs efficiently. To enable end-to-end training, we introduce a surrogate gradient for CAD that is both computationally efficient and better suited for optimization than the exact gradient. We validate ProjNet on four classes of constrained optimisation problems: linear programming, two classes of non-convex quadratic programs, and radio transmit power optimization, demonstrating its effectiveness across diverse problem settings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。