论文阅读|Info2vec: An aggregative representation method in multi-layer and heterogeneous networks

ゝ一世哀愁。 2022-09-07 03:52 160阅读 0赞

## 论文阅读|Info2vec: An aggregative representation method in multi-layer and heterogeneous networks ##

### 文章目录 ###

*   *  论文阅读|Info2vec: An aggregative representation method in multi-layer and heterogeneous networks
     *   *  Abstract
         *  Introduction
         *  Graph Transformation
         *  Info2vec: aggregation of information
         *   *  Measuring similarity
             *  Nodes sequences
             *  Language model
             *  Info2vec
         *  实验设置
         *  参考资料

### Abstract ###

将多层网络中的节点映射到低维向量在社区检测、节点分类和链路预测等方面有广泛应用。首先将异构网络通过图变换得到聚合网络，根据不同层的网络结构生成潜在的信息链接。然后通过聚合节点的结构、接近度和属性等信息，对聚合网络中不同节点之间的相似度进行综合度量。 基于节点具有的综合相似度值，可以使用边缘渗透方法生成上下文图，它为一些重要的下游工作（如分类、聚类和预测等）提供了基础。

--------------------

### Introduction ###

同一层中的节点，由于其属性不同，可能存在不同的类别。从skip-gram模型发展来的方法有，学习节点的广义表示，然后根据获得的表示向量执行一些下游任务（如分类、聚类、检测等）。

网络中的表征学习侧重于将原始图数据转换为低维向量，同时从结构、接近度和属性等角度保留图的内在属性。这种低维向量允许通过计算来广义理解两个节点之间的相似性，如表示向量之间的欧几里得距离或余弦相似度，以及促进进一步的下游分析。表示向量可以通过使用不同的方法获得，包括降维、矩阵分解和神经网络等。节点嵌入基于随机游走的算法已被广泛使用。

现有表示学习可分为以下三个分支：

*  侧重于接近度的相似性，如deepwalk（该方法在处理稀疏数据、缺失信息和并行计算的情况下具有优势，应用于网络分类和网络检测，但无法使远离根节点但功能相似的节点建立联系）。Node2vec（深度游走的通用版本，能够学习来自同一社区的节点以及共享相似角色的节点的表示）
 *  同时考虑近邻相似性和结构相似性。如struc2vec（计算层次结构中任意两个节点之间的相似度，然后构造一个加权的多层图来生成节点序列，最后使用skip-gram模型来学习潜在表示。该方法需要大量的计算资源，并且无法捕捉到近邻之间的相似性）
 *  归纳学习强调邻居以及高阶邻居的聚合节点的属性。如GraphSAGE（利用节点特征并将它们合并到学习过程中来训练一组聚合器函数，基于这些函数可以生成看不见的节点的嵌入。 通过将邻域信息与节点特征相结合，该方法在预测节点分类或动态图中的角色方面优于传统基线）

Info2vec从结构、接近度和属性的不同角度聚合信息，以实现更准确的预测。其`贡献`有：

*  通过聚合来自不同层的信息将多层异构网络转换为单层网络的方法，使得焦点层上的节点可以与来自支持层的信息很好地连接。
 *  通过考虑领域相似性、结构相似性和属性相似性来引入广义表示学习框架，以通过向量表示节点。所提出的框架优于一些传统的基线方法

--------------------

### Graph Transformation ###

多层异构图表示为 G L = ( L , E ) G^L=(L,E) GL=(L,E)，其中 L = \{ G 1 , G 2 , . . . , G m \} L=\\\{G\_1,G\_2,...,G\_m\\\} L=\{ G1,G2,...,Gm\}表示层集。在单层 G k = ( V k , E k , A k ) G\_k=(V\_k,E\_k,A\_k) Gk=(Vk,Ek,Ak)中，包含节点集 V k = \{ v 1 k , v 2 k , . . . , v n k \} V\_k=\\\{ v\_1^k,v\_2^k,...,v\_n^k \\\} Vk=\{ v1k,v2k,...,vnk\}，边集 E k = \{ e i j k \} E\_k= \\\{ e\_\{ij\}^k \\\} Ek=\{ eijk\}，节点 v i k v\_i^k vik和节点 v j k v\_j^k vjk通过边 e i j k e\_\{ij\}^k eijk连接。

令 ϕ k : v i k ∈ V k → θ i k ∈ A k \\phi \_k : v\_i^k ∈ V\_k → \\theta \_i^k ∈ A\_k ϕk:vik∈Vk→θik∈Ak表示 G k G\_k Gk层的节点 v i k v\_i^k vik具有属性 θ i k \\theta \_i^k θik，其中 θ i k = \[ θ i , 1 k , . . . , θ i , t k \] \\theta\_i^k = \[\\theta\_\{i,1\}^k,...,\\theta\_\{i,t\}^k\] θik=\[θi,1k,...,θi,tk\]。

令 E = \{ E 12 , E 13 , . . . , E k f , . . . \} E=\\\{E\_\{12\},E\_\{13\},...,E\_\{kf\},...\\\} E=\{ E12,E13,...,Ekf,...\}表示两层之间的连接。例如 E k l E\_\{kl\} Ekl表示层 G l G\_l Gl和层 G k G\_k Gk之间的连接，节点 v i k v\_i^k vik和节点 v j l v\_j^l vjl间的连接边表示为 e i j k l e\_\{ij\}^\{kl\} eijkl。

下图是论文中展现的多层异构图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

在多层异构网络中，了解支持层中结构或连接的基本信息有助于更好地理解焦点层上的活动。为准确捕获焦点层中节点的身份，需要采取措施聚合来自支持层的信息。实施图转化，将焦点层扩展为聚合网络，将焦点层的信息与支持层的信息相结合。聚合网络应包含焦点层中的所有现有边，以及一些新添加的链接。

考虑到不同网络层链路之间的相互依赖性，焦点层中的两个节点在支持层中具有共同邻居或连接到支持层中的某个边的情况下，在焦点层上更可能有密切的交互。具体来说，对于在焦点层原本没有连接的两个节点，对于以下两种不同的情况，它们之间需要在汇聚网络中建立一条新的链路：

*  三角形连接
 *  四边形连接

由论文中图可见：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

在聚合网络中，节点之间的边比焦点层中的边更密集，聚合的信息更多。图转换后的结果如下所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]

--------------------

### Info2vec: aggregation of information ###

#### Measuring similarity ####

论文采用的三种相似性度量

*  `Nearness similarity`（邻近相似性）  
     S n ( u , v ) = e α ( − l ( u , v ) + 1 ) S\_n(u,v)=e^\{\\alpha(-l(u,v)+1)\} Sn(u,v)=eα(−l(u,v)\+1)  
    取值范围为\[0,1\]， α \\alpha α是为了减少因节点u和节点v间最短路径 l ( u , v ) l(u,v) l(u,v)所带来的衰减。
 *  `Structural similarity`（结构相似性）
    
    采用动态时间扭曲（DWT）来测量两个节点之间的结构距离。  
     f k ( u , v ) = f k − 1 ( u , v ) ＋ g ( s ( R k ( u ) ) , s ( R k ( v ) ) ) f\_k(u,v)=f\_\{k-1\}(u,v)＋g(s(R\_k(u)),s(R\_k(v))) fk(u,v)=fk−1(u,v)＋g(s(Rk(u)),s(Rk(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)))表示s的第k跳邻居和v的第k跳邻居间有序数序列的距离。且 g ( D 1 , D 2 ) = ∑ d i ∈ D 1 , d j ∈ D 2 △ ( d i , d j ) = ∑ d i ∈ D 1 , d j ∈ D 2 ∣ d i − d j ∣ g(D\_1,D\_2)=\\sum\_\{d\_i∈D\_1,d\_j∈D\_2\}△(d\_i,d\_j)=\\sum\_\{d\_i∈D\_1,d\_j∈D\_2\}|d\_i-d\_j| g(D1,D2)=∑di∈D1,dj∈D2△(di,dj)=∑di∈D1,dj∈D2∣di−dj∣，其中 D 1 和 D 2 D\_1和D\_2 D1和D2是两个节点度数序列， d i 和 d j 分 别 表 示 D 1 和 D 2 d\_i和d\_j分别表示D\_1和D\_2 di和dj分别表示D1和D2中的度值。计算两个节点间的结构相似性公式为：  
     S s ( u , v ) = e − β f k ( u , v ) S\_s(u,v)=e^\{-\\beta f\_k(u,v)\} Ss(u,v)=e−βfk(u,v)  
    其中 β \\beta β是衰减系数。
 *  `Attribute similarity`（属性相似性）
    
    对于节点u和v的属性集 θ u = \[ θ u , 1 , . . . , θ u , t \] \\theta\_u = \[\\theta\_\{u,1\},...,\\theta\_\{u,t\}\] θu=\[θu,1,...,θu,t\]和 θ v = \[ θ v , 1 , . . . , θ v , t \] \\theta\_v=\[\\theta\_\{v,1\},...,\\theta\_\{v,t\}\] θv=\[θv,1,...,θv,t\]，相似值可以表示为如下的t维向量  
     h ( u , v ) = \[ δ 1 ( u , v ) , δ 2 ( u , v ) , . . . , δ t ( u , v ) \] h(u,v)=\[\\delta\_1(u,v),\\delta\_2(u,v),...,\\delta\_t(u,v)\] h(u,v)=\[δ1(u,v),δ2(u,v),...,δt(u,v)\]  
    其中  
     δ i ( u , v ) = \{ 1 , i f θ u , i = θ v , i 0 , i f θ u , i ≠    θ v , i \\delta\_i(u,v)=\\begin\{cases\} 1, \\quad if \\quad \\theta\_\{u,i\}=\\theta\_\{v,i\} \\\\ 0, \\quad if \\quad \\theta\_\{u,i\} \\neq\\; \\theta\_\{v,i\} \\end\{cases\} δi(u,v)=\{ 1,ifθu,i=θv,i0,ifθu,i=θv,i
    
    结构相似性可表示如下：  
     S a u , v = h ( u , v ) W a T S\_a\{u,v\}=h(u,v)W\_a^T Sau,v=h(u,v)WaT  
    其中W代表属性间联系权重。

综合上述三种情况，节点u和节点v间的综合相似性可表示为  
 S ( u , v ) = W n S n ( u , v ) ＋ W s S S ( u , v ) + W a S a ( u , v ) S(u,v)=W\_nS\_n(u,v)＋W\_sS\_S(u,v)+W\_aS\_a(u,v) S(u,v)=WnSn(u,v)＋WsSS(u,v)\+WaSa(u,v)

#### Nodes sequences ####

如何得到节点序列？

根据原始的异构网络计算出节点间的综合相似性S，然后构造完全图，将节点间的综合相似性S设置为对应边的权重W，然后采用边渗透，删除权重小于 δ \\delta δ的边就得到了上下文图。然后在此图上进行随机游走得到相应节点序列，通常设置路径长度 λ \\lambda λ在10左右。此处采用**偏随机游走**（biased random-walk），Node2vec中可见。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 3]

#### Language model ####

skip-gram语言模型

与deepwalk介绍类似

#### Info2vec ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 4]

--------------------

### 实验设置 ###

数据集：网络空间网络

参数设置： W n = 2 , W s = 1 , α = 0.5 , β = 1 , W α = \[ 1 , 0.1 , 0.1 , 0.1 , 0.5 \] , δ = 2 , d = 256 W\_n=2,W\_s=1,\\alpha=0.5,\\beta=1,W\_\{\\alpha\}=\[1,0.1,0.1,0.1,0.5\],\\delta=2,d=256 Wn=2,Ws=1,α=0.5,β=1,Wα=\[1,0.1,0.1,0.1,0.5\],δ=2,d=256

评价指标：JC，FMI，RI，F1

对比算法：DeepWalk，Node2vec，Struc2vec，GraphSAGE

--------------------

### 参考资料 ###

> Info2vec: An aggregative representation method in multi-layer and heterogeneous networks

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/03cd56b3330f48c3878c335d0db80661.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220829/d79a5d9df8bd470eaeae30886e016322.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220829/5a3485e985024193a97f9527e27d9580.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220829/f9ee95484ff843f0b8221bb4bf3fef87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20220829/eddf6b7bc4bd4be39edb04cfbc619da3.png