Exploring Evolution of Dynamic Networks via Diachronic Node Embeddings

• 论文原文：Exploring Evolution of Dynamic Networks via Diachronic Node Embeddings
• 作者：Jin Xu, Yubo Tao, Yuyu Yan, and Hai Lin
• 发表刊物/会议：2018 TVCG

文章提出了一种利用graph embedding的方法来探索动态图的方法。

一般而言，传统的动态图可视化方法可以分成三大类，基于动画的方法（animation），基于时间轴的方法（timeline），以及其他方法（如投影 projection）。基于动画的方法，往往会高亮相邻两帧之间的变化，但是当时间比较长的时候无法追踪变化；基于时间轴的方法，则将所有内容一起显示在同个视图中，但空间是个问题；基于投影的方法，把每一帧当做一个点，用投影的方法投影在一个视图中，但是很难展现图的结构的信息；

文章提出了一种同时展示结构属性和动态属性的可视分析方法。具体步骤如下：

A生成动态图，B为动态图每一帧的每个节点生成embedding向量，C将这些embedding向量对齐到同一向量空间中，DEF利用embedding向量可以做的数据挖掘（节点分类，节点聚类，动态轨迹聚类），G可视交互分析；

文章的主要贡献有：

1. 提出了一种新的节点embedding的方法
2. 提出了两种基于节点embedding的动态图聚类方法
3. 一个可视分析交互系统

动态图的构建

首先，将动态图按照$\Delta t$的时间间隔，划分成多个时间片段，然后将$[t_i-\omega/2, t_i+\omega/2)$作为$t_i$时刻对应的动态图。

节点embedding向量的生成

文章利用了skip-gram模型为单帧图的每一个节点生成embedding向量；

skip-gram模型可以理解为，当你输入一系列句子（sentences），以及包含这些句子中的词的语料库（corpus），skip-gram模型会为你预测语料库中的单词出现在某个指定的单词（word）附近的概率；这个过程中，会有一个重要的产物，叫做词向量，利用两个词向量的内积，我们就可以看到两个词在句子中共同出现的概率有多高；

skip-gram模型的目标函数，可以看做在最大化，同个句子中的相邻词汇的词向量的内积。

文章同样利用了skip-gram模型，做了如下修改：

用节点（node）替代词（word），用路径（path）替代句子（sentence），用节点集合（nodes set）代替语料库（corpus），于是也可以产生节点向量。

值得注意的有：

1. path的生成，靠的是random walk，假如图是一个有权图（weighted），那么random walk也需要依赖边权重。并且，为了提高效率，文章使用了负采样。

2. skip-gram模型的目标函数的修改。这里不仅仅要使得同一路径上的节点出现概率高，还要使得不相邻的节点共同出现的概率低：

   

3. 将上一帧产生的embedding向量，传入下一帧的skip-gram模型中，用以保持两帧之间的连续性：

   

embedding向量对齐

为了使得所有的embedding向量能够对齐到同一个向量空间中，方便比较和计算。所以这一步要对embedding向量进行正交变换，使得下面这个矩阵范数最小（也即差异最小）：

$$

\left|M_{i} \Omega-M_{b}\right|_{F}

$$

其中$M_i$表示第$i$帧的向量构成的矩阵（$n \times d$）；$\Omega$指的是正交变换矩阵；$M_b$指的是基准矩阵，也就是所有embedding向量都要对齐到这个基准矩阵上来；$\left|*\right|_{F}$则是Frobenius矩阵范数。

关于$M_b$的选取，有三种不同的方法：

1. 对齐到节点数最多的一帧（适合于变化较小的动态图）
2. 对齐到前一帧（因为两帧之间的变化不大，所以误差会较小，但是不断对齐的过程中，误差就会累计）
3. 将所有帧分成好几段，每一段都对齐到其中的某一帧（解决了上面的问题）

节点分类和聚类

1. 节点的分类：

   根据前后两帧之间节点embedding的变化，可以判断这个节点是dynamic（动态）还是stable（稳定）。

   当前后两帧的节点之间的欧氏距离（文中叫做evolution value）,大于阈值$\theta$时，则认为其为dynamic；

2. 节点聚类：

   可以用于揭示某一段时间内，稳定的社团结构。文章提出了稳定的概念，也就是大部分节点在这段时间内维持一个stable的状态。那么，在一段稳定时间内，将同一节点不同时间的所有向量求均值，就作为这段时间内该节点的向量。然后利用这些节点进行k-means聚类，即可得到不同的聚类（社团）。

3. 趋势聚类：

   如何对节点随时间变化的趋势进行聚类。两个节点随时间演化产生的两条轨迹，可以利用如下方法判断距离：

   

   同一时刻，两个节点的向量求欧氏距离；所有时刻的所有欧氏距离的平均值，作为两条轨迹的距离。

   利用knn graph，就可以对这些轨迹进行聚类。

系统界面

文章提出五个分析目标：

1. 整体网络的演化分析
2. 动态节点的演化分析
3. 动态社团的时序分析
4. 稳定社团的结构分析
5. 将分析与网络的整体进行关联

分析系统的视图与这五个目标对应：

控制面板（A）

统计视图（B）

对应目标1

横轴表示时间，纵轴表示网络的平均演变值（evolution value），用以刻画网络的整体趋势；其中的统计直方图分别用红、绿、紫分别表示动态节点数量，新出现节点数量和消失的节点数量。

节点视图（D）

对应目标2

横轴表示时间，纵轴则表示节点的演变值从低到高。只展示动态的节点，并且用黄到红的颜色映射来表示节点的演变值。

趋势视图（C）

对应目标3

横轴：时间；纵轴：利用PCA，将节点向量投影至1维，并用线连起来。可以看到很多不同的社团演化，其中比较特殊的有如下：

结构视图（E）

对应目标4

用PCA按照节点向量，投影至二维。

灰色表示稳定的节点，并且用大小来表示稳定的持续时间；动态节点则用了粉色-绿色的颜色映射来展示演变值。凸包围盒则用以概括不同的社团。

snapshot视图（F）

对应目标5

将以往探索过的结构记录在最右方。