CS224w图机器学习（一）：Graph介绍、特性和随机图模型

1 背景

阅读领域相关文献和学习名校课程能帮助我们很好的构建系统性深度学习的知识体系。新建《深度学习进阶课程》专栏，后续将从CS224w开始，陆续添加各名校深度学习课程的学习笔记。

CS224w是斯坦福大学计算机学院副教授 Jure Leskovec等人开设的一门主题为图机器学习的课程。课程首页：http://web.stanford.edu/class/cs224w/index.html#content。

2 CS224w Lecture 1: Introduction

CS224w第一课主要是介绍图的一些基础概念，算是回顾基础知识。课程主要介绍了如下几个模块。

2.1 什么是图？常见的图有哪些？

Why Networks? Networks are a general language for describing complex systems of interacting entities. 现实中常见的图有哪些？ 社交关系图、金融交易关系图、信息网络关系图、神经元结构图等。 图可以挖掘哪些信息？ 节点分类、链路预测、社区挖掘、网络相似度检测等。

2.2 图的基础结构

图的基本元素（component）

节点：nodes、vertices，用 N 表示。 边：links、edges，用 E 表示。 图：network、graph，用 G(N, E) 表示。

图的类型（Types of Graph）

Directed Graph & Undirected Graph 有向图与无向图，节点间的关系links有无方向。 Node Degree 节点

[公式]

的度

[公式]

为节点

[公式]

边的条数，有向图分为in-degree

[公式]

和out-degree

[公式]

Average Degree 图的平均度，无向图：

[公式]

，有向图：

[公式]

Complete Graph 完全图，任意节点之间都存在link的图成为完全图，无向图边的条数为

[公式]

，有向图为

[公式]

。 Bipartite Graph 二分图，图的节点可以分为两个集合

[公式]

和

[公式]

，集合内的节点之间无联系，边连接分别来自集合

[公式]

和

[公式]

的两个节点。如Authors-Papers，Actors-Movies等。 ”Folded“ network 二分图的两个独立集合

[公式]

和

[公式]

分别可构成”Folded“ Network，详情可参见下图。

中间为二分图，左图为集合U的Folded Network，右图为集合V的Folded Network

图的类型（More Types of Graph）

Unweighted & Weighted Graph 无权重图和权重图，节点间的关联（边）是否存在权重。 Self-loops（Self-edges） 节点自己和自己之间存在关联，即边连接着节点自身。 Multigraph 两个节点存在多条边。 Connected Graph 连通图，图内的任意两个节点之间存在一条路径。对于有向图，又分为强连通图（Strong Connected Directed Graph）和弱连通图（Weak Connected Directed Graph）。

图的表征（Representing Graph）

Adjacency Matrix 图

[公式]

的邻接矩阵

[公式]

是一个维度为

[公式]

的矩阵，矩阵元素

[公式]

代表节点

[公式]

和节点

[公式]

之间是否存在边。现实中，图的邻接矩阵非常稀疏，通常需要其他方法来表征。 Edge List 边的list，存储图中的所有边。如：

[公式]

。 Adjacency List 节点为key，与其存在关联的节点list为value的字典。如：

[公式]

。

================================================================

3 CS224w Lecture 2: Properties of Networks and Random Graph Models

CS224w第二课主要介绍图的性质，以及不同随机图模型的性质表现。

3.1 图的性质

度分布（Degree Distribution）

随机选取一个节点，该节点的度为

[公式]

，度分布指的是度为

[公式]

的节点个数

[公式]

和

[公式]

的分布图 度分布：

[公式]

。

路径长度（Path Length）

路径是维系两个节点间关联的一组节点，路径可以重复经过某一节点。 路径长度（Path Length）：两个节点间的最短路径

[公式]

。有向图两个节点的路径长度不具备交换律，即

[公式]

。 图的直径（Graph Diameter）：图的所有最短路径的最大值。 平均路径长度（Average Path Length）：无向联通图或有向强连通图的平均路径长度为

[公式]

。

聚类系数（Clustering coefficient）

聚类系数

[公式]

考虑节点

[公式]

的邻接节点之间的链接情况，

[公式]

，

[公式]

，其中

[公式]

是节点

[公式]

的邻接节点之间存在的边数，

[公式]

为节点

[公式]

的度数。 图的平均聚类系数为

[公式]

。

最大连通分量（Largest Connected Components）

集合内任意两点间存在一条路径的最大集合。Largest set where any two nodes can be joined by a path。 如何寻找图的最大联通分量？1）随机选取节点，并进行深度优先搜索，并标记访问过的节点，直至所有与该节点连通的节点都被访问到；2）如果存在未访问过的节点，从未访问过的节点中随机选取一个新节点，并重复深度优先搜索，如果所有节点都已访问，则结束；3）列表内节点最多的子集，为该图的最大连通分量。

3.2 随机图模型

3.2.1 ER随机图（Erdos-Renyi Random Model）

ER随机图存在如下两种情况：

[公式]

：

[公式]

个节点组成的无向图，任意两个节点

[公式]

之间存在一条边的概率为

[公式]

[公式]

：

[公式]

个节点组成的无向图，一共存在

[公式]

条随机分布的边

[公式]

随机图的性质

• Degree Distribution

对于图中的任意节点，它与其他所有节点之间存在边的概率为

[公式]

图中所有节点的Degree都服从二项分布

[公式]

。 由此我们也可知，

[公式]

的度分布也就是

[公式]

。 均值

[公式]

，方差

[公式]

，异变度

[公式]

，即n越大，度分布越集中在均值附近。

• Clustering Coefficient

对于图中的任意节点

[公式]

，假设它的degree为

[公式]

。 这

[公式]

个节点之间最多存在的边数为

[公式]

，每条边出现的概率为

[公式]

。 由此我们可知，实际边数的期望

[公式]

。 所以

[公式]

的聚类系数：

[公式]

• Path Length

ER随机图的平均路径长度为

[公式]

。 首先引入一个概念Expansion

[公式]

[公式]

等价于：

[公式]

。 Expansion 主要用来衡量图的鲁棒性（robustness），如下图。

定理：在一个节点个数为

[公式]

，expansion为

[公式]

的图中，图中任意两个节点的平均路径长度为

[公式]

。 考虑路径长度时，首先考虑ER随机图的广度优先搜索（BFS），第一层是初始节点，第二层是初始节点的邻接节点，...，直至覆盖图中所有节点，那么BFS的深度为

[公式]

，即ER随机图的直径：

[公式]

。 然而并非所有图都像EP随机图可基于概率进行BFS。所以我们需要参考下图，将expansion的概念引入，基于expansion来做广度优先搜索，初始节点为S，第二层为基于S进行expansion的节点集合，...，直至覆盖全部节点，每一次expansion为α，所以平均路径长度为

[公式]

。

• Connectivity

ER随机图的最大连通分量，随着平均度数的变化，如下图所示。

[公式]

[公式]

3.2.2 小世界模型（Small World Model）

小世界模型源于我们真实的社交网络

假如每个人有100个朋友，那么从自己出发 Step 1: reach 100 people Step 2: reach 10000 people Step 3: reach 1M people Step 4: reach 100M people 问题核心：忽略了朋友的朋友也是自己的朋友，需要聚类

考虑聚类系数，由此引入小世界模型，其主要包含两个组成部分

1）从低维的有规律的网络开始（如下图，我们使用一个环作为我们的低维有规律网络）。 此时网络具有很高的聚类系数，类似于每个人有100个朋友。 此时需要再对网络进行随机的剪切和重组。 2）Rewire：随机给两个距离较远的节点添加或删除边。 详细流程可参见下图，rewire使得我们可以将给一个确定的网络插入随机成分。

小世界模型的性质

如下图，横轴为rewire的概率p，实线的纵轴为平均最短路径长度，虚线的纵轴为聚类系数。 随着rewire的概率越大，聚类系数和平均路径长度越小。

3.2.3 Kronecker模型（Kronecker Graph Model）

引入Kronecker模型前，可先看下这个问题，我们能够通过递归生成网络？

如下图，通过自相似的方式，可生成更大的网络。这种方法也称为kronecker product。 同理，我们也可通过递归的方式来进行两个矩阵的乘运算。矩阵A和矩阵B的kronecker product，如下下图所示。 Kronecker图模型是以如下的方式，通过对初始图进行kronecker product循环而产生的。

随机Kronecker图模型

我们已经知晓通过自循环，可以生成Kronecker图模型，那么什么是随机Kronecker图模型呢？ 首先生成一个

[公式]

的随机矩阵

[公式]

，矩阵元素为0-1之间的随机数。 再基于kronecker product的方式，计算

[公式]

的

[公式]

次幂

[公式]

，

[公式]

中的元素

[公式]

代表节点i和节点j之间存在边的概率。 再基于

[公式]

中的概率去做类似于抛硬币的操作，命中则元素为1，没有命中则元素为0，最终随机Kronecker图模型中的元素全为0或1。 也可通过基于概率向Kronecker图中新增一条边的方式，来完成Kronecker图的构建（效果更快）。 最后，如下图所示，随机Kronecker图和真实网络的很多性质是类似的。

4 总结

• CS224w课程的第一章和第二章主要还是引入为主，介绍了一些与图相关的基础知识，距离图神经网络的实战，还相去甚远。
• 第一章介绍了图的定义、常见图的类型、图的基本结构。
• 第二章介绍了图的基本性质，并引入了三种随机图模型，通过分析这些模型的性质来加深我们对图的了解。