百度飞桨paddlepaddle图神经网络7日打卡营——初识图神经网络_paddlepaddle 图神经网络

图与图学习

图（graph）近来正逐渐变成机器学习的一大核心领域，在开始PGL框架学习之前，我们先简单学习一下图论的基本概念，图论的经典算法，以及近些年来图学习的发展。

一. 图是什么？

首先我们导入需要的包

import numpy as np
import random
import networkx as nx
from IPython.display import Image
import matplotlib.pyplot as plt
1
2
3
4
5

图的定义
图表示物件与物件之间的关系的数学对象，是图论的基本研究对象。

举个例子，一个简单的图可能是这样：

节点（node）用红色标出，通过黑色的边（edge）连接。

图可用于表示:

社交网络
网页
生物网络
…
我们可以在图上执行怎样的分析？

研究拓扑结构和连接性
群体检测
识别中心节点
预测缺失的节点
预测缺失的边
…
我们首先在我们的笔记本中导入第一个预构建的图：

# Load the graph
G_karate = nx.karate_club_graph()
# Find key-values for the graph
pos = nx.spring_layout(G_karate)
# Plot the graph
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)
1
2
3
4
5
6

空手道俱乐部图

这个「空手道」图表示什么？Wayne W. Zachary 在 1970 到 1972 年这三年中研究的一个空手道俱乐部的社交网络。该网络包含了这个空手道俱乐部的 34 个成员，成员对之间的连接表示他们在俱乐部之外也有联系。在研究期间，管理员 JohnA 与教练 Mr.Hi（化名）之间出现了冲突，导致俱乐部一分为二。一半成员围绕 Mr.Hi 形成了一个新的俱乐部，另一半则找了一个新教练或放弃了空手道。基于收集到的数据，除了其中一个成员，Zachary 正确分配了所有成员在分裂之后所进入的分组。

图的基本表示方法

• 图 G=(V, E) 由下列要素构成：
• 一组节点（也称为 verticle）V=1,…,n
• 一组边 E⊆V×V
• 边 (i,j) ∈ E 连接了节点 i 和 j
• i 和 j 被称为相邻节点（neighbor）
• 节点的度（degree）是指相邻节点的数量

节点、边和度的示意图

• 如果一个图的所有节点都有 n-1 个相邻节点，则该图是完备的（complete）。也就是说所有节点都具备所有可能的连接方式。
• 从 i 到 j 的路径（path）是指从 i 到达 j 的边的序列。该路径的长度（length）等于所经过的边的数量。
• 图的直径（diameter）是指连接任意两个节点的所有最短路径中最长路径的长度。

举个例子，在这个案例中，我们可以计算出一些连接任意两个节点的最短路径。该图的直径为 3，因为没有任意两个节点之间的最短路径的长度超过 3。

一个直径为 3 的图

• 测地路径（geodesic path）是指两个节点之间的最短路径。
• 如果所有节点都可通过某个路径连接到彼此，则它们构成一个连通分支（connected
  component）。如果一个图仅有一个连通分支，则该图是连通的（connected）

举个例子，下面是一个有两个不同连通分支的图：

一个有两个连通分支的图

• 如果一个图的边是有顺序的配对，则该图是有向的（directed）。i 的入度（in-degree）是指向 i
  的边的数量，出度（out-degree）是远离 i 的边的数量
  

有向图

• 如果可以回到一个给定节点，则该图是有环的（cyclic）。相对地，如果至少有一个节点无法回到，则该图就是无环的（acyclic）。
• 图可以被加权（weighted），即在节点或关系上施加权重。
• 如果一个图的边数量相比于节点数量较小，则该图是稀疏的（sparse）。相对地，如果节点之间的边非常多，则该图是密集的（dense）

Neo4J 的关于图算法的书给出了清晰明了的总结：

总结（来自 Neo4J Graph Book）

回到我们的空手道俱乐部图

In [8]
.degree() 属性会返回该图的每个节点的度（相邻节点的数量）的列表：

n=34
print(G_karate.degree())
degree_sequence = list(G_karate.degree())
[(0, 16), (1, 9), (2, 10), (3, 6), (4, 3), (5, 4), (6, 4), (7, 4), (8, 5), (9, 2), (10, 3), (11, 1), (12, 2), (13, 5), (14, 2), (15, 2), (16, 2), (17, 2), (18, 2), (19, 3), (20, 2), (21, 2), (22, 2), 
1
2
3