[论文笔记] 2019-AAAI-Hypergraph Neural Networks

1 摘要

    论文链接：https://arxiv.org/pdf/1809.09401.pdf
    代码链接：https://github.com/iMoonLab/HGNN

    本文提出了一种用于数据表示学习的超图神经网络（HGNN）)框架，该框架可以在超图结构中编码高阶数据相关性。该方法设计了超边卷积运算来处理表示学习过程中的数据相关性，能够学习考虑高阶数据结构的隐层表示，是考虑复杂数据相关性的通用框架。对引文网络分类和视觉目标识别任务进行了大量实验，实验结果表明，本文提出的HGNN方法优于目前最先进的方法，同时在处理多模态数据时具有更好的性能。

2 介绍

    传统图卷积神经网络方法应用数据之间成对的连接，但在实际场景中超过成对连接，甚至更复杂。社交媒体数据中，数据之间复杂的关系如图1所示。

    （1）数据相关性比成对关系复杂，很难用图结构来建模。
    （2）数据表示趋向于多模态，例如本例中的视觉连接、文本连接和社会连接。在这种情况下，传统的图结构在表述数据相关性方面存在局限性，限制了图卷积神经网络的应用。

    为了解决上述问题，本文提出了一个超图神经网络框架（HGNN），使用超图结构对数据进行建模。与简单图的对比如图2所示。

    （1）图所有边的度均为2，而超图使用其度自由的超边能够编码高阶数据关系；
    （2）图使用邻接矩阵表示，每条边连接两个顶点；而超图使用其灵活的超边很容易地扩展为多模态的数据表示（通过结合邻接矩阵，一个超图可以联合使用多模态数据生成超图）。

    因此，超图被应用于许多计算机视觉任务，如分类和检索任务。然而，传统的超图学习方法存在计算复杂度和存储成本高的问题，限制了超图学习方法的广泛应用。

    本文提出了一种用于数据表示学习的超图神经网络框架（HGNN）。该方法将复杂数据相关性用超图结构表示，并设计了超边卷积运算，以更好地利用高阶数据相关性进行表示学习。更具体地说，HGNN是一个通用框架，可以包含多模态数据和复杂的数据相关性。传统的图卷积神经网络可以看作是HGNN的一个特例。

3 超图神经网络

3.1 超图学习理论

    超图中的超边能连接两个或更多节点。超图定义为 $G=(V,E,W)$ ，包含一个顶点集 $V$ ，一个超边集 $E$ 。每条超边被赋予一个权重，即 $W$ , 是边权重的对角矩阵。超图 $G$ 可以表示为一个 $|V|\times |E|$ 的关联矩阵 $H$ ，其项为：

h ( v , e ) = { 1 , if  v ∈ e 0 , if  v ∉ e h(v,e) =

$$\begin{cases} 1, & \text{if } v \in e\\ 0, & \text{if } v \notin e \end{cases}$$ h(v,e)={1,0,​if v∈eif v∈/e​

    对于顶点 $v\in V$ ，其度表示为 $d(v)={\sum }_{e\in E}w(e)h(v,e)$ 。对于边 $e\in E$ ，其度表示为 $\delta (e)={\sum }_{v\in V}h(v,e)$ 。 $D_e$ 和 $D_v$ 分别表示边度和顶点度的对角矩阵。

    考虑超图上的节点分类问题，其中节点标签在超图结构上应该是平滑的。该任务可以表述为正则化框架：

arg ⁡ m i n f { R e m p ( f ) + Ω ( f ) } \arg \underset{f}{min} \{ R_{emp} (f) + \Omega (f) \} argfmin​{Remp​(f)+Ω(f)}

其中， $\Omega (f)$ 是超图上的正则化， $R_{emp}(f)$ 表示监督经验损失， $f(\cdot )$ 是分类函数。正则化 $\Omega (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 E} \sum_{\{u,v \} \in 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

    令 $\theta =D_v^{-\frac{1}{2}}HW{D}_e^{-1}{H}^T{D}_v^{-\frac{1}{2}}$ 和 $\Delta =I-\theta$ 。正则化 $\Omega (f)$ 可以写为

$$\Omega (f)=f^T\Delta$$

其中， $\Delta$ 是半正定，通常称为超图拉普拉斯。

3.2 超图上的谱卷积

    给定一个 $n$ 个顶点的超图 $G=(V,E,\Delta )$ ，由于超图拉普拉斯 $\Delta$ 是一个 $n\times n$ 的半正定矩阵，利用特征分解 $\Delta =\Phi \Lambda {\Phi }^T$ 得到标准正交特征向量 $\Phi =diag({\varphi }_1,\cdots ,{\varphi }_n)$ 和一个包含对应非负特征值的对角矩阵 $\Lambda =diag({\lambda }_1,\cdots ,{\lambda }_n)$ 。然后，超图上的一个信号 $x=(x_1,\cdots ,x_n)$ 的傅里叶变换定义为 $\hat{x}={\Phi }^{T}x$ ，其中将特征向量视为傅里叶基，将特征值解释为频率。信号 $x$ 与滤波器 $g$ 的谱卷积可表示为

$$g\times x=\Phi (({\Phi }^{T}g)\odot ({\Phi }^{T}x))=\Phi g(\Lambda ){\Phi }^{T}x$$

其中， $\odot$ 表示元素级Hadamard product， $g(\Lambda )=diag(g({\lambda }_1),\cdots ,g({\lambda }_n))$ 是傅里叶系数函数。然而，正与反傅里叶变换的计算复杂度为 $O(n^2)$ 。为了解决这一问题，使用 $K$ 阶多项式参数化 $g(\Lambda )$ 。使用截断的切比雪夫展开这样的多项式。切比雪夫多项式 $T_k(x)$ 通过 $T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)$ 递归计算， $T_0(x)=1$ 和 $T_1(x)=x$ 。因此， $g(\Lambda )$ 可以参数化为

$$g\times x\approx \sum _{k=0}^K{\theta }_k{T}_k(\tilde{\Delta })x$$

其中， $T_k(\tilde{\Delta })$ 是 $k$ 阶切比雪夫多项式， $\tilde{\Delta }=\frac{2}{{\lambda }_{max}}\Delta -I$。在上式中，排除了拉普拉斯特征向量的展开计算，只考虑矩阵幂、加法和乘法，进一步提高了计算复杂度。可以进一步让 $K=1$ 来限制卷积运算的阶数，因为超图中的拉普拉斯算子已经可以很好地表示节点之间的高阶相关。由于神经网络的尺度适应性， ${\lambda }_{max}\approx 2$ 。然后，将卷积运算进一步简化为

$$g\times x\approx {\theta }_{0}x-{\theta }_1{D}_v^{-\frac{1}{2}}HW{D}_e^{-1}{H}^T{D}_v^{-\frac{1}{2}}x$$

其中, ${\theta }_0$ 和 ${\theta }_1$ 为所有节点的滤波器参数。进一步使用单一参数 $\theta$ 来避免过拟合问题，它被定义为

{ θ 1 = − 1 2 θ θ 0 = 1 2 θ D v − 1 2 H W D e − 1 H T D v − 1 2

$$\begin{cases} \theta_1 = - \frac{1}{2} \theta \\ \theta_0 = \frac{1}{2} \theta D_v^{- \frac{1}{2}} HWD_e^{-1}H^TD_v^{- \frac{1}{2}} \end{cases}$$ {θ1​=−21​θθ0​=21​θDv−21​​HWDe−1​HTDv−21​​​

    因此，卷积操作可以被简化为

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

$$\begin{aligned} g \times x & \approx \frac{1}{2} \theta D_v^{- \frac{1}{2}} H(W + I)D_e^{-1}H^TD_v^{- \frac{1}{2}}x \\ & \approx \theta D_v^{- \frac{1}{2}} HWD_e^{-1}H^TD_v^{- \frac{1}{2}}x \end{aligned}$$ g×x​≈21​θDv−21​​H(W+I)De−1​HTDv−21​​x≈θDv−21​​HWDe−1​HTDv−21​​x​

其中， $(W+I)$ 可视为超边的权值。 $W$ 初始化为单位矩阵，这意味着所有超边的权值相等。

    当有一个具有 $n$ 个节点和 $C_1$ 维特征的超图信号 $X\in {\mathbb{R}}^{n\times C_1}$ 时，超边卷积可以表示为

$$Y=D_V^{-\frac{1}{2}}HW{D}_e^{-1}{H}^T{D}_V^{-\frac{1}{2}}X\Theta$$

其中， $W=diag(w_1,\cdots ,w_n)$ ， $\Theta \in {\mathbb{R}}^{C_1\times C_2}$ 是在训练过程中要学习的参数。过滤器 $\Theta$ 应用于超图中的节点以提取特征。卷积后可得到 $Y\in {\mathbb{R}}^{n\times C_2}$ ，可用于分类。

3.3 超图神经网络分析

    图3展示了超图神经网络的细节。利用多模态数据集的复杂相关性构造多个超边缘结构组。将超边组连接起来，生成超图相邻矩阵 $H$ ，将超图相邻矩阵 $H$ 和节点特征输入到HGNN中，得到节点输出标签。可以用以下公式构建超边缘卷积层 $f(X,W,\Theta )$

$$X^{(l+1)}=\sigma (D_v^{-\frac{1}{2}}HW{D}_e^{-1}{H}^T{D}_v^{-\frac{1}{2}}{X}^{(l)}{\Theta }^{(l)})$$

其中， $X^{(l)}\in {\mathbb{R}}^{N\times C}$ 是超图在 $l$ 层的信号， $X^{(0)}=X$ ， $\sigma$ 表示非线性激活函数。

    如图4所示，HGNN层可以进行节点边-节点转换，利用超图结构可以更好地细化特征。具体来说，首先通过可学习滤波器矩阵 ${\Theta }^{(l)}$ 对初始节点特征 $X^{(1)}$ 进行处理，提取出 $C_2$ 维特征。然后根据超边集合节点特征，形成超边特征 ${\mathbb{R}}^{E\times C_2}$，通过乘以 $H^T\in {\mathbb{R}}^{E\times N}$ 来实现。最后通过聚合它们相关的超边缘特征得到输出节点特征，超边缘特征通过乘以矩阵 $H$ 来实现，上式中 $D_v$ 和 $D_e$ 起到归一化的作用。因此，HGNN层可以通过节点-边-节点变换有效地提取超图上的高阶相关。

3.4 实现

3.4.1 超图构建

    在视觉目标分类任务中， $N$ 个视觉目标数据的特征可以表示为 $X=[x_1,\cdots ,x_n{]}^T$ 。根据两个特征之间的距离来构建超图。更具体地说，用欧氏距离来计算 $d(x_i,x_j)$ 。在构造中，每个顶点代表一个视觉对象，每个超边由一个顶点与其 $K$ 个最近邻居连接而成，这就产生了 $N$ 个超边，连接 $K+1$ 个顶点。因此，得到关联矩阵 $H\in {\mathbb{R}}^{N\times N}$ ，其中 $N\times (K+1)$ 项等于1，其他项等于0。在引用网络分类中，数据以图的结构进行组织，每个超边是根据图上的邻接关系将一个顶点与其相邻顶点连接起来建立的。所以也有 $N$ 条超边和 $H\in {\mathbb{R}}^{N\times N}$ 。

3.4.2 节点分类模型

    构建一个两层HGNN模型。使用softmax函数生成预测标签。在训练过程中，反向传播训练数据的交叉熵损失以更新参数 $\Theta$ ；在测试过程中，预测测试数据的标签以评估性能。当存在多模态信息时，通过构造超边组将多模态信息合并，然后将各种超边融合在一起，建立数据间的复杂关系模型。

4 实验

    该部分请见原文！

5 总结

    本文提出了一个超图神经网络（HGNN）的框架。在该方法中，HGNN将卷积运算推广到超图学习过程。谱域上的卷积用超图拉普拉斯进行，并用截断切比雪夫多项式进一步逼近。与传统图相比，HGNN是一个更通用的框架，它能够通过超图结构处理复杂的高阶相关性进行表示学习。在引文网络分类和视觉目标识别任务上进行了实验，以评估所提出的HGNN方法的性能。实验结果以及与现有方法的比较表明，该模型具有较好的性能。HGNN能够将复杂的数据相关性引入表示学习，从而在视觉识别、检索和数据分类等许多任务中具有广泛的应用潜力。