论文解读+圆桌：图神经网络对线性优化问题的求解能力丨图神经网络与组合优化读书会·周三直播
导语
利用图神经网络（GNN）求解线性规划问题，是近年来新兴的求解方式，可以帮助形成对线性规划问题的洞见。ICLR2023上的两篇文章，第一次对两类线性规划问题的可训练性作出回答。本次分享中，国防科技大学系统工程学院的蒲天乐和对外经贸大学统计学院校外导师陆怡舟将主要解读这两篇文章，并邀请论文一作、杜克大学数学系博士陈子昂和读书会发起人范长俊老师进行圆桌讨论，探讨GNN在优化领域的应用前景和未来研究方向。
为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院助理教授黄文炳，共同发起「图神经网络与组合优化」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在 AI for Science 中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。读书会从2023年6月14日开始，每周三晚 19:00-21:00 举行，持续时间预计8周。欢迎感兴趣的朋友报名参与！
分享内容简介
分享内容简介
分享内容大纲
分享内容大纲
-
优化问题的二部图表示
-
WL算法介绍
-
利用GNN求解优化问题的可训练性，及问题的数学描述
-
LP问题的可训练性，及证明思路
-
MILP问题的Random Feature
-
数值结果
圆桌拟讨论问题
圆桌拟讨论问题
1.图结构是否存在类似于图形图像、语言语义这样相对稳定的统计分布，这可能更加本质地决定了GNN的学习能力。对于LP(MILP)问题，现在的二部图的表达方式，似乎没有利用到优化问题的性质，是否合理？有没有能利用到问题背景的更直接、准确、本质化的图结构化方法？换言之，二部图是否是最适合用于描述LP(MILP)问题的图结构？
2.可训练性是使用GNN解决LP(MILP)问题的重要的理论关切点，除此以外，判别能力、训练误差、收敛速度、敏感性等性质也有很重要的理论价值，这些理论性质，在二部图的表达下，是否有解决的可能性？二部图，以及近年来以WL算法为主要工具的证明范式，是否会对理论解释力形成限制？能否展望GNN的理论发展方向，哪些方向将在未来最受关切最具备研究价值？对LP问题的可测性，有没有更加直观的解释。比如，所有的最优潮流问题对应的LP问题的集合，是可测的吗？
3.对LP问题进行分类，研究不同集合的LP问题的理论性质，包括GNN的可训练性，是否是自然的研究思路？换言之，不同类的LP问题之间的差异是否足够大，以至于不太可能训练出对所有LP问题普适的GNN？当前对LP问题的分类和性质的研究，是否形成了一致的看法？
4.GNN的求解效果会受到哪些因素的影响？采样数量、网络大小和参数是影响GNN在LP问题上表现的主要因素吗？还是说，LP问题对应的二部图的要素，譬如节点个数、连边数量，才是影响GNN效果的关键因素？
5.展望未来，GNN有多大可能性来替代传统的优化问题求解器？如果GNN结果做不到100%可靠，那么结合了GNN的求解器模式有哪些？如果只是将GNN结果作为传统求解器的初始值，是否有可能反而增加了求解时间和难度？
主讲人介绍
主讲人介绍
蒲天乐，国防科技大学系统工程学院2022级硕士研究生，师从陈超教授和范长俊副教授，研究方向为机器学习与组合优化，重点关注以图神经网络为代表的各种图技术在组合优化领域中的应用，研究兴趣包括但不限于图神经网络、组合优化、神经算法推理、复杂网络等。
陆怡舟，对外经贸大学统计学院校外导师。毕业于北京大学数学学院，曾在微软亚洲研究院从事互联网搜索算法研究工作，在WWW等国际会议发表图及矩阵计算方向论文多篇。目前从事金融风险管理和研究工作，担任中国农业风险管理研究会农业保险分会理事、民建北京市委金融委委员，研究兴趣包括因果学习、中介分析、参数及非参数效率分析、大规模图计算、神经网络及在风险特征分析、风险绩效评价、系统性风险管理、风险传染、大型系统韧性等方面的应用。
圆桌嘉宾
圆桌嘉宾
陈子昂，杜克大学数学系博士，师从鲁剑锋教授。研究方向为机器学习理论、优化、偏微分方程等，部分研究成果发表于SIAM J. Optim.，NeurIPS，ICLR等期刊或会议。
范长俊，国防科技大学系统工程学院副教授。研究方向包括图深度学习、组合优化、强化学习及其在智能决策、复杂系统和指挥控制中的应用。以第一作者或通讯作者在Nature Machine Intelligence、Nature Communications、AAAI等顶级期刊和会议发表论文多篇。
主要涉及到的参考文献
主要涉及到的参考文献
主要涉及的前置知识
主要涉及的前置知识
• 图神经网络（Graph Neural Network）
• 离散/整数/组合/非凸优化的介绍
https://www.zhihu.com/tardis/zm/art/27429666?source_id=1005
• 图同构测试（Weisfeiler-Lehman Test）
Weisfeiler-Lehman算法在大多数图上会得到一个独一无二的特征集合，这意味着图上的每一个节点都有着独一无二的角色定位。因此，对于大多数非规则的图结构，经算法处理后得到的特征可以作为图是否同构的判别依据，也就是WL测试。
https://archwalker.github.io/blog/2019/06/22/GNN-Theory-WL.html
https://blog.csdn.net/qq_27075943/article/details/106652510
https://blog.csdn.net/Datawhale/article/details/111398979
https://zhuanlan.zhihu.com/p/333398731
• 直流最优潮流（DC optimal power flow）
最优潮流是从电力系统稳定运行的角度来调整系统中各种控制设备的参数，在满足节点正常功率平衡及各种安全指标的约束下，实现目标函数最小化的优化过程。
https://ieeexplore.ieee.org/document/6486058
https://mp.weixin.qq.com/s/u-i5psFQSMlV83RfoiO-9Q
https://zhuanlan.zhihu.com/p/450276292
• 通用逼近定理（Universal Approximation Property）
在人工神经网络的数学理论中，通用逼近定理是在给定的函数空间内建立算法生成的函数类密度的结果。通常，这些结果涉及前馈架构在两个欧几里得空间之间的连续函数空间上的逼近能力，并且该逼近是相对于紧凑收敛拓扑而言的。
https://blog.csdn.net/qq_40206371/article/details/127192727
https://zhuanlan.zhihu.com/p/443284394
• 卢辛定理（Lusin’s theorem）
在实分析的数学领域，卢辛定理（以尼古拉·卢辛命名）或卢辛准则指出，有限函数几乎处处是可测的，当且仅当它在几乎所有域上都是连续函数时。
https://en.wikipedia.org/wiki/Lusin%27s_theorem
https://zhuanlan.zhihu.com/p/369876259
https://www.zhihu.com/question/488109662
• 斯通-维尔斯特拉斯定理（Stone-Weierstrass Theorem）
Weierstrass在其1885年的论文中提出了Weierstrass Approximation Theorem，根据该定理，对于任何定义在 [a,b] 上的连续实值函数 f ，存在一个多项式函数序列，该序列一致收敛于 f。之后，Stone对该定理进行了扩展，最后得到的定理即是Stone-Weierstrass Theorem。
https://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem
https://zhuanlan.zhihu.com/p/47464597
直播信息
直播信息
集智学园最新AI课程，
张江教授亲授：第三代人工智能技术基础
——从可微分编程到因果推理
自1956年“人工智能”诞生于达特茅斯会议以来，已经经历了从早期的以符号推理为主体的第一代人工智能，和以深度神经网络、机器学习为主体的第二代人工智能。ChatGPT的横空出世、生成式AI的普及、AI for Science等新领域的突破，标志着第三代人工智能的呼之欲出。可微分编程、神经微分方程、自监督学习、生成式模型、Transformer、基于图网络的学习与推理、因果表征与因果推断，基于世界模型的强化学习……，所有这些脱胎于前两代人工智能的技术要素很有可能将构成第三代人工智能的理论与技术的基础。
AI+Science 读书会
图神经网络与组合优化读书会启动
微信扫一扫,分享到朋友圈
