超圖嵌入論文閱讀2：超圖神經網絡
原文：Hypergraph Neural Networks ——AAAI2019（CCF-A）
源碼：https://github.com/iMoonLab/HGNN 500+star
概述
貢獻：用于數據表示學習的超圖神經網絡 (HGNN) 框架，對超圖結構中的高階數據相關性進行編碼
-
定義超邊卷積來處理表示學習過程中的數據相關性
-
夠學習考慮高階數據結構的隱藏層表示，是一個通用框架
——GCN可以看作是 HGNN 的一個特例，其中簡單圖中的邊可以被視為僅連接兩個頂點的 2 階超邊
-
引文圖、圖像識別數據集上實驗，優(yōu)于圖卷積網絡（GCN）
-
others：在處理多模態(tài)數據時具有優(yōu)勢
背景：
圖卷積能夠使用神經網絡模型對不同輸入數據的圖結構進行編碼，用于無監(jiān)督、半監(jiān)督、監(jiān)督學習，在表示學習方面顯示出優(yōu)越性。傳統(tǒng)圖卷積網絡，使用成對連接，難以表征多模態(tài)數據：
- 數據相關性可能比成對關系更復雜，很難用圖結構建模
- 數據表示往往是多模態(tài)的
——傳統(tǒng)的圖結構具有規(guī)定數據相關性的局限性，這限制了圖卷積網絡的應用。
超圖優(yōu)勢：
-
超圖可以使用其可變度數超邊對高階數據相關性（超出成對連接）進行編碼
-
使用超圖的靈活性超邊很容易擴展到多模態(tài)和異構數據表示：
如：可以通過組合鄰接矩陣來聯(lián)合使用多模態(tài)數據來生成超圖
——圖已被用于許多計算機視覺任務，例如分類和檢索任務
超圖問題：傳統(tǒng)的超圖學習方法計算復雜度和存儲成本較高，難以廣泛應用
相關研究：
-
超圖學習
前期發(fā)展：
- 2007首次引入，轉導推理旨在最小化超圖上連接更強的頂點之間的標簽差異
- 2009進一步用于視頻對象分割
- 2010對圖像關系進行建模，并進行轉導推理過程進行圖像排序
注意力機制引入：
- 2013對權重進行正則化
- 2008提出假設：高度相關的超邊應該具有相似的權重
多模態(tài)：
- 2012引入多超圖結構為不同的子超圖分配權重
-
圖神經網絡
前期發(fā)展：
- 2005 2009應用循環(huán)神經網絡來處理圖
譜方法：
- 2014第一個圖 CNN：圖拉普拉斯特征基
- 2015譜濾波器可以使用平滑系數參數化
- 2016圖拉普拉斯算子的切比雪夫擴展進一步用于近似譜濾波器
- 2017chebyshev 多項式被簡化為 1 階多項式，形成一個有效的逐層傳播模型
空間方法：
- 2016使用轉移矩陣的冪來定義節(jié)點的鄰域
- 2017使用高斯混合模型形式的局部路徑算子來概括空間域中的卷積
- 2018注意力機制被引入圖以構建基于注意力的架構，以在圖上執(zhí)行節(jié)點分類任務
HGNN
超圖學習
基礎知識（略）：
與簡單圖不同，超圖中的超邊連接兩個或多個頂點。超圖定義為 G = (V, E, W)
超圖 G 可以用 |V| × |E|關聯(lián)矩陣 H 表示
h
(
v
,
e
)
=
{
1
,
if?
v
∈
e
0
,
if?
v
?
e
,
h(v,e)=\left\{\begin{array}{l} 1, \text{if} \space v \in e \\ 0, \text{if} \space v \notin e, \\\end{array}\right.
h(v,e)={1,if?v∈e0,if?v∈/e,?
d
(
v
)
=
∑
e
∈
E
ω
(
e
)
h
(
v
,
e
)
d(v) =∑_{e∈E} ω(e)h(v, e)
d(v)=∑e∈E?ω(e)h(v,e)、
δ
(
e
)
=
∑
v
∈
V
h
(
v
,
e
)
δ(e) = ∑_{v∈V} h(v, e)
δ(e)=∑v∈V?h(v,e)。
D
e
\mathbf{D}_e
De? 和
D
v
\mathbf{D}_v
Dv? 分別表示邊度和頂點度的對角矩陣
超圖節(jié)點分類問題：節(jié)點標簽應該在超圖結構上平滑
——用以下正則化框架描述：
arg
?
min
?
f
{
R
e
m
p
(
f
)
+
Ω
(
f
)
}
\arg \min_f \{\mathcal{R}_{emp}(f)+\Omega(f)\}
argfmin?{Remp?(f)+Ω(f)}
其中
Ω
(
f
)
\Omega(f)
Ω(f) 是超圖上的正則化，
R
e
m
p
(
f
)
\mathcal{R}_{emp}(f)
Remp?(f) 表示監(jiān)督經驗損失，
f
(
?
)
f (·)
f(?) 是分類函數。正則化
Ω
(
f
)
\Omega(f)
Ω(f)定義為:
Ω
(
f
)
=
1
2
∑
e
∈
ε
∑
{
u
,
v
}
∈
V
w
(
e
)
h
(
u
,
e
)
h
(
v
,
e
)
δ
(
e
)
(
f
(
u
)
d
(
u
)
?
f
(
v
)
d
(
v
)
)
2
\Omega(f)=\frac{1}{2} \sum_{e \in \varepsilon} \sum_{\{u,v\}\in \mathcal{V}} \frac{w(e)h(u,e)h(v,e)}{\delta(e)} \left(\frac{f(u)}{\sqrt{d(u)}}-\frac{f(v)}{\sqrt{d(v)}}\right)^2
Ω(f)=21?e∈ε∑?{u,v}∈V∑?δ(e)w(e)h(u,e)h(v,e)?(d(u)?f(u)??d(v)?f(v)?)2
我們令
Θ
=
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
\mathbf \Theta=\mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1}\mathbf H^{\mathsf T}\mathbf D_v^{-1/2}
Θ=Dv?1/2?HWDe?1?HTDv?1/2?，
Δ
=
I
?
Θ
\mathbf \Delta = \mathbf I -\mathbf \Theta
Δ=I?Θ 歸一化
Ω
(
f
)
\Omega(f)
Ω(f) 可以寫成：
Ω
(
f
)
=
f
T
Δ
\Omega(f)=f^{\text T} \mathbf \Delta
Ω(f)=fTΔ
其中
Δ
\mathbf \Delta
Δ 是半正定的，通常稱為超圖拉普拉斯算子。
超圖譜卷積
給定一個具有 n 個頂點的超圖，拉普拉斯算子 Δ \mathbf \Delta Δ 是半正定的。對其進行特征分解 Δ = Φ Λ Φ T \mathbf \Delta =\mathbf \Phi \mathbf \Lambda \mathbf \Phi^{\mathsf T} Δ=ΦΛΦT 可得到正交特征向量 Φ = diag ( ? 1 , . . . , ? n ) \mathbf \Phi = \text{diag}(\phi_1,..., \phi_n) Φ=diag(?1?,...,?n?) 和對角矩陣 Λ = diag ( λ 1 , . . . , λ n ) \mathbf \Lambda =\text{diag}(\lambda_1,..., \lambda_n) Λ=diag(λ1?,...,λn?) 對應非負特征值。
信號
x
=
(
x
1
,
.
.
.
,
x
n
)
\text x = (x_1,..., x_n)
x=(x1?,...,xn?) 在超圖中定義為
x
^
=
Φ
T
x
\hat {\text x}=\mathbf \Phi^{\mathsf T}\text x
x^=ΦTx ，其中特征向量被視為傅里葉基，特征值被解釋為頻率。信號x和濾波器g的譜卷積可以表示為：
g
?
x
=
Φ
(
(
Φ
T
g
)
⊙
(
Φ
T
x
)
)
=
Φ
g
(
Λ
)
Φ
T
x
,
\text g\star \text x=\mathbf \Phi((\mathbf \Phi^{\mathsf T}\text g)\odot (\mathbf \Phi^{\mathsf T} \text x))=\mathbf \Phi g(\mathbf \Lambda) \mathbf \Phi^{\mathsf T}\text x,
g?x=Φ((ΦTg)⊙(ΦTx))=Φg(Λ)ΦTx,
- ⊙ \odot ⊙ 表示逐元素的Hadamard乘積
- g ( Λ ) = diag ( g ( λ 1 ) , . . . , g ( λ n ) ) g(\mathbf \Lambda)=\text{diag}(\text g(\lambda_1),...,\text g(\lambda_n)) g(Λ)=diag(g(λ1?),...,g(λn?)) 是傅立葉系數的函數
然而正向和反向傅里葉變換的計算成本為
O
(
n
2
)
O(n^2)
O(n2)。可以用某論文中的方法使用K 階多項式參數化
g
(
Λ
)
g(\mathbf \Lambda)
g(Λ)，我們使用截斷切比雪夫展開作為這樣的多項式。Chebyshv多項式
T
k
(
x
)
T_k(x)
Tk?(x)由
T
k
(
x
)
=
2
x
T
k
?
1
(
x
)
?
T
k
?
2
(
x
)
T_k(x) = 2xT_{k?1}(x)?T_{k?2}(x)
Tk?(x)=2xTk?1?(x)?Tk?2?(x)遞歸計算，其中
T
0
(
x
)
=
1
T_0(x) = 1
T0?(x)=1和
T
1
(
x
)
=
x
T_1(x) = x
T1?(x)=x。因此，
g
(
Λ
)
g(\mathbf \Lambda)
g(Λ)可以參數化為：
g
?
x
≈
∑
k
=
0
K
θ
k
T
k
(
Δ
^
)
x
,
\text g\star \text x \approx \sum_{k=0}^K \theta_k T_k(\hat {\mathbf \Delta})\text{x},
g?x≈k=0∑K?θk?Tk?(Δ^)x,
其中
T
k
(
Δ
^
)
T_k(\hat {\mathbf \Delta})
Tk?(Δ^) 是k階切比雪夫多項式，里面的縮放拉普拉斯算子為
Δ
^
=
2
λ
m
a
x
Δ
?
I
\hat{\mathbf \Delta}=\frac{2}{\lambda_{max}}\mathbf \Delta-\mathbf I
Δ^=λmax?2?Δ?I。排除了拉普拉斯特征向量的擴展計算，只包括矩陣冪、加法和乘法，提升運算速度。我們可以進一步讓 K = 1 來限制卷積操作的順序，因為超圖中的拉普拉斯算子已經可以很好地表示節(jié)點之間的高階相關性。另一篇論文檢建議，由于神經網絡的規(guī)模適應性，令
λ
m
a
x
≈
2
\lambda_{max} \approx 2
λmax?≈2，卷積運算可以進一步簡化為：
g
?
x
≈
θ
0
x
?
θ
1
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
x
,
\text g\star \text x \approx \theta_0 \text x-\theta_1 \mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2} \text x,
g?x≈θ0?x?θ1?Dv?1/2?HWDe?1?HTDv?1/2?x,
其中
θ
0
θ_0
θ0? 和
θ
1
θ_1
θ1? 是所有節(jié)點的過濾器參數。我們進一步使用單個參數 θ 來避免過擬合問題，定義為：
{
θ
1
=
?
1
2
θ
θ
0
=
1
2
θ
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
,
\left\{\begin{array}{l} \theta_1 = -\frac{1}{2}\theta \\ \theta_0 = \frac{1}{2}\theta \mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2}, \\\end{array}\right.
{θ1?=?21?θθ0?=21?θDv?1/2?HWDe?1?HTDv?1/2?,?
卷積運算可以簡化為下式：
g
?
x
≈
1
2
θ
D
v
?
1
/
2
H
(
W
+
I
)
D
e
?
1
H
T
D
v
?
1
/
2
x
≈
θ
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
x
\text g\star \text x \approx \frac{1}{2}\theta \mathbf D_v^{-1/2}\mathbf H \mathbf {(W+I)} \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2} \text x\\\approx \theta \mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2} \text x
g?x≈21?θDv?1/2?H(W+I)De?1?HTDv?1/2?x≈θDv?1/2?HWDe?1?HTDv?1/2?x
其中
(
W
+
I
)
\mathbf{(W + I)}
(W+I) 可以看作是超邊的權重。
W
\mathbf W
W 被初始化為單位矩陣，這意味著所有超邊的相等權重。
當我們有一個具有n個節(jié)點和C1維特征的超圖信號
X
∈
R
n
×
C
1
\mathbf X \in \mathbb R^{n \times C_1}
X∈Rn×C1? 時，我們的超邊卷積可以表示為：
Y
=
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
X
Θ
,
\mathbf{Y=D_v^{-1/2}HWD_e^{-1}H^{\mathsf T}D_v^{-1/2}X\Theta},
Y=Dv?1/2?HWDe?1?HTDv?1/2?XΘ,
其中
W
=
diag
(
w
1
,
.
.
.
,
w
n
)
\mathbf W =\text{diag}(\text{w}_1,...,\text{w}_n)
W=diag(w1?,...,wn?)，
Θ
∈
R
C
1
×
C
2
\Theta \in \mathbb R^{C_1 \times C_2}
Θ∈RC1?×C2? 是訓練過程中要學習的參數。過濾器
Θ
\mathbf \Theta
Θ 應用于超圖中的節(jié)點以提取特征。卷積后，我們可以得到
Y
∈
R
n
×
C
2
\mathbf Y \in \mathbb R^{n \times C_2}
Y∈Rn×C2? ，可用于分類。
超圖神經網絡分析
多模態(tài)數據集分為訓練數據和測試數據，每個數據包含多個具有特征的節(jié)點。然后從多模態(tài)數據集的復雜相關性構建多個超邊結構組。我們組合超邊組以生成超圖鄰接矩陣 H \mathbf H H。將超圖鄰接矩陣 H \mathbf H H和節(jié)點特征輸入到HGNN中，得到節(jié)點輸出標簽。
我們可以在以下公式中構建一個超邊卷積層
f
(
X
,
W
,
Θ
)
f \mathbf{(X, W, \Theta)}
f(X,W,Θ)：
X
(
l
+
1
)
=
σ
(
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
X
(
l
)
Θ
(
l
)
)
,
\mathbf X^{(l+1)}=\sigma (\mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2} \mathbf X^{(l)} \mathbf \Theta^{(l)}),
X(l+1)=σ(Dv?1/2?HWDe?1?HTDv?1/2?X(l)Θ(l)),
其中
X
(
l
)
∈
R
N
×
C
\mathbf X^{(l)} \in \mathbb R^{N \times C}
X(l)∈RN×C 是
l
l
l 層的超圖信號，
X
(
0
)
=
X
\mathbf X^{(0)} = \mathbf X
X(0)=X，
σ
\sigma
σ 表示非線性激活函數。
卷積層結構：
HGNN模型基于超圖上的譜卷積。HGNN 層可以執(zhí)行 節(jié)點-邊-節(jié)點 的變換，這可以有效地提取超圖上的高階相關性。
- 初始節(jié)點特征 X ( 1 ) \mathbf X^{(1)} X(1) 由可學習的濾波器矩陣 Θ ( 1 ) \mathbf \Theta^{(1)} Θ(1) 處理以提取 C 2 C_2 C2?- 維特征
- 據超邊收集節(jié)點特征以形成超邊特征 R E × C 2 \mathbb R^{E \times C_2} RE×C2? ，這是通過乘以矩陣 H T ∈ R E × N \mathbf {H^{\mathsf T}} \in \mathbb R^{\mathbf {E \times N}} HT∈RE×N 來實現的
- 通過聚合其相關的超邊特征來獲得輸出節(jié)點特征，該特征是通過乘以矩陣 H \mathbf H H 來實現的
—— D v \mathbf D_v Dv?和 D e \mathbf D_e De?在公式11中起到了歸一化的作用
與現有方法的關系：
超邊只連接兩個頂點時，超圖被簡化為一個簡單的圖，拉普拉斯算子 Δ \mathbf \Delta Δ 也與簡單圖的拉普拉斯算子一致（1/2倍相乘）
- HGNN可以自然地對數據之間的高階關系進行建模，有效地利用和編碼形成特征提取
- 與傳統(tǒng)的超圖方法相比，我們的模型在計算上非常高效，沒有拉普拉斯算子 Δ \mathbf \Delta Δ 的逆運算
- 在超邊生成的靈活性下對多模態(tài)特征具有很大的可擴展性
實施
- 超圖構造：圖片分類任務中，提取每個對象的特征，根據歐氏距離構建超圖。每個頂點代表一個視覺對象，每個超邊通過連接一個頂點及其 K 個最近鄰居來形成，這帶來了 N 個鏈接 K + 1 個頂點的超邊。引文圖也類似地構造。
- 節(jié)點分類模型：數據集分為訓練數據和測試數據，構建超圖。按上圖搭建網絡，構建了一個兩層HGNN模型，使用softmax 函數生成預測標簽。使用交叉熵損失函數，將各種超邊融合在一起，對數據的復雜關系進行建模。
實驗
兩個任務：引文網絡分類和視覺對象識別，與圖卷積網絡和其他最先進的方法進行比較。
引文網絡分類
Cora 和 Pubmed兩個數據集：
- 每個數據的特征是文檔的詞袋表示
- 每次選擇圖中的每個頂點作為質心，其連通頂點用于生成一條超邊，包括質心本身
- 獲得與原始圖規(guī)模相同的關聯(lián)矩陣
- Cora2708 個5%標記，Pubmed19717 個0.3%標記
參數設置：兩層 HGNN
- 隱藏層的特征維度設置為 16
- dropout 丟棄率 p = 0.5
- ReLU 作為非線性激活函數
- Adam 優(yōu)化器最小化交叉熵損失函數
- 學習率為 0.001
結果討論：Core和Pumbed上100次運行的平均分類精度
-
與最先進的方法相比，HGNN模型可以達到最佳或相當的性能
——與 GCN 相比，HGNN 方法在 Cora 數據集上略有改進，在 Pubmed 數據集上提高了 1.1%
-
HGNN 獲得的增益并不是很顯著——因為構建的超圖和傳統(tǒng)圖差不多
視覺對象分類
數據集：
- 普林斯頓ModelNet40
- 國立臺灣大學(NTU) 3D模型數據集
超圖構建：
-
特征使用多視圖卷積神經網絡 (MVCNN) 和組視圖卷積神經網絡 (GVCNN)提取
-
根據節(jié)點的距離構造一個概率圖，生成親和矩陣A來表示不同頂點之間的關系
A i j = exp ? ( ? 2 D i j 2 Δ ) A_{ij}=\exp(-\frac{2D_{ij}^2}{\Delta}) Aij?=exp(?Δ2Dij2??)
其中Dij表示節(jié)點i和節(jié)點j之間的歐氏距離。Δ 是節(jié)點之間的平均成對距離
-
兩種超圖構建方法：
- 基于單模態(tài)特征：每次選擇一個數據集中的一個對象作為質心，選取特征空間中的10個最近鄰生成一個超邊，包括質心本身
- 基于多模態(tài)特征：使用多個特征來生成建模復雜多模態(tài)相關性的超圖 G，只需要將超圖關聯(lián)矩陣拼接即可
結果討論：
- HGNN方法在ModelNet40數據集中優(yōu)于最先進的目標識別方法：分別獲得 4.8% 和 3.2% 的增益
- 與 GCN 相比，所提出的方法在所有實驗中都取得了更好的性能：一個特征取得輕微改進，多個特征改進明顯
優(yōu)勢分析
- 超圖結構能夠傳達數據之間的復雜關系和高階相關性，與圖結構或沒有圖結構的方法相比，可以更好地表示底層的數據關系。
- 當多模態(tài)數據/特征可用時，HGNN 的優(yōu)勢在于通過其靈活的超邊將這種多模態(tài)信息組合在同一結構中。
- 與傳統(tǒng)的超圖學習方法可能存在計算復雜度高、存儲成本高的問題相比，所提出的HGNN框架通過超邊卷積運算效率更高。
結論
超圖神經網絡 (HGNN) 的框架文章來源：http://www.zghlxwxcb.cn/news/detail-692079.html
- 將卷積運算推廣到超圖學習過程：譜域的卷積用超圖拉普拉斯算子進行，進一步用截斷的切比雪夫多項式逼近
- 是一個更通用的框架：與傳統(tǒng)圖相比，能夠通過超圖結構處理復雜和高階相關性以進行表示學習
- 對引文網絡分類和視覺對象識別任務進行了實驗：HGNN 模型有更好的性能
——HGNN能夠將復雜的數據相關性納入表示學習，從而在視覺識別、檢索和數據分類等許多任務中帶來潛在的廣泛應用。文章來源地址http://www.zghlxwxcb.cn/news/detail-692079.html
到了這里，關于超圖嵌入論文閱讀2：超圖神經網絡的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
![[自注意力神經網絡]Segment Anything(SAM)論文閱讀](https://imgs.yssmx.com/Uploads/2024/02/423006-1.png)
![[論文閱讀] (27) AAAI20 Order Matters: 基于圖神經網絡的二進制代碼相似性檢測（騰訊科恩實驗室）](https://imgs.yssmx.com/Uploads/2024/02/620112-1.png)
