正文

请到「今天看啥」查看全文

https://openreview.net/forum?id=S1ldO2EFPr

这篇论文表明：“在已知某些条件下的权重，当层数增加时，GCN除了节点度和连通分量以外，将无法学习其他任何内容。”这一结果扩展了“马尔可夫过程收敛到唯一平衡点”的性质，并表明其中收敛速度由转移矩阵的特征值决定。

The Logical Expressiveness of Graph Neural Networks

https://openreview.net/pdf?id=r1lZ7AEKvB

这篇论文展示了GNN与节点分类器类型之间的联系。在这之前，我们已经了解GNN与WL同构检验一样强大。但是GNN可以获得其他分类功能么？直观上不行，因为GNN是一种消息传递机制，如果图的一个部分和另一个部分之间没有链接，那么两者之间就不会传递消息。因此论文提出一个简单解决方案：在邻域聚合之后添加一个读出操作，以便每个节点在更新所有要素时与图中所有其他节点都有联系。

其他在理论上的工作还有很多，包括Hou等人测量GNN的图形信息的使用。以及 Srinivasan 和 Ribeiro提出的基于角色的节点嵌入和基于距离的节点嵌入的等价性讨论。论文链接如下：

Measuring and Improving the Use of Graph Information in Graph Neural Networks

https://openreview.net/forum?id=rkeIIkHKvS

On the Equivalence between Positional Node Embeddings and Structural Graph Representations

https://openreview.net/forum?id=SJxzFySKwH

2、新酷应用不断涌现

在过去的一年中，GNN已经在一些实际任务中进行了应用。例如已经有一些程序应用于玩游戏、回答智商测试、优化TensorFlow计算图形、分子生成以及对话系统中的问题生成。

HOPPITY: LEARNING GRAPH TRANSFORMATIONS TO DETECT AND FIX BUGS IN PROGRAMS

https://openreview.net/pdf?id=SJeqs6EFvB

在论文中，作者其提出了一种在Javascript代码中同时检测和修复错误的方法。 具体操作是将代码转换为抽象语法树，然后让GNN进行预处理以便获得代码嵌入，再通过多轮图形编辑运算符（添加或删除节点，替换节点值或类型）对其进行修改。 为了理解图形的哪些节点应该修改，论文作者使用了一个指针网络（Pointer network）， 该 网络采用了图形嵌入来选择节点，以便使用LSTM网络进行修复。 当然，LSTM网络也接受图形嵌入和上下文编辑。

LambdaNet: Probabilistic Type Inference using Graph Neural Networks

https://openreview.net/pdf?id=Hkx6hANtwH

类似的应用还体现在上面这篇论文中。来自得克萨斯大学奥斯汀分校的作者研究了如何推断像Python或TypeScript此类语言的变量类型。更为具体的，作者给出了一个类型依赖超图（type dependency hypergraph），包含了程序作为节点的变量以及它们之间的关系，如逻辑关系、上下文约束等；然后训练一个GNN模型来为图和可能的类型变量产生嵌入，并结合似然率进行预测。

Abstract Diagrammatic Reasoning with Multiplex Graph Networks

https://openreview.net/pdf?id=ByxQB1BKwH

在智商测试类的应用中，上面这篇论文展示了GNN如何进行IQ类测试，例如瑞文测验（RPM）和图三段论（DS）。具体的在RPM任务中，矩阵的每一行组成一个图形，通过前馈模型为其获取边缘嵌入，然后进行图形汇总。由于最后一行有8个可能的答案，因此将创建8个不同的图，并将每个图与前两行连接起来，以通过ResNet模型预测IQ得分。如下图所示：

来自：https://openreview.net/pdf?id=ByxQB1BKwH

Reinforced Genetic Algorithm Learning for Optimizing Computation Graphs

请到「今天看啥」查看全文