基于动态网络模式变化的网络结构增强嵌入.pdf

收稿日期:修回日期:作者简介:张同心()男硕士生主要研究方向为图神经网络:/基于动态网络模式变化的网络结构增强嵌入张同心 魏 强 陆路希(.信息工程大学河南 郑州 .盲信号处理重点实验室四川 成都)摘要:动态网络是网络结构和节点属性会随着时间推移而发生变化的复杂网络 由于动态网络能够更好地表达现实世界从而引起研究者们的兴趣 现实中的动态网络常常会出现网络模式的变化但是现有的动态网络模型在嵌入时往往将所有的快照划归为同一模式来学习并没有特别区分其中隐含的网络模式 针对这一情况提出了网络结构增强嵌入()框架该框架根据网络模式的变化能够有效地提取网络中的模式信息 具体表现为该框架首先判断动态网络时间片所处的模式然后对相同模式网络之间的网络结构信息增强最后在 个真实数据集上进行了链路预测实验 实验结果表明现有的动态网络嵌入模型在本框架下网络嵌入效果有显著地提高关键词:动态网络网络嵌入动态图神经网络中图分类号:文献标识码:文章编号:().引言近年来随着社会的飞速发展各领域的数据量不断增大特别是大规模的社交网络不断涌现例如微博、微信、等 对网络结构数据的分析成为了重要的研究领域对于网络数据的分析通常的做法是将网络映射到一个便于计算的稠密空间 网络嵌入通过学习网络中节点的低维空间表示从而将其转换为常规的机器学习问题 因此如何网络嵌入成为了研究者们关注的问题现有的网络嵌入方法大致分为 种基于随机游走的网络嵌入(如:)、基于矩阵分解的网络嵌入(如:局部线性映射(第 卷第 期 年 月信 息 工 程 大 学 学 报 .)和基于深度学习的网络嵌入(如:图神经网络()随着深度学习的发展基于深度学习的 逐渐成为网络嵌入的主流方法 但是这些网络模型通常只关注于一个给定的、静态的网络然而在现实生活中的网络有着高度的动态特性会频繁发生网络结构和节点属性的变化而网络变化的过程中会留下丰富的历史信息供后续分析使用 所以仅仅依赖静态网络嵌入方法已不满足现实需求研究者需要将研究目标放到动态网络中来随着图神经网络的不断发展和对动态网络的关注增加学术界对动态图神经网络()进行了大量研究其中文献提出了 方法它不依赖于快照的分割可以计算任意时间点的网络嵌入但是应用的网络场景仅适用于二部图网络泛化性能较弱文献提出了 方法它是基于图形嵌入的深度自动编码器可以处理不断增涨动态图已经可以进行基本的动态网络分析文献提出了 它很好地融合了图卷积网络()和循环神经网络的方式 之前研究的 动态嵌入是分别训练每个快照中的静态网络再将其通过循环神经网络串联起来 使用递归神经网络()来进化 从而在进化的网络参数中捕捉动态信息该模型可以再不需要节点一直存在的情况下灵活的处理动态数据文献也提出了一种新的动态网络嵌入方式 它首次将自注意力机制引入到动态图神经网络上并使用多头注意力机制来并行计算 上述的动态网神经网络模型能够对动态网络进行嵌入但是现有动态图神经网络认为网络是缓慢变化的 而现实情况中网络存在多种差异明显的模式并且模式之间存在突发转换例如公司周五时内部交流较多周末同时间段交流较少 这种情况对现有的动态 提出了挑战本文针对动态网络的数据特点提出针对动态网络模式变化的网络结构增强嵌入框架 动态网络因为天然具有相似性所以网络快照之间可以互相作为对照来学习部分未观测到的节点和边 动态网络的数据中普遍具有网络模式的变化的信息这为动态网络的结构获取带来了极大的优势 受到 的启发本文认为在同模式下的动态网络快照中网络结构更为相似而不同模式下的网络结构则差异性较大 所以本文沿用这一思路期望通过网络结构补全的方式增加动态网络信息以增强动态网络嵌入效果 首先得到附带模式标签的动态网络根据动态网络的模式信息对动态网络分模式嵌入 本文的贡献如下:)本文提出了一种有效利用网络模式变化的网络结构恢复框架)本文在大量实验上验证了 框架的有效性 问题定义.动态网络定义本文将动态网络表示为 ()其中 代表网络中随时间不断变化的节点集 代表网络中随时间不断变化的链路集合 代表网络中不断变化的节点属性集合 在本文中的动态网络由快照网络列表组成即 其中 为快照数量 每个快照都有其网络结构()其中是快照上的节点集、是快照 上的链路集、是 快照上的节点特征.网络模式定义网络模式在本文中被定义为动态网络中固有的聚类反映了网络在执行不同任务、发挥不同功能时的结构和状态 网络模式的变化在现实生活中经常会出现其具体表现之一为动态网络中的节点和链路有规律的变化如图 所示图 网络模式演化示意图图 展示了网络模式的变化:一共有 个节点它们分别在不同的时刻属于不同的社区 在时刻社区 而中拥有大量的节点社区 中只有少量的节点所以此刻网络被认为处于 模式在时刻社区中大量的节点流入社区少部分流入社区 在此时认为网络处在 模式 在 时刻社区 中又从社区 和社区 中流入大量节点此时认为网络恢复成模式 本文的研究目标是具有模式变化的网络所以 第 期张同心等:基于动态网络模式变化的网络结构增强嵌入本文希望获得在网络模式变化条件下的动态网络嵌入 网络结构增强方法在这一章节详细介绍 框架 主要由两个部分组成(如图 所示):模式发现单元、网络结构增强单元 其中:模式发现单元作用在动态网络嵌入前它将输入的动态网络快照序列进行网络模式判别用以得到每个网络快照的网络模式信息网络结构增强单元则是对网络中的结构增强它使得在相同模式下能够更多地获取到原有的网络结构在不同的相邻模式下更多的获取新网络结构的信息 接下来详细介绍每个单元组件图 框架结构图.模式发现单元在本小节中讨论模式发现单元 在网络模式判别的过程中本文首先采用的图编辑距离()来衡量快照网络之间的距离并得到快照之间的距离矩阵接着采用 聚类算法对快照进行聚类得到模式不同的快照 这一过程被定义为()()()()()()式中:为快照 为快照的数量 为快照之间的距离矩阵 为网络快照所属的模式 为模式的类别 在得到带有模式标签的快照后为了更好的理解模式发现单元获取到模式随时间变化的示例如图 所示图 模式 时间变化示意图上图中共有 个快照通过聚类算法聚合后按照时间顺序分布得到了模式时间变化图 其中圆形、矩形、三角形分别为不同模式下的快照在图中表现为()、()、()、()个时间段的数据分别为模式、模式、模式、模式.网络结构增强单元在经过模式发现单元的处理后动态网络分成了多个网络模式 在网络结构增强时希望在相同模式下能够更多地获取到原有的网络结构在不同的相邻模式下更多地获取新网络结构的信息基于上述的目标本文设计了一种有偏的图神经网络结构 它有两种表示形式一种基于图注意力机制的结构有偏网络模型和一种基于图卷积的结构平均网络模型 接下来分别介绍这两种网络模型的具体实现过程.基于图注意力机制的结构有偏网络模型图注意力模型是基于图注意力机制的模型()其本质就是训练两个节点间的注意力分数 通过在两个节点间添加一个系数来更改节点之间的权重从而实现不同邻居的信息接受程度不同 由此本文希望设置参数来直接控制节点之间的系数 这样就可以影响两个节点之间的权重从而进一步影响注意力分数 为了让相同模式和不同模式下的邻居聚合程度系数之间有一定的联系所以本文设置了超参数 节点在不同模式下与参数 之间的表示形式不同 信 息 工 程 大 学 学 报 年原节点注意力系数的计算为()()()本文在原有的 基础上添加了一层参数可控的注意力层 具体设置为网络快照中两节点权重 设置为 以达到结构增强的目的 可以认为是对邻居的信息接受程度 越大相同模式下对原有邻居的信息接受程度越小不同模式下对新邻居信息接受程度越小 越小相同模式下对原有邻居的信息接受程度越大不同模式下对新邻居信息接受程度越大如图 所示黑色节点为 时刻快照中节点 原有的邻居黄色为 快照中新加入的邻居在模式不同的情况下本文更倾向于获取到新邻居的信息模式相同时本文更倾向于获取原有的结构信息 将为不同的邻居设置不同的权重以达到网络结构增强的目的图 基于 的动态网络增强结构.基于图卷积的结构平均网络模型相比基于图注意力机制的结构而言基于图卷积的结构平均模型是基于图注意力机制的结构的一种特殊情况 以相同模式为例当 的值无限接近于 时节点在聚合邻居信息的过程中对新邻居的聚合系数为 而对旧邻居的聚合系数无穷大所以此时等于完全断开新邻居和节点之间的联系不同模式的情况下同理 这种方式发生了网络拓扑结构的改变使用更为直接的方式来影响网络信息聚合 本文增加了一层新的 模型用来实现不同模式下的信息聚合 相同模式时只聚合相同模式的邻居信息不同模式时只聚合当前快照中出现的新邻居信息和新链路连接到的节点信息 如图 所示图 基于 的动态网络增强结构 实验结果.数据集设置本文采用了 种数据集来测试 框架下的模型性能这 种数据集为现实世界中的 个真实数据集分别为安然公司员工电子邮件数据集()、加利福尼亚大学欧文分校学生在线社区交互信息数据集()、邮件数据()、邮件数据()其基本信息如表 所示表 真实数据集基本信息数据集节点数量边数量快照数量 .对照方法本文为了证明 框架的有效性本文选取了 种动态图神经网络嵌入模型来进行验证分别为:、)()为基础的动态图神经网络方法它利用递归机制将网络中的特征进行串联从而得到网络的动态嵌入 该方法适用于基于图卷积的结构平均网络模型)()为递归动态图神经网络类型的经典方法 与 不同的是它从结构的层面对网络进行分析用一个 对网络中的参数权重进行串联 该方法适用于基于图卷积的结构平均网络模型 第 期张同心等:基于动态网络模式变化的网络结构增强嵌入)为注意力动态图神经网络类型的典型方法它利用自注意力机制学习快照之间的联系对网络进行动态嵌入 该方法适用于基于图注意力机制的结构有偏网络模型.其他设置本文将在图神经网络领域应用较为广泛的链路预测任务中进行验证 链路预测是利用时间 之前的信息来预测()时刻的网络链接情况由于动态网络的历史信息已经被嵌入到模型的参数中所以通过一个全连接网络获得链路的概率实验中针对链路预测任务采用 曲线下的面积 指标.结果本实验将对照方法和使用 框架的方法通过链路预测任务测试模型的优劣在 种数据集上得到的 性能和计算结果如表 所示表 与 的比较单位:方法.表 结果表明使用在 框架下的动态网络嵌入模型在性能上获得了很大地提升达到了较为理想的效果当使用在 模型中时在数据集 中模型性能能够提升.超参数的影响实验还验证了基于 模型下的改进中超参数 的设置对模型性能的影响 在 数据集中使用 模型进行验证 其中 的值分别设置为.、.、.、.、.、.结果如图 所示图 基于 的动态网络增强结构从图 中可以看到随着 值的增加框架的性能逐渐降低并且在 值为.之后其性能较原模型更差 所以可以认为本文的框架符合预期要求在相同模式的情况下尽可能的获取原有邻居的节点信息 结束语本文将动态网络独有的网络模式属性剥离出来并作为一个重要的特征进行分析 这个角度给了本文很多动态网络分析的有利条件由此提出了一个能够利用动态网络模式信息的动态网络嵌入框架 它根据动态网络之间天然的相似性利用网络补全领域的研究分模式的对动态网络结构进行更改以达到提升嵌入模型性能的效果 值得注意的是该框架具有很好的泛化性能能够适应现有的动态网络嵌入模型在未来的工作中将探索动态网络模式变化带来的其他的可行性例如从网络节点属性的角度对动态网络进行增强嵌入 另外由于 的结构增强嵌入依赖于动态网络模式的划分 所以日后在动态网络模式划分时考虑使用更加有效的网络距离表示方法参考文献:.:.():.:.:.袁立宁李欣王晓冬等.图嵌入模型综述.计算机科学与探索():.:.:.():.:信 息 工 程 大 学 学 报 年:.:/.().:././.:.():./.().:././.:.:.:.:.:.:./.().:././.:.():.(编辑:冯 春)(上接第 页).():.:.高志文陶然单涛.外辐射源雷达互模糊函数的两种快速算法.电子学报():.():.:.:.陶琴潘英锋吴峻岩.一种改进的圆阵干涉仪解模糊算法.空军预警学院学报():.陶琴潘英锋吴峻岩.一种改进的圆阵干涉仪解模糊算法.空军预警学院学报():.():.():.王娟赵永波.变换实现方法研究.火控雷达技术():.():.:.():.(编辑:冯 春)第 期张同心等:基于动态网络模式变化的网络结构增强嵌入