用于自然语言处理的图神经网络综述

编程入门行业动态更新时间:2024-10-14 06:25:29

用于<a href=https://www.elefans.com/category/jswz/34/1768401.html style= 自然语言处理的图神经网络综述"/>

用于自然语言处理的图神经网络综述

由于博主主要对如何将序列数据转化为图数据感兴趣，所以只对综述中的自然语言处理的图构造方法、基于图的自然语言处理方法和用于 N L P NLP NLP的图表示学习方法进行了笔记总结，对 E n c o d e r − D e c o d e r Encoder-Decoder Encoder−Decoder架构以及自然语言处理任务感兴趣的小伙伴可以看看原文Graph Neural Networks for Natural Language Processing: A Survey。

1. 基于图的自然语言处理算法

1.1 随机游走算法

为了进行随机游走，可以从图中的任意节点开始，并根据一定的转移概率反复选择下一步访问的随机的邻居节点。随机游走中所有访问的节点形成一个随机路径。随机游走收敛之后，可以获得图中所有节点的稳定分布，得到这一分布之后，可以通过将概率分数排名获得具有高结构重要性的图中最显著的节点，或者通过计算两个随机游走分布之间的相似性度量两张图的关联性。

应用：文本语义相似性和语义网络上的语义距离度量、词义消歧、姓名消歧、查询扩展、关键字提取以及跨语言信息检索。

1.2 图聚类算法

谱聚类：谱聚类算法利用图的拉普拉斯矩阵的谱（特征值）进行降维，然后使用现有的K-means算法进行聚类。

随机游走聚类：随机游走聚类算法通过在图上进行 t t t步随机游走，从而将每个节点表示为一个代表图中所有其他节点的 t t t步生成概率的概率向量。任何聚类算法都可以应用于生成链路向量。请注意，对于图聚类来说，一个小的 t t t值更可取，因为我们更感兴趣的是捕获局部结构信息，而不是全局结构信息（在随机游走收敛后由稳定分布编码）。

最小切割聚类：最小切割算法也可以用于将图划分成簇。（没细讲算法）

应用：文本聚类任务。

1.3 图匹配算法

图匹配算法旨在计算两个图之间的相似性。其中，图编辑距离是衡量两个图的不相似性最常用的方法。它将距离计算为将一个图转换为另一个图所需的更改次数（即添加、删除、替换），然后将不相似度得分转换为相似度得分。

应用：图匹配算法在文本隐含任务中有应用，目的是决定是否可以从文本中推断出给定的句子。

1.4 标签传播算法

标签传播算法（ L P A s LPAs LPAs）是一类半监督的基于图的算法，它将标签从有标记的数据点传播到以前没有标记的数据点。基本上， L P A s LPAs LPAs通过在图中迭代地传播和聚合标签来操作。在每次迭代中，每个节点都会根据其邻居节点所拥有的标签来更改自己标签。因此，标签信息通过图扩散。

应用： L P A LPA LPA在网络科学文献中被广泛用于发现复杂网络中的社区结构。在自然语言处理文献中， L P A LPA LPA已成功应用于词义消歧和情绪分析。

1.5 局限和与图神经网络的联系

局限：虽然传统的基于图的算法已经成功地应用于许多自然语言处理任务中，但它们也有一些局限性。

（1）它们的表达能力有限。它们主要关注于捕获图的结构信息，但不考虑节点和边的特征，而这对许多自然语言处理应用非常重要。

（2）传统的基于图的算法目前还没有一个统一的学习框架。不同的基于图的算法具有非常不同的性质和设置，并且只适用于某些特定的情况。

近年来，神经网络作为一种特殊的能够建模任意图结构数据的神经网络受到越来越多的关注。大多数 G N N GNN GNN变体可以看作是一个基于消息传递的学习框架。与传统的基于消息传递的算法，如 L P A LPA LPA通过在图中传播标签来操作不同， G N N GNN GNN通常通过几个神经层转换、传播和聚合节点/边的特征来操作，以便学习更好的图表示。 G N N GNN GNN作为一种通用的基于图的学习框架，可以应用于各种与图相关的任务，如节点分类、链路预测和图分类。

2. 自然语言处理的图构造方法

2.1 静态的图构造

我们总结了 G N N GNN GNN中针对 N L P NLP NLP文献的各种静态图构造方法，并将它们共分为11类。我们假设输入是一个文档 d o c = { p a r a 1 , p a r a 2 , . . . , p a r a n } doc=\{para_1, para_2, ..., para_n\} doc={para1,para2,...,paran}, 由 n n n个被标记为 p a r a para para的段落组成。同样地，一个段落由 m m m个句子组成，表示为 p a r a i = { s e n t 1 , s e n t 2 , . . . , s e n t m } para_i=\{sent_1, sent_2, ..., sent_m\} parai={sent1,sent2,...,sentm}。每个句子由 l l l个词组成，表示为 s e n t i = { w 1 , w 2 , . . . , w l } sent_i=\{w_1, w_2, ..., w_l\} senti={w1,w2,...,wl}。

2.1.1 静态图构造方法

依赖关系图构造：形式为，给出一段话，可以通过使用各种 N L P NLP NLP解析工具（如 S t a n f o r f C o r e N L P StanforfCoreNLP StanforfCoreNLP）获得依赖解析树（如语法依赖树或语义依赖解析树），然后可以从依赖解析树中提取依赖关系，并将它们转换为依赖图。

步骤1：构造依赖关系。给定特定段落中的句子，首先获得每个句子的依赖关系解析树。我们将依赖树中的依赖关系表示为 ( w i , r e l i , j , w j ) (w_i, rel_{i, j}, w_j) (wi,reli,j,wj)，其中 w i w_i wi， w j w_j wj是由一个边类型 r e l i , j rel_{i, j} reli,j连接的单词节点。从概念上讲，边表示依赖关系“ w i w_i wi在关系 r e l i , j rel_{i, j} reli,j上依赖于 w j w_j wj”。我们将依赖关系集定义为 R d e p \mathcal{R}_{dep} Rdep。

步骤2：构造序列关系。序列关系对原始段落中元素的相邻关系进行编码。具体地说，对于依赖关系图的构造，我们定义了序列关系集 R s e q ⊆ V × V \mathcal{R}_{seq}\subseteq\mathcal{V}\times\mathcal{V} Rseq⊆V×V，其中， V \mathcal{V} V是基本元素（即单词）集合。对于每个序列关系 ( w i , w i + 1 ) ∈ R s e q (w_i, w_{i+1})\in\mathcal{R}_{seq} (wi,wi+1)∈Rseq，它意味着 w i w_i wi在给定的段落中与 w i + 1 w_{i+1} wi+1相邻。

步骤3：最终图转换。依赖图 G ( V , E ) \mathcal{G}(\mathcal{V}, \mathcal{E}) G(V,E)由单词节点和上面讨论的两种关系组成。给定段落 p a r a para para，依赖关系集 R d e p \mathcal{R}_{dep} Rdep和序列关系集 R s e q \mathcal{R}_{seq} Rseq，首先，对于每个关系 ( w i , r e l i , j , w j ) ∈ R d e p (w_i, rel_{i, j}, w_j)\in\mathcal{R}_{dep} (wi,reli,j,wj)∈Rdep，添加节点 v i v_i vi（用于表示单词 w i w_i wi）和节点 v j v_j vj（用于表示单词 w j w_j wj），以及从节点 v i v_i vi到节点 v j v_j vj的有向边，边类型为 r e l i , j rel_{i, j} reli,j。其次，对于每个关系 ( w i , w j ) ∈ R s e q (w_i, w_j)\in\mathcal{R}_{seq} (wi,wj)∈Rseq，我们添加两个节点 v i v_i vi（用于表示单词 w i w_i wi）和 v j v_j vj（用于表示单词 w j w_j wj），以及节点 v i v_i vi和 v j v_j vj之间的一条特定序列类型的无向边。

成分图构造：与依赖关系分析不同的是，依赖关系分析只关注单个词之间一对一的对应关系（即词级），而成分分析则对一个或几个对应词的组合进行建模（即短语级）。

步骤1：成分关系。一般来说，选区关系来源于主语（名词短语 N P NP NP）-谓语（动词短语 V P VP VP）关系。在这部分中，我们只讨论来自成分解析树的成分关系。与所有节点都具有相同类型的依赖解析树不同，成分解析树则区分了终端节点和非终端节点。成分语法的非终端类别标记了解析树的内部节点（例如， S S S表示句子， N P NP NP表示名词短语）。而叶节点用终端类别（句子中的单词）进行标记。节点集可以表示为：1）非终端节点集 V n t \mathcal{V}_{nt} Vnt（如 S S S和 N P NP NP）和2）终端节点集 V w o r d s \mathcal{V}_{words} Vwords。成分关系集与树的边相关联，可以表示为 R c o n s ⊆ V n t × ( V n t + V w o r d s ) \mathcal{R}_{cons}\subseteq\mathcal{V}_{nt}\times(\mathcal{V}_{nt}+\mathcal{V}_{words}) Rcons⊆Vnt×(Vnt+Vwords)。

步骤2：成分图构建。成分图 G ( V , E ) \mathcal{G}(\mathcal{V}, \mathcal{E}) G(V,E)由非终端节点 V n t \mathcal{V}_{nt} Vnt和终端节点 V w o r d s \mathcal{V}_{words} Vwords，以及成分边和序列边组成。与依赖关系图类似，给定一个段落和成分关系集 R c o n s \mathcal{R}_{cons} Rcons，对于每个成分关系 ( w i , r e l i , j , w j ) ∈ R d e p (w_i, rel_{i, j}, w_j)\in\mathcal{R}_{dep} (wi,reli,j,wj)∈Rdep，可以添加节点 v i v_i vi（用于表示单词 w i w_i wi）和节点 v j v_j vj（用于表示单词 w j w_j wj），以及从节点 v i v_i vi到节点 v j v_j vj的有向边。然后，对于原始文本中相邻的单词的每个单词节点对 ( v i , v j ) (v_i, v_j) (vi,vj)，在它们之间添加一条具有特定序列类型的无向边。这些序列边用于保留顺序信息。

A M R AMR AMR图构造： A M R AMR AMR图是有根的、有标记的、有向的、无环图，被广泛用于表示非结构化的抽象概念和具体自然文本之间的高级语义关系。与句法特性不同， A M R AMR AMR是一种高级的语义抽象。更具体地说，语义相似的不同句子可能共享相同的 A M R AMR AMR解析结果，例如，“Paul described himself as a fighter”和“Paul’s description of himself: a fighter”，如图3所示。除了 A M R AMR AMR偏向于英语的事实，它是语言分析的一个强大的辅助表示。

步骤1: A M R AMR AMR关系。从概念上讲， A M R AMR AMR解析树中有两种类型的节点：1）名称（例如，“Paul”）是节点实例的具体值；2）要么是英语单词（例如，“boy”）、 P r o p B a n k PropBank PropBank框架集的概念（例如，“want-01”），要么是特殊的关键词的概念。名称节点是唯一的标识，而概念节点则由不同的实例共享。连接节点的边被称为关系（例如:ARG0和:name）。可以从由边连接的节点对中提取这些 A M R AMR AMR关系，记为 ( n i , r e l i , j , n j ) ∈ R a m r (n_i, rel_{i, j}, n_j)\in\mathcal{R}_{amr} (ni,reli,j,nj)∈Ramr。

步骤2: A M R AMR AMR图。类似于依赖关系图和成分图，给定句子 s e n t sent sent和 A M R AMR AMR关系集 R a m r \mathcal{R}_{amr} Ramr，对于每条关系 ( n i , r e l i , j , n j ) ∈ R a m r (n_i, rel_{i, j}, n_j)\in\mathcal{R}_{amr} (ni,reli,j,nj)∈Ramr，我们添加节点 v i v_i vi（用于表示 A M R AMR AMR节点 n i n_i ni）和节点 v j v_j vj（用于表示 A M R AMR AMR节点 n j n_j nj），并添加一条从节点 v i v_i vi到节点 v j v_j vj的有向边，边类型为 r i , j r_{i, j} ri,j。

信息提取图的构造：信息提取图（IE Graph）旨在提取结构信息来表示自然句子之间的高级信息，如基于文本的文档。这些提取的关系捕获了距离遥远的句子之间的关系，已经被证明在许多自然语言处理任务中是有帮助的。

步骤1：指代消解。指代消解是信息提取任务的基本过程，目的是在文本序列中寻找指向相同实体的表述。如图4所示，名称“Pual”、名词术语“He”和“a renowned computer scientist”可以指同一个对象（人）。我们将指代簇 C C C表示为指代同一对象的一组短语。给定一段，可以得到从非结构化数据中提取的指代集 C = C 1 , C 2 , . . . , C n C={C_1, C_2, ..., C_n} C=C1,C2,...,Cn。

步骤2: I E IE IE关系。为了构建一个 I E IE IE图，第一步是从段落中提取三元组，这可以通过利用一些著名的信息提取系统（即 O p e n I E OpenIE OpenIE）来完成。我们称每个三元组（主语，谓词，宾语）为一个关系，它被表示为 ( n i , r i , j , n j ) ∈ R i e (n_i, r_{i, j}, n_j)\in\mathcal{R}_{ie} (ni,ri,j,nj)∈Rie。值得注意的是，如果两个三元组只因一个参数不同，而其他参数重叠，一个只保留较长的三元组。

步骤3: I E IE IE图构造。 I E IE IE图 G ( V , E ) \mathcal{G}(\mathcal{V}, \mathcal{E}) G(V,E)由上面讨论的IE节点和IE关系组成。给定段落和IE关系集 R i e \mathcal{R}_{ie} Rie，对于每个关系 ( n i , r i , j , n j ) ∈ R i e (n_i, r_{i, j}, n_j)\in\mathcal{R}_{ie} (ni,ri,j,nj)∈Rie，添加节点 v i v_i vi（表示主语 n i n_i ni）和 v j v_j vj（表示宾语 n j n_j nj），并从节点 v i v_i vi到节点 v j v_j vj添加相应的谓词类型的有向边。然后，对于每个指代簇 C i ∈ C C_i\in C Ci∈C，我们可以将 C i C_i Ci中的所有指代短语分解成一个节点。这可以大大减少节点的数量，并通过只保留一个节点来消除歧义。

话语图构造：当文档太长时，许多 N L P NLP NLP任务都会遭受长时间的依赖挑战。话语图描述了两个句子是如何在逻辑上相互联系的，它被证明可以有效地应对这一挑战。

步骤1：话语关系。话语关系来源于语篇分析，其目的是识别一组句子上的句子排序约束。给定两个句子 s e n t i sent_i senti和 s e n t j sent_j sentj，可以将话语关系定义为 ( s e n t i , s e n t j ) (sent_i, sent_j) (senti,sentj)，表示“句子 s e n t j sent_j sentj可以放在句子 s e n t i sent_i senti之后”的话语关系。话语分析已经被探索多年，发展了许多话语关系建模理论，如修辞结构理论（ R S T RST RST）和 G − F l o w G-Flow G−Flow。在许多 N L P NLP NLP任务中，给定一个文档 d o c doc doc，首先将文档分割成句子集 V = { s e n t 1 , s e n t 2 , . . . , s e n t m } \mathcal{V}=\{sent_1, sent_2, ..., sent_m\} V={sent1,sent2,...,sentm}。然后应用话语分析得到成对话语关系集 R d i s ⊆ V × V \mathcal{R}_{dis}\subseteq\mathcal{V}\times\mathcal{V} Rdis⊆V×V。

步骤2：话语图。话语图 G ( V , E ) \mathcal{G}(\mathcal{V}, \mathcal{E}) G(V,E)由上面讨论的句子节点和话语关系组成。给定文档 d o c doc doc和话语关系集 R d i s \mathcal{R}_{dis} Rdis，对于每个关系 ( s e n t i , s e n t j ) ∈ R d i s (sent_i, sent_j)\in \mathcal{R}_{dis} (senti,sentj)∈Rdis，添加节点 v i v_i vi（表示句子 s e n t i sent_i senti）和节点 v j v_j vj（表示句子 s e n t j sent_j sentj），并添加从节点 v i v_i vi到节点 v j v_j vj的有向边。

知识图构造：捕获实体和关系的知识图（KG）可以极大地促进许多 N L P NLP NLP应用中的学习和推理。一般来说，KG根据它们的图构造方法不同可以分为两大类。许多应用程序将KG视为非结构化数据（如文档）的稠密和可解释的中间表示，从概念上讲，它几乎类似于我们之前讨论过的IE图。另一方面，许多其他工作合并现有知识库，如 Y A G O YAGO YAGO和 C o n c e p t N e t ConceptNet ConceptNet，以进一步提高下游任务的性能。在下面，我们将从图构造的角度简要讨论第二类知识图。

KG可以记为 G ( V , E ) \mathcal{G}(\mathcal{V}, \mathcal{E}) G(V,E)，通常由知识库中的元素构造。形式上，将三元组 ( e 1 , r e l , e 2 ) (e_1, rel, e_2) (e1,rel,e2)定义为知识库中的基本元素，其中 e 1 e_1 e1是源实体， e 2 e_2 e2是目标实体， r e l rel rel是关系类型。然后在KG中添加两个节点 v 1 v_1 v1（用于表示源元素 e 1 e_1 e1)和 v 2 v_2 v2（用于表示目标元素 e 2 e_2 e2)，并从节点 v 1 v_1 v1到节点 v 2 v_2 v2添加类型为 r e l rel rel的有向边。如图5是知识图的一个示例。在文献中，知识图的构造方法可能会有很大的差异。在这里，我们对一种具有代表性的方法来进行说明。构造KG的第一件事是在给定的查询中获取术语实例。然后，可以通过一些匹配算法，如最大子串匹配，将术语实例与KG中的概念连接起来。这些概念被视为所提取的子图中的初始节点。下一步是获取KG中初始节点的1跳邻居。此外，我们还可以通过应用一些图节点相关性模型，如个性化 P a g e R a n k PageRank PageRank（PPR）算法，来计算邻居与初始节点的相关性。然后，根据这些结果，我们可以进一步剔除相关性得分低于置信阈值的边，并去除孤立的邻居节点。剩下的最终子图随后用于为任意图表示学习模块提供信息。

共指图构造：在语言学中，当某个段落中的两个或多个术语指代同一个对象时，就会出现共指。许多研究表明，这种现象有助于更好地理解语料库的复杂结构和逻辑，并解决歧义。为了有效地利用共指信息，构造了共指图来显式地建模隐式的共指关系。给定一组短语，一个共引用图可以把在文本语料库中指向同一实体的节点（短语）连接起来。

步骤1：共指关系。共指关系可以很容易地通过共指解析系统得到，如在IE图构造中所讨论的。类似地，我们可以得到给定的一个具体段落的共指簇集合 C \mathcal{C} C。集群 C i ∈ C C_i\in \mathcal{C} Ci∈C中的所有短语都是指向同一个对象。

步骤2：共指图。共指图依靠共指关系集 R c o r e f \mathcal{R}_{coref} Rcoref建立。根据节点类型，一般可分为两个主要类别：1）短语（或提及）2）单词。对于第一类，共指图 G \mathcal{G} G由关系集 R c o r e f \mathcal{R}_{coref} Rcoref中的所有提及组成。对于集群 C k ∈ C C_k\in \mathcal{C} Ck∈C中的每个短语对 p i p_i pi， p j p_j pj，可以在节点 v i v_i vi（用来表示短语 p i p_i pi）和节点 v j v_j vj（用来表示节点 p j p_j pj）之间添加一条无向边。在第二种情况下，共参照图 G \mathcal{G} G由单词组成。一个小的区别是，对于每对相关的短语，只连接每个短语的第一个单词。

相似图构造：相似图旨在量化节点之间的相似度，在许多自然语言处理任务中得到广泛应用。由于相似图通常是面向应用的，因此我们关注于为实体、句子和文档等各种类型的元素构造相似度图的基本过程，而忽略了应用程序的特定细节。值得注意的是，相似图的构建是在预处理过程中进行的，而没有与其余的学习系统进行端到端联合训练。

步骤1：相似性图。给定一个语料库 C C C，在一个相似图 G ( V , E ) \mathcal{G}(\mathcal{V}, \mathcal{E}) G(V,E)中，图的节点可以被定义为不同的粒度级别，如实体、句子和文档。不管具体节点类型如何，我们将基础节点集表示为 V V V。我们可以通过各种机制得到节点特征，如句子（或文档）的 T F − I D F TF-IDF TF−IDF和实体嵌入。然后，节点对之间的相似度得分可以通过余弦相似度等各种指标来计算，并用于表示节点对的边权值。

步骤2：稀疏机制。初始相似图通常是密集的，甚至一些边的权值非常小，甚至是负的。这些值可以被视为噪声，而噪声在相似度图中所起的作用不大。因此，提出了各种稀疏技术，通过使图稀疏化来进一步提高图的质量。一种广泛使用的稀疏方法是 k − N N k-NN k−NN。具体来说，对于节点 v i v_i vi和它的邻居集 N ( v i ) N(v_i) N(vi)，一个节点只保留 k k k个最大边权值的边并删除剩余的边。另一种广泛使用的方法是 ϵ \epsilon ϵ−稀疏法，我们将去除权值小于特定阈值 ϵ \epsilon ϵ的边。

共现图构造：共现图旨在捕捉文本中单词之间的共现关系，这在许多自然语言处理任务中得到了广泛的应用。共现关系，它描述了两个词在一个固定大小的上下文窗口中同时出现的频率，是一个获取语料库中单词之间的语义关系的重要特征。

步骤1：共现关系。共现关系由给定的语料库 C C C的共现矩阵来定义。对于一个特定段落 p a r a para para，段落由 m m m个句子组成，共现矩阵描述了单词如何同时出现。我们可以将共现矩阵表示为 M ∈ R ∣ V ∣ × ∣ V ∣ M\in \mathbb{R}^{|V|\times |V|} M∈R∣V∣×∣V∣，其中 ∣ V ∣ |V| ∣V∣为语料库 ∣ C ∣ |C| ∣C∣的词汇表大小。 M w i , w j M_{w_i, w_j} Mwi,wj描述了单词 w i w_i wi， w j w_j wj在语料库 ∣ C ∣ |C| ∣C∣中的一个固定大小的滑动窗口中同时出现的次数。在得到共现矩阵后，有两种典型的方法来计算单词之间的权重：1）共现频率，2）点互信息（ P M I PMI PMI）。

步骤2：共现图。共现图 G ( V , E ) \mathcal{G}(\mathcal{V}, \mathcal{E}) G(V,E)由上面讨论的单词节点和共现关系组成。给定语料库 C C C和共现关系集 R c o R_{co} Rco，对于每个关系 ( w i , w j ) ∈ R c o (w_i, w_j)\in R_co (wi,wj)∈Rco，添加节点 v i v_i vi（用来表示单词 w i w_i wi）和节点 v j v_j vj（用来表示单词 w j w_j wj），并添加一条从节点 v i v_i vi到节点 v j v_j vj的无向边，用上述计算的边权值初始化。

主题图构造：该主题图建立在多个文档之上，旨在建模不同主题之间的高级语义关系。具体地，给定一组文档 D = { d o c 1 , d o c 2 , . . . , d o c m } \mathcal{D}=\{doc_1, doc_2, ..., doc_m\} D={doc1,doc2,...,docm}，首先使用一些主题建模算法，如 L D A LDA LDA，来学习被表示为 T T T的潜在主题。然后可以用 V = D ∪ T \mathcal{V}=\mathcal{D}\cup \mathcal{T} V=D∪T构造主题图 G ( V , E ) \mathcal{G}(\mathcal{V}, \mathcal{E}) G(V,E)。仅当文档具有该主题时，才会生成节点 v i v_i vi（针对文档）和节点 v j v_j vj（针对主题）之间的无向边。

应用驱动图构造：应用驱动图指的是专门为特定的自然语言处理任务而设计的图，前面讨论的静态图类型不能简单地概括这一类图。在一些 N L P NLP NLP任务中，用特定应用的方法通过结构化的形成来表示非结构化的数据是很常见的。例如， S Q L SQL SQL语言可以很自然地用 S Q L SQL SQL解析树来表示。因此，我们就可以将其转换为 S Q L SQL SQL图。由于这些图基于领域知识，过于专业化，因此没有统一的模式来总结如何构建一个应用驱动图。

2.1.2 构造并讨论混合图

以前的大多数静态图构造方法只考虑节点之间的一个特定关系。虽然所得到的图在一定程度上很好地捕获了结构信息，但它们在利用不同类型的图关系方面也受到了限制。为了解决这一限制问题，人们对通过合并多个图来构建混合图，以此丰富图中的语义信息越来越感兴趣。构造混合图的方法大多是针对应用的，因此我们只总结了一些具有代表性的构造混合图的方法。为了捕获多个关系，一种常见的策略是构造一个包含多种类型的节点和边的异构图。一般情况下，我们假设可以用两个不同的图源 G a ( V a , E a ) \mathcal{G}_a(\mathcal{V}_a, \mathcal{E}_a) Ga(Va,Ea)和 G b ( V b , E b ) \mathcal{G}_b(\mathcal{V}_b, \mathcal{E}_b) Gb(Vb,Eb)创建一个混合图 G h y b i r d \mathcal{G}_{hybird} Ghybird。图 a a a、 b b b是两种不同类型的图，如依赖关系图和成分图。给定这些文本输入，如果 G a \mathcal{G}_a Ga和 G b \mathcal{G}_b Gb共享节点集（即 V a = V b \mathcal{V}_a=\mathcal{V}_b Va=Vb），我们通过标注表示特定关系的边来合并边集。否则，我们合并 V a \mathcal{V}_a Va和 V b \mathcal{V}_b Vb得到混合节点集，记为 V = V a ∪ V b \mathcal{V}=\mathcal{V}_a\cup \mathcal{V}_b V=Va∪Vb。然后，我们通过将 V a \mathcal{V}_a Va和 V b \mathcal{V}_b Vb之间的源节点和目标节点映射到 V \mathcal{V} V，来生成 E a \mathcal{E}_a Ea和 E b \mathcal{E}_b Eb到 E \mathcal{E} E的映射。

2.2 动态的图构造

虽然静态图构造具有将数据的先验知识编码到图结构中的优点，但它也有一些局限性。首先，为了构建一个合理的性能图拓扑，需要大量的人力努力和领域专业知识。其次，手动构建的图结构可能容易出错（例如，有噪声或不完整）。第三，由于图构建阶段和图表示学习阶段是不相交的，因此在图构建阶段引入的误差无法得到纠正，可能会累积到后期阶段，从而导致性能下降。最后，图的构建过程往往只由 N L P NLP NLP从业者的见解来决定，并且对于下游预测任务可能是次优的。为了应对上述挑战，最近关于 N L P NLP NLP的 G N N GNN GNN的尝试开始探索动态图的构建，而不需要借助人工或领域专业知识。大多数动态图构建方法的目的是动态地学习图结构（即加权邻接矩阵），图构建模块可以与后续的图表示学习模块以端到端的方式向下游任务进行联合优化。如图10所示，这些动态图的构造方法通常包括一个图相似度度量学习部分，通过考虑嵌入空间中每对节点的相似度来学习邻接矩阵，以及一个从学习到的全连通图中提取稀疏图的图稀疏化部分。将固有的图结构和学习到的隐含图结构结合起来，有利于提高学习性能。此外，为了有效地进行图结构和表示的联合学习，人们提出了各种学习范式。在下面，我们将讨论所有这些有效的动态图构造技术。

2.2.1 图相似度度量技术

基于节点属性包含学习隐式图结构的有用信息的假设，最近有工作将图结构学习问题作为定义在节点嵌入空间的相似度度量学习问题。学习到的相似性度量函数以后可以应用于未见过的节点嵌入集来推断图结构，从而实现归纳式图结构学习。对于部署在图等非欧几里得域中的数据，欧几里得距离并不一定是度量节点相似度的最佳度量指标。各种相似度度量函数已用于 G N N GNN GNN的图结构学习。根据所使用的信息源类型，我们将这些度量函数分为两类：基于节点嵌入的相似度度量和结构感知的相似度度量。

基于节点嵌入的相似度度量：基于节点嵌入的相似度度量函数通过计算嵌入空间中的每对节点之间的相似度来获得加权邻接矩阵。常见的度量函数包括基于注意力的度量函数和基于余弦的度量函数。

基于注意力的相似度度量函数：迄今为止提出的大多数相似度度量函数都是基于注意机制的。为了提高基于点积的注意力机制的学习能力，Chen等人（2020）提出了一种引入可学习参数的修正点积，公式如下：

其中 u ⃗ \vec{u} u 是一个非负权重向量，学习突出节点嵌入的不同维度， ⨀ \bigodot ⨀表示元素级乘法。

同样，Chen等人（2020）通过引入一个可学习的权重矩阵，设计了一个更具表现力的点积版本，公式如下：

W ⃗ \vec{W} W 是一个 d × d d\times d d×d的权重矩阵， R e L U ( x ) = m a x ( 0 , x ) ReLU(x)=max(0, x) ReLU(x)=max(0,x)是一个调整的线性单元（ R e L U ReLU ReLU），用于加强相似度矩阵的稀疏性。

基于余弦的相似度度量函数：Chen等人（2020）将香草余弦相似度扩展为多头加权余弦相似度，从多个角度捕获每对节点的相似度，公式如下：

w p ⃗ \vec{w_p} wp 是与第 p p p个角度相关联的权重向量，与节点嵌入有相同维度。直观地说， S i , j p S_{i, j}^p Si,jp计算第 p p p个角度的节点对的余弦相似度，其中每个角度考虑在嵌入中捕获语义的一部分。除了提高学习能力外，采用多头学习方法还能够稳定学习过程。

结构感知的相似度度量：受结构感知 t r a n s f o r m e r s transformers transformers 的启发，最近提出的方法采用了结构感知的相似度度量函数，除了节点信息，还额外考虑了本质图的现有边信息。例如，Liu等人（2019）提出了一种学习每对节点相似性的结构感知注意机制，公式如下：

v i ⃗ \vec{v_i} vi 表示节点 i i i的嵌入， e i , j ⃗ \vec{e_{i, j}} ei,j 代表连接节点 i i i和 j j j的边的嵌入， h i l ⃗ \vec{h_i^l} hil 是节点 i i i在第 l l l个 G N N GNN GNN层的嵌入， u ⃗ \vec{u} u 和 W ⃗ \vec{W} W 分别是可训练的权重向量和权重矩阵。

同样，Liu等人（2021）引入了一种结构感知的全局注意机制，公式如下：

e i , j ⃗ \vec{e_{i, j}} ei,j 是连接节点 i i i和节点 j j j的边的嵌入， W Q ⃗ \vec{W^Q} WQ ， W K ⃗ \vec{W^K} WK 和 W R ⃗ \vec{W^R} WR 是将节点和边的嵌入映射到潜在嵌入空间的线性变换。

2.2.2 图稀疏化技术

现实场景中的大多数图都是稀疏图。相似度度量函数考虑每一对节点之间的关系，并返回一个全连通图，这不仅计算成本昂贵，而且可能引入不重要的边等噪声。因此，对学习到的图结构明确地加强稀疏性是有益的。除了在相似度度量函数中应用 R e L U ReLU ReLU函数外，还采用了各种图稀疏化技术来增强学习到的图结构的稀疏性。

Chen等人（2020）应用 K N N KNN KNN式稀疏运算，从相似度度量学习函数计算的节点相似度矩阵中得到稀疏邻接矩阵，公式如下：

其中，对于每个节点，只保留 K K K个最近邻（包括其自身）和相关的相似度分数，其余的相似度分数被屏蔽。

Chen等人（2020）通过只考虑每个节点的 ε \varepsilon ε-邻域来实现一个稀疏邻接矩阵，公式如下：

其中， S S S中那些小于非负阈值 ε \varepsilon ε的元素都被屏蔽了（即设置为0）。

除了通过应用某种形式的阈值显式地增强学习到的图的稀疏性外，稀疏性也能以基于学习的方式隐式地执行。Chen等人（2020）引入了以下正则化公式，以增强稀疏图。

其中， ∥ ⋅ ∥ F \lVert\cdot\rVert_F ∥⋅∥F表示一个矩阵的弗罗贝尼乌斯范数。

2.2.3 结合本质图结构和隐式图结构

最近的研究表明，如果在进行动态的图构建时完全放弃本质图结构，可能会损害下游任务性能。这可能是因为本质图通常携带着关于下游任务的最优图结构的丰富的有用信息。因此，他们提出将学习到的隐式图结构与本质图结构相结合，假设学习到的隐式图可能是本质图结构的“转变”（如子结构），是对本质图结构的补充。另一个潜在的好处是结合本质图结构可能有助于加速训练过程，提高训练的稳定性。由于没有关于相似度度量的先验知识，并且可训练参数被随机初始化，通常需要很长时间才能收敛。

许多结合本质图结构和隐式图结构的方法被提出。例如，Li等人（2018）；Chen等人（2020）提出计算本质图结构的归一化图拉普拉斯矩阵 L ( 0 ) L(0) L(0)与隐式图结构的归一化邻接矩阵 f ( A ) f(A) f(A)的线性组合，公式如下：

其中 f : R n × n → R n × n f:\mathbb{R}^{n\times n}\rightarrow \mathbb{R}^{n\times n} f:Rn×n→Rn×n可以是任意归一化操作，如图拉普拉斯操作和行归一化操作。Liu等人（2021）提出了一种针对 G N N GNN GNN的混合消息传递机制，不是显式地融合两个图邻接矩阵，而是融合分别从本质图和学习到的隐式图计算出的两个聚合的节点向量，然后将融合的向量喂给 G R U GRU GRU以更新节点嵌入。

2.2.4 学习范式

大多数现有的动态的图构造方法由两个关键学习模块组成：图结构学习（即相似度度量学习）和图表示学习（即 G N N GNN GNN模块），最终目标是针对某些下游预测任务学习优化的图结构和表示向量。如何优化这两个独立的学习模块，以实现共同的最终目标，是一个重要的问题。这里我们强调三种具有代表性的学习范式。最直接的策略是以端到端的方式为下游（半）监督预测任务联合优化整个学习系统。另一种常见的策略是自适应地学习每个堆叠的 G N N GNN GNN层的输入的图结构，以反映中间图表示向量的变化。这类似于 t r a n s f o r m e r transformer transformer模型在每一层中学习不同的加权全连通图。与上述两种范式不同，Chen等人（2020）提出了一种迭代图学习框架，即基于更好的图表示向量学习更好的图结构，同时以迭代的方式基于更好的图结构学习更好的图表示向量。因此，这种迭代学习范式反复地改进了图的结构和图的表示向量，以获得最优的下游性能。

3. 用于 N L P NLP NLP的图表示学习方法

在上一节中，我们介绍了各种图构造方法，包括静态的图构造和动态的图构造。在本节中，我们将讨论各种能直接用于自然语言处理任务的图表示学习技术。图表示学习的目标是找到一种方法，通过机器学习模型将图结构和属性信息合并到低维嵌入中。为了在数学上形式化这个问题，我们给出了任意一个图的数学符号 G ( V , E , T , R ) \mathcal{G}(\mathcal{V}, \mathcal{E}, \mathcal{T}, \mathcal{R}) G(V,E,T,R)，其中， V \mathcal{V} V是节点集， E \mathcal{E} E是边集， T = { T 1 , T 2 , . . . , T p } \mathcal{T}=\{T_1, T_2, ..., T_p\} T={T1,T2,...,Tp}是节点类型的集合， R = { R 1 , R 2 , . . . , R q } \mathcal{R}=\{R_1, R_2, ..., R_q\} R={R1,R2,...,Rq}是边类型的集合。 ∣ ⋅ ∣ \lvert\cdot\rvert ∣⋅∣表示元素个数。 τ ( ⋅ ) ∈ T \tau(\cdot)\in \mathcal{T} τ(⋅)∈T是节点类型指示函数（例如， τ ( v i ) ∈ T \tau(v_i)\in \mathcal{T} τ(vi)∈T是节点 v i v_i vi的类型）， ϕ ( ⋅ ) ∈ R \phi(\cdot)\in \mathcal{R} ϕ(⋅)∈R是边类型指示函数（例如， ϕ ( e i , j ) ∈ R \phi(e_{i, j})\in \mathcal{R} ϕ(ei,j)∈R是边 e i , j e_{i, j} ei,j的类型）。(由于本人对图神经网络比较熟悉，所以这部分简略概括。)

3.1 用于同构图的 G N N GNN GNN

3.1.1 静态图：将边信息作为连接来处理

G C N GCN GCN， G G N N GGNN GGNN， G A T GAT GAT， G r a p h S a g e GraphSage GraphSage， D C N N DCNN DCNN

3.1.2 动态图

（表格来源于文章Foundations and modeling of dynamic networks using Dynamic Graph Neural Networks: A survey）

3.1.3 图神经网络：双向图嵌入

bidirectional G r a p h S a g e GraphSage GraphSage， bidirectional G G N N GGNN GGNN

3.2 用于多关系图的 G N N GNN GNN

R − G C N R-GCN R−GCN， D i r e c t e d − G C N Directed-GCN Directed−GCN， w e i g h t e d − G C N weighted-GCN weighted−GCN， C o m p − G C N Comp-GCN Comp−GCN， R − G G N N R-GGNN R−GGNN， R − G A T R-GAT R−GAT

门控机制：多关系图神经网络在叠加网络层以利用遥远邻居之间的隐式关联（即不直接连接）时也面临着过度平滑问题。为了解决这一问题，在多关系图神经网络中引入了结合节点输入特征和门聚合特征的门控机制。直观地说，门控机制可以看作是原始信号和学习到的信息之间的权衡。它规定了传播到下一步的更新消息的数量，从而防止模型彻底覆盖过去的信息。在这里，我们以经典的 R − G C N R-GCN R−GCN为例，介绍了门控机制，它实际上可以扩展到任意的变体。

我们将用激活函数 σ ( ⋅ ) \sigma(\cdot) σ(⋅)激活前的表示向量表示为

其中， f f f指聚合函数。最终，节点的最终表示是先前嵌入 h i k h^k_i hik和 G N N GNN GNN输出表示 σ ( u i k ) \sigma(u^k_i) σ(uik)的门控组合：

其中， g i ( k ) \mathbf{g}_i^{(k)} gi(k)是门控向量，并且激活函数 σ ( ⋅ ) \sigma(\cdot) σ(⋅)通常是 t a n h ( ⋅ ) tanh(\cdot) tanh(⋅)函数。门控向量由输入和输出计算得出的公式如下：

其中， σ \sigma σ代表sigmoid激活函数， f ( k ) ( ⋅ ) : R 2 d → R f^{(k)}(\cdot):\mathbb{R}^{2d}\rightarrow\mathbb{R} f(k)(⋅):R2d→R是线性变换。我们重复计算 g i ( k ) g^{(k)}_i gi(k) d d d次得到门控向量 g i ( k ) \mathbf{g}_i^{(k)} gi(k)。

图 T R A N S F O R M E R TRANSFORMER TRANSFORMER: T r a n s f o r m e r Transformer Transformer架构在 N L P NLP NLP领域取得了巨大的成功。受 G A T GAT GAT结合了信息传递和注意力机制的启发，许多文献通过开发具有结构感知能力的自注意机制，将结构化信息整合到 t r a n s f o r m e r transformer transformer中（我们称之为图形转换器）。

作为初始知识，这里我们简要回顾一下自注意力。为了清楚说明，我们省略了多头机制，只展示了自注意力函数。形式上，我们把自注意力的输入表示为 Q = { q 1 , q 2 , . . . , q m } ∈ R m × d q \mathbf{Q}=\{\mathbf{q}_1, \mathbf{q}_2, ..., \mathbf{q}_m\}\in\mathbb{R}^{m\times d^q} Q={q1,q2,...,qm}∈Rm×dq， K = { k 1 , k 2 , . . . , k n } ∈ R n × d k \mathbf{K}=\{\mathbf{k}_1, \mathbf{k}_2, ..., \mathbf{k}_n\}\in\mathbb{R}^{n\times d^k} K={k1,k2,...,kn}∈Rn×dk， V = { v 1 , v 2 , . . . , v n } ∈ R n × d v \mathbf{V}=\{\mathbf{v}_1, \mathbf{v}_2, ..., \mathbf{v}_n\}\in\mathbb{R}^{n\times d^v} V={v1,v2,...,vn}∈Rn×dv。然后输出表示向量 z i z_i zi计算方法为：

其中 W q ∈ R d × d q \mathbf{W}^q\in\mathbb{R}^{d\times d^q} Wq∈Rd×dq， W k ∈ R d × d k \mathbf{W}^k\in\mathbb{R}^{d\times d^k} Wk∈Rd×dk， W v ∈ R d × d v \mathbf{W}^v\in\mathbb{R}^{d\times d^v} Wv∈Rd×dv是训练参数， d d d是模型维度。注意，对于 t r a n s f o r m e r transformer transformer， query, key和value都是指节点的嵌入，即 q i = k i = v i = h i \mathbf{q}_i=\mathbf{k}_i=\mathbf{v}_i=\mathbf{h}_i qi=ki=vi=hi 。

包含结构知识的关系图有各种图 t r a n s f o r m e r transformer transformer，根据自注意函数可分为两类。一类是基于 R − G A T R-GAT R−GAT的方法，它采用类似关系 G A T GAT GAT的特征聚合方式。另一类是保留全连接图，同时将结构感知的关系信息纳入到自注意力函数中。