Representation Learning on Network 网络表示学习

  • 时间:
  • 浏览:1
  • 来源:大发快三代理—大发大发彩票app

DeepWalk 是最早提出的基于 Word2vec 的节点向量化模型。其主要思路,随后我利用构造节点在网络上的随机游走路径,来模仿文本生成的过程,提供随后节点序列,再套用 Word2Vec 对每个节点进行向量化表示。随后知道了节点 V 的前 k 个节点和后 k 个节点,就能很好地将网络邻居形状存入向量中。其目标随后我最大化 logPr(vik,,vi1,vi+1,,vi+k|Zi)logPr(vi−k,…,vi−1,vi+1,…,vi+k|Zi)

HOPE(High-Order Proximity preserved Embedding) 模型相比 GF,通过引入 ||SZsZTt||2F||S−ZsZtT||F2 考虑了高阶累似 性,论文作者尝试了 Kate Index, Root Page Rank, Common Neighbors, Adamic-Adar Score 等累似 性指标,随后把累似 性矩阵分解为 S=M1gMlS=Mg−1Ml,随后M1gMg−1 和 MlMl 算不算稀疏的,统统利用 SVD 能有较高的运行速度。

Laplacian Eigenmaps 的目标是将累似 性高的随后节点,映射到低维空间后依然保持距离相近,其损失函数定义为:

L(Z)=12(zizj)2Wij=ZTLZL(Z)=12(zi−zj)2Wij=ZTLZ 其中 LL 是图 G 的 Laplacian 矩阵,L=DAL=D−A,其中 DD 是度矩阵,AA 是邻接矩阵。

网络节点可视化,一般是将节点编码成二维或三维的向量,在坐标轴上标注出来。常常会以事实分类区别颜色标记在图像上,用来区分不同向量化最好的依据 的好坏。

或多或少 最好的依据 遇到随后较大的问題是,其输入向量维度被限制为|V||V| ,一方面对网络规模有一定限制,当时人面对新节点的接受程度不好(新节点加入后随后还要重新训练整个网络)。

在哪几种最好的依据 中,受研究和应用关注最多的随后我节点向量化(Node Embedding),即对于随后图 G=(V,E)G=(V,E),学习有这个 映射:

f:viziRdf:vi→zi∈Rd 其中 zizi 是随后输出的多维向量,随后满足d|V|d≪|V|。用于评估或多或少 学习效果的标准,随后我看向量化后重新复原网络形状的能力。

Note: 以下是根据综述 [1][2] 梳理的笔记,随后是初探,语言和理论必然有不严谨之处,欢迎指正。

从数据效果来看,node2vec 模型几乎在所有数据集中,都远胜或多或少模型。原困随后是 node2vec 模型一齐刻画了节点的社区形状和网络角色,说明在节点分类中 Random Walk 最好的依据 有比较不错的表现。

大帕累托图向量化算法,是属于非监督学习,如此针对特定的图计算任务(比如链路预测随后聚类)进行优化,随后我针对图信息的保存情形进行优化学习,其评价标准,随后我看其向量化后的数据对原始网络的恢复能力。整个学习过程被抽象为下图所示的框架图,它包括随后过程:

文章[2]在人工生成网络、社交网络、论文合作网络和蛋白质网络上对几种常见的向量化最好的依据 进行了网络重构、节点可视化、链路预测、节点分类的评测,大帕累托图模型实验的输出结果是128维的向量。网络信息如下:

综上 node2vec 和 SDNE 在除了链路预测问題中,几乎表现都很亮眼。值得重点挖掘!

Node2vec 是对 DeepWalk 的有这个 更广义的抽象,它引入了 biased-random walks,用来刻画每次随机游走是偏层厚探索(DFS)还是广度探索(BFS),分别侧重社区形状和节点重要性的信息。随后 node2vec 有 p 和 q 随后超参数,统统它是随后比较灵活的模型框架。后面 也会讲到,它在节点分类问題中有 着不俗的表现。

矩阵分解是传统的节点向量化最好的依据 ,其思想随后我对网络的邻接矩阵进行降维,给每个节点生成随后低维表示。

从 Top k 预测准确性来看,node2vec 模型在 BlogCatelog 数据中表现最好,或多或少数据集就比较一般(在 PPI 的 Top 表现随后我错)。HOPE 模型在 k 比较大时,效果一般在中上位置,比较稳定。

SDNE(Structural Deep Network Embeddings) 将节点的累似 性向量 sisi 直接作为模型的输入,通过 Auto-encoder 对或多或少 向量进行降维压缩,得到其向量化后的结果 zizi。其损失函数定义为:

L=viV||DEC(zi)si||22L=∑vi∈V||DEC(zi)−si||22 其中 sisi 是随后|V||V| 维的输入向量,而 zizi 的维数必然远小于前者。我我觉得它的建模思路和前面提到的矩阵分解是一致的,随后我在降维时用的算不算矩阵分解,随后我 Auto-encoder。

[2] William L. Hamilton, Rex Ying and Jure Leskovec. "Representation Learning on Graphs: Methods and Applications" arXiv preprint arXiv:1709.05584 (2017).

下图是模型对 SBM 生成网络补救,输出编码至 128 维向量后,再利用 t-SNE 进行压缩得到的二维图像。

作者在 SBM、PPI 和 BlogCatelog 网络上做了节点分类的实验。如下图:

在[1]中,作者提到节点向量化有3大挑战:

从网络形状和节点性质来看,SDNE 和 node2vec 保留了原始网络较多信息。尤其是 SDNE 把节点0单独放满了很远的位置,随后它是社区间的 bridge 节点。而 HOPE 对 0、32、33 的社区中心节点属性刻画的比较好,随后明显地划分出随后社区。GF 的表现依然比较差,除了把度大的节点放满了中心,叶子节点放满了附近,并如此很好的区别社区距离。

对于上述框架,它中有 随后概念:

在链路预测评估中,各个算法的表现并算不算很稳定。这也和模型的设计并算不算为特定任务而定制有关。

随机游走利用了网络形状采样,在补救大规模网络问題上,常常有很好的性能表现,一齐还还要很好地刻画网络局部信息。大帕累托图情形下,朋友儿对节点的观察并不一定还要考虑离它太远的节点,利用局部信息之上都都可以区别节点间的差异。

网络重构,是从向量化的节点出发,重新连边构建网络。朋友儿发现 保存了高阶节点关系的模型往往都都可以更好地重构网络 ,这也符合直观认识。SDNE 几乎在所有数据集上击败了或多或少模型。

本模块主要介绍3种常见的网络表示学习类别。

[3] Hamilton, William L., Rex Ying, and Jure Leskovec. "Inductive Representation Learning on Large Graphs." arXiv preprint arXiv:1706.02216 (2017).

随后模型 DNGR(Deep Neural Graph Representations) 与 SDNE 区别主要在于累似 性向量的定义不同,DNGR 将随后节点由随机游走得到的「一齐路径」作为衡量其累似 性的指标,而 SDNE 直接用一阶关系作为累似 性的输入。

当 node2vec 模型设置 BFS 倾向大或多或少时,还还要得到界限很清晰的聚类结果。随后 LE(Laplacian Eigenmaps) 和 GF(Graph Factorization) 模型的效果就比较差强人意了,尤其是 GF 基本都都可以看。

前面说的几种模型,大算不算利用网络形状对节点进行向量编码。另外有一类最好的依据 ,强调的更多是将节点有这个 及其邻居节点的属性(比如文本信息)或形状(比如统计信息)编码进向量中,累似 最好的依据 还还要统称为 Neighborhood Aggregation Algorithms,它们引入了更多形状信息,随后在邻居节点间共享了或多或少形状或参数。

下图是模型对 Karate 跆拳道俱乐部网络进行二维向量化编码的结果。

LINE(Large-scale Information Network Embeddings) 直观上看我我觉得并如此用随机游走。随后[2]将其归类到随机游走的范畴,原困是它和 DeepWalk 的框架累似 地应用了概率损失函数。即通过最小化节点 i,ji,j 相连的经验概率 ^p(i,j)p^(i,j) 与向量化后随后节点累似 性 p(vi,vj)p(vi,vj) 的距离,随后一齐考虑了一阶和二阶累似 度(优化随后损失函数),这和随机游走的底层动机是累似 的。在实际计算过程中,作者引入了一系列预补救和优化最好的依据 (比如负采样),来加快学习性能。

对于 Encoder-decoder 框架下现有的 state-of-the-art 模型,[2]的作者提出了2个弱点:

[1] Goyal, Palash, and Emilio Ferrara. "Graph Embedding Techniques, Applications, and Performance: A Survey." arXiv preprint arXiv:1705.02301 (2017).

网络表示学习(Representation Learning on Network),一般说的随后我向量化(Embedding)技术,简单来说,随后我将网络中的形状(节点、边随后子图),通过一系列过程,变成另随后维向量,通过随后一层转化,都都可以将复杂性的网络信息变成形状化的多维形状,从而利用机器学习最好的依据 实现更方便的算法应用。

根据[1]的调研,GF(Graph Factorization) 是第随后在 O(|E|) 的时间复杂性度上完成向量化的算法。其损失函数定义为:

L(Z,λ)=12(i,j)E(Wij<Zi,Zj>)2+λ2iZi2L(Z,λ)=12∑(i,j)∈E(Wij−<Zi,Zj>)2+λ2∑iZi2 其中 λλ 是正则化参数。跟后面 的 Laplacian Eigenmaps 相比,GF 算法是将随后向量重构后的边权作为衡量最好的依据 ,随后向量随后有多种重构最好的依据 ,比如直接点乘,随后求余弦累似 度等等。

GCN(Graph Convolutional Networks) 随后我其中的一类。上图是 GraphSAGE 算法 [3]的流程步骤。相比 SDNE 类的算法,GCN 的输入向量并不一定限制在 |V||V| 维,统统输入数据还还要大大减小维数。随后 GCN 在网络形状的基础上,又引入了节点信息,统统在节点分类、链路预测等任务上,比只考虑网络形状的模型有更好的表现,当然这也取决于数据的充足程度。

论文[2] 通过调研今年业界比较流行的向量化最好的依据 ,提出了一套通用的流程和模型框架。