Hypergraph & semi-supervised paper review
汇总了这几年的 超图 + 半监督中的有趣文献。
Wasserstein Soft Label Propagation on Hypergraphs: Algorithm and Generalization Error Bounds
核心思路：
- 背景和动机：随着超图在机器学习和数据挖掘算法中的应用不断增加，本文探讨了在超图上通过最优传输进行“软标签”传播的半监督学习算法。软标签（如概率分布、类别成员分数）传播相较于传统的硬标签传播，具有更高的灵活性和信息量，适用于不确定性和分布信息至关重要的场景。
- 算法设计：借鉴Wasserstein传播算法（Solomon et al., 2014），本文将标签传播过程重新构建为消息传递算法，通过Wasserstein重心实现了其在超图上的一般化。利用2-Wasserstein距离，提出了一种新的消息传递算法，用于在超图上传播一维分布。
- 理论贡献：在PAC学习框架内，本文提供了在图和超图上传播一维分布的泛化误差界，通过建立所提出算法的算法稳定性，揭示了Wasserstein传播算法在图上的新见解和更深层次的理解。
贡献
- 扩展Wasserstein传播至超图：提出了基于Wasserstein重心的超图软标签传播算法，并通过多边最优传输问题解决了该算法在超图上的推广。
- 算法稳定性和泛化误差界：在PAC学习框架下，本文建立了使用2-Wasserstein距离传播一维分布的泛化误差界，提供了关于Wasserstein传播算法在图上泛化能力的首个理论结果。
- 数值实验和实际应用：通过在随机超图和UCI数据集（包括国会投票记录和蘑菇特征数据）上的实验，展示了所提出算法的有效性。
传统的标签传播算法（如Belkin等人提出的算法）通常用于图（graph）上的标签传播，其标签为数值或类别变量。而Wasserstein传播算法通过最优传输理论将标签扩展为概率分布或软标签（soft label），提高了算法的灵活性和信息量。
- Wasserstein传播算法最初在图（graph）上定义，其目的是在节点之间传播概率分布标签。本文将这一过程重新构建为消息传递算法，并扩展到超图（hypergrap
在图上的Wasserstein标签传播
给定一个图$$G = (V, E)$$，定义一个度量空间上的概率分布映射$$\mu: V \to P(N)$$
假设有一部分节点 $$V_0 \subseteq V$$的标签已知，目标是确定其余节点 $$ V \setminus V_0 $$ 的标签。目标函数为：
$$ \min_{f: V \to P(N)} \frac{1}{m} \sum_{i=1}^{m} W_2^2(\mu_i, f(i)) + \gamma \sum_{(i,j) \in E} \omega_{ij} W_2^2(f(i), f(j)) $$
其中$$\gamma$$是正则化参数，$$\omega_{ij}$$ 是边$$(i, j)$$的权重，$$W_2$$是2-Wasserstein距离。
超图上的Wasserstein标签传播
在超图$$H = (V, E)$$上，由于超边（hyperedge）可以包含任意数量的顶点，目标函数需要重新定义。超图上的Wasserstein传播算法基于消息传递更新规则：
- 消息传递更新规则
从节点 i 向超边 E 发送消息$$ J_{i \to E}$$:
$$J_{i \to E}(b_i) = W_2^2(\mu_i, b_i) + \sum_{E’ \in E \setminus {E}: i \in E’} J_{E’ \to i}(b_i) $$
超边 E 向节点 i 发送消息$$J_{E \to i}$$:
$$J_{E \to i}(b_i) = \min_{f_{E \setminus {i}}} \left[ \text{bar}(E) + \sum_{k \in E \setminus {i}} J_{k \to E}(f_k) \right]$$
$$\text{bar}(E)$$是超边 E 上的 Wasserstein 重心
- 迭代更新信念
- 节点 i 的信念 b_i 更新为：
$$b_i = \arg \min_{f_i \in P(N)} \left[ W_2^2(\mu_i, f_i) + \sum_{E \in E: i \in E} J_{E \to i}(f_i) \right] $$
- 最终目标函数
- 对整个超图的目标函数为：
$$\min_{f: V \to P(N)} \frac{1}{m} \sum_{i=1}^{m} W_2^2(\mu_i, f(i)) + \gamma \sum_{E \in E} \text{bar}(E) $$
- Wasserstein重心
Wasserstein重心的计算是核心步骤之一，具体定义如下：
给定 k 个概率分布 $$\rho_1, \ldots, \rho_k$$ ，它们的Wasserstein重心为：
$$\text{bar}({\rho_i}{i=1}^k) = \inf{\nu \in P(N)} \frac{1}{k} \sum_{i=1}^k W_2^2(\rho_i, \nu)$$
对于一维概率分布，其Wasserstein重心可以通过累积分布函数的逆函数来计算：
$$F^{-1}{b}(s) = \frac{1}{k} \sum{i=1}^k F^{-1}_{\rho_i}(s)$$
Semi-supervised Hypergraph Node Classification on Hypergraph Line Expansion
一句话总结：用 线性扩展（LE）将超图转换为简单图结构
Self-Supervised Guided Hypergraph Feature Propagation for Semi-Supervised Classification with Missing Node Features
一句话总结： 用来解决只给一部分特征的任务。
SGHFP通过以下步骤进行特征传播和重建：
- 特征超图构建：根据节点的已知特征构建特征超图。
- 伪标签超图构建：利用前一迭代产生的重建特征通过两层GNN构建伪标签超图。
- 超图融合：在每次迭代前，将特征超图和伪标签超图融合，生成更有效的超图。
- 特征传播：使用融合后的超图进行特征传播，重建缺失的节点特征。
- 迭代优化：通过多次迭代优化，最终重建的节点特征用于下游的半监督分类任务。
自监督引导的超图特征传播（SGHFP）
Nonlinear Feature Diffusion on Hypergraphs
一句话总结： 提出一种非线性特征扩散方法，在超图上同时传播特征和标签，以捕捉更复杂的节点间关系。
Sheaf Hypergraph Networks (重了, 你多下了一个)
一句话总结：通过在超图中引入纤维丛（cellular sheaf）结构，增强了超图的表示能力，从而更好地建模复杂数据结构。
引入纤维丛超图结构：纤维丛超图通过在超图的节点和超边上关联向量空间，并提供线性投影，使信息在节点和超边之间传递，从而实现更丰富的数据表示。
提出纤维丛超图拉普拉斯算子：包括线性和非线性两种形式，提供了更具表达力的归纳偏差，有效地建模复杂现象。
开发新型神经网络模型：设计了基于纤维丛超图拉普拉斯算子的SheafHyperGNN和SheafHyperGCN模型，实验结果表明，这些模型在多个基准数据集上的表现优于现有方法。
Hypergraph-enhanced Dual Semi-supervised Graph Classification
一句话总结: 提出了一种增强的双半监督图分类框架（HEAL），通过超图和线图两个视角捕捉图语义，从而更好地利用未标记图数据，提高分类性能。
HEAL框架包括三个主要模块：
- 高阶依赖学习模块：通过自适应学习超图结构，捕捉节点间的复杂依赖关系。
- 线图卷积模块：利用线图捕捉超边间的交互，从而挖掘更深层次的语义结构。
- 关系一致性学习模块：促进两个分支间的知识传递，增强模型在未标记图上的表现。
Hypergraph Transformer for semi-supervised classification
一句话总结:利用Transformer架构有效地捕捉超图中的全局相关性，同时保留局部连接模式。
提出HyperGraph Transformer框架：通过Transformer架构结合超图特定组件，实现同时捕捉全局和局部结构信息，提升了超图表示学习的效果。
设计了新的位置编码机制和结构正则化方法：利用超图关联矩阵进行位置编码和结构正则化，有效地融合了超图的结构信息，提升了模型性能。
实验验证：在四个实际数据集上的实验结果表明，HyperGT在节点分类任务中显著优于现有的最先进方法，并展示了各个设计组件的有效性。
Hypergraph Label Propagation Network
一句话总结: 提出了一种超图标签传播网络（HLPN），将超图标签传播与深度神经网络结合，通过端到端架构优化特征嵌入，从而实现更高效的数据标注。
提出了一种新的超图半监督学习框架：该框架通过稀疏样本捕捉流形结构，并实现端到端学习。
提高超图学习效率：相比传统超图方法，HLPN不需要构建整个数据集的超图，从而提高了计算效率。
实验验证：在实际数据集上的实验结果表明，HLPN在性能上显著优于最先进的方法。
Hypergraph Convolutional Network based Weakly Supervised Point Cloud Semantic Segmentation with Scene-Level Annotations
一句话总结: 提出了一种基于加权超图卷积网络（WHCN）的弱监督点云语义分割方法，通过场景级别标注学习点级别伪标签，从而提高分割性能。
算法设计：
- 超点生成与超图构建：利用几何同质划分生成超点，以平衡不同类别点数的不均衡性，并降低模型复杂度。基于高置信度超点种子构建超图。
- 加权超图卷积网络：设计了加权超图卷积网络（WHCN），通过标签传播生成高精度的点级别伪标签。WHCN包括谱超图卷积块和超边注意力模块，调整超边权重以优化标签传播。
- 伪标签生成与分割网络训练：利用生成的伪标签训练分割网络，实现高精度的点云语义分割。
From Hypergraph Energy Functions to Hypergraph Neural Networks
这个你看了, 就不总结了
CHGNN: A Semi-Supervised Contrastive Hypergraph Learning Network
一句话总结: 提出了一种对比超图神经网络（CHGNN），结合自监督对比学习技术，从标记和未标记数据中学习。CHGNN包括一个自适应超图视图生成器、改进的超图编码器和一个结合相似度损失、节点分类损失和超边同质性损失的联合损失函数。
算法设计：
- 自适应超图视图生成器：采用自动增强策略，学习最小充分视图的扰动概率分布。
- 改进的超图****编码器：考虑超边的同质性，有效融合信息。
- 联合****损失函数：结合视图生成器的相似度损失、节点分类损失和超边同质性损失，增强监督信号。此外，还包括基础对比损失和交叉验证对比损失，提高对比学习效果。
Hypergraph Dynamic System
一句话总结: 出了一种超图动态系统（HDS），将超图和动态系统联系起来，描述表示的连续动态演化过程。提出的控制扩散超图动态系统通过常微分方程（ODE）实现，设计了一个多层HDSode作为神经实现，包含控制步骤和扩散步骤。
看起来解决了深层的 HGNN 模型的问题?
算法设计：
- 超图****动态系统：基于ODE，引入控制和扩散函数，形成超图动态系统模型。
- HDSode框架：设计了一个多层HDSode框架，实现可控且稳定的超图表示学习。
- 稳定性分析：证明了HDSode的稳定性，并展示了其在捕捉长距离顶点关系方面的能力。
VilLain: Self-Supervised Learning on Hypergraphs without Features via Virtual Label Propagation
一句话总结: 提出了一种新的自监督超图表示学习方法VilLain，基于虚拟标签（v-labels）的传播
算法设计：
- 虚拟标签生成：假设存在d个虚拟标签，并为每个节点分配一个稀疏的v-label概率分布。
- 超图上的v-label传播：通过交替在节点和超边之间传播v-label，来获得节点和超边的v-label分配矩阵。
- 多v-label传播：为了捕捉复杂的结构-标签模式，将嵌入空间划分为多个子空间，分别进行v-label传播，并最终连接各子空间的输出作为节点嵌入。
- 自监督损失函数设计：结合局部损失和全局损失，通过最大化节点和超边v-label分配向量的熵，确保标签的同质性和全局分布的均衡性和区分性。
Multi-Task Hypergraphs for Semi-supervised Learning using Earth Observations
背景和动机：在地球观测（Earth Observation）任务中，通常需要多任务处理不同的观测层数据。然而，由于传感器故障等原因，观测数据常常不完整。这一问题迫切需要一种能够在数据缺失情况下仍能有效学习的半监督学习方法。本文提出了一种强大的多任务超图（Multi-Task Hypergraph），通过利用不同任务之间的高阶依赖关系，在超图上实现多任务半监督学习。每个节点表示一个任务，通过不同路径形成的超边作为无监督教师，生成任务的可靠伪标签。
多任务超图结构：每个任务作为超图的节点，不同路径通过超图中的超边形成无监督教师。这些超边既作为教师也作为学生，通过自监督的方式进行学习。
超边集成模型：通过集成多个路径生成伪标签，提升伪标签的可靠性和鲁棒性。
自监督学习过程：利用NASA NEO数据集，进行大量实验验证多任务半监督学习方法的有效性。实验结果表明，该方法在数据分布逐渐变化的情况下，能够可靠地恢复多达七年的缺失数据。
主要贡献：
- 提出多任务超图框架：通过高阶任务依赖关系，实现了一个集成的、鲁棒的半监督学习方法。
- 设计了超边集成模型：利用多个路径生成伪标签，提升了伪标签的可靠性和模型的鲁棒性。
- 实验验证：在NASA NEO数据集上的实验表明，本文方法在多个基准任务上均取得了显著的性能提升，并能够适应数据分布的逐渐变化。
Efficient and Effective Attributed Hypergraph Clustering via 𝐾-Nearest Neighbor Augmentation
Efficient and Effective Attributed Hypergraph Clustering via 𝐾-Nearest Neighbor Augmentation
属性超图聚类（Attributed Hypergraph Clustering，AHC）旨在将属性超图中的节点划分为k个不相交的簇，使得同一簇内的节点在结构上紧密连接，并且属性相似，而不同簇的节点则属性差异显著。现有的AHC方法在处理大规模属性超图时面临计算成本高、聚类质量不佳等问题。
算法设计：本文提出了一种高效的属性超图聚类方法AHCKA（Attributed Hypergraph Clustering via K-nearest neighbor Augmentation），通过几个关键算法设计实现了高效的AHC：
- K-最近邻增强策略：利用属性信息优化超图结构，通过引入KNN图来构建额外的连接。
- 联合随机游走模型：设计了一个联合随机游走模型，以优化AHC目标。
- 高效求解器：利用矩阵运算和贪心迭代框架，大幅提升计算效率。
主要贡献：
- 提出了KNN增强策略：通过KNN图构建额外连接，有效利用属性信息提升超图结构的聚类质量。
- 设计了联合随机游走模型：结合超图和KNN图的高阶关系，以优化AHC的目标函数。
- 实现了高效求解器：通过矩阵运算和贪心迭代框架，显著提升了AHC的计算效率。
总结
本文提出的AHCKA方法通过KNN增强策略、联合随机游走模型和高效求解器，实现了高效的属性超图聚类。在多个实际数据集上的实验验证了其在聚类质量和计算效率上的优势，为大规模属性超图的聚类问题提供了一种有效的解决方案。未来工作将进一步优化KNN增强策略和随机游走模型，提高模型的适用性和鲁棒性。
MEGA: Multi-View Semi-Supervised Clustering of Hypergraphs
提出了一种多视图半监督超图聚类方法MEGA（Multi-view sEmi-supervised hyperGrAph clustering），结合实体的多种特征和部分已知标签信息，提升聚类性能。
背景和动机：在现实世界中，超图模型可以有效地表示复杂的实体间关系。传统的超图聚类方法主要依赖超图的连接结构，忽略了实体的其他属性和多视图关系。本文提出了一种多视图半监督超图聚类方法MEGA（Multi-view sEmi-supervised hyperGrAph clustering），结合实体的多种特征和部分已知标签信息，提升聚类性能。
算法设计：MEGA通过以下步骤实现多视图半监督聚类：
- 超图标准化切割与加权核K均值：证明超图标准化切割目标与加权核K均值目标的数学等价性，并基于此开发了一种高效的多级超图聚类算法hGraclus，为MEGA提供良好的初始化。
- 多视图聚类目标函数：将超图结构、实体的多种特征和关系以及部分已知标签信息整合到统一的非负矩阵分解（NMF）框架中，定义多视图聚类目标函数。
- 半监督聚类扩展：通过部分已知标签和成对约束，将多视图聚类目标函数扩展为半监督聚类框架。
目标函数:
$$\min_{W, H, \hat{H}j} \sum{i=1}^{p} \alpha_i |X_i - W_iH|F^2 + \sum{j=1}^{q} \beta_j |S_j - \hat{H}_j^TH|F^2 + \sum{j=1}^{q} \gamma_j |\hat{H}_j - H|_F^2 + |M \circ (P - WH)|_F^2$$