CS224W-图神经网络笔记3.1：Motifs and St

作者: Epiphron | 来源:发表于2021-02-02 09:07 被阅读0次

本文总结之日CS224W Winter 2021只更新到了第四节，所以下文会参考2021年课程的PPT并结合2019年秋季课程进行总结以求内容完整
课程主页：CS224W: Machine Learning with Graphs
视频链接：【斯坦福】CS224W：图机器学习( 中英字幕 | 2019秋)

1 引言

前面两节，讨论的网络的整体统计信息，这一节开始聚焦网络中的一些特殊结构（子图）和其中节点的的角色。

2 一些新概念

在深入学习本节前，需要先理解几个关键概念。

子图/子网络（Subgraph/Subnetwork）
motifs
graphlet
（节点的）结构性角色（structural rols）

2.1 子图Subgraph/子网络/Subnetwork

定义：字面上就可以理解，就是网络中的一部分节点和它们之间的边。

重要性（why）：我们可以借助子图挖掘出图的一部分性质和信息。

图片

例如，对不同类型的网络统计三个节点的各类子图出现的频次，得到不同网络的重要性概览（Network significance profile）。同类网络，有相似的子图分布。有的子图低于平均，有的高于平均。顺带一提高于平均的是下面要介绍的motifs。

图片

2.2 motifs

定义：（what）一类特殊子图的统称，它具有如下特点:

pattern：小的诱导子图（Small induced subgraph）。
- 诱导induced 表示节点之间的连接都包含在内。
recurring：高频出现
significant：重要指比预想（随机图）中出现的频率更高。

其他特点：

同一类motifs 之间，诱导子图的边必须完全一致。多一条边改个方向都不行
不同 motifs 之间可以重叠。

重要性（why）

帮助我们理解网络，理解不同节点之间关系。描述了节点间交互模式，通过模式匹配去理解网络。

如何衡量重要性（how）

因为Motifs 的定义要求Motif出现频率要更高，更重要。因此可以通过与随机网络中的Motifs数进行对比，以衡量真实网络中一种子图的显著性。具体通过下面的公式进行：

图片

因为，通常更大规模的网络有更高的Z值。因此，为了更方便在不同规模的网络之间进行比较，通过标准化之后的Z值的向量SP的方式解决。如上图所示。

关键问题 —— 随机网络怎么生成？

配置模型：根据给定的度序列k_1, k_2, …, k_N生成随机图，用来与真实网络进行对比。通常称为零模型（null model）
生成配置模型的两种方式：

图片

- 随机连接： 该方法生成的随机图，因为会忽略重边和自连接，故同一节点的度会发生改变。但根据《网络科学引论》的p275 。当网络规模足够大时，网络中的自边和重边的平均数将会趋于常数。
- 随机交换： 随机选择一对边，然后重连两个边，交叉两个点。生的随机图的节点的度，不发生改变。但计算的代价会较高，运行慢。为了保证随机图的随机性，需要运行的次数为 Q * E 次，其中Q应尽可能的大，如100。

获取具有相同节点数，边数，节点度数的随机图之后，我们就可以计算子图 $i$ 的 $Z$ 值。高值说明该子图是图G的一个Motif。

将一组子图的Z值作为网络的特征向量 $SP$ ，我们就得到了上面展示的对比图1。

2.3 Graphlets

非同构子图单元，是一类特殊的子图。Graphlets是对motif的扩展。它与motifs的区别：
- motif是从全局的角度来描述图的。用不同motifs来构成一个图的向量表示。
- 而Graphlet是从局部(节点)的角度出发来描述节点。用不同graphlet中的节点相对位置（局部信息），来形成一个节点的向量表示。