图神经网络02-图与图学习(上)

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

一. 图是什么?


首先我们导入需要的包


import numpy as np
import random
import networkx as nx
from IPython.display import Image
import matplotlib.pyplot as plt


图的定义


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


举个例子,一个简单的图可能是这样:


60.png

image


节点(node)用红色标出,通过黑色的边(edge)连接。


图可用于表示:

  • 社交网络
  • 网页
  • 生物网络


我们可以在图上执行怎样的分析?

  • 研究拓扑结构和连接性
  • 群体检测
  • 识别中心节点
  • 预测缺失的节点
  • 预测缺失的边

我们首先在我们的笔记本中导入第一个预构建的图:


# Load the graph
# Zachary的空手道俱乐部网络
G_karate = nx.karate_club_graph()
# Find key-values for the graph
pos = nx.spring_layout(G_karate)
# print(pos)
# Plot the graph
nx.draw(G_karate, cmap = plt.get_cmap('rainbow'), with_labels=True, pos=pos)

空手道俱乐部图


这个「空手道」图表示什么?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)是指相邻节点的数量


61.png

image


节点、边和度的示意图

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

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


62.png

image


一个直径为 3 的图

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

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


63.png

image


一个有两个连通分支的图

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


64.png

image


有向图

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

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


65.png

image


总结(来自 Neo4J Graph Book)

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


# .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), (23, 5), (24, 3), (25, 3), (26, 2), (27, 4), (28, 3), (29, 4), (30, 4), (31, 6), (32, 12), (33, 17)]


# 计算边的数量,但也计算度序列的度量:
nb_nodes = n #
nb_arr = len(G_karate.edges()) #边的数量
avg_degree = np.mean(np.array(degree_sequence)[:,1]) # 
med_degree = np.median(np.array(degree_sequence)[:,1])
max_degree = max(np.array(degree_sequence)[:,1])
min_degree = np.min(np.array(degree_sequence)[:,1])
# 最后,打印所有信息:
print("Number of nodes : " + str(nb_nodes))
print("Number of edges : " + str(nb_arr))
print("Maximum degree : " + str(max_degree))
print("Minimum degree : " + str(min_degree))
print("Average degree : " + str(avg_degree))
print("Median degree : " + str(med_degree))


Number of nodes : 34
Number of edges : 78
Maximum degree : 17
Minimum degree : 1
Average degree : 4.588235294117647
Median degree : 3.0


# 平均而言,该图中的每个人都连接了 4.6 个人。
# 我们可以绘出这些度的直方图:
degree_freq = np.array(nx.degree_histogram(G_karate)).astype('float')
plt.figure(figsize=(12, 8))
plt.stem(degree_freq)
plt.ylabel("Frequence")
plt.xlabel("Degre")
plt.show()


66.png


我们后面会看到,度的直方图相当重要,可用于确定我们看到的图的种类。


二. 如何存储图?


存储图的方式有三种,取决于你想用它做什么:

  • 存储为边列表:

1   2

1   3

1   4

2   3

3   4

...


我们存储有边连接的每一对节点的 ID,例如:


G_karate.edges()


EdgeView([(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 10), (0, 11), (0, 12), (0, 13), (0, 17), (0, 19), (0, 21), (0, 31), (1, 2), (1, 3), (1, 7), (1, 13), (1, 17), (1, 19), (1, 21), (1, 30), (2, 3), (2, 7), (2, 8), (2, 9), (2, 13), (2, 27), (2, 28), (2, 32), (3, 7), (3, 12), (3, 13), (4, 6), (4, 10), (5, 6), (5, 10), (5, 16), (6, 16), (8, 30), (8, 32), (8, 33), (9, 33), (13, 33), (14, 32), (14, 33), (15, 32), (15, 33), (18, 32), (18, 33), (19, 33), (20, 32), (20, 33), (22, 32), (22, 33), (23, 25), (23, 27), (23, 29), (23, 32), (23, 33), (24, 25), (24, 27), (24, 31), (25, 31), (26, 29), (26, 33), (27, 33), (28, 31), (28, 33), (29, 32), (29, 33), (30, 32), (30, 33), (31, 32), (31, 33), (32, 33)])


* 使用邻接矩阵,这通常是在内存中加载的方式:
对于图中的每一个可能的配对,如果两个节点有边相连,则设为 1。如果该图是无向图,则 A 是对称的。
![](https://ai-studio-static-online.cdn.bcebos.com/2b34d2e63e2743709e2bba2ec869034a15131b1104134bf697ed030856a1a634)


* 使用邻接列表:
1 :[2, 3, 4]
2 :[1,3]
3 :[2, 4]
...
这三种表示方式都是等价的,我们可以根据使用场景来选择图的存储方式。


三. 图的类型和性质


图可以根据不同标准进行分类,我们在这里主要讲一种分类方法,同构图与异构图。了解更多可以查看博客,图论(二)--各种图介绍


  • 同构图与异构图


两个图G和H是同构图(isomorphic graphs),能够通过重新标记图G的顶点而产生图H。

如果G和H同构,那么它们的阶是相同的,它们大小是相同的,它们个顶点的度数也对应相同。


异构图是一个与同构图相对应的新概念。

传统同构图(Homogeneous Graph)数据中只存在一种节点和边,因此在构建图神经网络时所有节点共享同样的模型参数并且拥有同样维度的特征空间。

而异构图(Heterogeneous Graph)中可以存在不只一种节点和边,因此允许不同类型的节点拥有不同维度的特征或属性。



相关文章
|
22天前
|
编解码 安全 Linux
网络空间安全之一个WH的超前沿全栈技术深入学习之路(10-2):保姆级别教会你如何搭建白帽黑客渗透测试系统环境Kali——Liinux-Debian:就怕你学成黑客啦!)作者——LJS
保姆级别教会你如何搭建白帽黑客渗透测试系统环境Kali以及常见的报错及对应解决方案、常用Kali功能简便化以及详解如何具体实现
|
22天前
|
安全 网络协议 算法
网络空间安全之一个WH的超前沿全栈技术深入学习之路(8-1):主动信息收集之ping、Nmap 就怕你学成黑客啦!
网络空间安全之一个WH的超前沿全栈技术深入学习之路(8-1):主动信息收集之ping、Nmap 就怕你学成黑客啦!
|
22天前
|
网络协议 安全 NoSQL
网络空间安全之一个WH的超前沿全栈技术深入学习之路(8-2):scapy 定制 ARP 协议 、使用 nmap 进行僵尸扫描-实战演练、就怕你学成黑客啦!
scapy 定制 ARP 协议 、使用 nmap 进行僵尸扫描-实战演练等具体操作详解步骤;精典图示举例说明、注意点及常见报错问题所对应的解决方法IKUN和I原们你这要是学不会我直接退出江湖;好吧!!!
网络空间安全之一个WH的超前沿全栈技术深入学习之路(8-2):scapy 定制 ARP 协议 、使用 nmap 进行僵尸扫描-实战演练、就怕你学成黑客啦!
|
22天前
|
网络协议 安全 算法
网络空间安全之一个WH的超前沿全栈技术深入学习之路(9):WireShark 简介和抓包原理及实战过程一条龙全线分析——就怕你学成黑客啦!
实战:WireShark 抓包及快速定位数据包技巧、使用 WireShark 对常用协议抓包并分析原理 、WireShark 抓包解决服务器被黑上不了网等具体操作详解步骤;精典图示举例说明、注意点及常见报错问题所对应的解决方法IKUN和I原们你这要是学不会我直接退出江湖;好吧!!!
网络空间安全之一个WH的超前沿全栈技术深入学习之路(9):WireShark 简介和抓包原理及实战过程一条龙全线分析——就怕你学成黑客啦!
|
2月前
|
监控 网络协议 Linux
网络学习
网络学习
149 68
|
1月前
|
存储 安全 网络安全
浅谈网络安全的认识与学习规划
浅谈网络安全的认识与学习规划
33 6
|
22天前
|
人工智能 安全 Linux
网络空间安全之一个WH的超前沿全栈技术深入学习之路(4-2):渗透测试行业术语扫盲完结:就怕你学成黑客啦!)作者——LJS
网络空间安全之一个WH的超前沿全栈技术深入学习之路(4-2):渗透测试行业术语扫盲完结:就怕你学成黑客啦!)作者——LJS
|
22天前
|
安全 大数据 Linux
网络空间安全之一个WH的超前沿全栈技术深入学习之路(3-2):渗透测试行业术语扫盲)作者——LJS
网络空间安全之一个WH的超前沿全栈技术深入学习之路(3-2):渗透测试行业术语扫盲)作者——LJS
|
22天前
|
SQL 安全 网络协议
网络空间安全之一个WH的超前沿全栈技术深入学习之路(1-2):渗透测试行业术语扫盲)作者——LJS
网络空间安全之一个WH的超前沿全栈技术深入学习之路(1-2):渗透测试行业术语扫盲)作者——LJS

热门文章

最新文章