携手创作，共同生长！这是我参加「日新方案 8 月更文应战」的第9天，点击查看活动详情

前言

Hello！ 非常感谢您阅读海轰的文章，假使文中有过错的当地，欢迎您指出～ 毛遂自荐 ଘ(੭ᵕ)੭ 昵称：海轰 标签：程序猿｜C++选手｜学生 简介：因C语言结识编程，随后转入核算机专业，取得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研。 学习经历：扎实根底 + 多做笔记 + 多敲代码 + 多考虑 + 学好英语！ 唯有尽力

知其然 知其所以然！

本文仅记载自己感兴趣的内容

简介

原文链接：dl.acm.org/doi/abs/10.…

会议：ACM Transactions on Knowledge Discovery from Data （CCF B类）

年度：2021/05/19

Abstract

近年来，图标明学习办法引起了越来越多的重视

这些办法专心于学习图中节点的数值标明

学习这些标明是完结图发掘、可视化和哈希等使命的强壮工具

它们特别令人感兴趣，因为它们促进了在图表上直接运用规范机器学习模型

图标明学习办法能够分为两大类:

• 保存节点衔接信息的办法
• 保存节点结构信息的办法

根据衔接性的办法专心于对节点之间的联系进行编码，衔接的节点在产生的潜在空间中愈加严密

而保存结构的办法产生了一个潜在空间，在这个空间中，服务于网络中类似结构功用的节点在图中被编码为互相挨近、互相独立、乃至互相挨近的节点

虽然有很多的作业重视于坚持节点连通性，但只需少量作业重视于坚持节点的结构

正确编码节点的结构信息是许多实践运用程序的根底，因为事实证明，能够运用这些信息成功地处理许多根据衔接的办法一般失败的使命

一个典型的比方是节点分类使命，即为节点分配或猜测特定的标签

现在结构标明办法的局限性在于其可扩展性、标明意义以及不能保证结构特性的办法化证明

咱们提出了一种新的图标明学习办法，称为图节点结构迭代标明学习办法(SIR-GN)

在这项作业中，咱们提出了两种变体(SIR-GN: GMM和SIR-GN: K-Means)，并展现了咱们的最佳变体SIR-GN: K-Means:

• (1)理论上保证了图结构类似性的保存
• (2)供给了其标明的清晰意义，并经过专门规划的归因进程来解说它
• (3)可弹性和快速核算

此外，从咱们的试验中，咱们标明SIR-GN: K-Means一般比文献中现有的结构图标明学习办法更好，或许在最坏状况下能够与之媲美

一起，咱们经过试验证明了与其他现有办法比较，它具有更好的可扩展性和核算功用

1 INTRODUCTION

图或网络是一种包括一组实体以及这些实体之间联系的数据结构

网络中的实体称为极点或节点，节点之间的联系称为边

图表具有很高的相关性，因为它们在许多研讨范畴中被很多用于标明联系和进程

它们能够代表分子、神经系统、社会网络、核算机网络等等

多年来，现已有很多的作业提出了剖析和运用图表办法的数据的办法，以处理许多不同的使命

这些使命的一些示例是节点分类、链路猜测、节点聚类等。

---

这些使命传统上是经过通用机器学习(ML)技能来处理的

但是，这些技能不能直接运用于图形办法的数据，有必要先将图形正确地转换为某品种型的数字标明

要想有用，标明有必要包括相关信息

一般，图发掘技能能够用来提取一组有意义的特征来描绘这个信息[7]，或许节点类似性衡量能够手艺规划作为ML模型[35][41]的特征

但是，这些进程是劳动密集型的，需求专业的范畴相关常识，而且产生的特性一般也是范畴相关的，这在不同的使命[17]之间转化为较差的泛化

---

为了战胜这些缺点，近年来无监督标明学习技能的研讨有所增加

标明学习技能在核算机视觉和自然语言处理等其他运用范畴也取得了很大的成果

在图论范畴，图标明学习，也被称为网络嵌入，旨在生成一个低维的数值向量标明在一个图的节点

能够说，有两种首要的图标明学习办法

• 根据衔接的办法
• 根据结构的办法

虽然有一些著作旨在完结两个使命[17][55]的标明，但最近的绝大多数著作都专心于榜首种[37][42]，生成包括整个网络中节点衔接信息的标明

咱们提出的办法首要针对第二品种型

结构标明学习办法旨在创立编码节点结构人物信息的标明

直观地说，网络上的节点能够完结一个或多个决议其在其间人物的功用

例如，在交际网络中，个人能够履行组管理员的功用，这种功用或结构人物能够从其网络结构揣度出来

其他常见的比方是像万维网这样的网页网络中的中心和威望

在网络拓扑中，一些示例人物能够是星形中心或星形边缘的近团，衔接图中不同区域的桥节点，等等

---

结构标明法与根据衔接的标明法的首要区别在于，根据衔接的标明法编码了根据节点衔接的节点挨近度概念

换句话说，网络内部的节点越近(它们之间的途径越短)，生成的标明就越类似

另一方面，结构表征学习办法疏忽了附近性的概念，这意味着结构类似的节点独立于它们在网络内的相对方位被以为是类似的，而专心于网络内的节点功用

---

图1显现了衔接性(一阶挨近)和结构标明(结构人物挨近)之间的简略比较

节点用色彩编码来标明类似性，即色彩类似的节点被以为互相类似

能够看出，一阶挨近编码的节点，只需有一条途径衔接它们，它们之间都是类似的

两个节点之间的途径越短，它们就越类似

例如，节点A和节点B与各自的街坊C和D最类似，但互相彻底不同，虽然它们在网络中的结构功用彻底相同

另一方面，当选用结构人物挨近时，两个节点类似不需求衔接，只需它们在网络中具有类似的功用就能够以为是类似的

例如，节点Z和Y在结构上是等价的，两个节点别离作为两个其他节点(X,W和V, U)之间的桥梁

一起，节点X、W、V、U在结构上也是等价的，因为它们在网络中的作用是相同的

这个比方展现了正确编码节点结构信息的办法关于许多实践运用程序来说是多么的重要

---

在著作中，有关于生成结构和衔接表征的著作

• 关于根据连通性的标明，Node2vec[17]提出了一种有偏随机游走办法来优化邻域坚持方针函数。在这种标明办法中，互相挨近的节点具有更类似的标明
• 在[39]中，它们显现了根据衔接的办法的局限性，特别是关于节点分类的使命，即将一个标签或特点分配给节点，出于这个动机，供给了保存结构特点的办法，因为它们答应ML模型泛化对节点分类重要的结构办法
• Struc2vec[39]提出了一品种似的办法，但抛弃了有偏差的随机漫步办法，倾向于首要生成一个加权多层上下文图，对输入图中出现的一切层次的结构类似性进行编码。然后，选用规范的随机游走法优化保邻域方针函数。这种办法成功地生成了结构标明法，但是，生成多层上下文图是一个杂乱的进程，当运用于更大的输入网络时，核算和空间成本都很高
• GraphWave[13]提出了一种彻底不同的办法，它运用光谱图分散办法。这种办法供给了很好的成果，但在概念上依然很杂乱(没有清晰的标明意义)，试验标明，这种根据矩阵分解的办法的核算成本很高(它在节点数量上有渐进的二次元时间杂乱度因子)，因而很容易运用于更大的图

此外，上面说到的任何一种办法都没有正式证明标明保存图的结构特点

最重要的是，上述一切办法都缺少可解说性

这是标明学习办法的一个常见缺陷，即生成的标明在其数值背面缺少任何或许的推理

---

为了战胜这些缺点，在本文中，咱们提出了一种快速的图节点结构迭代标明学习办法(SIR-GN)

该办法

• (i)将节点分组到$n$个不同的集群中
• (ii)运用集群为每个节点$v$生成一个向量，用于每个条目(与每个集群相关)衡量$v$归于该集群的或许性
• (ii)经过对一切相邻节点的似然向量进行汇总，得到每个节点的向量标明

这种新的表征学习办法在速度、猜测成果和可解说性方面优于文献中的结构学习表征办法

---

更详细地说，本文供给了以下奉献:

• 咱们提出了一种新的图节点结构标明，称为SIR-GN，它保存了图结构的类似性，在其生成的标明中供给了清晰的意义，是可弹性的，且核算速度快
• 咱们从理论上证明了咱们的办法在一个隐空间中编码节点结构信息，在节点结构之间保存一个衡量间隔的概念。咱们证明了具有相同结构的节点的向量标明是相同的，而且两个节点向量标明之间的曼哈顿间隔总是受其街坊中不匹配节点的数量的束缚
• 咱们供给了SIR-GN的两种改变的试验成果，即咱们的初始改变SIR-GN: GMM和咱们的首要改善改变SIR-GN: K-Means
• 咱们证明了经历和理论上的核算功率，咱们的办法比较，最先进的办法。SIR-GN: K-Means在核算杂乱度上与图的巨细呈线性联系。此外，它为并行化供给了一个很好的机会
• 咱们供给了一个专门为SIR-GN规划的归因进程，增强了咱们办法的可解说性。考虑到节点标明分类使命，该进程能够为每个节点划出担任特定分类成果的子图
• 咱们供给了一个根据中心性衡量的框架，以实证查验咱们的标明学习办法在保存图的结构特点方面的才能
• 咱们的办法在一切试验中都取得了较好的成果。咱们对产生的矢量标明进行了定性剖析，并展现了怎么用SIR-GN很好地保存了结构性质。在运用几种不同图的一切定量试验中，咱们的办法总是得到更好的成果，或许在少量状况下，在中心性衡量猜测、节点分类和边缘去除的鲁棒性方面具有可比性

2 RELATED WORK

鉴于高档图剖析办法在许多实践运用中的巨大价值，开发有用和高效的图的无监督标明学习技能现已引起了很大的兴趣

这些标明学习办法关于需求运用图办法数据的ML运用程序来说是必不行少的，因为ML技能能够直接运用于产生的标明

表征学习技能现已在许多研讨范畴取得了巨大的成功。其间一个范畴便是NLP

能够说，在自然语言处理范畴最闻名的表征学习办法是Skip-Gram模型，也便是Word2Vec[29][30]

该办法运用词序列(即句子)生成词标明，并运用它们优化邻域坚持似然方针

然后，它学习一个语言模型，该模型除了其他特征外，还将语义类似的单词放在生成的潜在空间中

---

DeepWalk[37]遵循了这个闻名的模型，并将其从单词序列推行到图形

为了完结这种泛化，DeepWalk经过对输入图中的节点序列运用截短的随机漫步来模拟句子，然后对这些序列运用Skip-Gram模型来生成终究的节点标明 这种抽样进程，直观上类似于图的深度优先遍历，结合Skip-Gram模型的邻域坚持方针，产生了一种根据衔接的标明学习办法，其间节点以直接、(一阶挨近)或间接(高阶挨近)的办法同享类似的街坊，坐落更靠近产生的潜在空间。

LINE[42]主张将图的探究从深度优先采样(DFS)或遍历改为宽度优先采样(BFS)，供给一个潜在空间，其间同享边的节点(一阶挨近)坐落更近的潜在空间

为了供给更灵敏的模型，Node2vec[17]提出了一个有偏随机游走进程，它能够在DFS战略和BFS战略之间进行插值

用户运用两个超参数在两种战略中进行挑选。它对生成的标明办法中的低阶和高阶信息进行编码。node2vec的作者以为BFS战略供给了与结构人物类似性密切对应的标明 在实践中，BFS战略要求节点衔接，而关于真正的结构等效，根本不该该有任何衔接要求 因为这束缚了仅在衔接节点之间进行任何或许的结构编码，另一个根本束缚是，如果结构类似的节点的间隔(跳数)大于Skip-Gram窗口，它们将永远不会同享相同的上下文

在[17]中，DeepWalk和LINE的功用比node2vec更差，因而它们不包括在咱们的试验部分

---

为了用结构等价信息编码标明

Struc2vec[39]提出运用Deepwalk的DFS战略，但将其运用于多层上下文图，对输入图的一切节点对之间的结构类似性联系进行编码

为了生成多层上下文图struc2vec，首要界说了一个衡量不同网络规范上节点类似度的层次结构，然后运用这个层次结构结构了一个加权多层图 它有三个首要特点:(1)图的每一层对应层次结构中的一个层次;(2)原始输入网络的一切节点都存在于每一层;(3)每层内部每个节点对之间的边权值与节点对之间的结构类似度成反比。在生成的图上运用Deepwalk模型能够取得很好的成果 多层图中互相挨近的节点标明(具有较高的结构人物类似度)在产生的潜在空间中以挨近的办法成功编码，但网络生成杂乱，且多层上下文网络的规模在运用于更大的输入图时或许会变得难以承受

GraphWave[13]与前面的办法不同，它不运用Skip-gram和随机游走来学习节点标明

GraphWave提出经过运用小波分散办法来学习节点结构人物 这个想法背面的直觉是，小波从具有类似结构作用的节点开端，将以类似的办法在整个网络中分散，创立一个能够丈量和比较的类似分散办法 作者首要将谱图小波运用于每个节点，并将这些提取的小波作为图上的概率散布 为了将这些信息转化为数值向量标明，作者经过运用特征经历函数嵌入小波散布 虽然这种办法供给了优秀的成果，恰当地保存了节点的结构人物附近性，但与其他结构标明学习办法(如Struc2vec)比较，谱图小波进程真的很慢

还有其他的作业，没有直接的标明学习技能，处理结构节点身份

RolX[21]是一个早期的比方

这种无监督办法提取网络中存在的结构节点人物 RolX经过首要提取各种节点特征来完结这一使命 这个联合特征空间稍后被用来核算更适合的基向量，其间每个节点在识别的人物(基)上被分配一个二进制散布 这答应每个节点归于多个人物 RolX的体现比struc2vec[39]更差，因而它不包括在咱们的试验部分

---

在咱们提出的作业中，咱们迭代地运用聚类来生成一个结构标明

现已有一些作业将聚类技能运用于其他高档图剖析，但它们与本文的意图没有直接联系

在完整性方面，例如，[50]运用光谱聚类在图中寻觅社区，比[31]的作业有所改善，他们标明，运用光谱聚类提高了社区检测使命的功用和功率

还有其他不直接编码一般网络结构的标明学习办法，它们直接存储两个节点之间的成对类似性

• 在[45]中，作者运用单层神经网络(NN)来学习编码特定网络衡量的标明。虽然根据任何挑选的类似度衡量生成标明供给了很大的灵敏性，并或许在特定使命中供给更好的成果，但为特定使命挑选正确的类似度需求很强的范畴专业常识。这是一种劳动密集型的作业，需求专业的范畴相关常识，而且所产生的特性一般也是范畴相关的，这就导致了跨不同使命的概括才能低下。此外，这种技能在节点数量上总是要求二次杂乱度。为了避免这种状况，作者提出了一种不需求核算一切类似对的近似办法，他们只需求其间的一部分。但是，相关的类似性衡量，如SimRank[22]和其他运用循环进程，这意味着关于核算两个节点之间的一个类似性，一切其他的都是需求的。

另一个近年来遭到越来越多重视的相关范畴是常识图的标明学习范畴

常识图包括实体的信息以及实体之间不同类型的联系 这些不同的联系使得常识图在标明结构化数据时非常有用，但一起又使[49]难以操作它们 已有许多研讨致力于简化操作，一起坚持常识图的固有结构

在[32]中，作者提出了两种闻名的常识图标明学习办法的组合，即潜在特征模型和图特征模型

前者运用实体的潜在特征来解说联系特征，并从数据中揣度联系特征

后者从可调查的图形办法中提取特征

作者论证并实证证明他们的新组合模型(TKGE)在常识图完结和三重分类使命上比其他先进的办法供给了显着的功用改善

• 在[56]中，作者将留意力会集在研讨较少的根据标明的常识图实体对齐问题上。作者提出了一个统一实体的多个视图的框架，以学习专门为这项使命编码的标明。关于这项使命，他们运用实体名称、联系和特点，并提出几种组合战略。此外，它们还供给了关于交叉kg(常识图)推理办法的详细信息，这些办法能够增强对齐才能。作者经过经历证明，他们提出的办法在根据标明的实体对齐使命中显着优于最先进的办法
• TransW[28]是由TransE[3]发动的最新的根据翻译的办法宗族。TransW提出了一种运用词标明的根据翻译的办法。这很有趣，因为运用作业标明扩展了曾经的办法，为它们供给了功用用于处理新的(曾经看不见的)实体和联系。关于常识图标明学习办法和或许运用的更深化的观点，请参阅[49]

---

近年来，人工神经网络被广泛运用于学习标明的各个范畴和运用范畴。在这项作业的范围内，图神经网络(gnn)是特别感兴趣的，因为它们是专门规划来处理图形办法的数据

在GNN宗族中，有各式各样的办法

• GraphSAGE[20]便是一个比方。GraphSAGE是一个根据卷积的GNN，也称为图卷积网络(GCNs)[23]。与众所周知的卷积神经网络中运用的卷积类似，GCNs经过运用图的结构(一般是节点的榜首级邻域)来履行卷积操作。更详细地说，GCNs对节点及其街坊的标明进行加权平均，这种办法有用地履行了信号聚合进程。这个进程生成新的标明，这些标明对来自图内部节点的本地上下文的信息进行编码。在文章中，作者提出了几种或许的聚合函数和一种节点抽样战略。这种战略经过为每个节点采样固定数量的街坊来提高核算功用。这削减了核算量，但一起，不行逆地改变了图结构。咱们相信，以这种办法修正图会降低用于根据结构的问题的标明的功用。正如咱们将在这项作业的试验部分看到的，对节点的邻域进行最细微的修正，就会对需求结构信息的使命的办法的功用产生负面影响。

gnn的其他办法是根据主动编码器的

• 在ARGA[34]中，作者提出了一种根据自编码器的GNN办法，并运用生成对抗网络作为正则化器。该算法分为两部分:主动编码器部分和对抗性部分。该自编码器选用根据gcn的编码器，以最大限度地削减图连通性的重构误差。该体系结构的对抗性部分运用对抗性练习方案来练习自编码器遵循预先挑选的先验散布(高斯散布)。这产生了一个更连贯和接连的潜在空间。为了生成终究的标明，对整个模型进行联合优化。

在GNN宗族之外还有其他根据nn的办法

• 在DRNE[46]中，作者提出了一个根据神经网络的办法的少量实例，专门针对结构表征学习范畴。在DRNE中，作者将节点邻域转换成有序的序列，并经过运用Long -term Memory层进行聚合。与theCBOW[29]办法类似，DRNE架构被练习来经过运用节点街坊的标明来重建节点的标明。为了避免退化解，作者提出在方针函数中加入弱导向正则化器。这是经过尝试一起重构每个节点的度来完结的。与GraphSAGE类似，DRNE运用节点采样战略。这种抽样修正了原始图结构，对结构问题的办法功用产生了负面影响

---

前面说到的一切根据nn的办法都归于无监督办法宗族

虽然它们不在本作业的范围内，但咱们以为有必要简要地说到一些最闻名的监督办法。这些办法包括:GCN[23]、GAT[47]和GIN[52]。关于gnn和相关办法的更深化的了解，请参阅[59]和[51]

现已有一些著作运用迭代来学习节点标明

• Chen等人[6]提出了规范监督分类使命的迭代进程。与其他分类使命不同的是，这种办法在实例之间创立一个挨近图，并为每个实例聚合(经过运用卷积层)街坊实例的隐藏特征，以便更好地对特定实例进行分类

这种办法在每次迭代时

• (1)在实例之间增加新的类似边(根据实例潜在特征的类似性)
• (2)在邻接矩阵中增加边
• (3)用新的邻接矩阵细化分类练习

在[19,57]中，作者运用迭代进程学习常识图的实体标明，并将这种标明用于链接猜测

与这些办法比较，咱们运用迭代进程在无监督的办法学习结构节点标明

---

终究，咱们还提出了一种办法来解说所生成的标明的意义，并解说运用这些标明练习ML模型的成果

近年来，各式各样的著作都企图抵达相同的方针

• GNNExplainer[53]是一种特定于GNN的解说办法，所供给的解说是一个子图，经过练习GNN的猜测最大化互信息
• 在DisenGCN[27]中，作者提出了一种包括一种新的邻域路由机制的GNN架构，该机制能够动态识别或许导致两个节点之间产生边的潜在要素。该办法生成了别离的节点标明，别离了节点联系背面改变的解说要素，为潜在的更可解说的标明

3 BACKGROUND

在本节中，咱们首要介绍一组将在整个作业中运用的重要符号和界说

然后，咱们提出了拓扑测度，咱们将在后边运用它来证明SIR-GN编码结构信息的有用性

表1包括一组标明法

Definition 3.1. Graph

设$G=(V,E)$是一个未标记的无向图或网络，其间

• $v$标明极点或节点的调集
• $E\subseteq (VV)$标明衔接$G$中节点的边的调集
• $|V|$和$|E|$别离标明图中包括的节点数和边数
• 恣意节点$u$的邻域由$nbr(u)=\{v|(u,v)\in Eor(v,u)\in E\}$给出
• $|nbr(u)|$标明该邻域的巨细或节点的度

Definition 3.2. Graph diameter

图的直径一般被界说为图中恣意两个节点之间的“最长最短途径”

更正式地说，直径是恣意两个图节点$(u,v)$之间的长度max(u,v∈v，∃pathfromutov)d(u,v)max_{(u,v∈v，∃path from u to v)}d (u,v)max(u,v∈v，∃pathfromutov)​d(u,v)，其间

• $d(u,v)$是节点$u$和$v$之间的间隔

Definition 3.3. K-order Proximity

标明学习办法需求一个节点之间挨近的概念来进行学习

根据运用的附近性概念，这些办法能够被划分为两类

• 根据衔接的办法(k阶附近性)
• 根据结构的办法(结构人物附近性)

k阶挨近探究[55]节点对之间的k阶联系

首要运用的联系是

• 一阶联系，反映节点之间的直接街坊联系
• 二阶挨近联系，由两个节点同享的共同街坊的数量决议
• 高阶挨近联系，捕捉更全局的联系

Definition 3.4. Structural Role Proximity

“结构人物挨近度”反映了在网络拓扑中具有类似人物或功用的节点之间的类似性

这些函数的一些示例或许是星形的中心、衔接双节点集群的节点等等

与k阶附近性比较，结构人物附近性不需求网络中一对节点互相衔接，乃至不需求它们坐落互相相邻的方位，就能够使它们类似

只需它们具有相同的结构特点，它们在网络中的方位是独立的，它们就会类似

---

接下来，咱们将介绍在本作业的试验部分中运用的一组拓扑测度

Betweenness Centrality

中间中心性(Betweenness Centrality)[15]被描绘为一个节点在两个其他节点之间的最短途径上充任桥梁的次数

办法上，节点$v$的BC界说为

其间

• st(v)_{st}(v)st​(v)为从极点$s$到极点$t$的最短途径数经过极点$v$的途径数
• st_{st}st​为从$s$到$t$的最短途径总数

Degree centrality

一个节点的度中心性(Degree centrality)[16]界说为它所衔接的节点占图中节点总数的比例

正式界说为

Eigenvector Centrality

由图邻接矩阵的主导特征向量给出特征向量中心性(Eigenvector Centrality)[2]

设A=(av,t)A = (a_{v,t})A=(av,t​)是邻接矩阵

• 其间av,t=1a_{v,t} = 1av,t​=1，如果极点$v$链接到极点$t$
• 否则, av,t=0a_{v,t} = 0av,t​=0
• 为常数

界说节点$v$的EC为

PageRank

PageRank (PR)[5]目标是EC的变体，开始是为搜索引擎对网页进行排名而开发的\

界说节点v的PR为

其间

• 是一个“阻尼因子”，它捕捉一个节点经过跟随链接抵达另一个节点的概率，而不是被传送到另一个节点

HITS算法[24]

HITS算法[24]是一个二分法的链接剖析算法，开始规划用于评价网页的相关性

在有向图中

• 榜首个得分是威望，它量化了网页内容的价值
• 第二个得分是网站集线器，它评价网站链接到其他网页的价值

在无向图的状况下，两个分数终究是相同的值

Node Clique Number

节点团数(NCN,Node Clique Number)是包括给定节点的最大 最大团的巨细

最大团问题[33]的界说如下：给定一组节点，其间一些节点之间有边，最大团是节点的最大子集，其间每个点都直接衔接到子会集的每个其他节点

4 SIR-GN METHODOLOGY

本节展现了咱们提出的办法SIR-GN，这是一种根据聚类的迭代办法，用于图上的节点结构标明学习

咱们提出了SIR-GN的两种变体

• SIR-GN: GMM
• SIR-GN: K-Means

这两种变体的首要区别是它们完结时运用的聚类办法

---

SIR-GN办法以节点的根本特点(即度)为起点对节点结构进行编码，经过运用节点聚类和节点邻域联系的迭代进程来学习丰富的结构标明

正如咱们稍后将看到的，迭代是重要的，因为它们有用地答应模型进一步深化到节点的结构类似性

SIR-GN的终究输出是一个结构标明向量，它不仅成功地编码了节点结构，而且与现在其他最先进的办法不同，它是可解说的，因为成果向量的每个维度都有详细的意义

总的来说，SIR-GN首要由初始化和迭代进程两个阶段组成

• 初始化为每个节点创立初始标明向量
• 迭代进程是咱们办法的首要部分，它本身能够分为两个步骤:极点描绘和聚合
• 履行迭代进程，直到满意预界说的中止原则

在下面的部分中，咱们将

• 详细描绘咱们的办法的一切阶段
• 展现两种出现的改变
• 讨论咱们办法的可解说性
• 剖析咱们办法的时间和空间杂乱性
• 并展现咱们办法的一些办法特点

---

为了便于理解咱们的办法，咱们供给了一个运转示例，如图2所示

其间包括示例网络的可视化标明及其初始化和迭代进程的两个迭代

关于迭代进程，咱们一起显现极点描绘和聚合步骤的值

网络和表格都用不同的色彩编码，以展现每个步骤中结构等效的节点

能够看出，示例网络包括四种不同的结构类型，组成四组，别离是蓝色(1,7)、橙色(2,6)、黄色(3,5)、绿色(4)

该算法的意图是逐渐区别示例图中出现的一切结构人物

经过将每个节点标明的色彩与分配给每个节点ID的色彩进行匹配，能够看到这一点

例如，在初始化步骤中，算法成功地识别了两个结构人物，别离用蓝色和三文鱼色

但咱们能够看到，从2到6的节点被过错地分组在一起(即三文鱼色)，虽然实践上它们应该被分为三个不同的结构人物(即橙色、黄色、绿色和上一个迭代)

然后，该算法经过改善初始化，在迭代2完毕时完结这种分解

在对办法的详细描绘期间，将进一步解说运转示例。

---

在以下部分中，咱们将运用以下通用界说

• 设$G=(V,E)$标明具有极点集$V$和边集$E$的无向无权图
• 关于每个极点$u\in V$，咱们界说$nbr(u)=V|(u,V)\in Eor(V,u)\in E\subseteq V$为包括$u$的邻域的调集(由边直接衔接到$u$的节点)
• $|nbr(u)|$为$u$的街坊数

4.1 Initialization

要初始化该办法，用户有必要首要挑选所需的输出标明巨细

在算法的极点描绘步骤中，生成的标明的每个维度将对应一个簇的质心

因而，算法接下来的步骤中运用的簇的数量将等于所挑选的标明巨细

聚类中粗的巨细也便是终究嵌入向量的维度d

此外，这还生成了两个在挑选所需标明巨细时有必要考虑的束缚

• 榜首个束缚是所挑选的巨细将是输出标明的实践巨细的上限。这背面的原因是，在某些状况下，输入图中没有包括满意的结构改变，使得模型无法抵达所恳求的集群数量。在这些状况下，未运用的集群和维将不包括任何信息，能够安全地丢掉
• 其次，恳求的巨细不能大于输入图$|V|$的节点数，作为最坏的状况，每个节点将包括在自己的集群中

但是，在SIR-GN的日常运用中，这些束缚并不重要，因为实际国际的图一般比任何可用的标明巨细都大，当包括相同数量的信息时，更紧凑的标明总是首选的

挑选所需的巨细后，该办法初始化每个节点$u$的标明向量

除一维向量外，一切向量的值都初始化为0(一切向量都是如此)

这些值被初始化为等于节点的程度$|nbr(u)|$

咱们迭代算法的终究方针是逐渐区别节点的结构信息

咱们经过有用地探究节点街坊的不同层次来完结这一点

考虑到这个方针，咱们挑选了度，因为这是最简略的核算信息，能够用来在结构上区别两个节点

虽然如此，只需初始化保证对每个结构上等价的节点，两个对应的初始标明都用相同的值初始化，就能够运用其他初始化办法

违背此条件意味着该算法将不保存结构特点(拜见第4.6节)。

图2展现了在三维向量空间中的度初始化

能够看出，榜首个维度的值正是节点度(1.0和2.0)

节点度能够看作是一个平凡的一维向量标明，但它满意相同结构的两个节点具有相同向量标明的原则

在咱们的试验中，第5节，咱们考虑节点度作为一个基线，并显现了它的功用有多差，当与咱们提出的办法比较

4.2 Iterative Process

算法1展现了咱们的首要办法SIR-GN: K-Means

用算法2中的高斯混合模型(GMM)极点描绘函数替换第17行中的K-Means极点描绘函数，能够很容易地将代码转换为sir – gn: GMM

表2包括运用的符号

如前所述，迭代进程由两个首要步骤组成

• 极点描绘(第17行)
• 聚合循环(第18-23行)，该进程的输出是显式编码每个生成的结构类别中街坊节点的期望数量的标明

---

恣意两个极点描绘函数的榜首部分，以及整个迭代进程，都是聚类步骤

需求留意的是，以下步骤中运用的集群数量等于初始化步骤中挑选的标明巨细

在聚类步骤中，咱们对生成的潜在空间的最小最大归一化当时状况运用聚类办法。这有用地将结构类似的节点分组在一组结构集群中

直观上，聚类描绘了存在于潜在空间中的首要结构人物，并供给了用一切可用结构人物之间的概率散布描绘图中一切极点的或许性

这个概率衡量一个节点归于特定结构人物的或许性(例如，假定咱们有一个极点和两个不同的簇，如果极点只归于榜首个簇，描绘向量将是[1.0,0.0])

在图2中，供给了极点标明，能够看到，在榜首次迭代时，极点标明只是标明每个节点所属的簇

• 榜首个集群包括节点1和7，第二个集群包括一切其他节点
• 在第2次迭代时，极点标明所代表的散布熵增大，节点2归于簇1的概率为0.23，簇3归于簇3的概率为0.77

为了生成这些极点描绘，咱们需求一种聚类算法，为咱们供给每个数据点成为新生成的聚类的一部分的概率散布

在这项作业中，咱们提出了两种或许的办法，但任何满意这一要求的办法都或许被运用。咱们首要提出SIR-GN: GMM变异

这个变体运用GMM聚类[38]

算法2展现了极点描绘步骤的这种改变

在咱们办法开发的早期阶段，GMM算法是咱们的榜首个候选算法，原因是GMM直接为咱们供给所需的概率散布

但是，GMM的核算成本使得它在需求更大标明尺寸的状况下不切实践(咱们在第5.7节展现SIR-GN: GMM的束缚)

为了战胜这些束缚，咱们提出了咱们的第二个变量SIR-GN: K-Means

因为SIR-GN: K-Means是咱们的首要和高档变异，除非还有清晰说明，以下一切剖析都是用这个变异履行的

但是，试验部分供给了在这两种改变中取得的成果，以便比较它们的功用

算法1显现了这个改变的极点描绘步骤

---

在SIR-GN: K-Means中，咱们提出了一种运用K-Means[26]的启发式办法

近似核算如下

首要，咱们运用K-Means算法和之前迭代得到的节点标明来核算每个结构类别的簇质心

在核算完质心后，咱们核算从上一次迭代的每个节点标明到每个质心的间隔(算法1中的第4行)

然后，为了用概率变换间隔，咱们运用以下公式(算法1中的第5行):

其间

• dVudV_udVu​为节点u的新核算的间隔向量
• $Max(a)$和$Min(a)$为检索输入阵列$a$的最大值和最小值的函数
• 得到的值与节点到质心的间隔成反比
• 终究，关于每个节点，咱们对其新核算的向量进行归一化，将其除以其一切间隔的总和(行6)

得到散布后，咱们在算法1的第18-23行遍历一切节点，并对其街坊的向量求和(聚合操作)，完毕迭代

例如，在图2中，节点4([0.46,1.54,0.0])的第2次迭代的标明PR是经过对节点3和节点5的极点标明([0.23,0.77,0.0]+[0.23,0.77,0.0])求和得到的

成果是对每个生成的结构人物类别中街坊节点的预期数量进行编码的标明

每次迭代都答应模型有用地深化到节点的结构类似性

如图2所示。在初始化期间，只需两个结构相同的组，蓝色和一切剩余的节点

终究一组包括一切2阶节点

在榜首次迭代之后，咱们能够看到咱们的模型怎么区别一个额定的结构组(黄色)，但依然无法区别节点4

这在进程的第2次迭代中得到纠正，在此进程中，模型正确区域别了一切现有的结构组

4.3 Stopping Criteria

咱们的办法的中止规范是用户挑选的输入变量$d$

直观上，d相当于算法所进行的结构探究深度(算法1第15行)，也便是说，SIR-GN将从图中每个节点周围最多$d$层的邻域中搜集结构信息

如果用户希望从整个可用网络中搜集结构信息，$d$应等于输入网络的直径

如第3节所述，图的直径是任何节点对之间的最大最小间隔。该值保证在此迭代次数之后，每个生成的节点标明都遭到网络中一切其他衔接节点的影响

不幸的是，在更大的图中核算准确的直径或许会很昂贵，然后咱们在附录a中供给了一种办法来有用地核算直径的近似

另一个束缚是，根据图的结构和稀少性，直径或许会导致一个高值，这导致很多的SIR-GN迭代

如果较低的迭代量是首选的，咱们根据经历调查到，一个很好的经历法则是当仅有生成的标明的数量中止增加时中止迭代进程

这能够经过在节点标明上运用HashSet并终究核算其巨细来轻松完结

直观地说，这种中止规范是可行的，因为咱们在每次迭代中探究更多的节点邻域级别，一起发现新的结构信息

然后将这些信息聚合为前一级的信息，与其他节点比较，更好区域别每个节点的向量标明

然后在整个迭代进程中，仅有标明的数量趋于增加，直到没有新的结构差异被发现

---

请留意，有此判据的SIR-GN在有限时间内中止，如下定理所述。

定理4.1 运用根据仅有标明数的中止原则的SIR-GN在有限时间内中止

证明。在4.5节中，定理4.3标明具有相同结构的一切两个节点对总是具有相同的标明。根据这个定理，很显着，仅有标明的数量是由每个节点周围仅有结构的数量简略地限制的。每个节点周围的不同结构的数量不能大于图$|V|$中的节点数量。因而，$|V|$限制了仅有标明的数量。那么，在每次迭代中，或许会产生两种状况:

• (1)仅有标明的个数坚持不变或比前一次迭代的W.R.T.削减;或
• (2)仅有标明的数量W.R.T.比前一次迭代增加。

在榜首种状况下，算法中止。而在第二种状况下，算法继续迭代

第二种状况不或许永远产生，因为仅有标明的数量遭到节点周围仅有结构的数量的束缚

然后算法在一个有限的时间内中止

咱们在第5.6节中供给了这种中止规范的实证评价

此外，咱们展现了根据仅有标明的数量的中止原则导致了较低的迭代量，但供给了与图的直径相当的功用

4.4 Interpretation and Outcome Explanation

SIR-GN能够解说为，作为极点描绘符聚合的成果，该办法创立了一个终究的节点标明，该标明对输入网络中存在的每个首要结构人物(结构集群)的街坊的预期数量进行编码

算法的每一次接连迭代都依赖于前一次迭代的结构簇供给的描绘信息，以生成新的节点标明

图3可视化地显现了咱们的办法怎么在整个迭代中聚合结构信息，以生成简略示例网络中一个节点(节点1)的终究结构标明

能够看出，每个节点都是在算法的前一次迭代中，根据街坊的状况搜集结构信息生成的

重复这个进程产生了一个结构信息流，从算法的榜首次迭代(树的叶子)开端，到当时迭代的终究结构标明(树的根)完毕，在街坊之间传递信息

这个可视化展现了，经过满意的迭代，咱们的办法怎么有用地在整个网络中分散结构信息，创立一个考虑到节点的整个衔接网络的结构标明

---

因为SIR-GN的可解说性，咱们能够界说一种办法来解说在分类使命中运用的节点标明

关于规范分类使命，给定一个输入特征向量$x$和一个分类器$f$，特点使命包括为$x$中的每个特征供给一个重要性排名，这促进$f$将x分类为特定的类

归因办法是与成果解说相关的办法(见[18]的调查)，它分为白盒办法(首要用于NN分类)和黑盒办法或模型不行知性办法(可用于各种解说技能)

模型不行知归因办法独立于特定的模型，能够运用于任何ML模型(如支持向量机、随机森林和逻辑回归)

一个盛行的模型不行知归因办法是LIME[40]

一般，当考虑根据向量节点标明的分类使命时，规范的归因进程不起作用，因为评分特征是不行解说的

在咱们的比方中，因为意义被很好地界说，而且咱们的向量标明聚集于节点周围的图结构，咱们能够界说一个进程，关于给定的节点v，给定一个通用特点向量attr(由通用特点办法供给)，能够对图中的边进行评分，以划出节点周围最相关的、对分类成果担任的结构。

为此，关于根据$SIR-GN:k-means$的进程的每次迭代$t$，咱们存储质心{C1t，…,Cnt}\{C^t_1，…, C^t_n\}{C1t​，…,Cnt​}用K-means聚类算法提取，对每个极点$v$用极点描绘DVvtDV^t_vDVvt​和标明PRutPR^t_uPRut​。然后，算法3给定节点$v$和规范归因进程供给的归因向量attr，对搜索极点$v$得到的每条边进行排序，直到预界说的深度$d$

算法3运用了一个递归函数(第6行)，它环绕节点$v$迭代打开结构，类似于图3

这种打开一直核算到深度$d$。给定节点$v$、特点向量attr和当时打开水平$t$，递归函数为每个节点$u\in nbr(v)$核算两件事

• 首要，函数核算一条边$(v,u)$的排名ra(v,u)tra^t_{(v,u)}ra(v,u)t​，这个排名是edgeContribi∗attr[i]edgeContrib_i * attr[i]edgeContribi​∗attr[i]每个维度$i$的总和(第17-20行)
• 其次，该函数核算节点$u$的新的归属向量currentAttrutcurrentAttr^t_ucurrentAttrut​。该归属向量currentAttrutcurrentAttr^t_ucurrentAttrut​是描绘PRut−1PR^{t−1}_uPRut−1​每个维度对分类的重要性的向量，它是经过impacti∗dgeContribi∗attr[i]impact_i ∗dgeContrib_i * attr[i]impacti​∗dgeContribi​∗attr[i]每个维度的矢量和得到的。向量impactiimpact_iimpacti​标明PRutPR^t_uPRut​到CitC^t_iCit​的每个维度的类似程度(在[0,1]范围内丈量的类似程度)(第15和16行)

一旦核算出currentAttrutcurrentAttr^t_ucurrentAttrut​，函数递归地调用自己，运用特点向量currentAttrutcurrentAttr^t_ucurrentAttrut​探究节点$u$(第25行)

正如咱们将在第5.8节调查到的，这个算法实践上强调了担任分类的重要结构

4.5 Time and Space complexity

4.6 Theoretical Properties

5 EXPERIMENTAL EVALUATION

本节介绍一组试验，旨在评价SIR-GN: GMMand SIR-GN: K-Means的才能。咱们正在将取得的成果与其他六种先进的办法进行比较。即:node2vec [17]， struc2vec [39]， GraphWave [13]， GraphSAGE [20]， ARGA [34]， andDRNE [46]

…..

读后总结

2022/07/20 榜首次阅读

以下图为例，讲解文章首要的算法：

首要，初始化嵌入矩阵，矩阵榜首列的值为每个极点的度，其余为0

然后运用对其进行聚类（比方k-means）

然后核算每个极点向量关于每个簇的概率

节点1对簇1（也便是榜首列）的概率为1，对簇2（也便是第二列）的概率为0… 节点3对簇1（也便是榜首列）的概率为0，对簇2（也便是第二列）的概率为1…

然后根据节点之间的衔接联系，更新嵌入矩阵

比方：节点2与节点1和节点3衔接，那么更新后节点2的标明为节点1+节点2的嵌入向量（node 2 = 1 + 3，自己之前的就不需求了）

2 = 【1.0， 0，0】 + 【0，1.0，0】 = 【1.0，1.0，0】

然后再对这个嵌入矩阵进行聚类，得到每个节点归于每个簇的概率

• 节点2归于簇1的概率为0.23，归于簇2的概率为0，归于簇3的概率为0.77
• 节点7归于簇1的概率为1，归于簇2的概率为0，归于簇3的概率为0.0

之后的步骤也便是不断迭代重复了

….

Note

• 迭代次数 = 嵌入向量的维度巨细d
• 聚类的簇巨细是动态改变的，需求去求，不是固定的
• 初始化时，能够区别两个类；榜首次迭代后，能够区别三个类；第2次迭代后，能够区别三类…（感觉有点问题，代码中从i=0->d, 迭代了d+1次啊？？ 有点迷）

很多细节没有细读，感觉仍是有点协助的，之后再细心研读！

结语

文章仅作为个人学习笔记记载，记载从0到1的一个进程

希望对您有一点点协助，如有过错欢迎小伙伴纠正