CS224w图机器学习（二）：Motifs & Structural Roles

内容简介

本文主要介绍CS224W的第三课，图的模块和结构性角色。

CS224W Lecture 3: Motifs and Structural Roles in Networks

CS224W第三课的主要内容，第三课的课程PDF可参见如下链接

1 Motifs & Subgraphs

在介绍图的模块前，先引入子图的概念。

如下图所示，分析无向图中任意三个节点的连接情况，大部分三个节点之间都有一条边，如图中的黄色节点所示。黄色的相互连接的三个节点，便是这个无向图的子图。 子图（Subgraphs）：图的组成部分，可用来描述和区分图

图中的黄色节点，三个节点构成的子图

了解什么是子图后，我们再介绍子图的重要性。

依旧以三个节点构成的子图为例，在有向图中，3个节点构成的子图一共有如下的13中模式。 我们再假设有这么一个计算公式（先不管这个公式是啥），能够计算出每一种子图相对于原始图的重要程度（significance）。且重要性为正值代表过表征（over-representation），重要性为负值代表欠表征（under-representation）。 再结合我们现实生活中的基因网络、神经元网络、社交网络、语言网络等，我们可分析这13种由三个节点构成的有向子图，分别在各个现实网络中的重要程度。 详情如下下图所示，横轴为13种子图，纵轴为归一化的重要性得分（先不管得分是怎么算的，重要的是引入这样的一个概念）。

由三个节点构成的有向图，一共有上述13种模式

现在我们了解了子图，也知道子图的重要性是可以衡量的。如此我们可以继续引入模块（motifs）的概念。

定义：图的模块指图中反复出现的重要的连接模式（recurring, significant pattern of interconnections） Motifs定义的三个关键词： pattern: small induced subgraph（小的导出子图）； recurring: found many times（高频出现）； significant: more frequent than expected in random network（相比于随机图，出现概率更高）。 Motifs的用途： 1）帮助我们理解图的工作原理 2）在给定的情境下，预测图的操作和反应 Motifs用途的相关案例：神经元网络的前馈回路（神经元网络的一个小的子图），可用于消除生物噪音。

介绍上述概念后，我们现在可深入解读图的模块（Motifs）：

Motifs的重要性度量（significance）：通过对比其在真实图和随机图中的出现频率。 记Motifs

[公式]

的重要性为

[公式]

。

[公式]

为真实网络中的出现次数，

[公式]

为随机网络中的出现次数。 真实网络的显著性分布（Significance Profile, SP），

[公式]

。 此时目标变成：如何产生一个合适的随机图？ - Configuration Model： 目标：给定节点的度的序列

[公式]

，产出满足条件的随机图。 流程：1）给定节点和边（触角）；2）基于边，随机配对这些节点；3）产生随机图。 - Switching 流程：1）从给定的初始图开始；2）随机挑选两条边，交换这两条边所对应的终止节点；3）重复N次。 产出：与初始图的度完全一致的随机图。 我们知晓了随机图的产生方法，也晓得Motifs重要性的度量，结合起来便能发现并检测原始图中的Motifs。 1）统计真实图中的子图数量；2）统计随机图中的子图数量；3）计算z-score；4）z-score越高的子图，越可能是原始图的模块。

Configuration Model 产生随机图的三个步骤

前面学习的Motifs，主要用来从局部（子图）窥探整个图的结构。下面引入的新概念Graphlet，则主要描述节点的特征、描述给定节点周围的网络结构。

什么是Graphlet？ 联通的非同构子图（Connected non-isomorphic subgraphs） 2个节点—5个节点的Graphlets如下图所示。PS：到10个节点时，Graphlets个数则达到了惊人的11716571。 Graphlet考虑的是连通的非同构子图，非同构是不同子图之间的关系，我们再次基础之上，还需要考虑子图自身的性质——自同构（automorphism orbit）。 以3个节点的graphlets为例，如G1图中包含白色点和黑色点，3个节点的Graphlets只有两种子图，但是节点的类型却包含三种，参见下图中的1、2、3。这就是子图的自同构所考虑的问题。 之前也提到Graphlets主要用来描述节点的特征，那么一组联通的非同构子图是怎么描述节点特征的呢？答案类似于节点的degree。 Graphlet degree vector（GDV）：一个节点在每一个固定的轨迹（orbit position）上所包含的graphlets的个数。 可参考下下图G的案例，节点v在a、b、c、d四个位置时的Graphlets数量。

图G中的节点v，在a、b、c、d四个位置时的GDV分别为2，1，0，2

介绍完Motifs和Graphlets的概念，现在学习如何去寻找图中的motifs和graphlets。

首先考虑如何计算子图的数量 以网络为中心的手段分如下两步（Network-centric approaches）： 1）列举所有size为k的连通子图；2）计算每个子图的出现次数（确保子图间的非同构性） 我们先看第一步：列举。课程介绍的手段为Extract Subgraph Enumeration（ESU）。 引入两个集合：

[公式]

：当前已构造好的子图；

[公式]

：可加入当前子图并构成新Motifs的候选人节点。 再结合下图的案例，寻找图G中的size为3的子图，来学习ESU是列举子图的技巧。 1）从Root节点开始，最左的第一个分支，子图集合

[公式]

元素为

[公式]

，可加入的新节点为

[公式]

，由此我们得到新的子图

[公式]

2）新子图为

[公式]

，能够加入新子图的节点为

[公式]

，得到符合条件的三个size为3的子图。 3）子图初始元素

[公式]

更新为

[公式]

，重复步骤1和2，

[公式]

，直至遍历左右节点。 寻找到所有子图后，再对同构的子图进行计数。G1子图有5个，G2子图有1个。 不难发现，在对子图进行计数时，需要考虑子图之间是否为同构图。怎么判断图与图的同构性呢？。此处仅引入式地介绍。 定义：如果存在一个双射f，使得图G中相邻的节点，在图H中也是相邻的，那么图G和图H是同构图。找到这样的双射f，便能说明图G和图H的同构图。

2 Structural Roles in Network

首先什么是角色（Roles）？

比如在工作中，领导会根据每个人的职责和工作性质来给每个人指定角色。 同理，在图中也需要根据节点的结构表现来决定其角色（Role）。 角色（Role）是指在网络中具有相似功能的节点（A group of nodes with similar structural properties）。 Role取决于节点间的相似性，而并非相互连接性。 与之对应的另一个概念：社区（community）则是相互连接的一组节点，重在连接性（A group of nodes that are well connected to each other）。 以计算机学院的社交网络为例： 学生、老师、教职工是角色； AI实验室、Theory实验室、Info实验室是社区。 角色和社区是一种互补的概念。如下图

关于角色更标准的描述。

结构等价性（Structural equivalence）：如果两个节点，与其他所有节点的关系都是相同的，那么我们称这两个节点是结构等价的。 以下图为例，节点3和节点4，跟其他所有节点的关系都相同，这两节点是结构等价的。节点1和节点2也是结构等价的。

3 Discovering structural roles and its application

怎么发现网络中的角色呢？课程介绍的方法是RoIX

RoIX是一种基于无监督学习的方式来自动挖掘网络中结构性角色的方法。 RoIX的实验逻辑如下图所示： 1）输入节点的邻接矩阵 2）递归特征提取 3）得到节点的特征矩阵 4）基于特征矩阵，提取角色 5）输出节点的角色矩阵，和角色的特征矩阵

怎么进行递归特征提取？

思想：对节点的特征进行整合，并使用它去生成新的递归特征。 初始特征：节点的邻居特征（neighborhood features）。 1）局部特征（Local features）：比如对于有向图的入度和出度：in-degree、out-degree、total degree，带权重图的weighted feature。 2）中心特征（Egonet features）：比如within-egonet edges、edges entering/leaving egonet。 递归特征提取的步骤： 1）从节点的初始特征开始。 2）使用均值（mean）和求和（sum）运算，基于初始特征，递归生成新的特征。 3）重复2），并对递归生成的特征，进行剪枝（去掉高度相关的特征）。

怎么进行角色提取？如下图，对递归生成的特征进行聚类，聚出来的类别就是提取的角色。

最后为什么角色很重要？它都有哪些应用场景？详情可参见下图。