【动态图表征】 TREND

论文信息

TREND: TempoRal Event and Node Dynamics for Graph Representation Learning

出处:WWW'21

链接:https://arxiv.org/abs/2203.14303

前言前言前言

康复训练开始!

逛WWW2022接收论文,刷到了这篇动态图表征的paper,想着之前看过好些时空图相关的论文,就寻思着瞅瞅有啥新思路没。

惯例先看看文章想解决啥问题。

Previous methods do not employ Hawkes or similar point processes for modeling the exciting effects between events [42], or not use message-passing GNNs for preserving the structures and features of nodes in an inductive manner [22, 47], or neither [25].

针对的问题就是时序图中的节点表征,也是想加入新的方法来提提效。对比的实验方法有CTDNE、TGAT、DyRep这些。上面文章总结的问题是没有使用过霍克斯过程或类似的点过程来处理"事件"(某个时间点下两个节点之间的边被成为事件)。或者是没有用直推式的图神经网络来处理,可能会导致新节点加入会很麻烦的问题。此外,论文还提出了两个挑战:

Challenge 1: How do we capture the uniqueness of the events on an individual scale?

Challenge 2: How do we govern the occurrence of events on a collective scale?

有点类似整体和个体的关系,每个事件在具有整体意义的同时也会具有个体意义,如果只考虑整体则会使所有边表征过于趋同(虽然会让长尾事件好处理一些),但如果过于关注事件的个体性则会导致容易过拟合,长尾事件难以表征等问题。文章借鉴了元学习的思路来处理这个,后面再说。

又细看了一眼,第一个问题就是在处理如何让各个事件表现出其个体化信息,第二个问题是在考虑整体事件(一系列事件发生对某件事情的影响),之前的那种理解应该是单指Challenge 1的。

基本概念定义

动态图表征

动态图可以用G=(V,E,T,X)\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{T},\mathcal{X})表示,V\mathcal{V}表示节点集合,E\mathcal{E}表示边集合,T\mathcal{T}表示时间域,X\mathcal{X}是节点的特征矩阵。事件被定义为节点iijj在时间tt中的边连接。和传统的图结构稍有差别的点在于,动态图中两个节点之间会在不同时间点下存在多次边连接,这也是静态图很难表示的一种情况。

动态图表征的目的是为了对于给定的G\mathcal{G},习得一个模型Φ(;θ)\Phi(·;\theta)。这个模型能将任何时间点的图中的节点映射到一个特征空间中。

霍克斯过程

论文里介绍的比较简单,去“Hawkes Process”[1]找了一下介绍。

The Hawkes process (HP) is a mathematical model for these ‘self-exciting’ processes, named after
its creator Alan G. Hawkes [4]. The HP is a counting process that models a sequence of ‘arrivals’ of
some type over time, for example, earthquakes, gang violence, trade orders, or bank defaults. Each
arrival excites the process in the sense that the chance of a subsequent arrival is increased for some
time period after the initial arrival. As such, it is a non-Markovian extension of the Poisson process.

大致意思是HP模拟的是一种随着时间推移,某种事件的到达序列。在初始事件之后的每次事件到达,都会使得后续到达概率增加。通用公式如下
λ(t)=μ(t)+tk(ts)dN(s)(1) \lambda(t)=\mu(t)+\int_{-\infin}^{t}{k(t-s)dN(s)}\tag{1} 其中μ(t)\mu(t)表示在t时刻的基础事件强度(我理解就是该时刻下事件发生的基础概率),kk表示核函数,用来建模历史事件对当前事件的时间衰减。N(s)N(s)表示截至到t时间为止的所有事件。

模型模型模型

结构图

放张整体结构图先压压惊

FrameWorkFrameWork

基于霍克斯过程的GNN

一点点来,先看左半边好了。用GraphSage的采样聚合思想去看这半边会很容易,其实就是把图按照边上的t时刻拆分,再分阶段去做聚合。如果要实现的话大概在GraphSage的基础上对邻居节点的样本聚合和顺序做些修改就行。

看看论文咋写的。

  • 时序图上的霍克斯过程

    这部分讲的是如何把霍克斯过程放到时序图上。直接看公式吧:
    λi,j(t)=μi,j(t)+i,j,tHi(t)γj(t)k(tt)+i,j,tHj(t)γi(t)k(tt)(2) \lambda_{i,j}(t)=\mu_{i,j}{(t)}+\sum_{i,j^{'},t^{'}\in{\mathcal{H}_i(t)}}{\gamma{j^{'}(t^{'})k(t-t^{'})}}+\sum_{i^{'},j,t^{'}\in{\mathcal{H}_j(t)}}{\gamma{i^{'}(t^{'})k(t-t^{'})}}\tag{2} 对应上面的公式,μi,j(t)\mu_{i,j}(t)表示t时刻的基础概率,后面两个\sum是用来计算所有和节点ii,jj有关的历史事件的。Hi/jtH_{i/j}{t}对应表示节点在tt时刻的事件。γ(j/i)(t)\gamma{(j/i)^{'}(t^{'})}用来表示历史上与ii,jj相关的事件对当前事件的影响。kk依旧是核函数,这里用的是k(tt)=exp(δ(tt))k(t-t^{'})=exp(-\delta(t-t^{'}))

    再和神经网络结合一点看(或者说简化一下看),公式也可以被表示为:
    λi,j(t)=f(hit,hjt)(3) \lambda_{i,j}(t)=f(h_i^{t},h_j^{t})\tag{3} ff是一个转换函数。

  • 时序图GNN层

    在实际网路层设计里,hi/jth_{i/j}^{t}可以被表示为
    hit,l=σ(hit,l1Wselfl)+i,j,tHi(t)hit,l1Whistlki~(tt)(4) h^{t,l}_{i}=\sigma(h_i^{t,l-1}W_{self}^{l})+\sum_{i,j^{'},t^{'}\in{\mathcal{H}_i(t)}}h^{t^{'},l-1}_{i}W_{hist}^{l}\widetilde{k_i}(t-t^{'})\tag{4} 这个公式其实就是GraphSage里的聚合公式,分邻居节点和自身特征两部分,唯一的差别在于增加了一个核函数计算衰减,\sum后半段那里。还有就是这边的衰减过了一个Softmax。
    ki~(tt)=k(tt)(i,j,t)Hi(t)k(tt)(5) \widetilde{k_i}(t-t^{'})=\frac{k(t-t^{'})}{\sum_{(i,j^{''},t^{''})\in{H_i(t)}}k(t-t^{''})}\tag{5}

动态建模事件(Modeling Event Dynamic)

hit,hjth_i^{t},h_j^{t}有了,接下来就该考虑怎么计算事件的表征了。论文里用来解决第一个挑战的方法也是在这里提出的。

这边运用了元学习的思路,借鉴了HyperNetwork的方法,论文使用了学习一个先验事件的方法进行建模。

一般来说,事件的表征是这样的:
λi,j(t)=f(hit,hjt)=FCLe((hithjt)2,θe)(6) \lambda_{i,j}(t)=f(h_i^{t},h_j^{t})=FCL_e((h_i^{t}-h_{j}^{t})^{\circ{2}},\theta_e)\tag{6} 2\circ{2}表示这里用了element-wise的平方。不过关键在于参数θe\theta_e,这是一个适用于所有事件的参数。从另一个角度来说,缺少了对不同事件的个性化。

论文的思想是借用HyperNet的方法,生成这个参数(这波和阿里妈妈那篇adaptPGM的论文核心感觉类似)。

也就是说,论文是希望学到一个共性参数θe\theta_e,但在实际的FCL中使用更为个性化的参数,公式表示为:
θei,j,t=τ(θe,hithjt;θτ)(7) \theta_{e}^{i,j,t}=\tau(\theta_e,h_i^{t}||h_j^{t};\theta_\tau)\tag{7} ||表示concate,然后公式(6)就可以变成:
λi,j(t)=f(hit,hjt)=FCLe((hithjt)2,θei,j,t)(8) \lambda_{i,j}(t)=f(h_i^{t},h_j^{t})=FCL_e((h_i^{t}-h_{j}^{t})^{\circ{2}},\theta_e^{i,j,t})\tag{8} 再具体一点,θei,j,t\theta_{e}^{i,j,t}怎么来呢?还是看公式:
α(i,j,t)=σ((hithjt)Wα+bα)β(i,j,t)=σ((hithjt)Wβ+bβ)θei,j,t=τ(θe,hithjt;θτ)=(α(i,j,t)+1)θe+β(i,j,t)(9) \alpha^{(i,j,t)}=\sigma((h_i^{t}||h_j^{t})W_\alpha+b_\alpha)\\ \beta^{}(i,j,t)=\sigma((h_i^{t}||h_j^{t})W_\beta+b_\beta)\\ \theta_{e}^{i,j,t}=\tau(\theta_e,h_i^{t}||h_j^{t};\theta_\tau)=(\alpha^{(i,j,t)}+1)\odot\theta_e+\beta^{(i,j,t)}\tag{9} OK,获得这部分表征之后,下一步需要考虑的就是损失函数了。论文用了根据符合deg(v)34deg(v)^{\frac{3}{4}}PnP_n分布采样(degdeg是节点的度)负样本,再利用negative log-likelihood函数计算,公式如下:
Le(i,j,t)=Log(λi,j(t))QEKPnlog(1λi,k(t)))(10) L_e(i,j,t)=-Log(\lambda_{i,j}(t))-\mathcal{Q}\cdot\mathbb{E}_{K\sim P_n}log(1-\lambda_{i,k}(t)))\tag{10}

动态建模节点(Modeling Node Dynamic)

动态建模事件里介绍了怎么进行事件、节点的表征方法和基于Challenge 1 的Loss。论文在动态建模节点这一小节里针对Challenge 2 进行了分析处理,论文认为:

While events can be individually different, they do not occur in isolation. Particularly, links are formed to connect nodes, which means their behaviors are collectively bounded by their common nodes. Thus, we propose to govern the collective characteristics of nodes at the node level, to capture the “event tendency” of nodes (Challenge 2)—different nodes have varying tendency to form new links with others, and even the same node would manifest different tendency at different times.

简单来说,论文认为事件发生的集体特征可以通过预测节点在时间tt发生的事件总数预测。即引入了:
ΔNi^(t)=FCLN(hit;θn)(11) \Delta\hat{N_i}(t)=FCL_N(h_i^{t};\theta_n)\tag{11} 预测tt时刻节点的度,并设计了以下的损失进行学习:
Ln(i,t)={0.5(ΔNi^Δ(Ni(t))2ΔN^i(t)ΔNi(t)<1ΔN^i(t)ΔNi(t)0.5ohterwise(12) L_n(i,t)=\begin{cases} 0.5(\Delta\hat{N_i}-\Delta(N_i(t))^2& |\Delta\hat{N}_i(t)-\Delta{N_i(t)}|<1\\ |\Delta\hat{N}_i(t)-\Delta{N_i(t)}|-0.5& ohterwise \end{cases}\tag{12}

TREND

至此,TREND的所有结构都介绍完成了,最后的模型需要优化的损失函数如下:
argminΘ(i,j,t)ItrLe+η1Ln+η2(α(i,j,t)22+β(i,j,t)22)(13) arg \underset{\Theta}{min}\sum_{(i,j,t)\in{\mathcal{I}^{tr}}}L_e+\eta_1L_n+\eta_2(||\alpha^{(i,j,t)}||_{2}^{2}+||\beta^{(i,j,t)}||_{2}^{2})\tag{13}

实验结果

拍图!

动态事件建模损失

事件预测事件预测

动态节点建模

节点预测节点预测

总结

我理解里,霍克斯过程的GNN本质上和之前按时间拆分图的方法相差不大。相反两个challenge对我来说更有意思一点,Challenge对应的动态生成参数的方法之前也了解过一些,就是感觉在参数量和计算时间上会花费更大,challenge2的这种用预测t时刻连边来增加辅助loss也有点意思。

引用

[1] Laub, Patrick J., Thomas Taimre, and Philip K. Pollett. "Hawkes processes." arXiv preprint arXiv:1507.02822 (2015).