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

                                                  多线程加速




相关文章
|
1月前
|
安全 物联网 物联网安全
量子通信网络:安全信息交换的新平台
【10月更文挑战第6天】量子通信网络作为一种全新的安全信息交换平台,正逐步展现出其独特的优势和巨大的潜力。通过深入研究和不断探索,我们有理由相信,量子通信网络将成为未来信息安全领域的重要支柱,为构建更加安全、高效、可靠的信息社会贡献力量。让我们共同期待量子通信网络在未来的广泛应用和美好前景!
|
19天前
|
机器学习/深度学习 计算机视觉 网络架构
【YOLO11改进 - C3k2融合】C3k2DWRSeg二次创新C3k2_DWR:扩张式残差分割网络,提高特征提取效率和多尺度信息获取能力,助力小目标检测
【YOLO11改进 - C3k2融合】C3k2DWRSeg二次创新C3k2_DWR:扩张式残差分割网络,提高特征提取效率和多尺度信息获取能力,助力小目DWRSeg是一种高效的实时语义分割网络,通过将多尺度特征提取分为区域残差化和语义残差化两步,提高了特征提取效率。它引入了Dilation-wise Residual (DWR) 和 Simple Inverted Residual (SIR) 模块,优化了不同网络阶段的感受野。在Cityscapes和CamVid数据集上的实验表明,DWRSeg在准确性和推理速度之间取得了最佳平衡,达到了72.7%的mIoU,每秒319.5帧。代码和模型已公开。
【YOLO11改进 - C3k2融合】C3k2DWRSeg二次创新C3k2_DWR:扩张式残差分割网络,提高特征提取效率和多尺度信息获取能力,助力小目标检测
|
20天前
|
监控 安全 测试技术
网络信息系统的整个生命周期
网络信息系统规划、设计、集成与实现、运行维护及废弃各阶段介绍。从企业需求出发,经过可行性研究和技术评估,详细设计系统架构,完成设备安装调试和系统集成测试,确保稳定运行,最终安全退役。
32 1
网络信息系统的整个生命周期
|
6天前
|
安全 Linux 网络安全
nmap 是一款强大的开源网络扫描工具,能检测目标的开放端口、服务类型和操作系统等信息
nmap 是一款强大的开源网络扫描工具,能检测目标的开放端口、服务类型和操作系统等信息。本文分三部分介绍 nmap:基本原理、使用方法及技巧、实际应用及案例分析。通过学习 nmap,您可以更好地了解网络拓扑和安全状况,提升网络安全管理和渗透测试能力。
33 5
|
9天前
|
SQL 安全 算法
网络安全的隐形盾牌:漏洞防御与信息加密的艺术
【10月更文挑战第36天】在数字世界的海洋中,网络安全犹如一艘船的保护罩,守护着我们的隐私和数据安全。本文将揭开网络安全的神秘面纱,从常见的网络漏洞到先进的加密技术,再到培养必要的安全意识,我们将一步步构建起防御的堡垒。文章不仅分享技术细节,还强调了在个人和组织层面采取积极措施的重要性。
|
20天前
|
存储 关系型数据库 MySQL
查询服务器CPU、内存、磁盘、网络IO、队列、数据库占用空间等等信息
查询服务器CPU、内存、磁盘、网络IO、队列、数据库占用空间等等信息
192 2
|
20天前
|
安全 网络协议 算法
网络空间安全之一个WH的超前沿全栈技术深入学习之路(8-1):主动信息收集之ping、Nmap 就怕你学成黑客啦!
网络空间安全之一个WH的超前沿全栈技术深入学习之路(8-1):主动信息收集之ping、Nmap 就怕你学成黑客啦!
|
1月前
|
机器学习/深度学习 存储 分布式计算
未来趋势:探索GraphRAG在大规模异构网络环境下的挑战与机遇
【10月更文挑战第11天】随着互联网和物联网技术的快速发展,数据不仅数量庞大,而且类型多样,形成了复杂的大规模异构网络。这些网络中包含了不同类型的节点(如文本、图像、视频等)以及它们之间的多种关系。如何有效地处理这种大规模异构网络,以便进行内容理解与生成,是当前研究的一个热点问题。Graph Retrieval-Augmented Generation (GraphRAG) 框架作为一种新兴的方法,在这一领域展现出了巨大的潜力。本文将深入探讨GraphRAG的基础理论、构建方法,并分析其在未来大规模异构网络环境下的挑战与机遇。
103 3
|
1月前
|
机器学习/深度学习 计算机视觉
TPAMI 2024:计算机视觉中基于图神经网络和图Transformers的方法和最新进展
【10月更文挑战第3天】近年来,图神经网络(GNNs)和图Transformers在计算机视觉领域取得显著进展,广泛应用于图像识别、目标检测和场景理解等任务。TPAMI 2024上的一篇综述文章全面回顾了它们在2D自然图像、视频、3D数据、视觉与语言结合及医学图像中的应用,并深入分析了其基本原理、优势与挑战。GNNs通过消息传递捕捉非欧式结构,图Transformers则结合Transformer模型提升表达能力。尽管存在图结构构建复杂和计算成本高等挑战,但这些技术仍展现出巨大潜力。论文详细内容见:https://arxiv.org/abs/2209.13232。
51 3
|
19天前
|
机器学习/深度学习 计算机视觉 网络架构
【YOLO11改进 - C3k2融合】C3k2融合DWRSeg二次创新C3k2_DWRSeg:扩张式残差分割网络,提高特征提取效率和多尺度信息获取能力,助力小目标检测
【YOLO11改进 - C3k2融合】C3k2融合DWRSDWRSeg是一种高效的实时语义分割网络,通过将多尺度特征提取方法分解为区域残差化和语义残差化两步,提高了多尺度信息获取的效率。网络设计了Dilation-wise Residual (DWR) 和 Simple Inverted Residual (SIR) 模块,分别用于高阶段和低阶段,以充分利用不同感受野的特征图。实验结果表明,DWRSeg在Cityscapes和CamVid数据集上表现出色,以每秒319.5帧的速度在NVIDIA GeForce GTX 1080 Ti上达到72.7%的mIoU,超越了现有方法。代码和模型已公开。