图机器学习 2.2-2.4 Properties of Networks, Random Graph

2020 年 3 月 28 日 图与推荐

图机器学习 2.1 Properties of Networks, Random Graph

本文继续学习斯坦福CS224W 图机器学习的第二课~

前面介绍了用来衡量一个图模型的几个主要属性,并且应用于实际中:msn人际关系图和PPI网络之后发现一些属性的值很接近

特殊->一般->建立模型

那么现在考虑一般情况下的模型:考虑最简单的图模型

【注意这里考虑的是无向图】我们用G_{np}来表示具有n个节点且每个边(u,v)都是服从概率p的独立同分布的无向图

img

注意】n和p不能唯一决定图模型!

也就是说图其实是随机过程的一个结果,下图是给定n,p值的一个例子
img

那么现在对于这么general的一个图,我们来看看前面提到的那些属性的值是多少

(1)度分布(degree distribution)

img
  • P(k):选定了一个节点,于是图中剩下n-1个节点,从剩下的节点中选取k个节点乘以这k个节点有k个边(也就是度为k)的概率
  • 有了度分布,可以发现其是 二项式的
  • 既然是二项式的我们就能得到其期望和方差
img

方差和期望的比值说明:当网络规模逐渐变大,平均值会越来越集中

对应了大数定理
img

补充上一节的一个内容:注意到度的直方图有利于我们判断图的结构

(2)聚合系数

img

这里的计算比较显然,但是注意到E[Ci]可以发现当期望是一个固定值时,随着图规模越来越大,随机图的聚合系数会趋近于0。

下面的学习部分,需要记住随机图的聚合系数是p】

讨论完了度分布和聚合系数,下面来看随机图的路径长度,这里通过“扩展(expansion)“来衡量

(3)expansion

什么是扩展数?

img

简单理解为:任取图中节点的一个子集,相对应的从子集中离开的(也就是和这些节点相关的)最小节点数目

或者还可以理解为:为了让图中一些节点不具备连接性,需要cut掉图中至少多少条边?

(answer:需要至少cut掉alpha Num(节点)条edges)

扩展数alpha也是一个用来衡量鲁棒性的一个度量

(4)largest connected component(最大连接元)

什么是最大连接元?我们看下面这个图就一目了然

图中标红的部分就是最大连接元:连接最多节点的部分

图来源:

https://networkx.github.io/documentation/networkx-1.9/examples/drawing/giant_component.htmlnetworkx.github.io

最大连接元的用途/意义:展示随机图的“进化”过程

当聚合系数=0的时候:也就是没有edge,这时候是一个空图

当聚合系数=1度时候:就是一个“全连接”的图

那么当聚合系数从0变化到1的过程中发生了什么变化?【当平均度=1的时候,因为k=p(n-1),此时聚合系数c=p=1/(n-1),出现了一个大连接元,以此类推】

img

学习完了随机图中的四个重要属性,下面来看随机图的应用性如何,看看和MSN数据的对比

img
  • 之前说过度分布的直方图有利于判断图的结构,MSN和随机图的直方图差距还是很大的;
  • 平均路径:MSN和随机图的数据差不多
  • 平均聚合系数:差距很大,随机图的非常小
  • 最大连接元:很接近

综上来看,随机图的实际应用性如何?----不好!

img

从上面的属性比较可以看出:实际上的网络并不是随机的。

那么问题来了,既然如此又为什么要学习随机图呢?因为这是最简单也是最有效的学习和评估网络的方法!

随机性包罗万象,我们可以根据实际网络的特性来修改随机图来适应实际网络的需要

那么,如何让随机图实际应用性变强呢?

上一节说了随机图和实际网络还是有差距的:主要体现在聚合系数和度分布不一样

那么能不能对随机图进行一定的修改,使得重要的度量能和实际网络对应上呢?那么就要介绍这部分的主要内容:small-world model(我暂且翻译为小世界模型吧)

img

随机图的聚合系数很小,直径很大。这才是和真实网络最大的差异之处。所以能不能有【高聚合系数+小直径】?首先来分析聚合系数反应的本质是什么。

【高聚合系数反映了局部性】简单来说就是:社交网络中,我的朋友们互相也是认识的,如同下图

img

聚合系数和直径之间有一个矛盾之处在于:图的扩展(expansion)会使得保持度不变的情况下,直径越小也会导致聚合系数越小;而高聚合系数(高度连接的网络)却往往直径很大。那么怎么解决这个矛盾?基于以下两个思想:

(1)聚合反应局部性(2)随机性可以使得“捷径“出现

img

解决方案如下:

STEP 1:选择高聚合的网络

STEP 2:对每个边,以概率p修改边的终点(引入捷径)

img

这个“捷径”的方法很类似于数值计算中的“插值”:把节点作为插值节点,那么这里修改过的边就类似”线性插值“

从图上可以看出来,想要随机创造捷径是很简单不费力的。

反过来思考:聚合系数呢?社交网络中,我的朋友们互相也认识,所以聚合系数高,可是很难让我的朋友们互相“绝交”从而让聚合系数降下来。下图可以反应这个现象

横坐标是修改原有图的边位置的概率,纵坐标是聚合系数

从图中可以看到“高聚合系数+低路径长度”的区域是很大的

既然已经解决了随机图和实际网络的"gap“,那么现在我们看看这个被修改了的随机图,表示的是什么?

(1)高聚合系数:我的大部分朋友们互相都认识(2)低直径:但是我也有几个朋友在另一个城市,且他们和其他朋友互不认识

实际网络这样的情况还是很多的

第二节课的最后一部分:Kronecker图模型

前面一直都是在讨论随机图,上一节还说到通过对随机图引入随机“捷径”可以将随机图变为small-world model,那么这部分来讲讲如何生成大的真实图。

首先开门见山介绍背后的idea:就是递归(循环)图生成

基于现实观察:自相似性

比如不同的friendship的建立往往基于相同的文化、相似的爱好等等

很多物体和本身的一部分是很类似的,那么利用这个思想,可以给定初始的小的图,从而对其进行不断的扩张得到递归图

img

那么这个思想基于的工具是:kronecker积--定义如下

img

这个积的定义基本上大家在很多数学书上都有看到,这个积的结果是明显放大了原有的矩阵的阶。那么对于在图中的推广就是利用图的邻近矩阵来做kronecker积

那么什么是kronecker 图?--初始图(初始邻近矩阵)的循环kronecker积

img

这样的方法即自然又简单,但是呢,我们观察下面这个图

img

尽管到目前为止讨论的Kronecker结构产生的图具有一系列所需的特性,但其离散性质在程度和频谱数量上会产生“阶梯效应”,这仅仅是因为单个值具有较大的多重性。例如,图邻接矩阵的特征值的度分布和分布以及主要特征向量分量的分布(即“网络”值)都受此影响。这些数量是多重分布的,这导致具有多个重复的单个值。下图说明了阶梯效应(这部分来自lecture讲解人的论文https://dl.acm.org/doi/10.5555/1756006.1756039

img
会发现得到的图邻近矩阵的结构是很规则的(因为邻近矩阵的元素都是1或者0),类似于具有规则结构的网格一样,这样的当然好(利于我们分析),可是这样的图结构就很难capture真实复杂网络的信息了,那么要怎么办?-----答案是引入随机性!

这里在初始矩阵引入随机性的意思是:放松初始矩阵--邻近矩阵只有0或者1元素的条件,而是可以有[0,1]之间的元素,也就是

(1)初始矩阵的每个元素反应的是特定边出现的概率

(2)对初始矩阵进行Kronecker积运算,以获得较大的随机邻接矩阵,在该矩阵中,大型矩阵的每个元素数值再次给出了特定边出现在大图中的概率,这样的随机邻接矩阵定义了所有图的概率分布

img

那么这个方法存在一个缺陷:费时间!

所以下面给出了一种快速方法---基于的思想:还是kronecker积的本质--循环性

img
img
img

总结一下:随机kronerker图从数学上用公式来表示就是

img
img

这给了我们对随机Kronecker图的非常自然的解释:每个节点由一系列分类属性值或特征来描述。然后,两个节点链接的可能性取决于各个属性相似性的乘积。


登录查看更多
10

相关内容

图机器学习(Machine Learning on Graphs)是一项重要且普遍存在的任务,其应用范围从药物设计到社交网络中的友情推荐。这个领域的主要挑战是找到一种表示或编码图结构的方法,以便机器学习模型能够轻松地利用它。

知识荟萃

精品入门和进阶教程、论文和代码整理等

更多

查看相关VIP内容、论文、资讯等
【ICML2020】持续图神经网络,Continuous Graph Neural Networks
专知会员服务
147+阅读 · 2020年6月28日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
153+阅读 · 2020年5月26日
【阿尔托大学】图神经网络,Graph Neural Networks,附60页ppt
专知会员服务
181+阅读 · 2020年4月26日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
和积网络综述论文,Sum-product networks: A survey,24页pdf
专知会员服务
23+阅读 · 2020年4月3日
专知会员服务
61+阅读 · 2020年3月4日
论文浅尝 | GMNN: Graph Markov Neural Networks
开放知识图谱
20+阅读 · 2020年2月14日
图神经网络(Graph Neural Networks,GNN)综述
极市平台
104+阅读 · 2019年11月27日
【论文笔记】Graph U-Nets
专知
80+阅读 · 2019年11月25日
Graph Neural Networks 综述
计算机视觉life
29+阅读 · 2019年8月13日
CVPR2018 | Decoupled Networks
极市平台
4+阅读 · 2019年3月22日
论文报告 | Graph-based Neural Multi-Document Summarization
科技创新与创业
15+阅读 · 2017年12月15日
图上的归纳表示学习
科技创新与创业
23+阅读 · 2017年11月9日
BranchOut: Regularization for Online Ensemble Tracking with CNN
统计学习与视觉计算组
9+阅读 · 2017年10月7日
GAN的数学原理
算法与数学之美
14+阅读 · 2017年9月2日
Arxiv
12+阅读 · 2018年9月15日
Relational recurrent neural networks
Arxiv
8+阅读 · 2018年6月28日
Arxiv
3+阅读 · 2018年2月24日
Arxiv
10+阅读 · 2018年2月4日
Arxiv
7+阅读 · 2018年1月10日
VIP会员
相关资讯
论文浅尝 | GMNN: Graph Markov Neural Networks
开放知识图谱
20+阅读 · 2020年2月14日
图神经网络(Graph Neural Networks,GNN)综述
极市平台
104+阅读 · 2019年11月27日
【论文笔记】Graph U-Nets
专知
80+阅读 · 2019年11月25日
Graph Neural Networks 综述
计算机视觉life
29+阅读 · 2019年8月13日
CVPR2018 | Decoupled Networks
极市平台
4+阅读 · 2019年3月22日
论文报告 | Graph-based Neural Multi-Document Summarization
科技创新与创业
15+阅读 · 2017年12月15日
图上的归纳表示学习
科技创新与创业
23+阅读 · 2017年11月9日
BranchOut: Regularization for Online Ensemble Tracking with CNN
统计学习与视觉计算组
9+阅读 · 2017年10月7日
GAN的数学原理
算法与数学之美
14+阅读 · 2017年9月2日
相关论文
Top
微信扫码咨询专知VIP会员