LINE:大规模信息网络嵌入方法

简介: LINE:大规模信息网络嵌入方法

论文标题:LINE: Large-scale Information Network Embedding


论文链接:https://arxiv.org/abs/1503.03578


论文来源:WWW 2015


一、概述


目前已有一些图embedding的方法,这些方法在小规模网络上有不错的效果,然而面对现实世界中的大规模信息网络时是无能为力的,这些网络通常包含几百万个节点和数十亿的边。举例来说,一些方法比如MDS,IsoMap以及拉普拉斯特征图法的复杂度与节点数量呈二次关系。


虽然最近的一些研究提出了一些大规模图的embedding方法,然而这些方法要么使用不是为了网络而设计的间接方法,要么缺少一个特别为图设计的目标函数。本文提出的LINE方法是一个新的大规模图embedding方法,提出了一个专门设计的目标函数,能够学习图的特性,并且提出了一个高效的优化算法,能够有效率地学习数百万节点的embedding向量。 LINE能够处理各种类型的网络,无论是有向的还是无向的,binary的还是加权的。模型优化的目标函数保留了图局部和全局的结构。


通常图的局部结构由图中可观测到的连接(也就是边)来反映,在本文中这被定义为节点之间的一阶相似性(first-order proximity)。我们观察到在现实世界的网络中,一些合理的连接可能是没有被观测到的,换句话说一阶相似性对于保持图的全局结构是不足够的。作为一阶相似性的互补,本文提出了节点之间的二阶相似性(second-order proximity),二阶相似性通过节点的共享邻居来决定,直观地来解释就是拥有共享邻居的节点是更为相似的。在许多现实的例子中可以印证这一点,比如拥有相同社交网络的两个人是很可能有共同的兴趣的,或者两个词如果经常和相同的一些词一起使用,那么这两个词的含义很可能是相似的。如下图所示,节点6,7之间有很高的一阶相似性,5,6之间有很高的二阶相似性:


QQ截图20220612095757.png

                                                   举例


大规模图embedding学习的优化问题很具有挑战性,直接应用随机梯度下降法是有问题的,这是因为在很多图中边是加权的,而且权重具有很高的方差。比如一个词共现网络中,权重数值从1到几十万不等,这些权重在优化时都要与梯度相乘,这就造成了梯度爆炸。为了解决这个问题,我们提出了一种边采样(edge-sampling)方法,根据边的权重作为概率来采样,这样就可以将加权图当做binary的图来处理。


二、问题定义


  1. 信息网络


QQ截图20220611221142.png


三、方法


LINE具有以下三个特点:

①能够保留节点之间的一阶相似性和二阶相似性;

②能够处理大规模图;

③能够处理任意类型边的图。

  1. 模型


  • LINE与一阶相似性


QQ截图20220611221301.png


QQ截图20220611221339.png


  • LINE与二阶相似性

对于有向图和无向图,都存在二阶相似性。给定一个网络,不失一般性,我们可以认为它是有向图(无向图也可以认为两个相反方向相同权重有向图的合并)。二阶相似性假设共享很多连接的节点是相似的。在这种假设下,每个节点被看做其他节点的“上下文”,如果两个节点具有相同的上下文分布的话,它们就应该是相似的。因此,每个节点扮演两种角色:

①节点本身;

②其他节点的上下文。


QQ截图20220611221547.png


QQ截图20220611221624.png

QQ截图20220611221705.png


  • 一阶与二阶相似性的结合

在本文中采用的结合一阶与二阶相似性训练结果的方法是首先单独按照上面一阶与二阶相似性的方法进行训练,然后将得到的对应的词向量拼接起来。本文没有提出联合训练的方法。

  1. 模型的优化

QQ截图20220611221822.png

QQ截图20220611221909.png


QQ截图20220611221937.png


Alias table method:【数学】时间复杂度O(1)的离散采样算法—— Alias method/别名采样方法

  1. 讨论

该部分讨论了LINE模型的几个实际问题。


  • 低度节点


QQ截图20220611222309.png


四、实验


  1. 数据集


在语言网络、社交网络、引用网络上进行实验,这些数据集覆盖了各种类型的网络:

QQ截图20220612095903.png

                                                 数据集

  1. 结果


在各个数据集上的实验结果如下:

QQ截图20220612095929.png

                                    word analogy on Wikipedia data

QQ截图20220612100022.png

                               page classification on Wikipedia data set

QQ截图20220612100052.png

                              multi-label classification on the Flickr network

QQ截图20220612100121.png

                         multi-label classification on the Youtube network

QQ截图20220612100210.png

                        multi-label classification on DBLP(AuthorCitation) network

QQ截图20220612100255.png

                        multi-label classification on DBLP(PaperCitation) network

  1. 可视化

QQ截图20220612100329.png

                                              可视化

  1. 网络稀疏性


应对稀疏网络结构:


QQ截图20220612100405.png

                                                  网络稀疏性

  1. 参数敏感性


超参数的影响:

QQ截图20220612100426.png

                                               参数敏感性

  1. 并行化


多线程训练的影响:

QQ截图20220612100509.png

                                                  多线程加速




相关文章
|
22天前
|
机器学习/深度学习 计算机视觉
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 MobileViTv1高效的信息编码与融合模块,获取局部和全局信息
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 MobileViTv1高效的信息编码与融合模块,获取局部和全局信息
129 62
RT-DETR改进策略【模型轻量化】| 替换骨干网络为 MobileViTv1高效的信息编码与融合模块,获取局部和全局信息
|
2月前
|
监控 安全 网络安全
深入解析PDCERF:网络安全应急响应的六阶段方法
PDCERF是网络安全应急响应的六阶段方法,涵盖准备、检测、抑制、根除、恢复和跟进。本文详细解析各阶段目标与操作步骤,并附图例,助读者理解与应用,提升组织应对安全事件的能力。
356 89
|
22天前
|
机器学习/深度学习 自然语言处理 计算机视觉
RT-DETR改进策略【Backbone/主干网络】| CVPR 2024 替换骨干网络为 RMT,增强空间信息的感知能力
RT-DETR改进策略【Backbone/主干网络】| CVPR 2024 替换骨干网络为 RMT,增强空间信息的感知能力
61 13
RT-DETR改进策略【Backbone/主干网络】| CVPR 2024 替换骨干网络为 RMT,增强空间信息的感知能力
|
22天前
|
计算机视觉
RT-DETR改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
RT-DETR改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
48 5
RT-DETR改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
|
26天前
|
机器学习/深度学习 计算机视觉
YOLOv11改进策略【模型轻量化】| 替换骨干网络为 MobileViTv1高效的信息编码与融合模块,获取局部和全局信息
YOLOv11改进策略【模型轻量化】| 替换骨干网络为 MobileViTv1高效的信息编码与融合模块,获取局部和全局信息
70 9
YOLOv11改进策略【模型轻量化】| 替换骨干网络为 MobileViTv1高效的信息编码与融合模块,获取局部和全局信息
|
2月前
|
机器学习/深度学习 数据采集 人工智能
GeneralDyG:南洋理工推出通用动态图异常检测方法,支持社交网络、电商和网络安全
GeneralDyG 是南洋理工大学推出的通用动态图异常检测方法,通过时间 ego-graph 采样、图神经网络和时间感知 Transformer 模块,有效应对数据多样性、动态特征捕捉和计算成本高等挑战。
73 18
GeneralDyG:南洋理工推出通用动态图异常检测方法,支持社交网络、电商和网络安全
|
26天前
|
机器学习/深度学习 自然语言处理 计算机视觉
YOLOv11改进策略【Backbone/主干网络】| CVPR 2024 替换骨干网络为 RMT,增强空间信息的感知能力
YOLOv11改进策略【Backbone/主干网络】| CVPR 2024 替换骨干网络为 RMT,增强空间信息的感知能力
36 0
YOLOv11改进策略【Backbone/主干网络】| CVPR 2024 替换骨干网络为 RMT,增强空间信息的感知能力
|
14天前
|
机器学习/深度学习 算法 文件存储
神经架构搜索:自动化设计神经网络的方法
在人工智能(AI)和深度学习(Deep Learning)快速发展的背景下,神经网络架构的设计已成为一个日益复杂而关键的任务。传统上,研究人员和工程师需要通过经验和反复试验来手动设计神经网络,耗费大量时间和计算资源。随着模型规模的不断扩大,这种方法显得愈加低效和不够灵活。为了解决这一挑战,神经架构搜索(Neural Architecture Search,NAS)应运而生,成为自动化设计神经网络的重要工具。
|
3月前
|
机器学习/深度学习 数据采集 人工智能
基于Huffman树的层次化Softmax:面向大规模神经网络的高效概率计算方法
层次化Softmax算法通过引入Huffman树结构,将传统Softmax的计算复杂度从线性降至对数级别,显著提升了大规模词汇表的训练效率。该算法不仅优化了计算效率,还在处理大规模离散分布问题上提供了新的思路。文章详细介绍了Huffman树的构建、节点编码、概率计算及基于Gensim的实现方法,并讨论了工程实现中的优化策略与应用实践。
91 15
基于Huffman树的层次化Softmax:面向大规模神经网络的高效概率计算方法
|
26天前
|
计算机视觉
YOLOv11改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
YOLOv11改进策略【卷积层】| CGblock 内容引导网络 利用不同层次信息,提高多类别分类能力 (含二次创新)
30 0

热门文章

最新文章