2020年，图机器学习将走向何方？

2020年已经过去了一段时间，但我们可以从最近的研究论文中窥见图机器学习（Graph Machine Learning，GML）的发展趋势。本文作者、机器学习研究科学家Sergei Ivanov将分享他对2020年GML发展的看法，并讨论相关研究论文。

在ICLR 2020会议上，共有150篇GML研究论文被提交，接收率约为三分之一，占所有接受论文的10%左右。作者阅读了其中的大多数论文，并对其发展趋势进行了分析。

我对这一趋势感到非常兴奋，因为它表明GML领域正在走向成熟，之前的启发式方法正在被新的理论解决方案取代。虽然要完全理解图神经网络（GNN）还需要一段时间，但关于GNN工作原理的研究已经取得了一些重要进展。

关键研究成果

Andreas Loukas的论文：《What graph neural networks cannot learn: depth vs width》。该研究证明，为了让GNN为常见的图问题（如环检测、直径估计、顶点覆盖等）提供解决方案，节点嵌入的维度与层数的乘积应与图的大小成反比。目前许多GNN实现无法满足这一条件，因为层数和嵌入维度与图的大小相差甚远。此外，大型网络的计算成本高昂，这促使我们需要设计更高效的GNN。
其他相关论文：展示了GNN在某些情况下只能学习节点度和连通分支，以及在逻辑表达方面的能力有限。

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

具体应用案例

Dinella等人：《HOPPITY: Learning Graph Transformations to Detect and Fix Bugs in Programs》。该研究展示了一种新的方法，通过将代码转换为抽象语法树，然后使用GNN进行预处理，从而检测和修复JavaScript中的bug。这种方法在GitHub commit上得到了验证，证明其效果显著优于其他方法。
Wei等人：《LambdaNet: Probabilistic Type Inference using Graph Neural Networks》。该研究展示了如何利用GNN为Python或TypeScript等语言推断变量类型，实验结果表明LambdaNet在标准变量类型和用户自定义类型中表现良好。
Wang等人：《Abstract Diagrammatic Reasoning with Multiplex Graph Networks》。该研究展示了如何利用GNN在IQ测试中进行推理，特别是在Raven Progressive Matrices任务中，通过构建图形并使用ResNet模型预测IQ分数，取得了良好的效果。
DeepMind：《Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs》。该研究提出了一种强化学习算法，用于优化TensorFlow计算图的成本，通过结合GNN和遗传算法实现了高效的优化。

2020年涌现了许多关于知识图谱的研究。知识图谱是一种表示现实世界的结构化方式，与普通图不同的是，知识图谱的节点和边都包含意义。这些图常用于回答复杂的查询，例如“2000年前，史蒂文·斯皮尔伯格因哪部电影获得奥斯卡奖？”这种查询可以转换为逻辑查询。

关键研究成果

Ren等人：《Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings》。该研究提出了一种将查询作为矩形框嵌入潜在空间的方法，从而可以执行自然的交运算，而析取运算则通过转换为DNF形式来处理。
Wang等人：《Differentiable learning of numerical rules in knowledge graphs》。该研究提出了一种高效处理数值规则和否定运算符的方法，证明在实际应用中没有必要将这些矩阵显式具体化，从而大大减少了运行时间。

图嵌入是图机器学习领域的一个老话题，但今年出现了关于如何学习图表示的一些新观点。

Deng等人：《GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding》。该研究提出了一种新方法，可以为任意无监督嵌入方法延长运行时间并提升节点分类准确性。其整体思路是先将原始图缩减，以便快速计算节点嵌入，然后再恢复原始图的嵌入。
其他相关论文：探讨了图分类问题的先前结果，发现一些简单的基线方法在某些情况下性能与最先进的GNN相当。