超圖卷積網絡(HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs)

1. 簡介 (Introduction)

1.1 背景 (Backgrounds)

在許多諸如co-authorship網絡，co-citation網絡等現實世界的網絡中，關系是復雜的并且超出了成對關聯。超圖（Hypergraph）提供了一種靈活而自然的建模工具來對這種復雜的關系進行建模。在許多真實的網絡中，這種復雜關系普遍存在，因此激發(fā)了使用超圖學習的問題。一種流行的學習方法是基于超圖的半監(jiān)督學習(SSL)，其目標是對超圖中未標記的頂點分配標簽。受圖卷積網絡(GCN)對于圖上的半監(jiān)督學習十分有效的啟發(fā)，我們提出了HyperGCN，這是一種基于超圖的譜論（sepctral theory）來訓練用于超圖上半監(jiān)督學習的GCN的新方法。我們通過在真實世界的超圖上進行SSL和組合優(yōu)化的詳細實驗來證明HyperGCN的有效性，并分析它何時會比最新基準更有效。

1.2 主要貢獻 (Contributions)

我們提出了HyperGCN，利用超圖的譜理論在超圖上訓練GCN，并且介紹了其變體：FastHyperGCN
在真實世界超圖上用我們的方法解決了SSL和組合優(yōu)化問題。且通過實驗證明了我們的算法比較高效
全面討論了我們的方法與HGNN的區(qū)別與優(yōu)勢

2. 相關工作 (Related work)

2.1 圖卷積網絡(GCN)

2.2 圖上半監(jiān)督學習(SSL on graphs)

圖/超圖上半監(jiān)督學習的輸入為一個圖(G),其中包括少量的labelled節(jié)點，大量的unlabelled節(jié)點。通過圖上半監(jiān)督學習，我們期望為unlabelled節(jié)點分配合適的label。這有助于我們使用大量的unlabelled數據，從而服務于下游任務。

SSL on graphs/hypergraphs 基于這樣一個假設：鄰域節(jié)點共享相同的label

對于SSL on graphs，q分類問題，我們可以選用交叉熵作為損失函數

2.3 圖與超圖常見符號對比(Summary of symbols)

3. 超圖卷積網絡 (HyperGCN: Hypergraph Convolutional Network)

3.1 超圖拉普拉斯變換

為了實現我們的假設目標：

the hypernodes in the same hyperedge having similar representations.

我們可以使用如下隱式正則器：

[sum_{ein E}max_{i,j in e}||h_i-h_j||^2
]

這是因為，要使得該式子盡可能的小，必須滿足每一條超邊各個節(jié)點的label彼此接近。

然而，我們還可以使用另一種方法：超圖拉普拉斯變換 來作為隱式正則器來實現這個目標。

簡單圖上的拉普拉斯矩陣可以視作一個線性變換，而超圖的拉普拉斯卻是一個非線形變換(L: R^n o R^n)。

定義：給定一個定義在超圖節(jié)點上的實值信號(S in R^n)，經過超圖拉普拉斯變換后的信號(L(S))計算如下：

首先將超圖中每一條超邊轉化為一條簡單邊。方法是選擇距離最遠的兩個節(jié)點，在這兩個節(jié)點之間連接一條邊，邊權即為原始的超邊邊權。
然后超圖就轉化成了簡單帶權圖(G_s)，我們對該簡單圖求標準化的拉普拉斯矩陣(L_0 = I - D^{-frac{1}{2}}A_sD^{-frac{1}{2}}) 。
超圖拉普拉斯變換即用所得到的(L_0)左乘(S)，即(L(S) = L_0 S)

3.2 超圖卷積(1-HyperGCN)

超圖在拉普拉斯變換后會化為簡單圖(G_s)。而本文所說的超圖卷積實際上就是先將超圖轉化為帶權簡單圖(G_s)后，再對簡單圖(G_s)做GCN。如圖為HyperGCN在某一個節(jié)點(v)上的單次更新操作。

3.3 帶中介超圖卷積(HyperGCN: Enhancing 1-HyperGCN with mediators)

上面的模型在生成簡單圖時將同一條邊上除了選取的兩個代表節(jié)點外其他節(jié)點都舍去了，這造成了信息的損失，所以這里提出了將這些點(K_e:={kin e: k
eq i_e,k
eq j_e})作為“中介”，將這些點分別跟(i_e,j_e)都連接起來，如下圖所示。

由于Laplacian矩陣中元素是經過正則化的，所以要求每個超邊中的小邊權重和都要為1，而對于具有中介的圖來說，在超邊中每增加一個點都要多兩條邊，即(a_n-a_{n-1}=2:=d,a_2 = 1)求解等差數列可以得到邊數量為(2|e|-3)，所以權重選擇為(frac{1}{2|e|-3})。(|e|)表示該超邊對應連接的節(jié)點數。

3.4 快速超圖卷積(FastHyperGCN)

我們使用最初始的特征X（無權）去構造Laplacian 矩陣(有中介)，我們將這個方法叫做FastHyperGCN，因為這X無需在每一輪中進行更新，所以這個方法速度會比其他快。然而，由于(X)始終是最初始的特征，難免會在效果上不如HyperGCN。

---- suffer now and live the rest of your life as a champion ----

總結

以上是生活随笔為你收集整理的超图卷积网络(HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。