基本应用
图基础与中心指标
一.基础属性
基本定义：节点、边
基本类型：有向图、无向图；加权图，非加权图；连通图，非连通图；连通分量，强连通分量，弱连通分量；二部图
邻居，𝑘阶邻居，度
子图、𝑘阶子图、路径、图直径
表示方式: 邻接矩阵，关联矩阵
遍历方式：深度优先，广度优先
#构建图
%matplotlib inline
from matplotlib import pyplot as plt
import networkx as nx
G=nx.Graph()#无向图，有向图用DiGraph
G.add_nodes_from(["A","B","C","D","E","F","G","H"])
G.add_edges_from([("A","B"),("A","C"),("B","C"),("C","D"),("E","F"),("F","G"),("G","H")])
nx.draw_networkx(G)
plt.show()
#度
nx.degree(G)>>>
DegreeView({'A': 2, 'B': 2, 'C': 3, 'D': 1, 'E': 1, 'F': 2, 'G': 2, 'H': 1})#连通分量
list(nx.connected_components(G))>>>
[{'A', 'B', 'C', 'D'}, {'E', 'F', 'G', 'H'}]#图直径:所有两两节点直接最短路径的最大值
subG=nx.subgraph(G,["A","B","C","D"])
nx.diameter(subG)>>>
2#路径长度
nx.shortest_path_length(G,source="A",target="D")>>>
2二.中心性指标
中心性指标主要用于衡量节点在图中的重要性/影响力，我们对节点重要性的解释有很多，不同的解释下判定中心性的指标也有所不同，通常有这些：点度中心性，中介中心性，接近中心性，特征向量中心性，PageRank，hits
#点度中心性
#节点的邻居越多，它就越重要，定义为：度/(节点数-1)
nx.degree_centrality(G)>>>
{'A': 0.2857142857142857,
'B': 0.2857142857142857,
'C': 0.42857142857142855,
'D': 0.14285714285714285,
'E': 0.14285714285714285,
'F': 0.2857142857142857,
'G': 0.2857142857142857,
'H': 0.14285714285714285}#中介中心性
#如果该节点出现该其它两两节点路径上的次数越多，它就越重要
nx.betweenness_centrality(G)>>>
{'A': 0.0,
'B': 0.0,
'C': 0.09523809523809523,
'D': 0.0,
'E': 0.0,
'F': 0.09523809523809523,
'G': 0.09523809523809523,
'H': 0.0}#接近中心性
#如果该节点与其它节点之间的距离越近，它就越重要
nx.closeness_centrality(G)>>>
{'A': 0.3214285714285714,
'B': 0.3214285714285714,
'C': 0.42857142857142855,
'D': 0.2571428571428571,
'E': 0.21428571428571427,
'F': 0.3214285714285714,
'G': 0.3214285714285714,
'H': 0.21428571428571427}#特征向量中心性
#定义：取邻接矩阵特征分解后，最大特征值对应的特征向量
#与某节点连接的节点的邻居越多，就越重要
#新增加一个节点I来连接两块连通分量
G=nx.Graph()
G.add_nodes_from(["A","B","C","D","E","F","G","H","I"])
G.add_edges_from([("A","B"),("A","C"),("B","C"),("C","D"),("E","F"),("F","G"),("G","H"),("I","B"),("I","F")])
nx.draw_networkx(G)
plt.show() >>>
nx.eigenvector_centrality(G)>>>
{'A': 0.44885390912200857,
'B': 0.5468450989996043,
'C': 0.5135021004101872,
'D': 0.21736961615213216,
'E': 0.09799461776528895,
'F': 0.2314938976977582,
'G': 0.11938887762076224,
'H': 0.0505393145300136,
'I': 0.3294789107351654}#pagerank
nx.pagerank(G)>>>
{'A': 0.10252135128679807,
'B': 0.14929077894067944,
'C': 0.153726203840718,
'D': 0.06022249294537078,
'E': 0.06475108608528522,
'F': 0.16971188372812845,
'G': 0.1235500933464885,
'H': 0.06917616539981883,
'I': 0.1070499444267125}#hits
nx.hits(G)>>>
({'A': 0.17564701604305502,
'B': 0.21399245433642766,
'C': 0.2009454874842481,
'D': 0.08506205753671801,
'E': 0.03834543957793587,
'F': 0.09058495722206274,
'G': 0.04671661924357704,
'H': 0.019775570471702603,
'I': 0.1289303980842729},
{'A': 0.1756470158158291,
'B': 0.21399245588711766,
'C': 0.2009454869245228,
'D': 0.085062057946483,
'E': 0.03834543855419052,
'F': 0.09058495938682286,
'G': 0.04671661787549817,
'H': 0.01977557118599924,
'I': 0.1289303964235366})Graph Embedding
一. DeepWalk原理
其实就两个阶段：
1）对图随机游走得到一个序列；
2）将该序列进行word2vec训练得到embedding
下面利用对word进行embbeding训练举例，我选择了当前的一条关于新冠的新闻，对其分词构建一个带权有向图，权重为其相邻两词的出现的次数
#准备预料
corpus="""新华社河内5月29日电（记者蒋声雄 黄硕）越南卫生部长阮青龙29日宣布该国发现新的新冠病毒变异毒株，它是此前在英国和印度发现的变异毒株的混合体。
阮青龙当天在越南全国新冠疫情防控视频会议上说，这种变异毒株混合体“非常危险”，传播性更强，能在空气中迅速传播。这一新发现的毒株混合体尚未命名。
据“越南快报网”报道，此前在越南已发现7种新冠病毒变异毒株，包括最早在印度和英国发现的变异毒株。
越南于今年4月底出现新一轮新冠疫情，首都河内、南部胡志明市、中部岘港市等主要城市出现多个本土病例，北部北江省某工业园内发生大规模感染新冠病毒事件。据越通社报道，截至当地时间29日12时，越南累计确诊新冠本土病例5213例，其中自4月27日以来新增确诊新冠本土病例3643例"""\
.replace("\n","").replace("，","").replace("、","").replace("（","").replace("）","").replace(" ","").replace("“","").replace("”","").split("。")corpus>>>
['新华社河内5月29日电记者蒋声雄黄硕越南卫生部长阮青龙29日宣布该国发现新的新冠病毒变异毒株它是此前在英国和印度发现的变异毒株的混合体',
'阮青龙当天在越南全国新冠疫情防控视频会议上说这种变异毒株混合体非常危险传播性更强能在空气中迅速传播',
'这一新发现的毒株混合体尚未命名',
'据越南快报网报道此前在越南已发现7种新冠病毒变异毒株包括最早在印度和英国发现的变异毒株',
'越南于今年4月底出现新一轮新冠疫情首都河内南部胡志明市中部岘港市等主要城市出现多个本土病例北部北江省某工业园内发生大规模感染新冠病毒事件',
'据越通社报道截至当地时间29日12时越南累计确诊新冠本土病例5213例其中自4月27日以来新增确诊新冠本土病例3643例']import jieba
lines=[list(jieba.cut(line)) for line in corpus]#分词Building prefix dict from the default dictionary …
Loading model from cache C:\Users\Alei\AppData\Local\Temp\jieba.cache
Loading model cost 0.619 seconds.
Prefix dict has been built successfully.
word_cnt={}
word_set=set()
for line in lines:
for i in range(0,len(line)-1):
pre_cnt=word_cnt.get((line[i],line[i+1]),0)
word_cnt[(line[i],line[i+1])]=1+pre_cnt
word_set.add(line[i])
word_set.add(line[i+1])#构建图
%matplotlib inline
from matplotlib import pyplot as plt
import networkx as nx
plt.figure(figsize=(16, 12))
plt.axis("off")
G=nx.DiGraph()
G.add_edges_from([(key[0],key[1]) for key in word_cnt.keys()])
nx.draw_networkx(G)
plt.show()
二.随机游走实现
随机游走的核心也很简单，大概流程如下：
1）从图中随机选择一个起始node
2）从它的（箭头指向的）邻居中随机选择一个新node
3）重复第2）步，直到满足终止条件，上面的所有node组成的序列即是我们所需
另外，上面的每一步都可以自定义自己的策略，比如第1）步初始点不从图中随机选择，而是从实际句子的初始词中选择，第2）步，随机选择下一个节点时，考虑边的权值，权值越大越容易被选择，第3）步，通常可以设置一个最大游走长度
import numpy as np
def walk_one_time(G,start_node,walk_len):
seq=[start_node]
for _ in range(walk_len-1):
current_node=seq[-1]#获取seq的最有一个节点
next_nodes=list(G.successors(current_node))#获取所有邻居节点
if len(next_nodes)==0:
break
selected_next_node=np.random.choice(next_nodes)#从所有邻居中随机选择一个
seq.append(selected_next_node)
return seq#test
walk_one_time(G,"变异",5)>>>
['变异', '毒株', '它', '是', '此前']#将上面的过程重复多次，即可得到一个新的corpus
def deep_walk(G,walk_len=10,num_seqs=100):
corpus=[]
for _ in range(num_seqs):
start_node=np.random.choice(G.nodes)
corpus.append(walk_one_time(G,start_node,walk_len))
return corpusnew_corpus=deep_walk(G)
new_corpus[0]>>>
['包括', '最早', '在', '越南', '快报', '网', '报道', '截至', '当地', '时间']三.Word2Vec的训练
word2vec的训练可以使用gensim工具包，word2vec的原理包括两点：
1）基于语言模型的原理，语言模型的作用用于判断一个句子出现的概率，由于句子通常会被分词，所有语言模型可以看作判断一个词语序列的出现概率，好的语言模型应该能做到比如如下的判断：
$$
Proba([[变异],[毒株],[混合体],[非常],[危险]])>Proba([[变异],[危险],[混合体],[非常],[毒株]])
$$
显然，第一句是人话，第二句读不通
2）而word2vec就是利用极大似然估计的方式让我们的人话出现的概率尽可能高，而鬼话的概率尽可能小，它采用三层的网络结构，
2.1）第一层是input层，它与我们的词典一一对应
2.2）中间层是hidden层，它就是我们embedding的维度
2.3）最后一层是output层，它同样与我们的词典一一对应
它的训练如下图，
1）我们对输入的文本截取一定的窗口，比如window_size=2，那么我们选取目标次前后的2X2+1=5个词语，比如[[变异],[毒株],[混合体],[非常],[危险]]这5个词语
2）然后，我们构建([变异],[毒株],[非常],[危险])->([混合体])的映射，其中前半部分，我们称作[混合体]的上下文
3）最后，我们利用极大似然估计估计上面的上下文和目标词的映射概率尽可能的大
from gensim.models import word2vec
model = word2vec.Word2Vec(new_corpus,window=2,vector_size=5,min_count=1)#查看embedding
model.wv["变异"]>>>
array([-0.19377613, 0.10809163, -0.16566691, -0.09616406, 0.00191299],
dtype=float32)model.wv["混合体"]>>>
array([ 0.15368475, -0.18145339, 0.00444265, 0.05817473, -0.01261494],
dtype=float32)这样，我们就为图上的每个节点训练出了一个embedding，另外上面的训练过程实际是采用了CBOW的方式，即用上下文来预测某个词，而实际deepwalk更多是使用skip-gram的方式，即利用单个词去预测它的上下文（上面图中的箭头反向），这样训练的embedding效果通常会更好
四.Node2Vec原理
Node2vec其实是对于DeepWalk中第2)步，随机游走方式的调整，以学习到图结构的同质性和结构性信息。这里：
1）同质性是指相邻两节点之间应该具有较高的相似度；
2）结构性是指邻居结构相似的两节点之间应该具有较高的相似度，即使这两节点之间没有路径连接
如下图，u与s1,s2,s3,s4之间在同质性上应该具有较高的相似度，而u与s6在结构性上应该具有较高相似度
那如何游走才能提现同质性和结构性呢，这其实可以利用我们常见的图搜索算法，深度优先搜索(DFS)和广度优先搜索(BFS):
1)DFS:深度优先搜索，在相俩节点间游走，倾向于获取同质性信息；
2)BFS:广度优先搜索，优先获取节点周围邻居序列，倾向于获取结构性信息；
具体的游走方式如下
已知，当前序列的最后两节点为[t,v]，即最后一步游走为t->v，那么接下的游走方式满足如下公式：
下面直观解释一下这三种情况：
(1) $d_{tx}=0$，表示$t$节点与$x$节点距离为0，所以它们是同一节点，言外之意是说从$v$节点又跳回了前节点$t$，它的跳转概率定义为$\frac{1}{p}$
(2) $d_{tx}=1$，表示既与$t$相连，又与$v$相连的节点，如图中的$x_1$，它的跳转概率定义为1
(3) $d_{tx}=2$，即图中的$x_2,x_3$节点，它们的跳转概率被定义为$\frac{1}{q}$
注意，上面的“概率”都未归一化，最终需要进行归一化操作，另外node2vec还需要考虑边的权重$w_{vx}$，所以它实际是对$\pi_{vx}=\alpha_{pq}(t,x)\cdot w_{vx}$进行归一化，下面对超参数$p,q$进行讨论；
对于p：如果$p>max(q,1)$,那么采样倾向于不会往回走，而如何$p<min(q,1)$，采样倾向于返回上一个节点，在初始点周围游走
对于q: 如果$q>1$，采样点倾向于在起始点周围游走做BFS采样，而如果$q<1$，倾向于远离起始点，做DFS采样
五.实现
#构建图
%matplotlib inline
from matplotlib import pyplot as plt
import networkx as nx
plt.axis("off")
G=nx.DiGraph()
edges=[("u","s1"),("u","s2"),("u","s3"),("u","s4"),("s1","s2"),("s1","s3"),("s3","s4"),
("s2","s4"),("s5","s2"),("s4","s5"),("s6","s5"),("s6","s7"),("s6","s8"),("s6","s9"),
("s5","s7"),("s7","s8"),("s8","s9")]
G.add_edges_from(edges)
G.add_edges_from((edge[1],edge[0]) for edge in edges)
nx.draw_networkx(G)
plt.show()
import numpy as np
class Node2Vec(object):
def __init__(self,walk_len=10,num_seqs=10,p=1,q=1):
self.walk_len=walk_len
self.num_seqs=num_seqs
self.p=p
self.q=q
def walk_one_time(self,G,start_node):
#添加第二个点
second_node=np.random.choice(list(G.successors(start_node)))
seq=[start_node,second_node]
for _ in range(self.walk_len-2):
t_node=seq[-2]
v_node=seq[-1]
next_nodes=list(G.successors(v_node))#获取所有邻居节点
proba=[]#记录概率
for next_node in next_nodes:
path_len=nx.shortest_path_length(G,source=t_node,target=next_node)
if path_len==0:
proba.append(1/self.p)
elif path_len==1:
proba.append(1)
else:
proba.append(1/self.q)
proba=np.asarray(proba)
proba=proba/np.sum(proba)#归一化
selected_next_node=np.random.choice(next_nodes,p=proba)#从所有邻居中随机选择一个
seq.append(selected_next_node)
return seq
def deep_walk(self,G):
corpus=[]
for _ in range(self.num_seqs):
start_node=np.random.choice(G.nodes)
corpus.append(self.walk_one_time(G,start_node))
return corpusnode2vec=Node2Vec(q=2)
corpus=node2vec.deep_walk(G)corpus[:1]>>>
[['s1', 'u', 's3', 's4', 's2', 'u', 's1', 's3', 'u', 's1']]#训练
from gensim.models import word2vec
model = word2vec.Word2Vec(corpus,window=2,vector_size=5,min_count=1)#查看embedding
model.wv['u']>>>
array([-0.14191031, 0.13018166, 0.1809364 , -0.10049632, -0.07593277],
dtype=float32)#计算相似度
model.wv.similarity("u","s5")>>>
0.07862966model.wv.similarity("u","s6")>>>
0.6219288GCN
GCN原理
1.1 问题1： 先看一个例子，假如我们有如下的5个用户，他们编号为0~4，且知道他们的关系如下，假如我们现在面对的是车险反欺诈的预测场景，已知编号1，2的为欺诈客户（正样本），编号4的为正常客户（负样本），现在要我们预测剩下的编号0，3的客户是欺诈客户还是正常客户？该怎么办呢？
我想基于前三节的内容至少可以有两个思路：
（1）基于度指标：计算当前节点的邻居节点中欺诈客户的占比，那么0号客户周围1/1的客户都是欺诈客户，所以他也是欺诈客户，而客户3周围有2/3的客户都是欺诈客户，所以他也是欺诈客户
（2）基于Graph Embedding：基于DeepWalk或者Node2Vec的方式为每个用户学习一个Embedding，然后计算它与邻居Embedding的相似度，然后统计累计相似度占比最高的标签为当前节点的标签，或者直接将这些Embedding送到一个分类器进行训练
1.2 问题2： 而我们在处理实际数据时，可能并不仅仅只有他们之间的关系数据，还会有他们各自的因子数据，比如年龄，最近半年的贷款额，最近一月的消费额度这三项，我们将其加到图中（已经归一化处理）
那现在如何处理？以往我们可能会只利用他们的因子数据来构建分类模型，比如使用lgbm对这三维度的因子建模预测，但这样又少了结构信息；那如果只利用了上面的结构信息建模又少了因子数据（当然你也可以尝试将Embedding+因子结合起来），那有没有办法同时利用结构信息和因子信息呢？这可以从CNN的卷积操作进行借鉴
1.3 更一般的认识CNN: 让我们重新理解一下CNN中卷积操作，
1) 卷积操作本质上是将某视野域内的像素点数据进行加权聚合，如下图左边将红色区块附近的8个绿块数据加权聚合到红块中（通常会包含红块自身的数据）；
2) 那如果我们将这些像素点强行拉开呢？这中间的图不就是一个图结构了吗？（而且现在的边时带权重的，它的权重就对应了卷积块上的数值）；
3) 那如果我们再将中图中的某些边切掉，那不就是更一般的图结构了
所以，我们完全可以利用CNN的方式来处理GNN：将周围邻居的信息加权聚合到中心节点，这便是GCN的基本思路了：
1）节点上的信息就是我们的因子，比如上面的年龄，最近半年的贷款额，最近一月的消费额…
2）而对邻居的加权聚合便是对于结构信息的处理…
如此这样，就能同时利用节点的因子信息和结构信息了，下面介绍GCN的详细推导
1.4 GCN推导
结构上：
与CNN类似，当前节点的更新信息由当前节点的信息和周围邻居信息累加得到，对于图结构而言，我们需要为每个节点添加一个自连接
比如对于节点1，它的更新后的信息就是：
$$
[0.4,0.2,0.7]+[0.2,0.3,0.5]+[0.3,0.3,0.5]+[0.4,0.2,0.3]=[1.3,1.0,2.0]
$$
再比如，对于节点4，它的更新后的信息就是：
$$
[0.2,0.4,0.3]+[0.4,0.2,0.3]=[0.6,0.6,0.6]
$$
想必，你也发现问题了，对于邻居很多的节点，聚合后的数值会比其它邻居少的节点大很多，所以我们需要进行归一化，GCN是采用的归一化方式如下，对于节点$v_i,v_j$，它们的度为$d(v_i),d(v_j)$，聚合信息时，会在它们前面乘以一个权重，即度的乘积的平方根的倒数：
$$
\frac{1}{\sqrt{d(v_i)}\cdot \sqrt{d(v_j)}}
$$
所以，这时对于节点1的更新就是：
$$
\frac{1}{4}[0.4,0.2,0.7]+\frac{1}{2\sqrt{2}}[0.2,0.3,0.5]+\frac{1}{2\sqrt{3}}[0.3,0.3,0.5]+\frac{1}{2\sqrt{3}}[0.4,0.2,0.3]
$$
上面的更新操作，可以对$X$左乘一个矩阵来进行计算：
$$
\tilde{L}_{sym}X
$$
这里的$X$就是我们的因子数据，第$i$行就是第$i$个因子的向量表示，比如$X_{0,:}=[0.2,0.3,0.5]$，而
$$
\tilde{L}{sym}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}, \tilde{A}=A+I, \tilde{D{ii}}=\sum_j\tilde{A}_{ij}
$$
这里的$A$是连接矩阵，$I$是单位矩阵，所以$\tilde{A}X$，就是添加了自连接且没加权的聚合表示，即最上面的表示，如节点1的聚合
$$
[0.4,0.2,0.7]+[0.2,0.3,0.5]+[0.3,0.3,0.5]+[0.4,0.2,0.3]=[1.3,1.0,2.0]
$$
而$\tilde{D}$是$\tilde{A}$的度矩阵，它只有对角线上有值，$\tilde{D}_{ii}$的值就是$\tilde{A}$的第$i$行求和，所以$\tilde{A}$矩阵前后分别乘一个$\tilde{D}^{-1/2}$相等于乘以了上文介绍的权重$\frac{1}{\sqrt{d(v_i)}\cdot \sqrt{d(v_j)}}$
因子上：
可以发现$ \tilde{L}{sym}X $ 中的 $ \tilde{L}{sym} $和$ X $都是已知的，GCN希望增强模型的表达能力，所以对于$ \tilde{L}_{sym}X $在特征上再做了一次线性变换，等价于右乘一个变量矩阵$ W $，为了进一步增强表达能力，通常还会对结果进行一个非线性变换$ \sigma $，所以最终的更新公式如下：
$$
X’=\sigma(\tilde{L}_{sym}XW)
$$
需要注意的是，$W$是对每一层的所有节点共享的，这里可以将其类比为CNN中的卷积核系数
如何训练？
这就和其它ML的任务一样的，构造一个损失函数$loss(X’,Y)$，然后基于梯度，更新参数$W$即可，比如($\eta$为学习率)：
$$
W\leftarrow W-\eta\frac{\partial loss(X’,Y)}{\partial W}
$$
代码实践
下面仅演示代码的核心部分
2.1 加载数据并构建$\tilde{L}_{sym}$
from code.gcn import *#加载数据
dataset = CoraData().dataUsing Cached file: E:\datas\Algs\GNN\cora\processed_cora.pkl
Cached file: E:\datas\Algs\GNN\cora\processed_cora.pkl
链接矩阵：表示文章之间的引用关系，这里是稀疏矩阵的格式
dataset.adjacency>>>
<2708x2708 sparse matrix of type '<class 'numpy.float32'>'
with 10556 stored elements in COOrdinate format>因子信息：2708X1433的矩阵，即2708篇文章的BOW表示
dataset.x>>>
array([[0., 0., 0., ..., 0., 0., 0.],
[0., 0., 0., ..., 0., 0., 0.],
[0., 0., 0., ..., 0., 0., 0.],
...,
[0., 0., 0., ..., 0., 0., 0.],
[0., 0., 0., ..., 0., 0., 0.],
[0., 0., 0., ..., 0., 0., 0.]], dtype=float32)标签信息：2708X1，分别标记了2708篇文章的7种类别
dataset.y>>>
array([3, 4, 4, ..., 3, 3, 3], dtype=int64)构建$\tilde{L}_{sym}$的代码：
def normalization(adjacency):
"""计算 L=D^-0.5 * (A+I) * D^-0.5"""
adjacency += sp.eye(adjacency.shape[0])
# 增加自连接
degree = np.array(adjacency.sum(1))
d_hat = sp.diags(np.power(degree, -0.5).flatten())
return d_hat.dot(adjacency).dot(d_hat).tocoo()#如果有GPU则使用GPU
device = "cuda" if torch.cuda.is_available() else "cpu"
#接着预处理剩下的数据
x = dataset.x / dataset.x.sum(1, keepdims=True)
# 归一化数据，使得每一行和为1
tensor_x = torch.from_numpy(x).to(device)
tensor_y = torch.from_numpy(dataset.y).to(device)
tensor_train_mask = torch.from_numpy(dataset.trn_mask).to(device)
tensor_val_mask = torch.from_numpy(dataset.val_mask).to(device)
tensor_test_mask = torch.from_numpy(dataset.test_mask).to(device)
normalize_adjacency = normalization(dataset.adjacency)
# 规范化邻接矩阵
indices = torch.from_numpy(np.asarray([normalize_adjacency.row, normalize_adjacency.col])).long()
values = torch.from_numpy(normalize_adjacency.data.astype(np.float32))
tensor_adjacency = torch.sparse.FloatTensor(indices, values, (2708, 2708)).to(device)2.2 构建模型
这部分代码拆分为了两块，
1）第一块是对单次图卷积的操作，对应上面的公式：$X’=\sigma(\tilde{L}_{sym}XW)$，代码如下(这里并没有实现激活函数的功能)：
class GraphConvolution(nn.Module):
def __init__(self, input_dim, output_dim, use_bias=True):
"""图卷积
input_dim: 节点输入特征的维度
output_dim: 输出特征维度
use_bias : bool, optional"""
super(GraphConvolution, self).__init__()
self.input_dim = input_dim
self.output_dim = output_dim
self.use_bias = use_bias
self.weight = nn.Parameter(torch.Tensor(input_dim, output_dim))
if self.use_bias:
self.bias = nn.Parameter(torch.Tensor(output_dim))
else:
self.register_parameter('bias', None)
self.reset_parameters()
def reset_parameters(self):
nn.init.kaiming_uniform_(self.weight)
if self.use_bias:
nn.init.zeros_(self.bias)
def forward(self, adjacency, input_feature):
"""
adjacency: 经过上面归一化后的链接矩阵，即\tilde{L}_{sym}
input_feature:输入特征，即X """
support = torch.mm(input_feature, self.weight)
output = torch.sparse.mm(adjacency, support)
if self.use_bias:
output += self.bias
return output2）第二块代码叠加了两层图卷积，第一层将1433维的BOW降低到16维，第二层将16维降低到7维，对应到我们的类别数
class GCNNet(nn.Module):
""" 定义一个包含两层GraphConvolution的模型 """
def __init__(self, input_dim=1433):
super(GCNNet, self).__init__()
self.gcn1 = GraphConvolution(input_dim, 16)
self.gcn2 = GraphConvolution(16, 7)
def forward(self, adjacency, feature):
h = F.relu(self.gcn1(adjacency, feature))
logits = self.gcn2(adjacency, h)
return logits#构建模型
model = GCNNet().to(device)2.3 训练模型
主要包括：
1）损失函数定义
2）优化器定义
3）训练过程： <1>前向得到loss ； <2>loss反向更新参数
# 超参数定义
learning_rate = 0.1
weight_decay = 5e-4
epochs = 200
# 损失函数使用交叉熵
criterion = nn.CrossEntropyLoss().to(device)
# 优化器使用Adam
optimizer = optim.Adam(model.parameters(), lr=learning_rate, weight_decay=weight_decay)
# 训练
loss_history = []
val_acc_history = []
model.train()
train_y = tensor_y[tensor_train_mask]
for epoch in range(epochs):
# 前向传播
logits = model(tensor_adjacency, tensor_x)
# 只选择训练节点进行监督
train_mask_logits = logits[tensor_train_mask]
# 计算损失值
loss = criterion(train_mask_logits, train_y)
# 反向传播计算参数的梯度
optimizer.zero_grad()
loss.backward()
# 使用优化方法进行梯度更新
optimizer.step()2.4 预测并查看效果
# tsne降维，查看效果
import warnings
warnings.filterwarnings("ignore",category=DeprecationWarning)
%matplotlib inline
#对X用tsne降维
from sklearn import manifold
tsne = manifold.TSNE(n_components=2,init="pca")
X_tsne = tsne.fit_transform(tensor_x.numpy())
#预测
pred = model(tensor_adjacency, tensor_x).max(1)[1].numpy()
#归一化显示
x_min, x_max = X_tsne.min(0), X_tsne.max(0)
X_norm = (X_tsne - x_min) / (x_max - x_min)
plt.figure(figsize=(12, 9))
plt.scatter(X_norm[:,0],X_norm[:,1],c=pred)
plt.yticks([])
plt.xticks([])
plt.show()
GraphSAGE
GraphSAGE原理
GraphSAGE是对GCN的优化，其中SAGE是sample和aggreage的缩写，从名称我们也可以看出它主要优化的两个方向：即采样和聚合
采样
GCN的训练需要图的全局信息（连接矩阵$\tilde{L}_{sym}$），对于太大的图，可能没有足够的内存或者显存进行训练，借鉴DNN中常用的批量训练方式，GCN也可以利用采样来进行训练，它的采样主要关注两方面：1）采样训练节点：由于GCN每增加一层，节点所利用到的邻居信息就要往外扩展一层，所以对于$k$层的GCN网络，我们需要每个训练节点的$k$阶子图样本；2）采样邻居节点：另外，由于某些超级节点（度特别大的节点，比如平均度为10的图，某些节点的度可能会有100W）存在，也有造成OOM的风险，对于$k$阶子图的规模也要进行控制，这可以通过限制每层邻居节点数量来控制，如下图第一层采样了3个节点，第二层采样了2个节点（有放回采样）
聚合
这一部分其实都是借鉴的DNN中的常见操作，比如取平均/求和/池化等等，这里可以自己设计，需要满足两点：1）不对不同的邻居数量，需要有相同维度的输出，比如$|Agg(v_1,v_2,v_3)|=|Agg(v_1,v_2)|$（$|\cdot|$表示维度）；2）平移不变性，对于不同的输入顺序需要有相同的输出，比如$|Agg(v_1,v_2)=Agg(v_2,v_1)|$，接下来再利用上面的例子演示一下聚合过程：
（1）首先将训练节点周围的3个邻居信息聚合，得到图1；
（2）然后再将3个邻居的邻居信息聚合到邻居，得到图2，这时第一层GCN就结束了；
（3）最后，再次将3个邻居信息聚合到训练节点，得到图3，第二层GCN结束。
其中，淡蓝色的点，表示该次操作后不再被需要的点，粉红的点表示采样点，红色和橘黄色分别表示第一轮GCN和第二轮GCN聚合后的点，红色有向边表示第一层的GCN聚合，橘黄色有向边表示第二层的GCN聚合，无向边表示不操作
实现
#1.准备数据
from code.graph_sage import *
data = CoraData().data
x = data.x / data.x.sum(1, keepdims=True) # 归一化数据，使得每一行和为1
train_index = np.where(data.train_mask)[0]
train_label = data.y
test_index = np.where(data.test_mask)[0]Using Cached file: E:\datas\Algs\GNN\cora\ch7_cached.pkl
#2.训练模型
INPUT_DIM = 1433 # 输入维度
# Note: 采样的邻居阶数需要与GCN的层数保持一致
HIDDEN_DIM = [64, 7] # 隐藏单元节点数
NUM_NEIGHBORS_LIST = [10, 10] # 每阶采样邻居的节点数
BTACH_SIZE = 16 # 批处理大小
EPOCHS = 100
NUM_BATCH_PER_EPOCH = 20 # 每个epoch循环的批次数
LEARNING_RATE = 0.01 # 学习率
DEVICE = "cuda" if torch.cuda.is_available() else "cpu"
model = GraphSage(input_dim=INPUT_DIM, hidden_dim=HIDDEN_DIM,
num_neighbors_list=NUM_NEIGHBORS_LIST).to(DEVICE)
print(model)
criterion = nn.CrossEntropyLoss().to(DEVICE)
optimizer = optim.Adam(model.parameters(), lr=LEARNING_RATE, weight_decay=5e-4)GraphSage(
in_features=1433, num_neighbors_list=[10, 10]
(gcn): ModuleList(
(0): SageGCN(
in_features=1433, out_features=64, aggr_hidden_method=sum
(aggregator): NeighborAggregator(in_features=1433, out_features=64, aggr_method=mean)
)
(1): SageGCN(
in_features=64, out_features=7, aggr_hidden_method=sum
(aggregator): NeighborAggregator(in_features=64, out_features=7, aggr_method=mean)
)
)
)for e in range(EPOCHS):
model.train()
for batch in range(NUM_BATCH_PER_EPOCH):
batch_src_index = np.random.choice(train_index, size=(BTACH_SIZE,))
batch_src_label = torch.from_numpy(train_label[batch_src_index]).long().to(DEVICE)
batch_sampling_result = multihop_sampling(batch_src_index, NUM_NEIGHBORS_LIST, data.adjacency_dict)
batch_sampling_x = [torch.from_numpy(x[idx]).float().to(DEVICE) for idx in batch_sampling_result]
batch_train_logits = model(batch_sampling_x)
loss = criterion(batch_train_logits, batch_src_label)
optimizer.zero_grad()
loss.backward() # 反向传播计算参数的梯度
optimizer.step() # 使用优化方法进行梯度更新
# print("Epoch {:03d} Batch {:03d} Loss: {:.4f}".format(e, batch, loss.item()))
# test
model.eval()
with torch.no_grad():
test_sampling_result = multihop_sampling(test_index, NUM_NEIGHBORS_LIST, data.adjacency_dict)
test_x = [torch.from_numpy(x[idx]).float().to(DEVICE) for idx in test_sampling_result]
test_logits = model(test_x)
test_label = torch.from_numpy(data.y[test_index]).long().to(DEVICE)
predict_y = test_logits.max(1)[1]
accuarcy = torch.eq(predict_y, test_label).float().mean().item()
# print("Test Accuracy: ", accuarcy)#3.查看效果
import warnings
warnings.filterwarnings("ignore")
%matplotlib inline
from sklearn import manifold
tsne = manifold.TSNE(n_components=2,init="pca")
X_tsne = tsne.fit_transform(x)
total_sampling_result = multihop_sampling(list(range(len(x))), NUM_NEIGHBORS_LIST, data.adjacency_dict)
total_x = [torch.from_numpy(x[idx]).float().to(DEVICE) for idx in total_sampling_result]
pred = model(total_x).max(1)[1].numpy()
x_min, x_max = X_tsne.min(0), X_tsne.max(0)
X_norm = (X_tsne - x_min) / (x_max - x_min) # 归一化
plt.figure(figsize=(12, 9))
plt.scatter(X_norm[:,0],X_norm[:,1],c=pred)
plt.yticks([])
plt.xticks([])
plt.show()
GAT
GAT原理
1.Attention是什么？
GAT是Graph Attention Networks的简称，即图注意力网络，借鉴于DNN的发展，将Attention应用于图网络是很自然的想法，在原始的GCN中，我们对俩节点$v_i,v_j$聚合时，会设置它们的权重为：
$$
w_{ij}=\frac{1}{\sqrt{d(v_i)}\sqrt{d(v_j)}}
$$
而Attention机制认为，这个权重应该由算法自己去学习，而不是显示的指定，所以在Attention机制下，权重可以被定义为如下表达：
$$
w_{i,j}=Attention(h_i,h_j,W)
$$
这里，$h_i,h_j$分别为$v_i,v_j$在当前层的向量表示，$W$是待学习参数，$Attention(h_i,h_j,W)$输出一个标量值，所以任意满足上面定义的表达式都可以看作是一种Attention，最简单的就是$h_i,h_j$向量做内积：$<h_i,h_j>$
2. GAT中的Attention
它的定义可以表示如下：
$$
e_{ij}=LeakyReLU(a^T[Wh_i||Wh_j])\
w_{ij}=\frac{exp(e_{ij})}{\sum_{k\in N(v_i)exp(e_{ik})}}
$$
首先，$h_i,h_j$通过矩阵$W$进行一次线性变换，然后通过$||$操作符将俩向量拼接成一个向量，接下来与一个同维度向量$a$做内积，最后通过非线性激活函数$LeakyReLU$得到一个标量$e_{ij}$，然后对其进行softmax归一化得到最终的权重值，按照加权求和的思路，节点$v_i$的新特征向量为：
$$
h’i=\sigma(\sum{j\in N(v_i)}w_{ij} Wh_j)
$$
通常我们会将单个attention过程，独立做多次（不同的$W,a$），然后将最终得到的多个新特征向量拼接起来（多头注意力）作为最终的新特征向量
实现
from code.gat import *#1.加载数据
dataset = CoraData().data
#如果有GPU则使用GPU
device = "cuda" if torch.cuda.is_available() else "cpu"
#接着预处理剩下的数据
x = dataset.x / dataset.x.sum(1, keepdims=True)
# 归一化数据，使得每一行和为1
tensor_x = torch.from_numpy(x).to(device)
tensor_y = torch.from_numpy(dataset.y).to(device)
tensor_train_mask = torch.from_numpy(dataset.trn_mask).to(device)
tensor_val_mask = torch.from_numpy(dataset.val_mask).to(device)
tensor_test_mask = torch.from_numpy(dataset.test_mask).to(device)
normalize_adjacency = dataset.adjacency
# 规范化邻接矩阵
indices = torch.from_numpy(np.asarray([normalize_adjacency.row, normalize_adjacency.col])).long()
values = torch.from_numpy(normalize_adjacency.data.astype(np.float32))
tensor_adjacency = torch.sparse.FloatTensor(indices, values, (2708, 2708)).to(device)Using Cached file: E:\datas\Algs\GNN\cora\processed_cora.pkl
Cached file: E:\datas\Algs\GNN\cora\processed_cora.pkl
#2.构建模型
model = GAT(1433, 16, 7, 0.2, 0.2, 4).to(device)#3.训练模型
learning_rate = 0.1
weight_decay = 5e-4
epochs = 5
# 损失函数使用交叉熵
criterion = nn.CrossEntropyLoss().to(device)
# 优化器使用Adam
optimizer = optim.Adam(model.parameters(), lr=learning_rate, weight_decay=weight_decay)
# 训练
loss_history = []
val_acc_history = []
model.train()
train_y = tensor_y[tensor_train_mask]
for epoch in range(epochs):
# 前向传播
logits = model(tensor_x,tensor_adjacency)
# 只选择训练节点进行监督
train_mask_logits = logits[tensor_train_mask]
# 计算损失值
loss = criterion(train_mask_logits, train_y)
# 反向传播计算参数的梯度
optimizer.zero_grad()
loss.backward()
# 使用优化方法进行梯度更新
optimizer.step()#4.查看效果
import warnings
warnings.filterwarnings("ignore",category=DeprecationWarning)
%matplotlib inline
#对X用tsne降维
from sklearn import manifold
tsne = manifold.TSNE(n_components=2,init="pca")
X_tsne = tsne.fit_transform(tensor_x.numpy())
#预测
pred = model(tensor_x,tensor_adjacency).max(1)[1].numpy()
#归一化显示
x_min, x_max = X_tsne.min(0), X_tsne.max(0)
X_norm = (X_tsne - x_min) / (x_max - x_min)
plt.figure(figsize=(12, 9))
plt.scatter(X_norm[:,0],X_norm[:,1],c=pred)
plt.yticks([])
plt.xticks([])
plt.show()
DGL
运行机制
为了更加高效的运行GNN，我们可以利用一些高效的图计算框架帮助我们训练模型，DGL（Deep Graph Library）便是一种比较方便的框架，它将所有的图计算过程拆分为了三个基本部分，分别介绍如下：
1.1 消息传递函数
该函数是将一条边以及与其关联的两个节点的信息进行聚合，然后将聚合后消息重新赋值到边上，可以用如下的表达式抽象表达：
$$
m_{uv}^{(t+1)}=\phi(x_u^{(t)},x_v^{(t)},w_{uv}^{(t)})
$$
其中，$w_{uv}^{(t)}$表示边$(u,v)$上的特征，$x_u^{(t)}$表示节点$u$上的特征，$x_v^{(t)}$表示节点$v$上的特征
1.2 聚合函数
聚合函数是将与训练节点关联的边上的消息，进行聚合：
$$
\rho_u^{t+1}=\rho({m_{uk}^{(t+1)}\mid k\in N(u)})
$$
这里，$N(u)$表示与节点$u$相连的邻居节点
1.3 更新函数
更新函数的作用是将聚合特征与节点的旧特征进行聚合，然后生成节点的新特征：
$$
x_u^{(t+1)}=\varphi(x_u^{(t)},\rho_u^{t+1})
$$
我们之前介绍的GCN，GAT，GraphSAGE便可分解为这三个基本操作函数，接下来我利用DGL库演示一下这3个基本操作
实践
2.1 构图：首先构建一张图，并为节点和边赋值
import dgl
import torchUsing backend: pytorch
u=torch.tensor([0,0,0,0,1,1,2,3,2,4,5,5,6,6,6,7,8])
v=torch.tensor([1,2,3,4,2,3,4,4,5,5,6,7,7,8,9,8,9])
g=dgl.graph((u,v))#转换为networkx可视化
%matplotlib inline
from matplotlib import pyplot as plt
import networkx as nx
plt.axis("off")
nx.draw_networkx(g.to_networkx())
plt.show()
#分别为节点和边赋值一个三维的向量
g.ndata["nx"]=torch.randn(g.num_nodes(),3)
g.edata["ex"]=torch.randn(g.num_edges(),3)#查看
g.ndata["nx"],g.edata["ex"]>>>
(tensor([[ 0.6239, 0.3987, -0.6238],
[-0.7141, -1.0818, -1.0757],
[-0.0540, 1.1078, 0.2700],
[ 0.5681, -1.0023, -1.4963],
[-1.3526, -0.5072, 0.3111],
[ 0.4039, 0.1909, 2.4836],
[ 0.2190, 0.9467, -0.6446],
[-0.5860, -1.7527, -1.0872],
[ 0.8450, 0.9458, -0.5495],
[ 1.3140, 0.4514, 0.5442]]),
tensor([[-0.5180, -0.1497, 0.4278],
[ 0.7970, -0.1222, -0.5810],
[-0.9885, 0.7971, -1.0056],
[-0.5377, 0.3229, -0.1410],
[ 1.2062, 1.3272, -0.4768],
[-0.6856, 0.9685, -1.3733],
[ 1.0140, -0.1059, 1.4300],
[-0.4088, 0.5824, -0.4151],
[ 1.4490, -1.0892, 0.2116],
[ 0.2986, -0.0652, -0.4363],
[ 0.7020, 0.6645, -1.1004],
[ 0.7326, 0.5491, 0.8222],
[-0.5815, -1.3774, 0.7640],
[ 1.1323, -1.4232, 0.2073],
[-0.3632, -1.3108, -1.2507],
[-0.7597, -1.1140, 0.2626],
[-0.8476, -1.2887, -0.7922]]))2.2 利用apply_edges进行消息传递
apply_edges可以完成第一个函数的操作，即将两节点特征和边特征进行某种操作，然后将结果保存回边上，我们先用dgl自带的api，将$u,v$节点的特征相加然后赋值到边上
g.apply_edges(dgl.function.u_add_v("nx","nx","add_x"))#第一个nx表示u上的nx特征，第二个表示v上的nx特征，add_x表示赋值到边上的特征
g.edata["add_x"]>>>
tensor([[-0.0902, -0.6831, -1.6995], [ 0.5699, 1.5065, -0.3538], [ 1.1919, -0.6036, -2.1202], [-0.7288, -0.1085, -0.3128], [-0.7681, 0.0260, -0.8057], [-0.1461, -2.0841, -2.5721], [-1.4066, 0.6007, 0.5811], [-0.7846, -1.5095, -1.1853], [ 0.3500, 1.2987, 2.7536], [-0.9487, -0.3163, 2.7946], [ 0.6229, 1.1375, 1.8389], [-0.1821, -1.5618, 1.3964], [-0.3670, -0.8060, -1.7318], [ 1.0640, 1.8925, -1.1941], [ 1.5330, 1.3981, -0.1005], [ 0.2589, -0.8069, -1.6367], [ 2.1590, 1.3972, -0.0053]])这个过程也可以写自定义函数进行操作
def message_func(edges): return {'new_add_x': edges.src['nx'] + edges.dst['nx']}g.apply_edges(message_func)g.edata["new_add_x"]>>>
tensor([[-0.0902, -0.6831, -1.6995], [ 0.5699, 1.5065, -0.3538], [ 1.1919, -0.6036, -2.1202], [-0.7288, -0.1085, -0.3128], [-0.7681, 0.0260, -0.8057], [-0.1461, -2.0841, -2.5721], [-1.4066, 0.6007, 0.5811], [-0.7846, -1.5095, -1.1853], [ 0.3500, 1.2987, 2.7536], [-0.9487, -0.3163, 2.7946], [ 0.6229, 1.1375, 1.8389], [-0.1821, -1.5618, 1.3964], [-0.3670, -0.8060, -1.7318], [ 1.0640, 1.8925, -1.1941], [ 1.5330, 1.3981, -0.1005], [ 0.2589, -0.8069, -1.6367], [ 2.1590, 1.3972, -0.0053]])2.3 利用update_all组合消息传递函数与聚合函数
update_all将消息传递和聚合函数一并进行操作，下面演示先将邻居节点特征加到边，然后再将边特征加到节点
g.update_all(dgl.function.u_add_v("nx","nx","add_x"), dgl.function.sum("add_x","add_edge_x"))g.ndata["add_edge_x"]>>>
tensor([[ 0.0000, 0.0000, 0.0000], [-0.0902, -0.6831, -1.6995], [-0.1982, 1.5326, -1.1595], [ 1.0459, -2.6876, -4.6922], [-2.9200, -1.0173, -0.9170], [-0.5987, 0.9824, 5.5482], [ 0.6229, 1.1375, 1.8389], [-0.5491, -2.3679, -0.3355], [ 1.3229, 1.0856, -2.8309], [ 3.6919, 2.7953, -0.1058]])当然，也可以自定义
def reduce_func(nodes): return {'new_add_edge_x': torch.sum(nodes.mailbox['add_x'], dim=1)}g.update_all(dgl.function.u_add_v("nx","nx","add_x"), reduce_func)g.ndata["new_add_edge_x"]>>>
tensor([[ 0.0000, 0.0000, 0.0000], [-0.0902, -0.6831, -1.6995], [-0.1982, 1.5326, -1.1595], [ 1.0459, -2.6876, -4.6922], [-2.9200, -1.0173, -0.9170], [-0.5987, 0.9824, 5.5482], [ 0.6229, 1.1375, 1.8389], [-0.5491, -2.3679, -0.3355], [ 1.3229, 1.0856, -2.8309], [ 3.6919, 2.7953, -0.1058]])2.3 更新函数：最后组合聚合特征和原特征
这部分操作就很容易了，因为聚合特征和原特征都在节点上了，所以我们直接操作即可，比如相加
g.ndata["nx"]>>>
tensor([[ 0.6239, 0.3987, -0.6238],
[-0.7141, -1.0818, -1.0757],
[-0.0540, 1.1078, 0.2700],
[ 0.5681, -1.0023, -1.4963],
[-1.3526, -0.5072, 0.3111],
[ 0.4039, 0.1909, 2.4836],
[ 0.2190, 0.9467, -0.6446],
[-0.5860, -1.7527, -1.0872],
[ 0.8450, 0.9458, -0.5495],
[ 1.3140, 0.4514, 0.5442]])g.ndata["nx"]=g.ndata["nx"]+g.ndata["add_edge_x"]
g.ndata["nx"]#注意从第二行开始看>>>
tensor([[ 0.6239, 0.3987, -0.6238],
[-0.8044, -1.7649, -2.7753],
[-0.2522, 2.6404, -0.8895],
[ 1.6139, -3.6899, -6.1886],
[-4.2726, -1.5244, -0.6059],
[-0.1948, 1.1733, 8.0318],
[ 0.8419, 2.0842, 1.1943],
[-1.1352, -4.1206, -1.4227],
[ 2.1679, 2.0314, -3.3804],
[ 5.0059, 3.2467, 0.4384]])PageRank算法
关于PageRank的原理，大家可以参考>>note
如图，以节点A举例，他的PR更新公示可以表示为：
$$
PR_A^{(t+1)}=w_{BA}PR_B^{(t)}+w_{CA}PR_C^{(t)}
$$
这里，$w_{BA}$表示边$(B,A)$上的权重，在默认情况下，我们可以设置为节点$B$的出度的倒数，而$PR_{*}$则表示某节点的PR值，下面利用DGL来计算PR，节点编号0 ~ 3分别对应上面的节点A ~ D
import dgl
import torchUsing backend: pytorch
构建图
u=torch.tensor([0,0,0,1,1,2,3,3])
v=torch.tensor([1,2,3,0,3,0,1,2])
g=dgl.graph((u,v))计算边权重
g.ndata["out_degrees"]=g.out_degrees()def message_func(edges):
return {"weight":1.0/edges.src["out_degrees"]}
g.apply_edges(message_func)
g.edata["weight"]>>>
tensor([0.3333, 0.3333, 0.3333, 0.5000, 0.5000, 1.0000, 0.5000, 0.5000])计算PR
#随机初始化一组PR
prs=torch.exp(torch.randn(4))
prs=prs/torch.sum(prs)
prs>>>
tensor([0.1702, 0.3912, 0.1391, 0.2994])g.ndata["pr"]=prsfor _ in range(100):
g.update_all(dgl.function.u_dot_e("pr","weight","weighted_pr"),#将源节点上的pr与边上的weight相乘后放到边上的weighted_pr变量中
dgl.function.sum("weighted_pr","pr"))#将所有入边上的weighted_pr求和后赋值到目标节点的pr变量中g.ndata["pr"]>>>
tensor([0.3333, 0.2222, 0.2222, 0.2222])上面的实现不够严谨，为了防止没有出度或者没有入度的节点，其实需要在聚合的时候再添加一个平滑项（见上面链接中的note）
GCN的DGL实现
我们先拎GCN出来看看，如何将其拆分为3个基本函数的形式，我们先回顾一下它的矩阵更新形式：
$$
X^{(t+1)}=\sigma(\tilde{L}_{sym}X^{(t)}W^{(t)})
$$
我们可以如下拆解：
消息传递函数
$$
m_{uv}^{(t+1)}=\frac{X_{v,:}^{(t)}W^{(t)}}{\sqrt{d_u}\cdot \sqrt{d_v}}
$$
这里，$d_u,d_v$分别表示节点$u,v$的度，$X_{v,:}^{(t)}$表示节点$v$的第$t$层的特征向量（这里是行向量表示），$W^{(t)}$是它在第$t$层的训练参数
聚合函数
$$
\rho_u^{(t+1)}=\sum_{v\in N(u)}m_{uv}^{(t+1)}
$$
这里，只是简单将每条边上的消息相加
更新函数
$$
X_{u,:}^{(t+1)}=\sigma(\rho_u^{(t+1)})
$$
就在聚合函数的基础上简单添加了一个激活函数即可
代码
只需要在之前gcn.py的基础上修改即可，下面说下主要修改的地方
1 将连接矩阵修改为DGLGraph
@staticmethod
def build_dgl_graph(adj_dict):
"""根据邻接表创建邻接矩阵"""
edge_index = []
for key in adj_dict.keys():
edge_index.append([key, key])
for item in adj_dict[key]:
edge_index.append([key, item])
edge_index.append([item, key])
u, v = torch.tensor([item[0] for item in edge_index]), torch.tensor([item[1] for item in edge_index])
return dgl.graph((u, v))2 GraphConvolution的Forward修改为DGL实现（核心）
class GraphConvolution(nn.Module):
def __init__(self, input_dim, output_dim, use_bias=True):
super(GraphConvolution, self).__init__()
self.input_dim = input_dim
self.output_dim = output_dim
self.use_bias = use_bias
self.weight = nn.Parameter(torch.Tensor(input_dim, output_dim))
if self.use_bias:
self.bias = nn.Parameter(torch.Tensor(output_dim))
else:
self.register_parameter('bias', None)
self.reset_parameters()
def reset_parameters(self):
nn.init.kaiming_uniform_(self.weight)
if self.use_bias:
nn.init.zeros_(self.bias)
def message_func(self, edges):
message = torch.mm(
edges.src["in_feature"] / torch.sqrt(edges.src['degree'] * edges.dst['degree']).reshape((-1, 1)),
self.weight)
if self.use_bias:
message += self.bias
return {"m": message}
def forward(self, dgl_graph: dgl.graph, input_feature):
with dgl_graph.local_scope():
dgl_graph.ndata["in_feature"] = input_feature
dgl_graph.ndata["degree"] = dgl_graph.in_degrees()
dgl_graph.update_all(
self.message_func,
dgl.function.sum("m", "neigh_sum")
)
return dgl_graph.ndata["neigh_sum"]from code.gcn_dgl import *Using backend: pytorch
#1.加载数据
dataset = CoraData().dataUsing Cached file: E:\datas\Algs\GNN\cora\processed_cora_dgl.pkl
Cached file: E:\datas\Algs\GNN\cora\processed_cora_dgl.pkl
dataset.dgl_graph>>>
Graph(num_nodes=2708, num_edges=24424,
ndata_schemes={}
edata_schemes={})#如果有GPU则使用GPUdevice = "cuda" if torch.cuda.is_available() else "cpu"#接着预处理剩下的数据x = dataset.x / dataset.x.sum(1, keepdims=True)# 归一化数据，使得每一行和为1tensor_x = torch.from_numpy(x).to(device)tensor_y = torch.from_numpy(dataset.y).to(device)tensor_train_mask = torch.from_numpy(dataset.trn_mask).to(device)tensor_val_mask = torch.from_numpy(dataset.val_mask).to(device)tensor_test_mask = torch.from_numpy(dataset.test_mask).to(device)#2.构建模型model = GCNNet().to(device)def accuracy(mask): model.eval() with torch.no_grad(): logits = model(dataset.dgl_graph, tensor_x) test_mask_logits = logits[mask] predict_y = test_mask_logits.max(1)[1] accuracy = torch.eq(predict_y, tensor_y[mask]).float().mean() return accuracy#3.训练模型
# 超参数定义
learning_rate = 0.01
weight_decay = 5e-4
epochs = 200
# 损失函数使用交叉熵
criterion = nn.CrossEntropyLoss().to(device)
# 优化器使用Adam
optimizer = optim.Adam(model.parameters(), lr=learning_rate, weight_decay=weight_decay)
# 训练
trn_acc_history = []
val_acc_history = []
model.train()
train_y = tensor_y[tensor_train_mask]
for epoch in range(epochs):
# 前向传播
logits = model(dataset.dgl_graph, tensor_x)
# 只选择训练节点进行监督
train_mask_logits = logits[tensor_train_mask]
# 计算损失值
loss = criterion(train_mask_logits, train_y)
# 反向传播计算参数的梯度
optimizer.zero_grad()
loss.backward()
# 使用优化方法进行梯度更新
optimizer.step()
# 计算当前模型在训练集上的准确率
train_acc = accuracy(tensor_train_mask)
trn_acc_history.append(train_acc)
# 计算当前模型在验证集上的准确率
val_acc = accuracy(tensor_val_mask)
val_acc_history.append(val_acc)import matplotlib.pyplot as plt
%matplotlib inline
plt.plot(val_acc_history)
plt.plot(trn_acc_history)
plt.legend(['val acc','trn acc'])>>>
<matplotlib.legend.Legend at 0x1a3b8099f60>
异质图RGCN_节点预测
原理
我们通常处理的更多的还是异构图，异构图包含了多种类型的节点以及多种类型的边，我们之前介绍的GCN/GAT/SAGE目前都只能应用于同质图（只有一种节点类型，一种边类型），那如何将同质图的算法扩展到异构图呢？一种通常的做法是：
（1）将异构图按照边的类别将切分为多个子图；
（2）然后分别在这些子图上运行图算法；
（3）最后将各子图的结果再进行一次聚合
相较于之前，我们就再多一次对关系的聚合即可：
$$
h_{i}^{(t+1)}=AGG({GNN_r(h_i^{(t)})\mid r\in R})
$$
这里，$GNN_r(h_i^{(t)})$表达在关系$r$上对节点$h_i^{(t)}$运行算法$GNN$后的结果，$R$表示所有关系，$AGG(\cdot)$表示对所有结果进行某种聚合，比如max,mean,sum等
实现
下面利用官方的示例以及API演示如何构造异构图，如何构造RGCN，并完成节点分类的任务
1 构造异构图
随机构造了1000个用户，500个商品，以及用户与用户之间的follow关系，用户与商品之间的click和dislike关系
import numpy as np
import torch
import dgl
n_users = 1000
n_items = 500
n_follows = 3000
n_clicks = 5000
n_dislikes = 500
n_hetero_features = 10
n_user_classes = 5
n_max_clicks = 10
follow_src = np.random.randint(0, n_users, n_follows)
follow_dst = np.random.randint(0, n_users, n_follows)
click_src = np.random.randint(0, n_users, n_clicks)
click_dst = np.random.randint(0, n_items, n_clicks)
dislike_src = np.random.randint(0, n_users, n_dislikes)
dislike_dst = np.random.randint(0, n_items, n_dislikes)
hetero_graph = dgl.heterograph({
('user', 'follow', 'user'): (follow_src, follow_dst),
('user', 'followed-by', 'user'): (follow_dst, follow_src),
('user', 'click', 'item'): (click_src, click_dst),
('item', 'clicked-by', 'user'): (click_dst, click_src),
('user', 'dislike', 'item'): (dislike_src, dislike_dst),
('item', 'disliked-by', 'user'): (dislike_dst, dislike_src)})
hetero_graph.nodes['user'].data['feature'] = torch.randn(n_users, n_hetero_features)
hetero_graph.nodes['item'].data['feature'] = torch.randn(n_items, n_hetero_features)
hetero_graph.nodes['user'].data['label'] = torch.randint(0, n_user_classes, (n_users,))
hetero_graph.edges['click'].data['label'] = torch.randint(1, n_max_clicks, (n_clicks,)).float()
# 在user类型的节点和click类型的边上随机生成训练集的掩码
hetero_graph.nodes['user'].data['train_mask'] = torch.zeros(n_users, dtype=torch.bool).bernoulli(0.6)
hetero_graph.edges['click'].data['train_mask'] = torch.zeros(n_clicks, dtype=torch.bool).bernoulli(0.6)Using backend: pytorch
2 构造模型
这里对每种关系都训练的GCN模型，然后每种关系的结果采用sum进行聚合
import dgl.nn as dglnn
import torch.nn as nn
import torch.nn.functional as F
class RGCN(nn.Module):
def __init__(self, in_feats, hid_feats, out_feats, rel_names):
super().__init__()
# 实例化HeteroGraphConv，in_feats是输入特征的维度，out_feats是输出特征的维度，aggregate是聚合函数的类型
self.conv1 = dglnn.HeteroGraphConv({
rel: dglnn.GraphConv(in_feats, hid_feats)
for rel in rel_names}, aggregate='sum')
self.conv2 = dglnn.HeteroGraphConv({
rel: dglnn.GraphConv(hid_feats, out_feats)
for rel in rel_names}, aggregate='sum')
def forward(self, graph, inputs):
# 输入是节点的特征字典
h = self.conv1(graph, inputs)
h = {k: F.relu(v) for k, v in h.items()}
h = self.conv2(graph, h)
return h3 训练模型
model = RGCN(n_hetero_features, 20, n_user_classes, hetero_graph.etypes)
user_feats = hetero_graph.nodes['user'].data['feature']
item_feats = hetero_graph.nodes['item'].data['feature']
labels = hetero_graph.nodes['user'].data['label']
train_mask = hetero_graph.nodes['user'].data['train_mask']
node_features = {'user': user_feats, 'item': item_feats}
opt = torch.optim.Adam(model.parameters())
for epoch in range(5):
model.train()
# 使用所有节点的特征进行前向传播计算，并提取输出的user节点嵌入
logits = model(hetero_graph, node_features)['user']
# 计算损失值
loss = F.cross_entropy(logits[train_mask], labels[train_mask])
# 进行反向传播计算
opt.zero_grad()
loss.backward()
opt.step()
print(loss.item())>>>
1.8662775754928589
1.851954698562622
1.8382809162139893
1.8252463340759277
1.812849998474121异质图RGCN_边预测
原理
边的预测我们可以基于它所关联的俩节点来计算，对于单个输出预测，等价于我们需要定义如下的一个函数：
$$
score_{(i,j)}=g(h_i,h_j)
$$
即构造一个函数，输入俩向量$h_i,h_j$（分别表示俩节点特征），然后输出一个标量（表示边的输出），最简单的我们可以使用内积$<h_i,h_j>$，或者将$h_i,h_j$拼接后再进行一次线性变换$w^T(h_i||h_j)$，或者将$h_i,h_j$相加后再进行一次线性变换$w^T(h_i+h_j)$，这里可以是任意你能想到的方式（不过要可导），而这个操作我们可以利用dgl的apply_edges这个api来实现，比如下面分别实现内积和线性变换的操作
import dgl.function as fn
from torch import nn
class HeteroDotProductPredictor(nn.Module):
def forward(self, graph, h, etype):
with graph.local_scope():
graph.ndata['h'] = h #一次性为所有节点类型的 'h'赋值
graph.apply_edges(fn.u_dot_v('h', 'h', 'score'), etype=etype)
return graph.edges[etype].data['score']
class MLPPredictor(nn.Module):
def __init__(self, in_features, out_classes):
super().__init__()
self.W = nn.Linear(in_features * 2, out_classes)
def apply_edges(self, edges):
h_u = edges.src['h']
h_v = edges.dst['h']
score = self.W(torch.cat([h_u, h_v], 1))
return {'score': score}
def forward(self, graph, h, etype):
with graph.local_scope():
graph.ndata['h'] = h #一次性为所有节点类型的 'h'赋值
graph.apply_edges(self.apply_edges, etype=etype)
return graph.edges[etype].data['score']Using backend: pytorch实现
下面与前一节的实现一样的内容就直接贴进来了
import numpy as np
import torch
import dgl
n_users = 1000
n_items = 500
n_follows = 3000
n_clicks = 5000
n_dislikes = 500
n_hetero_features = 10
n_user_classes = 5
n_max_clicks = 10
follow_src = np.random.randint(0, n_users, n_follows)
follow_dst = np.random.randint(0, n_users, n_follows)
click_src = np.random.randint(0, n_users, n_clicks)
click_dst = np.random.randint(0, n_items, n_clicks)
dislike_src = np.random.randint(0, n_users, n_dislikes)
dislike_dst = np.random.randint(0, n_items, n_dislikes)
hetero_graph = dgl.heterograph({
('user', 'follow', 'user'): (follow_src, follow_dst),
('user', 'followed-by', 'user'): (follow_dst, follow_src),
('user', 'click', 'item'): (click_src, click_dst),
('item', 'clicked-by', 'user'): (click_dst, click_src),
('user', 'dislike', 'item'): (dislike_src, dislike_dst),
('item', 'disliked-by', 'user'): (dislike_dst, dislike_src)})
hetero_graph.nodes['user'].data['feature'] = torch.randn(n_users, n_hetero_features)
hetero_graph.nodes['item'].data['feature'] = torch.randn(n_items, n_hetero_features)
hetero_graph.nodes['user'].data['label'] = torch.randint(0, n_user_classes, (n_users,))
hetero_graph.edges['click'].data['label'] = torch.randint(1, n_max_clicks, (n_clicks,)).float()
# 在user类型的节点和click类型的边上随机生成训练集的掩码
hetero_graph.nodes['user'].data['train_mask'] = torch.zeros(n_users, dtype=torch.bool).bernoulli(0.6)
hetero_graph.edges['click'].data['train_mask'] = torch.zeros(n_clicks, dtype=torch.bool).bernoulli(0.6)import dgl.nn as dglnn
import torch.nn.functional as F
class RGCN(nn.Module):
def __init__(self, in_feats, hid_feats, out_feats, rel_names):
super().__init__()
# 实例化HeteroGraphConv，in_feats是输入特征的维度，out_feats是输出特征的维度，aggregate是聚合函数的类型
self.conv1 = dglnn.HeteroGraphConv({
rel: dglnn.GraphConv(in_feats, hid_feats)
for rel in rel_names}, aggregate='sum')
self.conv2 = dglnn.HeteroGraphConv({
rel: dglnn.GraphConv(hid_feats, out_feats)
for rel in rel_names}, aggregate='sum')
def forward(self, graph, inputs):
# 输入是节点的特征字典
h = self.conv1(graph, inputs)
h = {k: F.relu(v) for k, v in h.items()}
h = self.conv2(graph, h)
return h在RGCN的基础上，我们可以继续构建对边的预测任务
class Model(nn.Module):
def __init__(self, in_features, hidden_features, out_features, rel_names):
super().__init__()
self.rgcn = RGCN(in_features, hidden_features, out_features, rel_names)
self.pred = HeteroDotProductPredictor()
def forward(self, g, x, etype):
h = self.rgcn(g, x)#这里得到RGCN后各节点的特征
return self.pred(g, h, etype)#然后求得边的score模型训练
model = Model(10, 20, 5, hetero_graph.etypes)
user_feats = hetero_graph.nodes['user'].data['feature']
item_feats = hetero_graph.nodes['item'].data['feature']
label = hetero_graph.edges['click'].data['label']
train_mask = hetero_graph.edges['click'].data['train_mask']
node_features = {'user': user_feats, 'item': item_feats}opt = torch.optim.Adam(model.parameters())
for epoch in range(5):
pred = model(hetero_graph, node_features, 'click')
loss = ((pred[train_mask] - label[train_mask]) ** 2).mean()
opt.zero_grad()
loss.backward()
opt.step()
print(loss.item())39.65708541870117
37.67030715942383
35.77607727050781
33.9720344543457
32.25625228881836
链接预测
原理
链接预测是预测边的存在性，注意它与边预测任务很不同，边预测是去预测已存在的边的属性。但通过负采样的技巧，我们可以将链接预测的问题转换为边预测的问题，可以看作：
$$
链接预测=负采样+边预测
$$
我们可以这样理解，如果两节点间存在边，那么我们定义该边上的属性为1，如果不存在边那么我们定义该边上的属性为0，所以我们将链接预测问题就转换为了边上的1/0预测问题，如果俩节点上的预测值靠近1，我们就可以认为它们之间存在一条边，如果预测值靠近0，就认为它们之间不存在边。但是“不存在的边”的量往往很大，这需要考虑任意两两之间的连接，所以我们采用负采样，从所有不存在的边中随机采样部分出来训练，如下示例图：
对于上面的假设，我们可以类似于logistic任务，使用交叉熵损失函数：
$$
L=-log\sigma(y_{u,v})-\sum{[1-log(y_{u,k})]\mid k\in P(u)}
$$
这里，$u,v$是存在连接的点，$P(u)$是对$u$的负采样点的集合，$y_{u,v}$类似于上一节输入两向量，输出一个标量的函数，比如做内积，而$\sigma(\cdot)$是sigmoid函数，将输出约束在(0,1)之间，除了交叉熵，我们还可以选择其他函数，参考>>
实现
这里需要实现的内容其实相比上一节主要多了两部分内容：
（1）第一部分是多了负采样；
（2）另一部分是需要修改损失函数的定义
import numpy as np
import torch
import dgl
import dgl.nn as dglnn
import torch.nn as nn
import torch.nn.functional as F
import dgl.function as fnUsing backend: pytorch
#1.生成异构图
n_users = 1000
n_items = 500
n_follows = 3000
n_clicks = 5000
n_dislikes = 500
n_hetero_features = 10
n_user_classes = 5
n_max_clicks = 10
follow_src = np.random.randint(0, n_users, n_follows)
follow_dst = np.random.randint(0, n_users, n_follows)
click_src = np.random.randint(0, n_users, n_clicks)
click_dst = np.random.randint(0, n_items, n_clicks)
dislike_src = np.random.randint(0, n_users, n_dislikes)
dislike_dst = np.random.randint(0, n_items, n_dislikes)
hetero_graph = dgl.heterograph({
('user', 'follow', 'user'): (follow_src, follow_dst),
('user', 'followed-by', 'user'): (follow_dst, follow_src),
('user', 'click', 'item'): (click_src, click_dst),
('item', 'clicked-by', 'user'): (click_dst, click_src),
('user', 'dislike', 'item'): (dislike_src, dislike_dst),
('item', 'disliked-by', 'user'): (dislike_dst, dislike_src)})
hetero_graph.nodes['user'].data['feature'] = torch.randn(n_users, n_hetero_features)
hetero_graph.nodes['item'].data['feature'] = torch.randn(n_items, n_hetero_features)
hetero_graph.nodes['user'].data['label'] = torch.randint(0, n_user_classes, (n_users,))
hetero_graph.edges['click'].data['label'] = torch.randint(1, n_max_clicks, (n_clicks,)).float()
# 在user类型的节点和click类型的边上随机生成训练集的掩码
hetero_graph.nodes['user'].data['train_mask'] = torch.zeros(n_users, dtype=torch.bool).bernoulli(0.6)
hetero_graph.edges['click'].data['train_mask'] = torch.zeros(n_clicks, dtype=torch.bool).bernoulli(0.6)#2.定义模型
class RGCN(nn.Module):
def __init__(self, in_feats, hid_feats, out_feats, rel_names):
super().__init__()
# 实例化HeteroGraphConv，in_feats是输入特征的维度，out_feats是输出特征的维度，aggregate是聚合函数的类型
self.conv1 = dglnn.HeteroGraphConv({
rel: dglnn.GraphConv(in_feats, hid_feats)
for rel in rel_names}, aggregate='sum')
self.conv2 = dglnn.HeteroGraphConv({
rel: dglnn.GraphConv(hid_feats, out_feats)
for rel in rel_names}, aggregate='sum')
def forward(self, graph, inputs):
# 输入是节点的特征字典
h = self.conv1(graph, inputs)
h = {k: F.relu(v) for k, v in h.items()}
h = self.conv2(graph, h)
return h
class HeteroDotProductPredictor(nn.Module):
def forward(self, graph, h, etype):
# h是从5.1节中对异构图的每种类型的边所计算的节点表示
with graph.local_scope():
graph.ndata['h'] = h
graph.apply_edges(fn.u_dot_v('h', 'h', 'score'), etype=etype)
return graph.edges[etype].data['score']
class Model(nn.Module):
def __init__(self, in_features, hidden_features, out_features, rel_names):
super().__init__()
self.sage = RGCN(in_features, hidden_features, out_features, rel_names)
self.pred = HeteroDotProductPredictor()
def forward(self, g, neg_g, x, etype):
h = self.sage(g, x)
return self.pred(g, h, etype), self.pred(neg_g, h, etype)#3.定义负采样函数，将负样本采样为另外一张图
def construct_negative_graph(graph, k, etype):
utype, _, vtype = etype
src, dst = graph.edges(etype=etype)
neg_src = src.repeat_interleave(k)
neg_dst = torch.randint(0, graph.num_nodes(vtype), (len(src) * k,))
return dgl.heterograph(
{etype: (neg_src, neg_dst)},
num_nodes_dict={ntype: graph.num_nodes(ntype) for ntype in graph.ntypes})#4.定义损失函数
def compute_loss(pos_score, neg_score):
# 间隔损失
n_edges = pos_score.shape[0]
return (1 - pos_score.unsqueeze(1) + neg_score.view(n_edges, -1)).clamp(min=0).mean()#5.训练模型
k = 5
model = Model(10, 20, 5, hetero_graph.etypes)
user_feats = hetero_graph.nodes['user'].data['feature']
item_feats = hetero_graph.nodes['item'].data['feature']
node_features = {'user': user_feats, 'item': item_feats}
opt = torch.optim.Adam(model.parameters())
for epoch in range(5):
negative_graph = construct_negative_graph(hetero_graph, k, ('user', 'click', 'item'))#这里只对"click"关系进行预测
pos_score, neg_score = model(hetero_graph, negative_graph, node_features, ('user', 'click', 'item'))
loss = compute_loss(pos_score, neg_score)
opt.zero_grad()
loss.backward()
opt.step()
print(loss.item())>>>
1.327864170074463
1.3069148063659668
1.277003288269043
1.2585861682891846
1.246128797531128整图预测
原理
整图预测是针对图层面的学习任务，比如判断某药物分子是否具有某种理化性质，再比如判断某社团是否具有欺诈可能，这需要我们对整个图提取它的特征表示，然后再基于此构建我们的学习任务，图的整体特征无外乎来源于三部分：1）节点特征；2）边特征；3）结构信息，基于这些信息，我们可以通过许多方式来构建图特征，DGL提供了一些简单的API，比如对各节点特征求和/求平均/pooling等，这可以方便我们构建一些基准图预测模型，下面我们利用对节点特征求平均的方式构建图特征，这可以通过dgl.mean_nodes这个API很方便的实现，它相当于做了如下计算：
$$
h_g=\frac{1}{|V|}\sum_{v\in V }h_v
$$
$h_v$表示节点$v$的特征，然后基于$h_g$特征向量，构建我们预测模型
实现
利用dgl自带的MiniGCDataset数据集，它包括如下的8种类别的图结构
#1.导入数据
import dgl
import torch
from dgl.data import MiniGCDataset
import matplotlib.pyplot as plt
import networkx as nx
#这里，随机构造了80个图，每个图是少10条边，最多30条边
dataset = MiniGCDataset(80, 10, 20)
graph, label = dataset[0]
#绘制图像
%matplotlib inline
fig, ax = plt.subplots()
nx.draw(graph.to_networkx(), ax=ax)
ax.set_title('Class: {:d}'.format(label))
plt.show()Using backend: pytorch
#2.定义模型
from dgl.nn.pytorch import GraphConv
import torch.nn.functional as F
from torch import nn
class Classifier(nn.Module):
def __init__(self, in_dim, hidden_dim, n_classes):
super(Classifier, self).__init__()
self.conv1 = GraphConv(in_dim, hidden_dim)
self.conv2 = GraphConv(hidden_dim, hidden_dim)
self.classify = nn.Linear(hidden_dim, n_classes)#线性分类器
def forward(self, g):
# 以节点度作为初始节点特征。对于无向图，入度与外度相同。
h = g.in_degrees().view(-1, 1).float()
# 执行图形卷积和激活函数
h = F.relu(self.conv1(g,h))
h = F.relu(self.conv2(g,h))
g.ndata['h'] = h
# 通过对所有节点表示求平均来计算图形表示。
hg = dgl.mean_nodes(g, 'h')
return self.classify(hg)#3.训练
import torch.optim as optim
from torch.utils.data import DataLoader
# 将多张图合并为一张图
def collate(samples):
# The input `samples` is a list of pairs (graph, label).
graphs, labels = map(list, zip(*samples)) #把一批图 zip成 列表对象
batched_graph = dgl.batch(graphs)#合并为一张图
return batched_graph, torch.tensor(labels)
# 训练集/测试集
trainset = MiniGCDataset(320, 10, 20)
testset = MiniGCDataset(80, 10, 20)
#batch训练
data_loader = DataLoader(trainset, batch_size=32, shuffle=True,
collate_fn=collate)
# 构建模型
model = Classifier(1, 256, trainset.num_classes)
loss_func = nn.CrossEntropyLoss()
optimizer = optim.Adam(model.parameters(), lr=0.001)
model.train()
epoch_losses = []
for epoch in range(100):
epoch_loss = 0
for i, (bg, label) in enumerate(data_loader):
prediction = model(bg)
loss = loss_func(prediction, label.long())
optimizer.zero_grad()
loss.backward()
optimizer.step()
epoch_loss += loss.detach().item()
epoch_loss /= (i + 1)
# print('Epoch {}, loss {:.4f}'.format(epoch, epoch_loss))
epoch_losses.append(epoch_loss)
plt.plot(epoch_losses)
plt.legend(["loss"])>>>
<matplotlib.legend.Legend at 0x2658c2b9dd8>
#4.测试
model.eval()
test_X, test_Y = map(list, zip(*testset))
test_bg = dgl.batch(test_X)
test_Y = torch.tensor(test_Y).float().view(-1, 1)
pred_Y = torch.max(model(test_bg), 1)[1].view(-1, 1)
print('Accuracy of argmax predictions on the test set: {:4f}%'.format(
(test_Y == pred_Y.float()).sum().item() / len(test_Y) * 100))Accuracy of argmax predictions on the test set: 72.500000%
#5.查看混淆矩阵
from sklearn.metrics import confusion_matrix
confusion_matrix(test_Y, pred_Y)>>>
array([[10, 0, 0, 0, 0, 0, 0, 0],
[ 0, 5, 0, 0, 3, 2, 0, 0],
[ 0, 0, 10, 0, 0, 0, 0, 0],
[ 0, 0, 0, 7, 0, 0, 3, 0],
[ 0, 0, 3, 0, 0, 0, 0, 7],
[ 0, 0, 0, 0, 2, 6, 0, 2],
[ 0, 0, 0, 0, 0, 0, 10, 0],
[ 0, 0, 0, 0, 0, 0, 0, 10]], dtype=int64)批量采样训练
实际业务中，我们需要处理的图往往很大，可能会有上亿的节点和边，如果把这些数据进行全量训练，GPU显存很难放的下，所以我们需要使用类似于DNN中那样的随机批量学习的方式进行训练，与DNN中的批量学习不同，GNN对单个训练样本的训练还需要利用到它的邻居节点，而且每多增加一层网络，所需的邻居样本还要往外扩展一层，所以对于$k$层的GNN网络，我们需要对训练样本进行$k$阶的子图采样操作（回想一下之前GraphSAGE代码中采样…），借助于DGL的api，我们只需要多添加2行代码就可以了…
#1.准备数据
import numpy as np
import torch
import dgl
import torch.nn as nn
import torch.nn.functional as F
from dgl.nn.pytorch import HeteroGraphConv, GraphConv
n_users = 1000
n_items = 500
n_follows = 3000
n_clicks = 5000
n_dislikes = 500
n_hetero_features = 10
n_user_classes = 5
n_max_clicks = 10
follow_src = np.random.randint(0, n_users, n_follows)
follow_dst = np.random.randint(0, n_users, n_follows)
click_src = np.random.randint(0, n_users, n_clicks)
click_dst = np.random.randint(0, n_items, n_clicks)
dislike_src = np.random.randint(0, n_users, n_dislikes)
dislike_dst = np.random.randint(0, n_items, n_dislikes)
hetero_graph = dgl.heterograph({
('user', 'follow', 'user'): (follow_src, follow_dst),
('user', 'followed-by', 'user'): (follow_dst, follow_src),
('user', 'click', 'item'): (click_src, click_dst),
('item', 'clicked-by', 'user'): (click_dst, click_src),
('user', 'dislike', 'item'): (dislike_src, dislike_dst),
('item', 'disliked-by', 'user'): (dislike_dst, dislike_src)})
hetero_graph.nodes['user'].data['feature'] = torch.randn(n_users, n_hetero_features)
hetero_graph.nodes['item'].data['feature'] = torch.randn(n_items, n_hetero_features)
hetero_graph.nodes['user'].data['label'] = torch.randint(0, n_user_classes, (n_users,))
hetero_graph.edges['click'].data['label'] = torch.randint(1, n_max_clicks, (n_clicks,)).float()
# 在user类型的节点和click类型的边上随机生成训练集的掩码
hetero_graph.nodes['user'].data['train_mask'] = torch.zeros(n_users, dtype=torch.bool).bernoulli(0.6)
hetero_graph.edges['click'].data['train_mask'] = torch.zeros(n_clicks, dtype=torch.bool).bernoulli(0.6)
user_feats = hetero_graph.nodes['user'].data['feature']
item_feats = hetero_graph.nodes['item'].data['feature']
labels = hetero_graph.nodes['user'].data['label']
train_mask = hetero_graph.nodes['user'].data['train_mask']
train_idx = torch.nonzero(train_mask, as_tuple=False).squeeze()Using backend: pytorch
我们使用MultiLayerFullNeighborSampler进行采样，它会采样当前节点的所有邻居节点，利用NodeDataLoader进行数据的批量读取
#2.定义采样器
sampler = dgl.dataloading.MultiLayerFullNeighborSampler(2)#采样2阶子图，对应了GNN中2层网络dataloader = dgl.dataloading.NodeDataLoader(hetero_graph, {"user": train_idx}, sampler, batch_size=128, shuffle=True,num_workers=0)通过对dataloader迭代，我们每次可以取出input_nodes, output_nodes, blocks这三个变量，其中：
input_nodes：包括训练所需的所有节点ID
output_nodes：包括训练目标的节点，对应上面128个随机的user节点
blocks：是个list,从blocks[0],blocks[1]….分别对应了节点的$k$阶子图，$k-1$阶子图…..直到这128个user节点自身的$0$阶子图
input_nodes, output_nodes, blocks = next(iter(dataloader))由于将原始的大图切分为了一个一个的block，所以对于模型定义中的forward阶段需要做一点修改，改动也很简单，将原始的全图变量，依层替换为对应的block即可
#3.定义模型
class RGCN(nn.Module):
def __init__(self, in_feats, hid_feats, out_feats, rel_names):
super().__init__()
# 实例化HeteroGraphConv，in_feats是输入特征的维度，out_feats是输出特征的维度，aggregate是聚合函数的类型
self.conv1 = HeteroGraphConv({
rel: GraphConv(in_feats, hid_feats)
for rel in rel_names}, aggregate='sum')
self.conv2 = HeteroGraphConv({
rel: GraphConv(hid_feats, out_feats)
for rel in rel_names}, aggregate='sum')
def forward(self, blocks, inputs):
# 输入是节点的特征字典
h = self.conv1(blocks[0], inputs)#2阶子图
h = {k: F.relu(v) for k, v in h.items()}
h = self.conv2(blocks[1], h)#1阶子图
return h#4.训练模型
#训练阶段没太大差异，注意输入、输出的具体格式
losses=[]
model = RGCN(n_hetero_features, 20, n_user_classes, hetero_graph.etypes)
opt = torch.optim.Adam(model.parameters(),lr=1e-2)
if __name__ == '__main__':
model.train()
for _ in range(20):
for input_nodes, output_nodes, blocks in dataloader:
# blocks = [b.to(torch.device('cuda')) for b in blocks]
input_features = blocks[0].srcdata['feature'] # returns a dict
output_labels = blocks[-1].dstdata['label'] # returns a dict
output_predictions = model(blocks, input_features)
loss = F.cross_entropy(output_predictions['user'], output_labels['user'])
opt.zero_grad()
loss.backward()
opt.step()
losses.append(loss.item())import matplotlib.pyplot as plt
%matplotlib inline
plt.plot(losses)
plt.legend(["loss"])>>>
<matplotlib.legend.Legend at 0x281a2e53fd0>
图网络解释
原论文：The graph neural network model
GNN
很多领域的数据的底层关系可以表示为图结构，如计算机视觉、分子化学、分子生物学、模式识别、数据挖掘等领域。
最简单的图结构为单节点图，以及作为节点序列的图，更复杂的图结构包括树、无环图、带环图等。
关于图的任务可以分为两类：
基于图的任务
graph-focused：以图为单位，直接在图结构的数据上实现分类或者回归。如：图表示化学化合物，每个顶点表示一个原子或者化学基团、边表示化学键。模型可以用于评估被检测的化合物的类别。
基于节点的任务
node-focused：以节点为单位，在每个结点上实现分类或者回归。如：目标检测任务中需要检测图像是否包含特定的目标并进行目标定位。该问题可以通过一个映射函数来解决，该映射函数根据相应区域是否属于目标对象从而对邻接的顶点进行分类。
如下图所示，对应于城堡的黑色顶点的输出为
1，其它顶点输出为0。网页分类任务中需要判断每个网页的类别。我们将所有的网页视作一个大图，每个网页代表一个顶点、网页之间的超链接代表边。可以利用网页的内容和图结构来进行建模。
传统的机器学习算法通过使用预处理阶段来处理图结构的数据。在这一阶段，算法将图结构数据映射到一个更简单的表达
representation，如一个实值向量。即：预处理阶段首先将图结构的数据“压缩” 为实值向量，然后使用list-based数据处理技术来处理。在数据压缩过程中，一些重要的信息（如：每个顶点的拓扑依赖性）可能会被丢失。最终的效果严重依赖于数据预处理算法。
最近有很多算法尝试在预处理阶段保留数据的图结构性质，其基本思路是：利用图的结点之间的拓扑关系对图结构的数据进行编码，从而在数据预处理过程中融合图的结构信息。递归神经网络
RNN、马尔科夫链都是这类技术。论文
《The graph neural network model》提出了GNN模型，该模型扩展了RNN和马尔科夫链技术，适合处理图结构的数据。GNN既适用于graph-focused任务，又适用于node-focused任务。GNN扩展了RNN，它可以处理更广泛的图任务，包括无环图、带环图、有向图、无向图等。GNN扩展了马尔科夫链，它通过引入学习算法并扩大了可建模的随机过程的类型从而扩展了随机游走理论。
GNN是基于消息扩散机制information diffusion mechanism。图由一组处理单元来处理，每个处理单元对应于图的一个顶点。- 处理单元之间根据图的连接性来链接。
- 处理单元之间交换信息并更新单元状态，直到达到稳定的平衡为止。
- 通过每个处理单元的稳定状态可以得到对应顶点的输出。
- 为确保始终存在唯一的稳定状态，消息扩散机制存在约束。
模型
方程求解算法
参数学习算法
8.实际上编码网络仅仅类似于静态的前馈神经网络，但是编码网络的layer 层数是动态确定的，并且网络权重根据输入图的拓扑结构来共享。因此为静态网络设计的二阶学习算法、剪枝算法、以及逐层学习算法无法直接应用于 GNN 。
转移函数和输出函数
模型分析
RNN
随机游走
计算复杂度
不动点
GNN 的核心是不动点理论，通过顶点的消息传播使得整张图的每个顶点的状态收敛，然后在收敛的状态基础上预测。
这里存在两个局限：
GNN将顶点之间的边仅仅视为一种消息传播手段，并未区分边的功能。基于不动点的收敛会导致顶点之间的状态存在较多的消息共享，从而导致顶点状态之间过于光滑
over smooth，这将使得顶点之间缺少区分度。如下图所示，每个像素点和它的上下左右、以及斜上下左右八个像素点相邻。初始时刻蓝色没有信息量，绿色、黄色、红色各有一部分信息。
开始时刻，不同像素点的区分非常明显；在不动点的收敛过程中，所有像素点都趋向于一致，最终整个系统的信息分布比较均匀。最终，虽然每个像素点都感知到了全局信息，但是我们已经无法根据每个像素点的最终状态来区分它们。
GCN
原论文：Spectral Networks and Deep Locally Connected Networks on Graphs
卷积神经网络
CNN要求输入数据为网格结构，并且要求数据在网格中具有平移不变性，如一维语音、二维图像、三维视频都是这类数据的典型代表。CNN充分利用了以下几个特点来大幅度降低模型的参数数量：- 权重共享：同一个卷积核可以应用于不同的位置。
- 空间局部性：卷积核的大小通常都远远小于输入信号的尺寸。
- 多尺度：通过步长大于一的卷积或者池化操作来减少参数，并获得更大的感受野
receptive field。
在网格数据结构中，顶点的邻居数量都是固定的。但是在很多任务中，数据并不是网格结构，如社交网络数据。在这些图数据结构中，顶点的邻居数量是不固定的。
图结构是一种比网格结构更通用的结构，论文
《Spectral Networks and Deep Locally Connected Networks on Graphs》在图结构上扩展了卷积的概念，并提出了两种构建方式：- 基于空域的卷积构建
Spatial Construction：直接在原始图结构上执行卷积。 - 基于谱域的卷积构建
Spectral Construction：对图结构进行傅里叶变换之后，在谱域进行卷积。
在网格数据中的卷积可以采用固定大小的卷积核来抽取特征；但是在图数据中，传统的卷积核无能为力。图卷积的本质是找到适合于图结构的可学习的卷积核。
空域构建
图卷积
拉普拉斯算子
卷积
频域构建
Fast GCN
原论文：Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
模型
卷积核
图粗化
池化
Semi-Supervised GCN
原论文：SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS
图的半监督学习方法大致分为两大类：
基于图的拉普拉斯矩阵正则化的方法， 包括标签传播算法
label propagation、流行正则化算法manifold regularization。基于图嵌入的方法，包括
DeepWalk、LINE等。但是基于图嵌入的方法需要一个
pipeline，其中包括生成随机游走序列、执行半监督训练等多个步骤，而每个步骤都需要分别进行优化。
论文《 SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS》 提出了一种可扩展的、基于Graph 的半监督学习方法，该方法基于一个有效的、能直接对Graph 进行操作的卷积神经网络变种。
该模型基于频域卷积的局部一阶近似来选择卷积网络结构，其计算复杂度为 ，其中 为边的数量。
该模型学到的隐层representation 既能够编码图的局部结构，又能够编码顶点的特征。
分子指纹GCN
原论文：Convolutional Networks on Graphs for Learning Molecular Fingerprints
在材料设计领域的最新工作已经将神经网络用于材料筛选，其任务是通过学习样本来预测新型分子的特性。预测分子特性通常需要将分子图作为输入，然后构建模型来预测。在分子图中顶点表示原子，边表示化学键。
这个任务的一个难点在于：输入的分子图可以具有任意大小和任意形状，而大多数机器学习模型只能够处理固定大小、固定形状的输入。
目前主流的方法是通过hash 函数对分子图进行预处理从而生成固定大小的指纹向量fingerprint vector，该指纹向量作为分子的特征灌入后续的模型中。
论文《Convolutional Networks on Graphs for Learning Molecular Fingerprints》 提出了分子指纹GCN 模型，该模型用一个可微的神经网络代替了分子指纹部分。
神经网络以原始的分子图作为输入，采用卷积层来抽取特征，然后通过全局池化来结合所有原子的特征。这种方式使得我们可以端到端的进行分子预测。
相比较传统的指纹向量的方式，我们的方法具有以下优势：
预测能力强：通过实验比较可以发现，我们的模型比传统的指纹向量能够提供更好的预测能力。
模型简洁：为了对所有可能的子结构进行编码，传统的指纹向量必须维度非常高。而我们的模型只需要对相关特征进行编码，模型的维度相对而言低得多，这降低了下游的计算量。
可解释性：传统的指纹向量对每个片段
fragment进行不同的编码，片段之间没有相似的概念。即：相似的片段不一定有相似的编码；相似的编码也不一定代表了相似的片段。我们的模型中，每个特征都可以由相似但是不同的分子片段激活，因此相似的片段具有相似的特征，相似的特征也代表了相似的片段。这使得特征的
representation更具有意义。
GGS-NN
原论文：GATED GRAPH SEQUENCE NEURAL NETWORKS
目前关于图神经网络模型的工作主要集中在单输出模型上，如
graph-level的分类。实际上有一些图任务需要输出序列，如：输出一条包含特定属性的顶点组成的路径。论文
《GATED GRAPH SEQUENCE NEURAL NETWORKS》基于GNN模型进行修改，它使用门控循环单元gated recurrent units以及现代的优化技术，并扩展到序列输出的形式。这种模型被称作门控图序列神经网络Gated Graph Sequence Neural Networks:GGS-NNs。在
Graph数据结构上，GGS-NNs相比于单纯的基于序列的模型（如LSTM）具有有利的归纳偏置inductive biases。归纳偏置：算法对于学习的问题做的一些假设，这些假设就称作归纳偏置。它可以理解为贝叶斯学习中的“先验
prior”，即对模型的偏好。CNN的归纳偏置为：局部性locality和平移不变性spatial invariance。即：空间相近的元素之间联系较紧、空间较远的元素之间没有联系；卷积核权重共享。RNN的归纳偏置为：序列性sequentiality和时间不变性time invariance。即：序列顺序上的timestep之间有联系；RNN权重共享。
在图上学习
representation有两种方式：- 学习输入图的
representation。这也是目前大多数模型的处理方式。 - 在生成一系列输出的过程中学习内部状态的
representation，其中的挑战在于：如何学习representation，它既能对已经生成的部分输出序列进行编码（如路径输出任务中，已经产生的路径），又能对后续待生成的部分输出序列进行编码（如路径输出任务中，剩余路径）。
- 学习输入图的
PATCHY-SAN
原论文：Learning Convolutional Neural Networks for Graphs
很多重要问题都可以视为图数据得学习问题。考虑以下两个问题：
- 给定一组图作为训练数据，学习一个用于对未见过的图（即测试图）进行分类或者回归的函数。其中训练集中任意两个图的结构不一定是相同的。例如：给定一组化合物以及它们对于癌细胞活性抑制效果，用于预测新的化合物对于癌细胞活性抑制的结果。
- 给定一张大图，学习该图的
representation从而可以推断未见过的图属性，如顶点类型（即顶点分类）、缺失边（即链接预测）。
卷积神经网络
CNN在图像领域中大获成功。图像image也是一种图graph，但是它是一种特殊的正方形的网格图，其中顶点表示像素。如下图所示，黑色/白色顶点表示像素的不同取值（黑色取值为1、白色取值为0），红色顶点表示当前卷积核的中心位置。(a)图给出了一个3x3卷积核在一个4x4图像上的卷积过程，其中步幅为1、采用非零填充。我们可以将
CNN视为遍历一个顶点序列（即图(a)中的红色顶点1,2,3,4）、然后为该序列中的每个顶点生成固定大小的邻域子图（即图(b)中的3x3网格） 的过程。其中邻域子图作为感受野receptive field，用于特征抽取（抽取感受野中顶点的特征）。由于像素点的隐式空间顺序，从左到右以及从上到下唯一确定了这个顶点序列。在
NLP问题中，句子也隐式的从左到右确定了单词的顺序。但是对于图graph问题，难以针对不同的问题给予一个合适的顶点顺序。同时数据集中不同图的结构不同，不同图的顶点之间都无法对应。因此如果希望将卷积神经网络应用到图结构上，必须解决两个问题：
- 为图确定一个顶点序列，其中我们为序列中的每个顶点创建邻域子图。
- 邻域图的归一化，即将邻域子图映射到向量空间，从而方便后续的卷积运算（因为卷积核无法作用于子图上）。
论文
《Learning Convolutional Neural Networks for Graphs》提出了一种学习任意图的卷积神经网络框架PATCHY-SAN，该框架解决了这两个问题。PATCHY-SAN适用于无向图/有向图，可以处理连续/离散的顶点和边的属性，也支持多种类型的边。对于每个输入的
graph，PATCHY-SAN方法首先确定了一个顶点序列；然后，对序列中每个顶点提取一个正好由 个顶点组成的邻域并归一化邻域，归一化的邻域将作为当前顶点的感受野；最后，就像 CNN的感受野一样，可以将一些特征学习组件（如卷积层、dense层)作用到归一化邻域上。其整体架构如下图所示，其中红色顶点表示顶点序列中的顶点。PATCHY-SAN方法具有以下优势：- 计算高效，原生支持并行计算，并且可用于大型图。
- 支持特征可视化，可以深入了解图的结构属性。
- 相比较与
graph kernel方法，PATCHY-SAN无需依赖任何特征工程就可以学到具体任务的特征。
GraphSage
原论文：Inductive Representation Learning on Large Graphs
在大型
Graph中，顶点的低维embedding在从内容推荐到蛋白质功能识别等各项任务中都非常有效。之前的工作都集中在从单个指定的图来学习顶点
embedding，这些方法都是transductive的。但是，很多实际应用需要为从未见过的顶点或者全新的图来快速生成embedding，即需要inductive能力。这种inductive能力对于生产中的机器学习系统至关重要，这些机器学习系统需要在不断变化的图上运行，并不断遇到从未见过的顶点（如Youtube上的新用户、新视频）。 另外这种inductive能力还可以促进图的泛化，例如我们在已知的分子结构图上训练模型，然后该模型可以为新的分子图产生顶点embedding。与
transductiv相比，inductive的顶点embedding更为困难，因为这需要泛化到从未就按过的顶点。而这需要将新观察到的子图 “对齐” 到模型已经训练过的旧的子图。inductive框架必须学会识别顶点邻域的结构属性，从而识别每个顶点（包括新发现的顶点）在图的局部角色以及全局位置。大多数现有的顶点
embedding方法本质都是transductive的。这些方法都使用基于矩阵分解来直接优化每个顶点的embedding。因为它们是在单个固定的图上对顶点进行训练和预测，因此天然地无法推广到未见过的顶点。也可以修改这些方法来满足
inductinve的要求， 如针对新的未见过的顶点进行若干轮额外的梯度下降。但是这种方式的计算代价较高，也容易导致顶点embedding在重新训练期间发生漂移。
最近也有通过图卷积（如
Semi-Supervised GCN）来学习图结构的方法，但是这些方法也是以transductive的方式在使用。论文《Inductive Representation Learning on Large Graphs》提出了一个通用的、称作Graph Sample and Aggregage:GraphSAGE的学习框架，该框架将图卷积推广到inductinve无监督学习。GraphSage是一种inductive的顶点embedding方法。与基于矩阵分解的embedding方法不同，GraphSage利用顶点特征（如文本属性、顶点画像信息、顶点的degree等）来学习，并泛化到从未见过的顶点。- 通过将顶点特征融合到学习算法中，
GraphSage可以同时学习每个顶点的邻域拓扑结构，以及顶点特征在邻域中的分布。GraphSage不仅可以应用于顶点特征丰富的图（如引文网络、生物分子网络），还可以应用到没有任何顶点特征的简单的图，此时可以采用顶点的结构属性来作为顶点特征（如顶点degree）。 GraphSage并没有为每个顶点训练一个embedding，而是训练了一组聚合函数，这些聚合函数用于从顶点的局部邻域中聚合信息特征。在测试期间，我们使用训练好的模型的聚合函数来为从未见过的顶点生成embedding。
- 通过将顶点特征融合到学习算法中，
和之前的
embedding方法类似，GraphSage设计了一个无监督损失函数。该损失函数允许对GraphSage进行无监督训练，而无需任何特定于具体任务监督信息。论文还展示了以监督方式来训练GraphSage。论文在三个顶点分类
benchmark上评估了GraphSave方法，从而验证了GraphSage在从未见过的数据上具有优秀的顶点embedding能力。最后论文研究了
GraphSave的表达能力，并通过理论分析证明了：虽然GraphSage是基于顶点特征的，但是它能够学得顶点在图中角色的结构信息。GraphSave方法和Semi-Supervised GCN密切相关。原始的Semi-Supervised GCN以transductive的方式进行半监督学习，这要求在训练过程中已知完整的图拉普拉斯算子。GraphSage的一个简单变种可以视为Semi-Supervised GCN框架以inductive方式的扩展。
GAT
卷积神经网络
CNN已经成功应用于图像分类、语义分割以及机器翻译之类的问题，其底层数据结构为网格状结构grid-like structure。但很多任务涉及到无法以网状结构表示的数据，如：社交网络、电信网络等，而这些数据通常可以用图的方式来组织。早期图领域任务通常作为有向无环图，采用循环神经网络
RNN来处理。后来发展出图神经网络GNN作为RNN的泛化来直接处理更通用的图，如循环图、有向图、无环图。GNN包含一个迭代过程来传播顶点状态直至达到状态平衡，即不动点；然后再根据顶点状态为每个顶点生成输出。GG-NN通过在顶点状态传播过程中使用门控循环单元来改进这一方法。另一个方向是将卷积推广到图领域，有两种推广思路：谱方法
spectral approach、非谱方法non-spectral approach。谱方法通常和图的谱表达
spectral representation配合使用，并已成功应用于顶点分类。但是这些谱方法中，学习的
filter都依赖于拉普拉斯矩阵分解后的特征向量。这种分解依赖于具体的图结构，因此在一种图结构上训练的模型无法直接应用到具有不同结构的图上。另外，该方法无法应用于
graph-level任务，因为不同图的结构通常不同，因此拉普拉斯矩阵也不同。非谱方法可以直接在图上定义卷积，从而对空间相邻的邻域顶点进行运算。
但是如何定义一种可以处理不同数量邻居顶点、且能保持
CNN权重共享的卷积操作是一个挑战。PATCHY-SAN通过归一化邻域得到固定大小的邻域。
attention机制在很多基于序列的任务中已经称为标配。注意力机制的一个好处是可以处理变长输入，并聚焦于输入中最相关的部分来做决策。当注意力机制作用于单个序列的representation时，通常称作self-attention或者intra-attention。受此启发，论文
《GRAPH ATTENTION NETWORKS》提出了一种基于注意力的架构Graph attention network:GAT来对图结构数据进行顶点分类。其基本思想是：通过self-attention策略来“注意”邻居顶点，从而计算每个顶点的representation。GAT堆叠了一些masked self-attention layer，这些层中的顶点能够注意到邻居顶点的特征，并给邻域中不同的顶点赋予不同权重。在这个过程中不需要进行任何复杂的矩阵操作（如矩阵求逆或者矩阵分解），也不需要任何依赖于图结构的先验知识。GAT模型具有以下优势：- 计算高效，因为
GAT可以在顶点邻居pair对之间并行执行。 - 通过对邻居顶点赋予任意权重，它可以应用到任意
degree的顶点，对网络结构的普适性更强。 - 该模型可以直接应用于归纳学习
inductive learning问题，包括将模型推广到从未见过的图。
- 计算高效，因为
inductive learning和transductive learning的区别：inductive learning是从具体样本中总结普适性规律，然后泛化到训练中从未见过的样本。transductive learning是从具体样本中总结具体性规律，它用于预测训练集中已经出现过的unlabelled样本，常用于半监督学习。半监督学习不一定是
transductive，它也可能是inductive。如：训练时仅考虑labelled样本，不使用任何unlabelled样本的信息。