张春成

V2

2022/03/05阅读:60主题:默认主题

图神经网络的计算和收敛

图神经网络的计算和收敛

图神经网络是考察节点关系的模式识别方法。 多用于解决复杂系统中, 针对节点之间的关系进行运算的模式识别问题。

本文是对它的运算过程进行模拟, 并且尝试通过简单的例子, 说明这类网络的收敛性。

本样例的代码可见我的开源代码[1]


简单图

图神经网络首先是一个图,

其中, 代表网络节点, 代表连接关系。

Graph Network 1
Graph Network 1

上图是一个全连通的连接图, 其中,节点的位置是随机生成的, 节点的颜色代表它的强度。

节点之间的连接关系如线段所示,

是由Voronoi算法计算得到的

对所有相邻的节点进行连接, 保证形成的每个每三角形内部都不包含任何节点。

这个算法的优点是简单易行, 但缺点是只保证了图中每个节点的连通性

从任意的节点出发, 都能在有限步之内达到另一个节点。

但除此之外,它没有任何意义, 既不能保证通路是唯一的, 也不能保证存在一条不重复的路径, 可以遍历全部节点。 所以,这只是一个“粗制烂造”的小破图。

图神经网络

而图神经网络的计算过程 就是在给定网络结构的情况下, 对边的权重进行学习。

各个边一旦有了权重, 节点的数值就可以“传递”给与之相邻的节点, 从而完成网络计算。

其中, 是节点 的邻居节点, 是加权系数。

在这样的更新规则下, 整个网络可以进行迭代, 如动画所示

【这一段棒到不行的视频】

随机收敛

而进一步分析可以发现, 迭代一定次数之后, 整个网络的节点数值会趋于稳定。

可能的状态之一

Graph Network 2
Graph Network 2

可能的状态之二

Graph Network 3
Graph Network 3

在达到这样的状态后, 各个节点的数值虽然继续更新, 但由于达到平衡, 因此数值不会发生变化。 并且实验表明, 稳定状态受到系统初始状态的影响

这种影响是图神经网络对输入进行模式识别的关键理论基础。

而图神经网络学习的目的是优化网络结构 , 使之满足

其中, 代表模式识别的损失函数。

至于如何把图的结构与损失函数联系起来, 就完全是另外的故事了。

参考资料

[1]

我的开源代码: https://observablehq.com/@listenzcc/graph-network

分类:

人工智能

标签:

机器学习

作者介绍

张春成
V2