视频链接：https://www.bilibili.com/video/BV1K5411H7EQ?from=search&seid=6556903981623125692
以下为大纲性知识点总结。

Graph基本介绍

图的表示

无向图，有向图
邻接矩阵A：无向图对称，有向图不对称

图的特性

图和子图
连通图：图内所有节点通过边连通在一起
连通分量：所有节点通过路径可以达到
最短路径：两个节点间最短路径
图直径：图中任意两节点最短路径的最大值

中心性

度：（无向图）指向某节点的边数
入度：（有向图）指向某节点的边数
出度：（有向图）从该节点出发的边数
度中心性：N/(n-1) N：度（对于有向图=入度+出度） n：图中节点数
特征向量中心性：计算邻接矩阵A的特征值和特征向量，其中最大特征值对应的特征向量表示特征向量中心性。（意义：和度强相关，当连接的节点越重要时该值越高）
中介中心性：其他节点的最短路径有多少经过该节点（中介能力）
连接中心性：（n-1)/该节点到其他节点的最短路径之和，衡量节点传播能力

网页排序算法PageRank

计算网页重要性
初始所有节点PageRank相同，
该节点PageRank值=所有指向该节点PageRank值的和（每条链接传输的PageRank值=节点PageRank值/出度），
迭代计算直到稳态。
添加阻尼系数（一般0.85，表示依概率跳转）

HITS算法

也是一个网页排序算法 Authority Hubs

networkx 库

Graph Embedding

DeepWalk

定义图，窗长，embedding维度，每个节点游走次数，游走路程长度
根据生成的随机游走序列计算SkipGram，作为每个节点embedding表示
应用于无向图

LINE

在大规模的图上，表示节点之间的结构信息；
一阶：局部的结构信息；
二阶：节点的邻居，共享邻居的节点可能是相似的。
可以应用于有向图

SDNE

structural deep network embedding
使用多个非线性层捕获节点的embedding

Node2Vec

同质性
结构等价性
基于近邻关系的建模
BFS、DFS

Struc2Vec

结构相似性的建模

Graph Network

GCN

分为谱域与空域

邻接矩阵+单位阵
D：度矩阵，用来归一化
该式的意义为：将该节点以及邻居节点的信息聚合作为该节点的embedding，训练参数W
多层GCN目的： 多次迭代聚合，增长信息流动路径

GraphSAGE

SAmple and aggreGatE 采样和聚合
归纳式的graph embedding，可以对没见过的节点生成embedding

分为采样和聚合两步。
采样即对邻居节点（有向图是指流入节点的信息）采样
聚合函数：对称的，对于输入排列不变
Mean
LSTM（节点随机打乱）
Pooling

minibatch的GraphSAGE

GAT

图注意力网络
将i，j节点信息拼起来

Complex Graph Network

Graph应用

GCN，GraphSAGE，GAT，节点的半监督学习
GraphSAGE，GAT的推理学习任务

Graph Code（github）

github.com/twjiang/graphSAGE-pytorch
github.com/tkipf/pygcn
github.com/Diego999/pyGAT

邻接矩阵需要归一化：采用加法规则时，对于度大的节点特征越来越大，对于度小的节点相反，可能会导致网络训练过程中梯度爆炸或者消失的问题

PyG：pytorch-geometric 库， 可以很方便的通过定义节点和边构建图，以及一些图网络的调用