图神经网络第1~2讲
# 相关链接：Stanford CS224W
第一讲
Complex systems are all around us
应用：社交网络、知识图谱
共性：事物之间的关系
Types
node
commuication
graph
经典任务：节点分类，链路预测，图的分类，聚类
场景：结构预测、推荐系统、交通预测、天气预报(DeepMind)
How
Empirical(以经验为依据): 研究图
图论相关知识
度、二部图、邻接矩阵、自环、边的属性
真实世界的网络是稀疏的(sparse)
| $ | E | «E_{max}$ |
边的属性(Attributes)：权重(freq. of comm)，排序(best, second best)，类型(friend, relative, co-workers)，Sign
连通图(任意两点有通路)、连通分支
不连通的图的矩阵是分块的
强连通：任意两点可达
正式上课
Pipeline of Traditional ML
| User | #posts | RegT | #fans | profile | Label |
|---|---|---|---|---|---|
| User1 | 80 | 2020-01-01 | 913 | prefile1.jpg | label1 |
Design Features + Obtain Features
1 Function: $y=f(x, \theta)$
2 Loss: $L(y,\hat{y})$
3 Optim: $\theta^*=\argmin_{\theta} L$
第二讲
1. What is Entropy
衡量系统的混乱程度的量，克劳修斯的定义是$\Delta S=Q/T$
信息熵，离散随机事件的概率，越有序，越低。不相关事件X，Y，信息量相加，同时发生概率相乘，因此用对数比较合适，另有霍夫曼编码的长度。
2. Cross Entropy
P和Q是两个概率分布，趋同的时候，小，不同的时候，大。
例子
| $user1$ | $[0.1\space0.1\space0.5\space0.3]$ |
|---|---|
| $\hat {user1}$ | $[0.0\space0.0\space1.0\space0.0]$ |
用交叉熵计算两个分布之差，相同为0
3. Feature Design
手动抽取特征的方法，一般针对于无向图。
3.1 节点层面
3.1.1 节点分类：
度数，每个节点邻居同等重要。
中心性：
Eigenvector Centrality:特征向量中心性
\[c_v=\frac{1}{\lambda}\sum\limits_{u\in N(v)}c_u=\frac{1}{\lambda}\sum\limits_{u\in G}a_{v,u}c_u\]计算时容易产生递归问题，上面等价于$\lambda c=Ac$
Betweenness Centrality:
计算有多少条最短路径经过某个节点（难算，不常用）
\[c_v=\sum\limits_{s\not =v\not =t}\frac{\#(经过v的s到t最短路径)}{\#(s到t最短路径)}\]Closeness Centrality:
计算某点到其余各点的最短路径长度之和，取倒数
\[c_v=\frac{1}{\sum\limits_{v\not=u}{u到v最短路径的长度}}\]Clustering Coefficient（聚集系数）:节点朋友之间的联系
举例：做微商的人有很多邻居，但他们互不认识的多。
\(c_v=\frac{\# (v邻居之间的边)}{C_{k_v}^{2}}\) （邻居多，就容易偏小）
Graphlet Degree Vector:
聚集系数实际上就是节点$v$在几个三角形内，拓展的多边形或者其他小图的形状，有四种小图的形式。合成一个向量
SUMMARY
基于重要性的特征，对于预测影响因素较大的节点比较合适
基于结构的特征，对于预测点在图中的角色、功能比较合适
3.2 边层面
预测哪些新的边会产生，
方法：
随机移除一些边，跑模型，看一下会产生的边。
当前训练，未来测试，有时间跨度地取数据，比较准，但需要有数据集的支持。
特征：
基于距离的特征：对v点，求它到各点的最短路径，优先推荐最短距离更近的点。
Local Neighborhood Overlap:
两点邻居的交集/并集，其他数量关系，问题是如果交集为空，两点仍有可能有紧密联系。
Local Neighborhood Overlap:
补充定理：邻接矩阵的幂的意义：$v_i$到$v_j$有$n$条长度为$k$的通路$\Leftrightarrow A^k$中的$a_{ij}^{(k)}=n$
证明 由邻接矩阵定义，$k=1$时显然成立。$k>1$时，如果结论成立，设$v_i\rightarrow v_j$长度为$k$的通路数量$a_{ij}^{(k)}=n_m$，要计算的是$v_i\rightarrow v_l$长度为$k+1$的通路数量$a_{il}^{(k+1)}$.那么：如果$v_j$经过1步就到达$v_l$，即$a_{jl}^{(1)}=1$，那么经过$v_j$的长度为$k+1$的通路就也有$n_m$条；如果$a_{jl}^{(1)}=0$，那么就不存在经过$v_j$的长度为$k+1$的通路。其中，$v_j$在图中可以是任意的，也就是说，$v_i\rightarrow v_l$的通路总数量，就是经过任意一点$v_j$的通路数量之和。有：
$a_{il}^{(k+1)}=a_{i1}^{(k)}a_{1l}^{(1)}+a_{i2}^{(k)}a_{2l}^{(1)}+…+a_{in}^{(k)}a_{nl}^{(1)}$
转换为向量形式，有： $a_{il}^{(k+1)}= \begin{bmatrix} a_{i1}^{(k)} & a_{i2}^{(k)} & … & a_{in}^{(k)}
\end{bmatrix} \begin{bmatrix} a_{1l}^{(1)}
a_{2l}^{(1)}
…
a_{nl}^{(1)} \end{bmatrix} $将式子左边扩展为列向量：
$ \begin{bmatrix} a_{1l}^{(k+1)}
a_{2l}^{(k+1)}
…
a_{nl}^{(k+1)} \end{bmatrix} =A^{k} \begin{bmatrix} a_{1l}^{(1)}
a_{2l}^{(1)}
…
a_{nl}^{(1)} \end{bmatrix} $再将列向量拼接起来，有$A^{k+1}=A^k A$