原文:[2403.01121] OpenGraph: Towards Open Graph Foundation Models
一种 Zero-shot 图学习方法。
提出了一个统一的图标记器来调整我们的图模型,以便在未见过的图数据上很好地泛化,即使底层图属性与训练期间遇到的属性有很大不同。
开发了一个可扩展的图转换器作为基础编码器,它有效地捕获全局拓扑上下文中的节点依赖关系。
引入了由大型语言模型(LLM)增强的数据增强机制,以减轻现实场景中数据稀缺的限制。
基础定义
表示学习
图 G 由一组节点 V 和一组边 E 组成。边 e = (v_s, v_t ) ∈ \mathcal{E} 表示源节点 v_s 和目标节点 v_t 之间观察到的关系。另外,我们定义一个特征矩阵 \bold{F} ∈ \mathbb{R}^{| V |×f} 捕获所有节点的 f 维特征属性。图表示学习旨在通过将结构和属性信息转换为低维向量嵌入来捕获有意义的节点表示。这些嵌入对节点间依赖关系和关系的模式进行编码,促进链接预测和节点分类等图学习任务。链接预测侧重于预测在给定数据中未观察到的节点对 (v_s, v_t ) 之间建立连接的概率。节点分类任务旨在根据每个节点的特征以及与其他节点的关系为每个节点分配类别。这些任务可以正式表达为:
这里,链接标签 e_{s,t} ∈ \{0, 1\} 指示节点 v_s 是否连接到节点 v_t 。f 表示具有可学习参数集 θ_f 的预测模型。节点标签 y_s ∈ \mathcal{C} 表示节点 v_s 的真实类别,而 \mathcal{C} 表示候选类别的集合。
零样本图学习
零样本图学习在一组图上训练模型,并在不共享任何图标记的不同测试图上评估其性能。目标是评估图模型学习广义图拓扑结构和节点依赖关系的能力。正式定义如下:
该任务的目标是开发一个图模型,表示为 f (·),它可以有效地理解一般和普遍的拓扑模式。它还应该识别上下文相关的模式,这对于各种下游图学习任务的高性能至关重要。值得注意的是,训练图 (G_s) 和测试图 (G_t) 没有公共节点 (v ∈ V)、边 (e ∈ E) 或节点特征属性语义。这对图模型提出了独特的挑战,以处理具有完全不同数据集的不同图域中发生的重大分布变化。
方法
OpenGraph的整体架构。 i) 统一的图标记生成器可有效地将任何输入图转换为通用图标记,从而适应节点标记集的变化。 ii)可扩展图转换器使用锚点采样和高效的自注意力机制有效地捕获全局节点依赖关系。 iii) LLM 增强的数据增强技术用于合成图生成,解决特定领域数据可用性有限的问题。
统一图分词器
为了克服在节点、边和特征语义方面存在显着差异的不同图所带来的挑战,提出一个图分词器可以有效地将输入图转换为统一的标记序列。在我们的图记号(garph tokenizer)生成器中,每个记号代表一个节点,并附有一个语义向量,表示为 \mathcal{G} → \bold{e}_0, \bold{e}_1, · · · , \bold{e}_{|\mathcal{V} |} 。通过利用共享节点表示空间并采用灵活的序列数据结构标准化不同图上的节点分布。此外,我们将边缘信息合并到统一的节点表示中,忽略图之间的差异。为了解决节点特征的变化,引入了通过一致的映射过程生成的拓扑表示空间。
统一的图分词器利用平滑的邻接矩阵(表示为 \tilde{A})和拓扑感知投影函数 \phi:\mathbb{R}^{|\mathcal{V}|}\to\mathbb{R}^{d}。该分词器负责处理特定的图形表示。为了实现这一点,我们从原始邻接矩阵 A ∈ \mathbb{R}^{|\mathcal{V}|×| \mathcal{V} |} 从边 E 构造。邻接矩阵的平滑过程执行如下:
A 是邻接矩阵,D 是导出的对角度矩阵。对于矩阵 D,我们采用 A 的拉普拉斯归一化 \bar{A} 来确保数值稳定性。为了捕获高阶连接并解决稀疏观察的节点关系,结合不同阶的 \bar{A} 的力量使我们能够获得拓扑信息 \tilde{A} 以进行进一步处理,其中 L 代表所考虑的最大功率阶数。
为了处理不同图数据集中相邻矩阵 A 维度的显着变化,使用固定输入维度的随机神经网络是不可行的。为了应对这一挑战,提出了一种使用函数 \phi:\mathbb{R}^{|\mathcal{V}|}\to\mathbb{R}^{{d}} 的拓扑感知投影方法。通过消除其中一个不同的维度,我们的目标是减少降维过程中的信息丢失。为了实现这一点,我们采用了一个大的隐藏维度 d(已经证明,在利用大维度时,即使是随机投影也可以产生令人满意的性能)。因此,为了更好地保存图信息并最大限度地减少图标记器中的随机性,我们对投影函数 φ 使用快速奇异值分解(SVD)。实证分析表明,快速 SVD 的两次迭代有效地保留了拓扑信息,同时产生的计算开销可以忽略不计。形式上,我们的图标记生成器根据以下操作计算生成的标记序列:
通过 SVD 获得的拓扑感知投影由 \bold{U, V} ∈ \mathbb{R}^{|V |×d} 组成且 Λ ∈ \mathbb{R}^{d×d} 。连接运算符 ∥ 将它们组合在隐藏维度中。层归一化函数 LN(·) 减少了数据集之间的数值方差。由此产生的 \bold{e}_v ∈ \mathbb {R}^d 结合了来自 \tilde{A} 的拓扑信息和拓扑感知投影 φ。这些信息增强了后续可学习的神经网络。
可扩展图 Transformer
OpenGraph 利用图 Transformer 作为骨干来整合所有节点之间的全局依赖关系。为了确保可扩展性并有效处理大规模图形数据集,OpenGraph 引入一些技术提高了图 Transformer 主干的效率。
为了优化模型的效率,考虑到嵌入大小较大,图 Transformer 使用当前训练批次中的采样记号序列进行训练(Token Sequence Sampling)。具体来说,训练批次 \{(v_{c_b} , v_{p_b} , v_{n_b} )|b = 1, · · · , B\} 由中心节点 v_{c_b}、正节点 v_{p_b} 和负节点 v_{n_b} 的 B 个三元组组成,它们用作图 Transformer 的输入:
初始记号嵌入 e_v 有效地捕获每个节点 v ∈ V 的局部结构信息。通过使用采样的记号序列可以保留图上下文。这种方法显着减少了 |V | 的序列长度。到 3×B,实现大规模图的高效训练。此外,由于初始令牌嵌入 e_v 本质上对节点之间的拓扑紧密度进行编码,因此我们的图 Transformer 不依赖于时间或文本序列转换器中通常使用的时间嵌入。
尽管序列采样减少了节点序列的长度,但自注意力中的成对关系学习仍然表现出 O(B^2 × d) 的复杂度,这会限制计算效率所需的批量大小 B。为了应对这一挑战,我们引入了一个额外的步骤,即在自注意力计算期间对一组锚节点 v_{a_s} 进行采样,通过锚点采样实现高效的自注意力(Efficient Self-attention with Anchor Sampling),其中 s = 1, · · · , S。这里,S 选择为 d/H < B,以确保自注意力模块产生与其他全连接组件相似的内存成本。这里,H 代表注意力头的数量。更具体地说,每个头的自注意力过程可以总结如下:
我们有效的自注意力涉及锚节点 v_a 和普通节点 v_t 的嵌入 \mathbf{e}_*^{(1)},\mathbf{e}_*^{(2)},\mathbf{e}_*^{(3)}。每次注意力计算后,多个头的结果被连接起来,通过可学习的线性层,并与残差连接连接。参数 \mathbf{W}^{(q)},\mathbf{W}^{(k)},\mathbf{W}^{(v)} 是注意力层的参数。为了降低计算复杂度,我们采用两阶段自注意力过程。它将 3×B 长度的序列转换为较短的 S 长度序列,然后反转该过程。这种分解将复杂度从 O(B^2 × d) 降低到 O(B × S) ,确保了大规模模型的可扩展性。
在自注意力模块之后,可扩展图 Transformer 的每一层都包含一个具有残差连接的两层全连接块,并伴有两层归一化模块。为了确保数值稳定性,应用了每层缩放。
LLM 的知识蒸馏
由于隐私问题限制对基本数据的访问等因素,获取不同领域的多样化图数据集可能具有挑战性。利用LLM来增强多样化图结构数据的生成。为了提高 LLM 增强图数据预训练模型的效率,我们开发了一种增强机制。这种机制使LLM增强图数据非常接近现实世界的图形特征,增强数据的相关性和有用性。
在生成图时,第一步是创建适合特定应用场景的节点集。每个节点都有一个基于文本的配置文件,有助于生成后续的边。然而,由于节点集规模巨大,在处理现实场景时,这项任务可能特别具有挑战性。例如,在电子商务平台中,图数据可能由数十亿种产品组成。因此,如何高效地使LLM生成大量节点成为一个重大挑战。
为了解决上述挑战,我们采用了一种策略,该策略涉及迭代地将一般节点划分为具有更精细语义粒度的子类别。例如,在生成产品节点时,我们首先向 LLM 提示“列出亚马逊等电子商务平台上产品的所有子类别”之类的查询。LLM 回复了一系列子类别,例如“服装”、“家居和厨房”、“电子产品”等。然后,我们要求 LLM 进一步细化每个子类别,继续这个迭代划分过程。重复这个过程,直到我们获得与现实世界实例非常相似的节点,例如带有“服装”、“女装”、“毛衣”、“连帽毛衣”、“白色连帽毛衣”等标签的产品。
将节点划分为子类别并生成细粒度实体的过程遵循树结构。初始通用节点(例如“产品”、“深度学习论文”)作为根,细粒度实体作为叶节点。我们采用提示树策略来遍历并生成这些节点。
为了生成边,我们使用吉布斯采样算法和生成的节点集V。该算法从随机样本开始,该样本根据实体-实体关系数据的类型而变化。例如,在论文引用网络中,样本是节点对 (vs0, vt0 )。在像作者-论文或用户-项目推荐网络这样的人与实体关系场景中,初始样本是一个二元向量 a0 ∈ {0, 1}| V | 。每个元素 ai = 1 表示采样者与第 i 个节点 vi 之间有交互,而 ai = 0 表示没有交互。在人-实体关系的情况下,边缘采样的吉布斯算法在附录A.3.3中描述。关键是估计概率 p (at ⊕ vt′ |at ),
实验与代码
项目地址:GitHub - HKUDS/OpenGraph: [EMNLP'2024] "OpenGraph: Towards Open Graph Foundation Models"