深蓝学院-GNN课程笔记13-图神经网络的高级应用

这个系列是深蓝学院图深度学习理论与实践的同步课程笔记。课程内容涉及图深度学习的基础理论与应用，本节主要介绍图神经网络的高级应用。

图上的组合优化问题

图上的很多组合优化问题，如最小顶点覆盖问题(MVC)、旅行商问题(TSP)都是NP-hard，目前我们仍然无法找到多项式时间的解而必须使用一些启发式算法。如何设计好的启发式算法是非常具有挑战性的问题，这往往需要大量的与具体问题相关的知识以及反复试验。

目前已经有研究人员尝试使用图神经网络来从给定的样本中学习这样的启发式算法，然后为未知的任务提供解。具体来说，我们首先需要把这样的组合优化问题转换成一个图机器学习问题，然后就可以利用图神经网络的框架来进行求解。对于最小顶点覆盖问题，我们可以把它建模成一个节点二分类问题；而旅行商问题则可以建模为一个边二分类问题。除了标准分类损失，使用图神经网络时往往还需要考虑问题自身的约束这样才能保证得到有效的解。

学习程序表示

我们可以使用机器学习来实现对源代码的各种自动化任务，如变量名误用、漏洞检测等。目前常用的自动化方法是借助NLP的相关方法来处理源代码，而显然这类方法很难捕获代码中的语法和语义关系。近年来研究人员尝试使用图来表示代码然后利用图神经网络来学习其表示以用于下游任务。

从源代码构建图的方法有很多，常用的图包括抽象语法树(AST)、控制流图(CFG)、数据流图(DFG)、自然代码序列(NCS)等。我们可以将这些图进行组合来程序的语法和语义信息，然后借助图神经网络执行各种各样的检测任务。

物理中相互作用的动力系统的推理

相互作用系统在自然界中无处不在。最常见的相互作用系统是N-body系统，其中N个对象之间相互施加引力，而任务的目标是在给定动力系统历史的情况下预测对象未来的轨迹。

显然我们可以把N-body系统建模成一个全连接图，然后利用图神经网络来预测每个节点(对象)的运动状态。