如何在图上进行卷积网络的深度学习(一)

作者:Tobias Skovgaard Jepsen

编译:ronghuaiyang


导读

这是第一部分,图卷积网络的高级介绍。

图的机器学习是一项非常困难的任务,因为图的结构非常复杂,但同时也提供了丰富的信息。本文是关于如何利用图卷积网络(GCNs)对图进行深度学习的系列文章中的第一篇。GCNs是一种功能强大的神经网络,旨在直接处理图并利用图的结构信息。

在本文中,我将介绍GCNs,并使用图解的方式说明信息如何通过GCN的隐藏层进行传播。我们将看到GCNs是如何聚合来自前一层的信息,以及这种机制如何生成图中节点的有用特征表示。

什么是图卷积网络?

GCNs是一种非常强大的图机器学习神经网络结构。事实上,它们非常强大,甚至一个随机初始化的2层GCN都可以生成网络中节点的有用特征表示。下图展示了由这样一个GCN生成的网络中每个节点的二维表示。请注意,即使没有任何训练,网络中节点的相对接近性也保留在二维表示中。

如何在图上进行卷积网络的深度学习(一)

更正式地说,graph convolutional network (GCN)是一个对图进行操作的神经网络。给定一个图G = (V, E), GCN的输入包括:

  • 一个N×F⁰的输入特征矩阵X,其中N是节点的数量,F⁰是每个节点输入特征的数量
  • 图结构的N×N矩阵表示,如G.[1]的邻接矩阵A

GCN中的一个隐藏层可以写成H^i^ = f(H^i-1^A)),其中,H⁰=X, f是前向传播。每一层的H^i^对应于一个N×F^i^的特征矩阵,其中每一是一个特性的表示一个节点的特征。在每一层,使用传播规则f聚合这些特征,形成下一层的特征。这样,每个连续层的特征都变得越来越抽象。在这个框架中,GCN的变体只在传播规则f的选择上有所不同。

一个简单的传播规则

最简单的传播规则之一是:

如何在图上进行卷积网络的深度学习(一)

其中,W^i^是第i层的权值矩阵,σ是非线性激活函数,比如ReLU函数。权值矩阵的维度为F^i^×F^i+1^,换句话说,权值矩阵的第二个维度的大小决定了下一层的特征的维度。如果你熟悉卷积神经网络,这个操作类似于滤波操作,因为权值在图中的各个节点上是共享的。

简化

我们用最简单的方法检查一下传播规则。令:

  • i = 1的时候,f 是关于输入特征矩阵的函数
  • σ 是恒等变换函数
  • 选择这样的权值,使得,AHW⁰ =AXW⁰ = AX.

换句话说, f(X,A

) =AX,这个传播法则也许太简单了一点,不过我们后面会加点东西。另外注意,AX现在相当于多层感知器的输入层。

一个简单的图的例子

作为一个简单的例子,我们使用下面的图:

如何在图上进行卷积网络的深度学习(一)

下面是 numpy的邻接矩阵的表示:

A = np.matrix([ 
[0, 1, 0, 0],
[0, 0, 1, 1],
[0, 1, 0, 0],
[1, 0, 1, 0]],
dtype=float
)

下面,我们需要特征!我们为每个节点生成了2个整数特征,这样后面手动计算会很方便。

In [3]: X = np.matrix([
[i, -i]
for i in range(A.shape[0])
], dtype=float)

XOut[3]: matrix([
[ 0., 0.],
[ 1., -1.],
[ 2., -2.],
[ 3., -3.]
])

应用传播法则

好了,我们现在有了一个图,邻接矩阵 A还有一组特征 X,我们看看应用传播法则的时候发生了什么:

In [6]: A * X
Out[6]: matrix([
\t\t\t\t\t\t\t\t\t\t\t\t\t\t[ 1., -1.],
[ 5., -5.],
[ 1., -1.],
[ 2., -2.]]

发生了什么?每个节点(每一行)的表示现在是其邻居特征的总和!换句话说,图卷积层将每个节点表示为其邻域的集合。我鼓励你自己检查一下计算结果。注意,在本例中,如果存在一条从v到n的边,则节点n是节点v的邻居。

问题浮出水面!

你可能已经发现问题了:

  • 节点的聚合表示不包括它自己的特征!表示是邻居节点特征的集合,因此只有具有自循环的节点才会在集合中包含自己的特征
  • 度大的节点的特征表示值较大,度小的节点的特征表示值较小。这可能导致梯度消失或爆炸,对于随机梯度下降算法也存在问题,这些算法通常用于训练此类网络,并且对每个输入特征的尺度(或值范围)敏感。

下面,我将分别讨论这些问题。

加入自循环

要解决第一个问题,只需向每个节点添加一个自循环。实际上,这是通过在应用传播规则之前将单位矩阵I添加到邻接矩阵A来实现的。

In [4]: I = np.matrix(np.eye(A.shape[0])) 
IOut[4]: matrix([
\t\t\t\t\t\t[1., 0., 0., 0.],
\t\t\t\t\t\t[0., 1., 0., 0.],
\t\t\t\t\t\t[0., 0., 1., 0.],
\t\t\t\t\t\t[0., 0., 0., 1.]

\t\t\t\t\t\t\t])

In [8]: A_hat = A + I
A_hat * X
Out[8]: matrix([
\t\t\t\t\t\t\t[ 1., -1.],
\t\t\t\t\t\t\t[ 6., -6.],
\t\t\t\t\t\t\t[ 3., -3.],
\t\t\t\t\t\t\t[ 5., -5.]
\t\t\t\t\t\t])

由于节点现在是其自身的邻居,所以在聚合其邻居的特征时将包含该节点自己的特征!

特征表示的归一化

特征表示可以通过节点的度来归一化,将邻接矩阵 A与度矩阵 D的逆矩阵相乘进行转换。因此,我们的简化传播规则是这样的:

如何在图上进行卷积网络的深度学习(一)

我们看看发生了什么,我们先计算度矩阵。

In [9]: D = np.array(np.sum(A, axis=0))[0] 
\t\t\t\t\tD = np.matrix(np.diag(D))
\t\t\t\t\tD

Out[9]: matrix([
\t\t\t\t\t\t\t[1., 0., 0., 0.],
\t\t\t\t\t\t\t[0., 2., 0., 0.],
\t\t\t\t\t\t\t[0., 0., 2., 0.],
\t\t\t\t\t\t\t[0., 0., 0., 1.]
\t\t\t\t\t\t\t])

在应用规则之前,让我们看看在邻接矩阵转换之后会发生什么。

之前

A = np.matrix([ 
\t\t\t\t\t\t[0, 1, 0, 0],
\t\t\t\t\t\t[0, 0, 1, 1],
\t\t\t\t\t\t[0, 1, 0, 0],
\t\t\t\t\t\t[1, 0, 1, 0]
\t\t\t\t\t\t\t],
dtype=float)

之后

In [10]: D**-1 * A
Out[10]: matrix([
\t\t\t\t\t\t\t[0. , 1. , 0. , 0. ],
\t\t\t\t\t\t\t[0. , 0. , 0.5, 0.5],
\t\t\t\t\t\t\t[0. , 0.5, 0. , 0. ],
\t\t\t\t\t\t\t[0.5, 0. , 0.5, 0. ]
\t\t\t\t\t\t\t])

我们发现邻接矩阵中的每一行的权值都除以了对于行的节点的度。我们在变换后的邻接矩阵上应用传播法则

In [11]: D**-1 * A * X
Out[11]: matrix([
\t\t\t\t\t\t\t\t[ 1. , -1. ],
\t\t\t\t\t\t\t\t[ 2.5, -2.5],
\t\t\t\t\t\t\t\t[ 0.5, -0.5],
\t\t\t\t\t\t\t\t[ 2. , -2. ]
\t\t\t\t\t\t\t\t])

得到与相邻节点特征均值对应的节点表示。这是因为(转换后的)邻接矩阵中的权值对应于相邻节点特征加权和中的权值。我再次鼓励你亲自验证这一观察结果。

合在一起

现在我们结合了自循环和归一化技巧。此外,我们还将重新介绍先前为简化讨论而放弃的权值和激活函数。

把权值加回来

首先要做的是使用权重。注意这里 D_hat是 A_hat=A+I的度矩阵,即加了自循环的A的度矩阵。

In [45]: W = np.matrix([ 
\t\t\t\t\t\t\t\t\t\t\t[1, -1],
\t\t\t\t\t\t\t\t\t\t\t[-1, 1]
\t\t\t\t\t\t\t\t\t\t])
\t\t\t\t\t\tD_hat**-1 * A_hat * X * W

Out[45]: matrix([
\t\t\t\t\t\t\t\t\t[ 1., -1.],
\t\t\t\t\t\t\t\t\t[ 4., -4.],
\t\t\t\t\t\t\t\t\t[ 2., -2.],
\t\t\t\t\t\t\t\t\t[ 5., -5.]
\t\t\t\t\t\t\t\t])

如果我们想减小输出特征表示的维数,我们可以减小权值矩阵 W的大小:

In [46]: W = np.matrix([ 
\t\t\t\t\t\t\t\t\t\t\t\t\t\t[1],
\t\t\t\t\t\t\t\t\t\t\t\t\t\t[-1]
\t\t\t\t\t\t\t\t\t\t\t\t])
\t\t\t\t\t\tD_hat**-1 * A_hat * X * W

Out[46]: matrix([[1.],
\t\t\t\t\t[4.],
\t\t\t\t\t[2.],
\t\t\t\t\t[5.]])

添加激活函数

我们选择保留特征表示的维数,并应用ReLU激活函数。

In [51]: W = np.matrix([ 
\t\t\t\t\t\t\t\t\t\t\t\t\t\t[1, -1],
\t\t\t\t\t\t\t\t\t\t\t\t\t\t[-1, 1]
\t\t\t\t\t\t\t\t\t\t\t\t])
\t\t\t\t\t\trelu(D_hat**-1 * A_hat * X * W)

Out[51]: matrix([[1., 0.],
\t\t\t\t\t[4., 0.],
\t\t\t\t\t[2., 0.],
\t\t\t\t\t[5., 0.]])

看!一个完整的带有邻接矩阵,输入特征,权重和激活函数的隐藏层!

回到现实中

最后,我们可以把一个图卷积网络应用到一个真实的图上。我将向你展示如何生成我们在本文前面看到的特征表示。

Zachary的空手道俱乐部

Zachary的空手道俱乐部是一个常用的社交网络,每个节点代表一个空手道俱乐部的成员,并将他们之间的关系用边来表示。在Zachary学习空手道的时候,管理员和教练发生了冲突,导致空手道俱乐部一分为二。下图显示了网络的图表示,节点的标记表示了这个人属于俱乐部的哪个部分。管理员和教练分别用“A”和“I”标记。

如何在图上进行卷积网络的深度学习(一)

构建GCN

现在我们来构建这个图卷积网络。实际上,我们不会训练网络,而只是随机初始化它来生成我们在本文开头看到的特征表示。我们将使用 networkx,它有一个现成的俱乐部的图形表示,并很容易计算 A_hat和 D_hat矩阵。

from networkx import karate_club_graph, to_numpy_matrixz
kc = karate_club_graph()
order = sorted(list(zkc.nodes()))
A = to_numpy_matrix(zkc, nodelist=order)
I = np.eye(zkc.number_of_nodes())
A_hat = A + I
D_hat = np.array(np.sum(A_hat, axis=0))[0]
D_hat = np.matrix(np.diag(D_hat))

接下来,我们随机初始化权值。

W_1 = np.random.normal( 
\t\t\t\t\t\t\t\t\t\t\t\t\tloc=0,
scale=1, size=(zkc.number_of_nodes(), 4))W_2 = np.random.normal( loc=0, size=(W_1.shape[1], 2))

堆叠GCN层。这里我们只使用单位矩阵作为特征表示,即每个节点都表示为一个类别变量的独热编码。

def gcn_layer(A_hat, D_hat, X, W): 
\t\t\treturn relu(D_hat**-1 * A_hat * X * W)
H_1 = gcn_layer(A_hat, D_hat, I, W_1)
H_2 = gcn_layer(A_hat, D_hat, H_1, W_2)
output = H_2

我们提取特征表示。

feature_representations = { 
\t\t\tnode: np.array(output)[node]

\t\t\tfor node in zkc.nodes()}

看!在Zachary的空手道俱乐部中,特征表示可以很好的将社区分开。我们还没开始训练呢!

如何在图上进行卷积网络的深度学习(一)

应该注意到,在这个示例中,由于ReLU函数的作用,随机初始化的权重很可能在x轴或y轴上给出0个值,因此需要多做几次随机初始化才能生成上面的图。

结论

在这篇文章中,我对图卷积网络做了一个高层次的介绍,并说明了GCN中每一层节点的特征表示是如何基于其邻域来进行聚合的。我们看到了如何使用numpy来构建这些网络,以及它们是多么强大:即使是随机初始化的GCNs也可以在Zachary的空手道俱乐部中分隔社区。

英文原文:https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780

如何在图上进行卷积网络的深度学习(一)


分享到:


相關文章: