用子图GNN提升分支决策，理论可行但实际效率低。
Branching Strategies Based on Subgraph GNNs: A Study on Theoretical Promise versus Practical Reality
- 提出基于节点锚定的子图GNN，理论可逼近最优分支策略。
- 实验显示其内存开销大、求解慢，不如传统MPNN和启发式方法。
- 适合关注模型表达力与计算效率平衡的研究者。
图神经网络（GNN）在混合整数线性规划（MILP）的‘学习分支’任务中展现出潜力。标准消息传递GNN（MPNN）虽高效，但理论上无法充分表示MILP结构；而高阶GNN（如2-FGNN）虽表达力强，却计算成本过高。本文研究子图GNN作为理论上的折中方案。关键发现：此前工作[Chen et al., 2025]表明，具备3-WL表达力的GNN可近似强分支（Strong Branching），而本文证明——表达力略低于3-WL的节点锚定子图GNN已足够实现该近似。然而，在四个基准数据集上的广泛实证表明，尽管其理论分支决策更优，但$O(n)$复杂度导致显著内存瓶颈和求解速度下降，远逊于MPNN和启发式方法。结果表明，当前表达性强的GNN在MILP分支中的计算代价超过其决策质量收益，未来研究需聚焦于保持表达力的同时提升效率。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) have emerged as a promising approach for ``learning to branch'' in Mixed-Integer Linear Programming (MILP). While standard Message-Passing GNNs (MPNNs) are efficient, they theoretically lack the expressive power to fully represent MILP structures. Conversely, higher-order GNNs (like 2-FGNNs) are expressive but computationally prohibitive. In this work, we investigate Subgraph GNNs as a theoretical middle ground. Crucially, while previous work [Chen et al., 2025] demonstrated that GNNs with 3-WL expressive power can approximate Strong Branching, we prove a sharper result: node-anchored Subgraph GNNs whose expressive power is strictly lower than 3-WL [Zhang et al., 2023] are sufficient to approximate Strong Branching scores. However, our extensive empirical evaluation on four benchmark datasets reveals a stark contrast between theory and practice. While node-anchored Subgraph GNNs theoretically offer superior branching decisions, their $O(n)$ complexity overhead results in significant memory bottlenecks and slower solving times than MPNNs and heuristics. Our results indicate that for MILP branching, the computational cost of expressive GNNs currently outweighs their gains in decision quality, suggesting that future research must focus on efficiency-preserving expressivity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。