本文转载自雷锋网。如需转载，请在雷锋网官网申请授权。2019年绝对是图机器学习（GML）大火的一年。所有的学术会议，图神经网络会场总是座无虚席。之所以图机器学习的研究在2019年突然火起来，是因为在过去的几年里，虽然深度学习在欧几里德空间的数据上取得了巨大的成功，但在很多实际应用场景中，数据往往是从非欧式空间生成的。欧几里得空间。正如阿里达摩院曾在2019年提到的：“纯深度学习已经成熟，图研究与深度学习相结合，将端到端学习与归纳推理相结合，有望解决深度学习无法处理的关系推理和可预测问题。“可解释性等一系列问题。”在过去的一年里，图机器学习得到了蓬勃的发展，从各大会议上图机器学习的火爆场面也可以看出。新年已经过去了一个月，所以可以2020年图机器学习的热度持续？会有哪些新的研究趋势？4月在埃塞俄比亚召开的ICLR2020就是一个很好反映这些问题的会议。本次会议由YoshuaBengio和YannLeCun领衔，两大深度学习巨头，旨在专注于深度学习各个方面的前沿研究。在ICLR2020中，共有150篇投稿与图机器学习相关，其中近1/3被接受，这也说明图机器学习依然火热，我们不妨将这些论文按照理论、应用、知识图谱、图嵌入等进行划分，一窥2020年图机器学习的研究趋势。注：文章涉及论文，可关注雷锋网“AI科技评论”微信公众号，后台回复“2020GML趋势”即可下载。1.GNN理论知识会更加扎实从目前的情况来看，图机器学习领域在成熟的道路上越走越远，但是图神经网络还有很大的提升空间。在过去的一年里，图神经网络得到了不断完善，因此诞生了很多理论研究。在对2020年做出预测之前，我们先简单回顾一下图神经网络的重要理论成果！Whatgraphneuralnetworkscannotlearn:depthvswidthhttps://openreview.net/forum?id=B1l2bp4YwS洛桑联邦理工学院AndreasLoukas的这篇论文，无论从影响力、简洁性还是理论理解的深度上来说，都是无疑是论文中的模型。它表明，当我们用GNN计算通常的图问题时，节点嵌入的维数（网络的宽度，w）乘以层数（网络的深度，d）应该与图的大小成正比图n，即dW=O(n)。但现实情况是，当前GNN的许多实现无法达到此条件，因为与图的大小相比，层数和嵌入数不够大。另一方面，更大的网络在实践中并不适用，这引发了如何设计有效的GNN的问题，这当然是研究人员未来工作的重点。需要明确的是，该论文还从80年代的分布式计算模型中汲取灵感，证明GNN本质上在做同样的事情。这篇文章也包含了很多有价值的结论，强烈推荐阅读原文。可关注雷锋网（公众号：雷锋网）微信公众号“AI技术评论”，后台回复“2020GML趋势”下载论文。同样，在另外两篇论文中，Oono等人。研究了GNN的能力。第一篇是《图神经网络在节点分类中失去了表达能力》，第二篇是《图神经网络的逻辑表达》。GraphNeuralNetworksExponentiallyLoseExpressivePowerforNodeClassificationshttps://openreview.net/forum?id=S1ldO2EFPr这篇论文表明：“在已知权重的特定条件下，当层数增加时，GCN，除了节点度和连通性之外的组件，其他什么也学不到。”该结果扩展了马尔可夫过程收敛到唯一平衡点的性质，并表明收敛速度由转移矩阵的特征值决定。图神经网络的逻辑表现力https://openreview.net/pdf?id=r1lZ7AEKvB这篇论文展示了GNN和节点分类器类型之间的联系，在此之前，我们了解到GNN和WL同构检查一样强大。但是GNN是否可以获得其他分类功能呢？直观上不能，因为GNN是消息传递机制，如果图的一部分和另一部分之间没有链接，那么两者之间就不会传递消息。因此论文提出了一个简单的解决方案：在邻域聚合之后添加一个读出操作，使得每个节点都连接起来在更新所有特征时对图中的所有其他节点。还有很多其他的理论工作，包括Hou等人测量图信息在GNN中的使用。以及Srinivasan和Ribeiro提出的基于角色和基于距离的节点嵌入的等价性讨论。论文链接如下：MeasuringandImprovingtheUseofGraphInformationinGraphNeuralNetworkshttps://openreview.net/forum?id=rkeIIkHKvSOntheEquivalencebetweenPositionalNodeEmbeddingsandStructuralGraphRepresentationshttps://openreview.net/forum?id=SJxzFySKwH2,新的炫酷应用层出不穷在过去的一年里，GNN已经应用于一些实际任务中。例如，已经有用于玩游戏、回答智商测试、优化TensorFlow计算的图形、分子生成和对话系统中的问题生成的程序。HOPPITY:LEARNINGGRAPHTRANSFORMATIONSTODETECTANDFIXBUGSINPROGRAMShttps://openreview.net/pdf?id=SJeqs6EFvB在论文中，作者提出了一种同时检测和修复Javascript代码错误的方法。具体操作是将代码转化为一棵抽象语法树，然后让GNN对其进行预处理得到代码embedding，然后通过多轮图编辑算子（增删节点、替换节点值或类型）。为了了解应该修改图形的哪些节点，作者使用了一个指针网络，该网络采用图形嵌入来使用LSTM网络选择要修复的节点。当然，LSTM网络也接受图形嵌入和上下文编辑。LambdaNet:ProbabilisticTypeInferenceusingGraphNeuralNetworkshttps://openreview.net/pdf?id=Hkx6hANtwH类似的应用在上面的论文中也有体现。德克萨斯大学奥斯汀分校的作者研究了如何在Python或TypeScript等语言中推断变量类型。更具体地说，作者给出了一个类型依赖超图（typedependencyhypergraph），它包含了程序的变量作为节点以及它们之间的关系，比如逻辑关系、上下文约束等；然后为图和可能的类型变量训练GNN模型以生成嵌入，并结合可能性进行预测。AbstractDiagrammaticReasoningwithMultiplexGraphNetworkshttps://openreview.net/pdf?id=ByxQB1BKwH在智商测试的应用中，上面的论文展示了GNN是如何进行智商测试的，比如Raven'stest（RPM）和图三段论（DS）。具体来说，在RPM任务中，矩阵的每一行组成一个图，通过前馈模型为其求出edgeembedding，然后对图进行汇总。由于最后一行有8个可能的答案，因此创建了8个不同的图，每个图都与前两行连接起来，以通过ResNet模型预测IQ分数。如下图所示：来自：https://openreview.net/pdf?id=ByxQB1BKwHReinforcedGeneticAlgorithmLearningforOptimizingComputationGraphshttps://openreview.net/pdf?id=rkxDoJBYPBDeepMind在上述论文中提出了一种RL算法至优化TensorFlow计算图的开销。该图先经过标准GNN处理，然后生成图中各节点调度优先级对应的离散化embedding，最后将embedding馈入遗传算法BRKGA进行模型训练，从而优化了图的实际情况获得了TensorFlow图。计算开销。值得注意的是，遗传算法决定了每个节点的放置和调度。类似的酷炫应用还有石辰策的分子结构生成、蒋杰川的游戏玩法和陈宇的游戏玩法等。论文链接如下：GraphConvolutionalReinforcementLearninghttps://openreview.net/forum?id=HkxdQkSYDBReinforcementLearningBasedGraph-to-SequenceModelforNaturalQuestionGenerationhttps://openreview.net/forum?id=HygnDhEtvr3，知识图谱会越来越流行今年的ICLR大会上，出现了很多关于知识图谱推理的论文。知识图示例（来源：https://arxiv.org/abs/1503.00759）本质上，知识图是一种表示事实的结构化方式。与一般图谱不同的是，知识图谱的节点和边实际上都有一定的含义，比如演员的名字、电影片名等。知识图谱中一个常见的问题是如何回答一些复杂的问题，比如“斯皮尔伯格的电影是哪部wontheOscarbefore2000?",这个问题被翻译成逻辑查询语言：使用BoxEmbeddingshttps://openreview.net/forum?id=BJgr4kSFDSQuery2BoxReasoningframeworkinStanfordUniversityHongyuRenetal.在他们的工作中，他们建议将查询嵌入到潜在空间中，而不是作为一个点（作为一个矩形框）。QUERY2BOX的两个操作和距离函数的几何例子这种方法使得可以很自然地进行求交操作（即合取∧）得到一个新的矩形框。但是对于联合操作（即析取∨），就没那么简单了，因为它可能会产生不重叠的区域。此外，为了使用嵌入准确地对所有查询进行建模，嵌入之间的距离函数（由VC维度测量）的复杂性与图中实体的数量成正比。但是，有一个很好的技巧可以将析取(∨)查询转换为DNF形式。此时AND操作只在图计算的最后进行，可以有效减少每次子查询的距离计算。知识图中数字规则的微分学习https://openreview.net/forum?id=rJleKgrKwSCMU的Po-WeiWang等人。在一篇类似主题的文章中，他们提出了一种处理数字实体和规则的方法。引用知识图谱（CitationKG）示例例如要引用知识图谱（CitationKG），可以有一个规则：influences(Y,X)←colleagueOf(Z,Y)∧supervisorOf(Z,X)∧hasCitation>(Y,Z)这是一个典型的情况，学生X受到他的导师Z的同事Y的影响（Y的引用率很高）。这条规则右边的每个关系都可以表示为一个矩阵，寻找缺失链接的过程可以表示为关系和实体向量的连续矩阵乘积。这个过程称为规则学习。由于矩阵的构造方式，神经网络方法只能使用分类规则colleagueOf(Z,Y)。作者的贡献在于，他们通过一种新颖的方法证明了在实践中不需要显式地表示这些矩阵，从而有效地处理了像hasCitation>(Y,Z)、取反运算这样的数值规则，这大大减少了运行时间。您可以教老狗新技巧！OnTrainingKnowledgeGraphEmbeddingshttps://openreview.net/forum?id=BkxSmlBFvr今年图神经网络（或者说机器学习）中经常出现的一个研究方向是：对已有的模型进行重新评估，在公平的环境下进行评估。上述文章就是其中之一。他们的研究表明，新模型的性能往往取决于实验训练中的“次要”细节，例如损失函数的形式、正则化器、采样方案等。在他们的大规模消融研究中，作者观察到，通过适当调整旧方法（例如RESCAL模型）的超参数，可以获得最先进的性能。当然，这个领域还有很多其他有趣的作品。艾伦等人。基于词嵌入的最新研究，进一步探索学习关系和实体表示的潜在空间。浅井等。显示模型如何在回答给定查询的维基百科图上检索推理路径。Tabacof和Costabello讨论了图嵌入模型概率校准中的一个重要问题。他们指出，目前流行的嵌入模型TransE和ComplEx（通过将logit函数转换为sigmoid函数来获取概率）存在误修正，即在事实中存在低估或高估。论文链接如下：OnUnderstandingKnowledgeGraphRepresentationhttps://openreview.net/forum?id=SygcSlHFvSLearningtoRetrieveReasoningPathsoverWikipediaGraphforQuestionAnsweringhttps://openreview.net/forum?id=SJgVHkrYDHProbabilityCalibrationforKnowledgeGraphEmbeddingModelshttps://openreview.net/forum?id=S1g8K1BFwS4,ANewFrameworkforGraphEmbeddingGraphembedding是图机器学习中长期存在的研究课题，今年有一些新的观点我们应该如何学习图表示出现了。GraphZoom:AMulti-levelSpectralApproachforAccurateandScalableGraphEmbeddinghttps://openreview.net/forum?id=r1lGO0EKDH康奈尔大学的ChenhuiDeng等人。提出了一种提高运行时间和准确性的方法，该方法可应用于任何无监督嵌入方法的节点分类问题。这篇论文的总体思路是先将原始图简化为更小的图，这样可以快速计算节点嵌入，然后恢复原始图的嵌入。最初，根据属性相似性用附加边扩充原始图，这些边对应于节点的k最近邻之间的链接。该图随后被粗化：每个节点通过局部谱方法投影到低维空间并聚合成簇。任何无监督图嵌入方法（例如DeepWalk、DeepGraphInfomax）都可以获得小图上的节点嵌入。在最后一步中，生成的节点嵌入（本质上代表集群嵌入）使用平滑运算符迭代广播，防止不同节点具有相同的嵌入。在实验中，GraphZoom框架相比node2vec和DeepWalk实现了惊人的40倍加速，准确率提升了10%。AFairComparisonofGraphNeuralNetworksforGraphClassificationhttps://openreview.net/forum?id=HygDF6NFPB已经有很多论文详细分析了图分类问题的研究成果。费德里科埃里卡等人。来自比萨大学的GNN模型在图分类问题上重新评估。他们的研究表明，不利用图拓扑（仅应用聚合节点特征）的简单基线可以实现与SOTAGNN相当的性能。事实上，这一令人惊讶的发现是由Orlova等人发表的。2015年，但并未引起广泛关注。UnderstandingIsomorphismBiasinGraphDataSetshttps://openreview.net/forum?id=rJlUhhVYvSSkolkovo科学技术研究所IvanovSergey等人在他们的研究中发现，在MUTAG和IMDB等常用数据集中，即使考虑节点属性，许多图将具有同构副本。而且，在这些同构图中，很多都有不同的目标标签，这自然会给分类器引入标签噪声。这表明利用网络中所有可用的元信息（例如节点或边缘属性）来提高模型性能非常重要。是否需要强大的图神经网络？ADissectiononGraphClassificationhttps://openreview.net/forum?id=BJxQxeBYwH另一部作品是UCLA孙一舟团队的作品。这项工作表明，如果将原来的非线性邻居聚合函数替换为线性邻居聚合函数，模型的性能不会下降。这与之前“图数据集对分类影响不大”的普遍观点相悖。同时这项工作提出了如何为此类任务找到合适的验证框架的问题。
