HyperGCN（2019-NIPS）

HyperGCN: A New Method of Training Graph Convolutional Networks on Hypergraphs

• 動機
• 貢獻
• 模型：
• • HyperGCN
  • 超圖拉普拉斯
  • 1-HyperGCN
  • HyperGCN: Enhancing 1-HyperGCN with mediators
  • FastHyperGCN
• 實驗
• • 資料集
  • baselines
  • HyperGCN比HGNN的優勢
  • 組合優化問題： densest k -subhypergraph problem（NP-hard）
  • 局限
• HyperGCN算法：
• • FastHyperGCN
  • 1-HyperGCN

論文：https://papers.nips.cc/paper/8430-hypergcn-a-new-method-for-training-graph-convolutional-networks-on-hypergraphs

code:https://github.com/malllabiisc/HyperGCN

動機

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

貢獻

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

我們方法的動機是基于節點相似度，而且我們發現我們方法可被用于超圖編碼不相似情況下的組合優化。

模型：

hypergraph 與 graph的符号對應

1.圖卷積

兩層的簡單圖卷積

其中：

• A ˉ = D ~ − 1 2 D ~ A ~ − 1 2 ,   A ~ = A + I \bar A=\tilde{D}^{-\frac{1}{2}}\tilde{D}\tilde{A}^{-\frac{1}{2}},\ \tilde{A}=A+I Aˉ=D~−21​D~A~−21​, A~=A+I,即标準化後的鄰接陣。

  2.半監督訓練：

  

  這裡是多分類問題，有 q 類，最小化标簽集 V L V_L VL​交叉熵。卷積層權重訓練使用梯度下降。

HyperGCN

預備：

• H = ( V , E ) \mathcal{H}=(V,E) H=(V,E)表示無向圖
• ∣ V ∣ = n , ∣ E ∣ = m |V|=n,|E|=m ∣V∣=n,∣E∣=m
• 有标簽集 V L V_L VL​

• 特征矩陣： X ∈ R n × p X \in \mathbb{R}^{n \times p} X∈Rn×p , 每個頂點 v ∈ V = { 1 , . . . , n } v\in V = \{1,...,n\} v∈V={1,...,n}

  任務：預測所有無标簽頂點，即， V V V \ V L V_L VL​

  原則：在相同的邊的節點是相似的，即具有相同的标簽。

  用 { h v : v ∈ V } \{h_v:v\in V\} {hv​:v∈V}表示V中的節點一些表示，最後顯示正則化目标為

  ∑ e ∈ E m a x i , j ∈ e ∣ ∣ h i − h j ∣ ∣ 2 \sum_{e\in E}max_{i,j\in e}||h_i-h_j||^2 e∈E∑​maxi,j∈e​∣∣hi​−hj​∣∣2

  然而我們采用了隐式正則化，即通過使用一個适當定義的GCN超圖的拉普拉斯變換，實作相同邊上的節點具有相似的表達。

超圖拉普拉斯

graph上的laplacian矩陣可以視作一個線性變換，而超圖的Laplacian卻是一個非線性變換： L : R n → R n \mathbb{L}:\mathbb{R}^n\rightarrow \mathbb R^n L:Rn→Rn

定義：超圖拉普拉斯

給定一個定義在超圖節點上的實值信号 S ∈ R n S\in \mathbb R^n S∈Rn， L ( S ) \mathbb{L}(S) L(S)計算如下：

1. 對圖上任意邊 e ∈ E e\in E e∈E,令 ( i e , j e ) : = a r g m a x i , j ∈ e ∣ S i − S j ∣ (i_e,j_e):=argmax_{i,j\in e}|S_i-S_j| (ie​,je​):=argmaxi,j∈e​∣Si​−Sj​∣,breaking ties randomly,即同一條邊上距離最遠的兩個頂點的編号表示為 ( i e , j e ) (i_e,j_e) (ie​,je​).
2. 頂點集V上的定義的權重圖 G S G_S GS​, 通過在邊 { { i e , j e } : e ∈ E } \{\{i_e,j_e\}:e\in E\} {{ie​,je​}:e∈E}上加上權重 w ( i e , j e ) : = w ( e ) w({i_e,j_e}):=w(e) w(ie​,je​):=w(e),這裡 w ( e ) w(e) w(e)是超圖e的權重。 A S A_S AS​表示 G S G_S GS​的帶權鄰接陣。實際上這裡相當于将超圖變成了普通的簡單帶權圖 G S G_S GS​。

3. 對稱正則化的超圖拉普拉斯變換表示為： L ( S ) : = ( I − D − 1 2 A S D − 1 2 ) \mathbb L(S):=(I-D^{-\frac{1}{2}}A_SD^{-\frac{1}{2}}) L(S):=(I−D−21​AS​D−21​)

   用上面的定義，給出一個超圖節點上的信号S就可以計算出其Laplacian變換後的值 L ( S ) \mathbb L(S) L(S)了。

1-HyperGCN

我們将簡單圖 G S G_S GS​的正則化帶權鄰接陣表示為 A ˉ S \bar{A}_S AˉS​,然後再圖 G S G_S GS​上使用GCN,(公式1), 在神經資訊傳播架構中我們将超節點v的資訊更新表示為：

h v τ + 1 = σ ( ( Θ ( τ ) ) T ∑ u ∈ N ( v ) ( [ A ˉ s ( τ ) ] u , v ⋅ h u ( τ ) ) ) h_v^{\tau+1}=\sigma((\Theta^{(\tau)})^T \sum_{u \in \mathcal{N}(v)}([\bar{A}_s^{(\tau)}]_{u,v}\cdot h_u^{(\tau)})) hvτ+1​=σ((Θ(τ))Tu∈N(v)∑​([Aˉs(τ)​]u,v​⋅hu(τ)​))

其中

• τ \tau τ是epoch數
• h v τ + 1 h_v^{\tau+1} hvτ+1​是節點 v v v新的隐含層節點表示。
• N ( v ) \mathcal{N}(v) N(v)是v 的鄰域
• [ A ˉ s ( τ ) ] u , v [\bar{A}_s^{(\tau)}]_{u,v} [Aˉs(τ)​]u,v​是正則化後邊 { v , u } \{v,u\} {v,u} 的權重
• h u ( τ ) h_u^{(\tau)} hu(τ)​是前一階段鄰域節點的隐含表示，

  

  上圖中超點v有5個超邊與其連接配接，然後用簡單邊去代替超邊，即在第 τ \tau τepoch時，邊為 ( i e , j e ) = a r g m a x i , j ∈ e ∣ ∣ ( Θ ( τ ) ) T ( h i ( τ ) − h j ( τ ) ) ∣ ∣ 2 (i_e,j_e)=argmax_{i,j\in e}||(\Theta^{(\tau)})^T(h_i^{(\tau)}-h_j^{(\tau)})||_2 (ie​,je​)=argmaxi,j∈e​∣∣(Θ(τ))T(hi(τ)​−hj(τ)​)∣∣2​

  得到第 τ \tau τ輪的簡單圖之後，我們在簡單圖上實作GCN，訓練到收斂。

  這裡使用的隐式正則化不僅可以将超圖結利用到SSL中節點分類，還可以通過這個GCN将節點的特征資訊也包含進來，比如：文本屬性等。

HyperGCN: Enhancing 1-HyperGCN with mediators

上面的模型在生成簡單圖時将同一條邊上除了選取的兩個代表節點外其他節點都舍去了，這造成了資訊的損失，是以這裡提出了将這些點 K e : = { k ∈ e : k ≠ i e , k ≠ j e } K_e:=\{k\in e:k\ne i_e,k\ne j_e\} Ke​:={k∈e:k​=ie​,k​=je​}作為“中介”，将這些點分别跟 i e , j e i_e,j_e ie​,je​都連接配接起來。

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

FastHyperGCN

我們使用最初始的特征X（無權）去構造Laplacian 矩陣(有中介)，我們将這個方法叫做FastHyperGCN，因為這X無需在每一輪中進行更新，是以這個方法速度會比其他快。

實驗

資料集

Table 3: Real-world hypergraph datasets used in our work. Distribution of hyperedge sizes is not

symmetric either side of the mean and has a strong positive skewness.

baselines

• Hypergraph neural networks (HGNN)
• Multi-layer perceptron (MLP)
• Multi-layer perceptron + explicit hypergraph Laplacian

• Confidence Interval-based method (CI)

  訓練次數200epochs，100次不同的訓練測試集劃分，測試結構

  

  結果顯示1-HyperGCN效果最差，這是很顯然是因為其隻在超邊中選取了兩個點，而其他兩個模型則把所有點的資訊都融合進去了。

HyperGCN比HGNN的優勢

我們在訓練集中加入噪聲，我們超邊所有連接配接的點都是同一類節點的稱為純的，而超邊不是全是同一類的稱為有噪聲的，我們将訓練集中的一部分取樣成純的，另一部分取成有噪聲的，兩者的比例記為 η \eta η,從0.75到0.5,（純到不純），得到表5結果，發現加入越多噪聲對我們HpyerGCN越有利，這是因為HGCN其連接配接的是更多相似的節點。

組合優化問題： densest k -subhypergraph problem（NP-hard）

即在超圖G中選出k 個頂點，使得其對應的子超圖涵蓋了G中最多的超邊。

局限

模型的結果的好壞對權重的初始化依賴性很大。

HyperGCN算法：

先選距離遠點的兩個核心點，其他點再跟他相連（也就是在鄰接陣中配置設定權重），然後成為權重普通圖。每層，每個epoch進行更新。

FastHyperGCN

将核心點和同一個超邊中的其他點先連好，然後作為新的普通圖，使用GCN學習。

1-HyperGCN

隻連接配接核心點，同一個超邊中的其他點都直接丢棄（也就是drop edge）。每個epoch 每層進行更新。