本博客是对一个图与表达学习库中涉及的模型进行讲解

表达学习库的地址为：https://github.com/thunlp/OpenNE

图的表示（输入）

edgelist

用边来表示整个图，这种表达方式更常用一些

1 2	ori_node dest_node weight_float(optional) ...

adjlist

用邻接节点表示整个图

1 2	ori_node dest_node1 dest_node2 dest_node3 dest_node4 ... ...

feature文件

用该文件可以为节点附加额外的特征

1	node feature_1 feature_2 ... feature_n

我们希望得到的

文件输出

1
2
3

num_of_nodes num_of_dims_of_representation
node_id dim1 dim2 ... dimd
...

模型输出

model = Node2vec(graph=g, path_length=80,
                 num_paths=10, dim=128,
                 p=1., q=1., window=10)
vectors = model.vectors
# output
{'1248': array([ 9.77877006e-02, ...]),
 '601': array([-0.24153167, ...]), ...}

评测

$Macro-F1=\frac{\sum_{A\in \mathcal{C}}F1(A)}{|\mathcal{C}|}$ $Pr=\frac{\sum_{A\in \mathcal{C}}TP(A)}{\sum_{A\in \mathcal{C}}(TP(A)+FP(A))},R=\frac{\sum_{A\in \mathcal{C}}TP(A)}{\sum_{A\in \mathcal{C}}(TP(A)+FN(A))}\\ Micro-F1=\frac{2*Pr*R}{Pr+R}$

Notation

符号	含义
$W$	图的邻接矩阵， $\vert V \vert \times \vert V \vert$
$Y$	图的嵌入表达， $\vert V \vert \times d$
d	嵌入表达的维数

Graph Factorization

GF的损失函数表达如下：

$J=\sum_{(i,j)\in E}(W_{ij}-Y_i{Y_j}^T)^2+\lambda\sum_{i}\|Y_i\|^2$

通过梯度下降调整嵌入表达矩阵。GF认为邻接矩阵上两点对应的值应与两点的表达向量的内积相近，同时对表达向量进行了L2正则化。

参数

参数名	作用
weight_decay	L2正则参数

Laplacian Eigenmaps

注意，这个方法仅用于无向图

这里额外用到度矩阵$D$和拉普拉斯矩阵$L$

$D=diag(d_1, d_2, ...)\\ d_i=\sum_jW_{ij}\\ L=D-W$

LE的优化函数表达如下：

$J=\sum_{i,j}\| Y_i-Y_j\|_2^2W_{ij}=tr(Y^TLY)\\ s.t. Y^TDY=I$

其中的限制条件是为了防止嵌入表达矩阵任意放缩

利用拉格朗日乘子法对目标函数求解

$f(Y)=tr(Y^TLY)+tr(\Lambda (Y^TDY-I))\\ \frac{\partial f(Y)}{\partial Y}=2LY+2DY\Lambda=0\\ \therefore LY=-DY\Lambda=\lambda DY\\ \therefore min(J)\Leftrightarrow min(tr(\lambda))$

特别的注意到

$D\cdot \bf{1}= W\cdot \bf{1}$

所以目标函数有平凡解，对应特征向量为$\bf{1}$，对应特征值为0，为了使目标函数最小而避免平凡解，故而选择特征值大于0的最小的特征值作为$\lambda$，取对应的特征向量作为最后的表达矩阵

SDNE

SDNE是一个半监督的神经网络模型，由两部分组成

论文中指出下面两个定义：

一阶近似：对于两个点而言，其邻接矩阵上对应的值为一阶近似值
二阶近似：即$W_i$与$W_j$之间的相似性

其损失函数表达如下，

$\mathcal{L}_{1st}=\sum_{i,j}W_{ij}\| Y_i-Y_j\|_2^2\\ \mathcal{L}_{2nd}=\sum_i\|(\hat{Y}_i-Y_i)\odot B_i \|_2^2\\ B=(W_{ij}\neq0)\times\beta+(W_{ij}=0)\times1,\beta>1$

特别的，在考虑$\mathcal{L}_{2nd}$的时候提到，可以想到两点之间没有连接，也就是邻接矩阵上值为0，未必就意味着两点之间没有联系，同时对于邻接矩阵为稀疏矩阵的情况下，Autoencoder更倾向于构建零矩阵，因此加入矩阵$B$

最后，总的损失函数表达如下：

$\mathcal{L}_{mix}=\mathcal{L}_{2nd}+\alpha\mathcal{L}_{1st}+\nu\mathcal{L}_{reg}$

其中最后一项为对神经网络的L2正则化

参数

参数名	作用
encoder_layer_list	autoencoder中encoder各层的神经元数，如共有2000个点，该参数为[1000, 200]，则autoencoder的网络表示为2000(input)->1000->200->1000->2000，200为最后嵌入表达的维数
alpha	一阶近似损失中用到的参数
beta	二阶近似损失中用到的参数
nu1	L1正则参数
nu2	L2正则参数

DeepWalk & Node2vec

deepwalk的步骤如下：

图
随机游走得到节点序列
利用skip gram模型得到表达

node2vec唯一的区别是在随机游走的过程中加入了两个参数，分别用于控制得到局部信息和整体信息

其中随机游走的转移概率（从点$v$到点$c$）定义如下：

$P(c_i=x|c_{i-1}=v)= \begin{cases} \frac{\pi_{vx}}{Z}& \text{if } (v,x)\in E\\ 0& \text{otherwise} \end{cases}$

其中$Z$为归一化常数

$\pi_{vx}=\alpha_{pq}(t,x)\cdot W_{vx}\\ \alpha_{pq}(t,x)= \begin{cases} \frac{1}{p}& \text{if } d_{tx}=0\\ 1& \text{if } d_{tx}=1\\ \frac{1}{q}& \text{if } d_{tx}=2\\ \end{cases},其中d为t与x之间的边数$

此外node2vec论文中还提到一些边预测和边采样的方式，详见论文。

参数

参数名	作用
dw	是否采用deepwalk，若为True，skip-gram采用层次softmax，否则采用负采样
path_length	随机游走的序列长度
num_paths	每个点随机游走的序列数
p	控制BFS随机游走的参数
q	控制DFS随机游走的参数

LINE

同样的，LINE也考虑了一阶近似和二阶近似，在一阶近似中，以预测概率和经验概率的KL散度作为损失函数

$预测概率p_{1ij}=\frac{1}{1+exp(-Y_i{Y_j}^T)}\\ 经验概率\hat{p}_{2ij}=\frac{W_{ij}}{\sum_{(i,j)\in E} W_{ij}}\\ \mathcal{L}_{1st}=-\sum_{(i,j)\in E}W_{ij}\text{ log }p_{1ij}\\$

在计算二阶近似时，LINE认为每个点应当有两个表达，一个是表达点本身，即$Y$，另一个则是作为其他点的特定context存在，这里记作$Y’$，两者都是待学习的参数，具体损失函数如下：

$预测概率p_{2}(v_j|v_i)=\frac{\text{exp}(Y_i{Y_j}'^T)}{\sum_{k=1}^{|V|}\text{exp}(Y_i{Y_k}'^T))}\\ 经验概率\hat{p}_{2}(v_j|v_i)=\frac{W_{ij}}{d_i},d_i为点i的出度\\ \mathcal{L}_{2nd}=-\sum_{(i,j)\in E}W_{ij}\text{ log }p_{2}(v_j|v_i)\\$

与node2vec类似，这里边采样也采用alias sample进行加速，并采用负采样加速训练效果

参数

参数名	作用
negative_ratio	负采样数量，默认为5，即每1个正样本对应5个负样本
order	采用一阶近似计算或是二阶近似进行计算或是两者结合，对应值1或2或3