原文摘自我自己的博客Link：http://holdenhu.cn/2020/paper-notegraph-transformer-networks/
作者：Seongjun Yun
來源：NeurIPS2019
筆記：Hu Hengchang
Intro
GTNs(Graph Transformer Networks)的主要功能是在原始圖上識別未連接節(jié)點之間的有用連接冲杀。
Transformer來學(xué)習(xí)有用的多跳連接，即所謂的元路徑煤蚌。將異質(zhì)輸入圖轉(zhuǎn)換為每個任務(wù)有用的元路徑圖异逐，并以端到端方式學(xué)習(xí)圖上的節(jié)點表示。
Definition
heterogeneous
異質(zhì)圖：例如银萍，引用網(wǎng)絡(luò)具有多種類型的節(jié)點(例作者络凿、論文憨攒、會議)和由它們之間的關(guān)系(如作者-論文觉既、論文-會議)定義的邊惧盹。
homogeneous
同質(zhì)圖，具有一種類型的節(jié)點和邊的標(biāo)準(zhǔn)圖瞪讼。
Related Work
傳統(tǒng)的GNN
是一種兩階段的方法钧椰，但每個問題都需要手工構(gòu)建元路徑。這些元路徑的選擇對下游分析的準(zhǔn)確性有很大的影響符欠。
包括spectral和non-spectral兩種方法嫡霞。
spectral是基于spectral domain(using Fourier basis)上進行卷積。
non-spectral直接在圖上沿著edge執(zhí)行卷積操作背亥。
Contribution
大多數(shù)現(xiàn)有的GNNs都被設(shè)計為在固定（fix）和同質(zhì)（homogeneous）的圖上學(xué)習(xí)節(jié)點表示。當(dāng)在不確定的圖或由各種類型的節(jié)點和邊組成的異質(zhì)（heterogeneous）圖上學(xué)習(xí)表示時悬赏，這些限制尤其成問題狡汉。一般的GNN手動定義元路徑，但GTNs可以學(xué)習(xí)有效的元路徑闽颇。
因此GTNs的出現(xiàn)：
提出了一種新的圖變換網(wǎng)絡(luò)盾戴，識別有用的元路徑和多跳連接來學(xué)習(xí)圖上的有效節(jié)點表示。
圖的生成是可解釋的兵多，提供有效路徑連接的解釋尖啡。
證明了圖變換網(wǎng)絡(luò)學(xué)習(xí)的節(jié)點表示的有效性橄仆，從而獲得了最佳的性能，而現(xiàn)有的方法在異質(zhì)圖的所有三種基準(zhǔn)節(jié)點分類中都使用了領(lǐng)域知識衅斩。
Implemention
我們的GTNs的目標(biāo)是生成新的圖結(jié)構(gòu)盆顾，同時學(xué)習(xí)到有效的node representation。GTNs使用多個candidate adjacency matrices尋找新的圖結(jié)構(gòu)畏梆。
preliminaries
圖表示為
,
is set of nodes,
is set of observed edges您宪。
和
分別表示node的種類，和edge的種類的set奠涌。
異質(zhì)圖能表示為adjacency matrices的集合
, 其中
, 它也可以寫成Tensor
Meta-path Generation
此圖即表示GT(Graph Transformer) Layer宪巨，它先從tensor
(每一片就是一種edge type)中用權(quán)重選擇adjacency matrices(即edge type)。權(quán)重選擇的方式也可以理解成卷積溜畅，卷積后的兩個matrices分別是兩個圖解構(gòu)捏卓，表示為
和
。
選擇matrices的兩個卷積核是用softmax計算得出的(比如圖中例子慈格，一個卷積核說取最前面的matrices怠晴，一個卷積核說取最后面那個matrices)，但實際上是帶有權(quán)重分配的峦椰。
然后再將兩個matrices組成新的圖結(jié)構(gòu)(即兩個鄰接矩陣的矩陣乘法龄寞，
)。
用數(shù)學(xué)形式可以表示為:
- 選擇的Q可以表示為：
即得出的是將
和權(quán)重參數(shù)
送去convolution layer卷積得到的
- 每一個
可以表示成：
其中是edge的類型集合汤功，
是edge第
種類型
在第
層的權(quán)重物邑。
以圖中為例：有4個{
}, 即對應(yīng)4層matrices: {
}，
={
}
- 如果不是分兩個Q滔金，而是多個色解，則最后得到的結(jié)果新A可表示為：
Multi-channel
為了同時生成多種類型的元路徑，圖1中1×1卷積的輸出通道設(shè)置為C餐茵。
然后科阎，GT層產(chǎn)生一組meta-path，中間鄰接矩陣Q1和Q2成為鄰接張量和
忿族，如圖2所示锣笨。通過多個不同的圖結(jié)構(gòu)學(xué)習(xí)不同的節(jié)點表示是有益的。在
個GT層堆棧之后道批，將GCN應(yīng)用于元路徑張量
的每個通道错英，并將多個節(jié)點的representation拼接起來。
結(jié)果的生成可表示為：
其中是concatenation操作隆豹。
表示channel數(shù)量椭岩。
, 表示張量
的第
個通道。
是
的degree matrix，
是訓(xùn)練權(quán)重矩陣判哥，
表示特征矩陣献雅。
Evaluation
研究問題:
Q1：GTN生成的新圖結(jié)構(gòu)對學(xué)習(xí)node representation是否有效？
Q2：GTN能否根據(jù)數(shù)據(jù)集自適應(yīng)地產(chǎn)生可變長度的元路徑塌计？
Q3：如何從GTNs生成的鄰接矩陣來解釋每個元路徑的重要性挺身？
Dataset
GTN和其他節(jié)點分類基線的性能
可以看到GTNs獲得最高性能。
可解釋元路徑
Note: 這里的不同字母表示不同種類的node.
