Abstract: Keywords: As a mathematical tool of naturally representing the high-order data correlation, hypergraphs exhibit significant advantages compared to traditional graph-based machine learning methods. The premise of the hypergraph-based learning paradigm lies in constructing hypergraph that can reflect the high-order relationships via hypergraph learning methods. However, the robustness of existing hypergraph learning methods in dealing with noise and data corruption limits their real applications. To address this issue, we propose a novel hypergraph learning method via block diagonal representation of the data. The proposed method optimizes an objective function of data reconstruction subject to the block diagonal constraint and generates hyperedges and define hyperedge weights using the derived reconstruction coefficients. The extensive experiments conducted on two real-world noisy image datasets demonstrate that the proposed method outperforms the existing hypergraph learning methods. Compared with the CR-HG (Correntropy-induced Low-rank Hypergraph) model, the proposed method achieves improvements of 2.6 and 1.0 percentage in clustering mutual information on the Coil 20 image dataset with 40% Gaussian noise ratio and 30% salt-and-pepper noise density, respectively. Additionally, on the USPS image dataset with 40% Gaussian noise ratio and 30% salt-and-pepper noise density, the proposed method increases the classification accuracy by 2.1 and 1.1 percentage, respectively. Overall, learning performance of the proposed method is superior to that of existing mainstream hypergraph learning methods.

Key words: Keywords: Block Orthogonality, Hyperedge generation, Hypergraph, Robustness, High-order relationship

摘要： 超图作为一种能够自然表征多元数据对象间高阶关系的数学工具，相较于传统图机器学习方法展现出显著优势。基于超图的机器学习范式的前提在于通过超图学习方法构建能够反映数据间高阶关系的超图。然而，现有超图学习方法在应对噪声和数据损坏方面的鲁棒性不足制约了其实际应用效果。为了解决超图学习的鲁棒性问题，提出一种基于块对角表示的超图学习方法。该方法通过优化一个引入块对角约束的数据重构目标函数，并利用获得的重构系数生成超边和设置超边权重。加入高斯噪声和椒盐噪声的图像数据集上的实验结果表明：与CR-HG (Correntropy-induced Low-rank Hypergrpah)模型相比，所提方法在加入高斯噪声的噪声率为40%和加入椒盐噪声的噪声密度为30%的Coil 20图像集上的聚类互信息分别提升2.6和1.0个百分点；在加入高斯噪声的噪声率40%和加入椒盐噪声的噪声密度为30%的USPS图像集上的分类准确率分别提升2.1和1.1个百分点，它的学习性能优于现有主流的超图学习方法。

关键词: 关键词: 块正交, 超边生成, 权重设置, 超图, 高阶关系