论文分享 | Signed Graph Convolutional Network

当前的众多工作主要集中在，对unsigned graph使用GCN学习上。然而，随着在线社交媒体的日益流行，符号图表正在变得无处不在。现阶段针对unsigned graph的GCN无法普及到signed graph上来。作者重新设计了GCN模型，根据平衡理论，定义平衡路径，维护‘friend’表示和‘enemy’表示，一起作为顶点的表达。

Balanced Path

实现GCN从unsigned graph 到 signed graph的跨越，需要解决两个问题：

第一是signed graph中符号为负的边，如何处理。unsigned中的一些基本假设在signed graph中不成立，例如趋同性。

第二是，如何在一个模型中，整合两类边的信息。这种合并是必不可少的，因为在网络结构中，符号为正和负的边不是相互隔离的，而是以复杂的方式相互影响。作者根据平衡理论，定义了平衡路径。以此为基础提出SGCN。

平衡理论，直观的讲就是，朋友的朋友，就是我的朋友。敌人的朋友就是我的敌人。这一理论将一个signed graph的周期分类为平衡或者不平衡。平衡的周期包含偶数条负连接，反之，如果一个周期包含奇数条负链接，被认为是不平衡。

如图1中，图AB，负边个数为偶数，是平衡周期。图CD，负边个数是奇数，是不平衡周期。 

基于平衡理论，提出平衡路径的定义，一个平衡的路径是由偶数条负链接组成。同理，一个不平衡的路径是由奇数条负链接组成。基于这个定义，可以看到，如果一个长度为L的路径，是从顶点到顶点，它拥有偶数个负链接，平衡理论建议这两个顶点之间的路径为正。比如图1中的B，顶点i和j之间(通过k连接)存在两个负链接，因此平衡理论建议这两个顶点之间的路径是正的。也即是‘敌人的敌人，就是我的朋友’。

上图2，可知，如果存在一个长度L，从到的平衡路径，设，那么，所有的正路径的邻居必然包含在中。因为在平衡路径中加入一个正边，依旧得到平衡路径，只是增加了长度。同理，增加了一个负边，就会得到不平衡路径。

先定义是用户的正邻居的集合。类似地，定义是用户的负邻居的集合。我们可以递归的得到一个长度为l+1的，从节点出发的平衡路径的邻居集合和不平衡路径的邻居集合。 

SGCN

回顾unsgned GCN，聚合中心节点的一阶邻居的信息，得到中心节点的单独表示。通过叠加多层网络，在图数据结构上传播，使中心节点整合k阶邻居的信息。但是在signed 网络中，无法对中心节点的邻居做到一视同仁。与中心节点直接以正边相关连的节点集合，被视为“朋友”，直接以负边相关联的节点集合，被视为‘敌人’。同理，对中心节点的平衡邻居集合，平衡理论也将他们视为‘朋友’，不平衡邻居集合，平衡理论建议将他们视为‘敌人’。这种现象如图2中所示。

因此，我们与其维护每个节点的一个单一表示，还不如同时保存他们的‘friend’表达和‘enemy’表达。这样，对于给定的user，就成功整合了正链接和负链接的信息。

通过图3可知，第一层卷积中，的两个正边邻居的信息将被整合到“friend”表达中，聚合函数使用。同样的，的一个负边邻居信息，使用聚合函数U(1)整合到“enemy”表达中。如此，通过GCN的第二层，我们可以整合2阶邻居的信息。有一个需要注意的关键点，聚合邻居信息，需要遵守平衡理论。也就是需要依赖与我们定义的中心节点的平衡邻居集合、不平衡邻居集合。因此，分别采用聚合函数和，作用在节点的二度平衡邻居和二度不平衡邻居上，得到的二度邻居信息。

在SGCN中，信息的传递和聚合，每层将维持两个表达：一个对应user的平衡邻居集合，另一个对应不平衡邻居集合。所以，每一层的聚合函数也分别两个部分。与unsigned GCN中一样，我们使用表示节点的初始化维特征向量。那么，针对任意的节点，第一层卷积聚合如下： 

需要注意的是参数，它们分别将来自中心节点的平衡邻居和不平衡邻居，转化为中心节点的“friend”表达，“enemy”表达。来自邻居的表达与中心节点本身的特征，使用拼接的方式组合。

当模型网络深度增加时，由于定义的和会更加复杂，所以，聚合函数也会更加复杂。尤其要注意到图2中负连接交叉的情况。如下，针对任意的节点，定义时的聚合函数： 

此时，线性变换矩阵，因为需要转化的信息来自三个部分。以公式(5)为例，要得到节点在第L层的“friend”特征表达，需要聚合节点本身的在层的‘friend’特征表达，符号正边连接的度平衡邻居信息(朋友的朋友)和符号负边连接的度不平衡邻居信息(敌人的敌人)。

基于以上，在signed graph中聚合，传播的方法，提出完整的SGCN框架，分为三步：

1、对于graph中的每个节点，初始化节点的表示，并赋值给。

2、第一层卷积聚集层，计算节点的‘friend’表示，‘enemy’表示。

3、L次迭代计算，更新节点的‘friend’表示，‘ememy’表示。

作者希望节点的特征表示能够理解signed graph的嵌入空间中的用户对之间的关系。基于这个目的，设计了目标函数。分为两个部分：第一项来自模型附加的MLG分类器。希望分类节点pair之间的连接关系。也即，对于一个三元组判断连接关系S的类别。第二项的依据是平衡理论。目的是，让正边连接的user节点在特征空间中的距离比没有连接的user节点更近，而没有连接的user节点之间的距离比有负边连接的user节点之间的距离更近。整个目标函数如下：

其中,表示SGCN参数，表示MLG分类器的参数，表示节点之间连接类型的权重。和分别代表采样有正/负边连接的节点对，并且对于节点进一步采样跟没有连接的节点。目标函数最后一项为正则化项。

实验

作者在真实数据集Bitcoin-Alpha 1 , Bitcoin-OTC 2 , Slashdot 3 and Epinions上设计了节点之间边的类型预测实验，并且将当前state-of-the-art的baseline方法做了对比，研究了单层SGCN或者不利用平衡理论的SGCN框架变体。验证了两个问题，SGCN能够高效的学习到节点的潜在表达；基于平衡理论，长路径上的聚合函数能够提升节点表达的效果。

SGCN-1只使用单层网络，并且不使用平衡理论和作者定义的平衡路径，SCN-1+ 也不使用平衡理论，但是包含两层网络。SGCN-2为作者提出的SGCN框架。比较各个baseline模型和SGCN-1，SGCN-1+，SGCN-2的AUC和F1值，发现SGCN框架和其变体普遍具有比其他模型更好的效果。而且SGCN-1+的效果优于SGCN-1，SGCN-2又优于SGCN-1+，可以表明平衡理论和定义的平衡路径提升了表达效果。

参考论文：
https://arxiv.org/abs/1808.06354