网络表示学习：SeqNE（AAAI 2019）论文解读

摘要

在大规模网络上，人们已经提出了许多成功的低维表示学习方法，而现有的方法几乎都是在不可分割的过程中设计的，即使只有一小部分节点感兴趣，也可以学习整个网络的嵌入。这会带来极大的不便，特别是在超大或动态网络上，这些方法几乎不可能实现。本文对分离矩阵分解问题进行了形式化描述，在此基础上提出了一种新的既能保持局部 信息 又能保持全局信息的目标函数。我们进一步提出了一种简单灵活的网络嵌入算法SepNE，它可以独立地学习分离过程中不同节点子集的表示。通过实现可分离性，减少了嵌入无关节点的不可继承性，产生了对超大网络的可扩展性，在分布式学习中的自动实现和进一步的适应性。

idea  

能否在保留整个网络信息的同时，分别学习与总体相比非常小的不同节点子集的表示？
主要解决大规模网络的嵌入效率问题（百万级别的数个小时。十亿级别的上千个小时，这是不可以接受的）

   本文在基于矩阵分解（后面记录）的框架下实现了NE问题的可分离性。

分离矩阵分解（Separated Matrix Factorization）

矩阵分解:

给定一个矩阵M，矩阵因子分解（MF）的目标是找到两个矩阵W和C都满足给定的约束条件，并使重建M时的残差最小化（M′'′=WT^TTC）。用公式表示:


   在一个具有n个节点的图嵌入任务中，M的大小为n×n。M的值为节点之间的相近程度，可以用多种度量定义（边的权重、连接关系等等）

SMF定义

给定一个网络G = (V，E)，丨V丨=n，邻近矩阵M，和一个分区设置f：V→V ’，V ’={V1，···，Vs}作为输入，任务是得到相应的W和C矩阵表示——（W1，····，Ws）和（C1，···，Cs）为了重构最优的M(损失同公式（1）一样)。

分区限制

给定顶点Vi_ii​，在M中，只将Mi_ii​j_jj​和Mj_jj​i_ii​分在一起。

方法

Local   information.

局部信息是指每个集合内或对角上的子矩阵的邻近度。
目的：给定节点集中的邻近度

建模SMF

通过分解对角线上的s矩阵，只保留局部信息：

Landmark information

Landmark信息表示子集和手动建立的路标之间的距离，Landmark是一组特殊的节点（表示为V0_00​），被选作为不同子集的参考。
目的：给定节点集与所选地标之间的接近度

   分两个阶段求解：


   第一个阶段（2）嵌入地标（W0_00​=Φ，C0_00​=ψ），

   第二阶段通过求解公式（3）得到剩余集的表示，并计算出Φ和ψ。

   （3）中的损失可以明确分解为局部损失和地标损失，如下所示
、

Global information.

目的：两个给定节点集之间的接近度


   全局信息：


   损失：


   正则化：

整体理解

损失

SepNE

Partition Setups

1. SepNE-RP（Random Patition）将节点随机分配给集合
2. SepNE-IO（仅感兴趣）将请求的节点放入一个或多个集合中，忽略所有未请求的节点。

Landmark Selection

贪心算法

   使用GDS，首先使用节点的度数形成一个最大堆，并将landmark集初始化为空。初始化后，GDS迭代检查堆的顶部。如果被当前地标集控制，则只需移除顶部，否则添加到集合中，然后移除。这个过程一直持续到堆为空或大小达到k。

Experiments

数据集（Available at http://socialnetworks.mpi-sws.

org/datasets.html）

多标签分类任务：

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删