苏涛作者萝卜兔编辑整理

论文分享 | 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

极验
极验

极验是全球顶尖的交互安全技术服务商,于2012年在武汉成立。全球首创 “行为式验证技术” ,利用生物特征与人工智能技术解决交互安全问题,为企业抵御恶意攻击防止资产损失提供一站式解决方案。

理论SGCN目标函数论文
1
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

正则化技术

当模型的复杂度增大时,训练误差会逐渐减小并趋向于0;而测试误差会先减小,达到最小值后又增大。当选择的模型复杂度过大时,过拟合现象就会发生。这样,在学习时就要防止过拟合。进行最优模型的选择,即选择复杂度适当的模型,以达到使测试误差最小的学习目的。

推荐文章
暂无评论
暂无评论~