转载：深度学习与地图网络
在过去的几年里，从图中所示的关系数据中寻找最佳归纳偏差引起了机器学习社区的极大兴趣。 依赖于图形结构的基于节点的消息收发机制产生第一代图形神经网络(GNN )，称为消息收发神经网络(MPNN )。 这些算法使用可训练的权重将各节点的特征传播到附近节点。 这些权重可基于节点之间的距离(Chebnet GNN )、连接节点特性)、注意网络的GAT )和边缘特性中的一个或两个。 考虑稀疏图时，这种方法的内存和计算复杂度与节点数呈线性关系。 因此，这些算法对大型稀疏图是可行的，并成功应用于许多下游任务。 尽管获得了这些成功和这些有趣的计算特性，但MPNN被证实还不够。 MPNN验证一阶Weisfeiler-Lehman检验无法区分的两个不同构图。 也就是说，现有的MPNN可能会在同一点嵌入两个不同的构图。 因此，从理论表达能力的角度来看，这些算法并不比1-WL测试强。 表明除了图同构问题外，MPNN不能解决图的许多其他组合问题。 已经有一些研究证明，要达到普遍近似，需要更高阶的关系。 在此背景下，提出了几种相当于3-WL测试的强大模型。 例如，PPGN模拟二阶Folklore WL测试(2-FWL )，相当于3-WL测试。 (Morris et al .2019 )提出了在1、2、3阶节点元组之间分层地使用消息收发以实现3-WL表示能力。 但是，使用这种关系会按指数增加内存使用量和计算复杂性。 因此，不可能在实践中使用通用近似模型。 本文介绍了四篇关于ICML的论文。 他们试图从多个角度解决这个问题。 内容是硬核，详细内容请参照原文。
1 .提高gnn表达能力的协同学习框架
acollectivelearningframeworktoboostgnnexpressiveness
作者：普华永道等
3359 arxiv.org/pdf/2003.12169.pdf
在这项工作中，作者提出了collective learning框架，这是一种用于图表显示学习的collective classification蒙特卡罗方法，证明该方法可以提高现有GNN的显示能力。
2. Weisfeiler和Lehman go拓扑：消息传递的简单网络
weisfeilerandlehmangotopological :消息传递simplicialnetworks
https://arxiv.org/abs/2103.03212
作者：剑桥大学Cristian Bodnar * Fabrizio Frasca*等
由于GNN等效于WL算法，因此GNN无法在图中学习任何任务。 特别是检测triangles or cliques等图表结构的能力受到限制。 作者通过局部的高阶信息交流解决了这个问题，这是一种用于simplicial complex同构测试的着色算法，是对图 WL 测试的泛化。
3 .突破消息传递限制
breakingthelimitsofmessagepassinggraphneuralnetworks
3358 hon eine.fr/Paul/publi/21.icml.gnn.pdf
为了通过保持线性复杂度来提高MPNNs的理论表达能力，一些研究者部分提出了随机化节点的特征，或者添加了唯一的标签来区分1-WL测试无法区分的两个不同构图。 这些解决方案需要大量的训练样本，而且收敛速度很慢。
本文提出用特征值的自定义非线性函数设计谱域内的图卷积，并利用所需长度的感知域来隐藏卷积支持。 通过这种方式，I )空间局部更新过程，ii )线性记忆和计算的复杂性(预处理工序中的特征分解除外)，iii )充分的光谱能力和) iv )理论上比1-WL测试更强大，正在实验中
上与 PPGN 一样优秀。实验表明，所提出的模型可以区分 1-WL 等效 MPNN 无法区分的成对图。它还能够计算 1-WL 等效 MPNN 无法计算的一些子结构。它的频谱能力能够在输出中产生各种频谱分量，而包括高阶 WL 等效模型在内的绝大多数 GNN 都没有。最后，由于稀疏矩阵乘法，除了预处理步骤中的特征分解外，它具有线性时间复杂度。4. Let's Agree to 还单身的电话：比较消息传递框架中的图卷积网络
https://arxiv.org/abs/2004.02593
Let's Agree to 还单身的电话: Comparing Graph Convolutional Networks in the Message-Passing Framework
在本文中，作者将在图上定义的神经网络转换为消息传递神经网络 (MPNN)，以研究此类模型不同类别的区分能力。作者感兴趣的是某些架构是否能够根据作为图输入给出的特征标签来区分顶点。
考虑 MPNNS 的两种变体：匿名 MPNN，其消息函数仅依赖于所涉及顶点的标签；度感知 MPNN，其中消息函数可以额外使用有关顶点度的信息。
前者涵盖了图网络的的流行形式：图神经网络（GNN）。后者涵盖了所谓的图卷积网络 (GCN)，这是 Kipf 和 Welling 最近引入的 GNN 变体。作者根据 Weisfeiler-Lehman (WL) 算法的区分能力获得了 MPNN 区分能力的下限和上限。本文的研究结果表明 (i) GCN 的区分能力受 WL 算法的限制，但它们领先一步；(ii) WL 算法不能由“普通”GCN 模拟，但在顶点特征与其邻居特征之间添加权衡参数（由 Kipf 和 Welling 自己提出）可以解决这个问题。
5. Pseudo黎曼流形用于有向图嵌入
https://arxiv.org/pdf/2106.08678.pdf
Directed Graph Embeddings in Pseudo-Riemannian Manifolds
在本文中作者证明了低纬度的cylindrical cmdggx时空和anti-de Sitter时空相比于高维的弯曲黎曼流形能够产生更好的嵌入空间，因此引入了Pseudo黎曼流形用于带环的DAG,进行链接预测.
Keypoints: 两个节点相似可能是由于特征相似也可能是结构相似，将嵌入的空间和时间分离能够解耦这两种情况；时间维度可以用于学习有向环，因此在这里作者引入一个非对称的概率学习边。
公众号：AI蜗牛车
保持谦逊、保持自律、保持进步
个人微信
备注：昵称+学校/公司+方向
如果没有备注不拉群！
拉你进AI蜗牛车交流群