Basics

• 水平对照：https://strengthlevel.com/strength-standards

Guides

• https://stronglifts.com/#guides

Basics

• 可以分为距离类、角度类、角度+距离类
  Read more »

GD&SGD&Mini-batch GD

• https://www.cnblogs.com/1024incn/p/4537177.html)
• https://developer.download.nvidia.cn/CUDA/training/StreamsAndConcurrencyWebinar.pdf
  Read more »

Background

• DeepWalk/Node2vec属于shallow encoding，有如下优缺点：
  • 需要O(|V|)的参数量，节点间的embedding不共享，每个node有独立的embedding
  • 推导式的（transductive）：training时没有的node，不会有embedding
  • 没有利用到节点的特征，只利用了graph structure
• 范式:
  • encoder生成node embedding，DeepWalk&Node2vec中为一个|V|*D的权重矩阵: $\operatorname{ENC}(v)=\mathbf{z}_{v}$
  • decoder将node embedding映射回原空间，这里存在隐式的decoder，embedding空间两向量的点积可以表示原空间u,v的相似度: $\operatorname{similarity}(u, v) \approx \mathbf{z}_{v}^{\mathrm{T}} \mathbf{z}_{u}$
    • 点积相似度：最小化两向量的模以及夹角余弦的乘积
• GNN: deep encoding
  • encoder为MLP
  • decoder为某种向量相似度

OpenResource

• OGB: The Open Graph Benchmark (OGB) is a collection of realistic, large-scale, and diverse benchmark datasets for machine learning on graphs.
• GraphGym: GraphGym is a platform for designing and evaluating Graph Neural Networks. —> 和pytorch配合
• GraphNets: 配合tensorflow

Class

• CS224W: Machine Learning with Graphs

Papers

• Tutorials and overviews:
  • Relational inductive biases and graph networks (Battaglia et al., 2018)
  • Representation learning on graphs: Methods and applications (Hamilton et al., 2017)
• Attention-based neighborhood aggregation:
  • Graph attention networks (Hoshen, 2017; Velickovic et al., 2018; Liu et al., 2018)
• Embedding entire graphs:
  • Graph neural nets with edge embeddings (Battaglia et al., 2016; Gilmer et. al., 2017)
  • Embedding entire graphs (Duvenaud et al., 2015; Dai et al., 2016; Li et al., 2018) and graph pooling (Ying et al., 2018, Zhang et al., 2018)
  • Graph generation and relational inference (You et al., 2018; Kipf et al., 2018)
  • How powerful are graph neural networks(Xu et al., 2017)
• Embedding nodes:
  • Varying neighborhood: Jumping knowledge networks (Xu et al., 2018), GeniePath (Liu et al., 2018)
  • Position-aware GNN (You et al. 2019)
• Spectral approaches to graph neural networks:
  • Spectral graph CNN & ChebNet (Bruna et al., 2015; Defferrard et al., 2016)
  • Geometric deep learning (Bronstein et al., 2017; Monti et al., 2017)
• Other GNN techniques:
  • Pre-training Graph Neural Networks (Hu et al., 2019)
  • GNNExplainer: Generating Explanations for Graph Neural Networks (Ying et al., 2019)

paper: LINE: Large-scale Information Network Embedding

Intro

• 包含一阶信息（直接相连的两节点的邻近度）和二阶信息（一对顶点的邻近度用临近节点的相似性衡量）的GE学习模型：只用到了一阶邻点
• DeepWalk/node2vec: 基于高阶相似度的GE学习模型

ppt

Semi-supervised binary node classification

• goal: 知道部分节点的label求其他节点的label
• main assumption：网络中存在的同质性。同类的node倾向于相互连接，或者聚在一起。
• framework
  • 初始化
  • 迭代
  • 收敛
• approaches
  • relational classification
  • iterative classification
  • correct & smooth
• 以节点二分类为例

PageRank

• 一个node的重要性由指向它的节点的重要性决定 —> 指向该node的节点数越多，且这些节点重要性越高，则该节点越重要。node j的重要性（传递函数）为： $$r_{j}=\sum_{i \rightarrow j} \frac{r_{i}}{d_{i}}$$ $$d_{i} \ldots out-degree of node i$$

• 矩阵形式：

  • 随机邻接矩阵M。j有$d_{j}$个出链，如果j -> i，则$M_{ij}=1/d_{j}$，因此每一列上的值要么为0，要么为$1/d_{j}$，且加和为1，称为列随机矩阵
  • rank vector r: $r_{j}$为node j的重要性score，且$\sum_{i} r_{i}=1$
  • n*1 = n*n * n*1:
    $\boldsymbol{r}=\boldsymbol{M} \cdot \boldsymbol{r}$,
  $$\quad r_{j}=\sum_{i \rightarrow j} \frac{r_{i}}{d_{i}}$$
• PageRank VS RandomWalk: 当random walk到达静态分布状态时满足$\boldsymbol{r}=\boldsymbol{M} \cdot \boldsymbol{r}$，即PageRank得到的重要性向量v是random walk的静态分布
• PangRank VS Eigenvector: PageRank得到的重要性向量v是当特征值为1时得到的主特征向量
  Read more »

Basic

• goal: 为node生成一个embedding
• 两个要素：encoder/相似度计量方法（encode前后都需要）
• framework: encoder 生成embedding —> 相似度计量方法决定embedding学习的好坏
• unsupervised/self-supervised way based on random walks
• task independent