图机器学习(5)——无监督图学习
- 0. 前言
- 1. 无监督图嵌入
- 2. 矩阵分解
- 2.1 图分解
- 2.2 高阶邻接保留嵌入
- 2.3 带有全局结构信息的图表示
- 3. skip-gram 模型
- 3.1 DeepWalk
- 3.2 Node2Vec
- 3.3 Edge2Vec
- 3.4 Graph2Vec
0. 前言
无监督机器学习是指训练过程中不利用任何目标信息的一类算法。这类算法能够自主发现数据中的聚类结构、潜在模式、异常特征等,适用于没有先验知识或标准答案的各类问题。与其他机器学习算法类似,无监督模型在图表示学习领域得到了广泛应用。它们为解决节点分类、社区发现等下游任务提供了有效工具。
本节将介绍主流的无监督图嵌入方法。这些技术的核心目标是从给定图中自动学习其潜在表示,同时保持图结构的关键特征。具体而言,算法需要在不依赖人工标注的情况下,通过挖掘图数据的内在规律,生成能够反映原始图拓扑特性的低维向量表示。
1. 无监督图嵌入
图是定义在非欧几里得空间中的复杂数学结构。简单来说,这意味着我们往往难以明确界定图中元素的“邻近性”——甚至“邻近”这一概念本身都可能难以定义。以社交网络图为例:两个用户可能彼此相连,但特征却截然不同——一个可能关注时尚与服饰,另一个则可能热衷于体育和电子游戏。这种情况下,是否能认为他们“相近”?
正因为如此,无监督机器学习算法在图分析中得到了广泛应用。无监督机器学习是一类可以在不需要人工标注数据的情况下进行训练的机器学习算法。这类模型通常仅利用邻接矩阵和节点特征中的信息,而无需预先了解下游机器学习任务的具体内容。
最常用的技术方案是学习能够保持图结构的嵌入表示。这类表示通常通过优化设计,使其能够重建节点间的成对相似性(例如邻接矩阵)。这些技术具有一项重要特性:学习到的表示可以编码节点或图之间的潜在关系,从而帮助我们发现隐藏的复杂新模式。
目前已有多种无监督图机器学习算法,这些算法可归纳为三大类:浅层嵌入方法、自编码器以及图神经网络 (Graph Neural Network
, GNN
),如下图所示:
接下来,将介绍浅层嵌入算法背后的主要原理。浅层嵌入方法特指一类仅能学习并返回输入数据嵌入值的算法,在本节中,我们将介绍其中的代表性算法,并通过实例演示其应用场景。
2. 矩阵分解
矩阵分解是一种广泛应用于不同领域的通用分解技术。许多图嵌入算法使用该技术来计算图的节点嵌入。
我们将首先概述矩阵分解的基本原理,随后重点介绍两种使用矩阵分解构建图的节点嵌入的算法,分别为图分解 (Graph Factorization
, GF
) 和高阶邻近保留嵌入 (Higher-Order Proximity Preserved Embedding
, HOPE
)。
设输入数据为矩阵 W∈Rm×nW ∈ ℝ^{m×n}W∈Rm×n,矩阵分解将其分解为 W≈V×HW ≈ V\times HW≈V×H 的形式,其中 V∈Rm×dV ∈ ℝ^{m×d}V∈Rm×d 称为源矩阵,H∈Rd×nH ∈ ℝ^{d×n}H∈Rd×n 称为丰度矩阵,ddd 代表生成嵌入空间的维度。矩阵分解算法通过最小化损失函数来学习 VVV 和 HHH 矩阵,该损失函数可根据具体求解问题进行调整。其通用形式采用 Frobenius
范数计算重构误差,定义为 ‖W−V×H‖F2‖W - V\times H‖_F^2‖W−V×H‖F2。
总体而言,所有基于矩阵分解的无监督嵌入算法都遵循相同原理:将图结构表示的输入矩阵分解为不同成分。各方法的主要区别在于优化过程中采用的损失函数——不同的损失函数能够构建出突显输入图特定性质的嵌入空间。
2.1 图分解
图分解算法 (graph factorization
, GF
) 是最早实现较好计算性能的节点嵌入模型之一。该算法基于前文所述的矩阵分解原理,对给定图的邻接矩阵进行分解。
设待计算节点嵌入的图为 G=(V,E)G=(V,E)G=(V,E),其邻接矩阵为 A∈R∣V∣×∣V∣A∈ℝ^{|V|×|V|}A∈R∣V∣×∣V∣。该矩阵分解问题使用的损失函数 LLL 如下:
L=12∑(i,j)∈E(Ai,j−Yi,:Yj,:T)2+λ2∑i∣∣Yi,:∣∣2L=\frac 12\sum_{(i,j)\in E} (A_{i,j}-Y_{i,:}Y_{j,:}^T)^2+\frac {\lambda }2\sum_i||Y_{i,:}||^2 L=21(i,j)∈E∑(Ai,j−Yi,:Yj,:T)2+2λi∑∣∣Yi,:∣∣2
其中,(i,j)∈E(i,j)∈E(i,j)∈E 表示图 GGG 中的一条边,而 Y∈R∣V∣×dY∈ℝ^{|V|×d}Y∈R∣V∣×d 为包含d维嵌入的矩阵。矩阵的每一行对应一个节点的嵌入表示。此外,嵌入矩阵的正则化项 λ\lambdaλ 用于确保问题即使在缺乏足够数据的情况下仍然具有良好的数值解。
该方法使用的损失函数主要是为了提高 GF
的性能和可扩展性。需要注意的是,该方法生成的解可能是噪声。此外,通过查看其矩阵分解公式,我们可以观察到 GF
执行的是强对称分解。该特性特别适合邻接矩阵对称的无向图,但对于有向图可能会成为潜在的限制。
接下来,使用 Python
和 GEM
库实现 networkx
图的节点嵌入。
(1) 使用 networkx
生成哑铃图 G
作为 GF
算法的输入:
G = nx.barbell_graph(m1=10, m2=4)
(2) 调用 GraphFactorization
类生成二维 (d=2
) 嵌入空间:
gf = GraphFactorization(d=2, data_set=None,max_iter=10000, eta=1*10**-4, regu=1.0)
(3) 通过 gf.learn_embedding(G)
计算输入图的节点嵌入:
gf.learn_embedding(G)
(4) 使用 gf.get_embedding()
方法获取计算得到的嵌入结果:
import matplotlib.pyplot as pltfig, ax = plt.subplots(figsize=(10,10))for x in G.nodes():v = gf.get_embedding()[x]ax.scatter(v[0],v[1], s=1000)ax.annotate(str(x), (v[0],v[1]), fontsize=12)
运行结果如下所示:
从图中可以观察到,属于组 1
和组 3
的节点被映射到空间的同一区域,这些节点与组2的节点形成了明显分隔。这种映射方式虽然能有效区分组1
、组 3
与组 2
,但未能实现组 1
与组 3
之间的清晰分离。
2.2 高阶邻接保留嵌入
高阶邻接保留嵌入 (higher-order proximity preserved embedding
, HOPE
) 是另一种基于矩阵分解原理的图嵌入技术。该方法能够保留高阶邻接信息,并且不强制其嵌入具有任何对称性质。在具体描述方法前,我们需要明确一阶邻接和高阶邻接:
- 一阶邻接 (
first-order proximity
):给定图 G=(V,E)G=(V,E)G=(V,E),其中每条边有一个权重 wijw_{ij}wij,若节点对 (vi,vj)(v_i,v_j)(vi,vj) 之间存在边,则说它们之间的一阶邻接度为边权重 wijw_{ij}wij,否则,两节点之间的一阶邻接度为0
- 二阶和高阶邻接 (
second- and high-order proximity
):通过二阶邻接,我们可以捕捉每对节点之间的二阶关系。对于任意顶点对 (vi,vj)(v_i,v_j)(vi,vj),二阶邻接可视为从 viv_ivi 到 vjv_jvj 的两步转移过程。高阶邻接则对这一概念进行了推广,使得我们可以捕捉到更为全局的结构。因此,高阶邻接可理解为从 viv_ivi 到 vjv_jvj 的 kkk (k≥3k≥3k≥3) 步转移关系
给定了邻接的定义后,我们可以描述 HOPE
方法。形式上,设 G=(V,E)G=(V,E)G=(V,E) 为需要计算嵌入的图,A∈R∣V∣×∣V∣A∈R^{|V|×|V|}A∈R∣V∣×∣V∣ 为其邻接矩阵。该问题使用的损失函数 LLL 定义如下:
L=∣∣S−YS×YtT∣∣F2L=||S-Y_S\times Y_t^T||_F^2 L=∣∣S−YS×YtT∣∣F2
其中,S∈R∣V∣×∣V∣S\in \mathbb R^{|V|\times |V|}S∈R∣V∣×∣V∣ 是从图 GGG 生成的相似度矩阵,YS∈R∣V∣×dY_S\in \mathbb R^{|V|\times d}YS∈R∣V∣×d 和 Yt∈R∣V∣×dY_t\in \mathbb R^{|V|\times d}Yt∈R∣V∣×d 是两个嵌入矩阵,表示 ddd 维嵌入空间。更详细地说,YSY_SYS 代表源嵌入,YtY_tYt 代表目标嵌入。
HOPE
使用这两个矩阵来捕捉有向网络中的非对称邻接关系,有向网络中存在从源节点到目标节点的方向性。最终的嵌入矩阵 YYY 通过将 YSY_SYS 和 YtY_tYt 矩阵按列简单拼接而成。由于此操作,HOPE
生成的最终嵌入空间将具有 2∗d2*d2∗d 个维度。
如前所述,矩阵 SSS 是从原图 GGG 获得的相似度矩阵,其目的是获取高阶邻接信息。SSS 被计算为 S=Mg⋅MlS = M_g \cdot M_lS=Mg⋅Ml,其中 MgM_gMg 和 MlM_lMl 都是矩阵多项式。
HOPE
的作者提出了多种计算 MgM_gMg 和 MlM_lMl 的方法。本节,我们展示一种常见且简便的计算方法——Adamic-Adar
(AA
)。在该方法中,Mg=IM_g = IMg=I (单位矩阵),而 Ml=A⋅D⋅AM_l = A\cdot D\cdot AMl=A⋅D⋅A,其中 DDD 是对角矩阵,其元素 Dij=1/(∑j(Aij+Aji))D_{ij} = 1/(∑_j(A_{ij}+A_{ji}))Dij=1/(∑j(Aij+Aji))。其他计算 MgM_gMg 和 MlM_lMl 的方法还包括 Katz
指数、Rooted PageRank
(RPR
) 和共同邻居 (Common Neighbors
, CN
)。
接下来,使用 Python
和 GEM
库对给定的 networkx
图执行节点嵌入:
import networkx as nx
from gem.embedding.hope import HOPEG = nx.barbell_graph(m1=10, m2=4)hp = HOPE(d=4, beta=0.01)
hp.learn_embedding(G)
上述代码与 GF
方法使用的代码类似,唯一区别在于类初始化时需要指定使用 HOPE
算法。根据 GEM
提供的实现,参数 ddd (表示嵌入空间的维度)将决定最终嵌入矩阵 YYY 的列数——该矩阵由 YSY_SYS 和 YtY_tYt 经列向拼接而成。
因此,YSY_SYS 和 YtY_tYt 的实际列数由参数 ddd 的值通过取整除法确定。代码运行结果如下所示:
在本节中,由于是无向图,源节点与目标节点不存在差异。上图展示了表示 YSY_SYS 的嵌入矩阵前两个维度的分布情况。可以看到,HOPE
生成的嵌入空间在这种情况下能够更好地区分不同的节点。
2.3 带有全局结构信息的图表示
带有全局结构信息的图表示 (GraphRep
),如 HOPE
,能够保留高阶邻接信息的同时,不强制嵌入具有对称性。形式上,假设 G=(V,E)G=(V,E)G=(V,E) 是我们想要计算节点嵌入的图,且 A=R∣V∣×∣V∣A=\mathbb R^{|V|\times |V|}A=R∣V∣×∣V∣ 是它的邻接矩阵。该问题使用的损失函数 LLL 如下:
Lk=‖Xk−YSk×Ytkᵀ‖F2L_k = ‖X^k - Y_S^k\times {Y_t^k}^ᵀ‖_F^2 Lk=‖Xk−YSk×Ytkᵀ‖F2
其中,Xk=R∣V∣×∣V∣X^k=\mathbb R^{|V|\times |V|}Xk=R∣V∣×∣V∣ 是为获取节点间 kkk 阶邻接度而从图 GGG 生成的矩阵,YSkY_S^kYSk 和 Ytk∈R∣V∣×dY_t^k\in R^{|V|\times d}Ytk∈R∣V∣×d 分别是表示源节点和目标节点 kkk 阶邻接度的 ddd 维嵌入矩阵。
XkX^kXk 矩阵通过以下公式计算:
Xk=Πk(D−1A)X^k = \Pi_k(D⁻¹A) Xk=Πk(D−1A)
其中 DDD 为度矩阵(对角矩阵),其元素:
Dij={∑pAipi=j0i≠jD_{ij}=\begin{cases} \sum_pA_{ip} & i=j \\ 0 & i \neq j \end{cases} Dij={∑pAip0i=ji=j
X1=D−1AX^1=D^{-1}AX1=D−1A 表示单步概率转移矩阵,Xij1X_{ij}^1Xij1 即节点 viv_ivi 到 vjv_jvj 的单步转移概率。推广至 kkk 阶时,XijkX_{ij}^kXijk 表示 kkk 步转移概率。
对于每一阶邻接度 kkk,都会拟合一个独立的优化问题。最终所有 kkk 个嵌入矩阵按列拼接,得到完整的源嵌入矩阵。
接下来,利用 Python
的 karateclub
库实现 networkx
图的节点嵌入:
import networkx as nx
from karateclub.node_embedding.neighbourhood.grarep import GraRepG = nx.barbell_graph(m1=10, m2=4)
gr = GraRep(dimensions=2,order=3)
gr.fit(G)
调用 karateclub
库中的 GraRep
类进行初始化,dimension
参数表示嵌入空间的维度,而 order
参数定义节点之间邻接度的最大阶数。最终嵌入矩阵(存储在 embeddings
变量中)的列数为 dimension * order
,因为对于每一个邻接度阶数,都会计算一个嵌入并在最终嵌入矩阵中连接起来。
具体而言,本节中计算了两个维度,因此 embeddings[:,:2]
表示 k=1k=1k=1 的嵌入,embeddings[:,2:4]
表示 k=2k=2k=2 的嵌入,embeddings[:,4:]
表示 k=3k=3k=3 嵌入。代码运行结果如下所示:
从图中可以看到,不同的邻接阶数会生成不同的嵌入分布。由于输入图结构较为简单,当 k=1k=1k=1 时就已经获得了良好分离的嵌入空间。具体而言,属于组 1
和组 3
的节点在所有邻接阶数下都具有相同的嵌入值(在散点图中呈现重叠状态)。
本节我们介绍了几种基于矩阵分解的无监督图嵌入方法。下一节将探讨使用 skip-gram
模型实现无监督图嵌入的技术。
3. skip-gram 模型
skip-gram
在不同的嵌入算法应用广泛,为了更好地理解这些方法,在深入详细描述之前,我们首先进行简要概述。
skip-gram
模型是一个简单的神经网络,具有一个隐藏层,其训练目标是预测当输入词出现时特定词汇共现的概率。神经网络通过使用文本语料库作为参考构建训练数据进行训练,具体流程如下所示:
上图中所示的例子展示了算法如何生成训练数据。首先选择一个目标单词,然后以其为中心构建固定窗口大小 w
的滑动窗口。窗口内的单词称为上下文单词。然后,根据窗口中的单词构建多组(目标单词,上下文单词)对。
当整个语料库的训练数据生成完毕后,skip-gram
模型便开始训练,预测给定目标词出现时各个词汇作为上下文词的概率。在训练过程中,神经网络学习输入单词的紧凑表示。这也就是 skip-gram
模型被称为 Word2Vec
技术的原因。skip-gram
模型的结构如下所示:
神经网络的输入是一个大小为 m
的二元向量,其中每个元素对应待嵌入语言的词典中的一个单词。在训练过程中,当输入 (目标词, 上下文词)
词对时,向量中仅有目标词对应的位置取值为 1
,其余元素均为 0
。隐藏层有 d
个神经元,隐藏层将学习每个单词的嵌入表示,创建一个 d
维的嵌入空间。
输出层为包含 m
个神经元的全连接层(与输入向量维度相同),采用 softmax
激活函数。每个神经元对应词典中的一个单词,其输出值表示该词与输入目标词的关联概率。考虑到 m
值较大时 softmax
计算复杂度较高,实际应用中通常采用分层 softmax
(hierarchical softmax
) 方法。
需要强调的是,skip-gram
模型的最终目标并非完成上述预测任务,而是构建输入单词的 d
维紧凑向量表示。利用隐藏层的权重矩阵,即可方便地提取出词汇的嵌入。另一种常见的 skip-gram
模型的变体是基于上下文预测目标词,即连续袋词模型 (Continuous Bag-of-Words
, CBOW
)。
在理解 skip-gram
模型基本原理后,我们继续介绍基于该模型构建的无监督图嵌入算法。这类算法的核心思想可概括为:首先从输入图中提取节点游走序列,将这些序列视为特殊"语料库"——其中每个节点对应一个"词汇",若两个节点在游走序列中相邻则视为"上下文邻近"。不同算法的核心差异在于游走序列的生成策略,不同的游走生成算法能够突出图的特定局部或全局结构特征。
3.1 DeepWalk
DeepWalk
算法使用 skip-gram
模型生成给定图的节点嵌入。为深入理解该模型,需要首先引入随机游走 (random walk
) 的概念。
设 GGG 为给定图结构,选择顶点 viv_ivi 作为起点。随机选择 viv_ivi 的一个邻居节点并移动至该节点,再从新位置随机选择下一个移动节点,重复此过程 ttt 次。如此产生的 ttt 个顶点随机序列即为长度为 ttt 的随机游走。需特别说明的是,该游走生成算法未施加任何构建约束,因此不能保证节点的局部邻域特征得到完整保留。
利用随机游走的概念,DeepWalk
算法为每个节点生成一个最大长度为 ttt 的随机游走。这些序列将作为 skip-gram
模型的输入数据,使用 skip-gram
生成的嵌入将作为最终的节点嵌入。下图展示了该算法的逐步执行过程:
上图所示算法流程如下:
- 随机游走生成:对于输入图 GGG 中的每个节点,生成 γγγ 条最大长度为 ttt 的随机游走序列。需要注意的是,参数 ttt 仅为长度上限,不同路径允许存在长度差异,并没有约束要求所有路径长度相同
skip-gram
训练:使用上一步中生成的所有随机游走,训练skip-gram
模型。当图作为输入传递给skip-gram
模型时,图可以看作是输入文本语料库,而图中的单个节点可以看作是语料库中的一个单词。随机游走序列可以看作是一个单词序列(句子)。然后,使用随机游走中节点生成的“虚拟”句子训练skip-gram
模型。此步骤使用标准skip-gram
模型参数,窗口大小w
和嵌入大小d
- 嵌入生成:从训练完成的
skip-gram
模型隐藏层中提取节点嵌入表示
接下来,使用 Python
和 karateclub
库对给定的 networkx
图执行节点嵌入:
dw = DeepWalk(dimensions=2)
从 karateclub
库导入 DeepWalk
类进行初始化,dimensions
参数表示嵌入空间的维度。DeepWalk
类接受的其他参数包括:
walk_number
:为每个节点生成的随机游走数walk_length
:生成的随机游走的最大长度window_size
:skip-gram
模型的窗口大小
使用 dw.fit(G)
在图 GGG 上拟合模型,并通过 dw.get_embedding()
提取嵌入:
dw.fit(G)
代码执行结果如下所示:
从上图中可以看到,DeepWalk
能够将区域 1
与区域 3
分离开来。这两个群体受到了属于区域 2
的节点的干扰。实际上,在嵌入空间中,这些节点并没有呈现出清晰的区分。
3.2 Node2Vec
Node2Vec
算法可以看作 DeepWalk
的扩展。DeepWalk
类似,Node2Vec
同样通过生成随机游走序列作为 skip-gram
模型的输入。训练完成后,skip-gram
模型的隐藏层将用于生成图中节点的嵌入表示。两种算法的核心差异在于随机游走序列的生成方式。
具体而言,DeepWalk
采用无偏随机游走,而 Node2Vec
引入了一种新技术,用于在图中生成有偏随机游走。该算法通过结合广度优先搜索 (Breadth- First Search
, BFS
) 和深度优先搜索 (Depth-First Search
, DFS
) 的图探索策略来生成游走序列。这两种策略在游走生成中的组合比例由参数 ppp 和 qqq 调控——参数 ppp 控制随机游走返回上一节点的概率,而参数 qqq 则调控游走探索图中未访问区域的可能性。
得益于这种组合机制,Node2Vec
既能保持图中局部结构的高阶邻接关系,又能保留全局社群结构特征。这种随机游走生成方法克服了 DeepWalk
在保持节点局部邻域特性方面的局限性。
接下来,使用 Python
的 node2vec
库实现 networkx
图的节点嵌入:
node2vec = Node2Vec(G, dimensions=2)
model = node2vec.fit(window=10)
embeddings = model.wv
首先从 node2vec
库中初始化 Node2Vec
类,dimensions
参数表示嵌入空间的维度。使用 node2vec.fit(window=10)
拟合模型。最后,使用 model.wv
获取嵌入向量。
需要注意的是,model.wv
是 Word2VecKeyedVectors
类的对象。为了获取特定节点的嵌入向量,假设 nodeid
是节点的 ID
,我们可以使用训练好的模型:model.wv[str(nodeId)]
。此外,Node2Vec类还接受以下参数:
num_walks
:为每个节点生成的随机游走的数量walk_length
:生成的随机游走的长度p
,q
:随机游走生成算法的 ppp 和 qqq 参数
代码运行结果如下所示:
从上图中可以看出,与 DeepWalk
相比,Node2Vec
能够在嵌入空间实现更好的节点分离效果。具体而言,区域 1
和区域 3
的节点能很好地聚类在空间的两个不同区域,而区域 2
的节点则恰当地分布在两个群体之间,且没有任何重叠。
3.3 Edge2Vec
Edge2Vec
算法生成的是边的嵌入空间而非节点嵌入。该算法本质上是 Node2Vec
生成嵌入的一个简单应用。其主要思想是使用两个相邻节点的节点嵌入进行一些基本的数学运算,以提取它们之间边的嵌入表示。
设 viv_ivi 和 vjv_jvj 为两个相邻节点,f(vi)f(v_i)f(vi) 和 f(vj)f(v_j)f(vj) 分别表示通过 Node2Vec
计算得到的节点嵌入。下表中列出的运算符可用于计算它们之间连边的嵌入表示:
运算符 | 公式 | 类名 |
---|---|---|
Average | f(vi)+f(vj)2\frac {f(v_i)+f(v_j)} 22f(vi)+f(vj) | AverageEmbedder |
Hadamard | f(vi)∗f(vj)f(v_i)*f(v_j)f(vi)∗f(vj) | HadamardEmbedder |
Weighted-L1 | ∣f(vi)−f(vj)∣\lvert f(v_i)-f(v_j)\rvert∣f(vi)−f(vj)∣ | WeightedL1Embedder |
Weighted-L2 | ∣f(vi)−f(vj)∣2\lvert f(v_i)-f(v_j)\rvert ^2∣f(vi)−f(vj)∣2 | WeightedL2Embedder |
接下来,使用 Python
和 Node2Vec
库实现给定 networkx
图的边嵌入:
from node2vec.edges import HadamardEmbedder
embedding = HadamardEmbedder(keyed_vectors=model.wv)
用 keyed_vectors
参数实例化 HadamardEmbedder
类,参数的值是由 Node2Vec
生成的嵌入。为了使用其他技术生成边嵌入,只需更换使用上表所列的其他算子类。嵌入结果如下所示:
3.4 Graph2Vec
前文所述方法都是针对给定图中单个节点或边生成嵌入空间,Graph2Vec
将这一概念进行泛化,能够为整张图生成嵌入表示。
具体来说,给定一组图结构数据,Graph2Vec
算法生成一个嵌入空间,其中每个点代表一个图。该算法使用 Word2Vec skip-gram
模型的变体,即 Document to Vector
(Doc2Vec
) 来生成嵌入表示。下图展示了该模型的简化示意图:
与简单的 Word2Vec
相比,Doc2Vec
模型额外接收一个代表文档的二元数组作为输入。给定"目标"文档和"目标"词语,该模型会基于输入的"目标"词语及其所属文档,预测最可能出现的"上下文"词语。
基于 Doc2Vec
模型,我们可以阐述 Graph2Vec
算法的核心思想:该方法将整张图视为一个文档,而将每个节点生成的自我图 (ego graph) 视为构成该文档的词语。
换句话说,图由子图组成,正如文档由句子组成。根据这一描述,算法可以总结为以下几个步骤:
- 子图生成:为每个节点生成一组带根节点的子图
Doc2Vec
训练:使用上一步骤生成的子图来训练Doc2Vec skip-gram
模型- 嵌入生成:使用训练好的
Doc2Vec
模型的隐藏层中包含的信息来提取每个节点的嵌入
接下来,使用 Python
和 karateclub
库实现一组 networkx
图的图嵌入。
(1) 使用随机参数生成了 20
个 Watts-Strogatz
图:
import random
import matplotlib.pyplot as plt
from karateclub import Graph2Vecn_graphs = 20def generate_radom():n = random.randint(6, 20)k = random.randint(5, n)p = random.uniform(0, 1)return nx.watts_strogatz_graph(n,k,p), [n,k,p]Gs = [generate_radom() for x in range(n_graphs)]
(2) 使用 karateclub
库初始化 Graph2Vec
类,设置嵌入空间维度为 2
:
model = Graph2Vec(dimensions=2, wl_iterations=10)
(3) 通过 model.fit(Gs)
方法在输入数据上训练模型:
model.fit([x[0] for x in Gs])
(4) 使用 model.get_embedding()
提取包含嵌入向量的数组:
embeddings = model.get_embedding()fig, ax = plt.subplots(figsize=(10,10))for i,vec in enumerate(embeddings):ax.scatter(vec[0],vec[1], s=1000)ax.annotate(str(i), (vec[0],vec[1]), fontsize=40)
代码运行结果如下所示:
从上图中可以看到为不同图生成的嵌入。
在本节中,我们介绍了基于矩阵分解和 skip-gram
模型的多种浅层嵌入方法。