图神经网络

GTN (Nips 2019)

Graph Transformer networks

arixv:https://arxiv.org/abs/1911.06455

前言前言前言

前几天忙着离职，重心就主要放在了把手上的一些东西整整完然后交给同事，博客更的少了一些，不过其实私下攒的文章还挺多的，就是格式上还都是书的格式，介绍的内容也不够细，还得再花点功夫修一修。从公司溜出来了以后应该就会一门心思走时空图神经网络了，先把手头的存货弄完，后面就接着时空序列了。

OK，这次介绍的文章是异质图神经网络相关的。虽然题目里有transformer，但其实内容和我们熟知的那个transformer一毛钱关系也没有。本文要解决的问题有两个，一个是图结构会带有噪声，这个噪声怎么理解呢？就是一般在之前的图神经网络中给，模型都是假设网络数据是完好的，所有该有的边都有，不该有的边就不会有，但现实生活中这种“完美”的情况是非常少见的，更多的情况是有些边（即一些联系）本来是应该存在的，但实际结构中并没有出现，也有边本来不应该存在，但它确实出现了，如何处理这种情况就是GTN想要解决的第一个问题；第二种问题是异质图问题。一般的神经网络考虑的都是同构图的情况，即节点都是同一类型而边关系也都是同一类型，这种情况容易处理但现实生活中极其少见。更多的情况是节点类型多样而边类型也多样，在Graph transformer Networks(GTN)预设的问题中，考虑的是统一节点类型但边类型总数大于1。

现有的处理异构图的方案一般有两类：一是将异构图当作同构图处理，但这样会丢失很多隐藏信息；二是利用元路径将异构图转化为同构图后再进行处理。这种方法需要为不同的问题人为设定meta-path，并且模型最后的效果在很大程度上受限于meta-path的设计，这意味着需要设计者在针对的问题上有很深刻的理解。而GTN则试图通过生成新的图结构自动寻找meta-path，来减少建模对专业知识的需求。同时，GTN在生成新图结构的过程中也会补齐一些原图中缺失的边，来解决噪声图带来的挑战。

总的来说，本文提出的模型主要针对的就是上面两个问题，解决方法就是上面那段的最后部分描述的。惯例，我们来介绍一下文章里用到的定义：

问题定义

GTN模型输入是拥有不同节点和边类型的异质图结构。$\mathcal{T}^v$和$\mathcal{T}^e$表示节点类型和边类型集合，输入图可以被视作$G=(V,E)$，其中$V$表示节点集合，$E$表示边集合，这里还存在两个映射函数，$f_v:V\to\mathcal{T}^v$,$f_e:E\to\mathcal{T}^e$，这两个映射函数能将每一个节点和每一条边映射到对应的类型中，正如上面提到过的，$|\mathcal{T}^e|>1$。与此同时，异质图网络也可以用一系列的邻接矩阵$\{A_k\}_{k=1}^K$表示，其中，$K=|\mathcal{T}^e|$而$A_k\in R^{N\times N}$。换一种写法，输入的异质图结构也可以被写作$\mathbb{A}\in R^{N\times N\times K}$。除了邻接矩阵之外，还有一个特征矩阵$X\in R^{N\times D}$。
meta-path

A meta path is a sequence of relations between object types, which defines a new composite relation between its starting type and ending type. Consider a bibliographic network extracted from DBLP with four types of objects, namely, authors (A), papers (P), terms (T), and venues (C).

简单（翻译）来说，元路径（meta path）就是连接实体的一条特定的路径。例如$v_1\overset{t_1}{\to}v_2\overset{t_2}{\to}...\overset{t_l}{\to}v_{l+1}$，这里面$v_l$表示实体，$t_l$表示边关系。对于这一条路径，可以定义一个复合关系$P=t_1\circ t_2\circ ...\circ t_l$，同时呢，这个关系也可以用邻接矩阵$A_p=A_{t_1}...A_{t_2}A_{t_1}$表示，其中的$A_{t_l}$表示只包含边关系$t_l$的图的邻接矩阵（这里因为两个一阶邻接矩阵相乘后的结果是二阶邻接矩阵，类推就可以得到一个N阶的邻接矩阵）。

GCN

GCN还是采用了一阶切比雪夫近似的经典方法，稍有不同的是传统公式是用$\tilde{D}^{-1}\tilde{A}\tilde{D}^{-1}$进行标准化操作，但这里使用了$\tilde{D}^{-1}\tilde{A}$进行标准化操作。所以这里使用的迭代公式为：
$H^{(l+1)}=\sigma(\tilde{D}^{-1}\tilde{A}H^{(l)}W^{(l)})$

模型模型模型！

Graph Transformer Layer

pia图！

GTL

这一部分是整个GTN的核心，如上图所示，它主要的目标是生成新的图结构。主要的操作有两步，首先，GT Layer会选择两个图结构$Q_1$和$Q_2$，其次，它会通过组合这两个图结构来得到一个新的图结构。那么，如何来获取原始图结构$Q$呢？GT Layer设计了一个$1\times 1$的卷积操作来获得图结构，可以表示为：
$Q=F(A:W_{\phi})=\phi(A:softmax(W_\phi))$其中，$\phi$表示卷积层而$W_\phi\in R^{1\times 1\times K}$表示对应的卷积核参数，$K$表示边类型的种类数量，$A$表示了所有邻接矩阵的集合。这边的操作类似于计算出每个邻接矩阵的注意力得分后进行加权相加。随后让两个图结构相乘并用度矩阵正则化: $A^{(l)}=D^{(-1)} Q_1 Q_2$，这里就可以得到一个长度为2的meta-path的邻接矩阵。

于是，根据GT Layer的原理，任意长度为l的meta-path的邻接矩阵可以通过以下的公式计算：
$A_p=(\sum_{t_1\in\Gamma^e}\alpha_{t_1}^{(1)}A_{t_1})(\sum_{t_2\in\Gamma^e}\alpha_{t_2}^{(2)}A_{t_2})...(\sum_{t_l\in\Gamma^e}\alpha_{t_l}^{(l)}A_{t_l})$其中，$A_p$代表meta-path的邻接矩阵，$\Gamma^{e}$表示所有边类型的集合，$\alpha_{t_l}^{(l)}$是边类型$t_l$在第l层的权重值，即为上述Softmax结果在第l维的得分。这里的每一个小括号里的内容就是在对每一种边的邻接矩阵做一个加权求和。

但这个结构有一个问题，就是随着GT Layer的不断叠加，meta-path的长度会不断增加，而在一些应用场景下，短的路径和长的路径同等重要，后面会讲到在GTN结构中会在卷积层使用多通道捕获多条meta-path的信息，若不做特殊处理，所有通道的meta-path都会处于相同长度，而无法捕获短的meta-path。为了解决这个问题，论文向邻接矩阵集合中加入了一个单位矩阵，这样当GT Layer增大时，只要该单位矩阵的权重得分为1而其他的权重得分为0，就能使得meta-path邻接矩阵不发生变化，meta-path不增长。

Graph Transformer Networks

拍图！

GTL

介绍完GT Layer后，整个GTN结构就很简单了，无非就是多层Layer的叠加。值得注意的是，GTN为了同时考虑多条meta-path的信息，会将每层GT Layer中的卷积参数扩展到$C$维，这样，生成的图结构就变成了$Q\in R^{N\times N\times C}$，经过N层GT Layer后最后的输出也是一个$N\times N\times C$的图结构向量，之后只要对这C个通道的图结构张量分贝进行GCN操作，就可以得到C组节点表征：
$Z=\underset{i=1}{\overset{C}{||}}\sigma(\tilde{D}_i^{-1}\tilde{A}_i^{(l)}XW)$需要特别提一嘴的是$||$是拼接操作，后面的几项操作是传统GCN中的常规操作，不讲了奥。这一步之后能得到一个最终节点表征，后面就可以针对具体任务设计下游任务了。

总结总结总结

呼~这篇文章总体还是挺有意思的，通过生成新的图结构来帮助解决图结构噪声和异质图结构的问题，（文章其实我之前研一的时候也读过，当时找论文找着找着看到这篇，实不相瞒应该是我读的第一篇异质图网络论文，对meta-path用邻接矩阵表示这一块还是印象挺深刻的），别的启发啥的话，这种邻接举证表示应该还是有东西玩的，可以想办法和别的什么方法结合一下之类的。