HGNN – Hypergraph Neural Networks

作者：

在

核心速览

这篇 Paper 提出了一种名为超图神经网络(HGNN)的框架，用于学习高维数据。该架构的核心是利用超图结构来编码数据间的高阶关联，以应对传统图神经网络在护理复杂多模态数据是遇到的局限性(因为传统图边只能连接至多两个顶点，也就是捕捉成对关系)。此外， Paper 还参照 GCN 的卷积操作，提出了超图架构下的超边卷积操作。该操作使得超图模型能够在学习过程中有效的处理数据间的高阶关联。通过超边卷积，HGNN 能够考虑学习高阶数据结构的隐藏层表示，并能够抽象出来作为一种更通用的框架，在更多方面进行应用。

论文主要致力于解决现有图神经网络在处理复杂、高阶和多模态数据关联方面的不足

论文的主要亮点包括：

超图结构的提出：HGNN通过超图而非传统图来建模数据，使得它能灵活地表示超越成对关系的高阶数据关联，尤其适用于多模态数据。
超边卷积的定义：论文创新性地设计了超边卷积操作，将图卷积的概念推广到超图域，实现了对高阶关联的高效捕获。
通用框架的提取：HGNN可以看作是传统图卷积神经网络（GCN）的推广（当超边仅连接两个顶点时），论文将其提出作为一个通用的框架，并且通过谱域近似提高了计算效率。

Hypergraph Architecture – 图源：论文 Figure 3

架构分析

既然超图结构可以视为 GNN 的一个推广，那么在架构分析中我们考虑将其与传统 GNN 以及 GCN(图卷积网络)的部分操作进行一个联合对比，以讨论其在基本概念、算子运算以及推导输出上的联系与区别。

Comparison between Hypergraph and Graph – 图源：论文 Figure 2

与图的概念类似，超图同样用于表述抽象为点的数据对象间的相互关系。但传统图中一条边至多连接两个顶点，超图中的边(称之为“超边”)则可以连接任意数量的顶点。这就使得超图能够很自然的建模高阶关系或者多边关系(Multi-way relations)。

类似的，超图中一样存在点集边集等类似概念

顶点集（Vertex Set）$\mathcal{V}$：通常用于表示数据中的个体、实体或观测点。通常用 $N = |\mathcal{V}|$ 表示顶点的数量。
超边集（Hyperedge Set）$\mathcal{E}$：连接元素，每个超边 $e \in \mathcal{E}$ 是顶点集 $\mathcal{V}$ 的一个非空子集，即 $e \subseteq \mathcal{V}$。
- 一条超边可以连接两个或更多顶点。当一个超边只连接两个顶点时，它就退化为普通图中的一条边。
- 通常用 $M = |\mathcal{E}|$ 表示超边的数量。
超边权重（Hyperedge Weights）$\mathbf{W}$：类似于加权边，每个超边 $e \in \mathcal{E}$ 可以被赋予一个权重 $\omega(e)$，用于表示该超边所捕捉到的关系的强度或重要性。
- 这些权重通常构成一个对角矩阵 $\mathbf{W} \in \mathbb{R}^{M \times M}$，其对角线元素为 $W_{ee} = \omega(e)$。
- 如果所有超边权重都为1，则 $\mathbf{W}$ 为单位矩阵(初始化相关)。

超图的数学表示

为了方便数学上的处理，超图通常用以下矩阵来表示：

入射矩阵(Incidence Matrix)$\mathbf{H}$：一个 $N \times M$ 维的矩阵，用于描述顶点和超边的连接关系。
- 其定义为 $$h(v, e) = \begin{cases} 1, & \text{if } v \in e \\ 0, & \text{if } v \notin e \end{cases}$$
  - 其中 $v \in \mathcal{V}$ 是顶点， $e \in \mathcal{E}$ 是超边。
  - $\mathbf{H}$ 的每一行对应一个顶点，每一列对应一个超边。如果顶点 $v$ 属于超边 $e$，则 $H_{ve} = 1$；否则 $H_{ve} = 0$。
顶点度矩阵（Vertex Degree Matrix）$\mathbf{D}_v$：一个 $N \times N$ 的对角矩阵，其对角线元素 $D_{vv}$ 表示顶点 $v$ 的度。
- 顶点 $v$ 的度 $d(v)$ 定义为所有包含该顶点 $v$ 的超边权重的和：$$d(v) = \sum_{e \in \mathcal{E}} \omega(e) h(v, e)$$
- 也就是说，$D_{vv} = d(v)$，非对角线元素为 $0$。
超边度矩阵（Hyperedge Degree Matrix）$\mathbf{D}_e$：一个 $M \times M$ 的对角矩阵，其对角线元素 $D_{ee}$ 表示超边 $e$ 的度。
- 超边 $e$ 的度 $\delta(e)$ 定义为组成该超边 $e$ 的顶点数量：$$\delta(e) = \sum_{v \in \mathcal{V}} h(v, e)$$
- 也就是$D_{ee} = \delta(e)$，非对角线元素为 $0$。

注意在这个定义中，论文没有将超边权重 $\omega(e)$ 引入到超边度中，而是直接计算连接的顶点数量，这和传统图的度定义一脉相承。

Hypergraph Laplacian

传统图论与图信号处理中，图 Laplacian 是一个重要的概念，它能够捕捉图结构的连接模式和拓扑性质，反映结构上的平滑特点。

GCN的拉普拉斯算子 (Normalized Graph Laplacian)：定义在简单图的邻接矩阵和度矩阵之上。最常用的是对称归一化拉普拉斯矩阵：

$$\mathbf{L}_{\text{sym}} = \mathbf{I} – \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$$

或非归一化拉普拉斯矩阵 $\mathbf{L} = \mathbf{D} – \mathbf{A}$。其中 $\mathbf{A}$ 是邻接矩阵，$D$ 是度矩阵。

而 HGNN 的拉普拉斯算子则定义在超图的入射矩阵 $\mathbf{H}$、超边权重矩阵 $\mathbf{W}$、顶点度矩阵 $\mathbf{D}_v$ 和超边度矩阵 $\mathbf{D}_e$ 之上。

$$\mathbf{\Delta} = \mathbf{I} – \mathbf{D}_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}_e^{-1} \mathbf{H}^\top \mathbf{D}_v^{-1/2}$$

它通过入射矩阵 $\mathbf{H}$ 将顶点与超边联系起来，再通过超边权重和度进行加权和归一化。这意味着它隐含地编码了通过超边连接的多个节点之间的共同关系。

泛化过程

我们知道，普通图的归一化图拉普拉斯算子 $\mathbf{L}_{\text{sym}} = \mathbf{I} – \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$。是基于二次型推导出来的：

$$\mathbf{f}^\top \mathbf{L} \mathbf{f} = \frac{1}{2} \sum_{u, v \in \mathcal{V}} A_{uv} (f_u – f_v)^2$$

这个二次型衡量了图上信号 $f$ 的平滑度。如果相邻节点 $u, v$ 上的信号值 $f_u, f_v$ 相近，$(f_u – f_v)^2$ 就小；如果它们相差很大，$(f_u – f_v)^2$ 就大。拉普拉斯算子就是通过最小化这个二次型（即鼓励相邻节点具有相似的信号值）来捕捉图的结构信息。

而当引入归一化后，它鼓励归一化后的信号 $f_u/\sqrt{d_u}$ 有平滑性，也就是通过放缩，放大远距离差异，减小近距离差异。

Hypergraph 的 Laplacian 推广，正是基于上述平滑度的一种泛化，目的是使超图能够适应数据的高阶连接特性。

在论文的公式 3 中，超图的正则化项是这么定义的：

$$\Omega(f) = \frac{1}{2} \sum_{e \in \mathcal{E}} \sum_{\{u,v\} \subseteq e} \frac{w(e)}{\delta(e)} \left( \frac{f(u)}{\sqrt{d(u)}} – \frac{f(v)}{\sqrt{d(v)}} \right)^2$$

其核心思想仍然是最小化信号在“连接紧密”的顶点之间的差异。但是，这里的“连接紧密”的定义发生了变化——

节点 $u$ 和 $v$ 不仅仅通过一条普通边连接，它们还可以通过超边 $e$ 来联系。一个超边 $e$ 连接了它内部所有的节点。那么此时超图正则化项的求和形式 $\sum_{\{u,v\} \subseteq e}$ 就表明，对于每一条超边 $e$ 来说，其内部的任意两个顶点 $u, v$ 都被认为是“连接在一起”的。它们之间的函数值差异 $(f(u) – f(v))^2$ 会被加总，并由超边 $e$ 的权重 $w(e)$ 和度 $\delta(e)$ 共同加权。也就是加权的排列组合然后求和。

我们将其写成矩阵形式：

$$\mathbf{H} \mathbf{W} \mathbf{D}_e^{-1} \mathbf{H}^\top$$

和传统图的归一化拉普拉斯矩阵相比相比，不难发现其就是替换了传统图的近似邻接矩阵A，归一化时采用的同样是顶点度矩阵

为什么会出现入射矩阵 $H$ ?因为它反映的是不同节点或超边间的连接

这个算子依然保持了谱图理论的核心性质（如半正定性），并能够用于超图上的频率傅立叶变换，所以接下来的操作与 GCN 中的卷积类似， Paper 定义为超图卷积。

谱域、傅里叶变换与谱卷积

The illustration of the hyperedge convolution layer – 图源：论文 Figure 4

由于 $\mathbf{\Delta}$ 是一个 $N \times N$ 的实对称半正定矩阵（对称性需要一些条件，但归一化拉普拉斯通常是其变体），它可以通过特征分解得到：

$$\mathbf{\Delta} = \mathbf{\Phi} \mathbf{\Lambda} \mathbf{\Phi}^\top$$

其中：

$\mathbf{\Phi} = [\phi_1, \dots, \phi_N]$ 是由 $N$ 个正交特征向量组成的矩阵，这些特征向量构成了超图上的傅立叶基（Fourier bases）
$\mathbf{\Lambda} = \text{diag}(\lambda_1, \dots, \lambda_N)$ 是一个对角矩阵，其对角线元素是对应的非负特征值 $\lambda_i$，这些特征值被解释为超图上的“频率”（frequencies）

而对于超图上的一个信号 $\mathbf{x} \in \mathbb{R}^N$ ，其傅立叶变换定义为：

$$\hat{\mathbf{x}} = \mathbf{\Phi}^\top \mathbf{x}$$

相应的，傅立叶逆变换则为：

$$\mathbf{x} = \mathbf{\Phi} \hat{\mathbf{x}}$$

谱域中的图卷积操作被定义为信号的傅里叶变换和滤波器的傅里叶变换的哈达玛积，然后对结果进行逆傅里叶变换，也就是：

$$g * \mathbf{x} = \mathbf{\Phi} ((\mathbf{\Phi}^\top g) \odot (\mathbf{\Phi}^\top \mathbf{x}))$$

通常为了简化，滤波器 $g$ 被视为一个在特征值上定义的函数 $g(\mathbf{\Lambda})$，即：

$$g * \mathbf{x} = \mathbf{\Phi} g(\mathbf{\Lambda}) \mathbf{\Phi}^\top \mathbf{x}$$

这里的 $g(\mathbf{\Lambda}) = \text{diag}(g(\lambda_1), \dots, g(\lambda_N))$ 是一个包含滤波器在每个频率分量上的响应的对角矩阵。

但此时我们注意到表达式依然涉及超图拉普拉斯的特征分解，在暴力情况下，其时间复杂度为 $O(N^3)$，面对大图效率依然乐观不起来

GCN 给出了它的解决方法，它更为激进通过将滤波器视为特征值的多项式函数使得卷积操作可被写为：

$$g * \mathbf{x} =g( \mathbf{\Phi} \mathbf{\Lambda} \mathbf{\Phi}^\top) \mathbf{x}$$

以及通过切比雪夫多项式(Chebyshev polynomials)近似滤波器:

$$g * \mathbf{x} \approx \sum_{k=0}^{K} \theta_k T_k(\tilde{\mathbf{\Delta}}) \mathbf{x}$$

注意此时的 $\tilde{\mathbf{\Delta}}$ 因为从需要满足切比雪夫变换的收敛要求需要落在 $[-1,1]$ 上，所以经过了 $\tilde{\mathbf{\Delta}} = \frac{2}{\lambda_{\text{max}}} \mathbf{\Delta} – \mathbf{I}$ 的缩放变换(因为 $\mathbf{\Delta} \in [0, 2]$)

接着是和 GCN (2017) 一样的操作，通过指定 $\theta_1$ 和 $]theta_0$ 为共享参数来统一表达式，并最终导出了如下形式：

$$g * \mathbf{x} \approx \theta \mathbf{D}_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}_e^{-1} \mathbf{H}^\top \mathbf{D}_v^{-1/2} \mathbf{x}$$

注意到论文之间初始化 $W$ 为单位矩阵以省略系数

超图神经网络层（HGNN Layer）

在定义完超图的 Laplacian 算子后，Paper 接着构建了超图的神经网络层。

对于包含 $N$ 个节点且每个节点有 $C_1$ 维特征的输入信号矩阵 $\mathbf{X}^{(l)} \in \mathbb{R}^{N \times C_1}$（$l$ 表示当前层），HGNN的单个卷积层（即“超边卷积”层）的输出 $\mathbf{X}^{(l+1)} \in \mathbb{R}^{N \times C_2}$ 被定义为：

$$\mathbf{X}^{(l+1)} = \sigma \left( \mathbf{D}_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}_e^{-1} \mathbf{H}^\top \mathbf{D}_v^{-1/2} \mathbf{X}^{(l)} \mathbf{\Theta}^{(l)} \right)$$

其中：

$\mathbf{\Theta}^{(l)} \in \mathbb{R}^{C_1 \times C_2}$ 是第 $l$ 层的可学习权重矩阵（可以看作是对特征进行线性变换的滤波器）。
$\sigma(\cdot)$ 是非线性激活函数（例如ReLU）。

如我们前面所说，核心的转换项 $\mathbf{D}_v^{-1/2} \mathbf{H} \mathbf{W} \mathbf{D}_e^{-1} \mathbf{H}^\top \mathbf{D}_v^{-1/2}$ 被称为超图传播算子。它负责在超图结构上传播和聚合节点特征。

更直观一点，超图传播算子实际上是一种 Node – Edge – Node 的转换：

$\mathbf{H}^\top \mathbf{X}^{(l)}$：将节点特征 $\mathbf{X}^{(l)}$ 聚合到超边。$\mathbf{H}^\top$ 的每一行对应一个超边，它将其所连接的节点的特征求和（或更精确地，进行线性组合），形成超边特征。
$\mathbf{D}_e^{-1}$：对聚合后的超边特征进行归一化，通常是除以超边的度，以避免超边连接过多顶点导致特征值过大。
$\mathbf{W}$：应用超边权重，调整不同超边的重要性。
$\mathbf{H}$：将经过加权和归一化的超边特征传播回节点。$\mathbf{H}$ 的每一行对应一个节点，它聚合其所属超边的特征。
$\mathbf{D}_v^{-1/2} (\dots) \mathbf{D}_v^{-1/2}$：对聚合后的节点特征进行进一步的归一化，通常是根据节点的度进行调整。这一步有助于稳定训练并确保特征不会随着网络层数的增加而数值爆炸或消失。

通过这种“节点-超边-节点”的转换，HGNN能够有效地在超图结构上进行信息传播和特征学习，从而捕获数据之间的高阶复杂关联。

与多模态的处理关联

其实论文中并没有做具体展开多模态相关的机制实验，原文的表述是：

“In the second case, multiple features are used to generate a hypergraph G modeling complex multi-modality correlation. Here, for the $i^{th}$ modality data, a hypergraph adjacent matrix Hi is constructed accordingly. After all the hypergraphs from different features have been generated, these adjacent matrices Hi can be concatenated to build the multi-modality hypergraph adjacent matrix H. In this way, the hypergraphs using single modal feature and multi-modal features can be constructed.”

论文表示流程是一样的，提到多模态也正是因为超图有处理不同模态数据之间以及模态内部的复杂高阶关系的能力。从框架的角度出发，在多模态上应用超图，我设想的流程主要包括：

模态数据的统一建模 $\longroghtarrow$ 数据间的高阶关系捕获 $\longrightarrow$ 模态间的信息融合

潜在局限与展望

超图构建：论文在实验中展示了两种超图构建方法：一种是基于K近邻（KNN）来为每个顶点生成一个超边（包含自身和K个最近邻），另一种是基于原始图结构将中心顶点及其邻居构成超边。然而，超图的构建方式对于HGNN的性能至关重要。不同的领域（如图像、文本、生物信息学）和不同的任务可能需要截然不同的超图构建策略，论文中提出的方法可能不是普遍最优的。特别是，K近邻方法会引入超参数K，其选择对性能影响大。

自适应或半自适应可能是一个潜在的优化方向，不过我没搜到相关方法..

权重设置：论文的HGNN模型中，超边权重 $\mathbf{W}$ 被初始化为单位矩阵（即所有超边权重相等）。虽然在公式 (9) 中提到了 $(W+I)$ 可以被视为超边权重，但实际实现中 $\mathbf{W}$ 通常是预设或简单的对角矩阵。这种硬编码的方式在架构搭建中似乎是不宜过多出现的，而且与相关工作中强调的超边权重学习的重要性形成对比。

近似局限：这同时是 GCN 的问题，一阶近似导致模型的长程提取能力不强，限制了模型捕获全局频率信息的能力。

高阶关联的可解释性：这是我始终没法理解的一个问题，论文一直反复强调“超图中的拉普拉斯算子已经可以很好地表示节点间的高阶关联”，但其给出的推导是由 GCN 的滤波器求解函数泛化而来，没有给出更严格的理论证明。

HGNN

分类导航