找人做网站被骗怎么办,泰州网站建设设计,网页制作软件工具,仿站工具下载后咋做网站需要论文的朋友可以后台私信我获取前言上一篇文章给大家带来了Graph Embedding技术中的代表算法Deepwalk#xff0c;今天给大家介绍graph embedding又一代表算法——LINE,LINE(large-scale information Network#xff0c;大规模信息网络)致力于将大型的信息网络嵌入到低维的…需要论文的朋友可以后台私信我获取前言上一篇文章给大家带来了Graph Embedding技术中的代表算法Deepwalk今天给大家介绍graph embedding又一代表算法——LINE,LINE(large-scale information Network大规模信息网络)致力于将大型的信息网络嵌入到低维的向量空间中且该模型适用于任何类型(有向、无向亦或是有权重)的信息网络。并提出了一种解决经典随机梯度下降限制的边缘采样算法提高了算法的有效性和效率,且在应用方面更广。总结下来LINE有以下几个特点或者优势(1)适用广适合任意类型的网络不论是有向图还是无向图还是带权图。(2)信息全目标函数(objective function)同时考虑了网络局部特征和全局特征。(3)效率高提出一种边采样的算法可以很好地解决SGD的效率问题。(4)时间快提出了十分高效网络表示方法在小时范围内的单机节点上学习百万级顶点网络的表示。下面一下来看看这篇文章吧。重要定义了解LINE算法之前需要了解一下论文里面的几个重要概念。信息网络信息网络定义为 G(V,E)其中V 是顶点集合顶点表示数据对象 E 是顶点之间的边缘的集合每条边表示两个数据对象之间的关系。每条边e(E)表示为有序对e(u,v)并且与权重Wuv0相关联权重表示关系的强度。如果G是无向的我们有 (u,v) !(v,u)和WuvWvu 如果G是有向的我们有(u,v) !(v,u) 和Wuv!Wvu,一般情况下我们认为权重非负。一阶相似性网络中的一阶相似性是两个顶点之间的局部点对的邻近度。对于有边(u,v) 连接的每对顶点该边的权重Wuv 表示u 和v之间的一阶相似性如果在u 和v之间没有观察到边他们的一阶相似性为0。二阶相似性二阶相似性指的是一对顶点之间的接近程度(u,v) 在网络中是其邻域网络结构之间的相似性。数学上让表示一阶附近与所有其他的顶点那么u和v之间的二阶相似性由pu和pv之间的相似性来决定。如果没有一个顶点同时和u与v 连接那么u和v 的二阶相似性是0。大规模信息网络嵌入给定大网络 G(V,E)大规模信息网络嵌入是将每个顶点v(V) 表示为低维空间(d)中的向量学习一个函数:其中d以上图为例一阶相似性表示两个顶点直接相连比如6和7两个顶点它们就是相似的二阶相似表示两个两个顶点有相同的连接顶点比如5和6虽然不直接连接但是同时和1,2,3,4相连所以5和6是相似的这和协同过滤是不是很像说白了就是根据图结构来表达顶点间的相似度。算法介绍一阶相似性对每个无向边(i,j)定义顶点vi和vj的联合概率分布为ui(d维)是顶点vi的低维向量表示为保持其一阶相似性p(,)为空间VxV上的一个分布W为ij两点间边权重总和。为了求解一阶相似直接方法是最小化以下的目标函数d(.,.)为两种分布之间的距离我们选择尽量减少两个概率分布的KL 散度。将d(,)替换为 KL 散度并省略一些常数我们得到︰注意一点一阶相似度仅适用于无向图,而不适用于有向图。二阶相似性二阶相似性适用于有向或者无向图(比如Deepwalk里面就用到了有向的二阶相似性)二阶相似性假定与其他顶点共享邻居顶点的两个点彼此相似(无向有向均可)一个向量u和u分别表示顶点本身和其他顶点的特定“上下文”意为二阶相似。对于每个有向边(i,j)我们首先定义由生成“上下文”的概率其实这和word2vec里面的公式是一样的代表一个条件分布我们取i为研究对象p(,vi)降维之后使其接近与经验分布p2。因此最小化以下目标函数d(,)和一阶里面定义一致表示两个分布的距离λi来表示网络中顶点i的声望(可以理解为权重),在本文中即是顶点i的度数因此二阶相似性的计算公式为最后将得到一阶相似向量和二阶相似向量直接拼接在一起得到最终的节点向量。模型优化由于O2的计算代价十分的昂贵因此目标函数优化时使用了负采样方法为每条边指定了一个目标函数注就是sigmoid函数K表示负采样边的个数其中dv是顶点v的出度(和词向量里面的几乎是一样的)。上述函数又可通过采用异步随机梯度下降算法(ASGD)来优化。每一步中ASGD算法对小批量边缘进行抽样然后更新模型参数。但是这也带来一个问题如果我们根据小权重的边缘选择较大的学习率那么大权重的边上就会出现梯度爆炸如果我们根据具有较大权重的边选择学习小的速率那么小权重上的边就会出现梯度消失。因此边缘采样同样要优化。从起始边缘采样并将采样的边缘作为二进制边缘其中采样概率与原始边缘的权重成比例。实验分析与展示与Deepwalk中的实验类似。数据集语言网络基于英文维基百科页面构建词共同网络社交网络Flickr、Youtube引用网络作者和论文引文网算法GFDeepwalkLINE-SGDLINELINE (1st2nd):参数设置对于所有方法随机梯度下降的小批量大小设置为1以起始值p0 0.025和pt p0(1-t)设定学习速度 T是小批量或边缘样品的总数为了公平比较语言网络嵌入的维度被设置为200而其他网络中默认设置为128其他的默认参数设置包括LINE的负采样k5样本总数T100亿(LINE),T200亿(GF)窗口大小win 10步行长度t 40对于Deep Walk每顶点行走y 40所有的嵌入向量最终通过设置 ||w||2 1进行归一化。语言网络评估学习嵌入的有效性词类比和文档分类。词类比给定一个单词对(a,b)和一个单词c该任务旨在找到一个单词d使得c和d之间的关系类似于a和b之间的关系。由实验结果可看出LINE(2nd)优于其他模型相比于其他算法LINE的二阶相似性可以更好的衡量词在空间中的关系。这个算法我没有使用过对于这个实验结果我表示怀疑。由上表可以看出LINE模型在文档分类上效果强于其他模型。上表比较一阶相似性和二阶相似性之间的效果。由表可以看出一阶相似体现的是与目标词句法和语义相关词的混合。二阶相似返回的是目标词对应的所有语义相关词。社交网络与语言网络相比社交网络更加稀缺将每个节点分配到一个或多个社区的多标签分类任务来评估顶点嵌入随机抽取不同百分比的顶点进行训练其余用于评估。结果在10次不同运行中进行平均。下面是在Flickr和Youtube数据集上的结果展示。引用网络通过GF和LINE两种方法对引用网络进行评估。还通过多标签分类任务评估顶点嵌入。 我们选择7个流行会议包括AAAICIKMICMLKDDNIPSSIGIR和WWW作为分类类别。训练结果模型效果 网络稀疏度参数分析从低维向量维度个训练样本数来展示不同模型效果总体来说LINE(2nd)好于其他。稳定性这些图说明了一点LINE算法很好很稳定好于Deepwalk等同类型算法。总结看这篇论文给我一种感觉是有一些很好的地方比如一阶、二阶相似性等但是效果不应该这么大可能是有一些工程经验文章没有说或者是我还是体会到总结下来就是LINE是以图的结构(边)来构造样本并没有Deepwalk里面随机游走等方式构造序列这种思想还是有很大的创新性的。
