前言

以下按照 CS224w\text{CS224w} 顺序进行，显然，其中肯定会穿插一些作者认为的应该具有的基础芝士（不过本人才大一，说不定听课的都掌握了）

但是我科技树乱点的，所以中途可能会学很多前置芝士。

ToDoList

目录 待办
核方法 还没学，在2.2.3
神经网络那个函数 在2.2.4
第二章剩下的内容 让我咕一下
N-gram 平滑化 还没学

1 概念

这一章并没有讲什么东西，但是我们依然可以学习以下内容

一些任务类型

包括 Graph-level，Node-level,Community(Subgraph)-level,Edge-level

实例

Node classification

Predict a property of a node

Example: Categorize online users / items

Predict whether there are missing links between two nodes

Example: Knowledge graph completion

Graph classification

Categorize different graphs

Example: Molecule property prediction

Clustering

Detect if nodes form a community

Example: Social circle detection

Other tasks

Graph generation: Drug discovery

Graph evolution: Physical simulation

应用

Node-level

Protein Folding -AlphaFold

Edge-level

1.推荐物品

任务：根据用户的浏览商品的行为推荐推荐产品。

此时就有一个新名词，embed，点嵌入，构造一个函数 d(c,x)d(c,x) ,假设我们用户访问的集是c，相关的是 x1x_1 不相关的是 x2x_2 那么需要有 d(c,x1)<d(c,x2)d(c,x_1)<d(c,x_2)

我能做到的实现是

1
2
3
4
5
6
1.把所有产品看作一个点
2.如果用户浏览，寻找这个点相关性大于一个阈值 k 的点是否被用户访问过，如果访问过，就放在一个并查集里面。
3.如果一个并查集大小大于 t ，可以找到其他点中与并查集的一些点相关性大于k的点的个数大于另外阈值 q 的，我们现在假定用户也喜欢这个，推荐给用户

很显然的，最后的所有点都在一个并查集上面，但是只要 k 够大，并且放弃用于过早的访问历史，即可实现这个推荐系统，不过写这个的时候我才看完第二章，可能有更好的实现。

2.药物关系预测

任务 Given a pair of drugs predict adverse side effects

把所有药物和蛋白质堪称一个节点，边表示影响。

由于是第一节，所以并没有说很细致的，萌新也没什么想法

3.交通路径预测

很基础的一个模型了，相信不需要介绍什么

Graph-level

1.药物预测

显然，药物的化学式是一张图。

有两个方向的应用，预测有用的药物（Generate novel molecules with high Drug likeness value）以及优化现有的药物（Optimize existing molecules to have desirable properties）

模拟例子

把例子看成点，根据每个点当前的惯性，边看成相互影响的关系，如果连接说明有影响，然后每次更具当前的惯性以及相互影响的关系来确定下一时刻下一张图的连通性

网络的构成

NN 顶点，代表物体
EE 边，代表影响
G(N,E)G(N,E) 图，代表系统

这些意义都是你自己定义的，你想怎么定义都可以，但是一般来说是需要符合现实的

混合图

G=(V,E,R,T)G=(V,E,R,T) 分别表示点，边，边的类型，点的类型

平均度 kˉ=⟨k⟩=1Na˚i=1Nki=EN\bar{k}=\left\langle k \right\rangle =\frac{1}{N} \aa_{i=1}^{N}k_i=\frac{E}{N}

这个是无向图度-和公式，但是中间两步搞不懂

对于有向图 kin‾=kout‾=EN\overline{k^{in}}=\overline{k^{out}}=\frac{E}{N}

二分图

应用的类型，这个除了直观的

1
2
3
4
Authors-to-Papers (they authored)
Actors-to-Movies (they appeared in)
Users-to-Movies (they rated)
Recipes-to-Ingredients (they contain)

还有很多很毒瘤的，看不出来的东西。

邻接矩阵表示

我不相信图论都没学就开224w

强连通分量

强连通分量中的所有的点两两可达。

2 传统图上机器学习方法

传统方法

Random forest

随机森林回归，即为随机决策森林，决策树的森林。大量决策树做出的预测更准确。

不过既然是传统方法，说明理解个大概就可以了。

还要注意这是个 supervised learning\text{supervised learning}

SVM

支持向量机 Support Vector Machine

是一种二分类模型，定义是在特征空间上的间隔最大的分类器（例如把找到一条斜线，这条斜线就是分类器，间隔就是两边点集到直线的最小值之和）

核技巧

给定两个向量 x1,2x_1,_2，计算内积 I=<x1,x2>I=<x_1,x_2>

假设现在通过某种非线性变化，把他们映射到了一个高维空间 Φ:x→ϕ(x)\Phi : x\to \phi(x)

如果我们求 I′=<ϕ(x1),ϕ(x2)>I'=<\phi(x_1),\phi(x_2)> 如果映射了再弄，复杂度就很高。 而让 I′I' 能用 x1,x2x_1,x_2 计算的方法，就是核技巧

但是才疏学浅，这里之后在写

netural network

定义感知器： 入度不唯一并且出度为一的点。

定义输出 output={0if∑jwjxj≤thresold1if∑jwjxj≥thresold\text{output}=\begin{cases}0 & if \sum_{j}\limits w_j x_j \leq \text{thresold} \\ 1 & if \sum_{j}\limits w_j x_j \geq \text{thresold}\end{cases}

thresold 是临界点。

aws 给出了一个图片，注意到虽然感受器只有一个输出，但是可以传给多个神经元

我们定义 b=−thresoldb=-\text{thresold} 并且定义 x=<x1,x2,x3x3>,w=(w1,w2,w3)x=\left<x_1,x_2,x_3x_3\right>,w=(w_1,w_2,w_3)

那么就有 output={0ifx∗w+b≤01ifx∗w+b≥1\text{output}=\begin{cases}0 & if x*w+b \leq 0 \\ 1 & if x*w+b \geq 1\end{cases}

我们更希望感知器输出具有连续性，那么我们可以有

t=11+e−(x∗w+b)t=\frac{1}{1+e^{-(x*w+b)}}

tt 满足与 Δw\Delta w 和 Δb\Delta b 之间满足线性关系，并且变化率是偏导数。

没学明白，后头看看更不更新NN

图上机器学习

点级别

点的中心性 NodeCentrality

1
2
3
eigenvector 特征向量
betweenness 中心性
closeness 密度

中心性定义 cv=1λ∑u∈N(v)cuc_v=\frac{1}{\lambda}\sum_{u\in N(v)}\limits c_u

这是一个 recursive 定义 ，也就是递归定义

显然的，我们有 λc=Ac\lambda c=Ac ， AA 是图的矩阵，如果 u,vu,v 联通 ，那么 Au,v=1A_{u,v}=1

那么就有，AA 是 cc 的特征向量

中心性 cv=#(任意s,t中经过c的最短路之和)任意s,t的最短路之和,s≠v≠tc_v=\frac{\#(任意s,t中经过c的最短路之和)}{任意s,t的最短路之和},s\neq v \neq t

密度 cv=1任意s,v最短路之和，s≠vc_v=\frac{1}{任意s,v最短路之和}，s \neq v

softmax,sigmoid

Softmax:   σ(z)[i]=ez[i]∑j=1kez[j]\text{Softmax:} ~~~\sigma(z)[i]=\frac{e^{z[i]}}{\sum_{j=1}^{k}\limits e^{z[j]}}

Sigmoid:   S(x)=11+e−x\text{Sigmoid:} ~~~S(x)=\frac{1}{1+e^{-x}}

3

编码，解码

把一个节点映射到高维空间，就是编码器

计算两个低维向量的相似性，就叫做解码器（感觉翻译有问题？）

node embedding ，就是先编码，然后解码，并且定义原图中的节点的相似度，优化编码器参数使得后面两者尽可能一致。

比如有一种编码器是嵌入查找

ENC(v)=zv=Z∗vENC(v)=z_v=Z*v ，ZZ 为嵌入向量表 ，这种行为叫做嵌入查找，也就是embedding-lookup

点嵌入 Node Embedding

我们假设一个映射函数 ϕ(x)\phi(x) ，现在我们让 uu 的映射成为 dd 维空间中 zu=ϕ(u)∈Rdz_u=\phi(u)\in R^{d}

现在我们定义一个相似度s(u,v)s(u,v) 使得 zuTzv≈s(u,v)z_u^{T}z_v \approx s(u,v)

似然函数

定义模型参数 θ\theta ，假设是抛硬币，求解两次都是正面向上的概率

定义一个似然函数 L(θ∣HH)=θ2L(\theta|HH)= \theta ^2

我们如果要最大化， arg max⁡θ=θ2,whereθ∈[0,1]\argmax_{\theta}\limits=\theta ^2,\text{where} \theta\in[0,1]

区分概率函数以及似然函数，就是看 P(x∣θ)P(x|\theta) 当 xx 已知，就是似然函数，否则为概率函数。

随机游走函数

我们可以用随机游走定义 s(u,v)s(u,v)

通过这个似然函数 max⁡ϕ∑u∈Vlog⁡(P(Du∣zu))\max_{\phi}\sum{u \in V}\log(P(D_u|z_u))

DuD_u 表示从节点 uu 出发，经过一定步长的行走得到的节点记录

min⁡L=∑u∈V∑v∈Du−log⁡(P(v∣zu))\min L=\sum_{u\in V}\limits \sum_{v\in D_u}\limits-\log(P(v|z_u))

显然的，我们可以利用 softmax 函数

P(v∣zu)=ezuTzv∑n∈VezuTzvP(v|z_u)=\frac{e^{ z_u^T z_v}}{\sum_{n\in V}\limits e^{ z_u^T z_v} }

然而计算是 O(V2)O(V^2) 的，所以我们需要优化，这个优化可以是Negative Sampling 即负采样

Word2vec

这个有点长了，慢慢看，反正右边有目录，具备这个前置芝士的可以跳了。

统计语言模型

p(W)=p(w1,w2,...,wT)p(W)=p(w_1,w_2,...,w_T)

链式分解后

P(W)=p(w1)p(w2∣w1)p(w3∣w2,w1)...p(wT∣w1,w2,...,wT−1)P(W)=p(w_1)p(w_2|w_1)p(w_3|w_2,w_1)...p(w_T|w_1,w_2,...,w_{T-1})

利用 Bayes 公式

p(wk∣w1,w2,...,wk)=p(w1,w2,...wk)p(w1,w2,...,wk−1)p(w_k|w_1,w_2,...,w_k)=\frac{p(w_1,w_2,...w_k)}{p(w_1,w_2,...,w_{k-1})}

显然，这个计算是指数级的，所以我们需要优化或者用一个近似计算，有一种近似计算就是 N-gram\text{N-gram} 模型

否则，我们这样计算

设目标函数 ∏w∈Cp(w∣Context(w))\prod_{w \in C} p(w|\text{Context}(w))

Corpus 表示语料，Context 表示上下文，即周边词集的集合。

我们利用最大对数似然，把目标函数设为

L=∑w∈Clog⁡p(w∣Context(w))L=\sum_{w\in C} \limits \log p(w|\text{Context}(w))

p(w∣Context(w))=F(w,Context(w),θ)p(w|\text{Context}(w)) = F(w,\text{Context}(w),\theta)

仅需要优化参数集 θ\theta 即可，可以选择合适模型使得 θ\theta 个数远小于 N-gram 参数个数

N-gram 模型

根据大数定理，就是当语料库足够大，概率 ≈\approx 频率

P(wk∣w1,w2,...,wk)≈fcount(w1,w2,...wk)count(w1,w2,...,wk−1)P(w_k|w_1,w_2,...,w_k) \approx f\frac{\text{count}(w_1,w_2,...w_k)}{\text{count}(w_1,w_2,...,w_{k-1})}

一般来说参数如下

n 模型参数数量
1 2e52e5
2 4e104e10
3 8e158e15
4 1.6e211.6e21

可见是指数增长，实际上一般采用三元模型

平滑化

N-gram 还有一个平滑化的环节

如果 count(w1,...wk−1)=0\text{count}(w_1,...w_{k-1})=0 是否能认为 p(w1,...wk)=0p(w_1,...w_{k})=0 ?

如果 count(w1,...wk−1)=count(w1,...wk)\text{count}(w_1,...w_{k-1})=\text{count}(w_1,...w_{k}) 能否认为 p(w1,...wk)=1p(w_1,...w_{k})=1 ?

还没看到讲这方面的，先咕咕

神经概率语言模型

指定一个固定长度的实值向量，使得v(w)∈Rmv(w)\in\mathbb{R}^m

计算一个词的词向量，yw=(yw,1,ww,2,...,yw,n)Ty_w=(y_{w,1},w_{w,2},...,y_{w,n})^T

然后使用 softmax归一化

p(w∣Context(w))=eyw,iw∑i=1meyw,ip(w|\text{Context}(w))=\frac{e^{y_{w,{i_w}}}}{\sum_{i=1}^{m}\limits e^{y_{w,i}}}

其中，iwi_w 表示 ww 在词典 DD 的索引

这里需要提前初始化一个 word embedding 矩阵，每一行表示一个单词向量，单词向量也是训练参数，每次训练需要更新。

一般来说，都是用级数近似指数，

参考

负采样

每次仅改变一小部分的权重。

优化随机游走函数计算

P(v∣zu)=ezuTzv∑n∈VezuTzvP(v|z_u)=\frac{e^{ z_{u}^{T} z_v}}{\sum_{n\in V}\limits e^{ z_u^T z_v} }

我们可以估计似然函数 min⁡L=∑u∈V∑v∈Du−(log⁡(σ(zuTzv))+∑i=1klog⁡(σ(zuTzni)))ni∼PV\min L=\sum_{u \in V}\limits \sum_{v\in{D_u}}\limits -(\log(\sigma(z_{u}^{T} z_v))+\sum_{i=1}^{k}\limits \log(\sigma(z_{u}^{T} z_{n_i}))) n_i \sim P_V

优化这个函数，可以使用梯度下降

梯度下降

  1. 随机化所有 zuz_u

  2. 计算梯度 ∂L∂zu\frac{\partial L}{\partial z_u}

  3. 更新映射 $ z_u \leftarrow z_u - \eta \frac{\partial L}{\partial z_u}$

  4. 循环，直到 zuz_u 收敛

随机梯度下降

  1. 随机化所有 zuz_u

  2. 计算 Lu=∑v∈Du−log⁡(σ(zuTzv))+∑i=1klog⁡(σ(−zuTzni)))ni∼PV,L^u=\sum_{v \in D_u}\limits{-\log(\sigma(z_u^T z_v))+\sum_{i=1}^{k}\limits \log(\sigma(-z_u^T z_{n_i}))) n_i \sim P_V ,}

  3. 计算梯度 ∂L(u)∂zu\frac{\partial L^{(u)}}{\partial z_u}

  4. 更新映射 zu←zu−η∂L(u)∂zuz_u \leftarrow z_u - \eta \frac{\partial L^{(u)} }{ \partial z_u }

  5. 循环，直到 zuz_u 收敛

随机游走

node2vec 是 dfs 和 bfs 的折中

walk(u,v) 定义是这次走的是 uu ，并且上次是 vv

我们假设现在有三种点 a,b,ca,b,c

其中 dis(v,b)=dis(u,v)\text{dis}(v,b)=\text{dis}(u,v) ,s(v,a)<dis(u,v)\text{s}(v,a)<\text{dis}(u,v),dis(v,c)>dis(u,v)\text{dis}(v,c)>\text{dis}(u,v)

我们引入两个超参数 p,qp,q

然后到 a,b,ca,b,c 的概率设置成为 1p,1,1q\frac{1}{p},1,\frac{1}{q}

图嵌入

即使你拥有钞能力，但是也没法承受一个超大的矩阵存储或者计算。

DeepWalk

um2

Super Node

Anonymous Walk Embeddings