«上一篇
 文章快速检索 高级检索

 智能系统学报  2019, Vol. 14 Issue (6): 1233-1242  DOI: 10.11992/tis.201905045 0

### 引用本文

ZHANG Lei, QIAN Feng, ZHAO Shu, et al. Network representation learning based on multi-granularity structure[J]. CAAI Transactions on Intelligent Systems, 2019, 14(6): 1233-1242. DOI: 10.11992/tis.201905045.

### 文章历史

1. 安徽大学 计算机科学与技术学院，安徽 合肥 230601;
2. 铜陵学院 数学与计算机学院，安徽 铜陵 244061

Network representation learning based on multi-granularity structure
ZHANG Lei 1,2, QIAN Feng 1,2, ZHAO Shu 1, CHEN Jie 1, ZHANG Yanping 1, LIU Feng 1
1. School of Computer Science and Technology, Anhui University, Hefei 230601, China;
2. School of Mathematics and Computer Science, Tongling University, Tongling 244061, China
Abstract: The Graph Convolution Network (GCN) can adapt to graphs with different structures. However, most GCN-based models have difficulty effectively capturing the high-order similarity of the network. Simply adding a convolution layer will cause the output features to be too smooth and difficult to distinguish. Moreover, the deep neural network is more difficult to train. In this paper, multi-granularity structure and a GCN are combined to represent the node characteristics of the learning network. A multi-granularity structure-based network representation learning method, Multi-GS, is proposed. First, based on the idea of modularity clustering and granular computing, hierarchical multi-granularity space was used to replace the original single-layer network topology space. The GCN model was then used to learn the representation of granules in different coarse- and fine-granularity spaces. Finally, representations of the different grains were combined into representations of nodes in the original space from coarse to fine. Experimental results showed that multi-GS can capture a variety of structural information, including first-order and second-order similarity, intra-community similarity (high-order structure), and inter-community similarity (global structure). In most cases, using multi-granularity structure can improve the classification performance of node classification tasks.
Key words: network represent learning    network topology    modularity increment    network coarsening    multi-granularity structure    Graph Convolution Network    node classification    link prediction

1 问题定义

 $Q = \frac{1}{{2m}}\sum\limits_{c \in C} {\left( {\frac{{l_c}}{{2m}} - {{\left( {\frac{{D_c}}{{2m}}} \right)}^2}} \right)}$ (1)

 $\begin{gathered} \Delta Q_{pq} = Q_k - Q_p - Q_q = \\ \displaystyle \frac{{{{\left( {l_p + l_q} \right)}^2}}}{{2m}} - {\left( {\frac{{D_p + D_q}}{{2m}}} \right)^2} - \frac{{l_p}}{{2m}} + {\left( {\frac{{D_p}}{{2m}}} \right)^2} - \\ \displaystyle \frac{{l_q}}{{2m}} + {\left( {\frac{{D_q}}{{2m}}} \right)^2} = \frac{{l_p}}{{2m}} + \frac{{l_{pq}}}{m} + \frac{{l_q}}{{2m}} - {\left( {\frac{{D_p}}{{2m}}} \right)^2} - \\ \displaystyle \frac{{D_pD_q}}{{2{m^2}}} - {\left( {\frac{{D_q}}{{2m}}} \right)^2} - \frac{{l_p}}{{2m}} + {\left( {\frac{{D_p}}{{2m}}} \right)^2} - \frac{{l_q}}{{2m}} + {\left( {\frac{{D_q}}{{2m}}} \right)^2} = \\ \displaystyle \frac{{l_{pq}}}{m} - \frac{{D_pD_q}}{{2{m^2}}} \\ \end{gathered}$ (2)

 Download: 图 1 网络拓扑的粒化分层示例 Fig. 1 An example of hierarchical view of network topology

2 网络表示学习方法Multi-GS

Multi-GS首先基于模块度构建多粒度的网络分层结构；接着使用GCN模型依次学习不同粒层中所有粒的特征向量；然后自底向上逐层对粒的特征向量进行映射、拼接；最后输出最终的结果作为初始网络中节点的特征表示，如图2所示。

2.1 基于模块度的网络粒化分层

1)level = 0；

2)granuleGraph = copy_Graph(G)；/*复制图结构*/

3)Qnew=modularity()；/*按式(1)计算模块度*/

4)repeat

5) ${\rm{Gr}}{^{\left( {\rm level} \right)}}\leftarrow {\rm{add_Graph}}({\rm granuleGraph})$

6) $C \leftarrow \left\{ {{C_i}| {{v_i} \in {\rm granuleGraph}}} \right\}$

7)repeat

8)Qcur= Qnew

9)for each vi in granuleGraph do

10)将粒 ${v_i}$ 从自身所在的集合中移出；

11)for ${v_j}$ in $\Gamma ({v_i})$ do

12)按式(2)计算粒 ${v_i}$ 移入集合 ${C_j}$ 后的模块度增量 $\Delta Q$

13)end for

14)将粒 ${v_i}$ 并入max(∆Q)>0的粒集合；

15)end for

16)Qnew=modularity()；

17)untill (Qcur = Qnew)

18) ${V^*} \leftarrow \left\{ {v_i^*|{\rm{each}}\;{C_i}\;{\rm{in}}\;{\rm granuleGraph}} \right\}$

19) ${E^*} \leftarrow \left\{ {e_{ij}^*|{e_{ij}},{v_i} \in {C_i},{v_j} \in {C_j}\;{\rm{and}}\;{C_i} \ne {C_j}} \right\}$

20) $\displaystyle{W^*} \leftarrow \left\{ {W_{ij}^*|\sum {{w_{ij}}} ,\;{\rm{if}}\;{v_i} \in {C_i}\;{\rm{and}}\;{v_j} \in {C_j}} \right\}$

21) ${\rm granuleGraph} \leftarrow {\rm{Graph}}\left( {{V^*},{E^*},{W^*}} \right)$

22)level = level +1；

23)untill (level>k)

24)return ${\rm{Gr}}{^{(0)}},{\rm{Gr}}{^{(1)}},\cdots,{\rm{Gr}}{^{(k)}}$

2.2 基于图卷积网络的粒特征表示学习

GCN模型的输入是不同分层中的粒关系矩阵 ${{A}}$ ${{A}} \in {{\bf{R}}^{N \times N}}$ 表示同一粒层中粒间的连接关系，其中， $N$ 表示粒的数量。给定粒 $i$ 和粒 $j$ ，则 $A_{ij} = w_{ij}$ $w_{ij}$ 表示粒 $i$ 和粒 $j$ 间的连接权重。首先，利用式(3)计算得到归一化的矩阵 $\widehat {{A}} \in {{\bf{R}}^{N \times N}}$

 $\widehat {{A}} = {{{D}}^{ - \frac{1}{2}}}\widetilde {{A}}{{{D}}^{ - \frac{1}{2}}}$ (3)

 $\mu = f\left( {\widehat {{A}}f\left( {\widehat {{A}}{{W}}_\mu ^{\left( 0 \right)}} \right){{W}}_\mu ^{\left( 1 \right)}} \right)$ (4)
 $\sigma = f\left( {\widehat {{A}}f\left( {\widehat {{A}}{{W}}_\sigma ^{\left( 0 \right)}} \right){{W}}_\sigma ^{\left( 1 \right)}} \right)$ (5)
 ${{Z}} \sim {\cal{N}}\left( {\mu ,\exp (\sigma )} \right)$ (6)
 ${{{A}}^ * } = {\rm{sigmoid}}\left( {{{Z}} * {{{Z}}^{\rm{T}}}} \right)$ (7)

 ${{\cal{L}}_{\rm latent}} = - \left( {\frac{{0.5}}{N}} \right) \cdot {\rm{mean}}\left( {\sum\limits_{i = 1}^d {\left( {1 + 2 \log \left( \sigma \right) - {\mu ^2} - {\sigma ^2}} \right)} } \right)$ (8)

 $\begin{gathered} {\rm{Loss}} = {{A}} \cdot \left[ - \log \left( {{\rm{sigmoid}}\left( {{{{A}}^ * }} \right)} \right) * {{{W}}^{(1)}}\right] + \\ \left( {1 - {{A}}} \right) \cdot \left[ - \log \left( {1 - {\rm{sigmoid}}\left( {{{{A}}^ * }} \right)} \right) \right] \\ \end{gathered}$ (9)
 ${{{W}}^{(1)}} = {{\left( {N \cdot N - \sum\limits_{i = 1}^N {{A_i}} } \right)} \Big/ {\sum\limits_{i = 1}^N {{A_i}} }}$ (10)
 ${{{W}}^{(2)}} = {{N \cdot N} \Big/ {\left( {N \cdot N - \sum\limits_{i = 1}^N {{A_i}} } \right)}}$ (11)
 ${{\cal{L}}_{\rm reconst}} = {{{W}}^{(2)}}{\rm{mean}}\left( {{\rm{Loss}}\left( {{{A}},{{{A}}^ * },{{{W}}^{(1)}}} \right)} \right)$ (12)

 ${\cal{L}} = {{\cal{L}}_{\rm latent}} + {{\cal{L}}_{\rm reconst}}$ (13)
2.3 算法描述

1) ${\rm{Gr}}{^{(0)}},{\rm{Gr}}{^{(1)}},\cdots,{\rm{Gr}}{^{(k)}}\leftarrow {\rm{Graphgranular}}(G)$

2)for m = 0 to k do

3) ${{{Z}}^{\left( {\rm{m}} \right)}} \leftarrow {\rm{GCN}}\left( {{\rm{Gr}}{^{\left( {{m}} \right)}}.{{A}},\Theta } \right)$

4)end for

5)for n = k to 1 do

6) ${{{Z}}^{\left( {{n}} \right)}} \leftarrow {\rm{projection}}\left( {{{{Z}}^{\left( {{n}} \right)}}} \right)$

7) ${{{Z}}^{\left( {{{n}} - 1} \right)}} \leftarrow {\rm{concatenate}}\left( {{{{Z}}^{\left( {{n}} \right)}},{{{Z}}^{\left( {{{n}} - 1} \right)}}} \right)$

8)end for

9)ZZ(0)

10)return Z

3 实验和结果分析

3.1 实验设定

1) 数据集。

2) 对比算法。

DeepWalk[7]：使用随机游走获取节点序列，通过SkipGram方法学习节点表示。

Node2Vec[8]：类似于DeepWalk，但是使用有偏向的随机游走获取节点序列。

GraRep[9]：通过构造 $k$ 步概率转移矩阵学习节点表示，能够保留节点的高阶相似性。

DNGR[11]：使用随机冲浪方法获取节点的高阶相似性，利用深度神经网络学习节点表示。

3) 参数设定。

3.2 节点分类

3.3 链接预测

3.4 可视化

3.5 参数敏感性分析