图机器学习的新趋势

方案所取代。关于图神经网络还有很多需要理解的地方，但是关于GNNs如何工作有相当多的重要结果。

我将从我最喜欢的一篇文章开始：What graph neural networks cannot learn: depth vs width。这篇论文在技术的简单性、很高的实际影响和深远的理论见解之间取得了惊人的平衡。

它表明节点嵌入的维度(网络的宽度，w)乘以层数(网络的深度，d)应该与图的大小n成比例，即dw = O(n)，如果我们希望GNN能够计算出流行的图问题的解决方案(如周期检测、直径估计、顶点覆盖等)。

因此，由于层的数量(在许多实现中约为2-5层)和嵌入的维度(约为100-1000层)与图的大小相比不够大，许多当前的GNN实现无法实现这一条件。另一方面，在目前的环境下，太大的网络计算存储代价过高，这就提出了一个问题：我们应该如何设计“高效”的GNN，这是我们将来需要解决的问题。这篇论文还从80年代的分布式计算模型中得到了启发，证明了GNNs本质上也做了同样的事情。里面有更多的结果，所以我建议你去看看。

类似地，另外两篇论文Oono & Suzuki和Barcelo等人也研究了GNNs的威力。第一个是Graph Neural Networks loss expression Power for Node Classification，表明：

在一定的权值条件下，当层数增加时，GCNs除了节点度和连通分量(由拉普拉斯频谱确定)外，什么也学不到。

这个结果是一个众所周知的性质的推广，即马尔科夫过程收敛于唯一的均衡，其中收敛率是由转移矩阵的特征值决定的。

在第二篇论文The Logical Expressiveness of Graph Neural Networks中，作者展示了GNNs与它们所能捕获的节点分类器类型之间的联系。我们已经知道，一些GNN具有与WL同构检验同样强大的能力，即当且仅当两个节点被GNNs分类相同时，它们被WL着色相同。但是GNN可以捕获其他分类函数吗?例如，假设一个布尔函数，当且仅当一个图有一个孤立的顶点时，才将true赋值给所有节点。GNNs能够捕获这种逻辑吗?从直觉上说不是，因为GNN是一种消息传递机制，如果图的一个部分与另一个部分(两个连接的组件)之间没有链接，那么这两个部分之间就不会传递消息。因此，一个推荐的简单修复方法是在邻居聚合之后添加一个读出操作，以便在更新所有特征时每个节点都拥有图中所有其他节点的信息。

其他理论方面的工作包括Hou等人对GNN图形信息的使用进行度量，以

（编辑：怀化站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!