关键词:
符号网络
表示学习
链接预测
社区发现
图神经网络
摘要:
符号网络是大数据时代的一种数据表现形式,由节点、节点间正负链接组成。符号网络中的任务在现实生活中有非常广泛的应用,如链接预测、社区发现、节点分类等。但符号网络的节点和链接需要高维向量表示,导致模型计算复杂的问题。表示学习是一种非常有效的学习节点嵌入方法,通过保留网络中拓扑结构、顶点内容和其它辅助信息,将网络顶点嵌入到低维向量空间中。所以用表示学习方法可以将符号网络任务中所需的信息提取出来,用低维向量有效表示节点信息。本文主要分析符号网络中两个重要任务,即链接预测和社区发现,探索表示学习方法在这两个任务中的技术和应用。上述工作所面临的主要挑战包括:1)面向链接预测:如何将符号网络中的社区结构和节点度分布信息融入到节点表示中,丰富节点表示信息,从而提高模型链接预测能力?2)面向社区发现:如何学习节点与社区的向量表示,探索社区与社区之间、社区与节点之间的区别与联系,从而将节点分配到相应社区?基于以上问题,本文提出两种新型符号网络表示学习算法:(1)提出基于结构增强的符号网络链接预测方法—Structure-enhanced Graph Representation Learning(SGRL)。目前的符号网络链接预测方法只关注于用平衡理论构造图神经网络并进行消息传递,从而得到节点的向量表示。这种方法只刻画了符号网络的拓扑结构以及某些邻居节点的信息。然而,一个复杂的符号网络具有很多结构信息,每种结构信息都会影响到节点的信息表示从而影响符号网络链接预测任务。针对该问题,本文提出SGRL方法,该方法探索符号网络中的结构信息,如:社区结构以及节点的度分布信息,从而增强节点的信息表示能力,提高模型链接预测的能力。首先,模型利用伯努利分布和高斯分布刻画符号网络中的社区结构,伯努利分布描述节点是否属于某个社区,高斯分布描述节点属于某个社区的强度。其次,模型引入迪利克雷分布刻画节点的度分布信息,迪利克雷分布属于幂律分布,因此,可以很好的描述节点的度分布情况。最后,从迪利克雷分布中采样得到的节点表示用于符号网络中的链接预测任务。实验结果表明,节点表示中很好的融入了社区结构和节点的度分布信息,提高模型链接预测的精准度。(2)提出基于社区与节点关系分析的符号网络社区发现算法—Representation Learning for Community-Node Relationship(RLCN)。目前研究者对符号网络社区发现的研究甚少,这些研究主要基于谱方法,利用特征根对社区进行探索。但是谱方法在处理大型图数据时计算复杂度高,而用深度表示学习方法,尤其是图神经网络表示学习方法不仅可以降低计算复杂度,而且可以提取更丰富的信息表示,更有利于复杂网络社区发现任务。针对该问题,本文提出一种基于图神经网络的方法,该方法通过模拟kmeans过程优化节点表示,得到社区与社区之间、社区与节点之间的联系与区别。首先,随机初始化社区的表示向量,利用基于符号网络的图神经网络模型得到节点表示,从而根据社区表示向量与节点表示向量的相似程度确定节点归属社区的概率,即分配矩阵。然后,利用针对符号网络社区结构的性质构造的损失函数对图神经网络中的参数进行优化,更新节点表示,从而得到最终的分配矩阵,完成社区发现任务。实验结果表明,模型找到了社区与社区之间、社区与节点之间的联系与区别,从而提高模型社区发现的能力。