图神经网络

视频学习笔记：https://www.bilibili.com/video/BV1334y1571g?spm_id_from=333.337.search-card.all.click

异构图

包含不同类型节点和连接

异构图的定义：节点类别的数量加上边的类别的数量大于2

元路径(Meta-path)：是连接两个对象的复合关系，是一种广泛使用的捕获语义的结构，比如，电影——演员——电影，这样的一个连接

基于元路径的邻居(Meta-path based Neighbors)：通过Meta-path找到的邻居信息

Heterogeneous Graph Attention Network（HAN）

这个算法主要包含了两个重要的计算方式，一个是节点级别的注意力(Node-level Attention)，另一个是语义级别的注意力(Semantic-level Attention)。

节点级别的注意力：对于原本给定的图结构，按照不同的元路径的定义，将其转化成另一种不同的图。举个例子，一张图的节点只有红和蓝两种颜色，定义一种元路径为红-蓝-红，然后根据这个元路径，利用基于元路径的邻居定义转化成一张只有红色节点的图，然后在这张图上对每一个节点，计算其与邻居的注意力，然后使用softmax进行归一化，然后将每个节点加权求和作为这个节点的新的表征（这个操作和GAT基本一致，当然也支持多头注意力的使用）。将每个节点更新完整后，将这些表征拼接起来，形成这个元路径的表征。

语义级别的注意力：这里主要是使用不同元路径定义的表征进行计算。对于每一个元路径定义的表征的每一个节点表征都做一个MLP（MLP参数共享）的操作，然后进行加权求和取平均从而获得这个元路径的权重，然后将每个元路径的权重都计算完成后，使用softmax的方式归一化每一个权重，得到的新权重，就是语义级别的权重。最后对于图上每个节点的新表示，则可以使用不同元路径定义下的节点表征乘上对应的语义级别权重的求和获得。

在实际使用过程中，可能会出现节点的特征数量不一致的情况，这个在开始节点级别的注意力之前，通常都会进行一个映射的操作，使得每个节点的特征数量保持一致。

这个算法可以使用下面的图进行表示，首先在a一行中，不同颜色表示不同的元路径定义形成的图， $\alpha_{i1}^{\phi_1}$ 表示的是与目标节点在 $\phi_i$ 元数据定义中与目标 $Z_i$ 相邻的节点计算出的节点级别注意力（和GAT中的 $\alpha$ 基本一致）。然后 $\beta_{\phi_i}$ 表示语义级别的权重，最终 $Z_i$ 的新表示就是不同元路径定义下的 $Z_i$ 与对应元路径定义下的语义级别权重的加权和。

Graph Transformer Networks（GTN）

GTN能够识别原始图上未连接节点之间的有用连接，同时在端到端学习新图上的有效节点的表示。HAN通过将异构图转化为由元路径构造的齐次图来学习图表示学习，但是，这些方法由邻域专家手动选择元路径，因此可能无法捕获每个问题的所有有意义的关系，同样，元路径的选择也会显著影响性能。而GTN可以在异构图上生成任务转化图，同时以端到端的方式学习转换图上的节点表示。

这次使用ACM数据集进行说明：Paper（3025），Author(5835)，Subject(56)

$\tau^v$ 和 $\tau^e$ 分别是节点类型集合和边的类型集合，比如节点在ACM中有Paper，Author，Subject三个类，而这个图是无向图，边的类型就会有Paper->Author，Autrhor<-Paper，Paper->Subject，Subject->Paper这四个关系(由于数据集中没有Author和Subject的边，所有没有这个类型）。后面这三个类别会简写为P，A，S。

邻接矩阵：

如上图，直接把所有节点列出来，形成NxN的矩阵，然后对于边为PA(Paper->Author)类型的如图中第二个图，蓝色部分的地方是有值的，其他地方都是0

特征矩阵： $X\in\mathbf{R}^{N\times D}$ ，其中 $D$ 表示维度，在数据集中只有Paper是有特征的，那么Author和Subject的特征可以通过拼接paper的方式构建(当然，也可以求和，取最大值等等)，然后将构建好的特征拼接在一起形成特征矩阵，如下图：

GTN组合多元元路径的范式：

$meta-path=\{PAP\} = \{PA,AP\}=Adj_{PA}\times Adj_{AP}$

就是矩阵相乘的一个方式就可以构建出多元元路径，可以看到PAP之间是有一个A相连的，乘积出来的邻接矩阵才有意义，但是如果是PA和PA相乘则没有意义。

算法结构图：

$\mathbb{A}$ 是经过之前说的多元元路径构造出的多个邻接矩阵的拼接结果，然后使用 $1\times1$ 的卷积方式对A的每一层进行加权，然后得到 $\mathbb{Q}$ 这个新的矩阵，然后这些矩阵两两相乘，最终获得要输入到GCN层中的邻接矩阵，然后输出特征。这个操作的含义就是可以自动地生成元路径构造出来的图，然后在GCN中野可以利用这些图构造不同的特征信息，从而达到一个节点分类的目的。

Attributed：节点属性，用户，商品

Multiplex：用户和item之间的边可以浏览，点击，添加到购物车，购买等。

解决这种异构图的方法

HON（同构网络），忽略了节点和边的属性，结果较差
MHEN（不考虑节点性质的异构网络），结果还不错（GATNE)
AMHEM（考虑多种类型，节点性质的异构图网络），结果比MHEN好一些

GATNE: General Attributed Multiplex Heterogeneous Network Embedding

GATNE中提出了两种方法，一个是直推式的方法GATNE-T，另一种是具有推理性的方法GATNE-I。这个方法的结构图如下

首先需要将图像中的所有边都去掉，然后只针对节点生成embedding，称为base embedding，这里通常是使用MLP的方式进行生成。

在这个图中不同类型的边，表示不同场景下的影响。以红色场景为例子，接着就要将原始的图，按照不同的场景进行拆分，分别叫做红色图和蓝色图，然后分开求Edge embedding。首先是初始化红色图下每个节点的embedding，然后采用邻居聚合的思想，对每一个节点 $v_i$ 的第k阶邻居进行聚合，得到 edge embedding $u_{i,red\_type}$ ，然后在蓝色图中，再次初始化每个节点的embedding，采用相同的方式得到edge embedding $u_{i, blue\_type}$ 。接着将这两个edge embedding进行拼接得到整个红色场景下的embedding聚合 $U_i$ ，对 $U_i$ 乘上一个可学习的权重，加一个tanh激活，然后再乘一个可学习的权重 $w_r$ ，加一个softmax得到红色场景下的注意力，拆开来看的话，就是红色图和蓝色图拼接在一起的注意力 $a_{i,r}$ 。最后计算红色场景下的Edge embedding（注意大写E和小写e的区别）为 $M^T_rU_ia_{i,r}$ ，其中 $M_r^T$ 是一个红色场景下可学习的参数。现在已经有了base embedding和Edge embedding，最终得到节点 $v_i$ ，边类型为红色的节点向量可表示为 $v_{i,r} = b_i + \alpha_rM_r^TU_ia_{i,r}$ ，其中 $b_i$ 为节点i的base embedding， $\alpha_r$ 为超参数控制edge embedding的重要程度。

同样的方法，也可以得到边类型为蓝色的节点向量表示。在预测阶段主要就是走在上面的红场景和蓝场景中的一个流程，从而得到输出结果。

之前提到了GATNE有两种实现方式，两种实现方式可以用下面的公式表示

$GATNE-T:v_{i,r} = b_i+\alpha_rM^T_rU_ia_{i,r}\\ GATNE-I:v_{i,r} = h_z{x_i}+\alpha_rM_r^TU_ia_{i,r}+\beta_rD_z^Tx_i$

其中 $h_z()$ 表示计算 $x_i$ 的base embedding的一个函数，所以GATNE-I中的 $h_z(x_i)$ 与GATNE-T中的 $b_i$ 基本相等。然后在GATNE-I中主要可能面向没有见过的节点，这时候 $U_i$ 的初始化过程可能也不确定于是可以引入一个初始化函数 $g_{z,r}$ 来进行初始化，也就是说GATNE-I中的节点初始化 $g_{z,r}(x_i)$ 与GATNE-T中的 $u_{i,r}^{(0)}$ 等价。最后还引入了一个项 $\beta_rD_z^Tx_i$ ，其中 $\beta_r$ 是学习的系数 $D_z$ 也是一个 $v_i$ 对节点类型为 $z$ 的一个可学习的转化矩阵。

二部图

二部图也可以叫做二分图，其节点可以分为两类，每一类内部是没有边连接的，类与类之间是有边连接的。

显示关系：图中可以看到的边，即不同类别之间的链接情况

隐式关系：图中没有看到边，但是可以通过边的传递性(最多传递一次)进行连接，即类别之间的链接情况。

BINE: Bipartite Network Embedding

通过观察到的显式关系和未观察到的隐式关系，通过优化显式和隐式两个任务来共同学习定点的embedding向量。

显式关系建模：

分别计算边和节点的分布，对于节点 $v_i$ ， $u_j$ （表示二部图中的两个类别内的节点），有边 $w_{ij}$ ，那么显式建模出的边的分布为 $P(i,j)=\frac {w_{ij}}{\sum_{e_{ij}\in E}w_{ij}}$ 。接着计算节点的分布 $\hat{P}(i, j)=\frac{1}{1+\exp \left(-\overrightarrow{\mathbf{u}}_{i}^{T} \overrightarrow{\mathbf{v}}_{j}\right)}$ ，主要用于估计embedding中两个定点之间的局部接近度。目标函数是最小化两个分布的距离，这里采用的就是KL散度的一股计算方式

$\begin{array}{c} \text { minimize } \quad O_{1}=K L(P \| \hat{P})=\sum_{e_{i j} \in E} P(i, j) \log \left(\frac{P(i, j)}{\hat{P}(i, j)}\right) \\ \propto-\sum_{e_{i j} \in E} w_{i j} \log \hat{P}(i, j) . \end{array}$

隐式关系建模：

隐式关系主要是只类间通过传递表示的关系，对于U类的节点 $u_i,u_j$ 的隐式关系可以表示为 $w_{ij}^U=\sum_{k\in V}w_{ik}w_{jk}$ ，k是另一个类U的节点编号，这样就可以获得类间的边表示了。这种操作可以使用矩阵相乘的方式进行简化。在搞糟了两个类的隐式图之后，会在这个网络中进行随机游走（论文中的随机游走，与之前的随机游走不太一样，在这篇文章中，中心性越高的节点随机游走的次数就越多，同时并不会固定游走长度，而是随机长度），构造了相同类型定点之间的二阶接近度。然后使用skip-gram和负采样计算节点的embedding。具体建模过程如下：

最后的目标函数为

$\text{maximize }L=\alpha \log O_{2}+\beta \log O_{3}-\gamma O_{1}$

节点的显示关系更新为：

$\begin{aligned} \overrightarrow{\mathbf{u}}_{i} &=\overrightarrow{\mathbf{u}}_{i}+\lambda\left\{\gamma w_{i j}\left[1-\sigma\left(\overrightarrow{\mathbf{u}}_{i}^{T} \overrightarrow{\mathbf{v}}_{j}\right)\right] \cdot \overrightarrow{\mathbf{v}}_{j}\right\} \\ \overrightarrow{\mathbf{v}}_{j} &=\overrightarrow{\mathbf{v}}_{j}+\lambda\left\{\gamma w_{i j}\left[1-\sigma\left(\overrightarrow{\mathbf{u}}_{i}^{T} \overrightarrow{\mathbf{v}}_{j}\right)\right] \cdot \overrightarrow{\mathbf{u}}_{i}\right\} \end{aligned}$

隐式更新为

$\begin{aligned} \overrightarrow{\mathbf{u}}_{i} &=\overrightarrow{\mathbf{u}}_{i}+\lambda\left\{\sum_{z \in\left\{u_{c}\right\} \cup N_{S}^{n s}\left(u_{i}\right)} \alpha\left[I\left(z, u_{i}\right)-\sigma\left(\overrightarrow{\mathbf{u}}_{i}^{T} \overrightarrow{\boldsymbol{\theta}}_{z}\right)\right] \cdot \overrightarrow{\boldsymbol{\theta}}_{z}\right\} \\ \overrightarrow{\mathbf{v}}_{j} &=\overrightarrow{\mathbf{v}}_{j}+\lambda\left\{\sum_{z \in\left\{v_{c}\right\} \cup N_{S}^{n s}\left(v_{j}\right)} \beta\left[I\left(z, v_{j}\right)-\sigma\left(\overrightarrow{\mathbf{v}}_{j}^{T} \overrightarrow{\boldsymbol{\vartheta}}_{z}\right)\right] \cdot \overrightarrow{\boldsymbol{\vartheta}}_{z}\right\} \end{aligned}$

符号图

符号图带来的挑战主要集中在负向链接，与正向链接相比，他不仅具有不同的语义，而且原理本质上是不同的，并且他们与正向链接形成了复杂关系

符号图的定义 $\mathcal{G}=(\mathcal{u},\mathcal{E}^+,\mathcal{E}^-)$ 其中 $\mathcal{E}^+$ 和 $\mathcal{E}^-$ 分别表示正向边和负向边，并且 $\mathcal{E}^+\bigcap\mathcal{E}^-=\empty$ ，说明边要么正向要么负向

我们要解决的挑战是：

如何处理负向连接，他们的属性和正向连接完全不同
如何将正负连接组合一个模型，以更好地学习点的表征

Signed Graph Convolutional Network(SGCN)

平衡理论：将节点集分成平衡节点和非平衡节点，对于某一个中心节点，对于一阶的平衡节点集就是与中心节点使用正向边相连的的节点，非平衡节点集就是与中心节点使用负向边向量的节点。在往外括一层，即二阶平衡节点集，则再下一层中，与一阶中加入的所有节点同为正向或同为负向的节点，加入到平衡节点集中，否则，加入到非平衡节点集。

根据这个平衡理论在SGCN中，在第一层会求出每个节点的平衡特征和非平衡特征。对于平衡特征其计算方式为：将当前节点与该节点在第一层的平衡节点集中的节点特征求和取平均的结果进行拼接，然后乘一个可学习的参数，然后加个激活，获得第一层的平衡特征。对于非平衡特征，则也是类似的方式，将当前节点与该节点在第一层的非平衡节点集中的节点特征求和取平均的结果进行拼接，乘可学习参数+激活。这就完成了第一层的结果。

按照第一层的方式计算完所有节点的平衡和非平衡特征后，进行第二层的节点计算。对于平衡特征的计算，则是先计算与目标节点相邻的正向边链接的节点的第一层平衡特征的平均值，然后计算与目标节点相邻的负向边连接的节点的第一层非平衡特征的平均值，将这个两个平均值与该节点在第一层的平衡特征进行拼接，可学习权重加权，激活后得到第二层的平衡特征。对于非平衡表征也基本类似，只是对于正向边连接的时候用的是第一层的非平衡特征，负向边相连的时候用的是第一层的平衡特征，然后将两个平均值与该节点在第一层的非平衡特征进行拼接，可学习权重加权，激活得到第二层的非平衡特征。用公式可以表示为：

$\begin{array}{l} \mathbf{h}_{i}^{B(l)}=\sigma\left(\mathbf{W}^{B(l)}\left[\sum_{j \in \mathcal{N}_{i}^{+}} \frac{\mathbf{h}_{j}^{B(l-1)}}{\left|\mathcal{N}_{i}^{+}\right|}, \sum_{k \in \mathcal{N}_{i}^{-}} \frac{\mathbf{h}_{k}^{U(l-1)}}{\left|\mathcal{N}_{i}^{-}\right|}, \mathbf{h}_{i}^{B(l-1)}\right]\right)\\ \mathbf{h}_{i}^{U(l)}=\sigma\left(\mathbf{W}^{U(l)}\left[\sum_{j \in \mathcal{N}_{i}^{+}} \frac{\mathbf{h}_{j}^{U(l-1)}}{\left|\mathcal{N}_{i}^{+}\right|}, \sum_{k \in \mathcal{N}_{i}^{-}} \frac{\mathbf{h}_{k}^{B(l-1)}}{\left|\mathcal{N}_{i}^{-}\right|}, \mathbf{h}_{i}^{U(l-1)}\right]\right) \end{array}$

最后将平衡和非平衡特征尽心拼接，作为最后节点的embedding。

SiGAT

利用平衡理论和地位理论，提出了Motifs方法来提取节点邻居，并使用GAT的方法去解决邻居聚合的问题。

平衡理论：一个图中负边有偶数个，则图是平衡的，反之若负边为奇数个，则图是不平衡的。

地位理论：如果A和B有一条正向边连接，不仅意味着他们有正向关系，还意味着B的地位比A更高。反之，如果是负向边连接，意味着地位更低。

Motifs方法：首先根据平衡理论和地位理论的两个约束没去构建有向图白和无向图，2个定点和三个定点的所有可能性，并形成一个模板，每一个模板称为Motifs。如下图：

然后在SiGAT的使用过程中，对于每一个节点 $u$ ，他会使用上图所示的每一种mofifs方法去寻找邻居(即图中的节点满足motifs模板的情况就认为是这种motifs的邻居)。然后找到邻居之后再每一种motifs下使用GAT的方式聚合邻居，再加上节点本身的特征拼接起来，再经过一个分类器，最终得到节点的表示特征。

SDGNN: Learning Node Representation for Signed Directed Networks

这个方法也利用了平衡理论和地位理论，只是并不像SiGAT中使用38个motifs，而是只使用有向边的4个motifs 进行邻居筛选，聚合方式也变成可以选择的方式，可以使用GAT进行聚合，也可以使用均值的方式进行聚合。然后这样的结构可以堆叠多层。

同时提出了三种损失函数

符号边：

对于 $u,v$ 节点的边 $\mathcal{L}_{sign}(u,v)=-y_{u,v}log(\sigma(z_u^Tz_v))-(1-y_{u,v})log(1-\sigma(z_u^Tz_v))$

总的符号边损失函数为 $\mathcal{L}_{sign}=\sum_{e_{u,v}\in\mathcal{E}}$
地位理论：地位排序函数 $s(z)=sigmoid(W\cdot z+b)$ ， $s(z_u)-s(z_v)$ 表示 $u,v$ 之间的一个关系

然后可以得到一个损失函数 $\mathcal{L}_{direction}(u\rightarrow v)=(q_{uv}-(s(z_u)-s(z_v)))^2$

其中 $q_{uv} = \begin{cases} max(s(z_u)-s(z_v),\gamma),u\rightarrow v:-\\min(s(z_u)-s(z_v),-\gamma),u\rightarrow v:+\end{cases}$ ， $\gamma=0.5$

最终地位损失函数为： $\mathcal{L}_{direction}=\sum_{e_{u,v}\in\mathcal{E}}\mathcal{L}_{direction}(u\rightarrow v)$
三角关系理论：

$J_{\text {tri }} =\prod_{\Delta \in T} J_{\Delta}$

$\mathcal{L}_{\text {triangle }} =-\log J_{\text {tri }}=\sum_{\Delta \in T}-\log J_{\triangle}=\sum_{\Delta \in T} \mathcal{L}_{\triangle}$

$\mathcal{L}_{\triangle_{i, j, k}} =\mathcal{L}_{i j}+\mathcal{L}_{i k}+\mathcal{L}_{k j}$

$\mathcal{L}_{i,j}=-y_{i, j} \log \left(\sigma\left(z_{i}^{\top} z_{j}\right)\right)-\left(1-y_{i, j}\right) \log \left(1-\sigma\left(z_{i}^{\top} z_{j}\right)\right)$
最终的Loss为：

$\mathcal{L}_{\text {loss }}=\mathcal{L}_{\text {sign }}+\lambda_{1} \mathcal{L}_{\text {direction }}+\lambda_{2} \mathcal{L}_{\text {triangle }},$

动态图

动态图相对于传统的图多了一个时间维度

动态网络表示可以按照时间粒度分为四个不同的级别：

Static：不关注图中的动态信息，而将其作为一张静态图同等处理
edge weight：动态信息只是作为一张静态图的节点或者边的labels而存在
discrete：离散表示使用一组有序的图来表示动态图
continuous network：使用确切时间信息的表示形式

离散表示(Discrete Representation)： $DG=\{G^1,G^2,...,G^3\}$ ，T表示快照数（有多少个时间间隔）

连续表示(Continuous Representation)：可以分成三种表示方式

基于链接持续时间的动态网络的表示：

$EB=\{(u_i,v_i,t_i,\Delta_i);i=1,2,...\}$

$v_i,v_j$ 表示发生事件的一对节点， $t_i$ 发生事件， $\Delta_i$ 持续时间
联系序列表示（瞬时发生，没有持续时间）：

$CS=\{(u_i,v_i,t_i);i=1,2,...\}$
图流表示

$GS=\{e_1,e_2,...\}$ ，其中 $e_i=(u_i,v_i,t_i,\delta_i),\delta_i\in\{-1,1\}$ 表示消失边和出现边

链接持续时间频谱：通过不同的持续时间可以分为四种网络

Interaction networks：链接瞬时发生，发邮件
Temporal networks：边有一定的持续时间，但比较短，人与人交谈
Evolving networks：链接持续存在的时间比较长，雇佣关系
Strictly evolving networks：链接出现后就会一直出现，比如引文网络

节点动态表示：动态网络之间的另一个区别因素就是节点可能出现，也有可能消失

Static：节点数量在一段时间内保持不变
Dynamic：节点可能出现和消失
Growing networks：只可能出现节点的网络

Dynamic Self-Attention Network（DySAT）

上图为DySAT的网络的结构。首先要了解这个算法的数据是怎么构建的，数据由时间，节点和边构成，描述了什么事件生成了什么节点和边，这时候就要根据自己定义的时间间隔去分离这些数据，然后按照分离的数据构造出上图所示的这些图结构。

然后在每一个图结构中计算节点的特征，如果没有特征就用one-hot表示。在图中针对任意一个节点v，其新表示是首先是计算其所有邻居对这个节点v的attention，计算方式是将两个节点加权乘积后拼接，使用一个 $\alpha$ 系数乘积，再乘上其边权，然后激活再softmax，最后得到邻居节点作用于这个节点的注意力，然后计算出每个邻居节点的注意力后将所有邻居节点乘上一个可学习权重，再乘上对应的注意力激活后，获得目标节点的新特征 $h_v^t$ 。与GAT不同的是，多乘了一个边的权重。

在获得了每一个时刻图的新表示之后，加入一个要学习的位置embedding，然后采用self-attentioon的机制计算每个节点的emvedding。 $W_q,W_k,W_v$ 分别是self-attention中的Q,K,V的权重，对于节点embedding $X_v$ ，将这个embedding分别乘以Q和K的权重得到的两个特征，在互相乘积使用一个缩放因子，然后考虑到当前图的时间，只作用之前的embedding，所以当前图的后面的图的就不用考虑，最后得到一个时间段 $X_v$ 的权重 $e_v^{ij}$ ，然后对这个表示使用softmax，得到QK计算出的注意力 $\beta_v^{ij}$ ，在使用V权重与 $X_v$ 相乘，再与 $\beta_v^{ij}$ 的拼接结果 $\beta_v$ 相乘，得到最终的节点表示 $Z_v$

EvolveGCN：Evolving Graph Convolutional Networks for Dynamic Graphs

其核心公式主要有三个：

$function [H_t^{(l+1)},W_t^{(l)}] = \text{EGCU-O}(A_t,H_t^{(l)},W_{t-1}^{(l)})\\ W_t^{(l)} = LSTM(W_{t-1}^{(l)})\\ H_t^{(l+1)} = GCONV(A_t,H_t^{(l)},W_t^{(l)})$

从这个结果中，从l层计算出l+1层的结果，首先是使用LSTM利用上一时刻 $t-1$ 同一层的权重 $W_{t-1}^{(l)}$ 作为输入，生成当前时刻 $t$ 的新的权重 $W_t^{(l)}$ 。然后将当前时刻的邻接矩阵 $A_t$ 和这一层当前时刻的节点特征 $H_t^{l}$ ，以及更新后的权重 $W_t^{(l)}$ 输入到图卷积中，计算下一层，当前时刻的特征 $H_t^{(l+1)}$

EvolveGCN-O就是上面三个公式描述的方法，对于EvolveGCN-H，他与EvolvGCN-O不同的地方在于，他除了使用权重对下一个权重进行更新外，还添加了当前时刻当前层的特征作为更新下一时刻权重的依据。用公式可以表示为：

$function [H_t^{(l+1)},W_t^{(l)}] = \text{PEGCU-H}(A_t,H_t^{(l)},W_{t-1}^{(l)})\\ W_t^{(l)} = GRU(H_t^{(l)},W_{t-1}^{(l)})\\ H_t^{(l+1)} = GCONV(A_t,H_t^{(l)},W_t^{(l)})$

两种方式的选择标准：

如果节点又信息，-H效果要好，因为考虑了节点的特征变化
如果节点信息比较少，-O效果好，因为他更新关系图结构的变化

Streaming Graph Neural Networks

主要解决的问题是：新的交互发生时，如何不断更新图网络的信息

当有新的节点交互产生时，应该更新交互的两个节点的特征，这个过程叫做更新组件。更新后的节点对其邻居也会产生一定的影响，也需要进行一定的更新，这个过程叫做传播组件。

更新组件

在某一时刻发生了source->target的一个交互（图中对应t7时刻v2->v5），在图中，v2是source，v5是target，所以v2只会更新source和节点特征，v5只会更新target和节点特征。 $u_{v2}(t_7-)$ 表示的是 $t_7$ 时刻之前 $v_2$ 节点的特征。在interact unit中，对两个节点的特征 $u$ 分别加权乘积加偏置激活得到交互信息 $e(t_7)$ ，然后分别计算出时间间隔 $\Delta_{t_s}$ 和 $\Delta_{t_g}$ 。

接着在update unite中分别使用S-Update和G-Update的操作更新target节点和source节点对应的特征。这两个更新操作的结构相同，但是参数不同。以S-Update为例，他的输入分别是 $C_{v2}^s(t_7-),h_{v_2}^S(t_7-),e(t_7),\Delta_{t_S}$ 。其内部主要是一个LSTM结构，主要计算过程如下图所示：

接着在merge util中，对于source节点则是使用更新后的source特征和之前的target特征进行加权求和加偏置更新source节点的特征（这里的target特征使用的是t时刻之前的，是因为，在前面提到的source节点只更新source特征，target特征是不更新的）。同理target节点则是使用更新后的target特征和之前的source特征进行加权求和加偏置对target节点的特征进更新。

传播组件

在传播组件中，选择两个交互节点当前邻居作为受影响的节点。这组件的任务就是对受影响的节点进行更新。这样设置的原因如下：

新边缘对整个图的影响通常是局部的
在将信息传播到邻居之后，一旦受以你选哪个的节点与其他节点发生交互，信息将进一步传播
当传播更多的受影响点时，性能不会显著提高，甚至会降低，因为在传播过程中可能引入噪声。

在这个组件中，受影响节点如果是起始节点连接到交互的source节点时，那么这个节点叫做source节点影响邻居的source节点，同理，如果是终点就是source节点影响邻居的target节点。组件的结构图可以用下面的图表示：

在prop unit中， $C_{v_x}^S(t-)$ 表示的是受影响节点在t时刻之前的source特征，然后 $g(\Delta_t^s)$ 和之前一样，是控制时间间隔的一股函数， $\hat{W}_s^s$ 是可学习的权重， $e(t)$ 是interact unite输出的交互特征， $h(\Delta_t^s)=\begin{cases}1,\Delta_t^s\leq\tau\\0,otherwise\end{cases}$ ，其含义是如果时间间隔超过 $\tau$ 就忽略他对受影响节点的影响。 $f_a(u_{v_x}(t-),u_{v_s}(t-))=\frac {exp(u_{v_x}(t-)^Tu_{v_s}(t-))}{\sum_{v\in N^s(v_s)}exp(u_v(t-)^T)u_{v_s}(t-)}$

Temporal Graph Attention Network（TGAT）

TGAT与GAT相似，都是通过attention的方式去聚合节点的特征，此外，还考虑了节点的时间特征。对于一个节点的新特征 $Z$ ，其在t时刻的计算公式为：

$Z(t) = [\widetilde{h}_0^{l-1}(t)||\Phi_{dr}(t-t),\widetilde{h}_1^{l-1}(t_1)||\Phi_{dr}(t-t_1),...,\widetilde{h}_N^{l-1}(t_N)||\Phi_{dr}(t-t_N)]^T$

$\widetilde{h}_0^{l-1}(t)$ 是指节点0在上一层中时间为t的特征，然后 $t-t_N$ 表示的是一个时间差， $\Phi_d(t)=[cos(w_1t+\theta_1),cos(w_2t+\theta_2),...,cos(w_dt+\theta_d)]$ 。除了第一个部分是节点本身，其他都是其邻居节点在上一层对应时刻的特征。

具体流程如下：

之前提到的特征Z对应图中橙色堆叠的部分，然后从图中可以看出，他是使用了一个多头的注意力进行计算（图中使用了3个头），在self-attention中有K，Q，V三个部分你，首选取出Z中的第0个特征（即目标节点加上时间特征的新表示）乘以Q的权重做为向量q，然后其邻居都乘上K的权重得到向量k，v则是其邻居都乘上V的权重，得到向量v。attention计算公式和图中一样。最后生成的头则是经过将这些头拼接起来，乘以一个权重+偏置+激活，再乘权重+偏置。

超图

超图是一种广义的关系结构，一个超边可以拥有任意数量的节点(>1)，如果所有超编都链接两个节点那么超图就退化为简单图。

超图的定义 $\mathcal{G} = (\mathcal{V},\mathcal{E},\mathbf{W})$ ，其中 $\mathcal{V}$ 是节点集合， $\mathcal{E}$ 是超边集合， $\mathbf{W}$ 是每个超边被赋予的权值。

超边的构建：

Hypergraph Neural Network（HGNN）

将GNN计算拓展到超图上，具体流程是图找培根能的公式10，加一个激活函数

Dynamic Hypergraph Neural Networks(DHGNN)

DHGNN的主要贡献是实现了GNN不同层之间动态地调整整层中的超图结构。

DHGNN主要有两个部分构成，一个是动态超图构建(DHG)，另一个是超图卷积(HGC)，算法总体结构如下图：

动态超图构建：主要使用KNN和K-means两种方式

输入：输入节点embedding X，KNN的参数k，K-Means簇的个数S

输出：超图集合 $\mathcal{G}$

使用K-means聚类X成C个类别

遍历X中的每一个节点

使用KNN计算该节点最近的k个节点

然后将这几个节点组成的超边加入到超图集合G中

然后计算当前节点与C各聚类中心的距离D

对D进行排序

取出前S-1个簇

遍历这S-1个簇

将当前簇中的所有节点与当前节点组成超边，然后加如到超图集合G中

结束遍历

结束遍历

输出超图集合G