Guide2020刚刚开始，但我们已经在最新的研究论文中看到了图机器学习（GML）的趋势。以下是我对GML2020的重要内容的看法以及对这些论文的讨论。简介本文的目的不是介绍神经网络（GNNs）等GML的基本概念，而是介绍我们在顶级科学会议上看到的前沿研究。GML领域共投稿150篇，三分之一的论文被录用。这相当于所有已接受论文的大约10%。我阅读了大部分GML论文，以下是我列出的2020年趋势：对GNN的理论理解更扎实；最新最酷的GNN应用；知识图谱越来越流行；新的图形嵌入让我们一个一个地看框架。1.对GNN的更扎实的理论理解看到这一趋势我特别兴奋，因为它表明GML领域的成熟和以前的启发式方法正在被新的理论解决方案所取代。关于图神经网络还有很多需要理解的地方，但是关于GNN的工作原理有很多重要的结果。我将从我最喜欢的一篇文章开始：图神经网络无法学习的内容：深度与宽度。本文在技术简单性、高实践影响和深刻的理论见解之间取得了惊人的平衡。它表明节点嵌入的维度（网络的宽度，w）乘以层数（网络的深度，d）应该与图的大小n成正比，即dw=O(n)，如果我们希望GNN能够计算图问题的流行解决方案（例如循环检测、直径估计、顶点覆盖等）。因此，许多当前的GNN实现无法达到此条件，因为层数（在许多实现中大约为2-5层）和嵌入的维数（大约100-1000层）与图的大小相比并不大。另一方面，在当前环境下，大型网络的计算和存储成本太高，这就提出了一个问题：我们应该如何设计一个“高效”的GNN，这是我们未来需要解决的问题.该论文还借鉴了80年代的分布式计算模型，证明GNN本质上做同样的事情。那里有更多的结果，所以我建议你去看看。同样，另外两篇论文Oono&Suzuki和Barcelo等人也研究了GNN的能力。第一个是GraphNeuralNetworkslossexpressionPowerforNodeClassification，它表明在一定的权重条件下，当层数增加时，GCNs只有节点度和连通分量（由拉普拉斯谱确定）。学不会。这个结果是马尔可夫过程收敛到唯一平衡这一众所周知的性质的推广，其中收敛速度由转移矩阵的特征值决定。在第二篇论文TheLogicalExpressivenessofGraphNeuralNetworks中，作者展示了GNN与它们可以捕获的节点分类器类型之间的联系。我们已经知道一些GNN与WL同构检查一样强大，即当且仅当它们被GNN分类为相同时，WL对两个节点着色相同。但是GNN能否捕获其他分类函数？例如，假设一个布尔函数当且仅当一个图有一个孤立的顶点时将true分配给所有节点。GNN可以捕获这种逻辑吗？直觉上不会，因为GNN是一种消息传递机制，如果图的一部分和另一部分（两个连接的组件）之间没有链接，那么消息将不会被传递。因此，一个推荐的简单修复是在邻居聚合之后添加一个读出操作，以便在更新所有特征时每个节点都具有关于图中所有其他节点的信息。其他理论工作包括Hou等人对GNN中图形信息使用的度量，以及Srinivasan和Ribeiro对基于角色和基于距离的节点嵌入的等效性的度量。2.GNN的新酷应用看到GNN如何应用于实际任务也很棒。今年的应用包括修复Javascript中的错误、玩游戏、回答类似智商的测试、优化TensorFlow计算图、分子生成和对话系统中的问题生成。在HOPPITY中：学习图转换以检测和修复程序中的错误。代码被转换为抽象语法树，然后由GNN对其进行预处理以获得代码嵌入。思路是给定一个处于初始状态的图，通过多轮图编辑操作（添加或删除节点，替换节点值或类型）对其进行修改。为了了解应该修改图形的哪些节点，他们使用了一个指针网络，该网络获取了图形的嵌入和编辑历史，并选择了节点。然后，使用LSTM网络执行修复，该网络还获取图形嵌入和编辑的上下文。作者在GitHub提交上验证了这种方法，显示出比其他不太通用的基线有显着改进。同样，Wei等人的工作LambdaNet：使用图神经网络的概率类型推断。作者提出了一个依赖于类型的超图，其中包含作为节点的程序变量以及它们之间的关系，例如逻辑（例如布尔类型）或上下文（例如相似的变量名称）约束。然后，首先训练GNN模型以生成图变量和可能类型的嵌入，这些嵌入用于预测最可能的类型。在实验中，LambdaNet在标准变量类型（例如Boolean）和用户定义类型上都表现更好。Wang等人的论文AbstractDiagrammaticReasoningwithMultiplexGraphNetworks。展示了如何使用GNN对类似IQ的测试进行推理（Raven渐进矩阵(RPM)和图三段论(DS)）。在RPM任务中，为矩阵的每一行组成一个图，其中边嵌入是通过前馈模型获得的，然后是图摘要。由于最后一行有8个可能的答案，因此创建了8个不同的图，每个图都与前两行连接起来，以通过ResNet模型预测IQ分数。DeepMind的一篇论文ReinforcedGeneticAlgorithmLearningforOptimizingComputationGraphs提出了一种RL算法来优化TensorFlow计算图的计算成本。图通过标准的消息传递GNN进行处理，该GNN生成与图中每个节点的调度优先级相对应的离散嵌入。这些嵌入被输入到遗传算法BRKGA中，该算法确定每个节点的设备放置和调度。通过模型的训练，优化得到的TensorFlow图的实际计算成本。GNN的其他有趣应用包括Shi等人的分子生成、Jiang等人的游戏和Chen等人的对话系统。3、知识图谱越来越流行。今年有很多关于知识图谱推理的论文。本质上，知识图谱是一种表示事实的结构化方式。与一般的图不同，知识图谱中的节点和边实际上是有一定意义的，比如电影中的演员或演员的名字（见下图）。知识图上的一个常见问题是回答复杂的问题，例如“史蒂文·斯皮尔伯格的哪部电影在2000年之前获得了奥斯卡奖？”，这可以转化为逻辑查询{Win(Oscar,V)∧Directed(Spielberg,V)∧ProducedBefore(2000,V)}}。Ren等人的论文Query2box：使用框嵌入对向量空间中的知识图进行推理。这种方法允许执行自然相交操作，即∧连接，因为它具有新的矩形框结构。然而，建立一个联合，即分离，并不是那么简单，因为它可能会导致不重叠的区域。此外，为了使用嵌入对任何查询进行准确建模，根据VC维度衡量的嵌入之间的距离函数的复杂性应该与图中实体的数量成正比。相反，有一个很好的技巧可以将析取查询替换为DNF形式，其中并集仅出现在计算图的末尾，这可以有效地简化为每个子查询的简单距离计算。在同一主题上，Wang等人。使用数字实体和规则发表论文“知识图中数字规则的微分学习”*。*例如，对于知识图谱引用，可以有一个规则，influences(Y,X)←colleagueOf(Z,Y)∧supervisorOf(Z,X)∧hasCitation>(Y,Z)，即学生X是通过了同一个导师Z的同学Y的影响，这个Z的引用次数更多了。规则右侧的每个关系都可以表示为一个矩阵，而寻找缺失链接的过程可以表示为关系与实体向量的连续矩阵乘法，这个过程称为规则学习。由于矩阵的构造方式，神经方法只能使用colleagueOf(Z,Y)等分类规则。作者的贡献是一种有效使用hasCitation>(Y,Z)和否定运算符等数值规则的新颖方法，表明实际上不需要显式具体化此类矩阵，从而大大减少了运行时间。在今年的GML上，机器学习的另一个反复出现的主题是重新评估现有模型以及它们在公平环境中的表现。喜欢这篇论文：你可以教老狗新技巧！Ruffinelli等人关于训练知识图嵌入。表明新模型的性能通常取决于实验训练的“次要”细节，例如损失函数的形式、正则化设备和采样方案。在一项大型消融研究中，作者观察到旧方法（例如RESCAL模型）只能通过适当调整超参数来实现SOTA性能。该领域还有许多其他有趣的文章。艾伦等人。显示模型如何在维基百科图上检索回答给定查询的推理路径。Tabacof&Costabello解决了图嵌入模型概率校准的重要主题。他们指出，流行的嵌入模型TransE和ComplEx，它们使用sigmoid函数的变换对数来获得概率，都是欠校准的，即低估或高估事实的存在。他们的方法依赖于生成不良三元组作为负样本，而已知的方法（例如Platt缩放和等渗回归）使用这些负样本来校准概率。4.图嵌入的新框架图嵌入是图机器学习中一个长期存在的话题，今年关于我们应该如何学习图表示有一些新的观点。邓等人的总体思路。在GraphZoom:AMulti-levelSpectralApproachforAccurateandScalableGraphEmbedding中，首先将原始图简化为更小的图，可以快速计算节点嵌入，然后恢复原始图嵌入。首先，根据属性相似性，原始图增加了与节点的k最近邻之间的链接相对应的附加边。然后，将图粗化：通过局部谱方法将每个节点投影到低维空间并聚合成簇。任何无监督的图嵌入方法，例如深度步进或深度图信息挖掘，都可以在小图上获得节点嵌入。在最后一步中，生成的节点嵌入（本质上代表集群嵌入）使用平滑运算符迭代地广播回来，以防止不同的节点具有相同的嵌入。在实验中，GraphZoom框架比node2vec和DeepWalk方法实现了惊人的40倍加速，准确率提高了10%。多篇论文详细分析了图分类问题的研究成果。Errica等人的AFairComparisonofGraphNeuralNetworksforGraphClassification的贡献是在这个问题上对GNN模型进行了公正的重新评估。文章给出了一个简单的基线，它不利用图的拓扑结构（它使用节点特征聚合）可以与SOTAGNNs相媲美。这种令人惊讶的现象显然是由Orlova等人发表的。2015年之前，但没有获得大量读者。这项工作的一个很好的结果是在PyTorch-Geometric上的流行数据集和代码基准测试上获得了公平的SOTA。在我们的工作UnderstandingIsomorphismBiasinGraphDataSets中，我们发现在MUTAG和IMDB等常用数据集上，许多图具有同构副本，甚至考虑节点属性。此外，在这些同构图中，有许多不同的目标标签，这自然会给分类器引入标签噪声。这表明使用所有可用的网络元信息（例如节点或边缘属性）以获得更好的模型性能的重要性。在另一项工作中，是否需要强大的图神经网络？图分类剖析，Chen等人。表明如果非线性邻域聚合函数被线性部分代替，其中包括邻居的度和图属性的传播，那么模型的性能不会下降，——这与之前的许多图数据集的说法是一致的对于分类来说是微不足道的，并提出了针对此任务的适当验证框架的问题。总结随着优秀会议的投稿率越来越高，我们可以期待2020年GML领域会有很多有趣的结果。我们已经看到该领域从深度学习在图上的启发式应用到更理性的方法和基本问题的转变图模型的范围。GNN在解决许多可以用图表示的实际问题中占有一席之地，但我希望总的来说，GML只是触及了图论和机器学习交叉领域的表面，我们应该继续关注即将到来的结果。
