机器学习的方法来帮助进行大图可视化

作者 Jackie Anxis 日期 2017-09-03
机器学习的方法来帮助进行大图可视化

机器学习的方法来帮助进行大图可视化

  • 论文原标题:What Would a Graph Look Like in This Layout? A Machine Learning Approach to Large Graph Visualization

为了为图数据挑选一个合适的布局,论文提出了一种机器学习方法,基于用graph kernel计算的图拓扑相似度。这种方法可以显示图结构在不同的布局方法下的外观,并且可以估计这些图在布局下的美学度量。文章的贡献点是提出了一个可以用来设计graph kernel的框架。

一、介绍

  • 背景:为了帮助用户找到一个合适的节点链接图布局,从而来描述一个图的结构,我们需要计算这个图数据在这种布局方法下的布局结果以及它的美学指标

  • 问题:一般的计算方法,对大图而言,计算以上两者开销太大。

  • 方案:文章提出用kernelized machine learning的方法来预测图的布局结果和美学指标,在保证一定精度的情况下,大量降低时间复杂度。

    而kernelized machine learning需要一个合适的kernel。这个kernel是用来比较图与图之间的相似度,从而驱动机器学习。

    kernel,或者叫做kernel function,是一个比较两个输入之间相似度的函数$\chi \times \chi \mapsto \Bbb{R}$,kernel function k,经常被定义为特征空间$\cal{H}$中两个向量的内积:

    $k(x, x’) = \langle\phi(x), \phi(x’)\rangle = \langle\bf{x}, \bf{x’}\rangle$

    其中$\phi$是输入$x$到特征向量$\bf{x}$的映射,$\chi\mapsto\cal{H}$

  • 基本假设:在给定的相同的布局方法下,如果图有相似的拓扑结构,那么他们就会有相似的布局结果。

拓扑相似度比较方法——graph kernel

  • 老方法:graph kernel通过将图递归分解成一系列子结构,通过这些子结构的比较来评价两个图的相似度。这些子结构可以是:walks, shortest path, subtrees, cycles和graphlets。

  • 存在问题:因为很多graph kernel不适合大图,因为时间复杂度的问题或者不适合未标记图(节点之间除了连通性以外没有其他区别的话,就把这个图成为未标记的,unlabeled)。

  • 新方法:文章采用了graphlet kernel,其特征向量采用的是graphlet(下文称之为图元)的频率分布向量。

    图元是一种小的异构的导出子图。导出的(induced)的定义是:对于$G=(V, E)$,$V$的一个子集$V1$,以$G$中两个端点都在$V1$中的边组成边集$E1$,和$V1$构成的的图为$G$的$V1$导出子图。

    图1:3、4、5节点的所有连通的图元

    下面列举了节点数为3/4/5的所有连通的图元:

  • 基本思想:通过计数图中相互独立的图元的个数,统计它们的频率分布,将图元的频率分布向量,作为图的特征向量,用kernel计算两个图的特征向量的内积,就可以比较图之间的相似度。

二、方法

设计graphlet kernel的框架

一个graphlet kernel的设计,需要以下步骤:

  1. 采样图元,统计个数(采样方法)
  2. 计算图元频率向量(频率计算方法)
  3. 求两个图元频率向量的内积(内积方法)

2-1采样图元

穷举所有图元开销过大,要穷举所有k节点图元,开销是$O(|V|^K)$。故而采用随机采样方法,主要有两种:

  • 随机节点采样(Random vertex sampling (RV)):为了找一个k节点图元,通过随机找k个节点,用它们原有的边连接。但对于真实世界的网络,$|E|<<O(|V|^2)$,那么大部分随机采样的图元将会是不连通的。当只想采样连通图元的话,就需要很多轮迭代才能采到足够数量的图元,时间开销会很大。
  • 随机游走采样(Random walk sampling (RW)):基于随机游走的采样方法,还没被用于设计graphlet kernel,这种采样方法可以用来采集连通图元。

2-2计算图元频率向量

图元频率被定义为每种图元$g_{i}$的相对频率,以此构成的频率向量,本质上就是图的一个特征向量。一共有两种方法用来计算频率向量:

  • 线性比例变换(linear scale, LIN):也被叫做图元浓度(graphlet concentration),是每种图元在图中的百分比,一些工作用每种图元的加权数量$w_i$来定义它:

    $x_i = \frac{w_i}{\sum w_i}$

  • 对数比例变换(Logarithmic scale, LOG):类似于节点度分布,图元频率分布也经常服从幂律分布,这会导致缺少关键信息的图元会远高于那些信息丰富的图元,故而一些工作用了一个对数变换来解决这个问题,其中$w_b$是一个基础权重,来防止$log(0)$:

    $x_i = log(\frac{w_i+w_b}{\sum (w_i+w_b)})$

2-3定义内积

文章引用了以下几个计算特征空间中的内积的kernel函数,内积结果即为两个图的相似度:

  • 余弦相似度(Cosine similarity,COS):现有最多的graphlet kernel使用欧氏空间中的两个向量的点积后产生的点积产生的矩阵的归一化结果作为核函数,也就是两个向量的余弦相似度,也是两个向量的

    $\langle \bf{x, x’} \rangle = \frac{\bf{x \cdot x’^T}}{||\bf x|||| \bf x’ ||}$

  • 高斯径向基函数核(Gaussian radial basis function kernel, RBF):经常被用在机器学习中,$\sigma$是一个自由参数

    $\langle \bf{x, x’} \rangle = exp(-\frac{||\bf{x - x’}||^2}{2\sigma ^ 2})$

    • 拉普拉斯核(Laplacian kernel,LAPLACIAN):是RBF核的一种变种:

    $\langle \bf{x, x’} \rangle = exp(-\frac{||\bf{x - x’}||_1}{\sigma})$

三、用途

3-1预测图的布局结果(WGL)

文章把这个方法称为WGL(What Would a Graph Look Like in This Layout? )

文章基于相似度,设计了一个类似KNN的最近邻算法,用来找出和输入图$G_{input}$拓扑结构最相似的k个图,并展示他们已存在的布局结果给用户。用户就可以通过观察这些拓扑相似的图来预测$G_{input}$的结果,步骤一共分三步:

  1. 计算准备好的已存在的图(每个图都预先计算好了布局结果)和输入图$G_{input}$的相似度
  2. 移除不满足约束条件的图(因为有些图,虽然它的特征向量和$G_{input}$很相似,但是因为节点过多或者过少,事实上应该不算做相似图,比如图2,文章中设置了一个约束条件,即相似图的节点数,不能多于$G_{input}$的2倍,或者少于$G_{input}$的1/2)
  3. 选出K个最相似图
图2:图元频率分布的四个例子

下图中,x轴表示了图元的种类,y轴表示了图元的频率。图a和c的图元频率分布相似,且节点数量也相近,我们可以认为它们两者是拓扑相似图;但是,虽然图b和d的图元频率分布相似,但是因为节点数量相差过大,它们事实上不应该算作相似图。

3-2预测图的美学指标(EAM)

文章把这个方法称为EAM(Estimating Aesthetic Metrics)

美学指标是用来评判一幅图布局的良好状况的一系列指标,既然计算一个图的实际布局结果非常耗时,我们可以训练一个回归模型,用于预测某个新的输入图的美学指标,而不用实际计算布局结果,训练步骤一共分三步:

  1. 准备训练数据(一系列的图,以及它们在不同布局下的布局结果和相关的美学指标)
  2. 用graph kernel计算训练数据中的图和图之间的相似度
  3. 训练回归模型

之后,我们就可以通过计算新的输入图和训练数据中的其他图的相似度,用已有的回归模型,估算输入图的美学指标。

四、评估

4-1估算布局的美学指标

4-1-1评估目的

为了回答一下几个问题:

  1. 精确?在不计算实际布局的情况下,是否能够精确地估算布局的美学指标?
  2. 快速?能否快速的获得估算结果?
  3. 更强?由上述框架产生的graph kernel是否能够在计算时间和精度方面都优于最先进的graph kernel?

4-1-2实验设计

4-1-2-1数据集
  1. 收集了包括并不限于社交网络、网络文档网络、几何网络的3700个图。在不失一般性的情况下,把具有多个连通部件的图拆成几个分离的图(一个连通部件对应一个图)。
  2. 之后剔除少于100个节点的图,因为这些图的计算会特别快,从而影响实验结果。
  3. 最后剩下8263个图,节点数范围从100~一亿一千万,边数范围从100~18亿。因为某些图在计算布局的时间上花了10天以上或者内存跑完了,这些图就被抛弃了。
4-1-2-2kernel选取

一共十二个(2×2×3)核函数,是由生成graph kernel的框架中提到的2种采样方法(随机选点RV和随机游走RW)×2种图元频率计算方法(线性LIN和对数LOG)×3种内积函数(COS, RBF和LAPLACIAN)组合而成。

并且,选取了一个目前已有的最先进的graph kernel,DGK(Deep Graph Kernel)进行比较。

对于所有的kernel,每幅图都采样了10000个有三个、四个、五个节点的图元(一共49种图元,其中29种是连通的,如图1所示)。因为计算开销的问题,这三种图元用的比较多,而6节点以上的图元一般比较稀有。并且RW采样只考虑连通图元,RV采样考虑非连通和连通的图元。

4-1-2-3布局方法选取

这里只考虑二维平面,用直线绘制边的布局方法。

因为时间问题,不可能计算所有的布局方法。所以根据(1)使用的广泛性,(2)是否有公开实现,(3)是否被证明优于同类其他方法,文章选取了5种布局方法类别中的8个具有代表性的布局方法。

  • 力引导(Force-directed methods):电子模型中选取了Fruchterman-Reingold (FR),能量模型中选取了Kamada-Kawai (KK)
  • 基于降维的方法(Dimension reduction based method):选取了High-Dimensional Embedder (HDE)
  • 谱方法(Spectral method):选取了Koren的方法
  • 多层方法(Multi-Level methods):选了sfdp和FM3
  • 基于聚类的方法(Clustering based methods):选了Treemap based layout和the Gosper curve based layout
4-1-2-4美学指标的选取

文章选取了其中四个有标准形式,具有一般性的,切能够在合理时间内计算得到的美学指标:

  • Crosslessness ($m_c$):在很多研究中,边的交叉数量被作为一种最重要的审美标准,边交叉越少越好:

    $$m_c = \begin{cases} 1 - \frac{c}{c_{max}}, & \text {if $c_{max} > 0$} \ 1, & \text{ otherwise} \end{cases}$$

    其中,$c$是边的交叉数,$c_{max}$是边交叉数的近似上界,被定义为:

    $$c_{max} = \frac{|E|(|E| - 1)}{2} - \frac{1}{2}\sum_{v \in V}(deg(v)(deg(v) - 1))$$

  • Minimum angle metric ($m_a$):被定义为点$v$上的边的最小夹角和理想的最小夹角的平均绝对离差:

    $$m_a = 1 = 1 - \frac{1}{|V|}\sum_{v \in V}|\frac{\theta (v) - \theta_{min}(v)}{\theta(v)}|$$

    其中,理想最小夹角,定义为点上的所有边刚好平分360°:

    $$\theta(v) = \frac{360°}{deg(v)}$$

  • Edge length variation ($m_l$ ):根据边长的变异系数计算得到:

    $$m_l = \frac{l_{cv}}{\sqrt{|E| - 1}},\quad l_{cv} = \frac{l_{\sigma}}{l_{\mu}} = \sqrt{\frac{\sum_{e \in E}(l_e - l_\mu)^2}{|E| \cdot l_{\mu}^2}}$$

    其中:

    • $l_{cv}$是边长的变异系数
    • $l_\sigma$是边长的标准差
    • $l_\mu$是边长的平均值
  • Shape-based metric($m_s$):可以用mean Jaccard similarity(MJS)方法,比较某个图和标准图(一般认为标准图的结构良好,属于较美的图)的相似度,定义该图的$m_s$

    $$m_s = MJS(G_{input}, G_S), \quad MJS(G_1, G_2) = \frac{1}{|V|} \sum_{v \in V} \frac{|N_1(v) \bigcap N_2(v)|}{|N_1(v) \bigcup N_2(v)|}$$

    其中,$G_1=(V, E_1)$和$G_2 = (V, E_2)$是所有节点都相同的两个图,$N_i(v)$是图$G_i$中$v$节点的相邻节点。采用Gabriel graph作为标准图,用于比较。

4-1-3如何评判估算结果是否精确

为了评价在某种布局下,上述步骤估算出来的美学指标和这幅图在这种布局下实际上的美学指标的吻合情况(也就是估算精度),需要计算一下输入图$G_{input}$在经过布局方法布局后,真实的美学指标。之后,可以用以下两种方法比较估算结果实际测量结果的吻合程度:

  • 均方根误差(Root-Mean-Square Error (RMSE)),结果越小越好

    $$RMSE(\cal Y, \tilde{\cal Y}) = \sqrt{\frac{1}{n}\sum_{i}(y_i - \tilde{y_i})^2}$$

    其中:

    • $\cal Y = {y_1,…,y_n}$是经过实际布局后,测量出来的真实结果;
    • $\tilde{\cal Y} = {\tilde{y_1},…,\tilde{y_n}}$是回归模型的估算结果。
  • 测定系数(coefficient of determination (R ) ):结果越小越好

    $$R^2(\cal Y, \tilde{\cal Y}) = 1 - \sum_{i}(y_i - \tilde{y_i})^2 / \sum_{i}(y_i - y_\mu)^2$$

    其中$y_\mu$是测量结果$y_i$的平均值

4-1-4实验结果

4-1-4-1估算精度方面
图3:部分精度评估结果

上图展示了四个不同的kernel(RW-LOG-LAPLACIAN, RW-LOG-RBF, RV-LIN-COS, DGK)在八种不同的布局方法($sfdp, FM^3, FR, KK, Spectral, HDE, Treemap, Gosper$)的四种不同美学指标($m_c, m_a, m_l, m_s$)的两种不同估算精度度量($RMES, R^2$)的结果。加粗部分是最佳结果。

  • 从上图可以看到,除了在$FM^3$布局下的$m_c$指标以外,RW-LOG-LAPLACIAN kernel的表现都是最佳。而RW-LOG-RBF kernel则在$FM^3$布局下的$m_c$指标表现最佳。DGK排名为第十二名,说明框架产生的kernel大部分都优于这个对照组,也就回答了第三个问题。
  • 总体而言,RW采样方法得到的结果精确度要高于RV采样方法,LOG变换比LIN变化的精度更高,用LAPLACIAN的核也比其他两者精度更高。
4-1-4-2计算时间方面

因为有一些算法是并行计算的,而有一些不是。故而,这里只汇报了CPU时间。Estimation time只考虑预测图的美学指标中提到的计算时间(不考虑训练模型的时间)。

结果显示,精度最高的核RW-LOG-LAPLACIAN kernel也跑的最快,平均每幅图0.14093秒(标准差为1.9559)的时间进行估算。

时间开销最大的是在采样图元的时候。

  • RW采样计算速度最快,每幅图平均0.14089秒 (标准差为1.9559)。
  • DGK的图元采样速度比RW要慢,每幅图平均3.38秒(标准差为7.88)。
  • RV采样计算速度最慢,每幅图平均6.81秒(标准差为7.04)。
图4:计算时间和图规模之间的关系

下图显示了拥有最高精度的RW-LOG-LAPLACIAN kernel,实际计算和估算八种布局结果以及四种美学指标的时间。左图展示了八种布局的平均实际布局时间以及估算时间(y)和图节点数量(x)之间的关系,右图则展现了不同美学指标的平均计算时间以及估算时间(y)与图节点数量(x)之间的关系。随着图的规模变大,实际布局计算时间以及美学指标的计算时间和估算时间之间也就拉开了距离。

4-1-5讨论

  • RW采样方法比RV采样方法精度高,因为RW只采样连通图元,故而我们推测,连通图元对展现图的结构信息更重要,故而估算结果的精度也更高。
  • 事实上,在用RV采样的过程中,每个图采样10000个图元,发现只有1.913%是连通图元,而有35.77%的图没有采样到连通图元,即便它们这些图本身都是连通的,这就使得这些图本身就很难用于比较。
  • 使用LOG变换的核,比使用LIN变换的核,平均而言有着更高的估算精度,可能是因为图元的分布也经常呈现出幂率分布。
  • 因为在估算过程中,不用再计算实际的布局结果,所以估算布局结果和美学指标的速度会很快。
  • 发现除了DGK以外,其他核矩阵的计算时间都很短,而且相差不大,平均5.99秒,标准差3.26。而DGK因为要计算语言模型language modeling,需要平均182.96秒。

4-2预测图的布局结果

4-2-1评估目的

此次评估是为了验证文章提到的WGL方法评价出来的图和图的相似情况是否和人类心理上认为的相似情况接近。

4-2-2实验设计

此次试验是一个排序实验,是为了比较WGL方法得到的训练数据中的图和目标图的拓扑相似度的排序结果($r_T$)和人类主观评价出来的相似度排序结果($r_P$)是否匹配。

4-2-2-1任务

图5所示,参与者都会面对一个目标图(Target)和九个选项(Choices),他们需要从这些选项中,挑选出和目标最像的三个图,并按照相似度进行排序。

为了避免偏见,实验并没有定义什么叫做“相似”,并且也没有告诉用户,这些图都是用同一种布局方法进行布局的。

实验采用了九个图数据,八种布局方法进行组合,一共是72个任务。

图5:用户调研中的其中一个任务示例

每个任务中,参与者都会面对一个目标图(Target)和九个选项(Choices),他们需要从这些选项中,挑选出和目标最像的三个图,并按照相似度进行排序。a, b, c三个图的中心节点被展示在右边。

4-2-2-2图的选取
  • 目标图(Target):一共选取了9个目标图,选择过程如下:
    1. 将已有的8000+图,利用谱聚类(spectral clustering)的方法分成9类
    2. 对于每一类,选出相互之间拓扑相似度最高的十个图,作为这一类的代表图
    3. 从这十个代表图中随机挑选一个作为目标图(Target)
  • 选项图(Choice):每幅目标图,都要挑选九幅选项图:
    1. 利用每幅图和目标图之间的相似度,利用Jenks natuarak breaks方法(一种一维的K均值分类方法)将所有图分成9类
    2. 从与目标图最相似的聚类中,选出和目标图相似度最高的图,作为其中一张选项图
    3. 剩余八类中,每一类都选出相互之间拓扑相似度最高的十个图,再从这十张图中随机挑选一张,作为剩余八张选项图
    4. 当然在挑选过程中,需要过滤掉那些节点数大于目标图两倍,或者小于目标图一半的图

4-2-3实验结果

图6:用户调研的总结

蓝色表示用户挑选其作为最相似图的比率,绿色表示用户挑选其作为第二相似图的比率,浅绿色表示用户挑选其作为第三相似图的概率。

左图(a)显示了用户主观的相似图判断和算法结果的匹配程度

中图(b)显示了,在不同布局下,算法选出的最相似图($r_T = 1$)和用户的选择的匹配程度

右图(c)显示了,对于不同的目标图,算法选出的最相似图($r_T = 1$)和用户的选择的匹配程度

  • 图6,发现有80.46%的情况,参与者认为最相似的选项图($r_P=1$)和系统选出来的最相似的图($r_T=1$)刚好吻合(图a最左边的蓝色长条);90.27%的情况下,参与者认为的最相似($r_P=1$)和第二相似($r_P=2$)的选项图和系统选出的最相似图($r_T=1$)吻合;而93.8%的情况下,参与者选出的第1、2、3相似的图($r_P={1,2,3}$)和系统选出的最相似图($r_T=1$)吻合。
  • 除了treemap布局和spectral布局以外,有78.52%~93.33%的情况下,参与者选出来的最相似图和算法得到的最相似图一致,有94.44%~99.26%的情况下,参与者选出来的最相似的三幅图和算法得到的最相似图吻合。
  • 目标图中,除了$G_{2331}$和$G_{3833}$,有79.58%~98.33%的情况下,参与者选出来的最相似图和算法得到的最相似图一致,有92.08%~99.99%的情况下,参与者选出来的最相似的三幅图和算法得到的最相似图吻合。

4-2-4讨论

  • 为什么Spectral和Treemap布局比其他的布局方法结果要差?
    • spectral:参与者根据线的形状、节点的个数来判断相似程度,我们发现,谱布局,经常会有很多节点重叠,故而会让参与者判断不准
    • treemap:因为它的几何限制,经常产生相似的图形,参与者几乎都提到,“这些图怎么长的都一样?”,他们经常会根据边的密度,整体边的走向来判断相似程度,故而判断不准
  • 为什么G2331情况比较糟糕?图5所示情况,参与者在b和c图中徘徊不定:
    • 参与者选择c的原因:密度、形状、边的数量
    • 参与者选择b的原因:中心节点的数量
    • 系统选择c的原因:大体上结构和目标相似

五、讨论

上图是8263幅图用RW-LOG-LAPLACIAN kernel计算得到的相似度的一个投影,这一对对的图是9对拓扑结构最相似但却非同构的图。

这篇论文,为我们进行大图可视化提供了一个新的思路,为了应对大图中高的计算代价,可以通过机器学习的方法,用预计算的代价来代替实时计算。这样就甚至能把大图的某些计算效率提高到实时的级别。