首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >ICML2019 Self-Attention Graph Pooling

ICML2019 Self-Attention Graph Pooling

作者头像
Houye
修改于 2020-04-15 06:32:37
修改于 2020-04-15 06:32:37
1.4K0
举报
文章被收录于专栏:图与推荐图与推荐

本文转载自知乎专栏: NLP入门论文解析 作者: Taki https://zhuanlan.zhihu.com/p/104837556

小编语: 经典的CNN架构通常包含卷积层和池化层. GNN将CNN泛化到了图数据上,在很多领域得到了广泛的应用.但是,目前的GNN主要关注如何定义节点的邻居并聚合邻居信息(也就是卷积层的设计),对于池化并没有较多的关注. 那么,图上的池化层该怎么来做呢?有什么独特的挑战呢?

Links:arxiv.org/abs/1904.0808

Github:github.com/inyeoplee77/

Conference:ICML2019

0 Abstrcat

深度学习的框架迁移到结构化的数据近期也是个热点,近期的一些学习都在将卷积+pool迁移到非结构化的数据中【模仿CNN,目前LSTM,GRU还没有人模仿】,将卷积操作迁移到Graph中已经被证明是有效的,但是在Graph中downsampling依旧是一个挑战性的问题,上篇论文也研究了Graph Pool【link】。在这篇论文,我们提出了一种基于self-attention的graph pool方法,我们的pool方法包括node feature/graph topology两个特征,为了公平,我们使用一样的训练过程以及模型结构,实验结果证明我们的方法在Graph classification中表现的好。

1 Introduction

深度学习的方法在数据的识别和增强等方面有突飞猛进。特别,CNNs成功地挖掘了数据的特征,例如 欧几里得空间的images,speech,video。CNNs包括卷积层和下采样层,卷积和池化操作都有 shift-invariance特性(也叫作 stationary property)。因此CNNs只需要很小的参数就可以获得较好的结果。

在很多领域,然而,大量的数据,都是以非欧数据的形式储存的,例如 Social Network,Biological network,Molecular structure都是通过Graph中的Node以及Edge的形式表示的,因此很多人尝试将CNN迁移到非欧空间数据上。

在Graph Pool领域,方法远远少于Graph Convolution,之前的方法只考虑了Graph topology,还有其他的方法,希望获得一个更小点的Graph表示,最近,也有一些方法希望学习Graph的结构信息,这些方法允许GNNs用一种End2End的方法。然而,这些池化方法都还有提升空间,譬如需要立方级别的存储复杂度,Gao & Ji 的方法[link]解决了复杂度的问题,但是没有考虑图的拓扑结构。

由此我们提出了一种 SAGPool模型,是一种 Self-Attention Graph Pooling method,我们的方法可以用一种End2End的方式学习结构层次信息,Self-attention结构可以区分哪些节点应该丢弃,哪些应该保留。因为Self-attention结构使用了Graph convolution来计算attention分数,Node features以及Graph topology都被考虑进去,简而言之,SAGPool继承了之前模型的优点,也是第一个将self-attention 加入Graph pooling中,实现了较高的准确度。

2 Related Work

2.1 Graph Convolution

Graph卷积在之前文章里说了很多了。主要是Spectral/Spatial两个领域,Spatial领域的卷积主要是直接在Graph中计算,中心节点通过邻接矩阵接受邻居节点的信息。Hamilton et al提出了GraphSAGE,通过采样传递信息学习节点的embedding。但是GraphSAGE是在一个固定大小的邻居域内操作,而GAT模型是根据attention结构,计算节点所有的邻居,然后信息传递直到稳态(stationary)。

2.2 Graph Pooling

Pooling layer让CNN结构能够减少参数的数量【只需要卷积核内的参数】,从而避免了过拟合,为了使用CNNs,学习GNN中的pool操作是很有必要的,Graph pool的方法主要为三种:topology based,global,hierarchical pooling。

Topology based pooling。早先的工作使用Graph coarsening 算法,而不是神经网络。谱聚类方法使用特征值分解来获得粗化图,但是特征值分解是一个花费算力的过程,Graclus不需要特征值,使用介于general spectral clustering objective and a weighted kernel k-means objective方法。

Global pooling。不想之前的方法,global pool方法考虑Graph feature,使用summation or neural networks在每一个layer pool所有的节点表示,不同结构的图都适用,因为这个方法一次性处理所有的representations。Gilmer et al. 将GNNs看做信息传递的结构,提供了一个通用的结构,可以使用Set2Set来初始化进而获得Entire Graph的表示。SortPool根据在结构中的角色来给节点的embedding 分类,然后将排序后的embedding传递到下一层。

3. Proposed Method

SAGPool的key points是使用GNN来计算self-attention scores。在3.1结构我们详细叙述了SAGPool的结构以及它们的变体。3.2中详细解释了模型的结构,SAGPool layer和模型结构在Fig 1和Fig 2中展示出来。

3.1 Self-Attention Graph Pooling

Global pooling architecture 使用一个Global pooling结构,如Fig 2所示

Global pooling结构包含三个卷积层,将它们的输出连接起来。Node features在readout layer+pooling layer之下流动,Graph feature representions之后传输到线形层做分类。

Hierarchical pooling architecture 在这个设置下,如Fig 2所示那样,做一次卷积,做一次pooling,最后将三次pooling的结果加起来使用MLP来分类。

4. Experiments

使用Graph分类问题来测试global pooling/hierarchical pooling方法。在4.1讨论了evaluation的数据集,4.3描述了我们怎么训练模型,结果的比较在4.4/4.5中描述。

4.1. Datasets

Graph中节点超过1K的benchmark datasets共有5个节点,datasets的数据在Table 1中描述。

4.3 Training Procedures

Shchur et al 证明数据集的不同分割可能会影响GNN模型的表现。在我们的实验里,我们使用10-fold cross validation,使用20个随机种子,每个数据集一共得到200个实验结果。在训练的时候,10%的训练数据用来做验证。使用Adam optimizer,early stoping。如果每50轮后validation准确率没有明显提升就停止训练,最多训练100K轮次。使用grid search的方式来确定参数。

4.4 Baselines

4.6 Summary of Results

结果是如Table 3/Table 4所示。可以看出SAGPool表现不错。

5. Analysis

在这个部分,我们提供了实验结果的分析。

5.1 Global and Hierarchical Pooling

很难说哪种结构更好,POOLg最小化了信息的loss,在节点数较少的数据集【NCI1,NCI109,FRANKENSTEIN】上表现更好,然而,POOLh在节点数多的数据集上表现更好【D&D,PROTEINS】,因为POOLh在提取large scale graphs信息方面更拿手。不过,SAGPool比其他的模型更好。

5.2 Effect of Considering Graph Topology

SAGPool使用的是第一阶近似,这也就允许SAGPool考虑图的拓扑结构。正如Table 3,考虑图的拓扑结构表现更好。此外,graph Laplacian不需要重新计算,因为可以从相同位置的Graph Convolution layer传递过来。当SAGPool和gPool一样的参数,SAGPool在图分类问题上表现更好。

5.3 Sparse Implementation

邻接矩阵经常是稀疏的,所以Manipulating graph data with a sparse matrix非常重要。使用sparse martix可以降低内存复杂度和时间复杂度。

5.4 Relation with the Number of Nodes

在DiffPool中,cluster zise需要重新定义,因为GNN使用了matrix S。cluster size需要设置合适,否则会导致2个问题。1)参数的数量和最大节点数是相关的。

2)当Graph的大小不一的时候,很难决定合适的cluster size。

5.5 Comparison of the SAGPool Variants

省略

5.6 Limitations

我们在模型中使用了pooling ratio k,来处理不同的various size。在SAGPool,我们难以量化这个比例K,为了解决这个问题,我们使用二分类来觉得节点的保留与否,但是这没有解决问题。

6 Conclusion

老生常谈。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-02-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 图神经网络与推荐系统 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
终于有人总结了图神经网络!
本文从一个更直观的角度对当前经典流行的GNN网络,包括GCN、GraphSAGE、GAT、GAE以及graph pooling策略DiffPool等等做一个简单的小结。
abs_zero
2021/07/05
11.4K1
一文带你浏览Graph Transformers
3. GT 中甚至可以结合进 GNN 以及频域信息(Laplacian PE),模型会有更强的表现力。
NewBeeNLP
2022/11/11
1K0
一文带你浏览Graph Transformers
实战级Stand-Alone Self-Attention in CV,快加入到你的trick包吧 | NeurIPS 2019
论文: Stand-Alone Self-Attention in Vision Models
VincentLee
2020/03/02
1.2K0
图神经网络中的Graph Pooling
https://blog.csdn.net/leviopku/article/details/106949616
zenRRan
2020/11/19
3K0
图神经网络中的Graph Pooling
关于图神经网络(Graph Neural Networks,GNN)基础知识汇总1.0
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。
江夏四卯
2023/09/30
9.7K0
一文读懂简化的图卷积网络GCN(SGC)| ICML 2019
3.2 SGC and Low-Pass Filtering 简化的图卷积和低通滤波器
AI科技大本营
2019/10/31
2.7K0
【综述笔记】Graph Neural Networks in Recommender Systems
如今推荐系统的研究非常火热,GNN也在很多领域表现优异。推荐系统主要的挑战是从历史交互(historical interactions)和边信息(side information)中学习有效的用户(user)和物品(item)表示,由于很多信息具有图结构,而且GNN擅长表示学习,所以很多工作将GNN应用到推荐系统中。
guichen1013
2020/12/22
1.7K0
【综述笔记】Graph Neural Networks in Recommender Systems
GitHub图深度学习引用Top 10文章,你都看过吗?
Github地址:https://github.com/naganandy/graph-based-deep-learning-literature
AI科技大本营
2019/07/23
2K0
TNNLS | GNN综述:A Comprehensive Survey on Graph Neural Networks
题目:A Comprehensive Survey on Graph Neural Networks
Cyril-KI
2022/11/01
2K0
TNNLS | GNN综述:A Comprehensive Survey on Graph Neural Networks
如何应对变化的图数据分布? Non-IID Graph Neural Networks
本文的出发点是 graph-level 的图分类任务,在图分类中,每个图都被视为一个数据样本,目标是在一组训练图上训练一个分类模型,通过利用其相关节点特征和图结构来预测未标记图的标签。当建立一个用于图分类的 GNN model 时,训练集中的图数据假定满足同分布。然而在现实世界中,同一数据集中的图可能具有差异性很大的不同结构,即图数据彼此之间可能是非非独立同分布的(Non-IID)。基于此本文提出了一种适用于 Non-IID 图数据的 GNN model。具体来说,首先给定一个图,Non-IID GNN 可以适应任何现有的图神经网络模型,为该图数据生成一个特定样本的模型。
Houye
2021/12/15
1.3K0
如何应对变化的图数据分布? Non-IID Graph Neural Networks
Graph Neural Network(GNN)综述
图(graph)是一个非常常用的数据结构,现实世界中很多很多任务可以描述为图问题,比如社交网络,蛋白体结构,交通路网数据,以及很火的知识图谱等,甚至规则网格结构数据(如图像,视频等)也是图数据的一种特殊形式,因此图是一个很值得研究的领域。
SIGAI学习与实践平台
2019/05/16
2.4K0
Graph Neural Network(GNN)综述
ViTAE:引入归纳偏置,浅层用CNN,深层用self-attention
引入归纳偏置,即局部性和尺度不变性,浅层用CNN编码token,深层用多头注意力机制做transformer的模块堆叠,是一次CNN和transformer结合探索,也是一个对送进多头注意力机制的token编码的探索,送进更信息更加聚合的token,来降低模型大小,提高分类任务的效果。
BBuf
2022/02/11
1.3K0
ViTAE:引入归纳偏置,浅层用CNN,深层用self-attention
2W字长文 | 漫谈工业界图神经网络推荐系统
图神经网络是近年来很火的一个研究方向,在生物化学,推荐系统,自然语言处理等领域都得到了广泛应用。其中图神经网络在推荐系统的应用方面,已有几篇综述[1][2][3]做过详细的归纳总结。但是让人感到美中不足的是,综述中总结的多是学术型工作,偏向于GNN模型上的微调,部分工作其实就是将上游的SGC[4],GrapSage[5],JKNet[6]等模型在几个祖传玩具数据集上刷一下结果讲一个故事,很少关心模型的扩展性,也很少关心图的构建,特征处理,线上打分等不可或缺的环节。
Houye
2021/11/17
1.5K0
2W字长文 | 漫谈工业界图神经网络推荐系统
重磅整理!推荐系统之深度召回模型综述(PART III)
前段时间读完了李航、何向南的《Deep learning for matching in search and Recommendation》,文章思路清晰,总结详实到位,值得一再翻阅,就想借这篇文章结合自己最近一年多的推荐召回工作内容,总结一下推荐系统中的深度召回模型,论文因篇幅限制,很多模型并未详细介绍,因此本文补充了一些内容。
NewBeeNLP
2021/04/12
1.8K0
漫谈图神经网络 (二)
在从图(Graph)到图卷积(Graph Convolution): 漫谈图神经网络 (一)中,我们简单介绍了基于循环图神经网络的两种重要模型,在本篇中,我们将着大量笔墨介绍图卷积神经网络中的卷积操作。接下来,我们将首先介绍一下图卷积神经网络的大概框架,借此说明它与基于循环的图神经网络的区别。接着,我们将从头开始为读者介绍卷积的基本概念,以及其在物理模型中的涵义。最后,我们将详细地介绍两种不同的卷积操作,分别为空域卷积和时域卷积,与其对应的经典模型。读者不需有任何信号处理方面的基础,傅里叶变换等概念都会在本文中详细介绍。
Houye
2020/04/07
1.3K0
All Attention You Need
起因:《Sequence to Sequence Learning with Neural Networks》
Datawhale
2019/11/27
3730
GNN系列 综述 GNN GCN GraphSAGE GAT 简单理解 及调优Trick
图(graph)是一种数据结构,图神经网络(Graph Neural Network)应该是深度学习在图结构数据上的一些模型、方法和应用。常见的图结构由节点(node)和边(edge)构成,节点包含了实体(entity)信息,边包含实体间的关系(relation)信息。
大鹅
2022/09/04
3.4K0
CS224w图机器学习(七):Graph Neural Networks
本文主要介绍CS224W的第八课,图神经网络。上一篇章的主题是图表征学习,主要在讲Node Embedding,核心步骤包含编码网络和相似性度量。本文则是从图神经网络的角度出发,展开一些编码网络的深度方法。
慎笃
2021/09/15
5930
图神经网络的“前世今生”
从图像分类, 视频处理到语音识别, 自然语言处理. 深度学习通过端到端的训练彻底改变了很多机器学习任务. 但是这些任务的数据都是欧式空间上的规则数据. 而现实中很多数据之间都有着相当复杂的关系, 一般表现为非欧空间之上的图结构.
智能生信
2021/02/04
1.2K0
从图嵌入算法到图神经网络
近几年来,伴随着计算机算力的急剧提升,神经网络从历史的尘埃中走出,横扫各大领域,完成一次次颠覆性的创新。依托高度弹性的参数结构,线性与非线性的矩阵变换,神经网络能适用于各式各样的数学场景,在各个类别的应用上我们都能看到神经网络的影子。其中著名的应用方向,包括自然语言处理、计算机视觉、机器学习、生物医疗、推荐系统、自动驾驶等等。图神经网络,广泛应用于社交关系、知识图谱、推荐系统、蛋白质分子建模,同样源自于对传统领域的创新,它的前身是图嵌入算法;而图嵌入算法又以图数据作为载体。这一关系,将贯穿本文始末,成为我们的展开线索。
张小磊
2020/04/21
2K0
从图嵌入算法到图神经网络
推荐阅读
相关推荐
终于有人总结了图神经网络!
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档