Hypergraph learning method via block diagonal representation

doi:10.11772/j.issn.1001-9081.2025050540

Journal of Computer Applications ›› 2026, Vol. 46 ›› Issue (4): 1042-1049.DOI: 10.11772/j.issn.1001-9081.2025050540

• Artificial intelligence • Previous Articles Next Articles

Hypergraph learning method via block diagonal representation

Shengwei ZHANG¹, Hao WANG², Taisong JIN²()

^1.Luoyang Institute of Electro-Optical Equipment of AVIC，Luoyang Henan 471000，China
^2.School of Informatics，Xiamen University，Xiamen Fujian 361102，China

Received:2025-05-19 Revised:2025-08-18 Accepted:2025-08-27 Online:2025-08-28 Published:2026-04-10
Contact: Taisong JIN
About author:ZHANG Shengwei， born in 1982， M. S.， research fellow. His research interests include computer vision， pattern recognition.
WANG Hao， born in 2001， M. S. candidate. His research interests include computer vision， pattern recognition.
Supported by:
General Program of National Natural Science Foundation of China(62072386);Fujian Provincial Natural Science Foundation(2025J01003)

基于块对角表示的超图学习方法

张生伟¹, 王豪², 金泰松²()

^1.中国航空工业集团公司洛阳电光设备研究所，河南洛阳 471000
^2.厦门大学信息学院，福建厦门 361102

通讯作者: 金泰松
作者简介:张生伟（1982—），男，河南南阳人，研究员，硕士，主要研究方向：计算机视觉、模式识别
王豪（2001—），男，河南安阳人，硕士研究生，主要研究方向：计算机视觉、模式识别
基金资助:
国家自然科学基金面上项目(62072386);福建省自然科学基金资助项目(2025J01003)

Abstract

Abstract:

As a mathematical tool of representing the high-order relationship among multiple data objectives naturally, hypergraphs exhibit significant advantages compared to traditional graph-based machine learning methods. The premise of hypergraph-based learning paradigm lies in constructing hypergraph that can reflect the high-order relationships via hypergraph learning methods. However, the lack of robustness of the existing hypergraph learning methods in dealing with noise and data corruption limits their real application effects. To address this issue, a hypergraph learning method via block diagonal representation was proposed. In the method, an objective function of data reconstruction introducing the block diagonal constraint was optimized, and hyperedges were generated and the hyperedge weights were set using the obtained reconstruction coefficients. Experimental results on two image datasets adding noise demonstrate that compared with CR-HG (CorrentRopy-induced low-rank HyperGraph) method, the proposed method achieves improvements of 2.6 and 1.0 percentage points in Normalized Mutual Information (NMI) on the Coil20 image set with 40% Gaussian noise ratio and 30% salt-and-pepper noise density, respectively. Additionally, on the USPS image set with 40% Gaussian noise ratio and 30% salt-and-pepper noise density, the proposed method increases the Classification Accuracy for Classification（ACC） by 2.1 and 1.1 percentage points, respectively. It can be seen that the learning performance of the proposed method is superior to that of the existing mainstream hypergraph learning methods.

Key words: block orthogonality, hyperedge generation, weight setting, hypergraph, high-order relationship

摘要：

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

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

CLC Number:

TP391

Shengwei ZHANG, Hao WANG, Taisong JIN. Hypergraph learning method via block diagonal representation[J]. Journal of Computer Applications, 2026, 46(4): 1042-1049.

张生伟, 王豪, 金泰松. 基于块对角表示的超图学习方法[J]. 《计算机应用》唯一官方网站, 2026, 46(4): 1042-1049.

Figures/Tables 11

References 40

[1]	BATTISTELLA E， VAKALOPOULOU M， PARAGIOS N， et al. GHOST： graph-based higher-order similarity transformation for classification［J］. Pattern Recognition， 2024， 155： No.110623.
[2]	ZHANG G， LIU T， YE Z. Dynamic screening strategy based on feature graphs for UAV object and group re-identification［J］. Remote Sensing， 2024， 16（5）： No.775.
[3]	FANG Y， PAN X， SHEN H B. De novo drug design by iterative multiobjective deep reinforcement learning with graph-based molecular quality assessment［J］. Bioinformatics， 2023， 39（4）： No.btad157.
[4]	SUNEERA C M， PRAKASH J， SINGH P K. Question answering over knowledge graphs using BERT based relation mapping［J］. Expert Systems， 2023， 40（10）： No.e13456.
[5]	LU J， WAN H， LI P， et al. Exploring high-order spatio-temporal correlations from skeleton for person re-identification［J］. IEEE Transactions on Image Processing， 2023， 32： 949-963.
[6]	马慧芳，刘芳，夏琴，等. 基于加权超图随机游走的文献关键词提取算法［J］. 电子学报， 2018， 46（6）： 1410-1414.
	MA H F， LIU F， XIA Q， et al. Keywords extraction algorithm based on weighted hypergraph random walk［J］. Acta Electronica Sinica， 2018， 46（6）： 1410-1414.
[7]	GAO Y， ZHANG Z， LIN H， et al. Hypergraph learning： methods and practices［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2022， 44（5）： 2548-2566.
[8]	陈子睿，王鑫，王晨旭，等. 面向时间感知的知识超图链接预测［J］. 软件学报， 2023， 34（10）： 4533-4547.
	CHEN Z R， WANG X， WANG C X， et al. Towards time-aware knowledge hypergraph link prediction［J］. Journal of Software， 2023， 34（10）： 4533-4547.
[9]	宗林林，周佳慧，谢秋婕，等. 基于超图的多模态情绪识别［J］. 计算机学报， 2023， 46（12）： 2520-2534.
	ZONG L L， ZHOU J H， XIE Q J， et al. Multi-modal emotion recognition based on hypergraph［J］. Chinese Journal of Computers， 2023， 46（12）： 2520-2534.
[10]	HUANG S， KANG Z， TSANG I W， et al. Auto-weighted multi-view clustering via kernelized graph learning［J］. Pattern Recognition， 2019， 88： 174-184.
[11]	LIU T， LIYANAARACHCHI LEKAMALAGE C K， HUANG G B， et al. An adaptive graph learning method based on dual data representations for clustering［J］. Pattern Recognition， 2018， 77： 126-139.
[12]	WANG W， YAN Y， NIE F， et al. Flexible manifold learning with optimal graph for image and video representation［J］. IEEE Transactions on Image Processing， 2018， 27（6）： 2664-2675.
[13]	郭正山，左劼，段磊，等. 面向知识超图链接预测的生成对抗负采样方法［J］. 计算机研究与发展， 2022， 59（8）： 1742-1756.
	GUO Z S， ZUO J， DUAN L， et al. A generative adversarial negative sampling method for knowledge hypergraph link prediction［J］. Journal of Computer Research and Development， 2022， 59（8）： 1742-1756.
[14]	于亚新，张文超，李振国，等. 基于超图的EBSN个性化推荐及优化算法［J］. 计算机研究与发展， 2020， 57（12）： 2556-2570.
	YU Y X， ZHANG W C， LI Z G， et al. Hypergraph-based personalized recommendation & optimization algorithm in EBSN［J］. Journal of Computer Research and Development， 2020， 57（12）： 2556-2570.
[15]	LI F， WANG X， CHENG D， et al. Hypergraph self-supervised learning with sampling-efficient signals［C］// Proceedings of the 33rd International Joint Conference on Artificial Intelligence. California： ijcai.org， 2024： 4398-4406.
[16]	ZHANG Z， XIAO Y， JIANG L， et al. Spatial-temporal interplay in human mobility： a hierarchical reinforcement learning approach with hypergraph representation［C］// Proceedings of the 38th AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2024： 9396-9404.
[17]	WANG M， LIU X， WU X. Visual classification by l₁-hypergraph modeling［J］. IEEE Transactions on Knowledge and Data Engineering， 2015， 27（9）： 2564-2574.
[18]	YU J， TAO D， WANG M. Adaptive hypergraph learning and its application in image classification［J］. IEEE Transactions on Image Processing， 2012， 21（7）： 3262-3272.
[19]	JIN T， JI R， GAO Y， et al. Correntropy-induced robust low-rank hypergraph［J］. IEEE Transactions on Image Processing， 2019， 28（6）： 2755-2769.
[20]	JIN T， YU J， YOU J， et al. Low-rank matrix factorization with multiple hypergraph regularizer［J］. Pattern Recognition， 2015， 48（3）： 1011-1022.
[21]	HUANG S， ELGAMMAL A， YANG D. On the effect of hyperedge weights on hypergraph learning［J］. Image and Vision Computing， 2017， 57： 89-101.
[22]	DUCOURNAU A， BRETTO A. Random walks in directed hypergraphs and application to semi-supervised image segmentation［J］. Computer Vision and Image Understanding， 2014， 120： 91-102.
[23]	PURKAIT P， CHIN T J， SADRI A， et al. Clustering with hypergraphs： the case for large hyperedges［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2017， 39（9）： 1697-1711.
[24]	ZHANG C， HU S， TANG Z G， et al. Re-revisiting learning on hypergraphs： confidence interval， subgradient method， and extension to multiclass［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（3）： 506-518.
[25]	WANG Z， CHEN J， SHAO Z， et al. Dual-view desynchronization hypergraph learning for dynamic hyperedge prediction［J］. IEEE Transactions on Knowledge and Data Engineering， 2025， 37（2）： 597-612.
[26]	LIU Q， SUN Y， WANG C， et al. Elastic-net hypergraph learning for image clustering and semi-supervised classification［J］. IEEE Transactions on Image Processing， 2017， 26（1）： 452-463.
[27]	ZHAO Y， LUO X， JU W， et al. Dynamic hypergraph structure learning for traffic flow forecasting［C］// Proceedings of the IEEE 39th International Conference on Data Engineering. Piscataway： IEEE， 2023： 2303-2316.
[28]	CAI D， SONG M， SUN C， et al. Hypergraph structure learning for hypergraph neural networks［C］// Proceedings of the 31st International Joint Conference on Artificial Intelligence. California： ijcai.org， 2022： 1923-1929.
[29]	LI M， YANG Y， MENG L， et al. Self-supervised hypergraph structure learning［J］. Artificial Intelligence Review， 2025， 58： No.190.
[30]	BAI J， GONG B， ZHAO Y， et al. Multi-scale representation learning on hypergraph for 3D shape retrieval and recognition［J］. IEEE Transactions on Image Processing， 2021， 30： 5327-5338.
[31]	GAO Y， FENG Y， JI S， et al. HGNN⁺： general hypergraph neural networks［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2023， 45（3）： 3181-3199.
[32]	VIJAIKUMAR M， HADA D， SHEVADE S. HyperTeNet： hypergraph and Transformer-based neural network for personalized list continuation［C］// Proceedings of the 2021 IEEE International Conference on Data Mining. Piscataway： IEEE， 2021： 1210-1215.
[33]	LI Y， CHEN H， SUN X， et al. Hyperbolic hypergraphs for sequential recommendation［C］// Proceedings of the 30th ACM International Conference on Information and Knowledge Management. New York： ACM， 2021： 988-997.
[34]	YU J， YIN H， LI J， et al. Self-supervised multi-channel hypergraph convolutional network for social recommendation［C］// Proceedings of the Web Conference 2021. New York： ACM， 2021： 413-424.
[35]	PEDRONETTE D C G， VALEM L P， ALMEIDA J， et al. Multimedia retrieval through unsupervised hypergraph-based manifold ranking［J］. IEEE Transactions on Image Processing， 2019， 28（12）： 5824-5838.
[36]	JIN T， YU Z， GAO Y， et al. Robust l₂-Hypergraph and its applications［J］. Information Sciences， 2019， 501： 708-723.
[37]	JIN T， CAO L， ZHANG B， et al. Hypergraph induced convolutional manifold networks［C］// Proceedings of the 28th International Joint Conference on Artificial Intelligence. California： ijcai.org， 2019： 2670-2676.
[38]	FENG Y， YOU H， ZHANG Z， et al. Hypergraph neural networks［C］// Proceedings of the 33rd AAAI Conference on Artificial Intelligence. Palo Alto： AAAI Press， 2019： 3558-3565.
[39]	LU C， FENG J， LIN Z， et al. Subspace clustering by block diagonal representation［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2019， 41（2）： 487-501.
[40]	TURK M， PENTLAND A. Eigenfaces for recognition［J］. Journal of Cognitive Neuroscience， 1991， 3（1）： 71-86.

方法	α=0%		α=10%		α=20%		α=30%		α=40%
方法	AC	NMI	AC	NMI	AC	NMI	AC	NMI	AC	NMI
KNN-HG	75.6	85.2	74.9	85.7	72.5	81.4	68.4	75.7	59.7	69.4
L₁-HG	77.2	87.6	76.7	86.2	75.4	82.4	73.7	82.1	72.5	81.7
L₂-HG	77.9	87.9	77.3	86.3	74.1	84.5	72.9	83.7	71.9	81.9
EN-HG	77.9	88.1	75.2	86.4	74.0	85.3	74.2	84.1	72.9	82.5
CR-HG	78.3	89.6	76.9	88.6	75.6	87.7	74.1	82.4	73.5	81.1
本文方法	79.5	90.3	78.9	89.8	76.7	87.5	73.7	83.9	73.9	83.7

方法	α=0%		α=10%		α=20%		α=30%		α=40%
方法	AC	NMI	AC	NMI	AC	NMI	AC	NMI	AC	NMI
KNN-HG	75.6	85.2	74.9	85.7	72.5	81.4	68.4	75.7	59.7	69.4
L₁-HG	77.2	87.6	76.7	86.2	75.4	82.4	73.7	82.1	72.5	81.7
L₂-HG	77.9	87.9	77.3	86.3	74.1	84.5	72.9	83.7	71.9	81.9
EN-HG	77.9	88.1	75.2	86.4	74.0	85.3	74.2	84.1	72.9	82.5
CR-HG	78.3	89.6	76.9	88.6	75.6	87.7	74.1	82.4	73.5	81.1
本文方法	79.5	90.3	78.9	89.8	76.7	87.5	73.7	83.9	73.9	83.7

方法	α=0%		α=10%		α=20%		α=30%		α=40%
方法	AC	NMI	AC	NMI	AC	NMI	AC	NMI	AC	NMI
KNN-HG	78.6	81.6	77.9	79.9	70.7	73.4	66.5	70.6	58.9	59.5
L₁-HG	77.5	80.6	76.9	78.7	77.8	77.9	74.5	76.7	73.9	72.9
L₂-HG	79.4	81.9	78.9	81.3	78.1	79.5	75.7	76.9	72.9	74.2
EN-HG	77.9	80.7	77.5	79.9	76.2	78.7	75.4	76.3	73.5	72.9
CR-HG	80.8	81.6	79.7	80.2	78.4	79.4	76.9	76.6	73.6	74.7
本文方法	81.2	81.8	80.9	81.9	80.6	81.5	76.7	79.9	74.5	75.7

方法	α=0%		α=10%		α=20%		α=30%		α=40%
方法	AC	NMI	AC	NMI	AC	NMI	AC	NMI	AC	NMI
KNN-HG	78.6	81.6	77.9	79.9	70.7	73.4	66.5	70.6	58.9	59.5
L₁-HG	77.5	80.6	76.9	78.7	77.8	77.9	74.5	76.7	73.9	72.9
L₂-HG	79.4	81.9	78.9	81.3	78.1	79.5	75.7	76.9	72.9	74.2
EN-HG	77.9	80.7	77.5	79.9	76.2	78.7	75.4	76.3	73.5	72.9
CR-HG	80.8	81.6	79.7	80.2	78.4	79.4	76.9	76.6	73.6	74.7
本文方法	81.2	81.8	80.9	81.9	80.6	81.5	76.7	79.9	74.5	75.7

方法	噪声密度为10%		噪声密度为20%		噪声密度为30%
方法	AC	NMI	AC	NMI	AC	NMI
KNN-HG	70.4	81.3	66.5	76.4	60.4	70.1
L₁-HG	72.8	82.2	70.4	78.7	67.7	74.5
L₂-HG	72.6	82.5	70.1	79.2	68.2	75.3
EN-HG	74.7	84.4	72.7	82.5	70.3	80.1
CR-HG	74.9	85.1	73.1	83.1	71.3	80.2
本文方法	75.4	86.2	73.8	84.1	71.8	81.2

Hypergraph learning method via block diagonal representation

基于块对角表示的超图学习方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 40

Related Articles 15

Recommended Articles

Metrics

方法	噪声密度为10%		噪声密度为20%		噪声密度为30%
方法	AC	NMI	AC	NMI	AC	NMI
KNN-HG	71.7	73.5	68.3	69.6	60.1	65.6
L₁-HG	72.8	75.3	70.2	72.9	68.2	70.6
L₂-HG	72.9	75.4	70.1	72.5	69.1	70.9
EN-HG	76.5	78.5	72.2	75.7	71.4	73.3
CR-HG	77.8	79.1	73.4	76.3	72.4	74.2
本文方法	78.4	80.3	74.2	77.1	72.9	75.3

[1]	Xing QIU, Zuxing XUAN, Kejia HUANG, Wen ZHANG, Xiao ZHUANG. Hypergraph-based eaves tile dating method under data imbalance conditions [J]. Journal of Computer Applications, 2026, 46(2): 620-629.
[2]	Cong WANG, Yancui SHI. Group recommendation model by graph neural network based on multi-perspective learning [J]. Journal of Computer Applications, 2025, 45(4): 1205-1212.
[3]	Hongyan ZHAO, Lihua GUO, Chunxia LIU, Riyun WANG. Scientific document summarization model based on multi-graph neural network and graph contrastive learning [J]. Journal of Computer Applications, 2025, 45(12): 3820-3828.
[4]	Jinghua ZHAO, Zhu ZHANG, Xiting LYU, Huidan LIN. Multiscale information diffusion prediction model based on hypergraph neural network [J]. Journal of Computer Applications, 2025, 45(11): 3529-3539.
[5]	Wenbo ZHAO, Zitong MA, Zhe YANG. Link prediction model based on directed hypergraph adaptive convolution [J]. Journal of Computer Applications, 2025, 45(1): 15-23.
[6]	Li ZENG, Jingru YANG, Gang HUANG, Xiang JING, Chaoran LUO. Survey on hypergraph application methods： issues， advances， and challenges [J]. Journal of Computer Applications, 2024, 44(11): 3315-3326.
[7]	Nengqiang XIANG, Xiaofei ZHU, Zhaoze GAO. Information diffusion prediction model of prototype-aware dual-channel graph convolutional neural network [J]. Journal of Computer Applications, 2024, 44(10): 3260-3266.
[8]	Lantian XU, Ronghua LI, Yongheng DAI, Guoren WANG. Maximal clique searching algorithm for hypergraphs [J]. Journal of Computer Applications, 2023, 43(8): 2319-2324.
[9]	Weichao DANG, Bingyang CHENG, Gaimei GAO, Chunxia LIU. Contrastive hypergraph transformer for session-based recommendation [J]. Journal of Computer Applications, 2023, 43(12): 3683-3688.
[10]	Xiaojie LI, Chaoran CUI, Guangle SONG, Yaxi SU, Tianze WU, Chunyun ZHANG. Stock trend prediction method based on temporal hypergraph convolutional neural network [J]. Journal of Computer Applications, 2022, 42(3): 797-803.
[11]	TIAN Ling, ZHANG Jinchuan, ZHANG Jinhao, ZHOU Wangtao, ZHOU Xue. Knowledge graph survey： representation， construction， reasoning and knowledge hypergraph theory [J]. Journal of Computer Applications, 2021, 41(8): 2161-2186.
[12]	Yongkai ZHANG, Zhihao WU, Youfang LIN, Yiji ZHAO. Spatio-temporal hyper-relationship graph convolutional network for traffic flow forecasting [J]. Journal of Computer Applications, 2021, 41(12): 3578-3584.
[13]	ZHOU Yang, WU Qiwu, JIANG Lingzhi. Group key management scheme based on distributed path computing element in multi-domain optical network [J]. Journal of Computer Applications, 2019, 39(4): 1095-1099.
[14]	YU Jianglan, LI Xiangli, ZHAO Pengfei. Sparse non-negative matrix factorization based on kernel and hypergraph regularization [J]. Journal of Computer Applications, 2019, 39(3): 742-749.
[15]	LIU Shengjiu, LI Tianrui, YANG Zonglin, ZHU Jie. Measure method and properties of weighted hypernetwork [J]. Journal of Computer Applications, 2019, 39(11): 3107-3113.

图像集	样本数	特征维数	类别数
Coil20	1 440	1 024	20
USPS	9 298	256	10

图像集	样本数	特征维数	类别数
Coil20	1 440	1 024	20
USPS	9 298	256	10

方法	Coil20					USPS
方法	α=0%	α=10%	α=20%	α=30%	α=40%	α=0%	α=10%	α=20%	α=30%	α=40%
KNN-HG	93.5	92.7	86.2	83.1	77.8	95.3	95.9	90.5	83.9	75.3
L₁-HG	95.3	95.3	93.6	92.3	90.3	97.3	97.9	95.3	89.3	81.2
L₂-HG	96.4	95.1	94.3	93.1	92.5	98.7	96.9	95.9	94.3	93.7
Ada-HG	94.6	93.5	89.3	85.7	81.1	96.9	95.4	92.5	84.7	78.3
EN-HG	95.1	93.5	92.3	91.2	89.5	95.7	93.3	91.9	91.3	89.4
CR-HG	97.3	95.1	95.1	94.3	92.0	98.6	96.9	95.3	93.5	91.6
本文方法	97.8	96.7	95.8	94.9	93.5	98.9	97.9	96.1	94.9	93.7

方法	Coil20					USPS
方法	α=0%	α=10%	α=20%	α=30%	α=40%	α=0%	α=10%	α=20%	α=30%	α=40%
KNN-HG	93.5	92.7	86.2	83.1	77.8	95.3	95.9	90.5	83.9	75.3
L₁-HG	95.3	95.3	93.6	92.3	90.3	97.3	97.9	95.3	89.3	81.2
L₂-HG	96.4	95.1	94.3	93.1	92.5	98.7	96.9	95.9	94.3	93.7
Ada-HG	94.6	93.5	89.3	85.7	81.1	96.9	95.4	92.5	84.7	78.3
EN-HG	95.1	93.5	92.3	91.2	89.5	95.7	93.3	91.9	91.3	89.4
CR-HG	97.3	95.1	95.1	94.3	92.0	98.6	96.9	95.3	93.5	91.6
本文方法	97.8	96.7	95.8	94.9	93.5	98.9	97.9	96.1	94.9	93.7