江南APP官网论文解读+圆桌：图神经网络对线性优化问题的求解能力丨图神经网络与组合优化读书会·周三直播利用图神经网络（GNN）求解线性规划问题，是近年来新兴的求解方式，可以帮助形成对线性规划问题的洞见。ICLR2023上的两篇文章，第一次对两类线性规划问题的可训练性作出回答。本次分享中，国防科技大学系统工程学院的蒲天乐和对外经贸大学统计学院校外导师陆怡舟将主要解读这两篇文章，并邀请论文一作、杜克大学数学系博士陈子昂和读书会发起人范长俊老师进行圆桌讨论，探讨GNN在优化领域的应用前景和未来研究方向。

　　为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院助理教授黄文炳，共同发起「」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在 AI for Science 中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。读书会从2023年6月14日开始，每周三晚 19:00-21:00 举行，持续时间预计8周。欢迎感兴趣的朋友报名参与！

　　优化问题在实际生产生活中无处不在，例如，电力控制中的最优潮流问题，对电网的稳定安全运行具有重要意义，最终也需要转换为规划问题进行求解。利用图神经网络（GNN）来求解线性规划问题，是近年来新兴的求解方式，人们可以借助GNN帮助形成对线性规划问题的洞见，或是为经典求解器提供初始值以便更快求解。

　　但人们很快会面临线性规划问题对应的神经网络的可训练性问题，也即，是否GNN的输出结果能够较好的贴近经典方法的求解结果。进一步，如果线性规划问题是可训练的话，那么GNN的求解误差是否是有限的。ICLR2023上的两篇文章，第一次对两类线性规划问题的可训练性作出了回答。本次分享将与大家共同学习这两篇文章的思路、逻辑，并将通过一个小圆桌讨论，对GNN在优化领域的应用前景和未来的研究方向进行探讨。

　　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级硕士研究生，师从陈超教授和范长俊副教授，研究方向为机器学习与组合优化，重点关注以图神经网络为代表的各种图技术在组合优化领域中的应用，研究兴趣包括但不限于图神经网络、组合优化、神经算法推理、复杂网络等。

　　陆怡舟，对外经贸大学统计学院校外导师。毕业于北京大学数学学院，曾在微软亚洲研究院从事互联网搜索算法研究工作，在国际会议发表图及矩阵计算方向论文多篇。目前从事金融风险管理和研究工作，担任中国农业风险管理研究会农业保险分会理事、民建北京市委金融委委员，研究兴趣包括因果学习、中介分析、参数及非参数效率分析、大规模图计算、神经网络及在风险特征分析、风险绩效评价、系统性风险管理、风险传染、大型系统韧性等方面的应用。

　　陈子昂，杜克大学数学系博士，师从鲁剑锋教授。研究方向为机器学习理论、优化、偏微分方程等，部分研究成果发表于SIAM J. Optim.，NeurIPS，ICLR等期刊或会议。

　　范长俊，国防科技大学系统工程学院副教授。研究方向包括图深度学习、组合优化、强化学习及其在智能决策、复杂系统和指挥控制中的应用。以第一作者或通讯作者在Nature Machine Intelligence、Nature Communications、AAAI等期刊和会议发表论文多篇。

　　对GNN求解MILP的逼近能力进行了理论推导，并从理论上证明了添加随即特征的方法能够提高GNN的求解能力，为实践提供了理论依据。

　　本文研究了作为GNN表达能力度量的双连通性。作者提出了一种利用节点间距离的新算法，并在合成和现实世界数据中进行了验证。

　　运筹学在国内，远没有新兴的人工智能以 及传统学科统计来的普及。人工智能、统计最后几乎都能化简成求解关于一个能量/损失函数的优化问题。但相信很多人不知道，运筹学正是研究优化理论的学科。而因此，我把运筹学称为人工智能、大数据的“引擎”，正本清源其在人工智能中重要性。这篇文章包括的内容有运筹学、线性规划回顾 、整数规划问题 、什 么是组合优化江南APP官方网站、非凸优化、整数规划与非凸优化的关系、整数规划和非凸优化为何重要、整数规划在工业界的应用、整数规划在AI的应用和展望。

　　Weisfeiler-Lehman算法在大多数图上会得到一个独一无二的特征集合，这意味着图上的每一个节点都有着独一无二的角色定位。因此，对于大多数非规则的图结构，经算法处理后得到的特征可以作为图是否同构的判别依据，也就是WL测试。

　　最优潮流是从电力系统稳定运行的角度来调整系统中各种控制设备的参数，在满足节点正常功率平衡及各种安全指标的约束下，实现目标函数最小化的优化过程。

　　在人工神经网络的数学理论中，通用逼近定理是在给定的函数空间内建立算法生成的函数类密度的结果。通常，这些结果涉及前馈架构在两个欧几里得空间之间的连续函数空间上的逼近能力，并且该逼近是相对于紧凑收敛拓扑而言的。

　　在实分析的数学领域，卢辛定理（以尼古拉·卢辛命名）或卢辛准则指出，有限函数几乎处处是可测的，当且仅当它在几乎所有域上都是连续函数时。

　　扫码参与图神经网络与组合优化读书会，加入群聊江南APP官方网站，获取系列读书会回看权限，成为图神经网络社区的种子用户，与社区的一线科研工作者与企业实践者沟通交流，共同推动图神经网络社区的发展。

　　自1956年“人工智能”诞生于达特茅斯会议以来，已经经历了从早期的以符号推理为主体的第一代人工智能，和以深度神经网络、机器学习为主体的第二代人工智能。ChatGPT的横空出世、生成式AI的普及、AI for Science等新领域的突破，标志着第三代人工智能的呼之欲出。可微分编程、神经微分方程、自监督学习、生成式模型、Transformer、基于图网络的学习与推理、因果表征与因果推断江南APP官方网站，基于世界模型的强化学习……，所有这些脱胎于前两代人工智能的技术要素很有可能将构成第三代人工智能的理论与技术的基础。

　　本课程试图系统梳理从机器学习到大语言模型，从图神经网络到因果推理等一系列可能成为第三代人工智能基础的技术要素，为研究者或学生在生成式AI、大模型、AI for Science等相关领域的学习和研究工作奠定基础。

　　AI+Science 是近年兴起的将人工智能和科学相结合的一种趋势。一方面是 AI for Science，机器学习和其他 AI 技术可以用来解决科学研究中的问题，从预测天气和蛋白质结构，到模拟星系碰撞、设计优化核聚变反应堆，甚至像科学家一样进行科学发现，被称为科学发现的“第五范式”。另一方面是 Science for AI，科学尤其是物理学中的规律和思想启发机器学习理论，为人工智能的发展提供全新的视角和方法。

　　集智俱乐部联合斯坦福大学计算机科学系博士后研究员吴泰霖（Jure Leskovec 教授指导）、哈佛量子计划研究员扈鸿业、麻省理工学院物理系博士生刘子鸣（Max Tegmark 教授指导），共同发起以”为主题的读书会，探讨该领域的重要问题，共学共研相关文献。读书会从2023年3月26日开始，每周日早上 9:00-11:00 线周。欢迎对探索这个激动人心的前沿领域有兴趣的朋友报名参与。

　　现实世界中大量问题的解决依赖于算法的设计与求解。传统算法由人类专家设计，而随着人工智能技术不断发展，算法自动学习算法的案例日益增多，如以神经网络为代表的的人工智能算法，这是算法神经化求解的缘由。在算法神经化求解方向上，图神经网络是一个强有力的工具，能够充分利用图结构的特性，实现对高复杂度算法的高效近似求解。基于图神经网络的复杂系统优化与控制将会是大模型热潮之后新的未来方向。

　　为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院助理教授黄文炳，共同发起「图神经网络与组合优化」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在 AI for Science 中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。读书会从2023年6月14日开始，每周三晚 19:00-21:00 举行，持续时间预计8周。欢迎感兴趣的朋友报名参与！