图机器学习入门CS224W——学习记录1_基本图机器学习

课程主页

图机器学习导论

数学上图论最早起源于哥尼斯堡七桥问题。

**main question: **如何充分的利用节点之间的连接，利用关系结构进行更好地数据挖掘、数据分析？——即如何对图数据进行数据挖掘。

把图神经网络看成一个黑箱，Input为Network，Output可以为Node labels, New links, Generated graphs and subgraphs。

实现端到端表示学习representation learning ，类似CNN的automatically learn the features。就是把节点变成d维向量的过程。
所谓的端到端就是不需要人工去干涉，不需要人工去辅助，自己学到关键的特征。

课程概览

• Traditional methods:Graphlets, Graph Kernels
• Methods for node embeddings:DeepWalk, Node2Vec
• Graph Neural Networks:GCN, GraphSAGE, GAT, Theory of GNNs
• Knowledge graphs and reasoning:TransE, BetaE
• Deep generative models for graphs:GraphRNN
• Applications to Biomedicine, Science, Industry

图机器学习编程工具

• PyG
• GraphGym
• NetworkX
• SNAP.PY
• DGL：复现了很多论文

图数据可视化工具

• graphin.antv.vision
• Echarts
• graphxr

图数据库

专门用来存储索引、推理图数据的数据库。

• Neo4j
• ……

图机器学习应用

许多应用

Tasks

• node level
• edge level，例如推荐系统中
• community(subgraph) level
• graph level prediction, graph generation

Examples of Subgraph-level ML Tasks

例如导航从一个点到另一个点，可利用图来预计到达的时间。
Nodes:Road segments
Edges:Connectivity between road segments
Prediction:Time of Arrival(ETA)

图是最优质的长期资产。网络效应是一个企业最深的护城河。

几个图数据挖掘项目

• readpaper
• connected papers
• bios 医疗知识图谱
• ……

图的基本表示

本体图 Ontology

如何设计本体图，取决于将来想解决什么问题。

图的种类

• 无向图
• 有向图
• 异质图heterogeneous
  一种特殊的异质图：二分图。例如论文的作者和论文之间的关系，可以抽象成二分图。
  
  把二分图展开：Folded networks
  

节点连接数

可以用node degree表示其连接数，侧面反映一个节点的重要度。

邻接矩阵

无向图邻接矩阵为对称矩阵。主对角线为0
有向图为非对称矩阵。主对角线为0

为什么把图表示为矩阵的形式：
各种工具解决的都是矩阵运算的问题，加速的就是矩阵运算，把图表示成矩阵的形式，就是翻译成计算机能理解的。

图形数据结构可用以下表示形式：

• adjacency matrix邻接矩阵
• incidence matrix 关联矩阵
• adjacency list邻接列表

大多数的网络的邻接矩阵是稀疏的。

连接列表、邻接列表

连接列表只记录存在连接的节点对。连接表关心数据中的head和tail
邻接列表，把所有和该节点相关的都记下来。
例如：三国演义中任务关系的连接表和邻接表的示意：

其他种类的图

• 无权图
• 带权图
  例如：一个城市到另一个城市交通的可通达性也可用带权图表示。
• self-loops自环图
• multigraph多重图

图的连通性

connected graph/disconnected graph
强连通图：任意两个节点可以到达
弱连通图
强连通域，strongly connected components(SCCs)

六度空间理论：全世界任意两个人可以通过不超过六个中间人相互认识，可以跨越时间。

传统图机器学习（图特征工程）

人工设计一些特征，进行编码低维向量。
例如一个银行的风控系统，每个节点是一个用户，节点有两种特征：

• 属性特征
• 连接特征（和其他节点的连接关系）
  
  feature design:using effective features over graphs is the key to achieving good model performance。

节点层面的特征工程

给定$G=(V,E)$，学习$f:V->R$,输入某个节点的D维向量，输出该节点是某类的概率。

例如半监督节点分类问题。

对每个节点构造特征：

• node degree 连接数，可通过邻接矩阵求得
  node degree只看数量不看质量。
• node centrality 节点重要度，考虑了质量。
  不同衡量重要度的方法：
  • eigenvector centrality特征向量重要度，如果周围节点重要，该节点也是重要的。$$c_v=\frac{1}{\lambda }\sum _{u\in N(v)}{c}_u$$明显是一个递归地过程。可等价为求临界矩阵特征值和特征向量的问题。
  • betweenness centrality，衡量咽喉的位置
  • closeness centrality，衡量去哪都近
• clustering coefficient 集群系数，在ego-network中计算三角形个数
• graphlets
  GDV：graphlet degree vector，数一个节点周围预先定义好的子图模式。
  在networkx中graphlets视为atlas。

连接层面的特征工程

即通过已知连接补全未知连接。

两种：

• links missing at random，客观静态随时间不变的。
• links over time随时间变化的

link-level features:

• 基于两节点距离
• 基于两节点局部连接信息，但是存在局限，如果局部信息不足，就需要全局了。
  例如：
  • common neighbors 共同好友个数
  • jaccard’s coefficient 交并比
  • admic-adar index共同好友
• 基于两节点在全图的连接信息
  katz index：计算节点u和节点v之间长度为k的路径个数。了解这个计算过程！邻接矩阵A，则katz系数计算为邻接矩阵的k次方的第u行第v列。

$$S=\sum _{i=1}^{\infty }{\beta }^i{A}^i=(I-\beta A{)}^{-1}-I$$

全图层面的特征工程

把整张图变成一个D维的向量，特征应能反应全图的特征。

weisfeiler-lehman kernel，使用颜色微调的方法，迭代的丰富节点词库。
例如：给定的两个图，先assign initial colors，经过gggregate neighboring colors，再把每一种颜色用不同数字代替，得到hash aggregated colors。


经过k步表示捕捉了全图中k跳的连接。计算量是非常高效的。

把两张图的向量作数量积得到一个标量的方法称为kernel method，在传统图机器学习中用的很多。

NetworkX代码实战-创建图和可视化

常见的数据集

空手道俱乐部数据集

G = nx.karate_club_graph()
nx.draw(G, with_labels=True)
1
2

雨果《悲惨世界》人物关系

G = nx.les_miserables_graph()
plt.figure(figsize=(12,10))
pos = nx.spring_layout(G, seed=10) # 可设置一个布局
nx.draw(G, pos, with_labels=True)
1
2
3
4

连接表实战

数据来源：OpenKG-四大名著人物关系知识图谱和OWL本体

读取数据，利用zip创建边/连接，然后创建图：

df = pd.read_csv('triples.csv')
print(df.head())
# 构建连接
G = nx.DiGraph()
edges = [edge for edge in zip(df['head'], df['tail'])]
G.add_edges_from(edges)
G.edges('关羽')
1
2
3
4
5
6
7

节点可以为任意可哈希的对象，比如字符串、图像、XML对象，甚至另一个Graph、自定义的节点对象。

设置每个节点的坐标

import networkx as nx
import matplotlib.pyplot as plt
G = nx.Graph()
G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(1,5)
G.add_edge(2,3)
G.add_edge(3,4)
G.add_edge(4,5)
nx.draw(G, with_labels=True)
1
2
3
4
5
6
7
8
9
10

如图

设置坐标：

pos = {1:(0,0), 2:(-1,0.3), 3:(2,0.17), 4:(4,0.225), 5:(5,0.03)}
options = {
    "font_size": 36,
    "node_size": 3000,
    "node_color": "white",
    "edgecolors": "black",
    "linewidths": 5,
    "width" :5,
}
nx.draw_networkx(G, pos, **options)

ax = plt.gca()
ax.margins(0.20)
plt.axis("off")
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

如图：

NetworkX代码实战-上海地铁站点图数据挖掘

计算pagerank节点重要度

pagerank = nx.pagerank(G, alpha=0.8) # 只对有向图有效，会自动把无向图转成双向图
1

图表示学习node embeddings

自监督表示学习方法进行嵌入。

d维向量要充分的反应在原图中的结构信息等。

如何把节点映射成D维向量？

• 人工特征工程
• 图表示学习：通过随机游走构造自监督学习任务
• 矩阵分解
• 深度学习：图神经网络

研究对象：

• 节点
• 边
• 子图
• 全图

图嵌入概述

传统图机器学习需要人工进行特征工程。

表示学习：自动学习特征，将各模态转为向量。

将节点映射为d维向量，则该向量是低维的连续的稠密的，与下游任务无关的。

• 低维：向量维度远小于节点数
• 连续：每个元素都是实数
• 稠密：每个元素都不为0，分布式表示。注意区别稀疏向量/one-hot

理解嵌入d维空间，相当于把一个节点嵌入到d空间的一个点。而且d维空间向量的相似度反映了原图中节点相似度。例如下图所示：

图嵌入-基本框架：编码器-解码器

假设图G，V是节点集，A是邻接矩阵，仅利用节点连接信息，没有节点属性信息的情况。

编码器：输入节点，输出节点的向量。

解码器：假设两个节点经过编码后得到两个向量$z_u,z_v$，这两个向量的点乘数值（即余弦相似度）能够反映节点的相似度。
如果两个节点有连接，计算出来的相似度可能就是1或者向量是平行的或是同一个向量或是共线的。

可以自己定义相似：本节中我们使用random walks，即随机游走采样得到一个节点序列，如果两个节点共同出现在这个序列中，则认为这两个向量是相似的。

shallow encoding

这里的shallow encoding相对于深编码器的，
最简单就是查表，即把所有节点的d维向量写在一个矩阵里，例如下图中的$Z$，一个5维的6个节点，然后乘以$v$，$v$是一个one-hot，取出某一个节点的嵌入向量。

我们的目标是：maximize $z_v^T{z}_u$ for node pairs (u, v) that are similar。

虽然没有针对某种特定的下游任务，但是可以用于下游任务当中。

基于随机游走的方法

随机游走就是字面意思，可以自己指定随机游走的策略。

图和NLP的认知对比，加深理解：

如何计算从$u$节点出发的随机游走序列经过$v$节点的概率？——使用非线性函数，softmax。

这里判定节点相似性的定义是共同出现在同一个随机游走序列。

步骤：

• 采样得到若干随机游走序列，计算条件概率
• 迭代优化每个节点的D维向量，使得序列中共现节点向量数量积大，不共现节点向量数量积小。

Node2Vec

在deepwalk完全随机游走的基础上，增加p,q参数，实现有偏的二阶随机游走。

node2vec algorithm:

• 先计算边的权重和概率
• 以u出发计算长为l的r个序列
• SGD进行优化

也有其他随机游走的方法：LINE方法

矩阵分解角度：图嵌入和随机游走

矩阵分解，假设两个向量相似，则点积后为1，不相似则点积后为0，例如下图中$Z^T$的第二行和$Z$的第四列，如果两个相乘为1，如蓝色所示，则表明第二个节点和第四个节点是相似的（两节点相连）。

目标是：$mi{n}_z||A-Z^{T}Z||$

局限

• 无法立刻泛化到新加入的节点。
• 随机游走探索相邻局部的信息，可以使用匿名随机游走。
• 仅利用图本身的连接信息，没利用属性信息，可利用图神经网络

嵌入整张图

全图嵌入或者子图嵌入。

• 直接对所有节点嵌入求和，得到全图嵌入
• 可以引入一个虚拟节点来表示子图/图整体的嵌入，

匿名随机游走

anonymous walks：每次见到不同节点，就发一个新编号。（认号不认人）

采样出不同匿名随机游走序列的个数，可以作为全图的向量。
例如：3个节点，匿名采样序列有五种，111，112,122,123

采样多少次？
匿名随机游走长度固定时，要使误差大于$ϵ$ 的概率小于$\delta$需要采样m次，其中$$m=\lceil \frac{2}{{ϵ}^2}(log(2^n-2)-log(\delta ))\rceil$$

后面还会介绍到分层聚类。

DeepWalk 图神经网络论文精读

论文链接：DeepWalk: Online Learning of Social Representations

解决图嵌入问题，把图节点转成d维向量。后续就可以在嵌入的向量空间中进行任务，例如分类。

为什么embedding

计算机认识向量，把事物表示成向量。

了解word2vec

• CBOW
  用周围词预测中心词
• Skip-gram
  输入中心词，预测周围词

deepwoak官方ppt

图机器学习第一步就是提取特征：

• 节点
• 对
• 群

了解语言模型。

核心idea:short random walks = sentences

deepwalk步骤：

• input : Graph
  每个节点产生$\gamma$个random walk，每个序列长度为$t$，
• random walks
• representation mapping
• hierarchical softmax
• output : representation

Deepwalk论文一些了解

在线学习，把新增的节点和关系构建出随机游走序列，增量学习，迭代更新到原有模型中
可以参考B站精读。
还列出了一些参考：
deepwalk

网络数据化时期DeepWalk，随后又有了LINE、Node2Vec、NetMF、NetSMF等

GraphSAGE 使用多层聚合函数，每一层聚合函数会将节点及其邻居的信息聚合在一起得到下一层的特征向量，GraphSAGE 采用了节点的邻域信息，不依赖于全局的图结构。

代码实战：维基百科词条嵌入可视化

视频中介绍了一个自动爬虫网站。

先导入一些必要的包：

import networkx as nx

import matplotlib.pyplot as plt

import pandas as pd
import numpy as np
import random

from tqdm import tqdm # 进度条
import matplotlib.pyplot as plt
%matplotlib inline

plt.rcParams['font.sans-serif']=['SimHei']  # 用来正常显示中文标签
plt.rcParams['axes.unicode_minus']=False  # 用来正常显示负号
1
2
3
4
5
6
7
8
9
10
11
12
13
14

然后进行读入数据，查看数据数量：

# 读取数据
df = pd.read_csv('seealsology-data.tsv', sep = '\t')
print(df.head())
1
2
3

显示为：(13211,3)
然后定义生成随机游走序列的函数：

# 生成随机游走的节点序列的函数
def get_randomwalk(node, path_length):
    '''
    输入起始节点和路径长度，生成随机游走节点序列
    :param node:
    :param path_length:
    :return:
    '''
    random_walk = [node]
    for i in range(path_length - 1):
        temp = list(G.neighbors(node)) # 该节点的邻域节点列表
        temp = list(set(temp) - set(random_walk)) # 减去random中已有的
        if len(temp) ==0:
            break
        # 然后再从邻接节点中选择下一个节点
        random_node = random.choice(temp) # 随机选择一个节点
        random_walk.append(random_node)
        node = random_node
    return random_walk
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

然后查看图中节点名称，

# 查看图中节点个数
all_nodes = list(G.nodes())
all_nodes
1
2
3

以random forest节点出发，生成一个长为5的序列

# 以random forest节点为起始节点，走5步
get_randomwalk('random forest', 5)
1
2

输出为：
[‘random forest’,
‘bootstrap aggregating’,
‘out-of-bag error’,
‘cross-validation (statistics)’,
‘model selection’]

下面批量生成游走序列，

gamma =  10 # 表明每个节点作为起始节点生成随机游走序列个数
walk_length = 5 # 序列长度
random_walks = []
for n in tqdm(all_nodes): # 遍历每个节点
    for i in range(gamma):
        random_walks.append(get_randomwalk(n, walk_length))
1
2
3
4
5
6

然后建立模型进行训练

# 训练deepwalk，其实就是word2vec
from gensim.models import Word2Vec
model = Word2Vec(
    vector_size=256,# embedding维数
    window=4, # 窗口宽度
    sg = 1, # skip-gram
    hs = 0, # 不加分层softmax
    negative=10, # 负采样，
    alpha=0.03, # 初始学习率
    min_alpha=0.0007, # 最小学习率
    seed=  14
     )
# 构建词汇表
model.build_vocab(random_walks, progress_per=2)
# 训练
model.train(random_walks, total_examples=model.corpus_count, epochs=50, report_delay=1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

训练完成后返回：(16572157, 16576750)
然后就可以查看每一个节点deepwalk之后的embedding。
例如查看random forest节点，

model.wv.get_vector('random forest')
1

结果如图所示：

可以看到每一维度都是一个实数，是低维连续稠密的向量。

继续使用PCA进行降维

# 使用PCA降维，降到2维
X = model.wv.vectors
from sklearn.decomposition import PCA
pca = PCA(n_components=2)
embed_2d = pca.fit_transform(X)
embed_2d.shape
1
2
3
4
5
6

然后绘制

# 绘制
plt.figure(figsize=(14,14))
plt.scatter(embed_2d[:,0], embed_2d[:,1])
plt.show()
1
2
3
4

如图所示

举例，可视化某个词条的二维embedding

term = 'computer vision'
term_256d = model.wv[term].reshape(1,-1) # 从model中取出的是256维的
term_256d.shape
1
2
3

输出：(1,256)
再把该节点的向量映射到2维的，然后在图中表示出来

term_2d = pca.transform(term_256d)
# 映射到二维的
print(term_2d)
plt.figure(figsize=(14,14))
plt.scatter(embed_2d[:,0], embed_2d[:,1])
plt.scatter(term_2d[:,0], term_2d[:,1], c= 'r', s = 200)
plt.show()
1
2
3
4
5
6
7

如图所示：

可视化一些词条的二维embedding
如下：

# 可视化某些词条的二维
pagerank = nx.pagerank(G)
node_importance = sorted(pagerank.items(), key=lambda x:x[1], reverse=True)
# 取最高的前n个点
n = 30
terms_chosen = []
for each in node_importance[:n]:
    terms_chosen.append(each[0])
# 再手动补充一些节点
terms_chosen.extend(['computer vision','deep learning','convolutional neural network','convolution','natural-language processing','attention (machine learning)','support-vector machine','decision tree','random forest','computational imaging','machine vision','cognitive science','neuroscience','psychophysics','brain','visual cortex','visual neuroscience','cognitive model','finite difference','finite difference time domain','finite difference coefficients','finite difference methods for option pricing','iso 128','iso 10303'])
print(terms_chosen)
1
2
3
4
5
6
7
8
9
10
11

再绘制

# 得到索引
term2index = model.wv.key_to_index
plt.figure(figsize=(14,14))
plt.scatter(embed_2d[:,0], embed_2d[:,1])
for item in terms_chosen:
    idx = term2index[item]
    plt.scatter(embed_2d[idx, 0], embed_2d[idx, 1], c='r',s = 50 )
    plt.annotate(item ,xy=(embed_2d[idx,0],embed_2d[idx, 1]), c= 'k', fontsize=12)

plt.show()
1
2
3
4
5
6
7
8
9
10

如图：