论文《Structural Information Enhanced Graph Representation for Link Prediction》阅读

论文《Structural Information Enhanced Graph Representation for Link Prediction》阅读

  • 论文概况
  • Introduction
    • 问题一:**现有的节点标记技巧只能帮助感知路径深度,而缺乏对路径“宽度”的感知,例如节点度或路径数量**。
    • 问题二:GNN 是以节点为中心的模型,其感受野是中心节点的邻域。然而,链接预测中的一些目标节点可能相距很远,GNN 很难捕获它们之间的远程信息。
    • 问题三:为了增强 GNN 的远程信息捕获能力,需要增加 GNN 层数以扩大感受野,但这可能会导致过度平滑和过度拟合等问题。
    • 问题四:计算是在所有元素之间成对执行的,导致计算复杂度呈二次方,并且**大量参数导致数据饥饿问题**。
    • 问题五:一些工作对图学习中的邻居提出了质疑,邻居特征在链接预测中的是否必要?
  • Method
    • 模块一:子图采样
    • 模块二:邻域结构编码
    • 模块三:成对结构编码
    • 模块四:链路解码
    • 复杂度计算
  • 总结

论文概况

本文是2024年AAAI上的一篇论文,该篇文章聚焦于使用GNN和自注意力网络来解决绘画推荐问题,提出了GCSAN(Graph Contextualized Self-Attention Network)模型。

Introduction

链接预测是根据图中现有的节点和边来预测缺失或潜在的边的任务,其典型应用包括知识补全、推荐等。链路预测的方法有很多种,其中基于图神经网络(GNN)的方法因其良好的性能和效率而成为主流。
GNN在许多领域取得了很好的成果。它们以某个节点为中心,通过消息传递(MP)将相邻节点和边的特征聚合到中心节点,善于学习节点表示。
但是GNN对图进行编码时,专注于捕获以节点为中心的邻居信息,而没有感知目标节点对的结构关系
最近,一些工作尝试通过节点标记技巧来解决这个问题。例如:ID-GNN:对目标节点进行着色以将其与邻居节点区分开来;SEAL:计算封闭子图中所有节点的 DRNL(双半径节点标签)。

问题一:现有的节点标记技巧只能帮助感知路径深度,而缺乏对路径“宽度”的感知,例如节点度或路径数量

此外,它们仍然受到 GNN 的 MP 范式的限制,导致链路预测的信息感知和传输方面存在缺陷:一方面,邻居节点标记收敛到目标节点然后聚合成关系表示的方式是隐式且复杂的,可能存在信息丢失的风险。另一方面,GNN 的感受野可能不足以进行链接预测

问题二:GNN 是以节点为中心的模型,其感受野是中心节点的邻域。然而,链接预测中的一些目标节点可能相距很远,GNN 很难捕获它们之间的远程信息。

在这里插入图片描述
图 1:GNN 失败的链接预测案例。在(a)中,节点h1和h2是同构的,但链路(h1,t)和(h2,t)不是同构的。 (b)和©显示了两种不同的结构,(d)显示了头节点h的公共计算图。
图 的右侧部分显示了一个简单的示例,其中 ID-GNN 和最常用的 3 层 GNN 的 SEAL 都无法区分(b)和(c)中所示的两种链接结构。当使用 GNN 计算头节点 h 的表示时,两种结构中的计算图(包括节点的 DRNL)是相同的,如图(d)所示,尾节点t的颜色没有聚合。因此,即使使用标签技巧,3 层 GNN 也无法区分这两个链接结构。

问题三:为了增强 GNN 的远程信息捕获能力,需要增加 GNN 层数以扩大感受野,但这可能会导致过度平滑和过度拟合等问题。

在本文中,作者提出了一个额外的注意力模块来弥补 GNN 在捕获成对结构和直接学习目标节点之间的关系表示方面的不足
自注意力是学习成对关系的强大机制,如Transformer,但它缺乏感知元素结构的能力

问题四:计算是在所有元素之间成对执行的,导致计算复杂度呈二次方,并且大量参数导致数据饥饿问题

为了捕获目标节点的成对结构特征,作者引入拓扑编码来编码成对启发式,例如最短路径距离(SPD)、Adamic-Adar等,并将它们融合到注意力中。
此外,作者的编码目标不是全局信息,而是 GNN 遗漏的目标节点的成对结构将注意力计算限制在目标节点上,避免昂贵的计算和引入来自其他节点的噪声的风险。因此,所提出的注意力模块专注于目标节点并有效地编码结构特征:二元结构注意力(BSA)。

问题五:一些工作对图学习中的邻居提出了质疑,邻居特征在链接预测中的是否必要?

作者尝试删除邻居节点特征。以表 1 中的 SEAL(在 ogbl-ppa 和 ogbl-引用2 上使用 NGNN)为例,我们观察到没有邻居节点特征的情况下的改进(实验设置与实验部分和附录中描述的建议方法相同)。这种现象与直觉相矛盾,但似乎是可以解释的:在链路预测中,邻居节点特征可能与任务无关并且容易产生噪声。例如,在预测配偶关系时,关键信息可能是两个人有一个共同的孩子,但孩子的兴趣、电话号码和其他特征可能并不重要。

对于上述问题,作者提出了一种用于链路预测(Structural Information Enhanced GraphS,IEG)的结构信息增强图表示框架。一方面,我们使用GNN收集目标节点的邻域信息,去除邻居节点特征,使模型更加关注结构特征。另一方面,引入(二元结构注意力)BSA对目标节点的成对特征,特别是长程结构特征进行编码,以补充GNN的不足。该方法方法在六个流行的基准测试中显示出卓越的性能,包括在 ogblppa、ogbl-itation2 和 Pubmed 上排名第一。

Method

在这里插入图片描述
整体架构。如图2所示,所提出的链接预测框架由四个主要部分组成:子图采样、用于邻域结构编码的结构信息增强GNN、用于成对结构编码的二进制结构变换(BST)和链接解码

模块一:子图采样

在这里插入图片描述
子图采样给定一个目标节点对 (vi , vj ),我们对其周围的 k 跳封闭子图进行采样。该子图由每个目标节点周围的两个 k 跳子图的并集组成两个子图之间的边也被合并。例如,在图 2 中,超出 1 跳的附加边 e1,5 包含在目标节点对 (h, t) 的 1 跳封闭子图中。与普通子图相比,封闭子图为链接预测提供了更好的连接性和更多信息输入。 WLNM已经证明,不仅一阶和二阶启发式特征可以在封闭子图中直接计算,而且即使是高阶启发式特征在少量跳数下也是可行的。

模块二:邻域结构编码

在这里插入图片描述
为了对邻域结构进行编码并学习每个目标节点的表示,可以使用任何 GNN。 GNN 通过以节点为中心的 MP 聚合邻域信息,典型形式如下所示:
在这里插入图片描述
归一化邻接矩阵、单位矩阵、节点嵌入矩阵、线性参数矩阵。
通常,可以通过聚合目标节点的各自嵌入来获得相似性表示。在这项工作中,我们采用了SortPooling 形成相似度表示。
为了增强对结构信息的拟合作者删除了邻居节点特征以避免潜在的噪声使模型更加关注目标节点的邻居结构。具体来说,输入到 GNN 的信息不包含任何节点特征,而是采用 DRNL 编码的结构特征。 DRNL对子图中每个节点与目标节点之间的距离进行编码,具体形式为:
在这里插入图片描述
另一方面,目标节点的节点特征用附加的前馈网络(FFN)进行编码,然后在池化之前与 GNN 编码的结构表示连接。

模块三:成对结构编码

使用标签技巧,GNN 框架对于链接预测也存在两个局限性:由于感受野受限而缺乏远程结构信息,以及以节点为中心的模型和以链接为中心的任务之间的冲突。为了解决这些缺点,作者提出了BST来专门捕获目标节点之间的成对结构和特征相似性,直接表示关系并补充GNN的局限性
在这里插入图片描述
BST 的核心 BSA 的计算如图所示。该过程涉及两个输入:目标节点的特征和目标节点对的结构特征。后者使用启发式方法计算,如最短路径距离(SPD)、最短路径数(SPN)、公共邻居(CN)、杰卡德指数、阿达米克-阿达尔指数(AA)等。例如,Jaccard 和 AA 计算为
在这里插入图片描述
除了描述节点对的连接路径之外,Jaccard 和 AA还分别引入目标节点的边数和共同邻居的度,以进行归一化。此外,作者还采用结构查找嵌入结合节点特征嵌入来获得结构编码,从而增强结构信息的表示:
在这里插入图片描述
在这里插入图片描述
其中Pquery(SPD)和P key(SPD)表示以SPD作为两个单独的参数化表P query和 P key的索引 查找 获得的两个结构向量,从其他启发式方法获得的结构向量遵循相同的过程。然后,将所有查询结构向量用公式7,8聚合。
然后,通过公式5将两个结构向量分别与 qi 和 kj 相乘,并将它们相加以获得结构编码,记为 bij 。这里,qi和kj是目标节点特征的线性变换,WQ和WK表示变换矩阵。这有效地将丰富的启发式结构与节点特征融合起来,表征了目标节点的结构相关性。最后,将结构编码 bij 合并到注意力系数 aij 中:
在这里插入图片描述
其中 d 是 qi 的维度。为了获得单头 BSA 的结果,我们将 softmax 归一化注意力系数与值嵌入相乘,然后将多个头连接起来形成多头 BSA:
在这里插入图片描述
在这里插入图片描述
其中值嵌入 vj 是 hj 到 WV 的线性变换。符号∥表示concatenate操作,WO是多头融合的线性变换矩阵
在这里插入图片描述
最后,BST 块由 BSA、层归一化 (LN)、残差连接 和 FFN 组件组成,如图 2 所示。与常规 Transformer 类似,成对结构编码模块 BST,是通过堆叠多个BST块得到的。
与常规 Transformer 相比,所提出的 BST 具有多个优点:
1.避免了远离目标的节点引入的潜在噪声和过度泛用风险。
2.收集更多与任务相关的结构信息。
3.计算复杂度大大降低

模块四:链路解码

在这里插入图片描述
一般来说,邻域嵌入和成对嵌入可以与任何专门设计的技术融合,以获得良好的链接预测结果。模块最后连接嵌入以形成关系表示,并使用多层感知器(MLP)将其解码为链接分数。这个过程被表述为
在这里插入图片描述

复杂度计算

在这里插入图片描述
与 FCA 相比,BSA 显着降低了计算复杂度。 FCA 需要两个主要的计算成本:SPD 搜索和注意力计算,复杂度分别为 O(N(N + E) log N) 和 O(N2D + ND2 )。这里,N和E表示子图中的节点和边的数量,D表示节点特征的维度。相比之下,BSA 的计算复杂度远低于 FCA,如表 2 所示,SPD 的计算复杂度仅为 O((N + E) log N),Attention 的计算复杂度为 O(D2 )。
Transformer 的整体计算成本与 SPD 和 Attention 的计算成本之和成正比。因此,从全连接变压器(FCT)到BST的加速比范围为N到N2,当N<D或N>D时,可以分别近似为N或N2。 BST 有效地解决了 Transformer 在链路预测中计算成本高昂的问题,使 SIEG 能够应用于更大规模的数据集。

总结

本文从理论上分析了 GNN 在信息感知和传输方面对于链路预测的两个固有缺陷,并通过实验发现了邻居节点特征的有害影响。为了解决这些问题,我们提出了一种结构信息增强的链接预测框架,该框架涉及去除邻居节点特征,同时通过 GNN 拟合更集中的邻居结构,并引入 BST 来编码目标节点之间的结构关系,补充 GNN 的缺陷。所提出的方法在六个流行基准上取得了显着的结果,包括在 ogbl-ppa、ogbl-itation2 和 Pubmed 上排名第一。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520456.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

软考117-上午题-【计算机网络】-杂题+小结

一、杂题 真题1&#xff1a; 真题2&#xff1a; 真题3&#xff1a; 真题4&#xff1a; 真题5&#xff1a; 真题6&#xff1a; 真题7&#xff1a; 真题8&#xff1a; 真题9&#xff1a; 真题10&#xff1a; 真题11&#xff1a; 真题12&#xff1a; 真题13&#xff1a; 真题14&a…

【算法集训】基础算法:二分查找 | 概念篇

二分枚举&#xff0c;也叫二分查找&#xff0c;指的就是给定一个区间&#xff0c;每次选择区间的中点&#xff0c;并且判断区间中点是否满足某个条件&#xff0c;从而选择左区间继续求解还是右区间继续求解&#xff0c;直到区间长度不能再切分为止。 由于每次都是把区间折半&am…

AUTOSAR MCAL for SemiDrive E3 功能模块使用介绍:I2C

一、 概述 本文主要介绍如何使用芯驰提供的 AUTOSAR MCAL 软件包&#xff0c;开发 SemiDrive E3 的 I2C 模块&#xff0c;对 RTC 芯片进行读写操作。 硬件使用 E3640 GATEWAY 开发板&#xff0c;软件包为 mcal3.1。 图1 硬件环境 二、模块简介 E3 系列最多支持 8 个 I2C&am…

【51单片机入门记录】A/D D/A转换器概述

目录 一、A/D D/A转换器简介 &#xff08;1&#xff09;模数转换器-ADC &#xff08;analogue-to-digital conversion&#xff09; &#xff08;2&#xff09;数模转换器-DAC&#xff08;digital-to-analogue conversion&#xff09; &#xff08;3&#xff09;应用场景 二…

全国计算机等级考试三级Linux应用与开发技术考试-习题汇总

https://blog.csdn.net/qq_42025798/article/details/119155696 3.第1章-计算机体系结构与操作系统-练习题-简答题 https://blog.csdn.net/qq_42025798/article/details/119186151 4.第1章-计算机体系结构与操作系统-练习题-填空题 https://blog.csdn.net/qq_42025798/article/…

gulp项目配置,压缩css,压缩js,进行监听文件改动

1&#xff0c;创建项目 npm install -g gulp这个应该很熟悉&#xff0c;就是全局安装gulp 2&#xff0c;创建一个工程&#xff0c;使用node创建&#xff0c;统一命令 npm init -y3,创建后&#xff0c;目录出现一个package.json文件&#xff0c;没错&#xff0c;就是我们用vu…

【Leetcode每日一题】模拟 - 外观数列(难度⭐⭐)(51)

1. 题目解析 题目链接&#xff1a;38. 外观数列 这个问题的理解其实相当简单&#xff0c;只需看一下示例&#xff0c;基本就能明白其含义了。 2.算法原理 所谓“外观数列”&#xff0c;其实只是依次统计字符串中连续且相同的字符的个数。依照题意&#xff0c;依次模拟即 可。…

Java面向对象进阶基础知识

面向对象进阶 static 静态变量 被该类的所有的对象共享 不属于对象,属于类 随着类的加载而加载,优先于对象存在 类名调用(推荐) 对象名调用 static的注意事项 静态方法中没有this关键字 静态方法,只能访问静态 非静态方法可以访问所有 在Java中&#xff0c;static关…

元宇宙虚拟空间的碰撞体检测(四)

前言 该文章主要讲元宇宙虚拟空间的碰撞体检测&#xff0c;基本技术点&#xff0c;不多说&#xff0c;直接引入正题。 碰撞体检测 这里可以看到检测代码的逻辑是经过一系列判断&#xff0c;最后判断模型类型属性如果是trimesh&#xff0c;那么通过解析出来的顶点来生成我们的…

Linux:IO多路转接之select

文章目录 selecttimeval结构体fd_set 优缺点分析完整代码 本节要介绍的主题是多路转接式IO select 先说结论&#xff0c;这个select是做什么的呢&#xff1f; select是负责在Linux系统中&#xff0c;让一个人可以有多个鱼竿&#xff0c;可以不停的进行轮询&#xff0c;只要有…

【C语言基础】:文件操作详解(前篇:准备知识)

文章目录 一、什么是文件以及文件的分类1.1 程序文件1.2 数据文件1.3 文件名 二、文本文件和二进制文件2.1 数据在文件中的存储 三、文件的打开和关闭3.1 流和标准流3.1.1 流3.1.2 标准流 3.3 文件指针3.5 文件的打开和关闭 一、什么是文件以及文件的分类 文件是指存储在计算机…

【SCI绘图】【曲线图系列1 python】绘制扫描点平滑曲线图

SCI&#xff0c;CCF&#xff0c;EI及核心期刊绘图宝典&#xff0c;爆款持续更新&#xff0c;助力科研&#xff01; 本期分享&#xff1a; 【SCI绘图】【曲线图1 python】绘制扫描点平滑曲线图 1.环境准备 python 3 import numpy as np import pandas as pd import proplot …

代码随想第31天 | 122.买卖股票的最佳时机II 、 55. 跳跃游戏 、 45.跳跃游戏II

一、前言 参考文献&#xff1a;代码随想录 今天主要还是贪心&#xff0c;但是是比较难想到的题目&#xff0c;不管那么多吧&#xff0c;直接做吧&#xff01; 二、买卖股票的最佳时机|| 1、思路&#xff1a; 这个思路我确实想不出来&#xff0c;但是这个思路又异常的简单&…

MySQL复制拓扑1

文章目录 主要内容一.安装MySQL服务器1.MySQL 安装程序和其它文件保存在下发的 mysql8-files.iso 镜像文件中&#xff0c;可以使用虚拟光驱来提取到 Linux 文件系统。代码如下&#xff08;示例&#xff09;: 2.将 MySQL8.0 程序解压到 /opt 目录&#xff0c;再创建到 MySQL 默认…

c# wpf LiveCharts 绑定 简单试验

1.概要 c# wpf LiveCharts 绑定 简单试验 2.代码 <Window x:Class"WpfApp3.Window2"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schem…

嵌入式驱动学习第六周——内核函数调用(堆栈打印)

前言 在内核中&#xff0c;函数调用堆栈非常重要&#xff0c;因为它可以帮助开发人员理解代码是如何执行的&#xff0c;从而进行调试、性能优化或问题排查。堆栈可以显示当前执行的函数以及导致该函数调用的先前函数&#xff0c;从而形成一个函数调用链。本篇博客就介绍堆栈打印…

编程新手必看,学习python中字符串数据类型内容(8)

1、 Python3 字符串 字符串是 Python 中最常用的数据类型。我们可以使用引号( ’ 或 " )来创建字符串。 创建字符串很简单&#xff0c;只要为变量分配一个值即可。例如&#xff1a; var1 Hello World! var2 "Runoob"Python 访问字符串中的值 Python 不支持单…

虚拟主机、VPS主机和云服务器的区别

对于每个建站新手来说&#xff0c;首先要解决的就是服务器购买的问题&#xff0c;目前市面有很多类型的服务器&#xff0c;常见的有&#xff1a;阿里云、腾讯云、Vultr云服务器&#xff0c;也有RackNerd、Cloudways等提供的VPS&#xff0c;还有SiteGround、ChemiCloud 、 Hosti…

如何保护大模型API安全

大模型的崛起正在改变着我们对机器学习和人工智能的理解&#xff0c;它们不仅提供了令人惊叹的预测和分析能力&#xff0c;还在各行各业的应用中发挥着重要作用。通过提供 API&#xff0c;用户无需了解底层实现细节&#xff0c;使大型模型能够更好地与用户和应用程序进行交互&a…