【论文阅读】Hypergraph Neural Networks

Hypergraph Neural Networks

• 超图学习部分

• 超图上的谱卷积

• • 超图的傅里叶变换
  • 超图上的卷积
  • 分析

• 实现

• 实验

• • 引文网络分类
  • 视觉对象识别

超图学习部分

基于符号\mathcal{G=(V,E,W)}来定义的超图结构中分别对应于顶点集合V、超边集合E以及权重集合W。通过关联矩阵\bm H的表示形式，则可清晰地体现各元素之间的关联关系。其中h(n,\theta)为二元函数，在v\in e时取值为1，在其他情况下取值为0。

节点的度d(v)=\sum_{e\in \mathcal{E}}w(e)h(v,e)
超边的度\delta(e)=\sum_{v\in \mathcal{V}}h(v,e)

超图顶点被划分为若干分类问题，并对应于一个正则化框架：

该函数在超图中作为正则化项使用：其具体表达式如下所示：

\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)}

其中每一项均经过详细计算与权重分配：

\left( \frac{f(u)}{\sqrt{d(u)}} - \frac{f(v)}{\sqrt{d(v)}} \right)^2

通过进一步简化分析可知：

\Omega(f) = f^\top (\Delta f)

其中矩阵 \Delta 被定义为 I - L，
而 L = D_v^{-1/2} H W D_e^{-1} H^\top D_v^{-1/2}。

超图上的谱卷积

附上一个普通图的谱卷积：如何理解GCN（大神写的太好了！入门也可以看）

超图的傅里叶变换

将拉普拉斯矩阵进行谱分解后可得其由特征向量矩阵\Phi=diag(\phi_1,...,\phi_n)与对应特征值矩阵\Lambda=diag(\lambda_1,...,\lambda_n)组成，并且所有这些特征值均为非负数。
通过等式\Delta \Phi = \Lambda \Phi可知：
设超图上的信号向量为X=(X_1, X_2, ..., X_n)表示每个节点对应一个信号值

经典的傅里叶变换公式如下所示：其数学表达式被定义为 F(w) = \int f(t) e^{-iwt} dt。这一过程通常用于将时域信号转换至频域以便分析不同频率成分的作用机制。

超图上的卷积

卷积性质：两个函数的卷积的傅里叶变换等于各自傅里叶变换之乘积累。即为函数傅里叶变换乘积分量之逆运算；对于任意两个函数f(t)和h(t)有：

f * h = \mathcal{F}^{-1}[\mathcal{F}(f) \cdot \mathcal{F}(h)] = \frac{1}{2\pi} \int_{-\infty}^{\infty} \mathcal{F}(f)(\omega) \cdot \mathcal{F}(h)(\omega) e^{i\omega t} d\omega

根据定义可知：卷积核g的傅里叶变换可表示为\hat{g}=diag(\{\hat{g}(\lambda_1),...,\hat{g}(\lambda_n)\})因此其与矩阵X相乘的结果为\hat g\Phi^\top X, 经过逆运算后得到\Phi \hat g\Phi^\top X

\hat{g}也可以被定义为一个基于特征值\lambda_i的对角矩阵形式g(\Lambda)=diag(g(\lambda_1),...,g(\lambda_n))
信号与滤波器之间的谱卷积关系可具体表式如下：

g \star X = \Phi \left( (\Phi^\top g) \odot (\Phi^\top X) \right) = \Phi g(\Lambda) \Phi^\top X

上述公式计算开销较大：一方面特征向量矩阵乘法操作的时间复杂度达O(n^2)；另一方面处理大规模超图拉普拉斯矩阵时涉及较大的特征分解计算负担。因此我们转而采用切比雪夫多项式K次幂的方式来进行函数近似逼近。

请查看一篇关于Chebyshev多项式在GCN卷积核中的详细解析文章：Chebyshev多项式作为GCN卷积核

切比雪夫多项式：
定义如下：
T_k(x) = \begin{cases} 0, & k=0\\ x, & k=1\\ 2xT_{k-1}(x)-T_{k-2}(x), & k>1 \end{cases}
通过这种定义方式得到了一个新的卷积核：
g_\theta(\Lambda)\approx\sum^K_{k=0}\theta_kT_k(\tilde{\Lambda})
其中\tilde{\Lambda}是对\Lambda施加的一种变换操作，并将其范围限制在区间[-1,1]内；具体地，
\tilde{\Lambda}=2\frac{\Lambda}{\lambda_{max}} - I
基于上述定义关系式，则可得到以下卷积运算公式：
g_\theta(\Lambda)\star X\approx\Phi\sum_{k=0}^K\theta_k T_k(\tilde{\Lambda})\Phi^Tx=\sum_{k=0}^K\theta_k T_k(\Phi \tilde{\Lambda }\Phi^T)x=\sum^K_{k=0}\theta_k T_k(\tilde{\Delta})x
其中，

\tilde{\Delta}=\frac{2}{\lambda_{max}} \Delta - I

值得注意的是，在上述公式推导过程中无需计算拉普拉斯矩阵的特征向量；仅需执行矩阵运算即可实现目标函数值的近似求解。由于超图中的拉普拉斯矩阵能够有效捕捉节点间的高阶关联特性；因此我们采取取k=1的情况来进行简化运算；并设定参数\lambda_{max}\approx2；最终得到以下简洁形式：

g_\theta(\Lambda)\star X=\sum^K_{k=0}\theta_k T_k(\tilde{\Delta})x

这些参数\theta_0和$\θ₁$属于滤波器组件，并通过引入简化的参数设置以防止过拟合：
其中：

θ₀ = (½) · θ · Dₐ_v⁻¹² · H · Dₑ⁻¹·Hᵀ·Dₐ_v⁻¹²

θ₁ = -(½) · θ

将矩阵(W + I)视为整体用于超边权重构建时，卷积操作的结果等价于：

θ · Dₐ_v⁻¹² · H · W · Dₑ⁻¹·Hᵀ·Dₐ_v⁻¹²·x

给定一个超图信号X,它由n个节点构成,并包含C_1个特征维度.该信号经过卷积运算可表示为:
Y=D_v^{-1/2}HWD_e^{-1}H^TD_v^{-1/2}X\Theta
其中参数\Theta是在训练过程中需要学习的,滤波器\Theta在超图节点间提取特征.

在本研究中所设计的超边卷积层：

分析

在图中展示了超图神经网络的相关细节。该数据集包含了多种模态的数据信息，并对每一种模态分别构建相应的超图结构。随后将各模态所对应的超图进行串联整合，并将构建好的超图结构与节点特征输入HGNN模型进行训练以获得最终输出标签。在图形中标注有两个箭头符号：一个代表多模态信息传递路径

下图中具体说明了该卷积过程的工作原理及其作用机制, 通过超图结构进一步细化特征信息, 实现节点到边再到节点的变换过程

1. Node Feature Transform。利用滤波器矩阵\Theta作用于节点特征向量x^{(1)}= [x^{(1)}_1, x^{(1)}_2, ..., x^{(1)}_n]^T \in \mathbb{R}^n}上实现了一次非线性变换操作，使得其输出结果为大小为n \times c_2}的新节点特征向量；经过计算后得到的新特征向量具有维度为n \times c_2}；这一过程等价于将该过程表示为n \times c_1}维输入向量x与一个大小为c_1 \times c_2}的滤波器矩阵\Theta = [\theta_{i,j}]_{c_1,c_2}}}之间的矩阵乘法运算

Edge Feature Collection. According to the node rules of hyperedges, multiplying the updated feature matrix from the previous step with H^T yields the super edge features of size E \times C_2. The product of an E \times N dimensional matrix and an N \times C_2 dimensional matrix is computed using H^T.

3. Node Feature Aggregating。通过将关联超边特征进行聚合整合出该节点的（N\times C_2）特征。其中矩阵H转置与其所乘矩阵相乘的结果即为所需输出。

实现

• 构建超图结构。将N个对象表示为X=[x_1,...,x_n]^T形式，并计算各顶点间的欧式距离度量值。随后采用K近邻算法确定每条超边包含的具体顶点数量（即K+1个顶点），最终获得一个维度为N\times N的关联矩阵H。
• 开发分类模型。数据集被划分为测试集和训练集两部分，并设计一个双层的HGNN架构（每次卷积操作执行两次）。在模型训练过程中基于反向传播算法优化滤波器参数，并通过激活函数计算节点的预测标签值。利用测试数据进行标签预测从而评估模型性能。
• 在处理多模态信息时，则可以通过融合不同超边信息来提升模型性能。

实验

引文网络分类

1. 数据集

这两个数据集属于图结构，在每次选取图中一个顶点作为中心时，通过其连接的顶点构建超边。

将隐藏层的特征维度设定为16，并通过引入dropout技术（即随机移除神经元）来防止模型过拟合。其中其drop\ rate设为0.5，并采用ReLU激活函数选择使用Adam优化算法以最小化模型损失，并设定学习速率为0.001

3. 结果结果显示，在数据集上重复运行100次并计算得到了平均准确率，并与表格中的其他方法进行了对比。因为构建的超图相较于传统图并未增加额外信息量, 所以其准确率提升并不明显

视觉对象识别

1. 数据集

通过不同形状的表示方法实现多模态感知的提升，在群视图卷积神经网络（GVCNN）的基础上进一步优化了群体感知能力

2. 构建超图结构。
   基于单一特征, 选择10个邻居节点并形成相应的超边.
   分别基于两组不同的特征生成独立的超图网络, 并对这些网络进行融合.

3. 效果良好