丹凤千字科普：excel一行等于另外两行的乘积（详细资料介绍）

文章标题：图机器学习（GML）在2020年的趋势洞察

在2020年刚刚过去的一个多月里，我们已经可以从最近的研究论文中窥见图机器学习（Graph Machine Learning，GML）的未来趋势。机器学习研究科学家Sergei Ivanov分享了他对GML发展趋势的看法，并介绍了近期相关的研究论文。

本文的目的并非介绍GML的基础概念如图网络（Graph Neural Networks，GNN），而是关注顶会前沿研究。作者概述了学术顶会ICLR 2020提交的关于GML的研究论文概况：共有150篇GML研究论文提交至此次会议，接收率为三分之一，约占全部接收论文的10%。

作者阅读了大部分论文，并列出他对2020年GML研究趋势的判断，包括：对GNN的理论理解更加深入、出现新的GNN应用、知识图谱更加流行以及诞生新的图嵌入框架。

一、对GNN的理论理解更加深入

我对这一趋势感到尤为振奋，因为它表明GML领域的成熟，先前的启发式方法正在被新的理论解决方案所取代。要完全理解图网络还有很长的路要走，但关于GNN工作原理的重要研究成果已经出现。

例如，我最喜欢的一项研究是Andreas Loukas的论文《What graph neural networks cannot learn: depth vs width》。这篇论文在技术简洁性、强大的实践影响力和意义深远的理论见解三者之间实现了完美的平衡。该研究证明，要想让GNN为常见的图问题（如环检测、直径估计、顶点覆盖等）提供解决方案，节点嵌入的维度与层数的乘积应与图大小成正比。目前许多GNN实现无法达到此条件，大型网络的代价高昂，这就提出了一个问题：如何设计高效的GNN？这是我们未来需要解决的任务。

类似地，以下两篇论文也探讨了GNN的力量。第一篇论文《Graph Neural Networks Exponentially Lose Expressive Power for Node Classification》证明，在特定权重条件下，当层数增加时，受拉普拉斯谱的影响，GCN只能学习节点度和连通分支。该结果是马尔可夫过程收敛至唯一均衡这一著名特性的泛化。

另一篇论文《The Logical Expressiveness of Graph Neural Networks》展示了GNN和多种节点分类器之间的联系。我们已经知道一些GNN和同构的WL test一样强大，即当且仅当两个节点被GNN判断为同一类别时，WL赋予二者相同的颜色。那么GNN具备其他分类功能吗？该研究提出了一种简单的方法来解决这个问题：在邻域聚合之后添加readout函数，这样当每个节点更新所有特征时，它具备图中其他节点的信息。

二、出现新的GNN应用

看到GNN被应用于实际任务也非常令人兴奋。在2020年，GNN将应用于修复Javascript中的bug、玩游戏、回答IQ类测、优化TensorFlow计算图、分子生成以及对话系统中的问题生成等任务。

类似的研究还包括Wei等人的《LambdaNet: Probabilistic Type Inference using Graph Neural Networks》，它主要探讨如何为Python或TypeScript等语言推断变量类型。该研究展示了一种类型依赖超图，图中的节点是程序变量，还编码了变量之间的关系，如逻辑约束或语境约束等。先训练一个GNN模型为图中的变量和可能的变量类型生成嵌入，然后利用嵌入预测具备最高似然的类型。实验结果表明，LambdaNet在标准变量类型和用户自定义类型中均获得了更好的性能。

三、知识图谱更加流行

这一年涌现出大量有关知识图谱的论文。知识图谱是一种表示事实的结构化方式，其节点和边均包含意义。例如演员姓名或参演电影等。知识图谱的常见任务是回答复杂的query，如“史蒂文斯皮尔伯格凭借哪部电影在2000年之前获得奥斯卡奖？”这个问题可以转换为逻辑query。为此Ren等人的论文《Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings》提出了一种将query作为矩形框嵌入潜在空间的方法，而不是作为一个点。该方法可以执行复杂的逻辑运算来得到新的矩形框，从而精确地建模任意query的嵌入。论文还提出了一种处理数值实体和规则的全新方法。Allen等人的论文《On Understanding Knowledge Graph Representation》则基于近期对词