图布局与图链接预测

现状

最近师弟师妹的加入，使得我们小组越来越壮大，然后频繁召开的组会次数越来越多，基本上一周一次，那么对于我们学生而言，压力也是挺大的，需要做大量的调研，讲清楚一篇论文。但是这也是好事，不仅能够让讲得人成长很快，而且也能让听得人“优化一下大脑”。不亦乐乎，故现做一下分享与记录。

本次主要分享师弟、师妹的两篇文献讲解

《Revisiting Stress Majorization as a Unified Framework for
Interactive Constrained Graph Visualization》

《weisfeiler-lehman neural machine for link prediction》

Part 1

第一篇文献应该属于图可视化的范畴，关于图可视化这个领域，我们可以查阅A Survey on Graph Visualization^[1],也可以直接阅读作者潘嘉铖^[2]对此综述的理解。

^[3]

此论文就是典型的旧问题，新方法。最大创新之处如上图所示，将Strees Majorization的’距离标量’改变为’距离矢量’，然后就有了作者接下来的一系列数学论证，运用到的数学工具是矩阵，编程是通过c++语言实现的，值得一提的是此论文的实验确实详实。

意义：
虽然自己并不是专门研究图可视化领域，但是此论文给我的启发就是顶会上的文章首先写得很漂亮^[4]，然后就是作者的大会视频^[3]可以借鉴。

疑惑： D3.js or Three.js的库是怎样引入约束的？

Part 2

第二篇文献属于社交网络当中的“边链接（Link Prediction）”预测工作。

作者提出了一种Wlnm（Weisfeiler-Lehman Neural Machine）方法进行“边链接”预测，对于网络中的每一个边，这种方法首先抽取了一个子图(一个边连接的封闭子图）,紧接着将封闭子图进行图编码转换为连接矩阵形式，然后将连接矩阵输入给神将网络进行一个边链接预测模型的学习。对于此任务的整个流程图如下所示：

作者提到自己两大工作就是这个框架流程对各种现实中的网络都具有普适性(great generality)、自己提出了一种新的Graph labeling方法。

普适性：由于作者采用的是神经网络，自动去学习网路结构中的拓扑特征（topological features），所以相比于之前的手工设计的规则或者经验方法（heuristics methods）。
Graph label算法：这方面有着很强的图理论知识背景，作者自己提出了一种WL算法的变种，即Palette-WL；

作者自己实现的流程如如下：

在自己实现的过程中首要解决两个问题：1）子图的抽取K的选取。2）运用自己提出的算法进行子图编码。

疑惑：为什么要进行图编码？图编码如何进行向矩阵转换？

Part 3

知识补充：

图

图（Graph）表示对象与对象之间关系的方法，两大要素：对象即节点（node）、关系即边（edge）

一般用两种形式表示图：

1）G=(V,E);v表示节点的集合，E表示边的集合。

2）邻接矩阵（Adjacent matrix）：矩阵的第i个节点与第j个节点为1表示有边，为0表示无边。刻画了一个图的结构信息。
缺点是：大部分节点没有关系，邻接矩阵特别稀疏，不利于存储计算。

图嵌入（Network Embedding）

网络表示学习（Network Representation Learning）也称为图嵌入法（Graph Embedding Method）：用低维、稠密、实值的向量表示网络中节点。该向量反映了图中的结构，最大的好处就是不再手工提取特征，可以将异质信息投影到同一个低维空间，然后可以输入任何的机器学习模型去解决具体面对的问题。图嵌入的经典应用推荐、节点分类、链接预测、可视化。

在深度学习方法中，我们也经常听到Embedding层。那么深度学习中的Embedding到底是什么含义呢？为什么需要这个层呢^[6]？

1）使用ont-hot编码的向量很高维，也很稀疏

2）使用了embeeding之后，在神经网络训练过程中，我们就可以可视化地了解到词语之间的关系。

面对上述优点与缺点，如何实现这种embedding操作呢？
举个栗子：对于一句话如：“deep learning is very deep”经过嵌入层之后可能就会表示为[1,2,3,4,1];原因是我们影射了一种关系，如下所示：

我们用留个维度的向量[.32,.02,.48,.21,.56,.15]表示额“deep”这个单词，工程实现上我们会用矩阵的索引“1”来表示单词“deep”^[8]。

node to vector

像大家熟知的NLP领域中的word to vector^[7]，大家就在考虑能不能够将这种想法运用到图（Graph）中.基于DeepWalk算法的改进实现^[9]。形成了自己的启发式方法，然后将一张图（复杂的图结构）转换为一篇“文本”，然后调用现成的word2vec模型来生成向量。

嵌入为什么能够进行可视化呢？

node2vector^[9]作为一种图嵌入（图表示）的方法，因为其遵循了两大原则：homolphily（同质性）；structural equivalence（结构等价性）。那么实际用途可以进行网络的分析。比如对于小说《悲惨世界》人物关系的分析，总共有77个人物，即77个节点。人物之间总共有254个关系，即254个边存在。

上图是通过词嵌入可视化之后得到的社区图，下图是通过词嵌入可视化得到人物角色等价（有点不好理解）可视化图

现状