时序图节点嵌入策略的研究

相较于传统的图数据分析方法,图嵌入算法是一种面向图节点的新型图数据分析策略.其旨在通过将图节点向量化表达,进而在节点向量基础上利用神经网络相关技术更有效的进行图数据分析或挖掘工作,如在节点分类、链接预测及交通流预测等经典问题上取得效果显著.虽然研究者们在图嵌入方面已取得了诸多成果,但是面向时序图的节点嵌入问题却未被充分重视,本文便是在先前研究工作的基础上,结合信息在时序图中的传播特性,提出了一种对时序图节点进行自适应嵌入表达的方法ATGEB （Adaptive Temporal Graph Embedding）.首先,为了解决不同类型时序图节点活跃程度不同的问题,通过设计一种自适应方式对其活跃时刻进行聚类.而后,在此基础上设计一种游走模型用以保存节点对之间的时间关系,并将节点游走序列保存在一种双向多叉树上进而可以更快速的得到节点时间相关的游走序列.最后,在基于节点游走特性和图拓扑结构的基础上,对节点向量进行重要节点采样,以便在尽可能短的时间内训练出满足需求的网络模型.通过充分的实验证明,本文面向时序图的嵌入策略相较于现流行的嵌入方法,在时序图时序中节点间时序可达性检测以及节点分类等问题上得出了更好的实验效果.     

基于社团多特征融合嵌入表示的时序链路预测方法

时序动态网络在静态网络基础上综合了时间属性的概念,包含了网络结构的复杂性、动态性等内涵,是研究复杂网络链路预测问题的较优思维对象,因在现实世界中具有较高应用价值而备受关注。目前大部分传统方法研究对象仍局限于静态网络,存在对网络时域演化信息利用不充分、时间复杂度较高等问题。结合社会学理论,提出一种基于社团多特征融合嵌入表示的时序链路预测方法,该方法的核心思想是通过分析网络动态演化特性,在社团范围内学习节点的嵌入表示向量,融合多特征以衡量节点间连边的生成概率。利用网络集体影响力的方法对节点和连边的权值进行计算,基于集体影响的连边权值进行社团划分,将网络划分为若干个社团子图,得到基于集体影响的相似性指标。在社团范围内,利用有偏的随机游走,结合梯度优化的Skip-gram方法获取所有节点的嵌入表示向量,得到基于社团范围游走的相似性指标。融合节点的集体影响、社团范围节点的多个中心性特征和学习到的节点表示向量,得到多特征融合的相似性指标,3 种新指标都可以用于衡量节点之间形成连边的概率。对比基于移动平均、嵌入表示、图神经网络等经典时序链路预测方法,在 6 个真实数据集上的实验结果表明,所提基于社团多特征融合的方法在 AUC评价标准下取得更优的预测性能。     

基于重启随机游走的图自编码器

针对现有的图自编码器无法捕捉图中节点之间的上下文信息的问题,提出基于重启随机游走的图自编码器.首先,构造两层图卷积网络编码图的拓扑结构和特征,同时进行重启随机游走捕捉节点之间的上下文信息;其次,为了聚合重启随机游走和图卷积网络获得的表示,设计自适应学习策略,根据两种表示的重要性自适应地分配权重.为了证明该方法的有效性,将图最终的表示应用于节点聚类和链路预测任务.实验结果表明,与基线方法相比,提出的方法实现了更先进的性能.     

基于时间图注意力的交通流量预测模型

交通状况预测是智能交通系统的一个重要组成部分,而车流量是交通状况最直接的体现,因而对交通流量进行预测具有重要的应用价值。一方面,城市中的道路本身带有空间拓扑性质,另一方面车流量随时间动态变化。因此交通流量预测问题的关键在于对数据中存在的时间和空间依赖进行建模。针对这一特性,使用神经网络模型和注意力机制来探索交通流量数据中的时空依赖关系,提出基于时间图注意力的交通流量预测模型。空间依赖方面,使用图卷积网络与注意力结合的学习算法对不同影响程度节点分配不同的权重,加入节点自适应学习,有效提取空间特征;时间依赖方面,使用时序卷积网络对时间特征进行提取,通过扩张卷积扩大感受域从而捕获较长时间序列数据的特征。由图注意力网络和时间卷积网络构成一个时空网络层,最终连接到输出层输出预测结果。该模型使用图卷积神经网络和注意力机制结合的方式提取空间特征,充分考虑了道路间的空间关系,利用时序卷积网络捕获时间特征。在两个真实的数据集上进行实验后发现,在未来15 min、30 min、60 min的时间段内该模型都有良好表现,结果优于现有基准模型。     

基于双视角的耦合网络表示学习算法

传统网络表示学习算法大多依赖于节点视角下的随机游走获取网络局部采样序列,再通过最大化相邻节点的共现概率将网络中的节点表示成低维向量.本文在真实网络上的经验分析表明,对节点和边两种视角分别进行随机游走会产生具有不同节点分布的采样序列,进而得到不同的社区划分.为此,本文提出了一种基于双视角的耦合表示学习算法DPBCNE.该方法基于边视角进行随机游走以获得不同于节点视角的采样结果,再融合基于节点视角下的节点采样序列进行耦合训练,以学习节点和边的表示.实验结果表明,相较于现有的网络表示学习算法,DPBCNE能更好地保留网络拓扑结构信息,并在下游分类和预测任务中获得更好的效果.     

基于随机化矩阵分解的网络嵌入方法

随着互联网的普及,越来越多的问题以社交网络这样的网络形式出现.网络通常用图数据表示,由于图数据处理的挑战性,如何从图中学习到重要的信息是当前被广泛关注的问题.网络嵌入就是通过分析图数据得到反映网络结构的特征向量,利用它们进而实现各种数据挖掘任务,例如边预测、节点分类、网络重构、标签推荐和异常检测.最近,基于矩阵分解的网络嵌入方法NetMF被提出,它在理论上统一了多种网络嵌入方法,并且在处理实际数据时表现出很好的效果.然而,在处理大规模网络时,NetMF需要极大的时间和空间开销.本文使用快速随机化特征值分解和单遍历奇异值分解技术对NetMF进行改进,提出一种高效率、且内存用量小的矩阵分解网络嵌入算法eNetMF.首先,我们提出了适合于对称稀疏矩阵的随机化特征值分解算法freigs,它在处理实际的归一化网络矩阵时比传统的截断特征值分解算法快近10倍,且几乎不损失准确度.其次,我们提出使用单遍历奇异值分解处理NetMF方法中高次近似矩阵从而避免稠密矩阵存储的技术,它大大减少了网络嵌入所需的内存用量.最后,我们提出一种简洁的、且保证分解结果对称的随机化单遍历奇异值分解算法,将它与上述技术结合得到eNetMF算法.基于5个实际的网络数据集,我们评估了eNetMF学习到的网络低维表示在多标签节点分类和边预测上的有效性.实验结果表明,使用eNetMF替代NetMF后在后续得到的多标签分类性能指标上几乎没有损失,但在处理大规模数据时有超过40倍的加速与内存用量节省.在一台32核的机器上,eNetMF仅需约1.3 h即可对含一百多万节点的YouTube数据学习到网络嵌入,内存用量仅为120GB,并得到较高质量的分类结果.此外,最近被提出的网络嵌入算法NetSMF由于图稀疏化过程的内存需求太大,无法在256 GB内存的机器上处理两个较大的网络数据,而ProNE算法则在多标签分类的结果上表现不稳定,得到的Macro-F1值都比较差.因此,eNetMF算法在结果质量上明显优于NetSMF和ProNE算法.在边预测任务上,eNetMF算法也表现出与其它方法差不多甚至更好的性能.     

基于图嵌入与支持向量机的社交网络节点分类方法

针对无属性社交网络的节点分类问题,提出了一种基于图嵌入与支持向量机,利用社交网络中节点之间关系特征,对节点进行分类的方法.首先,通过DeepWalk、LINE等多种图嵌入模型挖掘节点隐含关系特征的同时,将高维的社交网络数据转换为低维embedding向量.其次,提取节点度、聚集系数、PageRank值等特征信息,组合构成节点的特征向量.然后,利用支持向量机构建节点分类预测模型对节点进行分类预测.最后,在三个公开的社交网络数据集上实验,与对比方法相比,提出的方法在社交网络节点分类任务中能取得更好的分类效果.     

基于改进图注意机制的网络嵌入方法研究及应用

网络已被广泛用作抽象现实世界系统以及组织实体之间关系的数据结构;网络嵌入模型是将网络中的节点映射为连续向量空间表示的强大工具;基于图卷积（Graph convolutional neural, GCN）的网络嵌入方法因受其模型迭代过程参数随机优化和聚合函数的影响,容易造成原始节点特征信息丢失的问题;为有效提升网络嵌入效果,针对于图神经网络模型在网络嵌入中节点表征学习的局限性,提出了一种基于二阶邻域基数保留策略的图注意力网络SNCR-GAT（Second-order Neighborhood Cardinality Retention strategy Graph attention network）,通过聚合二阶邻域特征基数的方式,解决网络节点潜在特征学习过程中重要信息保留问题;通过在节点分类和可视化两个网络嵌入应用任务上进行实验,结果表明,SNCR-GAT模型在网络嵌入上的性能表现相比较基准方法更具优越性。     

基于节点-属性二部图的网络表示学习模型

在图结构数据上开展推理计算是一项重大的任务,该任务的主要挑战是如何表示图结构知识使机器可以快速理解并利用图数据。对比现有表示学习模型发现,基于随机游走方法的表示学习模型容易忽略属性对节点关联关系的特殊作用,因此提出一种基于节点邻接关系与属性关联关系的混合随机游走方法。首先通过邻接节点间的共同属性分布计算属性权重,并获取节点到每个属性的采样概率;然后分别从邻接节点与含有共有属性的非邻接节点中提取网络信息;最后构建基于节点-属性二部图的网络表示学习模型,并通过上述采样序列学习得到节点向量表达。在Flickr、BlogCatalog、Cora公开数据集上,用所提模型得到的节点向量表达进行节点分类的Micro-F1平均准确率为89.38%,比GraphRNA（Graph Recurrent Networks with Attributed random walks）高出了2.02个百分点,比经典工作DeepWalk高出了21.12个百分点;同时,对比不同随机游走方法发现,提高对节点关联有促进作用的属性的采样概率可以增加采样序列所含信息。     

基于社区优化的深度网络嵌入方法

随着现代网络通信和社会媒体等技术的飞速发展,网络化的大数据由于缺少高效可用的节点表示而难以应用。将高维稀疏难于应用的网络数据转化为低维、紧凑、易于应用的节点表示的网络嵌入方法受到广泛关注。然而已有网络嵌入方法得到节点低维特征向量后,再将其作为其他应用（节点分类、社区发现、链接预测、可视化等）的输入来作进一步分析,没有针对具体应用构建模型,难以取得满意的结果。针对网络社区发现这一具体应用,提出结合社区结构优化进行节点低维特征表示的深度自编码聚类模型CADNE。首先基于深度自编码模型,通过保持网络局部及全局链接的拓扑特性来学习节点的低维表示,然后利用网络聚类结构对节点低维表示进一步优化。该方法同时学习节点的低维表示和节点所属社区的指示向量,使节点的低维表示不仅能保持原始网络结构中的拓扑结构特性,而且能保持节点的聚类特性。与已有的经典网络嵌入方法进行对比,结果显示CADNE模型在Citeseer和Cora上取得最优聚类结果,在20NewsGroup上准确率提升最高达0.525;分类性能在Blogcatalog、Citeseer数据集上取得最好结果,在Blogcatalog上训练比例20%时比基线方法提升最高达0.512;并且CADNE模型在可视化对比中能够得到类边界更加清晰的节点低维表示,验证了所提方法具有较好的节点低维表示能力。     

基于特征和图结构信息增强的多教师学习图神经网络

近年来,图神经网络对图数据强大的表征能力和建模能力使其在诸多领域广泛应用并取得了重大突破。然而,现有模型往往倾向于对图卷积聚合策略和网络结构进行优化,缺乏了对图数据自身先验知识的探索。针对上述问题,通过知识蒸馏的方法,设计了一种基于特征信息和结构信息增强的多教师学习图神经网络,打破了现有模型对于数据先验知识提取的局限性。针对图数据背后所蕴涵的丰富特征与结构信息,分别设计了节点特征和边的数据增强方式。在此基础上,将原始数据和增强后的数据通过多教师学习模块进行知识嵌入,使得学生模型学习到更多关于数据的先验知识。在Cora、Citeseer和PubMed数据集上,节点分类准确率分别提升了1%、1.3%、1.1%。实验结果表明,提出的信息增强的多教师学习模型能够有效地捕获先验知识。     

基于特征和结构信息增强的图神经网络集成学习框架

近年来,图神经网络由于其丰富的表征和推理能力受到广泛的关注,然而,目前的研究聚焦于卷积策略和网络结构的调整以获得更高的性能,不可避免地面临单一模型局限性的约束。受到集成学习思想的启发,面向图神经网络创新性地提出一套集成学习框架(EL-GNN)。不同于常规的文本和图像数据,图数据除了特征信息外还包括了丰富的拓扑结构信息。因此,EL-GNN不仅将不同基分类器的预测结果进行融合,还在集成阶段额外补充了结构信息。此外,基于特征相似或结构邻居节点通常具有相似标签的先验假设,借助特征图重构,进一步优化集成策略,充分平衡了节点的特征和结构信息。大量实验表明,提出的集成策略取得了良好的成效,并EL-GNN在节点分类任务上显著优于现有模型。     

基于节点相似度的无监督属性图嵌入模型

属性图嵌入旨在将属性图中的节点表示为低维向量,并同时保留节点的拓扑信息和属性信息.属性图嵌入已经有一系列相关工作,然而它们大多数提出的是有监督或半监督的算法.在实际应用中,需要标记的节点数量多,导致这些属性图嵌入算法的难度大,且需要消耗巨大的人力物力.针对上述问题以无监督的视角重新分析,提出了一种无监督的属性图嵌入算法...     

基于域内特征间相似性的点击率预估优化

基于深度学习的点击率预估模型多数通过建模各个域的特征之间的交互关系提升预估准确率。特征嵌入向量对模型效果具有重要影响,而现有的CTR模型中不同特征的嵌入向量学习过程相互独立,且由于特征长尾分布导致大部分低频特征不能学习到较好的向量表示,严重影响模型的预测效果。基于域内特征间存在隐含的相似性,提出两种分别基于特征间共现概率和游走概率的相似度定义和对应的相似性图构建方法,并给出结合剪枝策略的广度优先遍历算法实现相似特征的高效计算。在此基础上,基于域内特征相似性图,设计一种嵌入生成器,对于低频特征,在域内特征相似性图上通过图神经网络聚合与其相似的特征信息,生成新的特征嵌入,作为预处理过程对特征嵌入向量进行数据增强,提升嵌入向量的表示学习质量。在公开数据集Criteo、Avazu上的实验结果表明,该方法明显提升点击率预估模型的预测准确率,其中对代表性点击率预估模型xDeepFM和AutoInt,AUC指标分别提升了0.007和0.008,LogLoss则下降了0.009和0.006,证明了嵌入生成模型的有效性。     

一种基于节点嵌入表示学习的社区搜索算法

针对已有社区搜索算法采用高维稀疏向量表示节点时间复杂度高的问题,提出一种基于节点嵌入表示学习的社区搜索算法CSNERL.节点嵌入技术能够直接从网络结构中学习节点的低维实值向量表示,为社区搜索提供了新思路.首先,针对已有节点嵌入算法存在较高概率在最亲近邻居间来回游走的问题,提出基于最亲近邻居但不立即回访随机游走的节点嵌入模型NECRWNR,采用NECRWNR模型学习节点的特征向量表示;然后,采用社区内所有节点的向量均值作为社区的向量表示,通过选择与当前社区距离最近的节点加入社区的方法实现一种新的社区搜索算法.在真实网络和模拟网络数据集上分别与相关的社区搜索算法进行实验对比,结果表明所提出社区搜索算法CSNERL具有更高的准确性.     

融合链接预测相似度矩阵的属性网络嵌入算法

在属性网络中,与节点相关联的属性信息有助于提升网络嵌入各种任务的性能,但网络是一种图状结构,节点不仅包含属性信息还隐含着丰富的结构信息。为了充分融合结构信息,首先通过定义节点的影响力特性、空间关系特征;然后根据链接预测领域基于相似度的定义构建相似度矩阵,将节点二元组中的关联向量映射到相似度矩阵这一关系空间中,从而保留与节点相关的结构向量信息;再基于图的拉普拉斯矩阵融合属性信息和标签特征,将上述三类信息集成到一个最优化框架中;最后,通过二阶导数求局部最大值计算投影矩阵获取节点的特征表示进行网络嵌入。实验结果表明,提出的算法能够充分利用节点二元组的邻接结构信息,相比于其他基准网络嵌入算法,本模型在节点分类任务上取得了更好的结果。     

一种融合节点属性信息的社会网络链接预测方法

随着大规模社会网络的发展,链接预测成为了一个重要的研究课题。研究了在社会网络中融合节点属性信息进行链接预测,在传统的社会-属性网络图模型的基础上,将节点属性的类别这一重要参量加入到网络构建中。基于此,提出了一系列为网络中不同类型的连边分配边权重的方法,最后通过随机游走的方法进行网络链接的预测。实验表明,所提链接预测方法相比同类方法有明显的效果提升。     

基于节点相似性的图注意力网络表示学习模型

图注意力网络(GAT)通过注意力机制聚合节点的邻居信息以提取节点的结构特征,然而并没有考虑网络中潜在的节点相似性特征。针对以上问题,提出了一种考虑网络中相似节点的网络表示学习方法NSGAN。首先,在节点层面上,通过图注意力机制分别学习相似网络和原始网络的结构特征;其次,在图层面上,将两个网络对应的节点嵌入通过基于图层面的注意力机制聚合在一起,生成节点最终的嵌入表示。在三个数据集上进行节点分类实验,NSGAN比传统的图注意力网络方法的准确率提高了约2%。     

基于边采样的网络表示学习模型

近年来,以微博、微信、Facebook为代表的社交网络不断发展,网络表示学习引起了学术界和工业界的广泛关注。传统的网络表示学习模型利用图矩阵表示的谱特性,由于其效率低下、效果不佳,难以应用到真实网络中。近几年,基于神经网络的表示学习方法因算法效率高、能较好保存网络结构信息,逐渐成为网络表示学习的主流算法。网络中的节点因为不同类型的关系而相互连接,这些关系里隐藏了非常丰富的信息（如兴趣、家人）,但所有现存方法都没有区分节点之间边的关系类型。本文提出一个能够编码这种关系信息的无监督网络表示学习模型NEES,首先通过边采样得到能够反映边关系类型信息的边向量,其次利用边向量为图中每个节点学习到一个低维表示。我们分别在几个真实网络数据上进行了多标签分类、边预测等任务,实验结果表明NEES方法能取得超过现存最好算法的优异效果,且其是可规模化的,可以很好地应用于大型网络的表示与计算。     

结合跳跃连接的多层图注意力网络会话推荐

基于会话的推荐旨在根据匿名用户的短期交互数据来预测用户下一次交互项目. 现有图神经网络会话推荐模型大多在信息传播过程中平等对待所有邻居节点, 而没有区分他们对于中心节点的重要性, 从而给模型训练引入噪声. 此外, 随着图神经网络层数的增加, 过度平滑问题会随之产生. 针对上述问题, 本文提出结合跳跃连接的多层图注意力网络会话推荐模型(MGATSC). 首先利用图注意力网络学习邻居节点对于中心节点的重要性, 并堆叠多层网络以获取高阶邻居信息; 然后为了缓解过度平滑问题, 采用基于残差注意力机制的跳跃连接更新每层网络的节点嵌入, 并通过平均池化得到最终节点嵌入. 最后将反向位置嵌入融合到节点嵌入中, 经过预测层生成推荐. 在Tmall、Diginetica以及Retailrocket这3个公开数据集上的实验结果表明所提模型优于所有基线模型, 验证了模型的有效性与合理性.