图神经网络第3~4讲

我们想要自动抽取task-independent的特征。

目标：将图转换为d维的表示向量v。

机器学习/矩阵稀疏

原图中两个节点的相似性在映射后仍然保持

Two Key Components:

$\textrm{ENC}(v)=\textbf z_v$

$\textrm {sim}(u,v)\sim=\textbf z_v·\textbf z_u$

Shadow Encoding: An Enbedding-lookup

$\textrm{ENC}(v)=\textbf Zv$

OBJECT: $\max \textbf z_v·\textbf z_u$

如何定义相似度(Similarity)

邻居？相同的邻居？结构相似？

基于邻接矩阵的相似度[WWW’13]

直观：两点在原图有边，那么它们要尽可能接近。参数就是表示向量。

训练：SGD或矩阵分解(SVD/QR)

\[L=\sum\limits_{(u,v)\in V\times V}\Vert \textbf z_u^\top\textbf z_v - \textbf A_{uv}\Vert_2\]

问题：浅层嵌入参数多、时间复杂度高、只考虑local connectivity

随机游走(Random Walk)[KDD’14]

从u出发能到达v的概率：$P_R(v

u)$

目标：

\[\textbf z_u^\top\textbf z_v\approx P_R(v|u)\]

优势：本地和更远的邻居信息、只需要考虑随机游走上共同出现的节点对的概率

Notation:

$z_u$是$u$的嵌入

$P(v	z_u)$是预测的u随机游走到达v的概率，用Softmax和Sigmoid计算。

给定$G$，学习$f(u)=z_u$

对数似然目标函数

没有解决复杂度较高的问题

复杂一点的随机游走node2vec[KDD’16]

两个参数控制全局和局部的游走，一个控制BFS，一个控制DFS

trade off

Return p:往回走的概率

In-out q:trade off的概率

优势

表达能力强

效率高，只考虑随机的

理论

$\textbf z_u$是点u的表示向量

$P(v	\textbf z_u)$ 表示从u出发的随机游走到达v的概率，是一个计算出来的量。要求$P$是概率，由 $\textbf z_u$, $\textbf z_v$ 表示，随着它们的点乘单调递增。

\[P(v|\textbf z_u)=\frac{\exp(\textbf z_u^\top\textbf z_v)}{\sum\limits_{n\in V}\exp(\textbf z_u^\top\textbf z_n)}\]

任务是找到映射

\[f:u\rightarrow\Reals^d:f(u)=\textbf z_u\]

目标

\[\max\limits_f\sum\limits_{u\in V}\log P(N_R(u)|\textbf z_u)\]

在随机游走策略R下的u的邻居

\[L=\sum\limits_{u\in V}\sum\limits_{v\in N_R(u)}-\log P(v|\textbf z_u)=\sum\limits_{u\in V}\sum\limits_{v\in N_R(u)}-\log \frac{\exp(\textbf z_u^\top\textbf z_v)}{\sum\limits_{n=1}^k\exp(\textbf z_u^\top\textbf z_n)}\]

问题和解决

复杂度较高，是由于分母上的求和。解决方案是负采样。

在分母上只取k个点，并用sigmoid函数归一化。

一般来说，k取5-20，是一个超参数。

随机梯度下降：每次只取一部分样本进行梯度下降，

随机游走策略

node2vec[KDD’16]：结合BFS和DFS

本地信息：朝着距离起点更近的节点走的概率

全局信息：朝着距离起点更远的节点走的概率

问题

训练集没有的没有办法算

距离远的点的结构相似性

点的特征