导读

2020年虽然已经结束，但在这一年中，图机器学习（GML）领域出现了许多新的研究进展。以下是我对2020年GML趋势的一些看法及对相关论文的讨论。

引言

本文旨在介绍2020年图机器学习领域的前沿研究，而不是详细介绍其基本概念，如图神经网络（GNN）。以下是我在顶级学术会议上发现的主要趋势：

• 在GML领域，共有150篇论文提交，其中有三分之一被接受。这相当于所有接受论文的10%左右。

我阅读了大部分GML论文，并列出了以下2020年的主要趋势：

1. 对GNN有更扎实的实际理解
2. 最新最酷的GNN应用
3. 知识图谱逐渐流行
4. 图嵌入的新框架

接下来我们将逐一探讨这些趋势。

1. 对GNN有更扎实的实际理解

我很高兴看到这一趋势，因为它表明GML领域正在从启发式的应用转向更加合理的理论方法。尽管关于GNN的工作还有很多待解决的问题，但已有许多重要的研究成果。

我从最喜欢的一篇论文开始：《What graph neural networks cannot learn: depth vs width》。这篇论文在技术简单性、实际影响和理论深度之间找到了很好的平衡。

• 它表明，为了使GNN能够有效解决常见的图问题（如检测环、估计直径、顶点覆盖等），节点嵌入的维度（网络的宽度，w）与层数（网络的深度，d）的乘积应与图的大小n成比例，即dw = O(n）。然而，当前大多数GNN的层数（通常为2-5层）和嵌入维度（通常为100-1000）相对较小，不足以满足这一条件。同时，过大的网络在计算和存储方面成本较高。

其他相关研究包括Oono & Suzuki和Barcelo等人所做的工作。前者研究了GCN的损失函数对节点分类的影响，后者则探讨了GNN与节点分类器的关系。

其他理论方面的研究还包括Hou等人对GNN图形信息的度量，以及Srinivasan & Ribeiro对基于角色和基于距离的节点嵌入等价性的度量。

2. GNN的新酷应用

我还很高兴看到GNN在实际任务中的应用。今年的应用包括修复JavaScript中的bug、玩游戏、回答类似于IQ测试的问题、优化TensorFlow计算图、生成分子和生成对话系统中的问题。

例如，在《HOPPITY: Learning Graph Transform to Detect and Fix Bugs In Programs》中，代码被转换为抽象语法树，然后通过GNN进行预处理以获得代码嵌入。通过多轮图形编辑操作符（添加或删除节点，交换节点值或类型），可以逐步修复代码。为了决定需要修改哪些节点，作者使用了一个指针网络，该网络接受图的嵌入和编辑历史，并选择要修改的节点。随后，通过LSTM网络执行修复，该网络也获取图嵌入和编辑上下文。实验结果显示，这种方法在GitHub提交上优于其他基线方法。

另一篇论文《LambdaNet: Probabilistic Type Inference using Graph Neural Networks》展示了如何利用GNN进行类型推断。作者提出了一个包含程序变量及其关系的超图模型，然后通过训练GNN生成图变量和可能类型的嵌入，最终预测最有可能的类型。实验结果表明，LambdaNet在标准变量类型（如布尔类型）和用户定义类型中表现良好。

其他有趣的应用包括《Abstract Diagrammatic Reasoning with Multiplex Graph Networks》，展示了如何使用GNN在类IQ测试中进行推理；《Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs》，展示了如何使用强化学习优化TensorFlow计算图；以及《Graph Zoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding》，介绍了如何通过多尺度谱方法加速图嵌入。

3. 知识图谱变得越来越流行

今年出现了许多关于知识图谱推理的研究。知识图谱是一种表示理想结构化数据的有效方法，其中节点和边具有实际意义。例如，“史蒂芬·斯皮尔伯格的哪些电影在2000年之前获得了奥斯卡奖？”这类问题可以通过逻辑查询来回答。

《Query2box: Reasoning over Knowledge Graphs in Vector Space Using Box Embeddings》提出了一种使用盒嵌入的新方法，使得可以执行自然的交集操作。而《Differentiable Learning of Numerical Rules in Knowledge Graphs》则探讨了如何使用数值规则和规则学习方法来处理复杂的查询。

此外，《You CAN Teach an Old Dog New Tricks! On Training Knowledge Graph Embeddings》展示了如何通过调整超参数来改进旧模型的性能。《A Fair Comparison of Graph Neural Networks for Graph Classification》则对GNN模型在图分类任务中的表现进行了公正的评估。

4. 图嵌入的新框架

图嵌入是图机器学习的一个长期主题，今年出现了一些新的方法来改进图表示的学习。

《GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding》提出了一种多尺度谱方法，首先将原始图简化为更小的图，从而快速计算节点嵌入，然后再恢复原始图的嵌入。这种方法在加速和精度方面都有显著提升。

其他研究还包括对图分类任务的详细分析，如《A Fair Comparison of Graph Neural Networks for Graph Classification》和《Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classification》，这些研究提供了对现有模型的重新评估，并提出了改进的方向。

总结

随着顶级会议提交论文数量的增加，我们可以期待在2020年GML领域会有更多有趣的研究成果。从启发式的应用到更加合理的理论方法，GNN在解决许多可以用图表示的实际问题上发挥了重要作用。GML正处于图论和机器学习交叉领域的初期阶段，未来还有许多值得期待的发展。