ACTA Scientiarum Naturalium Universitatis Pekinensis

基于时空建模的动态图­卷积神经网络

李荆1 刘钰2 邹磊2,†

- 李荆 刘钰 邹磊

1. 北京大学前沿交叉学科­研究院, 北京 100871; 2. 北京大学王选计算机研­究所, 北京 100871; † 通信作者, E-mail: zoulei@pku.edu.cn

摘要 为了使图表示学习得到­的嵌入向量对节点和边­不断变化的动态图具有­很好的信息表征能力, 提出一种动态图卷积神­经网络模型(DYGCN), 将动态图上的表示学习­建模为时间和空间信息­的聚合。该模型将从图卷积神经­网络(GCN)的空间卷积提取图上的­结构信息与从时间卷积­神经网络(TCN)的因果卷积提取时序上­的历史信息相结合, 同时在空间卷积层加入­自适应的模型更新机制, 使得模型参数随着图结­构的变化能够自适应地­更新。在金融领域数据集上针­对金融欺诈检测进行的­边分类实验表明, 该模型比现有方法有很­大的性能提升。关键词 动态图; 图卷积神经网络(GCN); 图表示学习; 时空卷积

随着卷积神经网络(convolutio­nal neural networks, CNN)在计算机视觉、自然语言处理以及语音­识别等领域的成功应用, 研究者们对图神经网络(graph neural networks, GNN)在图学习方面的潜力产­生极大的兴趣。图像、自然语言和语音信号都­属于欧几里德数据结构(Euclidean data structure), 这类数据结构排列整齐, 很容易定义其中的邻居。例如, 可以用矩阵表示一张图­片中的每个像素点, 将文本和

语音信号视为一维序列。这种数据结构的特性使­得我们很容易定义作用­于其上的卷积操作, 用来提取局部特征。然而, 图(graph)却是一种非欧几里德数­据结构(non-euclidean data structure), 其中的节点并不是规则­的排列。并且, 对于不同节点, 其邻居数目不同, 因此传统CNN的卷积­操作无法直接运用到图­中。

图卷积神经网络(graph convolutio­nal networks,国家自然科学基金(61932001)资助收稿日期: 2020–05–25; 修回日期: 2020–06–07

GCN)将 CNN中的卷积概念扩­展到图中, 通过定义作用于图上的­卷积操作来提取节点的­邻域信息。由于图卷积操作可以对­图结构以及图上的邻域­信息进行有效的提取, 所以GCN在图表示学­习领域表现出强大的优­势。研究表明, GCN在很多图挖掘任­务(如节点分类、边分类、链接预测和聚类等)中有最优的表现[1–2]。已有的图卷积神经网络­大多基于静态图设计,即模型对图的建模和表­示进行学习, 假设图结构不改变。然而, 现实中提取的图是动态­变化的, 图中的节点和边都会随­着时间而有插入和删除, 节点属性和边属性也会­随时间而改变。例如, 在一个以用户为节点, 用户间交易为边的金融­网络中, 一个具有现实意义的任­务就是识别其中的可疑­用户(例如洗钱组织成员)或可疑交易(例如信用卡诈骗交易)。在这个图中, 随着用户间不断进行交­易, 图结构也随之不断地变­化, 因此我们不仅需要关注­图中当前时刻的信息, 也需要分析图上历史时­刻的信息。如图 1所示, 银行账户F在时刻t可­能是一个正常用户, 之后加入某洗钱组织, 从而在 t+1时刻开始一些可疑交­易(虚线箭头所示 F→D, D→B, B→C, C→F), 因此在t+2 时刻, 根据账户H与账户F之­间的联系以及历史交易­记录等, 需要考虑H是否有可能­也变成了可疑用户。在图不断变化的场景下, 需要用动态模型去提取­动态图上的结构信息以­及历史时刻信息, 从而得到具有丰富信息­的节点表示。本文提出一个基于时空­建模的动态图卷积神经­网络(dynamic graph convolutio­nal network, DYNGCN)来建模动态图上的节点­表示问题。模型将动态图的节点表­示学习视为时间维度和­空间维度信息的聚合, 并引入自适应的模型更­新机制, 感知图结构的动态性。为了进一步验证模型的­建模能力, 在多组比特币交易数据­集上进行链接预测任务, 实验结果表明了 DYNGCN模型对动­态图节点信息提取的有­效性。

1 相关工作1.1 静态图表示学习方法

传统的图表示学习方法­是在图的邻接矩阵计算­出的相似矩阵上进行奇­异向量分解(singular vector decomposit­ion, SVD), 得到节点的低维向量表­示[3–4]。这种方法非常直观, 但基于SVD的操作却­缺乏可扩展性。另一类方法是受Wor­d2vec[5]对单词向量表示学习的­启发, 将处理句子的方法迁移­到处理图中(如 Deepwalk[6]和 Node2vec[7]), 在图中设计随机游走策­略, 得到节点序列, 然后将这些节点序列视­为句子, 输入 Skipgram[5]模型, 学习到节点的低维向量­表示。随着深度学习在很多领­域表现出的巨大优势, 如GNN[8–12]广泛应用于节点表示学­习领域, 第三类方法主要通过设­计图卷积算子来学习图­中节点的邻域信息。以上方法都聚焦在静态­图上的节点表示学习, 而缺乏对图动态性的建­模。

1.2 动态图表示学习方法1.2.1 基于矩阵分解的方法

解决动态图上节点表示­学习问题的一个思路是, 将静态图上的方法进行­扩展, 比如加入某些更新机制。DANE[13]就是采用这种方法, 将动态图视为时序上的­一系列快照(snapshot), 每个快照是一个静态图, t时刻的向量表示是由­t–1时刻的特征向量更新­而来, 不是在每个时间切片上­都重新计算。相似地, DHPE[14]也动态地更新学习到的­表示向量, 同时通过广义的奇异值­分解(generalize­d singular value decomposit­ion, Gsvd)和矩阵摄动理论(matrix perturbati­on theory), 保留高阶相似性。在不断更新

求近似的过程中, 这类增量SVD的方法­会产生越来越严重的误­差累积, 因此Zhang等[15]提出一种SVD重启的­最大误差界限理论, 通过设置最优的重启时­间来减少学习过程中的­误差累积。

1.2.2 基于随机游走的方法

受静态图上基于随机游­走方法的启发, 一些研究者提出在动态­图上随机游走的方法。DNE 模型[16]采用一种与LINE[17]等价的可分解的目标函­数来学习新节点的表示­向量, 同时也提出一种对受到­最大影响原始节点的嵌­入向量调整机制。另一方面, CTDNE[18]将动态图建模为连续时­间上的过程,为条边设置多个相关的­时间戳, 同时将随机游走的路径­限制在符合边的时间序­列路径上。CTDNE 将动态性和时序性考虑­进随机游走的过程中, 同时也保证了模型的可­扩展性。

1.2.3 基于自编码器的方法

此类动态图表示学习方­法是基于一些非监督学­习框架, 例如自编码器。DYNGEM[19]利用前一时刻的自编码­器来初始化当前时刻的­训练参数, 从而能够保留节点表示­的历史信息。同时, DYNGEM通过一个­启发式的算法, 根据不同时刻的图结构, 将SDNE[20]的架构进行调整, 从而适应新的图结构。考虑到DYNGEM只­利用过去一个时刻的历­史信息,

[21] Goyal 等 随之提出 dyngraph2v­ec 模型, 可以编码更多的历史时­刻信息, 但架构更复杂, 不具有更好的可扩展性。

1.2.4 基于点过程的方法

为了将图的动态性建模­为连续的而不是分段的­时间切片, 基于点过程的方法, 尝试将图中的边视为一­个事件, 则一个事件的发生会反­过来影响整个网络结构。Knowevolve[22]和 Dyrep[23]是其中的重要研究成果。Dyrep将图的动态­性考虑为关联过程(associatio­n process) 和通信过程 (communi-cation process) 两个过程, 将图中的节点表示视为­关联过程和通信过程中­间的调解者, 这两个过程反过来又

[24]带来节点表示的更新。Dynamictri­ad 模型 也受点过程的启发, 尝试建模图中的闭合三­点(两两之间有边相连的3­个节点)是如何从开放的三点(3个节点中有两个节点­之间没有边相连)的状态发展而来。Dynamictri­ad模型认为闭合三点­的形成是图的动态性的­反映。这类方法考虑了连续时­间的因素,在事件建模和预测方面­有很强的优势。

1.2.5 基于图卷积的方法

随着图卷积神经网络在­获取图结构信息方面表­现出的巨大优势, 一种新的动态图嵌入学­习的方法是将GCN与­RNN (如 LSTM等)相结合, 其中GCN用来提取图­结构上的信息, RNN则用来建模时间­维

[25]度上的动态变化。Seo 等 提出两种GCRN架构,其共同特征是利用GC­N来学习节点的向量表­示,然后将一段时间学习到­的向量序列输入LST­M 模型, 建模序列上的动态性。两种架构的唯一区别在­于, 其中一个模型将传统的­LSTM中的欧几里德­2D卷积运算修改为图­卷积运算。相似地, Manessi 等[26]提出 WD-GCN/CD-GCN 结合 LSTM的变种和扩展­的图卷积运算来建模图­结构及其长短期依赖。不同的是, WD-GCN的输入是图序列, 而CD-GCN 的输入是对应的节点特­征的有序序列。

进一步地, GCN-GAN模型[27]将带权动态图上的时序­性链接预测任务建模为­GCN与RNN的架构,再与生成性对抗网络(generative adversaria­l networks, GAN)相结合。GCN-GAN模型同样运用 GCN去学习每个时间­片上的拓扑结构特征, 然后运用LSTM去学­习序列性的变化, 采用GAN的学习框架­去生成下一个时间步, 从而学习到更有效的节­点表示。Star[28]模型加入对偶注意力(attention)机制来增强GCN和R­NN架构的学习能力。Evolve-gcn[29]模型改变了之前方法中­学习节点表示在时序上­的动态性的思路, 转而去学习 GCN参数在时序上的­动态性。虽然Evolvegc­n也采用GCN与 RNN相结合的方式, 但此结构中的RNN用­于建模 GCN的权重参数在时­间维度上的动态性, 从而学习到动态图上的­节点表示。

2基于时空建模的动态­图卷积神经网络2.1 问题定义

我们定义动态图和动态­图上的表示学习如下: …,一个动态图被表示为多­个静态图的序列, 即 G= …, {G1, G2, GT}, 其中 Gt=(vt, Et)表示在时刻t, t∈{1, 2, T}的快照。对于图Gt的邻接矩阵­AT∈RN×N, 如果 (vt)i 和 (vt)j 之间有边相连, 那么 (At)i,j=1, 否则

⋯, ∀t∈{1, (At)i,j=0。动态图上的节点表示学­习为学习到一组映射的­序列F={f1, f2, ft}, 2, …, T}, 其中每个映射都将时刻 t 的节点映射为低维向量(yt)v= ft (v), 使得映射后的向量能保­留节点的原始信息。也就是说若两个点在原­始图中越相似, 则它们映射

后的向量就越接近。

2.2 模型架构

本文提出的模型将动态­图上的表示学习建模为­时间和空间信息的聚合, 同时加入模型自适应机­制,可以随着图结构的变化­而更新模型参数。如图2所示, 模型基本架构由空间卷­积层和时间卷积层组成,模型第一层是由一个空­间卷积层来聚合节点的­邻居信息, 同时利用GRU单元自­适应更新参数。输出的向量输入第二层­的时间卷积层, 聚合当前时刻和历史时­刻的信息。由此, 每个节点的表示都融合­当前以及历史时刻的邻­居信息。最后, 加上一个自适应的空间­卷积层, 用来聚合邻居的当前时­刻和历史时刻信息。

2.3 空间卷积层

我们利用GCN的图结­构提取优势来学习每个­时间片下的结构信息。GCN通过定义的谱图­卷积聚合邻居信息, 从而将卷积的思想扩展­到图上。形式化地, 对于t时刻的图Gt=(vt, Et), GCN的第l层输l入­为第l –1层输出的向量 X 和邻接矩阵At, 输出是t更新后的节点­向量 X tl 。第 l层的运算表示为1 X l  1   ( X代表第݈层图卷积层, l , A , W l )  ( D ˆ  1/2 A ˆ Dˆ  1/2 l l X W ), (1) t t t t t tt t t其中, 上角标l 下角标t表示第  t个时间步;A ˆ  A  I ; D ˆ  diag N Aˆ ; I为单位t t t j 1 t ( ij ) D ˆ  1/ 2 A ˆ Dˆ 1/ 2矩阵; 运算 是对邻接矩阵At的一­个归一t tt l化处理, 以此作为一个近似的图­卷积滤波器; W t是时刻t的第l层的­权重矩阵; 函数σ为激活函数(如RELU)。网络第一层的输入 X t0 是 t时刻节点的特征矩阵, 矩阵的每一行是每一个­节点的K维特征向量。经过L层的图卷积层, 每一个时间切片的输出­向量中都聚合了节点的­邻居信息。考虑到图的动态性, 动态图卷积层在静态G­CN的架构上加入更新­机制。因为当图结构改变时, 卷积操作的权重参数也­应进行更新, 以便适应新的图结构。动态图卷积层采用RN­N组件对GCN模型的­权重参数进行更新, 对于每一个t∈{1, 2, …, T}和l ∈{1, 2, …, L}, RNN组件都以参数W­tl 的初始值为输入, 输出更新后的Wtl 。虽然RNN的多种实现(如LSTM和GRU)都能达到这个目的, 但由于GRU结

构的输入包含每个时刻­的节点表示, 可以为权重参数的更新­引入更丰富的图结构信­息, 因此我们的架构采用G­RU的实现方式。

时刻t第l层的权重更­新方式如下: W l   (X l ,W l)  (1 Z l ) W l Z l  Wˆ l , (2) t t t t t 1 t t

Zl  sigmoid( Ul Xl  V l W l  B l ), (3) t Z t Z t 1 Z Rl  sigmoid( U l X l  V l W l  Bl ), (4) t R t R t 1 R W  tanh( Ul Xl  V ( R W )  Bl , (5) l l l l t W t W t t 1 W l l l其中, Z , R 和Wt分别是更新门输出、重置门输出t t和预输出。权重矩阵的更新可以看­作是将标准的GRU操­作作用在矩阵的每一列。标准GRU操作是针对­向量之间的, 而更新GCN权重矩阵­的过程是针对矩阵之间­的操作。时刻t的权重矩阵Wt­l 作为GRU的l隐状态; t时刻第l层的节点表­示矩阵 X 作为GRU t单元的输入, 以引入当前时刻的信息; GRU单元输l l出更新后的Wt , 作为下一时刻的权重矩­阵。W 1 t 1的计算中包含历史时­刻和当前时刻的信息。由于权l l重矩阵Wt 与节点表示矩阵 X 有不同的列维度, 因t l此在本层的网络层操­作中新加入对 X 的采样, 以t达到与Wtl 相同的列数。GCN模块自下而上聚­合节点的邻居信息, 而GRU模块随时间维­度自左向右更新权重参­数。由此, 空间卷积层动态地获得­节点的邻域信息。空间卷积层的操作可以­形式化地表示为l 1  l l  l  l l )), (6) X  ( X , A , W )  ( X , A , ( X , W t t t t t t t t其中, 函数和 分别表示图卷积操作和­权重更新操作。

2.4 时间卷积层

在动态图节点表示学习­中提取时序信息是非常­关键的环节。已有的模型大多采用R­NN的架构来建模时序­变化, 由于基于RNN的架构­具有复杂的门机制, 因此在运算上更加耗时, 也更消耗内存。同时, 标准的RNN在训练中­容易出现梯度消失的问­题, 并且只能获取较短时间­的记忆, 对长时间的序列无法很­好地处理。虽然LSTM和GRU­在一定程度上解决了梯­度消失和短期记忆的局­限, 但相对于基于CNN的­架构, 在运算速度、内存消耗以及性

能表现方面依然处于劣­势, 因此我们的模型采用基­于CNN的架构(即TCN[30]结构)来获取历史信息。

与 RNN的架构相比, 由于卷积操作的可并行­性, TCN使得运算速度获­得极大提升, 同时其运算对内存的消­耗也更小。重要的是, TCN结构对历史信息­的感受域更灵活, 可以通过简单地增大卷­积核或增加扩张卷积的­dilation size来增大感受域, 从而获取更长时间序列­的信息。另一方面, RNN的架构对动态性­的建模是将历史信息单­纯地归纳入每个时刻的­Hidden state 中, 通过 Hidden state来记忆历史­信息。TCN的卷积结构则通­过灵活性的信息聚合方­式, 将历史信息与当前时刻­的信息相结合, 从而提取动态图中的时­序信息和结构信息, 也从另一个角度将时间­卷积与空间卷积进行统­一。

时间卷积层由一个1D­的全连接卷积模块(1D fully-convolutio­nal unit)和一个因果卷积模块(causal convolutio­nal unit)构成, 1D的全连接卷积操作­保证输出层与输入层有­相同的序列长度, 因果卷积操作则保证在­t时刻的输出都只由它­之前的时刻(包括当前时刻)卷积得到, 由此保证由当前时刻的­信息和历史信息去建模­未来时刻的预测。在因果卷积阶段, 为使网络结构对更长的­时间序列也有更长更灵­活的感受域, 在因果卷积中加入扩张­卷积(dilated convolutio­ns)的设置, 随着网络层数增加, 卷积的扩张(dilation)值设置为2的层数次幂。图3 展示TCN中的扩张卷­积过程, 其中每层的 dilation size依次为1, 2和 4, 卷积核大小为2。形式化地, 给定一个第l层的长为­T, 有M维特

l ×征的输入序列X ∈ RT M, 以及一个滤波器f :{0,

l  1, …, k–2}, 对于X 的元素x, 卷积运算 定义如下:  ( x )  ( Xl  f )( x )   k  2 f ( i )  X l , (7) d i 0 x  d i

其中, d是扩张因子, k是滤波器大小, x  d  i 代表历史的方向。我们可以通过增加滤波­器大小 k 或增加扩张因子d来增­大卷积的感受域。同时, 卷积操作支持对序列的­并行运算, 因此在效率上有极大的­提升。

时空卷积模型第l层空­间卷积后的节点嵌入向­量是对邻居信息的聚合, 经过时间卷积层后, 可以得到每个节点以及­节点邻居的历史信息。在此之上叠加一个空间­卷积层, 则每个节点的向量表示­都包含它及其邻居的当­前和历史时刻信息的聚­合。因此, 这种时间卷积与空间卷­积相互交叠的模型结构­使得输出的节点嵌入向­量拥有更丰富的结构信­息和历史信息。

2.5 模型训练

为了测试模型的表示能­力, 我们在特定的边分类任­务中对模型进行训练。边分类任务在很多现实­场景下有很强的现实意­义, 例如对金融网络中的犯­罪识别, 就需要对两个账户之间­的连边进行边分类研究。动态图下的边分类任务­旨在预测某条边(u, v)在 t时刻的边标签类别。为了对边进行分类, 我们需要边的两个端点­的节点向量表示。给定有边相连的两个节­点u和v在 t时刻的向量表示分别­为 X tu和 X tv , 用参数矩阵P来预测边(u, v)的标签: yuv  softmax( P [ Xu ; X v ]), (8)

t t t模型的交叉熵损失函­数为L     1( zt )i log( yt ) i, (9) T N uv uv t  1 ( u , v ) uv i  uv其中, z 表示边的真实标签类别; 权重参数αuv 是

t平衡类别分布的权重­的超参数, 实验的数据集均存在严­重的类别不均衡问题, 通过调节 αuv来平衡分类类别­的比重。

3 实验3.1 数据集

在两个金融领域数据集­上进行模型验证。数据集来自两个不同的­比特币交易网站的用户­之间的信任度评分网络。数据集的详细信息如表­1所示。

Bitcoin OTC①数据集是从比特币交易­网站中提取的用户之间­的信任度评分网络。用户用-10 (完全不信任)到+10(完全信任)对其他用户进行打分, 每

个打分用相应的时间戳­代表打分时间。数据集的时间跨度约为­5年, 我们设置13.8天的时间间隔, 数据集共产生138个­时间步。将138个时间步切分­为训练集、验证集和测试集, 切分比例见表1。另外, Bitcoin OTC数据集的类别分­布极不均衡, 89%的数据都是正例, 负例只占很少的部分。

Bitcoin Alpha②数据集同样是一个比特­币用户之间的信任网络, 但用户和评分数据提取­自另一个比特币平台B­tc-alpha。评分数据为 2010 年 11 月8 日—2016 年 1 月 22 日, 设置 13.6天的时间间隔,将数据集分为140个­时间步。训练集、验证集和测试集的划分­比例见表1。评分依然从–10 (完全不信任)到+10 (完全信任), 但是与 Bitcoin OTC的89%的正例比例相比, Bitcoin Alpha有更高的正­例比例( 93%)。由于两个数据集都存在­类别严重不均衡问题,在反欺诈场景下, 负例的评分类别更值得­关注。所以, 我们把负分的类别作为­分类的主类别, 更加注重负分类的分类­情况。

3.2 对比模型

我们使用静态方法和动­态方法, 将DYNGCN模型与­一些现有模型进行对比。在对比模型中, 动态方法是从不同的方­向进行: 节点导向的(基于节点表示向量的动­态性)、模型导向的(基于模型参数)以及各自不同的动态建­模方式。

GCN 这是一个静态的图卷积­模型, 也是进行图表示学习的­经典方法。模型通过谱卷积聚合节­点的邻居信息来学习节­点的嵌入向量。由于动态图中的每一个­时间步都会产生一个图­的快照, 我们对每个时间步都采­用同一个GCN模型, 即不考虑图的动态性, GCN模型基于每个时­间步上的图进行训练。

GCN-GRU[25] 将GCN与序列建模相­结合, 首先通过GCN架构学­习每个时间快照下节点­的表示向量, 再将这些向量输入GR­U 单元, 学习节点表示的动态性。此方法对动态性的表示­建立在节点表示

向量上, 属于节点导向的方法。为了更好地进行对比, 本实验将原方法中的C­hebnet更换为G­CN, 将LSTM替换为GR­U。

Evolvegcn 这是一种模型导向的方­法。此方法也将GCN与R­NN相结合, 但与GCN-GRU不同, Evolvegcn中­采用RNN建模GCN­参数的更新。整个模型训练沿着卷积­层从下到上和时间维从­前到后进行。将动态性建模到RNN­的隐向量中, 针对每个时间步, 学习到更新后的GCN­权重参数, 节点的表示向量经过更­新后的权重参数, 进行图卷积运算,得到更新后的节点表示。Evolvegcn有­Evolvegcnh­和 Evolvegcn-o两种实现方法。-H类采用GRU进行动­态建模, -O类采用LSTM进行­动态性建模。我们的对比基于这两种­方法。

3.3 实验设置

两个数据集在每个时间­步上的边都比较少, 导致每个时间步的图快­照很稀疏。为了让图表示学习算法­有更好的学习能力, 我们设置每条边的生存­时长为自边产生起10­个时间步的时间窗口。实验中,对历史信息的步长设置­为10。所有模型的GCN卷积­层数都为 2, Bitcoin OTC数据集的 em-bedding size设置为110, Bitcoin Alpha的 embedding size 设置为90, 同时设置两层GCN卷­积的 embed-ding size为相同值。输入的节点特征设置为­节点的出度/入度值。模型中的权重初始化均­为正态分布初始化,并且都采用Adam优­化器, dropout的比例­均设置为0.3, 学习率(learning rate)设置为 0.001。我们在损失函数中加入­L2正则化项, L2正则的权重设置为­0.0005。所有测试集上的结果均­在验证集最优的迭代轮­下记录。

3.4 实验结果

表2展示DYNGCN­模型与对比模型的分类­表现对比。两个数据集的类别不均­衡使得模型的分类能

力面临很大挑战, 但本文的DYNGCN­模型取得最好的分类能­力, 比其他模型有明显的优­势。对于整体的分类能力, 我们对比准确率和加权­F1值; 由于小类对反金融欺诈­有更强的现实意义, 我们也对比小类的 F1值以及对应的精确­率和召回率。表2中所有的实验结果­均为在验证集上取得最­优时的测试结果。

从表2可以发现, DYNGCN有最高的­分类准确率和加权F1 值, 表明 DYNGCN有很好的­总体分类性能表现。对于小类的分类结果, DYNGCN也达到最­好的F1值和精确率。虽然从召回率来看, DYNGCN略低于G­CN和 GCN-GRU, 但DYNGCN仍然优­于其他方法, 因为其他方法虽然有更­高的召回率, 却以更低的精确率为代­价。作为精确率和召回率的­调和平均值, F1值在分类性能上是­更有效的评估标准。

进一步地, 我们绘制在Bitco­in Alpha测试集上小­类的 F1值和分类准确率随­时间变化曲线(图 4)。可以看出, 静态的GCN方法与其­他动态方法有明显的差­距, 并且DYNGCN的优­势在各个时间步都更明­显。另外, GCN方法的准确率也­更低。因为GCN是为静态图­设计的, 未考虑图上的动态性, GCN在动态图上的性­能劣势反映动态性建模­的必要性和优势。

从图4可以看出, DYNGCN模型的优­势在整个时间轴上都可­以保持。特别地, 对于时间步15, 其他方法的分类能力都­非常差, 而DYNGCN模型依­然保持F1值的绝对优­势。这得益于DYNGCN­模型对时空信息的双重­建模, 能对于时间序列上的突­变情况有较为稳定的表­现。另外, 相比两个类型的 Evolvegcn, DYNGCN都有更好­的分类表现, 因为 Evolvegcn只­关注模型权重参数的动­态性而忽略图结构的变­化。GCN-GRU的相对更低分类­能力是因为,虽然每个节点的历史信­息都被考虑, 但由于DYNGCN

独特的时空卷积操作以­及模型更新机制, 对于更高层次的表示学­习, 仍然是DYNGCN更­有优势。

4 总结

本文提出一种动态图的­表示学习模型DYNG­CN,通过时间卷积和空间卷­积的交替进行以及自适­应的模型更新机制, 聚合时间维度和空间维­度的信息,可以学习到更有效的节­点表示。进一步地, 在两个类别分类极其不­均衡的动态金融网络中­进行边分类任务, 结果表明 DYNGCN模型优于­所有对比模型。本文对动态图表示学习­的研究具有很强的现实­意义, 也可为未来的研究方向­提供多种可能性。后续工作中, 可以进一步提升模型的­可扩展性, 将模型的图表示学习任­务扩展到更广泛的领域, 如节点分类、链接预测和聚类等, 同时增加对其他领域数­据集的学习和分析。

参考文献

[1] Kipf T N, Welling M. Semi-supervised classifica­tion with graph convolutio­nal networks [EB/OL]. (2017– 02–22)[2020–05–20]. https://arxiv.org/abs/1609.02907 [2] Hamilton W, Ying Zhitao, Leskovec J. Inductive representa­tion learning on large graphs // Guyon I, Luxburg U V, Bengio S, et al. Advances in Neural Informatio­n Processing Systems. Long Beach: Current Accociate, 2017: 1024–1034 [3] Cao Shaosheng, Lu Wei, Xu Qiongkai. Grarep: learning graph representa­tions with global structural informatio­n // Proceeding­s of the 24th ACM Internatio­nal on Conference on Informatio­n and Knowledge Management. New York, 2015: 891–900 [4] Ou Mingdong, Cui Peng, Pei Jian, et al. Asymmetric transitivi­ty preserving graph embedding // Proceeding­s of the 22nd ACM SIGKDD Internatio­nal Conference on Knowledge Discovery and Data Mining. New York, 2016: 1105–1114 [5] Mikolov T, Chen Kai, Corrado G, et al. Efficient estimation of word representa­tions in vector space [EB/OL]. (2013–09–07)[2020–05–20]. https://arxiv.org/ abs/1301.3781v3 [6] Perozzi B, Al-rfou R, Skiena S. Deepwalk: online learning of social representa­tions // Proceeding­s of the 20th ACM SIGKDD Internatio­nal Conference on Knowledge Discovery and Data Mining. New York, 2014: 701–710 [7] Grover A, Leskovec J. Node2vec: scalable feature learning for networks // Proceeding­s of the 22nd ACM SIGKDD Internatio­nal Conference on Knowledge Discovery and Data Mining. New York, 2016: 855–864 [8] Bruna J, Zaremba W, Szlam W, et al. Spectral networks and locally connected networks on graphs [EB/OL]. (2013–12–21)[2020–05-20]. https://arxiv.org/ abs/1312.6203 [9] Chen Jie, Ma Tengfei, Xiao Cao. FASTGCN: fast learning with graph convolutio­nal networks via importance sampling [EB/OL]. (2018–01–30)[2020–05–20]. https://arxiv.org/abs/1801.10247 [10] Defferrard M, Bresson X, Vanderghey­nst P. Convolutio­nal neural networks on graphs with fast localized spectral filtering // Lee D D, Sugiyama M, Luxburg U V, et al. Advances in Neural Informatio­n Processing Systems. Barcelona, 2016: 3844–3852

[11] Hamilton W, Ying Zhitao, Leskovec J. Inductive representa­tion learning on large graphs // Guyon I. Luxburg U V, Bengio S, et al. Advances in Neural Informatio­n Processing Systems. Long Beach, 2017: 1024–1034 [12] Veličković P, Cucurull G, Casanova A, et al. Graph attention networks // Internatio­nal Conference on Learning Representa­tions [EB/OL]. (2018–02–04) [2020– 05–20]. https://arxiv.org/abs/1710.10903v1 [13] Li Jundong, Dani H, Hu Xia, et al. Attributed network embedding for learning in a dynamic environmen­t // Proceeding­s of the 2017 ACM on Conference on Informatio­n and Knowledge Management. New York, 2017: 387–396 [14] Zhu Dingyuan, Cui Peng, Zhang Ziwei, et al. Highorder proximity preserved embedding for dynamic networks. IEEE Transactio­ns on Knowledge and Data Engineerin­g, 2018, 30(11): 2134–2144 [15] Zhang Ziwei, Cui Peng, Pei Jian, et al. Timers: errorbound­ed SVD restart on dynamic networks [EB/OL]. (2017–11–27)[2020–05–20]. https://arxiv.org/abs/1711. 09541 [16] Du Lun, Wang Yun, Song Guojie, et al. Dynamic network embedding: an extended approach for skipgram based network embedding // Proceeding­s of the 27th Internatio­nal Joint Conference on Artificial Intelligen­ce. Stockholm, 2018: 2086–2092 [17] Tang Jian, Qu Meng, Wang Mingzhe, et al. Line: large-scale informatio­n network embedding // Proceeding­s of the 24th Internatio­nal Conference on World Wide Web. Florence, 2015: 1067–1077 [18] Nguyen G H, Lee J B, Rossi R A, et al. Continuous­time dynamic network embeddings // Companion Proceeding­s of the Web Conference. Lyon, 2018: 969– 976 [19] Goyal P, Kamra N, He Xinran, et al. Dyngem: deep embedding method for dynamic graphs [EB/OL]. (2018–05–29)[2020–05–20]. https://arxiv.org/abs/1805. 11273 [20] Wang Daixin, Cui Peng, Zhu Wenwu. Structural deep network embedding // Proceeding­s of the 22nd ACM SIGKDD Internatio­nal Conference on Knowledge Discovery and Data Mining. New York, 2016: 1225– 1234 [21] Goyal P, Chhetri S R, Canedo A. dyngraph2v­ec: capturing network dynamics using dynamic graph representa­tion learning [EB/OL]. (2018–09–07)[2020–05– 20]. https://arxiv.org/abs/1809.02657v2 [22] Trivedi R, Dai Hanjun, Wang Yichen, et al. Knowevolve: deep temporal reasoning for dynamic knowledge graphs // Proceeding­s of the 34th Internatio­nal Conference on Machine Learning. Sydney, 2017: 3462–3471 [23] Trivedi R, Farajtabar M, Biswal P, et al. Representa­tion learning over dynamic graphs [EB/OL]. (2018– 03–11)[2020–05–20]. https://arxiv.org/abs/1803.04051v2 [24] Zhou Lekui, Yang Yang, Ren Xiang, et al. Dynamic network embedding by modeling triadic closure process // Proceeding­s of the Thirty-second AAAI Conference on Artificial Intelligen­ce. New Orleans, 2018: 571–578 [25] Seo Y, Defferrard M, Vanderghey­nst P, et al. Structured sequence modeling with graph convolutio­nal recurrent networks [EB/OL]. (2016–12–22)[2020–05– 20]. https://arxiv.org/abs/1612.07659 [26] Manessi F, Rozza A, Manzo M. Dynamic graph convolutio­nal networks. Pattern Recognitio­n, 2020, 97: 107000 [27] Lei Kai, Qin Meng, Bai Bo, et al. GCN-GAN: a nonlinear temporal link prediction model for weighted dynamic networks // IEEE Conference on Computer Communicat­ions. Paris, 2019: 18758423 [28] Xu Dongkuan, Cheng Wei, Luo Dongsheng, et al. Spatio-temporal attentive rnn for node classifica­tion in temporal attributed graphs // Proceeding­s of the 28th Internatio­nal Joint Conference on Artificial Intelligen­ce. Macao, 2019: 3947–3953 [29] Pareja A, Domeniconi G, Chen Jie, et al. Evolvegcn: evolving graph convolutio­nal networks for dynamic graphs [EB/OL]. (2019–11–18)[2020–05–20]. https:// arxiv.org/abs/1902.10191v3 [30] Bai Shaojie, Kolter J Z, Koltun V. An empirical evaluation of generic convolutio­nal and recurrent networks for sequence modeling [EB/OL]. (2018–04– 19)[2020–05–20]. https://arxiv.org/abs/1803.01271

 ??  ?? 图 1动态图示例Fig. 1 An example of a dynamic graph
图 1动态图示例Fig. 1 An example of a dynamic graph
 ??  ?? 红色圆点代表空间聚合­中的中心节点, 黄色圆点代表其一阶邻­居, 橙色圆点代表历史信息­聚合中的数据流向, 灰色圆点代表时空聚合­中未激活节点图 2 DYNGCN 模型架构Fig. 2 DYNGCN model architectu­re
红色圆点代表空间聚合­中的中心节点, 黄色圆点代表其一阶邻­居, 橙色圆点代表历史信息­聚合中的数据流向, 灰色圆点代表时空聚合­中未激活节点图 2 DYNGCN 模型架构Fig. 2 DYNGCN model architectu­re
 ??  ?? 图 3 TCN 中扩张卷积示例Fig. 3 An example of dilation convolutio­n in TCN
图 3 TCN 中扩张卷积示例Fig. 3 An example of dilation convolutio­n in TCN
 ??  ??
 ??  ??
 ??  ?? 图 4 F1值和准确率随时间­变化曲线Fig. 4 F1 and accuracy score over time
图 4 F1值和准确率随时间­变化曲线Fig. 4 F1 and accuracy score over time

Newspapers in Chinese (Simplified)

Newspapers from China