Link Prediction – 1

最近找了份实习没啥时间看Paper，毕业论文打算从图这一块入手写，抽空看了几篇文章做个记录，在之后写毕业论文的时候也可以让自己做一些参考，主要是一些对于图之中的链接进行预测的文章。

Multi-Scale Learning

多尺度学习的方法，这里的尺度(Scale)指的并不是使用的数据的多样性，像之前见过的一篇文章里面会使用文本的信息以及音频的信息共同来处理，那种也属于添加了不同的尺度，但是那种的方式有一个特有的名字叫做是Multi-Model Approach。这里的Multi-Scale的方法呢则应该是来自于CV领域的一些想法，总所周知，数据是机器学习的重中之重，很多模型需要足够的数据喂养才可以成长起来，那么在缺少数据的情况下我们可以采用一些什么样的方法呢？在CV领域有一种方法就是把图片的尺寸进行压缩或者是切割之后，作为一种增广之后的数据进行使用。那么在Graph的领域也可以尝试运用这样的思想，但是很可惜的是，在图这样的一种并不那么标准的数据格式下，进行Rescale则显得要复杂许多。

首先来分析一下Link Prediction的任务目标是什么，有很多方法可以解决Link Prediction的问题，一种很经典的方法就是启发式的方法(Heuristic Approach),其基本的思想就是使用一个启发函数(Heuristic Function)计算不同的节点之间的“相似度”，并进以评估是不是会存在一条边。但是由于启发函数是有我们认为所设定的，所以在不同的图结构上面可能需要我们人为的进行一定程度的适配以获得更好的效果。为了解决这样的一种困难呢，Zhang and Chen在2018年提出了一个框架叫做SEAL，在这样的一种框架之下，可以学习到在大的图之中的某些封闭子图的结构，从而就将Link Prediction的任务转换成为了一个Graph Classification的任务了。我们首先来看看SEAL的方法是怎么处理的

SEAL Framework

在其之中使用了一个图卷积神经元层以抽取图中节点的特征并获得每一个封闭子图的特征，获得了特征之后使用SEAL Framework判断是否两个节点相互联系。这样的方法还是一个比较直接的方法，但是这样的一种方法有一个非常明显的缺陷就是每个节点都会非常显著的被周围的节点的特征所影响。也就是说他们的“视野”很近，从而导致长距离的那些节点的特征很难被获取。

Multi-Scale Approach for Graph Link Prediction

对于连接预测类的任务呢，作者认为可以分成几个不同的步骤：分别是封闭子图结构的抽取、子图结构特征的获得，以及最终的目标-链接预测。那我们从这三个步骤开始依次分析：

1. 获得子图的结构

当前最直接可以拿到图的特征的方法是图卷积的方法，而如前文所言，GCN的方法很难捕获长距离的节点特征。而为了可以获得长距离的依赖关系，作者提出了一种Aggregation的方法，通过将含有重复的信息的节点融合成为一个新的“节点”的方式获得长距离的依赖关系。以不同的Scale的图网络为我们的最终的预测任务提供可以互补的信息。

为了将冗余节点合成一个新的节点，我们需要评估一下不同的节点之间的相似性。作者所提出的方式是对于每一个节点都Assigh一个Label，然后基于Label来合并不同的冗余节点。那么问题就退化成为了如何为不同的节点Assigh Label，作者的做法是首先选择出两个待判断的Target Nodes然后对于子图之中的每一个Node i都进行如下的流程

$$f_{l}(i) = 1+ min(d_x,d_y) + d_x +d_y$$

在上面的公式里的$d_x = d(i,x), d_y = d(i ,y)$代表了在节点$i$和两个Target Nodes $x$以及$y$的最短距离，最终的函数结果可以看成是一种Score。由于我们现在想做的事情是判断在网络两个节点是不是包含了类似的信息，所以我们的处理方式是将具有相同的性质的节点结合在一起，这个相同的性质呢，选择的就是之前所计算出来的那个Score，当两个Node i 和 j满足下面的条件的时候，我们就会将他们加起来

$$\{ (i,j)|f_{l}(i) = f_{l}(j) and A(i,j) = 1\}$$

这里的$A(i,j)$代表的是是在$i,j$之间通过一条直接相连的边进行连接。这个的条件是说，当i和j通往两个待判断节点的路径相同且有直接的边相连的时候，则认为他们是可以相互代替的。需要注意的是这里的考虑的因素仅仅是结构上的因素而没有考虑到内在的特征的因素，当然这样也可以很大的程度上提供有用的信息。

然后按照同样的思路，合并了一轮之后可以再进行下一轮的合并，通过多轮的合并，我们就可以获得多种多样的新的图结构帮助判断。

Industrial Research

Risk Analysis with Supply Chain Mining

蚂蚁金服的一项工作，虽然蚂蚁上市失败了，但是不得不数看过的几篇蚂蚁金服写的文章都非常不错。这篇文章主要研究的问题是中小企业的财务风险的问题，和蚂蚁的业务也非常的契合，与大企业不同，中小企业的最大的问题就是没有足够的财务相关数据来分析企业的风险情况。但是幸运的是，（对于蚂蚁金服）可以获得大量的交易数据，换言之我们可以通过交易的双方构建一张交易网。但是并不是所有的信息都会对于预测财务风险有所帮助，在网络之中也会出现一些对于我们预测财务风险完全无用甚至有害的信息。为了处理这样的一个问题，作者使用了Spatial-Temporal结合的方式进行处理，也就是还算经典的时间空间图模型进行处理。

在正式开始解决问题之前，作者首先进行了两个探索性的分析过程，第一个过程就是研究是不是可以通过供应链的信息帮助解决信息缺乏的问题。其一个假设是，如果上游或下游供应方含有相关信息，那么一定程度上可以反馈出我们的Target公司的信息，从直觉上来讲，Target公司信息缺乏的概率会是远远小于Target公司和上下游公司同时缺乏相关信息的可能的，事实上研究人员也进行了统计发现的确如此。

其中的RF1就是在供应链之中的单个公司含有相关信息的概率，而RF2则是和其上游公司之中有一家有相关信息的概率，RF3则是其与下游公司之中有一家有相关信息的概率，RF4是与其上下游公司之中有一家有相关信息的概率。可以发现如果将考量范围拓展到整个供应链上，是可以对于原有的数据缺乏程度进行一定程度的补充的。

而第二个探索性分析的过程就显得更加直接，判断供应链之中的企业的数目是不是和企业出现债券违约的情况有所联系，最后可视化成为了下图

可以发现随着供应链之中的连接数不断的增加，公司的债券的违约的数量也会出现显著的下降。也就至少说明了公司的上下游连接越丰富，公司的债券越不容易违约。

这两个探索性的分析初步的说明了我们的这一项研究是有意义的，接下来呢，就是进入本文的重头戏的部分了，利用GNN来挖掘供应链之中的一些特征。首先我们对于我们接下来要用的一些术语进行定义，第一个定义叫做是SME Graph，在时间点$t$的一个SME图我们将其记作是G^t,$G^{t} = \{V,E^{t},X^{t},E^{t}\}$,其中的$V$和$E$代表了节点和边的信息，而$X^t$和$E^t$则代表了节点的特征矩阵以及边的特征矩阵。从$t_1$到$t_2$的SME图连接起来则就可以构成一张供应链时空图。而第二个定义我们叫做是Graph-Based Supply Chain Mining,给定一张SME时空图以及在两两实体之间是否存在一条边的数据，我们希望可以预测到未来在不同的实体之间是不是会出现连接。

而模型的整体架构呢如下图所示

在上图之中有两个非常特殊的机制，第一个机制就是Spatial-Aware Aggregator，第二个机制是Temporal-Aware Aggregator.从上图之中可以看见，作者提出的模型之中在每一个Snapshot都使用了Spatial-Aware Aggregator的机制，基于这样的一个机制，我们可以在每一个时间步上面都获得一个对应的Embedding，而获得了每一个节点的T个Embedding之后，将这T个Embedding作为Input输入Temporal-Aware Aggregator之后就可以得到一个最终的Embedding，并进入端到端的模型训练之中。

那我们不妨对于这两个机制进行一些简单的分析流程，首先是Spatial Aware Aggregator.如果我们给定一个目标节点$u$以及其在时间点$t$时候的Neighborhood 记作$N_u^{t}$,那么这个Spatial-Aware Aggregator $\phi(\cdot)$就可以被定义为是

$$z_{u}^{t} = \phi(x_{u}^{t},\{(x_{v}^{t},e^{t}_{u,v}): v\in N^{t}_{u};\Theta_{\phi}^{t})$$

其中的$x$以及$e$代表的都是节点和边的特征，$\Theta$是待学习的参数。我们使用Attention作为这个$\phi$，也就是说

这个还是一个比较常规的做法，就是引入Attention机制进行加权。之后的Temporal Aware Aggregator机制则借鉴了LSTM之中的一些思想。当给定了图的结构和每一个Snapshot的节点Embedding的时候，我们使用下面的方法计算

在每一个时间步之中不仅仅会考虑到由空间图直接过来的Embedding的数据，同时也会考虑到之前的时间状态的$h,c$的相关信息，至此，我们就可以充分大利用了时间维度以及空间维度上的所有的节点的信息。

并根据这样的一个Embedding完成我们所需要完成的任务，比如说连接预测的任务的话，他所做的工作其实也只是输入节点的Embedding然后使用一个MLP进行二分类的判断而已，当然，整个网络的贡献在计算Embedding的时候就已经使用过了，但是并不是直接使用整个图进行任务的处理还是让自己略微有些失望。

Anchor Link Prediction

Anchor Link Prediction指的是在两个不同的网络之中得以识别出相同的Entity，并且可以准确的将一个网络之中的边的特征移植到另一个网络之中，以如下的图所示

我们就可以以这种方式将两个不同的网络之中的结构相连接起来，作者的创新点主要有2，第一点是使用了叫做n-tuple representation的机制，第二点是使用了Type-Aware Alignment的方法，对于n-tuple representation其实也就是对于每一个网络结构都去学习一个Embedding，而由于作者担心在这样的过程之中有可能会使得不同的图之中的类别信息有所丢失，所以其又引入了一个机制可以保留一些Type的信息。

假设在一个图G之中给定了节点$v_{ai}$之后，使用$N_{v_{ai}}$d代表节点$v_{ai}$的第$r$类型的Neighborhood节点，为了获得Type的Embedding信息，首先我们会对于其Embedding进行初始化，将节点的初始化Embedding记作是$x_j$,将邻居的节点记作是$x_j$，首先通过一个线性变化处理初始特征，然后使用Attention的方法进行加权。

获得了每一个节点的表示以及Attention之后，以下面的公式获得Type的Embedding

当然也可以很简单的拓展到多头的情况下

至此，我们就可以得到了代表了某一种Type的节点的Embedding表示。

那么如何将Type的信息融入节点之中呢？依旧是使用Attention的方法，这里的Attention是计算节点以及Type Embedding之间的Attention，具体的细节限于篇幅我也不展开了。结果的最后我们就可以获得含有Type的信息的节点表示将其记作是$f$。得到了信息表示之后我们就可以进行Anchor Link的判断了，首先我们有一个基本的假设，也就是说，如果某一个节点在两张图之中都出现了，那么他的Embedding理应是相差不大的(这个假设其实我认为问题还是蛮大的，特别是在神经网络这样的一个黑箱之中，你很难保证Embedding的过程是真的有什么实际性质的吧？）

然后使用这样的一个目标函数对于整体进行优化，S和T代表的是两种不同的图，d则代表了距离度量的函数，在本文之中所选择的距离是很简单的曼哈顿距离
至此就可以将两个网络之中的节点进行对应起来，写到这里想起一个蛮有意思的事情，当初Facebook收购WhatsApp的时候，欧盟曾经觉得这样的一笔交易涉及垄断，因为欧盟认为一旦收购完成，Facebook将两个软件里面的数据一整合可能就会产生垄断行为，但是Facebook说这两个软件的数据并不互通，他们无法将两个软件里面的个人信息进行对应，欧盟也就信了扎克伯格的话，但是转头就杀了个回马枪罚了Facebook 1.1亿欧元，说是对于官员的判断进行了误导。为什么是误导呢？因为欧盟的官员发现如果一个人用手机注册了这两个app那么自然而然的就可以将这个Anchor Link给找出来，在这个互联网时代，如果说这个技术真的可以帮助对应在不同的网络之中的个人的话，我还是比较排斥这样的一种技术的。

Other Domain

GMAN : A Graph Multi-Attention Network for Traffic Prediction

预测交通一直而言都是一个非常复杂但是很有意义的工作，可以帮助更好的调度汽车进而方便人们的出行。这样的一个预测任务不但要考虑到所预测的节点的周围路口的动态交通信息，同时也需要考虑到该节点的历史的状况的信息，所以使用的框架是时空图也就呼之欲出了。

作者将道路网络抽象成为一张有向图$G=(V,E,A)$,其中的$V$代表的是在道路之中的各个节点，而$E$代表的是在这些节点之间所连接而形成的边，$A$就是我们所熟知的邻接矩阵了，对于时间$T$内的所有的Snapshot都建立这样的一张图，我们就可以获得$T$张图。我们的任务可以看成是在获得了前面的$t$个时间步的数据之后对于后面的第$t+1$个数据进行预测。整体的框架可以看下图

其实也就是一个Encoder-Decoder框架下的处理方式，在处理时间和空间的维度的信息的时候也是利用了Attention的机制进行一个过滤，但是对于时间和空间的信息，这里并不是拼接或者是其他的更复杂的处理的方式而是仅仅相加的处理，其实一直觉得这样的相加的方式会破坏掉两部分的信息的一些性质，不知道有没有相关的文献分析过不同的处理方式的区别。

 

小结

感觉这些文章的方法都是从时间空间的角度获取信息，并且通过Attention的方法进行整合，虽然结果看起来都是非常有效的，但是可能自己想要找的文章会要更加具有“可解释性”一些吧，就是可以比现在的这些方法更容易看出原理和这个学习的过程是怎么样的。但是这些文章也给了自己很大的启发，希望之后自己也可以用上这些方法吧。