Home

引言 此为原创文章，未经许可，禁止转载 前面的文章中，我们介绍了GNN的三个基本模型GCN、GraphSAGE、GAT，分析了经典的GCN逐层传播公式是如何由谱图卷积推导而来的。GNN模型现在正成为学术研究的热点话题，那么我们不经想问，GNN模型到底有多强呢？之前的文章我们介绍了用来衡量GNN表达能力的算法—Weisfeiler-Leman，这篇文章我们将以该算法为基础，向大家介绍ICLR 2019的oral论文 How powerful are graph neural networks 。 图神经网络 Graph Neural Network GNNs 利用图结构和节点初始特征$X_0$学习图节点的表示(embeddings)$h_v$，或者整个图的表示$h_G$。前面我们...

一、引言 此为原创文章，未经许可，禁止转载 前面的文章中，我们介绍了GNN的三个基本模型GCN、GraphSAGE、GAT，分析了经典的GCN逐层传播公式是如何由谱图卷积推导而来的。GNN模型现在正处于学术研究的热点话题，那么我们不经想问，GNN模型到底有多强呢？ 我们的目的是分析GNN的表达能力，我们需要一个模型作为衡量标准。比如说如果我们想衡量GBDT的分类能力的话，通常情况下我们会使用同样的数据集，采用不同的分类模型如LR, RF, SVM等做对比。对于GNN模型，我们采用的对比模型叫做Weisfeiler-Leman，其常被用做图同构测试(Graph Isomorphism Test)，图同构测试即给定两个图，返回他们的拓扑结构是否相同。图同构问题是一个非常难的问题，目前...

本篇文章主要受 如何理解 Graph Convolutional Network? 来自superbrother的回答 的启发，在此表示感谢！如有侵权，请联系我删除。 引言 图神经网络的逐层更新公式简单优雅而高效，以GCN为例，节点Embedding是由自身和邻居节点Embedding的聚合之后再进行非线性变换而得到。如此简单优雅的更新规则是怎么推导出来的呢，背后有没有什么理论依据？在GCN的论文中，作者介绍了两种启发GCN逐层线性传播法则的方法，分别是从谱图卷积的角度和Weisfeiler-Lehman算法的角度。本篇博文将详细介绍如何从图拉普拉斯矩阵出发，通过定义图上的傅里叶变换和傅里叶逆变换而定义图上卷积公式，最后推导出优雅的GCN逐层更新公式。至于Weisfeiler-Le...

规划 图神经网络是表征学习中兴起的一个新方向，本博客将以论文带读的方式讨论图神经网络的最新进展。下图展示了目前的规划： 这篇博文会记录进度，预计每一周或两周完成一个模块，规划也会随时更新。 进度 2019-06-01：完成”基础：三剑客”模块 GCN GraphSAGE GAT 2019-06-12: 完成”谱图卷积”模块 Spectral Graph 2019-06-19: 有同学反馈对图的基本概念不是很了解，于是加上了一个基本介绍 GNN Basics 2019-06-24：完成”表达能力模块” WL algorithm GNN power 2019-06-30：”框架模块” DGL sampler ...

此为原创文章，转载务必保留出处 引言 在前两篇博文中，我们讨论了基本的图神经网络算法GCN, 使用采样和聚合构建的inductive learning框架GraphSAGE, 然而图结构数据常常含有噪声，意味着节点与节点之间的边有时不是那么可靠，邻居的相对重要性也有差异，解决这个问题的方式是在图算法中引入“注意力”机制(attention mechanism), 通过计算当前节点与邻居的“注意力系数”(attention coefficient), 在聚合邻居embedding的时候进行加权，使得图神经网络能够更加关注重要的节点，以减少边噪声带来的影响。 图注意力机制的类型 目前主要有三种注意力机制算法，它们分别是：学习注意力权重(Learn attention weights)...

此为原创文章，转载务必保留出处 引言 在GCN的博文中我们重点讨论了图神经网络的逐层传播公式是如何推导的，然而，GCN的训练方式需要将邻接矩阵和特征矩阵一起放到内存或者显存里，在大规模图数据上是不可取的。其次，GCN在训练时需要知道整个图的结构信息(包括待预测的节点), 这在现实某些任务中也不能实现(比如用今天训练的图模型预测明天的数据，那么明天的节点是拿不到的)。GraphSAGE的出现就是为了解决这样的问题，这篇博文中我们将会详细得讨论它。 Inductive learning v.s. Transductive learning 首先我们介绍一下什么是inductive learning. 与其他类型的数据不同，图数据中的每一个节点可以通过边的关系利用其他节点的信息，这样就...

此为原创文章，转载务必保留出处 引言 这是我们介绍图神经网络的第一篇文章，取自Kipf et al. 2017，文章中提出的模型叫Graph Convolutional Network(GCN)，个人认为可以看作是图神经网络的“开山之作”，因为GCN利用了近似的技巧推导出了一个简单而高效的模型，使得图像处理中的卷积操作能够简单得被用到图结构数据处理中来，后面各种图神经网络层出不穷，或多或少都受到这篇文章的启发。 问题定义 考虑图（例如引文网络）中节点（例如文档）的分类问题，假设该图中只有一小部分节点标签（label）是已知的，我们的分类任务是想通过这部分已知标签的节点和图的结构来推断另一部分未知标签的节点的标签。这类问题可以划分到基于图结构数据的半监督学习问题中。半监督学习（se...

引言 图卷积神经网络(Graph Convolutional Network)作为最近几年兴起的一种基于图结构的广义神经网络结构，因为其独特的计算能力，而受到广泛学者的关注与研究。传统深度学习模型 LSTM 和 CNN 在欧几里得空间数据(语言，图像，视频等)上取得了不错的成绩，但是在对非欧几里得空间数据(eg：社交网络、信息网络等)进行处理上却存在一定的局限性。 针对该问题，研究者们引入了图论中抽象意义上的图(Graph)来表示非欧几里得结构化数据。并利用图卷积网络对来图(Graph)数据进行处理，以深入发掘其特征和规律。 本文首先分别介绍了欧几里得结构化数据和非欧几里得结构化数据特点；然后，针对非欧几里得结构化数据的表示问题，引入了图论中抽象意义上的图(Graph)概念，并对...