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

2020 年 3 月 28 日 图与推荐
图机器学习 2.2-2.4 Properties of Networks, Random Graph

图机器学习 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图的非常自然的解释:每个节点由一系列分类属性值或特征来描述。然后,两个节点链接的可能性取决于各个属性相似性的乘积。


登录查看更多
9

相关内容

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

知识荟萃

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

更多

查看相关VIP内容、论文、资讯等

题目: Graph Random Neural Networks

摘要:

图神经网络(GNNs)将深度学习方法推广到图结构数据中,在图形挖掘任务中表现良好。然而,现有的GNN常常遇到具有标记节点的复杂图结构,并受到非鲁棒性、过度平滑和过拟合的限制。为了解决这些问题,本文提出了一个简单而有效的GNN框架——图随机神经网络(Grand)。与现有GNNs中的确定性传播不同,Grand采用随机传播策略来增强模型的鲁棒性。这种策略也很自然地使Grand能够将传播从特征转换中分离出来,减少了过度平滑和过度拟合的风险。此外,随机传播是图数据扩充的一种有效方法。在此基础上,利用无标记节点在多个扩展中的分布一致性,提高模型的泛化能力,提出了Grand的一致性正则化方法。在图形基准数据集上的大量实验表明,Grand在半监督的图形学习任务上显著优于最先进的GNN基线。最后,证明了它可以显著减轻过度平滑和过度拟合的问题,并且它的性能与鲁棒性相结合。

成为VIP会员查看完整内容
0
115

主题: TOPOLOGY OF DEEP NEURAL NETWORKS

摘要: 我们研究数据集M=Ma∪Mb⊆Rd的拓扑结构如何表示二进制分类问题中的两个类别a和b,如何通过经过良好训练的神经网络的层而发生变化,即在训练集和接近零的泛化误差(≈0.01%)。目的是揭示深层神经网络的两个奥秘:(i)像ReLU这样的非平滑激活函数要优于像双曲正切这样的平滑函数; (ii)成功的神经网络架构依赖于多层结构,即使浅层网络可以很好地近似任意函数。我们对大量点云数据集的持久同源性进行了广泛的实验,无论是真实的还是模拟的。结果一致地证明了以下几点:(1)神经网络通过更改拓扑结构来运行,将拓扑复杂的数据集在穿过各层时转换为拓扑简单的数据集。无论M的拓扑多么复杂,当通过训练有素的神经网络f:Rd→Rp时,Ma和Mb的贝蒂数都会大大减少;实际上,它们几乎总是减小到可能的最低值:对于k≥1和β0(f(Mi))= 1,i = a,b,βk(f(Mi))= 0。此外,(2)ReLU激活的Betti数减少比双曲线切线激活快得多,因为前者定义了改变拓扑的非同胚映射,而后者定义了保留拓扑的同胚映射。最后,(3)浅层和深层网络以不同的方式转换数据集-浅层网络主要通过更改几何结构并仅在其最终层中更改拓扑来运行,而深层网络则将拓扑变化更均匀地分布在所有层中。

成为VIP会员查看完整内容
0
21

时间序列数据的GANs通常使用滑动窗口或自我注意力来捕获底层的时间依赖关系。虽然这些技术没有明确的理论依据,但它们成功地大幅减小了判别器的尺寸,加快了训练过程,提高了生成质量。本文给出了时间序列数据等由贝叶斯网络捕获的具有条件独立结构的高维分布的广义统计分析的理论基础和实践框架。我们证明了几个概率发散满足关于贝叶斯网络图邻域的次可加性性质,给出了两个贝叶斯网络之间距离的一个上界,这个上界是图上每个邻域上它们的边缘距离之和。这就引出了我们提出的次加性GAN框架,该框架在Bayes-net的邻近区域使用一组简单的判别器,而不是在整个网络上使用一个巨大的鉴别器,从而提供了显著的统计和计算优势。我们证明了包括Jensen-Shannon, Total Variation, 和Wasserstein在内的几个概率距离具有次加性或广义次加性。此外,我们还证明了积分概率矩阵(IPMs)在某些温和条件下也具有次可加性。此外,我们证明了几乎所有的f-发散都满足局部次加性,当分布相对接近时,局部次加性保持不变。我们在合成数据集和真实数据集上的实验验证了所提出的理论和次加性GANs的优点。

成为VIP会员查看完整内容
0
49

题目: Logical Expressiveness of Graph Neural Networks

摘要:

图神经网络(Graph Neural Networks, GNNs)是近年来在分子分类、知识图谱补全等结构化数据处理领域中流行起来的一类机器学习体系结构。最近关于GNNs表达能力的研究已经建立了它们对图中节点进行分类的能力与用于检查图同构的WeisfeilerLehman (WL)测试之间的紧密联系。具体来说,这两篇论文的作者分别观察到,WL测试产生的节点分类总是细化了任何GNN产生的分类,而且有GNN可以重现WL测试。这些结果表明,GNNs在节点分类方面与WL测试一样强大。然而,这并不意味着GNNs可以表达任何通过WL测试改进的分类器。我们的工作旨在回答以下问题:什么是可以用GNNs捕获的节点分类器?在本文中,我们从逻辑的角度来看待这个问题,将其限制在FOC2中可表达的属性上,即具有计数能力的一阶逻辑的两变量片段进行研究。

作者:

Pablo Barceló是智利天主教大学工程学院和数学学院数学与计算工程研究所所长,研究领域为数据库理论、计算机科学中的逻辑、自动机理论。

成为VIP会员查看完整内容
0
32

Modeling generative process of growing graphs has wide applications in social networks and recommendation systems, where cold start problem leads to new nodes isolated from existing graph. Despite the emerging literature in learning graph representation and graph generation, most of them can not handle isolated new nodes without nontrivial modifications. The challenge arises due to the fact that learning to generate representations for nodes in observed graph relies heavily on topological features, whereas for new nodes only node attributes are available. Here we propose a unified generative graph convolutional network that learns node representations for all nodes adaptively in a generative model framework, by sampling graph generation sequences constructed from observed graph data. We optimize over a variational lower bound that consists of a graph reconstruction term and an adaptive Kullback-Leibler divergence regularization term. We demonstrate the superior performance of our approach on several benchmark citation network datasets.

0
3
下载
预览

Text Classification is an important and classical problem in natural language processing. There have been a number of studies that applied convolutional neural networks (convolution on regular grid, e.g., sequence) to classification. However, only a limited number of studies have explored the more flexible graph convolutional neural networks (e.g., convolution on non-grid, e.g., arbitrary graph) for the task. In this work, we propose to use graph convolutional networks for text classification. We build a single text graph for a corpus based on word co-occurrence and document word relations, then learn a Text Graph Convolutional Network (Text GCN) for the corpus. Our Text GCN is initialized with one-hot representation for word and document, it then jointly learns the embeddings for both words and documents, as supervised by the known class labels for documents. Our experimental results on multiple benchmark datasets demonstrate that a vanilla Text GCN without any external word embeddings or knowledge outperforms state-of-the-art methods for text classification. On the other hand, Text GCN also learns predictive word and document embeddings. In addition, experimental results show that the improvement of Text GCN over state-of-the-art comparison methods become more prominent as we lower the percentage of training data, suggesting the robustness of Text GCN to less training data in text classification.

0
12
下载
预览

Meta-graph is currently the most powerful tool for similarity search on heterogeneous information networks,where a meta-graph is a composition of meta-paths that captures the complex structural information. However, current relevance computing based on meta-graph only considers the complex structural information, but ignores its embedded meta-paths information. To address this problem, we proposeMEta-GrAph-based network embedding models, called MEGA and MEGA++, respectively. The MEGA model uses normalized relevance or similarity measures that are derived from a meta-graph and its embedded meta-paths between nodes simultaneously, and then leverages tensor decomposition method to perform node embedding. The MEGA++ further facilitates the use of coupled tensor-matrix decomposition method to obtain a joint embedding for nodes, which simultaneously considers the hidden relations of all meta information of a meta-graph.Extensive experiments on two real datasets demonstrate thatMEGA and MEGA++ are more effective than state-of-the-art approaches.

0
4
下载
预览

Memory-based neural networks model temporal data by leveraging an ability to remember information for long periods. It is unclear, however, whether they also have an ability to perform complex relational reasoning with the information they remember. Here, we first confirm our intuitions that standard memory architectures may struggle at tasks that heavily involve an understanding of the ways in which entities are connected -- i.e., tasks involving relational reasoning. We then improve upon these deficits by using a new memory module -- a \textit{Relational Memory Core} (RMC) -- which employs multi-head dot product attention to allow memories to interact. Finally, we test the RMC on a suite of tasks that may profit from more capable relational reasoning across sequential information, and show large gains in RL domains (e.g. Mini PacMan), program evaluation, and language modeling, achieving state-of-the-art results on the WikiText-103, Project Gutenberg, and GigaWord datasets.

0
8
下载
预览

We consider the task of learning the parameters of a {\em single} component of a mixture model, for the case when we are given {\em side information} about that component, we call this the "search problem" in mixture models. We would like to solve this with computational and sample complexity lower than solving the overall original problem, where one learns parameters of all components. Our main contributions are the development of a simple but general model for the notion of side information, and a corresponding simple matrix-based algorithm for solving the search problem in this general setting. We then specialize this model and algorithm to four common scenarios: Gaussian mixture models, LDA topic models, subspace clustering, and mixed linear regression. For each one of these we show that if (and only if) the side information is informative, we obtain parameter estimates with greater accuracy, and also improved computation complexity than existing moment based mixture model algorithms (e.g. tensor methods). We also illustrate several natural ways one can obtain such side information, for specific problem instances. Our experiments on real data sets (NY Times, Yelp, BSDS500) further demonstrate the practicality of our algorithms showing significant improvement in runtime and accuracy.

0
3
下载
预览

Graph Convolutional Neural Networks (Graph CNNs) are generalizations of classical CNNs to handle graph data such as molecular data, point could and social networks. Current filters in graph CNNs are built for fixed and shared graph structure. However, for most real data, the graph structures varies in both size and connectivity. The paper proposes a generalized and flexible graph CNN taking data of arbitrary graph structure as input. In that way a task-driven adaptive graph is learned for each graph data while training. To efficiently learn the graph, a distance metric learning is proposed. Extensive experiments on nine graph-structured datasets have demonstrated the superior performance improvement on both convergence speed and predictive accuracy.

0
5
下载
预览
小贴士
相关资讯
论文浅尝 | GMNN: Graph Markov Neural Networks
开放知识图谱
19+阅读 · 2020年2月14日
图神经网络(Graph Neural Networks,GNN)综述
极市平台
73+阅读 · 2019年11月27日
【论文笔记】Graph U-Nets
专知
60+阅读 · 2019年11月25日
Graph Neural Networks 综述
计算机视觉life
23+阅读 · 2019年8月13日
CVPR2018 | Decoupled Networks
极市平台
4+阅读 · 2019年3月22日
论文报告 | Graph-based Neural Multi-Document Summarization
科技创新与创业
15+阅读 · 2017年12月15日
图上的归纳表示学习
科技创新与创业
18+阅读 · 2017年11月9日
BranchOut: Regularization for Online Ensemble Tracking with CNN
统计学习与视觉计算组
9+阅读 · 2017年10月7日
GAN的数学原理
算法与数学之美
12+阅读 · 2017年9月2日
相关论文
Hongwei Wang,Jure Leskovec
28+阅读 · 2020年2月17日
Simon S. Du,Kangcheng Hou,Barnabás Póczos,Ruslan Salakhutdinov,Ruosong Wang,Keyulu Xu
8+阅读 · 2019年11月4日
Generative Graph Convolutional Network for Growing Graphs
Da Xu,Chuanwei Ruan,Kamiya Motwani,Evren Korpeoglu,Sushant Kumar,Kannan Achan
3+阅读 · 2019年3月6日
Liang Yao,Chengsheng Mao,Yuan Luo
12+阅读 · 2018年9月15日
Joint Embedding of Meta-Path and Meta-Graph for Heterogeneous Information Networks
Lichao Sun,Lifang He,Zhipeng Huang,Bokai Cao,Congying Xia,Xiaokai Wei,Philip S. Yu
4+阅读 · 2018年9月11日
Relational recurrent neural networks
Adam Santoro,Ryan Faulkner,David Raposo,Jack Rae,Mike Chrzanowski,Theophane Weber,Daan Wierstra,Oriol Vinyals,Razvan Pascanu,Timothy Lillicrap
8+阅读 · 2018年6月28日
Avik Ray,Joe Neeman,Sujay Sanghavi,Sanjay Shakkottai
3+阅读 · 2018年2月24日
Petar Veličković,Guillem Cucurull,Arantxa Casanova,Adriana Romero,Pietro Liò,Yoshua Bengio
8+阅读 · 2018年2月4日
Duhyeon Bang,Hyunjung Shim
7+阅读 · 2018年1月28日
Ruoyu Li,Sheng Wang,Feiyun Zhu,Junzhou Huang
5+阅读 · 2018年1月10日
Top