携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第20天,link.springer.com/article/10.…
期刊:Knowledge and Information Systems (CCF-B)
年度:2022/01/16
Abstract
图嵌入算法将图嵌入到低维空间中,使得嵌入保留了图的固有属性。虽然图嵌入从根本上与图可视化有关,但以前的工作并没有显式地利用这种联系
我们开发了Force2Vec,它在图形嵌入环境中使用力定向图形布局模型,目标是在机器学习(ML)和可视化任务中出类拔萃
我们通过将Force2Vec的核心计算映射到线性代数并利用现代处理器中可用的多级别并行来使Force2Vec高度并行。由此产生的算法比现有方法快一个数量级(平均比DeepWalk快43倍),并且可以在几个小时内从具有数十亿条边的图中生成嵌入内容
与已有的方法相比,Force2Vec在图形可视化方面有更好的表现,在链接预测、节点分类和聚类等ML任务中的表现与之相当或更好。
1 Introduction
图是社会、信息、化学和生物领域中出现的关系数据的强大模型。现实世界图形的稀疏性、不规则性,特别是高维性,使得对图形的机器学习(ML)比图像和文本数据要困难得多。根据Erdös等人的定义,n个顶点的图可以表示n维特征空间[10]。为了从这样的高维数据(n可以是数十亿或更多)中学习,ML技术将需要大量的训练数据来构建可信的模型。为了解决这个问题,通常将图形嵌入到d维矢量空间中,其中2≤d≤n2≤d≤ n。因此,图嵌入使得用于分类和回归的标准ML技术能够容易地应用于图。
图上的ML方法可以大体上分为转导式方法和归纳式方法,其中所有测试时间查询被限制在训练数据中给出的节点集合,而归纳方法可以在训练期间不可用的新图上定义测试时间查询。归纳算法,如GCN[16]和GraphSAGE[13],使用神经网络对未知数据进行泛化,更适合于动态图。相比之下,DeepWalk[23]、node2vec[12]、Verse[30]和HARP[8]等转导算法直接以无监督的方式学习图的嵌入。传导式算法通常后面紧跟着另一种ML算法,更适用于静态图。本文只考虑转导图的嵌入算法。
尽管最近几年图嵌入在ML研究中受到了更多的关注,但这个问题已经被图画界和可视化界研究了60多年,比如Tutte在1963[31]中讨论的力定向算法。在图形绘制中,顶点被嵌入到2D或3D空间中,因此可以在2D或3D屏幕上可视化图形的“美观”布局。因此,图绘制和节点嵌入都解决了相同的基本问题:找到一个函数,将图中的每个顶点vv映射到dd维向量zv∈Rdz_v∈R^d。主要区别在于d的值:图表绘制使用d=2或3d=2或3,而ML任务使用d≈100d≈100。尽管有这种明确的联系,但最近的图嵌入研究主要是基于诸如word2vec[21]等语言模型的技术。本文在图嵌入和力有向图绘制之间建立了联系,从而将ML和可视化研究线条放在同一把伞下。
力导向布局算法考虑了相邻顶点之间的弹簧式吸引力(例如,基于胡克定律)和不相邻顶点之间的排斥力(例如,基于带电粒子之间的库仑定律)
相比之下,基于随机游动的算法(如node2vec)从顶点v执行随机游动,这些游动中到达的顶点形成v的上下文。然后,这些方法根据v的上下文内外的顶点形成两个顶点子集,并最大化似然函数
在这里,我们通过引力在v的背景下模拟可能性计算,而在v的背景外通过排斥力来模拟可能性计算
我们开发了一种新的基于相似性的优化函数,该函数结合了吸引力和排斥力来学习低维表示
这个名为Force2Vec的表现力导向框架为所有适用于图形嵌入的流行图形绘制模型打开了大门。尽管许多下游ML任务不需要可见的布局,但从图形可视化文献中改编的力定向嵌入的概念通常有助于各种ML任务,如节点分类和链接预测。我们的实验表明,Force2Vec在节点分类、链接预测和可视化任务中的性能与之相当或更好。
图嵌入算法的计算代价很高。包括Force2Vec在内的大多数现有算法通过使用诸如随机梯度下降(SGD)之类的优化方法来最小化损失函数
找到一个有数百万个顶点和数亿条边的图的嵌入可能需要几个小时甚至几天的时间
例如,并行DeepWalk大约需要一天时间才能找到使用48核Intel Skylake处理器的Orkut图(3M个顶点和1.17M条边)的嵌入(参见表7)。这是分析大规模社会和生物网络的一个严重障碍
在本文中,我们开发了一种并行Force2Vec算法,其运行速度比现有方法快一个数量级
这种加速来自两个来源
- (A)Force2Vec的数学公式将梯度计算映射为在计算上类似于稀疏矩阵-密集矩阵乘法的线性代数运算
- (B)我们通过使用多级并行和常规数据访问为低级别核设计了高效的算法。因此,Force2Vec允许我们快速生成高质量的大规模图形嵌入
本文的主要贡献如下:
- 我们在Force2Vec算法中融合了图形嵌入的可视化和ML方法。Force2Vec为各种ML任务实现了最先进的结果,如节点分类和链接预测,并生成高质量的可视化
- Force2Vec为基于线性代数的数学公式的图形嵌入提供了一个富有表现力的框架。该框架还可以实现其他的图形嵌入和可视化算法
- 我们提出了一种高效使用多核处理器和内存的高度并行算法。对于各种大图形,Force2Vec比DeepWalk快22到56倍,比Verse快10.5到45.4倍
- Force2Vec可以生成包含数十亿条边的图的嵌入。对于如此大的图,现有的大多数算法都无法生成嵌入
2 Background and related work
2.1 The general structure of the node embedding problem
设G(V,E)G(V,E)表示有nn个顶点VV和mm个边EE的图
A∈Rn×nA∈R^{n×n}表示图的稀疏邻接矩阵
- 其中Aij=1A_{ij}=1当vi,vj∈E{v_i,v_j}∈E,否则Aij=0A_{ij}=0
节点嵌入问题的目的是学习一个dd维嵌入矩阵Z∈Rn×dZ∈R^{n×d},使得每个顶点vv都可以通过函数f:v→zv∈Rdf:v→z_v∈R^d嵌入到dd维向量空间中
其中zvz_v是vv在RdR^d和d<<nd << n中的嵌入
嵌入函数f也被称为编码器,因为它将顶点编码成RdR^d中的一个向量
设δ:Rd×Rd→Rδ:R^d×R^d→R是计算两个顶点的嵌入向量之间的相似度的函数
在本文中,我们考虑
- δ是一个概率分布函数,δ(zu,zv)的值在0到1之间δ(z_u,z_v)的值在0到1之间
- δG(u,v)δ_G(u,v)是原图中uu和vv之间的某个近似值
- 例如,δG(u,v)δ_G(u,v)可以简单地表示顶点连通性:δG(u,v)=1δ_G(u,v)=1,当(u,v)∈E(u,v)∈E时
图嵌入算法的目标是找到一个嵌入使得δ(zu,zv)≈δG(u,v)δ(z_u,z_v)≈δ_G(u,v)
因此,通过定义损失函数L(δ(zu,zv),δG(u,v))L(δ(z_u,z_v),δ_G(u,v))来测量嵌入的和真实的邻近值之间的差异,然后通过使用SGD最小化该损失函数,可以找到良好的嵌入
嵌入算法的这种一般结构属于编码器-解码器范例,该范例对于捕获大多数无监督图嵌入技术非常有表现力
注意,与GNN等半监督方法不同,非监督嵌入方法需要另一种算法,如Logistic回归来对节点进行分类或预测链接
2.2 Previous work
图嵌入是图挖掘和机器学习文献中研究较多的问题。我们建议读者参考最近的一项调查[6],以全面了解该领域。研究人员之前已经开发了各种编码和解码方案、图接近度量度和损失函数[12,23,29,30]。我们可以根据编码方案和学习策略对它们进行大致分类
我们在表1中简要总结了一些嵌入方法
早期的图挖掘方法是从图中手动提取特征,如度、聚类系数等。这不能完全捕捉到图[2,14]的内在结构。后来,基于矩阵分解的方法[1,7]被引入使用奇异值分解(SVD)或非负矩阵分解(NMF)来分解图(由各种矩阵表示)。缺乏并行化和较高的运行时/内存复杂性限制了它们在更大的图上的应用。
大量基于随机游走的方法被引入到图表示学习中
- DeepWalk[23]在图上执行随机漫游,以对每个顶点的一组路径进行采样。然后,使用word2vec模型[21]来描述该问题以生成节点嵌入
- Line从图中捕获一阶和二阶邻近度的信息,即1跳和2跳邻居[29]
- Node2vec方法基于深度优先搜索(DFS)和广度优先搜索(BFS)遍历对行走进行采样[12]。
- Tsitsulin等人。介绍一种通用的图嵌入方法,称为Verse,它使用各种方法来实例化嵌入[30]。Verse表明,随机游走的平稳分布最终收敛到个性化的PageRank[22]
- HARP[8]为三种最先进的方法开发了多层次算法[32]。尽管HARP提高了一些嵌入方法的速度,但它在存储几个中间图时会消耗大量内存。
一般而言,通用的图嵌入方法应该运行速度快,占用内存少,并生成在不同预测任务中表现良好的高质量嵌入
为了实现这些目标,我们引入了一种称为Force2Vec的无监督并行算法。
3 The Force2Vec algorithm
3.1 A general framework for node embedding
图的良好嵌入在嵌入空间中保留了来自原始图的结构信息
因此,相邻顶点通常具有与非相邻顶点相似的嵌入。设N(u)N(u)表示uu在特定上下文中的“邻居”
这里,N(u)N(u)可以简单地表示通过边与uu相连的顶点或从uu随机游动到达的顶点
使用相似性分布函数δ,我们可以将顶点u的损失函数定义为相对于图中所有其他顶点的负对数似然:
然后我们可以优化公式1,通过使用随机梯度下降(SGD)算法最小化损失函数。为此,L(u)L(u)相对于zuz_u的梯度被计算为
我们在SGD的每次迭代中更新顶点uu的嵌入如下:
其中,η是学习速率或步长
3.2 The force model of the gradient
公式2揭示了这种用于嵌入图的顶点的通用技术的两个基本方面:
- (A)梯度的第一分量(∇fa(u,v)=1δ(zu,zv))(∇f_a(u,v)=frac{1}{δ(z_u,z_v)})与一对相邻顶点之间的相似度成反比
- 以及(B)梯度的第二分量(∇fr(u,w)=11−δ(zu,zw))(∇f_r(u,w)=frac{1}{1−δ(z_u,z_w)})与一对不相邻顶点之间的相似度成正比
表2详细说明了这些关系
对于一对相邻顶点{u,v}{u,v},梯度分量∇fa(u,v)∇f_a(u,v)与它们的相似性δ(zu,zv)δ(z_u,z_v)成反比。相比之下,不相邻的顶点对{u,w}{u,w}的梯度分量∇fr(u,w)∇f_r(u,w)与它们的相似性δ(zu,zw)δ(z_u,z_w)成正比。因此,当∇fa(u,v)∇f_a(u,v)在嵌入空间中距离较远时吸引邻居,而当非邻居在嵌入空间中靠近时∇fr(u,w)∇f_r(u,w)排斥它们
有趣的是,梯度的这两个分量的行为就好像当∇fa(u,v)∇f_a(u,v)彼此远离时吸引邻居,而当非邻居在嵌入空间中靠近时∇fr(u,w)∇f_r(u,w)排斥它们
这些类型的吸引力和排斥力是力有向图布局算法[15,20,24]的核心,这些算法通常用于生成美观的图形可视化效果。我们利用图嵌入和力定向布局方法之间的这种明显的联系,设计了一系列称为Force2Vec的算法,用于图的稳健表示、学习和可视化。
为了将图的嵌入问题重塑为力有向模型,我们主要关注于弹簧-电模型,其中基于顶点的连通性计算两种力,即当两个顶点通过边连接时的吸引力和当两个顶点之间没有连接时的排斥力[11]
在弹簧-电模型的原始设置中
- 相邻的顶点通过胡克定律规定的弹簧式引力相互吸引
- 而不相邻的顶点根据带电粒子之间的库仑定律相互排斥
研究人员通过改变与顶点之间的相似性(或距离)有关的力的大小,开发了该模型的许多变体
在本文中,我们探索了两个算法变体:
- (1)我们考虑了方程1、3中相似性函数δ的几种选择
- 我们将几个广泛使用的力模型直接插入到渐变中
- 在这两种情况下,计算的梯度中的第一项可以被认为是一对相邻顶点之间的吸引力,而第二项可以被认为是一对不相邻顶点之间的排斥力
- 因此,我们用∇fa(u,v)∇f_a(u,v)表示吸引分量,其中uu和vv是相邻的,用∇fr(u,w)∇f_r(u,w)表示排斥分量,其中uu和ww不是相邻的
类似于以前的工作[12,30],我们使用负样本来降低方程1中第二项的成本。
设S(u)S(u)表示被认为是uu的负样本的顶点的子集
然后,我们通篇使用以下方程:
3.3 Variants of the similarity function and force models
我们的总体目标是生成对可视化和其他下游机器学习任务有效的嵌入
为此,我们考虑了两个相似函数和三个力模型
The sigmoid function
我们的第一个相似函数是基于应用于两个嵌入向量[12,23,30]的点积上的Sigmoid函数
用δ(zu,zv)=σ(zu,zv)=11+e−zuzvδ(z_u,z_v)=σ(z_u ,z_v)=frac{1}{1+e^{−z_uz_v}},我们得到以下损失函数:
然后我们计算方程5的梯度详情如下:
其中
- ∇fa(u,v)=(σ(zu,zv)−1)∇f_a(u,v)=(σ(z_u,z_v)−1).zvz_v表示uu和vv之间的引力
- ∇fr(u,w)=σ(zuzw)∇f_r(u,w)=σ(z_u z_w).zwz_w表示uu和ww之间的排斥力。
那么
- 作用在u上的总吸引力是∇fa(u)=∑v∈N(u)∇fa(u,v)∇f_a(u)=∑_{v∈N(u)}∇f_a(u,v)
- 作用在uu上的总排斥力是∇fr(u)=∑w∈S(u)∇fr(u,w)∇f_r(u)=∑_{w∈S(u)}∇f_r(u,w)
Student’s t-distribution
我们的第二个相似性函数是t分布,它在高维数据可视化中被发现是有效的[19,28]
请注意,单自由度t分布近似于标准柯西分布[18]
将δ(zu,zv)=11+t2δ(z_u,z_v)=frac{1}{1+t^2}的值放入公式4中,其中t=‖zu−zv‖t=‖z_u−z_v‖。我们得到了以下信息:
我们可以如下计算损失函数的梯度:
其中,与Sigmoid函数类似
- 第一项表示作用于uu的引力∇fa(u)∇f_a(u)
- 第二项表示作用于uu的排斥力
请注意,式8中的∇fa(u)∇f_a(u)和∇fr(u)∇f_r(u)。表示相应渐变的标量值
为了得到渐变的方向,我们将它们与单位向量相乘,如下所示:
Using force-directed models directly in gradients
除了上述相似函数外,我们还在梯度计算中直接采用了几种流行的力定向模型
表3总结了这些模型以及吸引力和排斥力
这些模型通常用于获得美观的图形布局,ForceAtlas2的作者对这些模型提供了精确的描述[15]
3.4 Optimization
在获得梯度后,我们可以使用公式3使用SGD算法来优化嵌入
一个普通的SGD,它在公式3中的每次更新中只处理一个顶点
有为多线程提供足够的并行度。在小批量SGD中,我们计算小批量顶点的梯度,并并行更新小批量顶点的嵌入
这里,我们只实现了同步版本的mini Batch-SGD,它独立地处理小批中的每个顶点,从而提供确定性的结果,不像SGD的异步并行化[26]。
3.5 The Force2Vec algorithm
算法1提供了基于负采样的Force2Vec算法的一般描述
该算法可以很容易地根据不同的力模型进行调整
- 第3行创建相同大小的小批次(随机且不替换)
- 算法1的每次迭代(第49行)计算一小bb个顶点VbV_b的梯度,然后更新顶点在VbV_b中的嵌入
- 对于一个小批量的VbV_b,我们按照给定的策略识别一组Nb的相邻顶点。例如,NbN_b可以是与VbV_b相邻的顶点,也可以是从VbV_b随机漫游发现的顶点。因此,吸引力是在VbV_b 和 NbN_b之间计算的。在计算排斥力时,我们使用负抽样方法[12,21]。顶点的负样本集由从均匀分布中随机选择的非相邻顶点的子集形成。
- 在算法1的第6行中,我们为当前小批量选择一组负样本SbS_b。SbS_b包含ss个顶点,小批量中的每个顶点都使用这些顶点来计算排斥力。在形成NbN_b和SbS_b之后,我们可以根据我们的力模型计算梯度(第7行),如下一节所讨论的
- 第8行和第9行使用计算出的渐变更新VbV_b中顶点的嵌入
Gradient computation based on force models
算法2描述了我们如何在当前的 minibatchVbV_b中为每个顶点计算渐变
算法2还将NbN_b(VbV_b的邻居)和SbS_b(VbV_b的负样本)作为输入
我们用NbN_b来计算引力,用SbS_b来计算斥力,两者都相对于VbV_b
- 第2行的外部for循环的每次迭代都会计算顶点u∈Vbu in V_b的梯度∇f(u)∇f(u)。由于VbV_b中顶点的渐变是独立计算的,因此多个线程可以并行处理顶点
- 算法2的第4至第5行表示基于相对于NbN_b中的顶点的吸引力的梯度计算。具体地,第5行计算uu与其在NbN_b中的邻居vv之间的∇fa(u,v)∇f_a(u,v)。该梯度计算(∇fa(u,v)∇f_a(u,v))取决于诸如基于等式的力模型
- 类似地,算法2的第6至7行显示了基于相对于SbS_b中的顶点的排斥力的梯度计算。具体地说,第6行计算SbS_b中uu和它的负样本ww之间的∇fr(u,w)∇f_r(u,w)
- 第8行将吸引力和排斥力的梯度分量相加。最后,该函数返回一个存储VbV_b中每个顶点的渐变的b×db×d矩阵
Initialization and hyper parameters
算法1从每个顶点uu的随机嵌入zuz_u、初始学习率ηη、小批量bb的大小和迭代的次数开始。这些参数可以根据经验进行调整,如结果部分所示
Computational complexity
每个梯度分量∇fa(u,v)∇f_a(u,v)和∇fr(u,w)∇f_r(u,w)可以通过对嵌入向量zu、zvz_u、z_v和zwz_w进行运算来计算
因此,计算∇fa(u,v)∇f_a(u,v)和∇fr(u,w)∇f_r(u,w)的复杂度为O(d)O(d)
如果我们只考虑NbN_b中的1跳邻居,则需要为图中的每条边计算∇fa(u,v)∇f_a(u,v),这给出了吸引力计算的O(md)O(md)复杂度
如果使用多跳邻居或随机漫游,这种复杂性可能会改变
每个顶点计算相对于负样本的排斥力,给我们计算排斥力的总成本为O(nsd)O(nsd)
因此,Force2Vec的每次迭代复杂度为O(md+nsd)O(md+nsd)。这里,吸引力和排斥力的相对成本取决于邻里关系的形成和负抽样策略
rForce2Vec: Random walk-based Force2Vec
算法1为Force2Vec提供了一个通用的框架,并且可以很容易地适用于其他力和嵌入模型
例如,我们可以根据DeepWalk和node2vec中使用的随机游走来形成顶点的邻域
为了捕捉这个模型,我们需要从当前的小批量VbV_b中通过随机行走来创建NbN_b,如算法3所示
对于每个顶点u(第4到7行),我们从其后续的k跳邻居中选择k个顶点来计算吸引力。在使用算法3创建NbN_b之后,我们可以将其传递给算法1,而无需更改梯度计算
我们将这种方法称为rForce2Vec,通过从多跳邻居中提取信息,该方法可能在异类网络中执行得更好
引力的计算复杂度为O(nkd)O(nkd)
RForce2Vec中计算排斥力的复杂性保持不变
3.6 Parallel Force2Vec
A linear algebra model
基于吸引力和排斥力的梯度计算(即算法2)主导了Force2Vec的运行时。为了有效地优化梯度计算,我们将其建模为一系列线性代数运算。设VbV_b为当前小批量中bb个顶点的集合,Zb∈Rb×dZ_b∈R^{b×d}为VbV_b对应的嵌入矩阵切片。还假设Ab∈Rb×nA_b∈R^{b×n}表示存储对应于VbV_b的边的邻接矩阵的切片。图1显示了此设置的一个示例,其中小型批处理由前四个顶点组成。
根据公式计算吸力。例如,在图1中,邻接矩阵第0行的顶点V0在位置1、3和7有三个非零元素,这意味着Nb(V0)={v1,v3,v7}N_b(V_0)={v_1,v_3,v_7}。因此,我们访问z1、z3和z7z_1、z_3和z_7(图1中的红色箭头所示),
根据力方程执行一些计算(例如,公式6),然后求和以计算顶点V0V_0的梯度∇fa(V0)∇f_a(V_0)。该计算遵循稀疏密集矩阵乘法(SpMM)的模式。类似地,基于公式的排斥力计算也是如此。6访问不相邻顶点的子集的嵌入(图1中的v2v_2和v5v_5)。这种排斥力计算也可以映射到一般的SPMM操作。
虽然图1提供了在梯度计算中使用SpMM的高级概念,但由于各种力模型的复杂性,我们不能直接使用现成的SpMM实现。例如,图2显示了我们如何根据公式6实际计算∇fa(V0)∇f_a(V_0)。首先计算z0z_0与z1、z3、z7z_1、z_3、z_7之间的点积。这些点积产生由a1、a2和a7a_1、a_2和a_7表示的标量值,它们通过生成s1、s2和s7s_1、s_2和s_7的Sigmoid函数传递。我们通过在向量的每个通道中复制这些标量值来传播这些标量值以形成向量,这些向量被逐个元素地乘以其对应的嵌入向量。将得到的矢量相加,以最终输出∇fa(V0)∇f_a(V_0)。虽然这种计算在概念上类似于SpMM,但是使用Sigmoid使得使用标准库变得更加困难。该映射允许我们最佳地并行化梯度计算,如下所述。
Thread-level parallelization
小批量中的所有顶点都是独立的,并并行计算渐变。例如,不同的线程可以并行地计算图1中四个顶点(对应于zbz_b的顶点)的梯度。因此,每个线程可以按照图2所示的流程顺序计算∇fa(V)∇f_a(V)和∇fr(V)∇f_r(V)。当小批量中的顶点具有相似数量的邻居时,我们使用静态调度,其中每个线程处理来自小批量的相同数量的顶点。然而,如果顶点的阶数非常高(通常在无标度网络中可以看到),则在高阶数的顶点上的计算可能会成为瓶颈。为了解决这个问题,我们计算小批的度分布,并根据线程的数量对小批进行划分,使得每个线程处理的邻居数量几乎相等。后一种方法为无标度图带来了更好的负载平衡。
SIMD vectorization
虽然每个线程在核中计算∇fa(V)∇f_a(V)和∇fr(V)∇f_r(V),但是通过采用每个核中可用的单指令多数据(SIMD)并行性,可以进一步优化这些计算。为此,我们使用硬件内部结构实现了图2中的计算。我们的库包括一个代码生成器,它为不同的硬件架构生成内部代码(类似于[33])。在我们的实现中,我们使用了广泛的寄存器块来执行SIMD寄存器上的顶点的所有中间计算,从而减少了对输出的写访问。请注意,我们需要使用任何硬件体系结构的SIMD寄存器的全部容量来有效地实现这一技术,而通用编译器通常不太擅长这种级别的自动向量化。
4 Experiments
4.1 Experiment setup
4.2 Runtime and scalability experiments
4.3 Visualization quality
4.4 The effectiveness of embeddings in ML tasks
….
5 Conclusions
提出了一种基于力有向图布局模型的并行图嵌入算法Force2Vec
Force2Vec通过以下方式推进了图形嵌入领域
- (A)通过将经过验证的可视化模型合并到ML优化中,Force2Vec提供了高质量的图形可视化;
- (B)通过使用多级并行性,Force2Vec的运行速度至少比以前的图形嵌入算法快了一个数量级
- (C)Force2Vec在节点分类、链接预测和(D)Force2Vec提供了一个通用的并行框架,可以很容易地与各种力定向和基于随机游走的方法一起使用
因此,Force2Vec使各种科学领域的大规模图形学习和可视化成为可能
Force2Vec通过整合几个相似性函数和力模型,在ML和可视化任务中都表现出色
我们的广泛评估表明,Force2Vec的不同变体在不同的机器学习和可视化任务中表现良好
根据我们的观察,表12总结了常见任务的推荐模型
例如,t分布的Force2Vec通常对多类别分类设置中的节点进行分类时执行得最好。与t分布相结合的Force2Vec也可以很好地执行集群任务
相比之下,具有Sigmoid相似性函数的Force2Vec对于多标签节点分类任务执行得最好。Force2Vec与Sigmoid相结合,在链路预测方面也表现得更好
为了生成更好的可视化布局,使用LinLog模型的Force2Vec通常比其他模型执行得更好。然而,如果可视化图形是唯一的目标,则可以只使用传统的图形布局算法,例如BatchLayout[24],因为后者有望为图形可视化生成更好的布局
读后总结
2022/07/29 第一次阅读
这篇文章是另一篇文章(还没有读)的拓展
因为没有读之前那一篇,所以有点模糊
总的来说,就是依据一个损失函数
使用SGD进行优化
在这个过程中发现,梯度下降时候,节点与其邻域节点可以类比于力模型中的引力,而与其他节点则可以类比于排斥力
再利用不同的力模型进行替换,得到最终的嵌入
相似函数也可以修改为其他的,这里有两种,一个是sigmod,一个是t分布
结语
文章仅作为个人学习笔记记录,记录从0到1的一个过程
希望对您有一点点帮助,如有错误欢迎小伙伴指正