Representation Learning on Network 网络表示学习笔记

2024-06-22 15:08

本文主要是介绍Representation Learning on Network 网络表示学习笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • Embedding Nodes
    • Encoder-decoder View
    • Encoding Methods
      • 1 Factorization based
      • 2 Random Walk based
      • 3 Deep Learning based

网络表示学习(Representation Learning on Network),一般说的就是向量化(Embedding)技术,简单来说,就是将网络中的结构(节点、边或者子图),通过一系列过程,变成一个多维向量,通过这样一层转化,能够将复杂的网络信息变成结构化的多维特征,从而利用机器学习方法实现更方便的算法应用。

Embedding Nodes

在这些方法中,受研究和应用关注最多的就是节点向量化(Node Embedding),即对于一个图 G=(V,E)G=(V,E),学习一种映射:

f:viziRd

其中 zi 是一个输出的多维向量,并且满足 d≪|V|。用于评估这个学习效果的标准,就是看向量化后重新复原网络结构的能力。

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

  1. 学习属性的选择:不同的向量化表示方法,都是对网络信息的一种摘要。有时我们会倾向于保存网络中节点的近邻关系,有时倾向学习节点在网络中的角色(比如中心节点)。不同的应用对“学习属性”的选择有不同的要求,故而引发了各类算法的爆发。
  2. 规模化:现实应用中有很多网络包含了大量的节点和边,高效的向量化方法,能够在短时间内处理超大规模的网络,才比较有实际应用的可能性。
  3. 向量维度:如何确定合适的向量表示维度,是一个很难的问题,并且也是和具体场景相关的。事实上,越高的维度可能带来越好的效果,但是会极大降低应用性能。平衡性能和效果,在不同的应用中需要因地制宜。

1. Encoder-decoder View

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

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

  • Encoder:负责把每个节点映射到一个低维向量中
  • Decoder:负责从向量化的信息中重新构建网络结构和节点属性

这里写图片描述

对于上述框架,它包含4个概念:

  1. 节点关系函数 sG:V×V→R+sG:V×V→R+ 衡量两个节点之间的距离

  2. Encode 函数 ENC:V→RdENC:V→Rd 将节点映射到 d 维向量

  3. Decode 函数 DEC:Rd×Rd→R+DEC:Rd×Rd→R+ 将向量化信息重新恢复成节点关系

  4. 损失函数 ll 用于度量模型刻画能力,比如 DEC(zi,zj)DEC(zi,zj) 与 sG(vi,vj)sG(vi,vj)的偏差情况。

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

  1. 向量化后的节点之间没有参数共享,完全是一种记忆化的模型存储和查询方式(Look-up),这对存储和计算都构成了不小的挑战。由于节点之间没有参数共享,也就大大损失了泛化能力。

  2. 目前大部分向量化方法,仅利用网络结构信息,并没有利用网络节点本身的属性(比如文本、图像和统计特征),使得结果向量对网络信息的存储很有限。

  3. 大部分模型是对静态网络结构的直推学习,并没有考虑网络时间演化过程中新节点的生成和旧节点的湮灭,而网络的动态特性对理解其性质也至关重要。这个弱点甚至会影响向量化在动态网络上的效果。比如在互联网场景中,每天都有新的结构产生和消除,今天生成的向量化表示,两天后的可用性是否会大打折扣?这是一个值得深思的问题。

2. Encoding Methods

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

2.1 Factorization based

矩阵分解是传统的节点向量化方法,其思想就是对网络的邻接矩阵进行降维,给每个节点生成一个低维表示。

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

L(Z)=12(zizj)2Wij=ZTLZ

其中 LL 是图 G 的 Laplacian 矩阵,L=D−AL=D−A,其中 DD 是度矩阵,AA 是邻接矩阵。

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

$%

2.2 Random Walk based

随机游走利用了网络结构采样,在处理大规模网络问题上,常常有很好的性能表现,同时可以很好地刻画网络局部信息。大部分情况下,我们对节点的观察并不需要考虑离它太远的节点,利用局部信息已经能够区别节点间的差异。

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

这里写图片描述

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

LINE
LINE(Large-scale Information Network Embeddings) 直观上看其实并没有用随机游走。但是[2]将其归类到随机游走的范畴,原因是它和 DeepWalk 的框架类似地应用了概率损失函数。即通过最小化节点 i,ji,j 相连的经验概率 p^(i,j)p^(i,j) 与向量化后两个节点相似性 p(vi,vj)p(vi,vj) 的距离,并且同时考虑了一阶和二阶相似度(优化两个损失函数),这和随机游走的底层动机是相似的。在实际计算过程中,作者引入了一系列预处理和优化方法(比如负采样),来加快学习性能。这里写图片描述

2.3 Deep Learning based

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

L=viVDEC(zi)si22

其中 sisi 是一个 |V∥|V‖ 维的输入向量,而 zizi 的维数必然远小于前者。其实它的建模思路和前面提到的矩阵分解是一致的,只是在降维时用的不是矩阵分解,而是 Auto-encoder。
这里写图片描述

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

这种方法遇到一个较大的问题是,其输入向量维度被限制为|V||V| ,一方面对网络规模有一定限制,另一方面对新节点的接受程度不好(新节点加入后可能需要重新训练整个网络)。

GCN
前面说的几种模型,大都是利用网络结构对节点进行向量编码。另外有一类方法,强调的更多是将节点本身及其邻居节点的属性(比如文本信息)或特征(比如统计信息)编码进向量中,这类方法可以统称为 Neighborhood Aggregation Algorithms,它们引入了更多特征信息,并且在邻居节点间共享了一些特征或参数。
这里写图片描述

GCN(Graph Convolutional Networks) 就是其中的一类。上图是 GraphSAGE 算法 [3]的流程步骤。相比 SDNE 类的算法,GCN 的输入向量不必限制在 |V||V| 维,所以输入数据可以大大减小维数。因为 GCN 在网络结构的基础上,又引入了节点信息,所以在节点分类、链路预测等任务上,比只考虑网络结构的模型有更好的表现,当然这也取决于数据的丰富程度。
3. Evaluation
文章[2]在人工生成网络、社交网络、论文合作网络和蛋白质网络上对几种常见的向量化方法进行了网络重构、节点可视化、链路预测、节点分类的评测,大部分模型实验的输出结果是128维的向量。网络信息如下:
这里写图片描述
A. Graph Reconstruction这里写图片描述
网络重构,是从向量化的节点出发,重新连边构建网络。我们发现 保存了高阶节点关系的模型往往能够更好地重构网络 ,这也符合直观认识。SDNE 几乎在所有数据集上击败了其他模型。

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

下图是模型对 SBM 生成网络处理,输出编码至 128 维向量后,再利用 t-SNE 进行压缩得到的二维图像。
这里写图片描述

当 node2vec 模型设置 BFS 倾向大一些时,可以得到界限很清晰的聚类结果。但是 LE(Laplacian Eigenmaps) 和 GF(Graph Factorization) 模型的效果就比较差强人意了,尤其是 GF 基本不能看。

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

这里写图片描述

从网络结构和节点性质来看,SDNE 和 node2vec 保留了原始网络较多信息。尤其是 SDNE 把节点0单独放到了很远的位置,因为它是社区间的 bridge 节点。而 HOPE 对 0、32、33 的社区中心节点属性刻画的比较好,并且明显地划分出两个社区。GF 的表现依然比较差,除了把度大的节点放在了中心,叶子节点放在了周围,并没有很好的区别社区距离。

C. Link Prediction
在链路预测评估中,各个算法的表现并不是很稳定。这也和模型的设计并不是为特定任务而定制有关。
这里写图片描述

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

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

这里写图片描述
从数据效果来看,node2vec 模型几乎在所有数据集中,都远胜其他模型。原因可能是 node2vec 模型同时刻画了节点的社区结构和网络角色,说明在节点分类中 Random Walk 方法有比较不错的表现。

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

Reference
[1] Goyal, Palash, and Emilio Ferrara. “Graph Embedding Techniques, Applications, and Performance: A Survey.” arXiv preprint arXiv:1705.02801 (2017).

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

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

这篇关于Representation Learning on Network 网络表示学习笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1084633

相关文章

HarmonyOS学习(七)——UI(五)常用布局总结

自适应布局 1.1、线性布局(LinearLayout) 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列,Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距,达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式,且在各类尺寸屏幕上表现一致,其中交叉轴为垂直时,取值为Vert

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya(不是本人,claude AI)在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容: 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

学习hash总结

2014/1/29/   最近刚开始学hash,名字很陌生,但是hash的思想却很熟悉,以前早就做过此类的题,但是不知道这就是hash思想而已,说白了hash就是一个映射,往往灵活利用数组的下标来实现算法,hash的作用:1、判重;2、统计次数;

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

ASIO网络调试助手之一:简介

多年前,写过几篇《Boost.Asio C++网络编程》的学习文章,一直没机会实践。最近项目中用到了Asio,于是抽空写了个网络调试助手。 开发环境: Win10 Qt5.12.6 + Asio(standalone) + spdlog 支持协议: UDP + TCP Client + TCP Server 独立的Asio(http://www.think-async.com)只包含了头文件,不依

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学