Graph Embedding模型【Struc2Vec】学习笔记

编程入门行业动态更新时间:2024-10-08 02:21:06

Graph Embedding模型【Struc2Vec】<a href=https://www.elefans.com/category/jswz/34/1770117.html style= 学习笔记"/>

Graph Embedding模型【Struc2Vec】学习笔记

概要

struc2vec模型的基本思想：网络图中的相似结构的节点具有相似性。如图所示，节点u和节点v具有相似的结构，但是它们在图中可能相距很远。struc2vec则利用这种图结构信息训练出节点的隐含信息表示。

struc2vec根据节点在图中的结构信息评估节点的相似性，包含它的边关系、邻接节点的位置、标签等信息。struc2vec模型不要求图是连通图，即若两个节点不连通，只要在网络图中的结构信息相似即可。

构建分层体系测量结构的相似性，允许渐进地对结构上的相似性有更严格的定义。例如，在分层底部，结构相似依赖节点的度，在分层顶部，则依赖整个网络（从节点的角度）。

为节点生成随机的上下文。通过加权随机遍历多层图(而不是原始网络)观察到结构相似的节点序列。因此，经常出现在相似上下文中的两个节点可能具有相似的结构。语言模型可以利用这种上下文来学习节点的潜在表示。

Struc2Vec模型

Struc2Vec的两个目标：

两个节点的表示向量的距离和两个节点的结构相似有很强的关联，不同结构的两个节点的距离应该尽可能远。
节点的向量表示和任何节点以及节点标签和边的属性没有关系。

Struc2Vec模型分为四个主要步骤：

对于不同的邻域大小，确定图中每个顶点对之间的结构相似性。在节点之间的结构相似度度量中引入了一个层次结构，提供了更多的信息来评估层次结构的每个级别的结构相似度。
构造一个加权的多层图，其中网络中的所有节点都呈现在每一层中，每一层对应于层次结构的一个层次来度量结构相似性。并且各层内每个节点对之间的边权值与其结构相似性成反比。
使用多层图为每个节点生成上下文。特别地，在多层图上使用有偏随机游走来生成节点序列。这些序列可能包括结构更相似的节点。
应用一种技术来学习由节点序列所给出的上下文的潜在表示，例如Skip-Gram。

如何计算节点的结构相似度

模型的第一步就是计算节点之间的结构相似度。论文引入分层结构计算两个节点之间的结构相似度，具体的： f k ( u , v ) = f k − 1 ( u , v ) + g ( s ( R k ( u ) ) , s ( R k ( v ) ) ) （式 1 ） f_k(u,v)=f_{k-1}(u,v)+g(s(R_k(u)), s(R_k(v))) \space\space\space\space（式1） fk(u,v)=fk−1(u,v)+g(s(Rk(u)),s(Rk(v))) （式1）其中 k ⩾ 0 k\geqslant 0 k⩾0并且 ∣ R k ( u ) ∣ , ∣ R k ( v ) ∣ > 0 |R_k(u)|,|R_k(v)| > 0 ∣Rk(u)∣,∣Rk(v)∣>0。 g ( D 1 , D 2 ) ≥ 0 g(D_1,D_2)\ge 0 g(D1,D2)≥0表示节点的有序度序列 D 1 D_1 D1， D 2 D_2 D2之间的距离，且 f − 1 = 0 f_{-1}=0 f−1=0。当节点 u u u和 v v v的 k k k阶邻接节点是同构的，则 f k − 1 ( u , v ) = 0 f_{k-1}(u,v)=0 fk−1(u,v)=0。

可知（式1）是一个递归式， f − 1 = 0 f_{-1}=0 f−1=0，想要求 f k ( u , v ) f_k(u,v) fk(u,v)，则需要求出 g ( s ( R k ( u ) ) , s ( R k ( v ) ) ) g(s(R_k(u)), s(R_k(v))) g(s(Rk(u)),s(Rk(v)))，即节点 u u u和 v v v的有序度序列之间的距离。因为节点 u u u和 v v v的k阶邻接节点的个数可能不一样，导致它们的有序度序列长度也可能不一样，所以论文采用动态时间规整(Dynamic Time Warping，简称DWT)计算。

对于序列中元素之间的距离论文中采用 d ( a , b ) = m a x ( a , b ) m i n ( a , b ) − 1 d(a,b)=\frac{max(a,b)}{min(a,b)}-1 d(a,b)=min(a,b)max(a,b)−1其中 a a a属于节点 u u u的有序度序列中的元素， b b b属于节点 v v v的有序度序列中的元素。例如度为1和2的差异为 2 1 − 1 = 1 \frac{2}{1}-1=1 12−1=1，而度为101和102的差异为 102 101 − 1 = 0.0099 \frac{102}{101}-1=0.0099 101102−1=0.0099，它们的结果是符合我们预期的。这个距离函数的定义可以根据特定的需求自己定义。

构造多层带权图

构建多层带权图的目的是为了编码节点之间的结构相似度。

论文定义每一层 k ∈ ( 0 , 1 , . . , k ∗ ) k\in(0,1,..,k^*) k∈(0,1,..,k∗)节点之间的权重为 w k ( u , v ) = e − f k ( u , v ) , k = 0 , 1 , . . , k ∗ w_k(u,v)=e^{-f_k(u,v)},k=0,1,..,k^* wk(u,v)=e−fk(u,v),k=0,1,..,k∗根据（式1）可知， f k ( u , v ) ≥ 0 f_k(u,v) \ge 0 fk(u,v)≥0，则 w k ( u , v ) ∈ ( 0 , 1 ] w_k(u,v) \in (0, 1] wk(u,v)∈(0,1]。当且仅当节点的距离为0（即 f k ( u , v ) = 0 f_k(u,v)=0 fk(u,v)=0）时边权重等于1。同一层节点之间的边是无向的。

不同层次上的同一顶点论文中使用有向边进行连接。则每一层 k k k中的每个节点 u u u都和该节点 u u u在上一层( k − 1 k-1 k−1)和下一层( k + 1 k+1 k+1)进行连接。其边的权重定义为： w ( u k , u k + 1 ) = l o g ( Γ k ( u ) + e ) , k = 0 , 1 , . . . , ( k ∗ − 1 ) w(u_k,u_{k+1})=log(\Gamma_k(u)+e),k=0,1,...,(k^*-1) w(uk,uk+1)=log(Γk(u)+e),k=0,1,...,(k∗−1) w ( u k , u k − 1 ) = 1 w(u_k,u_{k-1})=1\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space w(uk,uk−1)=1 其中 Γ k ( u ) \Gamma_k(u) Γk(u)是第 k k k层与节点 u u u相连的边的权重大于第 k k k层所有边权重平均值的边的数量。其公式为 Γ k ( u ) = ∑ v ∈ V 1 ( w k ( u , v ) > w k ‾ ) \Gamma_k(u)=\sum_{v\in V}1(w_k(u,v)> \overline {w_k}) Γk(u)=v∈V∑1(wk(u,v)>wk)其中 w ‾ k \overline w_k wk是第 k k k层所有边权的平均值， w ‾ k = ∑ ( u , v ) w k ( u , v ) n \overline w_k=\frac{\sum_{(u,v)} w_k(u,v)}{n} wk=n∑(u,v)wk(u,v)， n n n为 k k k层边的数量。

构建节点序列

上一步构造了多层图，计算了节点间的结构相似度（仅仅依赖于节点的度，不包含节点任何的标签信息），构造节点序列论文采用的是有偏随机游走策略，根据多层图的边权重随机游走的概率。而在每一步游走之前需要先判断是否需要改变当前层游走，这个判断是根据一个概率 q q q，（论文中并没有将这个概率是超参还是训练得到）。

当概率 q > 0 q>0 q>0，随机游走保留着当前层，并且从节点 u u u到 v v v的游走概率为： p k ( u , v ) = e − f k ( u , v ) Z k ( u ) p_k(u,v)=\frac{e^{-f_k(u,v)}}{Z_k(u)} pk(u,v)=Zk(u)e−fk(u,v)其中 Z k ( u ) Z_k(u) Zk(u)为归一化因子， Z k ( u ) = ∑ v ∈ V , v ≠ u e − f k ( u , v ) Z_k(u)=\sum_{v \in V,v \not = u}e^{-f_k(u,v)} Zk(u)=∑v∈V,v=ue−fk(u,v)。有概率公式可知，游走会更加偏向结构相似的节点。

当概率 q < 0 q<0 q<0,随机游走会改变层进行游走，而改变到 ( k − 1 ) (k-1) (k−1)层还是 ( k + 1 ) (k+1) (k+1)层，则根据节点 u k u_k uk到 u k − 1 u_{k-1} uk−1、 u k + 1 u_{k+1} uk+1的概率决定： p k ( u k , u k + 1 ) = w ( u k , u k + 1 ) w ( u k , u k + 1 ) + w ( u k , u k − 1 ) p_k(u_k,u_{k+1})=\frac{w(u_k,u_{k+1})}{w(u_k,u_{k+1})+w(u_k,u_{k-1})} pk(uk,uk+1)=w(uk,uk+1)+w(uk,uk−1)w(uk,uk+1) p k ( u k , u k − 1 ) = 1 − p k ( u k , u k + 1 ) p_k(u_k,u_{k-1})=1-p_k(u_k,u_{k+1}) \quad\quad\quad\quad\space\space pk(uk,uk−1)=1−pk(uk,uk+1)

语言模型

在上一步中构建了节点的序列之后，便是利用节点序列训练生成节点的向量表示。论文采用的是Skip-Gram模型。

对模型复杂度的优化

1、减少有序度序列的长度
虽然在 k k k层的有序度序列界限为 m i n ( d m a x k , n ) min(d^k_{max},n) min(dmaxk,n)，其中 d m a x k d^k_{max} dmaxk表示第 k k k层的最大度数，但是对于某些图来说，即使 k = 3 k=3 k=3，其空间复杂度为 O ( n ) O(n) O(n)。论文的解决方案是对序列进行压缩存储，统计每个序列中度数出现的次数，形成**（度数、出现次数）**的二元组，因为网络中有很多相同度数的节点。然后修改DTW距离计算函数 d i s t ( a , b ) = ( m a x ( a 0 , b 0 ) m i n ( a 0 , b 0 ) − 1 ) m a x ( a 1 , b 1 ) dist(a,b)=\bigg( \frac{max(a_0,b_0)}{min(a_0, b_0)}-1\bigg)max(a_1,b_1) dist(a,b)=(min(a0,b0)max(a0,b0)−1)max(a1,b1)其中 a 0 , b 0 a_0,b_0 a0,b0为度数， a 1 , b 1 a_1,b_1 a1,b1 为度的出现次数。

2、减少节点对相似度计算的次数
原框架中每一层中的任意两个节点对都需要计算其结构相似度。然而两个不同度数的节点（如度数为2和20）即使 k = 0 k=0 k=0其机构相似距离也很大，因此最后得到的边的权重很小。故这种节点对的相似度计算是没有意义。

论文给的方案是只计算节点度数接近的节点对 ( u , v ) (u,v) (u,v)的相似度，如何找到节点 u u u度数接近的节点 v v v？在对应节点 u u u的有序度序列中使用二分查找获取度数接近的节点。这个过程的时间复杂度为 O ( l o g n ) O(logn) O(logn)，所以总的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。

3、减少多层图的层数
多层图的层数由原图谱的“直径” k ∗ k^* k∗决定，对很多图来说，图的直径会远远大于顶点之间的平均距离。当层数 k k k接近“直径” k ∗ k^* k∗时，环上的度序列长度相对变短了，因此 f k ( u , v ) f_k(u,v) fk(u,v)和 f k − 1 ( u , v ) f_{k-1}(u,v) fk−1(u,v)也变得更接近了。故将层数 k ′ k' k′限制在 k ′ < k ∗ k'<k^* k′<k∗。使用最重要的一些层来评估结构相似度。