超图嵌入论文阅读2：超图神经网络

原文：Hypergraph Neural Networks ——AAAI2019（CCF-A）

源码：https://github.com/iMoonLab/HGNN 500+star

概述

贡献：用于数据表示学习的超图神经网络 (HGNN) 框架，对超图结构中的高阶数据相关性进行编码

• 定义超边卷积来处理表示学习过程中的数据相关性

• 够学习考虑高阶数据结构的隐藏层表示，是一个通用框架

  ——GCN可以看作是 HGNN 的一个特例，其中简单图中的边可以被视为仅连接两个顶点的 2 阶超边

• 引文图、图像识别数据集上实验，优于图卷积网络（GCN）

• others：在处理多模态数据时具有优势

背景：

图卷积能够使用神经网络模型对不同输入数据的图结构进行编码，用于无监督、半监督、监督学习，在表示学习方面显示出优越性。传统图卷积网络，使用成对连接，难以表征多模态数据：

1. 数据相关性可能比成对关系更复杂，很难用图结构建模
2. 数据表示往往是多模态的

——传统的图结构具有规定数据相关性的局限性，这限制了图卷积网络的应用。

超图优势：

• 超图可以使用其可变度数超边对高阶数据相关性（超出成对连接）进行编码

• 使用超图的灵活性超边很容易扩展到多模态和异构数据表示：

  如：可以通过组合邻接矩阵来联合使用多模态数据来生成超图

——图已被用于许多计算机视觉任务，例如分类和检索任务

超图问题：传统的超图学习方法计算复杂度和存储成本较高，难以广泛应用

相关研究：

1. 超图学习

   前期发展：

   • 2007首次引入，转导推理旨在最小化超图上连接更强的顶点之间的标签差异
   • 2009进一步用于视频对象分割
   • 2010对图像关系进行建模，并进行转导推理过程进行图像排序

   注意力机制引入：

   • 2013对权重进行正则化
   • 2008提出假设：高度相关的超边应该具有相似的权重

   多模态：

   • 2012引入多超图结构为不同的子超图分配权重

2. 图神经网络

   前期发展：

   • 2005 2009应用循环神经网络来处理图

   谱方法：

   • 2014第一个图 CNN：图拉普拉斯特征基
   • 2015谱滤波器可以使用平滑系数参数化
   • 2016图拉普拉斯算子的切比雪夫扩展进一步用于近似谱滤波器
   • 2017chebyshev 多项式被简化为 1 阶多项式，形成一个有效的逐层传播模型

   空间方法：

   • 2016使用转移矩阵的幂来定义节点的邻域
   • 2017使用高斯混合模型形式的局部路径算子来概括空间域中的卷积
   • 2018注意力机制被引入图以构建基于注意力的架构，以在图上执行节点分类任务

HGNN

超图学习

基础知识（略）：

与简单图不同，超图中的超边连接两个或多个顶点。超图定义为 G = (V, E, W)

超图 G 可以用 |V| × |E|关联矩阵 H 表示
$$h(v,e)=\{\begin{array}{l}1,\text{if}v\in e\\ 0,\text{if}v\notin e,\end{array}$$
$d(v)={\sum }_{e\in E}\omega (e)h(v,e)$、$\delta (e)={\sum }_{v\in V}h(v,e)$。${\mathbf{D}}_e$ 和 ${\mathbf{D}}_v$ 分别表示边度和顶点度的对角矩阵

超图节点分类问题：节点标签应该在超图结构上平滑

——用以下正则化框架描述：
arg ⁡ min ⁡ f { R e m p ( f ) + Ω ( f ) } \arg \min_f \{\mathcal{R}_{emp}(f)+\Omega(f)\} argfmin​{Remp​(f)+Ω(f)}
其中 $\Omega (f)$ 是超图上的正则化，${\mathcal{R}}_{emp}(f)$ 表示监督经验损失，$f(\cdot )$ 是分类函数。正则化$\Omega (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
我们令$\mathbf{\Theta }={\mathbf{D}}_v^{-1/2}\mathbf{HW}{\mathbf{D}}_e^{-1}{\mathbf{H}}^{\mathsf{T}}{\mathbf{D}}_v^{-1/2}$，$\mathbf{\Delta }=\mathbf{I}-\mathbf{\Theta }$ 归一化 $\Omega (f)$ 可以写成：
$$\Omega (f)=f^{\text{T}}\mathbf{\Delta }$$
其中 $\mathbf{\Delta }$ 是半正定的，通常称为超图拉普拉斯算子。

超图谱卷积

给定一个具有 n 个顶点的超图，拉普拉斯算子 $\mathbf{\Delta }$ 是半正定的。对其进行特征分解 $\mathbf{\Delta }=\mathbf{\Phi \Lambda }{\mathbf{\Phi }}^{\mathsf{T}}$ 可得到正交特征向量$\mathbf{\Phi }=\text{diag}({\varphi }_1,...,{\varphi }_n)$ 和对角矩阵 $\mathbf{\Lambda }=\text{diag}({\lambda }_1,...,{\lambda }_n)$ 对应非负特征值。

信号 $\text{x}=(x_1,...,x_n)$ 在超图中定义为 $\hat{\text{x}}={\mathbf{\Phi }}^{\mathsf{T}}\text{x}$ ，其中特征向量被视为傅里叶基，特征值被解释为频率。信号x和滤波器g的谱卷积可以表示为：
$$\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},$$

• $\odot$ 表示逐元素的Hadamard乘积
• $g(\mathbf{\Lambda })=\text{diag}(\text{g}({\lambda }_1),...,\text{g}({\lambda }_n))$ 是傅立叶系数的函数

然而正向和反向傅里叶变换的计算成本为 $O(n^2)$。可以用某论文中的方法使用K 阶多项式参数化 $g(\mathbf{\Lambda })$，我们使用截断切比雪夫展开作为这样的多项式。Chebyshv多项式$T_k(x)$由$T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)$递归计算，其中$T_0(x)=1$和$T_1(x)=x$。因此，$g(\mathbf{\Lambda })$可以参数化为：
$$\text{g}\star \text{x}\approx \sum _{k=0}^K{\theta }_k{T}_k(\hat{\mathbf{\Delta }})\text{x},$$
其中 $T_k(\hat{\mathbf{\Delta }})$ 是k阶切比雪夫多项式，里面的缩放拉普拉斯算子为 $\hat{\mathbf{\Delta }}=\frac{2}{{\lambda }_{max}}\mathbf{\Delta }-\mathbf{I}$。排除了拉普拉斯特征向量的扩展计算，只包括矩阵幂、加法和乘法，提升运算速度。我们可以进一步让 K = 1 来限制卷积操作的顺序，因为超图中的拉普拉斯算子已经可以很好地表示节点之间的高阶相关性。另一篇论文检建议，由于神经网络的规模适应性，令 ${\lambda }_{max}\approx 2$，卷积运算可以进一步简化为：
$$\text{g}\star \text{x}\approx {\theta }_0\text{x}-{\theta }_1{\mathbf{D}}_v^{-1/2}\mathbf{HW}{\mathbf{D}}_e^{-1}{\mathbf{H}}^{\mathsf{T}}{\mathbf{D}}_v^{-1/2}\text{x},$$
其中 ${\theta }_0$ 和 ${\theta }_1$ 是所有节点的过滤器参数。我们进一步使用单个参数 θ 来避免过拟合问题，定义为：
$$\{\begin{array}{l}{\theta }_1=-\frac{1}{2}\theta \\ {\theta }_0=\frac{1}{2}\theta {\mathbf{D}}_v^{-1/2}\mathbf{HW}{\mathbf{D}}_e^{-1}{\mathbf{H}}^{\mathsf{T}}{\mathbf{D}}_v^{-1/2},\end{array}$$
卷积运算可以简化为下式：
$$\begin{gathered} \text{g}\star \text{x}\approx \frac{1}{2}\theta {\mathbf{D}}_v^{-1/2}\mathbf{H}(\mathbf{W}+\mathbf{I}){\mathbf{D}}_e^{-1}{\mathbf{H}}^{\mathsf{T}}{\mathbf{D}}_v^{-1/2}\text{x} \\ \approx \theta {\mathbf{D}}_v^{-1/2}\mathbf{HW}{\mathbf{D}}_e^{-1}{\mathbf{H}}^{\mathsf{T}}{\mathbf{D}}_v^{-1/2}\text{x} \end{gathered}$$
其中 $(\mathbf{W}+\mathbf{I})$ 可以看作是超边的权重。$\mathbf{W}$ 被初始化为单位矩阵，这意味着所有超边的相等权重。

当我们有一个具有n个节点和C1维特征的超图信号 $\mathbf{X}\in {\mathbb{R}}^{n\times C_1}$ 时，我们的超边卷积可以表示为：
$$\mathbf{Y}={\mathbf{D}}_{\mathbf{v}}^{-1/2}\mathbf{HW}{\mathbf{D}}_{\mathbf{e}}^{-1}{\mathbf{H}}^{\mathsf{T}}{\mathbf{D}}_{\mathbf{v}}^{-1/2}\mathbf{X\Theta },$$
其中 $\mathbf{W}=\text{diag}({\text{w}}_1,...,{\text{w}}_n)$，$\Theta \in {\mathbb{R}}^{C_1\times C_2}$ 是训练过程中要学习的参数。过滤器 $\mathbf{\Theta }$ 应用于超图中的节点以提取特征。卷积后，我们可以得到 $\mathbf{Y}\in {\mathbb{R}}^{n\times C_2}$ ，可用于分类。

超图神经网络分析

多模态数据集分为训练数据和测试数据，每个数据包含多个具有特征的节点。然后从多模态数据集的复杂相关性构建多个超边结构组。我们组合超边组以生成超图邻接矩阵$\mathbf{H}$。将超图邻接矩阵$\mathbf{H}$和节点特征输入到HGNN中，得到节点输出标签。

我们可以在以下公式中构建一个超边卷积层 $f(\mathbf{X},\mathbf{W},\mathbf{\Theta })$：
$${\mathbf{X}}^{(l+1)}=\sigma ({\mathbf{D}}_v^{-1/2}\mathbf{HW}{\mathbf{D}}_e^{-1}{\mathbf{H}}^{\mathsf{T}}{\mathbf{D}}_v^{-1/2}{\mathbf{X}}^{(l)}{\mathbf{\Theta }}^{(l)}),$$
其中 ${\mathbf{X}}^{(l)}\in {\mathbb{R}}^{N\times C}$ 是 $l$ 层的超图信号，${\mathbf{X}}^{(0)}=\mathbf{X}$，$\sigma$ 表示非线性激活函数。

卷积层结构：

HGNN模型基于超图上的谱卷积。HGNN 层可以执行 节点-边-节点 的变换，这可以有效地提取超图上的高阶相关性。

1. 初始节点特征 ${\mathbf{X}}^{(1)}$ 由可学习的滤波器矩阵 ${\mathbf{\Theta }}^{(1)}$ 处理以提取 $C_2$- 维特征
2. 据超边收集节点特征以形成超边特征 ${\mathbb{R}}^{E\times C_2}$ ，这是通过乘以矩阵 ${\mathbf{H}}^{\mathsf{T}}\in {\mathbb{R}}^{\mathbf{E}\times \mathbf{N}}$ 来实现的
3. 通过聚合其相关的超边特征来获得输出节点特征，该特征是通过乘以矩阵 $\mathbf{H}$ 来实现的

——${\mathbf{D}}_v$和${\mathbf{D}}_e$在公式11中起到了归一化的作用

与现有方法的关系：

超边只连接两个顶点时，超图被简化为一个简单的图，拉普拉斯算子 $\mathbf{\Delta }$ 也与简单图的拉普拉斯算子一致（1/2倍相乘）

• HGNN可以自然地对数据之间的高阶关系进行建模，有效地利用和编码形成特征提取
• 与传统的超图方法相比，我们的模型在计算上非常高效，没有拉普拉斯算子 $\mathbf{\Delta }$ 的逆运算
• 在超边生成的灵活性下对多模态特征具有很大的可扩展性

实施

1. 超图构造：图片分类任务中，提取每个对象的特征，根据欧氏距离构建超图。每个顶点代表一个视觉对象，每个超边通过连接一个顶点及其 K 个最近邻居来形成，这带来了 N 个链接 K + 1 个顶点的超边。引文图也类似地构造。
2. 节点分类模型：数据集分为训练数据和测试数据，构建超图。按上图搭建网络，构建了一个两层HGNN模型，使用softmax 函数生成预测标签。使用交叉熵损失函数，将各种超边融合在一起，对数据的复杂关系进行建模。

实验

两个任务：引文网络分类和视觉对象识别，与图卷积网络和其他最先进的方法进行比较。

引文网络分类

Cora 和 Pubmed两个数据集：

• 每个数据的特征是文档的词袋表示
• 每次选择图中的每个顶点作为质心，其连通顶点用于生成一条超边，包括质心本身
• 获得与原始图规模相同的关联矩阵
• Cora2708 个5%标记，Pubmed19717 个0.3%标记

参数设置：两层 HGNN

• 隐藏层的特征维度设置为 16
• dropout 丢弃率 p = 0.5
• ReLU 作为非线性激活函数
• Adam 优化器最小化交叉熵损失函数
• 学习率为 0.001

结果讨论：Core和Pumbed上100次运行的平均分类精度

• 与最先进的方法相比，HGNN模型可以达到最佳或相当的性能

  ——与 GCN 相比，HGNN 方法在 Cora 数据集上略有改进，在 Pubmed 数据集上提高了 1.1%

• HGNN 获得的增益并不是很显著——因为构建的超图和传统图差不多

视觉对象分类

数据集：

• 普林斯顿ModelNet40
• 国立台湾大学(NTU) 3D模型数据集

超图构建：

• 特征使用多视图卷积神经网络 (MVCNN) 和组视图卷积神经网络 (GVCNN)提取

• 根据节点的距离构造一个概率图，生成亲和矩阵A来表示不同顶点之间的关系

  $$A_{ij}=\exp (-\frac{2D_{ij}^2}{\Delta })$$

  其中Dij表示节点i和节点j之间的欧氏距离。Δ 是节点之间的平均成对距离

• 两种超图构建方法：

  1. 基于单模态特征：每次选择一个数据集中的一个对象作为质心，选取特征空间中的10个最近邻生成一个超边，包括质心本身
  2. 基于多模态特征：使用多个特征来生成建模复杂多模态相关性的超图 G，只需要将超图关联矩阵拼接即可

结果讨论：

• HGNN方法在ModelNet40数据集中优于最先进的目标识别方法：分别获得 4.8% 和 3.2% 的增益
• 与 GCN 相比，所提出的方法在所有实验中都取得了更好的性能：一个特征取得轻微改进，多个特征改进明显

优势分析

1. 超图结构能够传达数据之间的复杂关系和高阶相关性，与图结构或没有图结构的方法相比，可以更好地表示底层的数据关系。
2. 当多模态数据/特征可用时，HGNN 的优势在于通过其灵活的超边将这种多模态信息组合在同一结构中。
3. 与传统的超图学习方法可能存在计算复杂度高、存储成本高的问题相比，所提出的HGNN框架通过超边卷积运算效率更高。

结论

超图神经网络 (HGNN) 的框架

• 将卷积运算推广到超图学习过程：谱域的卷积用超图拉普拉斯算子进行，进一步用截断的切比雪夫多项式逼近
• 是一个更通用的框架：与传统图相比，能够通过超图结构处理复杂和高阶相关性以进行表示学习
• 对引文网络分类和视觉对象识别任务进行了实验：HGNN 模型有更好的性能

——HGNN能够将复杂的数据相关性纳入表示学习，从而在视觉识别、检索和数据分类等许多任务中带来潜在的广泛应用。