#####好好好#####论文分享 | Learning Aligned-Spatial GCNs for Graph Classification

本文主要是介绍#####好好好#####论文分享 | Learning Aligned-Spatial GCNs for Graph Classification,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目前大部分GCN方法可以被归为两类:Spectral(基于频域)卷积和 Spatial(基于空域)卷积。前者主要基于 Spectral Graph Theory 将图信号变换到谱域与滤波器系数进行相乘再做逆变换[1][2],这种方法处理的图结构常常是固定大小的(节点个数固定)并且主要解决的是节点分类问题。然而现实中图数据的大小往往不固定,例如生物信息数据中的蛋白质结构、社交网络中的用户关系等,基于 Spatial 策略的图卷积操作可以直接定义在邻居节点上,通过采样或排序的方式将邻居节点聚合从而学习图的拓扑特征。尽管如此,Spatial 策略的 GCN 在将卷积层学习到的不同大小图的多尺度特征输入给分类器之前仍要将其转换为固定大小表示,常见的方法就是将图的各节点特征进行加和池化得到图的全局特征,这会造成图局部特征信息的损失,因此这类 Spatial 策略的 GCN 方法在图分类上具有相对较差的性能。

这篇论文提出了一种空间对齐(Aligned-Spatial)图卷积网络 ASGCN,用于解决图分类问题,将任意大小的图通过传递的对齐方法(Transitive Alignment)转化为固定大小的图结构,并定义了一个与之相关的图卷积运算方式。ASGCN 不仅减少了局部信息的损失,还可以自适应指定不同邻居节点在信息聚合中的重要性,因此在很多图分类数据集上都展现出了很好的分类性能。

任意大小图的传递对齐

论文提出一种图匹配方法用于节点的传递对齐,算法框架分3步,如图1所示:

图1

假设数据集所有图共包含n个节点,算法框架:

第1步:使用一种Node Embedding方法将所有节点嵌入到 K 维空间进行向量化表示,所有向量可用集合表示;

第2步:使用一种聚类方法从集合中计算出M个聚类中心节点(M为超参数)构成一个模板图;

第3步,将所有图结构与M个节点的模板图进行传递对齐,对齐后任意大小的图都被转化为M个节点的固定大小。

具体而言,论文中第1步使用的 Node Embedding 方法是作者于2014年提出的基于深度的特征表示算法[3] Depth-Based(DB) Representation,该方法是一种无监督的Node Embedding方法,并已被证实可以有效地表征节点从局部到全局的拓扑信息,第p个图结构第i个节点的K层深度特征向量记作 。

第2步论文中使用的是常见的Kmeans算法,则关于全部节点的 M 个聚类中心 可通过最小化以下目标函数得到:

论文第3步首先计算原始图结构与模板图结构的节点集合计算距离矩阵,设第p个原始图结构与模板图结构的K维节点向量距离矩阵为,则原始图的第i个节点与模板图的第j个节点距离可由以下公式计算:

如果距离矩阵中的第 i 行、第 j 列元素在整个 i 行中最小,说明原始图的第i个节点与模板图的第 j 个节点最相似,论文将这种关系称为原始图的第i个节点与模板图的第 j 个节点是对齐的。基于上述规则,可以从距离矩阵中得到原始图与模板图的对齐矩阵:

其中每行仅有一个元素为1其余元素为0,表示原始图的每个节点都对应一个模板图中的节点,反过来与模板图中特定节点对应的原始图节点可能有多个。

值得注意的是,当两个原始图结构中的节点都与相同的模板图结构中的节点对齐时,这两个原始图结构中的节点也是相互对齐的,因此这种对齐关系是传递的。

得到对齐矩阵后,假设第p个图结构的带self-loop的邻接矩阵为 ,节点的属性特征矩阵为 ,则将原始图结构通过对齐转化为M节点固定大小的图结构的公式如下:

上述传递对齐算法流程与作者在2016年提出的针对模式空间的节点匹配算法[4]类似。(篇幅限制本文介绍传递对齐算法略有缩减,具体细节请参考论文原文)

新的Spatial图卷积运算操作

经过传递对齐后的所有图结构均有M个节点,且任意对齐后的图结构的邻接矩阵所对应的节点都与模板图节点共享相同排序,即无论原始图结构节点在邻接矩阵中的排列顺序是否改变,对齐后图结构的邻接矩阵都保持了相同的节点排列顺序,这种节点的置换不变性(Permutation Invariance)使得后面设计的新图卷积运算成为可能。对于第h个滤波器,新的Spatial图卷积运算公式如下:

其中Zh 是M个维度为 c 的节点信号 在通过第h个滤波器后得到的M个维度为1的节点信号,是元素位乘积(Element-wise Hadamard Product),是M个维度为c的可训练权重矩阵。假设输入的图结构有5个节点,单个节点信号维度为3,则针对节点v2,节点特征信号在通过单一滤波器进行上述图卷积操作时的具体计算示意图如下:

论文提出的图卷积运算与大部分现有的图卷积运算最大的区别,即图中任意节点都被分配了相应不同的可训练权重,使得训练过程中网络可以自适应地区分指定节点之间的重要性。

空间对齐的图神经网络

基于上述提出的传递对齐算法框架以及与之对应的新型Spatial图卷积运算,论文给出了一个空间对齐的图神经网络结构,结构如下图所示:

首先网络的第1部分进行的是无监督学习,通过传递对齐将所有大小不一的原始图结构转化为相同大小的图结构;网络的第2部分是将转化后的图结构输入给新型Spatial图卷积层;网络的第3部分首先将第2部分各图卷积层的输出进行拼接组合,再将拼接后的节点信号输入给传统的1D卷积层、池化层,最后经过全连接层输出分类结果。

实验

论文选择了在图分类问题中常见的标准数据集[5],其中包含生物信息图结构以及社交网络图结构,具体数据集信息如下:

对比的方法包括传统的Graph Kernel方法以及基于深度学习的方法。

与Graph Kernel的实验对比效果如下:

与深度学习的实验对比效果如下:

实验证明提出的ASGCN方法在大部分数据集中都显著优越于其他方法,无论是Graph Kernel还是深度学习的方法。值得注意的是,在对比实验中,论文提出的ASGCN方法在处理所有不同数据集时,都使用了相同的网络结构(卷积层数、输出维度)及模板图大小设置(M取值)。对于不同数据集,实验变化的超参数只有学习率(learning rate)以及迭代次数(epoch),因此论文认为如果针对不同数据集,网络结构以及模板图大小也做出相应的调整优化,会得到比当前更好的实验效果。

总结

论文提出了一种新的基于空间的GCN模型ASGCN,将任意大小的图转换为固定大小的对齐结构,并在对齐图结构上执行新的Spatial图卷积操作。与大多数现有的基于Spatial的GCN不同,ASGCN可以在图卷积操作的过程中自适应地区分指定节点之间的重要性,这也解释了ASGCN相比大部分现有GCN在实验上表现更好的原因。

相关链接

论文作者主页:

https://www.researchgate.net/profile/Lu_Bai3

Graph Kernel:

https://www.zhihu.com/question/57269332/answer/157375170

参考文献

[1] Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2013). Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203.

[2] Henaff, M., Bruna, J., & LeCun, Y. (2015). Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.05163.

[3] Bai, L., & Hancock, E. R. (2014). Depth-based complexity traces of graphs. Pattern Recognition, 47(3), 1172-1186.

[4] Bai, L., Rossi, L., Zhang, Z., & Hancock, E. (2015, June). An aligned subtree kernel for weighted graphs. In International Conference on Machine Learning (pp. 30-39).

[5] Kersting, K., Kriege, N., Morris, C., Mutzel, P., & Neumann M. (2016). Benchmark Data Sets for Graph Kernels. (2016). http://graphkernels.cs.tu-dortmund.de

这篇关于#####好好好#####论文分享 | Learning Aligned-Spatial GCNs for Graph Classification的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/967566

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

AI hospital 论文Idea

一、Benchmarking Large Language Models on Communicative Medical Coaching: A Dataset and a Novel System论文地址含代码 大多数现有模型和工具主要迎合以患者为中心的服务。这项工作深入探讨了LLMs在提高医疗专业人员的沟通能力。目标是构建一个模拟实践环境,人类医生(即医学学习者)可以在其中与患者代理进行医学

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

java常用面试题-基础知识分享

什么是Java? Java是一种高级编程语言,旨在提供跨平台的解决方案。它是一种面向对象的语言,具有简单、结构化、可移植、可靠、安全等特点。 Java的主要特点是什么? Java的主要特点包括: 简单性:Java的语法相对简单,易于学习和使用。面向对象:Java是一种完全面向对象的语言,支持封装、继承和多态。跨平台性:Java的程序可以在不同的操作系统上运行,称为"Write once,

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

OmniGlue论文详解(特征匹配)

OmniGlue论文详解(特征匹配) 摘要1. 引言2. 相关工作2.1. 广义局部特征匹配2.2. 稀疏可学习匹配2.3. 半稠密可学习匹配2.4. 与其他图像表示匹配 3. OmniGlue3.1. 模型概述3.2. OmniGlue 细节3.2.1. 特征提取3.2.2. 利用DINOv2构建图形。3.2.3. 信息传播与新的指导3.2.4. 匹配层和损失函数3.2.5. 与Super

分享5款免费录屏的工具,搞定网课不怕错过!

虽然现在学生们不怎么上网课, 但是对于上班族或者是没有办法到学校参加课程的人来说,网课还是很重要的,今天,我就来跟大家分享一下我用过的几款录屏软件=,看看它们在录制网课时的表现如何。 福昕录屏大师 网址:https://www.foxitsoftware.cn/REC/ 这款软件给我的第一印象就是界面简洁,操作起来很直观。它支持全屏录制,也支持区域录制,这对于我这种需要同时录制PPT和老师讲

BERT 论文逐段精读【论文精读】

BERT: 近 3 年 NLP 最火 CV: 大数据集上的训练好的 NN 模型,提升 CV 任务的性能 —— ImageNet 的 CNN 模型 NLP: BERT 简化了 NLP 任务的训练,提升了 NLP 任务的性能 BERT 如何站在巨人的肩膀上的?使用了哪些 NLP 已有的技术和思想?哪些是 BERT 的创新? 1标题 + 作者 BERT: Pre-trainin