Hypergraph Neural Networks
超图学习部分
定义超图
G
=
(
V
,
E
,
W
)
\mathcal{G=(V,E,}W)
G=(V,E,W),分别代表顶点、超边、权重。 超图可以用关联矩阵
H
H
H来表示:
h
(
n
,
θ
)
=
{
1
,
if?
v
∈
e
0
,
otherwise
h(n,\theta) = \begin{cases} 1, & \text{if } v\in e\\ 0, & \text{otherwise} \end{cases}
h(n,θ)={1,0,?if?v∈eotherwise?
节点的度
d
(
v
)
=
∑
e
∈
E
w
(
e
)
h
(
v
,
e
)
d(v)=\sum_{e\in \mathcal{E}}w(e)h(v,e)
d(v)=∑e∈E?w(e)h(v,e) 超边的度
δ
(
e
)
=
∑
v
∈
V
h
(
v
,
e
)
\delta(e)=\sum_{v\in \mathcal{V}}h(v,e)
δ(e)=∑v∈V?h(v,e)
超图顶点分为问题,可以被表示为一个正则化框架: 该公式可查看另一篇论文:超图的二分类论文
a
r
g
m
i
n
f
{
R
e
m
p
(
f
)
+
Ω
(
f
)
}
arg min_f\left\{R_{emp}(f)+\Omega(f)\right\}
argminf?{Remp?(f)+Ω(f)} 其中
R
e
m
p
(
f
)
R_{emp}(f)
Remp?(f)为经验损失:
R
e
m
p
(
f
)
=
1
N
∑
i
=
1
N
L
(
y
i
,
f
(
x
i
)
)
R_{emp}(f)=\frac{1}{N}\sum_{i=1}^NL(y_i,f(x_i))
Remp?(f)=N1?∑i=1N?L(yi?,f(xi?))
Ω
(
f
)
\Omega(f)
Ω(f)为超图上的正则化函数:
Ω
(
f
)
=
1
2
∑
e
∈
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 \mathcal{E}}\sum_{u,v \in \mathcal{V}}\frac{w(e)h(u,e)h(v,e)}{\delta (e)}(\frac{f(u)}{\sqrt{d(u)}}-\frac{f(v)}{\sqrt{d(v)}})^2
Ω(f)=21?e∈E∑?u,v∈V∑?δ(e)w(e)h(u,e)h(v,e)?(d(u)
?f(u)??d(v)
?f(v)?)2 上式可以简化为:
Ω
(
f
)
=
f
T
Δ
f
\Omega(f)=f^T\Delta f
Ω(f)=fTΔf 其中
Δ
=
I
?
L
\Delta=I-L
Δ=I?L,
L
=
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
L=D^{-1/2}_vHWD_e^{-1}H^TD^{-1/2}_v
L=Dv?1/2?HWDe?1?HTDv?1/2?
超图上的谱卷积
附上一个普通图的谱卷积:如何理解GCN(大神写的太好了!入门也可以看)
超图的傅里叶变换
对拉普拉斯矩阵进行特征分解,特征向量矩阵
Φ
=
d
i
a
g
(
?
1
,
.
.
.
,
?
n
)
\Phi=diag(\phi_1,...,\phi_n)
Φ=diag(?1?,...,?n?),特征值矩阵
Λ
=
d
i
a
g
(
λ
1
,
.
.
.
,
λ
n
)
\Lambda=diag(\lambda_1,...,\lambda_n)
Λ=diag(λ1?,...,λn?),特征值均为非负值。 由
Δ
Φ
=
Λ
Φ
\Delta \Phi=\Lambda \Phi
ΔΦ=ΛΦ可以得到:
Δ
=
Φ
Λ
Φ
T
\Delta=\Phi \Lambda \Phi^T
Δ=ΦΛΦT 把超图上的信号记为
X
=
(
X
1
,
.
.
.
,
X
n
)
X=(X_1,...,X_n)
X=(X1?,...,Xn?),表示每一个节点有一个信号值。
传统的傅里叶变换为:
F
(
w
)
=
∫
f
(
t
)
e
?
i
w
t
?
d
t
F(w)=\int f(t) e^{-iwt}\, {\rm d}t
F(w)=∫f(t)e?iwtdt。这里的
f
(
t
)
f(t)
f(t)表示信号,
e
?
i
w
t
e^{-iwt}
e?iwt为基函数,傅里叶变换为二者的积分形式。 仿照上述傅里叶变换,离散积分就是一种内积形式,将拉普拉斯矩阵的特征向量作为傅里叶基底,
F
(
λ
l
)
=
∑
i
=
1
N
X
i
u
l
(
i
)
F(\lambda_l)=\sum_{i=1}^N X_i u_l(i)
F(λl?)=i=1∑N?Xi?ul?(i) 其表示在特征值
λ
l
\lambda_l
λl?的情况下,
X
X
X的傅里叶变换就是与
λ
l
\lambda_l
λl?对应的特征向量进行内积运算。 推广到矩阵形式则有:
X
^
=
(
X
Φ
)
T
=
Φ
T
X
\hat{X}=(X\Phi)^T=\Phi^T X
X^=(XΦ)T=ΦTX,此时特征向量为傅里叶基底,而特征值则为频率。 逆变换为 :
X
=
Φ
X
^
X=\Phi\hat{X}
X=ΦX^
超图上的卷积
卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积。也就是说卷积为函数傅里叶变换的乘积的逆变换;对于函数
f
(
t
)
f(t)
f(t)和函数
h
(
t
)
h(t)
h(t)有:
f
?
h
=
F
?
1
[
f
^
(
w
)
h
^
(
w
)
]
=
1
2
π
∫
f
^
(
w
)
h
^
(
w
)
e
i
w
t
?
d
w
f*h=F^{-1}[\hat{f}(w)\hat{h}(w)]=\frac{1}{2\pi}\int \hat{f}(w)\hat{h}(w) e^{iwt}\,{\rm d}w
f?h=F?1[f^?(w)h^(w)]=2π1?∫f^?(w)h^(w)eiwtdw 仿照上述定义: 卷积核
g
g
g的傅里叶变换可以写为
g
^
=
d
i
a
g
(
g
^
(
λ
1
)
,
.
.
.
,
g
^
(
λ
n
)
)
\hat{g}=diag(\hat{g}(\lambda_1),...,\hat{g}(\lambda_n))
g^?=diag(g^?(λ1?),...,g^?(λn?)) 因此两者乘积为
g
^
?
X
=
g
^
Φ
T
X
\hat{g}*X=\hat{g}\Phi^TX
g^??X=g^?ΦTX,求其逆变换为
Φ
g
^
Φ
T
X
\Phi \hat{g}\Phi^TX
Φg^?ΦTX
可以将
g
^
\hat{g}
g^?变换为
g
(
Λ
)
=
d
i
a
g
(
g
(
λ
1
)
,
.
.
.
,
g
(
λ
n
)
)
g(\Lambda)=diag(g(\lambda_1),...,g(\lambda_n))
g(Λ)=diag(g(λ1?),...,g(λn?)),为特征值的对角矩阵 信号与滤波器的谱卷积可以表示为:
g
?
X
=
Φ
(
(
Φ
T
g
)
⊙
(
Φ
T
X
)
)
=
Φ
g
(
Λ
)
Φ
T
X
g\star X=\Phi((\Phi^Tg)\odot(\Phi^TX)) =\Phi g(\Lambda)\Phi^TX
g?X=Φ((ΦTg)⊙(ΦTX))=Φg(Λ)ΦTX 由于上式计算代价很大:(1)使用特征向量矩阵的乘法运算复杂度为
O
(
n
2
)
O(n^2)
O(n2);(2)计算规模较大的超图的拉普拉斯矩阵的特征分解需要很大的计算量。因此采用切比雪夫多项式的K阶阶段来对
g
(
Λ
)
g(\Lambda)
g(Λ)进行近似。
附上一个推导讲解文章链接:Chebyshev多项式作为GCN卷积核
切比雪夫多项式:
T
k
(
x
)
=
{
0
,
k
=
0
x
,
k
=
1
2
x
T
k
?
1
(
x
)
?
T
k
?
2
(
x
)
,
k
>
1
T_k(x) = \begin{cases} 0, & k=0\\ x, & k=1\\ 2xT_{k-1}(x)-T_{k-2}(x), & k>1 \end{cases}
Tk?(x)=??????0,x,2xTk?1?(x)?Tk?2?(x),?k=0k=1k>1? 得到一个新的卷积核为
g
θ
(
Λ
)
≈
∑
k
=
0
K
θ
k
T
k
(
Λ
~
)
g_\theta(\Lambda)\approx\sum^K_{k=0}\theta_kT_k(\tilde{\Lambda})
gθ?(Λ)≈k=0∑K?θk?Tk?(Λ~) 这里的
Λ
~
\tilde{\Lambda}
Λ~是对
Λ
\Lambda
Λ的变换,将其范围限制在
[
?
1
,
1
]
[-1,1]
[?1,1]之间,得到
Λ
~
=
2
Λ
/
λ
m
a
x
?
I
\tilde{\Lambda}=2\Lambda/\lambda_{max}-I
Λ~=2Λ/λmax??I 因此得到卷积公式如下:
g
θ
(
Λ
)
?
X
≈
Φ
∑
k
=
0
K
θ
T
k
(
Λ
~
)
Φ
T
x
=
∑
k
=
0
K
θ
k
T
k
(
Φ
Λ
~
Φ
T
)
x
=
∑
k
=
0
K
θ
k
T
k
(
Δ
~
)
x
g_\theta(\Lambda)\star X\approx\Phi\sum_{k=0}^K\theta T_k(\tilde{\Lambda})\Phi^Tx=\sum_{k=0}^K\theta_kT_k(\Phi \tilde{\Lambda }\Phi^T)x=\sum^K_{k=0}\theta_kT_k(\tilde{\Delta})x
gθ?(Λ)?X≈Φk=0∑K?θTk?(Λ~)ΦTx=k=0∑K?θk?Tk?(ΦΛ~ΦT)x=k=0∑K?θk?Tk?(Δ~)x 其中
Δ
~
=
2
λ
m
a
x
Δ
?
I
\tilde{\Delta}=\frac{2}{\lambda_{max}}\Delta-I
Δ~=λmax?2?Δ?I,在上面的公式中,无需计算拉普拉斯的特征向量,只需要进行矩阵的运算。由于超图中的拉普拉斯已经能够很好地表示节点之间的高阶相关性,因此可以进一步地令
K
=
1
K=1
K=1,来简化卷积运算,并令
λ
m
a
x
≈
2
\lambda_{max}\approx2
λmax?≈2因此得到如下公式:

这里的
θ
0
\theta_0
θ0?和
θ
1
\theta_1
θ1?是滤波器的参数,定义一个简单的参数来避免过拟合:
{
θ
0
=
1
/
2
?
θ
D
v
?
1
/
2
H
D
e
?
1
H
T
D
v
?
1
/
2
θ
1
=
?
1
/
2
?
θ
\begin{cases} \theta_0=1/2\ \theta D^{-1/2}_vHD_e^{-1}H^TD^{-1/2}_v \\ \theta_1=-1/2\ \theta \end{cases}
{θ0?=1/2?θDv?1/2?HDe?1?HTDv?1/2?θ1?=?1/2?θ? 把
W
+
I
W+I
W+I看作一体作为超边权重,因此卷积运算最终可以转化为
θ
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
x
\theta D^{-1/2}_vHWD_e^{-1}H^TD^{-1/2}_vx
θDv?1/2?HWDe?1?HTDv?1/2?x
如有一个超图信号X,具有
n
n
n个节点,
C
1
C_1
C1?个特征维度,其卷积可以表示为:
Y
=
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
X
Θ
Y=D_v^{-1/2}HWD_e^{-1}H^TD^{-1/2}_vX\Theta
Y=Dv?1/2?HWDe?1?HTDv?1/2?XΘ 其中
Θ
\Theta
Θ为训练过程中需要学习的参数,滤波器
Θ
\Theta
Θ在超图节点中提取特征。
一个超边卷积层:
X
(
l
+
1
)
=
σ
(
D
v
?
1
/
2
H
W
D
e
?
1
H
T
D
v
?
1
/
2
X
(
l
)
Θ
(
l
)
X^{(l+1)}=\sigma(D^{-1/2}_vHWD_e^{-1}H^TD^{-1/2}_vX^{(l)}\Theta^{(l)}
X(l+1)=σ(Dv?1/2?HWDe?1?HTDv?1/2?X(l)Θ(l)
X
(
l
+
1
)
X^{(l+1)}
X(l+1)为第
l
l
l层的超图信号,
X
(
0
)
=
X
X^{(0)}=X
X(0)=X,
σ
\sigma
σ为激活函数。
分析
下图中说明了超图神经网络细节 。数据集是多模态数据,为每一种模态构建一个超图结构,再将多个模态的超图进行串联,形成一个大超图。再将超图结构和节点特征输入HGNN进行训练,得到输出标签。 图中两个箭头,一种为多模态,一种为单一模态形式。  下图中,描述了一个HGNN层的卷积过程 ,其能够进行节点-边-节点的变换,利用超图结构更好地细化特征。
- Node Feature Trasform。通过滤波器
Θ
\Theta
Θ对节点特征
X
(
1
)
X^{(1)}
X(1)进行处理得到
N
×
C
2
N\times C_2
N×C2?的节点特征
可以将其看作是一个
N
×
C
1
N\times C_1
N×C1?的矩阵
X
X
X与一个大小为
C
1
×
C
2
C_1\times C_2
C1?×C2?的矩阵
Θ
\Theta
Θ的乘积 - Edge Feature Gathering。根据超边集合节点规则,将上一步更新过的特征矩阵与
H
T
H^T
HT相乘得到
E
×
C
2
E\times C_2
E×C2?的超边特征
E
×
N
E\times N
E×N的矩阵
H
T
H^T
HT与一个大小为
N
×
C
2
N\times C_2
N×C2?的矩阵的乘积 - Node Feature Aggregating。将相关超边特征进行聚合得到输出节点的(
N
×
C
2
N\times C_2
N×C2?)特征
N
×
E
N\times E
N×E的矩阵
H
T
H^T
HT与一个大小为
E
×
C
2
E\times C_2
E×C2?的矩阵的乘积 
实现
- 构建超图。将
N
N
N个对象表示为
X
=
[
x
1
,
.
.
.
,
x
n
]
T
X=[x_1,...,x_n]^T
X=[x1?,...,xn?]T。计算两个顶点间的欧式距离,采用
K
K
K近邻算法来构建超边,每条超边中有
K
+
1
K+1
K+1个顶点,获得维度为
N
×
N
N\times N
N×N的关联矩阵
H
H
H。
- 构建分类模型。
数据被分为测试集和训练集两个部分,建立两层HGNN模型(每一次进行两次卷积),使用激活函数生成预测标签。在训练过程中,采用反向传播来更新滤波器参数。对测试数据的标签进行预测,来对性能进行评估。 在处理多模态信息时,可以将各种超边进行融合
实验
引文网络分类
- 数据集
 以上的两个数据集为图结构,每次选取图中的一个顶点作为质心,利用其连接的顶点生成超边。 - 隐藏层的特征维数设置为16,采用
d
r
o
p
o
u
t
dropout
dropout(随机删除一些神经元)来避免过拟合,
d
r
o
p
?
r
a
t
e
=
0.5
drop \ rate=0.5
drop?rate=0.5。
采用
R
e
L
U
ReLU
ReLU作为激活函数,采用Adam优化算法来最小化损失函数,
l
e
a
r
n
i
n
g
?
r
a
t
e
=
0.001
learning\ rate=0.001
learning?rate=0.001 - 结果。在数据集上分别运行100次,得到平均准确率。与其他方法对比如下表。由于构建的超图相比于图并没有添加额外的信息,因此其准确率提高不大。

视觉对象识别
- 数据集
 采用两种形状表示方法,多视图卷积神经网络(MVCNN)以及群视图卷积神经网络(GVCNN)。 - 构造超图结构。
使用一种特征,选取10个邻居构建超边 使用两种特征,每一种特征构建一个超图,再将不同的超图进行拼接 - 效果良好
|