# 【动态图表征】 TREND

## 论文信息

TREND: TempoRal Event and Node Dynamics for Graph Representation Learning

## 前言前言前言

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].

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?

## 基本概念定义

### 霍克斯过程

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.

$\lambda(t)=\mu(t)+\int_{-\infin}^{t}{k(t-s)dN(s)}\tag{1}$其中$\mu(t)$表示在t时刻的基础事件强度（我理解就是该时刻下事件发生的基础概率），$k$表示核函数，用来建模历史事件对当前事件的时间衰减。$N(s)$表示截至到t时间为止的所有事件。

## 模型模型模型

FrameWork

### 基于霍克斯过程的GNN

• 时序图上的霍克斯过程

这部分讲的是如何把霍克斯过程放到时序图上。直接看公式吧：
$\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}$对应上面的公式，$\mu_{i,j}(t)$表示t时刻的基础概率，后面两个$\sum$是用来计算所有和节点$i$,$j$有关的历史事件的。$H_{i/j}{t}$对应表示节点在$t$时刻的事件。$\gamma{(j/i)^{'}(t^{'})}$用来表示历史上与$i$,$j$相关的事件对当前事件的影响。$k$依旧是核函数，这里用的是$k(t-t^{'})=exp(-\delta(t-t^{'}))$

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

• 时序图GNN层

在实际网路层设计里，$h_{i/j}^{t}$可以被表示为
$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。
$\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）

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

$\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}$$\circ{2}$表示这里用了element-wise的平方。不过关键在于参数$\theta_e$，这是一个适用于所有事件的参数。从另一个角度来说，缺少了对不同事件的个性化。

$\theta_{e}^{i,j,t}=\tau(\theta_e,h_i^{t}||h_j^{t};\theta_\tau)\tag{7}$$||$表示concate，然后公式（6）就可以变成：
$\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}$再具体一点，$\theta_{e}^{i,j,t}$怎么来呢？还是看公式：
$\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)^{\frac{3}{4}}$$P_n$分布采样（$deg$是节点的度)负样本，再利用negative log-likelihood函数计算，公式如下：
$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）

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.

$\Delta\hat{N_i}(t)=FCL_N(h_i^{t};\theta_n)\tag{11}$预测$t$时刻节点的度，并设计了以下的损失进行学习：
$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

$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}$

## 引用

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