论文阅读笔记#4

论文：Node Embedding over Temporal Graphs

作者：Uriel Singer1 , Ido Guy2 and Kira Radinsky1

Basic Knowledges

Adam 优化算法

Adam相当于RMSProp+momentum，将两类方法的优势结合起来，集大成者。momentum使用了一阶梯度，RMSProp使用了二阶梯度，Adam二者均使用。是工程和研究中万金油的算法。

偏差修正：在训练的前期，梯度权值之和比较小，需要将权值之和修正为1。

一般\(\beta_1=0.9,\beta_2=0.999\)

node2vec

原文链接：https://blog.csdn.net/qq_27430269/article/details/92631472

node2vec的核心在于得到从每一个节点u出发，定长l的随机游走序列集合，进而得到每个节点的“新邻居”，然后用word2vec的思想来学习更新每一个节点的表示向量。
node2vec伪码

其他见于博客机器学习矩阵知识。

Research Questions

本文提出了一种在时序图中嵌入节点的方法。
提出了一种学习时序图节点和边随时间变化的算法，并将这种动态整合到一个时间节点嵌入框架中，用于不同的图预测任务。
提出了一个联合损失函数（a joint loss function），通过学习结合节点的历史时间嵌入来创建节点的时间嵌入，从而优化每个给定任务(例如，链接预测)。
检验结果的方法 temporal link prediction 和 multi-label node classification

Methods

Notations

Graph \(G=(V, E)\)

Edge \((u, v)_t \in E\) 时间t从u指向v

Temporal graph \(G_t = (V_t, E_t)\) \(G_{t_1}, ..., G_{t_T}\) (随时间的图快照)

Goal

文章给出了两个任务，对每个\(v \in V\)，找到一个特征向量\(f_T(v)\)最小化预测任务的损失。

节点分类任务的分类交叉熵损失：
链路预测任务的二分类损失：

算法希望通过图的静态快照学习函数s.t.，进而得到特征向量\(f_T(v)=F_t(v,G_1,...,G_t)\)，函数形式：

作者将问题由temporl embedding learning转化为一个优化问题来最小化损失函数。使用Adam来优化方程。

A,B都是在模型中不断更新的权重参数矩阵，没有什么特殊意义，文章重点讨论\(Q_t,R_t\)

\(Q_t\)是在时间t的静态节点表征矩阵，存放t时刻NE，最小化\(Q_t\) 的损失相当于优化之前静态图快照的NE，用抽样邻居节点的方法

\(R_t\)为rotation matrix ，用来作为连续时间静态嵌入的队列

Initialization using Static Node Embeddings

文章使用node2vec 来初始化\(Q_t\) ,将\(G_{t_1}, ..., G_{t_T}\) 的NE计算结果（一个\(T\times d\)的向量）作为\(Q_t\)的初始化值。由于上述的node2vec虽然最小化了节点嵌入的距离，但即使两张图是完全相同的，也不能保证嵌入的一致性，因为它们在处理时相互独立，无法保证图节点嵌入的坐标对齐。所以有了如下旋转矩阵。

Temporal Node Embedding Alignment

旋转矩阵是在乘以一个向量的时候，改变向量的方向但不改变大小的效果，并保持了手性的矩阵。手性指一个物体不能与其镜像相重合，如左手与互成镜像的右手不重合。利用了正交普鲁克问题（Orthogonal Procrustes Problem）在两矩阵间做最小二乘近似。最终对\(R_{t+1}\)计算：

Node Embedding over Time

这里主要讨论A,B和\(\sigma\)的选择以及最终优化。为了进行节点分类和链路预测的图预测任务，常常使用d-dimensional vector 作为节点，然后将其作为任何有监督的机器学习分类器的输入。

最后的优化过程是利用历史嵌入\(T\)为每个节点创建一个单一的d维表示\(X^{(v)}\)，为了减少数据，文章使用RNN和LSTM。

图示对流程进行了说明：对于节点分类任务，每个在t时刻嵌入的节点对齐后，输入到LSTM大小为d的存储单元中。LSTM的最后一个存储单元\(h_T \in \mathbb{R}^d\)表示节点的最终时间嵌入\(v^t\)，对特定任务进行优化。

对于链路预测任务，每条边\(e = (v_1,v_2)\)表示为\((v_1^t,v_2^t)\)大小为2d的向量，是它所连接的两个节点的拼接。然后被送入一个大小为d的全连接(FC)层，然后是一个softmax层。

论文阅读笔记#4