《图机器学习》-Machine Learning for Graphs
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
Machine Learning for Graphs
一、Application of Graph ML
图机器学习的任务可以分为四个类型
- N o d e l e v e l Node\ level Node level(结点级别)
- E d g e l e v e l Edge\ level Edge level(边级别)
- C o m m u n i t y ( s u b g r a p h ) l e v e l Community(subgraph)\ level Community(subgraph) level(社区/子图级别)
- G r a p h l e v e l p r e d i c t i o n , G r a p h g e n e r a t i o n Graph\ level\ prediction,Graph\ generation Graph level prediction,Graph generation(图级别,图生成)
典型的图机器学习任务有
-
N
o
d
e
c
l
a
s
s
i
f
i
c
a
t
i
o
n
Node\ classification
Node classification:(结点分类)
主要做的是预测结点的属性- 应用实例对在线用户/项目进行分类
-
L
i
n
k
p
r
e
d
i
c
t
i
o
n
Link\ prediction
Link prediction:(链接预测)
主要做的是预测两个节点之间是否缺少链接- 应用实例 K n o w l e d g e g r a p h c o m p l e t i o n Knowledge\ graph\ completion Knowledge graph completion
-
G
r
a
p
h
c
l
a
s
s
i
f
i
c
a
t
i
o
n
Graph\ classification
Graph classification(图分类)
主要做的是将不同的图及逆行分类- 应用实例分子属性的预测
-
C
l
u
s
t
e
r
i
n
g
Clustering
Clustering
主要做的是检测节点是否形成社区- 应用实例社区搜索
-
O
t
h
e
r
t
a
s
k
s
Other\ tasks
Other tasks:
-
G
r
a
p
h
g
e
n
e
r
a
t
i
o
n
Graph\ generation
Graph generation(图生成):
- 应用实例药物发现
-
G
r
a
p
h
e
v
o
l
u
t
i
o
n
Graph\ evolution
Graph evolution(图演变)
- 应用实例物理模拟
-
G
r
a
p
h
g
e
n
e
r
a
t
i
o
n
Graph\ generation
Graph generation(图生成):
n o d e l l e v e l nodel\ level nodel level应用实例 P r o t e i n F o l d i n g Protein\ Folding Protein Folding
蛋白质有一些列氨基酸组成氨基酸之间相互作用在局部形成类似螺旋、薄片的形状这些形状折叠起来称为更大尺度的三维蛋白质结构。
所以需要做的是仅基于蛋白质的氨基酸序列来预测蛋白质的三维结构。
这一直以来都是一个难以完成的任务最近 A l p h a F o l d AlphaFold AlphaFold的提出解决了 P r o t e i n F o l d i n g Protein\ Folding Protein Folding问题。
其关键思想是构建 S p a t i a l g r a p h Spatial\ graph Spatial graph
- N o d e s Nodes Nodes蛋白质序列中的氨基酸构成 S p a t i a l g r a p h Spatial\ graph Spatial graph的节点
- E d g e s Edges Edges氨基酸之间的邻接关系构成 S p a t i a l g r a p h Spatial\ graph Spatial graph的边
通过对 S p a t i a l g r a p h Spatial\ graph Spatial graph的学习搭建深度学习模型预测节点(蛋白质氨基酸序列)在空间中的位置从而预测蛋白质的三维结构。
e d g e l e v e l edge\ level edge level应用实例 D r u g S i d e E f f e c t s Drug\ Side\ Effects Drug Side Effects(药物副作用)
在现实生活中许多病人会同时复用多种药物以治疗疾病不同的药物之间相互复用可能会导致一些副作用。然而因为有很多的药物所以很多药物组合的副作用还未知晓。
所以需要做的是给定一对药物预测其可能的不良副作用。
现有的研究已有通过 B i o m e d i c a l G r a p h L i n k P r e d i c t i o n Biomedical\ Graph\ Link\ Prediction Biomedical Graph Link Prediction对该问题进行了求解。
其思想是构建一张只包含两种类型的异构网络图
- N o d e s Nodes Nodes节点由药物 D r u g s Drugs Drugs和蛋白质( P r o t e i n s Proteins Proteins)组成
- E d g e s Edges Edges若药物之间会相互作用、药物与蛋白质之间相互作用、蛋白质之间会相互作用则在两节点之间连接一条边。
如下图
对于某两个药物如
S
i
m
v
a
s
t
a
t
i
n
Simvastatin
Simvastatin和
C
i
p
r
o
f
l
o
x
a
c
i
n
Ciprofloxacin
Ciprofloxacin我们可以预测一起服用时分解肌肉组织的可能性有多大。其实就是这两个药物之间存在
r
2
r_2
r2边的可能性如下图
S
u
b
g
r
a
p
g
−
l
e
v
e
l
Subgrapg-level
Subgrapg−level应用实例
T
r
a
f
f
i
c
P
r
e
d
i
c
t
i
o
n
Traffic\ Prediction
Traffic Prediction(交通预测)
如地图软件上的到达目的地的路线长度、耗时的预测。
此问题可以将公路网络作为一张图
- N o d e s Nodes Nodes将路段作为节点
- E d g e s Edges Edges若两路段之间是连通的则添加一条边
之后就可以使用图神经网络预测到达时间。
G r a p h l e v e l Graph\ level Graph level应用实例 D r u g D i s c o v e r y Drug\ Discovery Drug Discovery(药物发现)
一些抗生素可以表示为一些小的分子而分子可以表示成一张图
- N o d e s Nodes Nodes原子作为节点
- E d g e s Edges Edges化学键作为边
接下来搭建一种图神经网络图分类模型输入一组候选分子结构图从候选分子中预测有希望是抗生素的分子。
即通过 G r a p h Graph Graph来判断该分子是否含有某种属性如判断该分子结构图中是否有两个环。
G r a p h g e n e r a t i o n Graph\ generation Graph generation应用实例 G e n e r a t i n g n o v e l m o l e c u l e s Generating\ novel\ molecules Generating novel molecules(生成新分子)
如构建一个图生成模型学习现有的分子模型从而生成一个新的具有某种属性的新分子(如耐高温属性)
G
r
a
p
h
e
v
o
l
u
t
i
o
n
Graph\ evolution
Graph evolution应用实例
P
h
y
s
i
c
a
l
s
i
m
u
l
a
t
i
o
n
Physical\ simulation
Physical simulation
通过构建一整物理模拟图
- N o d e s Nodes Nodes: 粒子作为节点
- E d g e s Edges Edges: 粒子之间的相互作用做为边
接下来构建一个模型根据例子当前的位置、邻域粒子的关系来预测图将如何演变。
二、Choice of Graph Representation
图的组成部分
-
节点(对象实体) n o d e , v e r t i c e s node,vertices node,vertices
-
边(节点间的交互) l i n k s , e d g e s links,edges links,edges
-
图(节点和边构成整张图) n e t w o r k , g r a p h network,graph network,graph
通常使用 N N N表示节点 E E E表示边 G ( N , E ) G(N,E) G(N,E)表示整个图。
图是一个通用的表示语言
- 将演员通过电影之间的合作关系构建一张图
- 人际关系图边代表不同的关系
需要根据需求来构建合适的图
- 如果想把同事们关联起来可以构建一个职业关系图
- 如果想把相互引用的科学论文连接起来可以构建引文图
构建一个合适的图需要考虑
- 什么将组成图的节点
- 什么将组成图的边
对给定领域/问题选择适当的网络表示决定了我们成功使用网络的能力。
D i r e c t e d v s . U n d i r e c t e d G r a p h s Directed\ vs.\ Undirected\ Graphs Directed vs. Undirected Graphs
U
n
d
i
r
e
c
t
e
d
G
r
a
p
h
s
Undirected\ Graphs
Undirected Graphs(无向图)
无向图中的边是没有没有方向的即节点之间是相互联系的。如下图
D
i
r
e
c
t
e
d
G
r
a
p
h
s
Directed\ Graphs
Directed Graphs(无向图)
有向图中的边是有方向的即节点之间的交互通常是单项的。如下图
N o d e D e g r e e s Node\ Degrees Node Degrees
无向图节点的度与节点相邻的边数
如下图
A
A
A节点的度
k
A
=
4
k_A=4
kA=4
无向图平均度 k ˉ = 1 N ∑ i = 1 N k i = 2 E N \bar{k}=\frac{1}{N}\sum\limits_{i=1}^Nk_i=\frac{2E}{N} kˉ=N1i=1∑Nki=N2E
2 E N \frac{2E}{N} N2E:
2 × 2\times 2×边的数量 ÷ ÷ ÷顶点的数量
每条边都会为顶点贡献度数2所以2E即所有顶点的度数之和
在有向图中定义了入度和出度。
顶点的出度以顶点为起点的边数。
- 如上图 C C C的出度 k C o u t = 1 k^{out}_{C}=1 kCout=1
顶点的入度以顶点为终点的边数。
- 如上图 C C C的出度 k C i n = 2 k^{in}_{C}=2 kCin=2
节点的(总)度是进出度的和。
- 节点 C C C的度 k C = k C o u t + k C i n = 3 k_C=k^{out}_{C}+k^{in}_{C}=3 kC=kCout+kCin=3
有向图平均度 k i n ˉ = k o u t ˉ = E N \bar{k^{in}}=\bar{k^{out}}=\frac{E}{N} kinˉ=koutˉ=NE
每条边只会贡献一个入读和一个出度所以总的出度=总的入度=E
B i p a r t i t e G r a p h Bipartite\ Graph Bipartite Graph(二部图)
B
i
p
a
r
t
i
t
e
G
r
a
p
h
Bipartite\ Graph
Bipartite Graph中有两种类型的节点即节点可以被分成两个不相交的集合
U
U
U和
V
V
V
U
U
U和
V
V
V之间存在链接。如下图
实例
-
A
u
t
h
o
r
s
−
t
o
−
P
a
p
e
r
s
Authors-to-Papers
Authors−to−Papers:
根据 A u t h o r Author Author撰写论文的关系将 A u t h o r Author Author与 P a p e r s Papers Papers链接。 -
A
c
t
o
r
s
−
t
o
−
M
o
v
i
e
s
Actors-to-Movies
Actors−to−Movies
根据演员在电影中是否出现链接电影实体和演员实体 -
U
s
e
r
s
−
t
o
−
M
o
v
i
e
s
Users-to-Movies
Users−to−Movies
根据用户对电影的评分评分高则将用户实例和电影实例链接
F o l d e d / P r o j e c t e d B i p a r t i t e G r a p h Folded/Projected\ Bipartite\ Graph Folded/Projected Bipartite Graph(投影图)
如下图可以将中间的 B i p a r t i t e G r a p h Bipartite\ Graph Bipartite Graph投影成 P r o j e c t e d U Projected\ U Projected U和 P r o j e c t e d V Projected\ V Projected V。
P
r
o
j
e
c
t
e
d
U
Projected\ U
Projected U中节点
U
U
U的链接关系可以根据
B
i
p
a
r
t
i
t
e
G
r
a
p
h
Bipartite\ Graph
Bipartite Graph来确定如
1
、
2
、
3
1、2、3
1、2、3节点之间都链接了相同的节点
A
A
A则可以认为
1
、
2
、
3
1、2、3
1、2、3节点是连通的所以在
P
r
o
j
e
c
t
e
d
U
Projected\ U
Projected U中链接
1
、
2
、
3
1、2、3
1、2、3节点。
个人想法
就是将异构图 B i p a r t i t e G r a p h Bipartite\ Graph Bipartite Graph通过某个元路径将其转换为同构图。
该方式在存储稀疏图的时候会花费大量内存存储不存在的边。
图的表示方式
A d j c e n c y M a t r i x Adjcency\ Matrix Adjcency Matrix
- 无向图
- A i j = A j i A_{ij}=A_{ji} Aij=Aji
- 若 i i i到 j j j有一条边 A i j = 1 A_{ij}=1 Aij=1否则 A i j = 0 A_{ij}=0 Aij=0
- k i = ∑ j = 1 N A i j k_i=\sum \limits_{j=1}^{N}A_{ij} ki=j=1∑NAij
- 有向图
- A i j = A j i A_{ij}=A_{ji} Aij=Aji不一定成立
- 若 i i i到 j j j有一条边 A i j = 1 A_{ij}=1 Aij=1否则 A i j = 0 A_{ij}=0 Aij=0
- k i o u t = ∑ j = 1 N A i j k^{out}_i=\sum \limits _{j=1}^{N}A_{ij} kiout=j=1∑NAij
- k i i n = ∑ i = 1 N A i j k^{in}_i=\sum \limits _{i=1}^{N}A_{ij} kiin=i=1∑NAij
E d g e l i s t Edge\ list Edge list
将图组织成一个关于边的列表如下图
但是该方式不利于进行图的操作如计算出度、入读都需要遍历整个列表代价太大。
D d j a c e n y l i s t Ddjaceny\ list Ddjaceny list(邻接列表):
构建长度为
V
V
V的列表第
i
i
i个列表存
i
i
i顶点的邻居节点如下图
该方法适用于存储稀疏矩阵减少内存消耗。
为了丰富图的表示信息可以为边、顶点和图添加属性
对节点和边可添加的属性如下
- W e i g h t Weight Weight权重
- R n a k i n g Rnaking Rnaking排名
- T y p e Type Type类型
- S i g n Sign Sign标记
- 与图结构相关的属性 与图结构相关的属性 与图结构相关的属性如共同节点的数量
权重图与无权重图
若在边上添加了 w e i g h t weight weight则该图是一个权重图否则是无权重图。
可以通过邻接矩阵来表示权重图与无权重图如下图
S e l f − e d g e s ( s e l f − l o o p s ) Self-edges(self-loops) Self−edges(self−loops)
图中存在以相同顶点为终点和起点的边如下图
M u l t i g r a p h Multigraph Multigraph
顶点之间可以存在多条边如下图
C o n n e c t e d ( u n d i r e c t e d ) g r a p h Connected (undirected)\ graph Connected(undirected) graph(无向连通图)
任何两个顶点都可以用一条路径连接起来
一个不连接的图是由两个或多个连通分量组成的
具有多个连通分量的图的邻接矩阵可以写成块对角线形式这样非零元素就被限制在某个方形区域其他元素都为零
C o n n e c t e d ( d i r e c t e d ) g r a p h Connected (directed)\ graph Connected(directed) graph(有向连通图)
- 有向强连通图
任何两个顶点都可以用一条路径连接起来 - 有向弱连通图
如果我们忽略边的方向是连通的
图中的 { A 、 B 、 C } \{A、B、C\} {A、B、C}构成的子图就是一个强连通图而整张图是一个弱连通图。
S
t
r
o
n
g
l
y
c
o
n
n
e
c
t
e
d
c
o
m
p
o
n
e
n
t
s
(
S
C
C
s
,
强连通分量
)
Strongly\ connected\ components (SCCs,强连通分量)
Strongly connected components(SCCs,强连通分量)
有向图中可以构成强连通图的子图。如
{
A
、
B
、
C
}
\{A、B、C\}
{A、B、C}构成的子图就是一个强连通分量