GraRep

GraRep: Learning Graph Representations with Global Structural Information

I. 前言

GraRep 主要用于图节点表示，特点是可以学习图的全局信息。

GraRep的作者认为，$skip-gram$ 模型通过获取每个节点与其 $k$ 阶邻节点之间关系，其缺点是将 $k$ 阶的关系信息转化到一个固定、普通的子空间（common subspace），因为 $k$ 阶是 $k$ 固定的。

$LINE$ 定义的损失函数可以同时获取 $1$ 阶 和 $2$ 阶的邻域信息，$LINE$ 实现了学习局部的非线性复杂关系，但是 $LINE$ 不能高效处理大于 $k$ 阶 (大于2阶)的邻域信息。

作者认为不同节点应该对应不同 $k$ 阶邻域，并通过该策略可以实现图的全局信息表示。

II. 模型

2.1、模型定义

GraRep除了定义了邻接矩阵 $S$, 度矩阵 $D$，还定义了转移矩阵 $A$。

$$A=D^{-1} A$$

从定义中可以看出，图的转移矩阵其实是邻接矩阵的归一化(re-scale)。

图中每个节点采用 $d$ 维的向量表示，全部节点组成的向量组用矩阵表示为 $W\in Rˆ{|V| \times d}$。

2.2、损失函数

GraRep 利用转移矩阵 $A$ 来定义条件概率，因此两个节点 $w$ 与 $c$ 之间的存在通路的条件概率 $p_k(c|w)$ 如下：

$$p_k(c|w) = A^{k}_{w,c}$$

值得注意的是，$ A^{k}_{w,c}$ 为矩阵 $A^{k}$ 的第 $w$ 行，第 $c$ 列的值。因此，只需要同时计算出不同阶的 $A^k, k=1,2,…,N$, 便可以得到各个点之间的不同阶之间的转移概率。

作者参考 $skip-gram$ 的思想，并引入噪声对比估计(NCE)策略，提出如下的损失函数：

$$L_k=\sum_{w\in V} L_k(w) \\ L_{k}(w,c)=(\sum_{c\in V}p_{k}(c|w)log \delta (w .c))+ \lambda E_{c^{'}~p_k(V)}[log \delta(-w. c^{'})]\\ =(\sum_{c\in V}p_{k}(c|w)log \delta (w .c))+ \lambda \sum _{c \in V}p_k(c)[log \delta(-w. c)] \\ p_k(c) = \frac{1}{N}\sum_{w^{'} \in (V not c )} A^k_{w^{'},c}$$

其中，$\delta$ 为 $sigmod$ 函数，$\lambda$ 为超参。 $w.c$ 是两个 $d$ 维向量的点积，因此是计算两个节点的嵌入向量的相似度。$N$ 为图中边的数量。

即 该损失函数的第一项是 两个节点 $w,c$ 的相似度通过 $sigmod$ 函数进行归一化并引入非线性能力，然后与从 $w$ 到 $c$ 之间条件转移概率相乘，目的是衡量两个节点之间存在通路的概率。如果两个节点的相似度比较大，同时转移概率也很大，那么大概率这两个节点之间存在通路。

损失函数的第二项是求期望，是求 $w$ 与除 $c$ 点之外的其他点的相似度与其之间转移概率相乘后的期望，目的是希望只有 $w$ 与 $c$ 点足够相似，而 $w$ 与 其他点具有足够的差异。

III.优化

由于损失函数中包含两个变量，即两个不同的顶点。对于双变量函数的损失函数，GraRep的根据两个顶点之间的相似度出发，将双变量转化为单变量进行优化。

定义两个顶点 $w$ 与 $c$ 之间的相似度为 $e=w.c$ 。因此根据 《求导》可以得到：

$$<Empty \space Math \space Block>$$

因此可以看到，当达到极值的时候，此时的相似度为式4，此时损失函数最小。

从矩阵的角度重新审视：

$$<Empty \space Math \space Block>$$

显然，$Y$ 定义的是图中顶点之间两两的相似度。

进一步，由于相似度为负，基本没有意义。因此文中对 $Y_{i,j}^k$ 与0进行比较，取最大值，保证只考虑的相似度大于0的两两节点。