Survey on hypergraph application methods： issues， advances， and challenges

doi:10.11772/j.issn.1001-9081.2023111629

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (11): 3315-3326.DOI: 10.11772/j.issn.1001-9081.2023111629

• Artificial intelligence • Next Articles

Survey on hypergraph application methods： issues， advances， and challenges

Li ZENG¹^,², Jingru YANG¹, Gang HUANG¹^,³, Xiang JING¹^,², Chaoran LUO¹()

^1.National Key Laboratory of Dataspace Technology and System，Beijing 100091，China
^2.School of Software and Microelectronics，Peking University，Beijing 102600，China
^3.School of Computer Science，Peking University，Beijing 100871，China

Received:2023-12-01 Accepted:2024-01-01 Online:2024-01-04 Published:2024-11-10
Contact: Chaoran LUO
About author:ZENG Li， born in 2000， M. S. candidate. His research interests include system software， internet of data， dataspace.
YANG Jingru， born in 1995， Ph. D.， assistant research fellow. Her research interests include big data governance， data analysis， dataspace.
HUANG Gang， born in 1975， Ph. D.， professor. His research interests include system software， software adaptation， internet of data.
JING Xiang， born in 1979， Ph. D.， associate professor. His research interests include operating system， distributed computing.
Supported by:
National Basic Research Program of China(2021YFF0901100)

超图应用方法综述：问题、进展与挑战

曾蠡¹^,², 杨婧如¹, 黄罡¹^,³, 景翔¹^,², 罗超然¹()

^1.数据空间技术与系统全国重点实验室，北京 100091
^2.北京大学软件与微电子学院，北京 102600
^3.北京大学计算机学院，北京 100871

通讯作者: 罗超然
作者简介:曾蠡（2000—），男，湖南娄底人，硕士研究生，主要研究方向：系统软件、数联网、数据空间
杨婧如（1995—），女，黑龙江双鸭山人，助理研究员，博士，主要研究方向：大数据治理、数据分析、数据空间
黄罡（1975—），男，湖南株洲人，教授，博士，主要研究方向：系统软件、软件自适应、数联网
景翔（1979—），男，江苏无锡人，副教授，博士，主要研究方向：操作系统、分布式计算；
基金资助:
国家重点基础研究发展计划项目(2021YFF0901100)

Abstract

Abstract:

Hypergraph is the generalization of graph， which has significant advantages in representing higher-order features of complex relationships compared with ordinary graph. As a relatively new data structure， hypergraph is playing a crucial role in various application fields increasingly. By appropriately using hypergraph models and algorithms， specific problems in real world were modeled and solved with higher efficiency and quality. Existing surveys of hypergraph mainly focus on the theory and techniques of hypergraph itself， and lack of a summary of modeling and solving methods in specific scenarios. To this end， after summarizing and introducing some fundamental concepts of hypergraph， the application methods， techniques， common issues， and solutions of hypergraph in various application scenarios were analyzed； by summarizing the existing work， some problems and obstacles that still exist in the applications of hypergraph to real-world problems were elaborated. Finally， the future research directions of hypergraph applications were prospected.

Key words: hypergraph application, image processing, network analysis, recommender system, distributed network

摘要：

超图是图的泛化，相较于普通图，它在复杂关系的高阶特征表达上具有显著优势。作为一种相对较新的数据结构，超图在应用领域正在发挥越来越大的作用，研究者采用超图模型及算法对现实世界中的具体问题进行建模、求解，有效地提升了解决问题的效率及质量。现有对超图的综述更多侧重于解决超图本身问题的理论及技术，缺乏对超图在具体应用场景下的建模及求解方法的归纳总结。为此，在总结介绍超图的一些基础概念后，分析了超图在各个主流应用场景下的应用方法、技术、共性问题及解决方案；通过对现有工作的归纳总结，阐述了超图运用于现实问题中仍然存在的一些问题与障碍；最后，对超图应用的未来研究方向进行了展望。

关键词: 超图应用, 图像处理, 网络分析, 推荐系统, 分布式网络

CLC Number:

TP311

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.

曾蠡, 杨婧如, 黄罡, 景翔, 罗超然. 超图应用方法综述：问题、进展与挑战[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3315-3326.

Figures/Tables 6

References 89

1	ÇATALYÜREK Ü， DEVINE K， FARAJ M， et al. More recent advances in （hyper）graph partitioning［J］. ACM Computing Surveys， 2023， 55（12）： No.253.
2	胡秉德，王新根，王新宇，等.超图学习综述：算法分类与应用分析［J］.软件学报，2022，33（2）：498-523.
	HU B D， WANG X G， WANG X Y， et al. Survey on hypergraph learning： algorithm classification and application analysis［J］. Journal of Software， 2022， 33（2）： 498-523.
3	ZHOU D， HUANG J， SCHÖLKOPF B. Learning with hypergraphs： clustering， classification， and embedding［C］// Proceedings of the 19th International Conference on Neural Information Processing Systems. Cambridge： MIT Press， 2006： 1601-1608.
4	ZHANG R， ZOU Y， MA J. Hyper-SAGNN： a self-attention based graph neural network for hypergraphs［EB/OL］. ［2023-09-21］..
5	JIANG W， QI J， YU J X， et al. HyperX： a scalable hypergraph framework［J］. IEEE Transactions on Knowledge and Data Engineering， 2019， 31（5）： 909-922.
6	LIN Y R， SUN J， CASTRO P， et al. MetaFac： community discovery via relational hypergraph factorization［C］// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2009： 527-536.
7	KOYUTÜRK M， AYKANAT C. Iterative-improvement-based declustering heuristics for multi-disk databases［J］. Information Systems， 2005， 30（1）： 47-70.
8	TURK A， SELVITOPI R O， FERHATOSMANOGLU H， et al. Temporal workload-aware replicated partitioning for social networks［J］. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（11）： 2832-2845.
9	LI Y， ZHAO L， CUI C， et al. Fast big data analysis in geo-distributed cloud［C］// Proceedings of the 2016 IEEE International Conference on Cluster Computing. Piscataway： IEEE， 2016： 388-391.
10	ZHAO H， LIU X， LI X. Towards efficient and fair resource trading in community-based cloud computing［J］. Journal of Parallel and Distributed Computing， 2014， 74（11）： 3087-3097.
11	ÇATALYÜREK Ü V， KAYA K， UÇAR B. Integrated data placement and task assignment for scientific workflows in clouds［C］// Proceedings of the 4th International Workshop on Data-Intensive Distributed Computing. New York： ACM， 2011： 45-54.
12	LI C， TANG J， MA T， et al. Load balance based workflow job scheduling algorithm in distributed cloud［J］. Journal of Network and Computer Applications， 2020， 152： No.102518.
13	ZHANG H， SONG L， HAN Z. Radio resource allocation for device-to-device underlay communication using hypergraph theory［J］. IEEE Transactions on Wireless Communications， 2016， 15（7）： 4852-4861.
14	WANG L， WU H， DING Y， et al. Hypergraph-based wireless distributed storage optimization for cellular D2D underlays［J］. IEEE Journal on Selected Areas in Communications， 2016， 34（10）： 2650-2666.
15	LUO Q， YU D， CAI Z， et al. Hypercore maintenance in dynamic hypergraphs［C］// Proceedings of the IEEE 37th International Conference on Data Engineering. Piscataway： IEEE， 2021： 2051-2056.
16	GUAN Z， MIAO G， McLOUGHLIN R， et al. Co-occurrence-based diffusion for expert search on the Web［J］. IEEE Transactions on Knowledge and Data Engineering， 2013， 25（5）： 1001-1014.
17	FANG Q， SANG J， XU C， et al. Topic-sensitive influencer mining in interest-based social media networks via hypergraph learning［J］. IEEE Transactions on Multimedia， 2014， 16（3）： 796-812.
18	LI D， XU Z， LI S， et al. Link prediction in social networks based on hypergraph［C］// Proceedings of the 22nd International Conference on World Wide Web. New York： ACM， 2013： 41-42.
19	YANG D， QU B， YANG J， et al. Revisiting user mobility and social relationships in LBSNs： a hypergraph embedding approach［C］// Proceedings of the 2019 World Wide Web Conference. New York： ACM， 2019： 2147-2157.
20	FAN H， ZHANG F， WEI Y， et al. Heterogeneous hypergraph variational autoencoder for link prediction［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2022， 44（8）： 4125-4138.
21	WANG J， ZHANG Y， WEI Y， et al. Metro passenger flow prediction via dynamic hypergraph convolution networks［J］. IEEE Transactions on Intelligent Transportation Systems， 2021， 22（12）： 7891-7903.
22	WANG J， ZHANG Y， WANG L， et al. Multitask hypergraph convolutional networks： a heterogeneous traffic prediction framework［J］. IEEE Transactions on Intelligent Transportation Systems， 2022， 23（10）： 18557-18567.
23	张永凯，武志昊，林友芳，等.面向交通流量预测的时空超关系图卷积网络［J］.计算机应用，2021，41（12）：3578-3584.
	ZHANG Y K， WU Z H， LIN Y F， et al. Spatio-temporal hyper-relationship graph convolutional network for traffic flow forecasting［J］. Journal of Computer Applications， 2021， 41（12）： 3578-3584.
24	LI P Z， HUANG L， WANG C D， et al. EdMot： an edge enhancement approach for motif-aware community detection［C］// Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2019： 479-487.
25	HUANG L， CHAO H Y， XIE G Q. MuMod： a micro-unit connection approach for hybrid-order community detection［C］// Proceedings of the 34th AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2020： 107-114.
26	HUANG L， TANG Y， FU C Z， et al. GHOC： a generative model for hybrid-order community detection［J］. International Journal of Intelligent Systems， 2022， 37（11）： 9055-9079.
27	XU J， SINGH V， GUAN Z， et al. Unified hypergraph for image ranking in a multimodal context［C］// Proceedings of the 2012 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway： IEEE， 2012： 2333-2336.
28	GAO Y， WANG M， ZHA Z J， et al. Visual-textual joint relevance learning for tag-based social image search［J］. IEEE Transactions on Image Processing， 2013， 22（1）： 363-376.
29	YU J， TAO D， WANG M， et al. Learning to rank using user clicks and visual features for image retrieval［J］. IEEE Transactions on Cybernetics， 2015， 45（4）： 767-779.
30	ZHU L， SHEN J， XIE L. Topic hypergraph hashing for mobile image retrieval［C］// Proceedings of the 23rd ACM International Conference on Multimedia. New York： ACM， 2015： 843-846.
31	ZHU L， SHEN J， XIE L， et al. Unsupervised topic hypergraph hashing for efficient mobile image retrieval［J］. IEEE Transactions on Cybernetics， 2017， 47（11）： 3941-3954.
32	LEE J， CHO M， LEE K M. Hyper-graph matching via reweighted random walks［C］// Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2011： 1633-1640.
33	LEORDEANU M， ZANFIR A， SMINCHISESCU C. Semi-supervised learning and optimization for hypergraph matching［C］// Proceedings of the 2011 International Conference on Computer Vision. Piscataway： IEEE， 2011： 2274-2281.
34	HONG C， YU J， YOU J， et al. Multi-view ensemble manifold regularization for 3D object recognition［J］. Information Sciences， 2015， 320： 395-405.
35	HUANG Y， LIU Q， LV F， et al. Unsupervised image categorization by hypergraph partition［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2011， 33（6）： 1266-1273.
36	SHI H， ZHANG Y， ZHANG Z， et al. Hypergraph-induced convolutional networks for visual classification［J］. IEEE Transactions on Neural Networks and Learning Systems， 2019， 30（10）： 2963-2972.
37	CHEN G， ZHANG J， WANG F， et al. Efficient multi-label classification with hypergraph regularization［C］// Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2009： 1658-1665.
38	ZHANG Y F， XU C， CHENG J， et al. Naming faces in films using hypergraph matching［C］// Proceedings of the 2009 IEEE International Conference on Multimedia and Expo. Piscataway： IEEE， 2009： 278-281.
39	AN L， CHEN X， YANG S. Person re-identification via hypergraph-based matching［J］. Neurocomputing， 2016， 182： 247-254.
40	HUANG Y， LIU Q， METAXAS D. Video object segmentation by hypergraph cut［C］// Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2009： 1738-1745.
41	KIM S， YOO C D， NOWOZIN S， et al. Image segmentation using higher-order correlation clustering［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2014， 36（9）： 1761-1774.
42	ZHAO S. Image emotion computing［C］// Proceedings of the 24th ACM International Conference on Multimedia. New York： ACM， 2016： 1435-1439.
43	ZHAO S， YAO H， GAO Y， et al. Predicting personalized emotion perceptions of social images［C］// Proceedings of the 24th ACM International Conference on Multimedia. New York： ACM， 2016： 1385-1394.
44	YU J， RUI Y， CHEN B. Exploiting click constraints and multi-view features for image re-ranking［J］. IEEE Transactions on Multimedia， 2014， 16（1）： 159-168.
45	HUANG Y， LIU Q， ZHANG S， et al. Image retrieval via probabilistic hypergraph ranking［C］// Proceedings of the 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway： IEEE， 2010： 3376-3383.
46	YU J， RUI Y， TANG Y Y， et al. High-order distance-based multiview stochastic learning in image classification［J］. IEEE Transactions on Cybernetics， 2014， 44（12）： 2431-2442.
47	PLIAKOS K， KOTROPOULOS C. Simultaneous image tagging and geo-location prediction within hypergraph ranking framework［C］// Proceedings of the 2014 IEEE International Conference on Acoustics， Speech and Signal Processing. Piscataway： IEEE， 2014： 6894-6898.
48	MURTHY V N， SHARMA A， CHARI V， et al. Image annotation using multi-scale hypergraph heat diffusion framework［C］// Proceedings of the 2016 ACM International Conference on Multimedia Retrieval. New York： ACM， 2016： 299-303.
49	TANG C， LIU X， WANG P， et al. Adaptive hypergraph embedded semi-supervised multi-label image annotation［J］. IEEE Transactions on Multimedia， 2019， 21（11）： 2837-2849.
50	YE M， YIN P， LEE W C， et al. Exploiting geographical influence for collaborative point-of-interest recommendation［C］// Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2011： 325-334.
51	YANG T， YANG C， ZHANG L， et al. Co-clustering interactions via attentive hypergraph neural network［C］// Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2022： 859-869.
52	BU J， TAN S， CHEN C， et al. Music recommendation by unified hypergraph： combining social media information and music content［C］// Proceedings of the 18th ACM International Conference on Multimedia. New York： ACM， 2010： 391-400.
53	LA GATTA V， MOSCATO V， PENNONE M， et al. Music recommendation via hypergraph embedding［J］. IEEE Transactions on Neural Networks and Learning Systems， 2023， 34（10）： 7887-7899.
54	LI L， LI T. News recommendation via hypergraph learning： encapsulation of user behavior and news content［C］// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. New York： ACM， 2013： 305-314.
55	GHARAHIGHEHI A， VENS C， PLIAKOS K. Fair multi-stakeholder news recommender system with hypergraph ranking［J］. Information Processing and Management， 2021， 58（5）： No.102663.
56	YAO L， SHENG Q Z， NGU A H H， et al. Things of interest recommendation by leveraging heterogeneous relations in the Internet of Things［J］. ACM Transactions on Internet Technology， 2016， 16（2）： No.9.
57	RONG G， ZHANG Y， YANG L， et al. Modeling review history for reviewer recommendation： a hypergraph approach［C］// Proceedings of the ACM/IEEE 44th International Conference on Software Engineering. New York： ACM， 2022： 1381-1392.
58	JIA R， ZHOU X， DONG L， et al. Hypergraph convolutional network for group recommendation［C］// Proceedings of the 2021 IEEE International Conference on Data Mining. Piscataway： IEEE， 2021： 260-269.
59	GUO L， YIN H， CHEN T， et al. Hierarchical hyperedge embedding-based representation learning for group recommendation［J］. ACM Transactions on Information Systems， 2022， 40（1）： No.3.
60	WANG J， DING K， HONG L， et al. Next-item recommendation with sequential hypergraphs［C］// Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2020： 1101-1110.
61	MA X， ZHAO T， GUO Q， et al. Fuzzy hypergraph network for recommending top-K profitable stocks［J］. Information Sciences， 2022， 613： 239-255.
62	李晓杰，崔超然，宋广乐，等.基于时序超图卷积神经网络的股票趋势预测方法［J］.计算机应用，2022，42（3）：797-803.
	LI X J， CUI C R， SONG G L， et al. Stock trend prediction method based on temporal hypergraph convolutional neural network［J］. Journal of Computer Applications， 2022， 42（3）： 797-803.
63	WANG J， DING K， ZHU Z， et al. Session-based recommendation with hypergraph attention networks［C］// Proceedings of the 2021 SIAM International Conference on Data Mining. Philadelphia， PA： SIAM， 2021： 82-90.
64	党伟超，程炳阳，高改梅，等.基于对比超图转换器的会话推荐［J］.计算机应用，2023，43（12）：3683-3688.
	DANG W C， CHENG B Y， GAO G M， et al. Contrastive hypergraph transformer for session-based recommendation［J］. Journal of Computer Applications， 2023， 43（12）： 3683-3688.
65	ZHAO S， WEI W， LIU Y， et al. Towards hierarchical policy learning for conversational recommendation with hypergraph-based reinforcement learning［C］// Proceedings of the 32nd International Joint Conferences on Artificial Intelligence. California： IJCAI， 2023： 2459-2467.
66	ZHAO S， WEI W， MAO X L， et al. Multi-view hypergraph contrastive policy learning for conversational recommendation［C］// Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2023： 654-664.
67	VAN LIERDE H， CHOW T W S. A hypergraph model for incorporating social interactions in collaborative filtering［C］// Proceedings of the 2017 International Conference on Data Mining， Communications and Information Technology. New York： ACM， 2017： No.32.
68	ZHENG X， LUO Y， SUN L， et al. A novel social network hybrid recommender system based on hypergraph topologic structure［J］. World Wide Web， 2018， 21： 985-1013.
69	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.
70	CHEN X， XIONG K， ZHANG Y， et al. Neural feature-aware recommendation with signed hypergraph convolutional network［J］. ACM Transactions on Information Systems， 2021， 39（1）： No.8.
71	WU H， LONG J， LI N， et al. Adversarial auto-encoder domain adaptation for cold-start recommendation with positive and negative hypergraphs［J］. ACM Transactions on Information Systems， 2023， 41（2）： No.33.
72	LIU B， ZHAO P， ZHUANG F， et al. Knowledge-aware hypergraph neural network for recommender systems［C］// Proceedings of the 2021 International Conference on Database Systems for Advanced Applications， LNCS 12683. Cham： Springer， 2021： 132-147.
73	WU G， LI J-Z， HU J-Q， et al. System Π： a native RDF repository based on the hypergraph representation for RDF data model［J］. Journal of Computer Science and Technology， 2009， 24（4）： 652-664.
74	MOK W Y， FONG J， EMBLEY D W. Extracting a largest redundancy-free XML storage structure from an acyclic hypergraph in polynomial time［J］. Information Systems， 2010， 35（7）： 804-824.
75	FONG J， MOK W Y， LI H. Design non-recursive and redundant-free XML conceptual schema with hypergraph （extended abstract）［C］// Proceedings of the 2011 International Conference on Database Systems for Advanced Applications， LNCS 6637. Berlin： Springer， 2011： 40-52.
76	GHALEB F F M， TAHA A A， HAZMAN M， et al. RDF-BF-Hypergraph representation for relational database［J］. International Journal of Mathematics and Computer Science， 2020， 15（1）： 41-64.
77	BAIARDI F， TELMON C， SGANDURRA D. Hierarchical， model-based risk management of critical infrastructures［J］. Reliability Engineering and System Safety， 2009， 94（9）： 1403-1415.
78	LI Y， SHEN H. Preventing identity disclosure in hypergraphs［C］// Proceedings of the IEEE 11th International Conference on Data Mining Workshops. Piscataway： IEEE， 2011： 659-665.
79	HIBAOUI A EL， VALLET L. Hypergraph model for anonymous communications［C］// Proceedings of the 2012 International Conference on Multimedia Computing and Systems. Piscataway： IEEE， 2012： 888-894.
80	YAMAGUCHI Y， OGAWA A， TAKEDA A， et al. Cyber security analysis of power networks by hypergraph cut algorithms［J］. IEEE Transactions on Smart Grid， 2015， 6（5）： 2189-2199.
81	周阳，吴启武，姜灵芝.基于分布式路径计算单元的多域光网络组密钥管理方案［J］.计算机应用，2019，39（4）：1095-1099.
	ZHOU Y， WU Q W， JIANG L Z. 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.
82	ZHU J， ZHAO X， HU H， et al. Emotion recognition from physiological signals using multi-hypergraph neural networks［C］// Proceedings of the 2019 IEEE International Conference on Multimedia and Expo. Piscataway： IEEE， 2019： 610-615.
83	LIANG Z， OBA S， ISHII S. An unsupervised EEG decoding system for human emotion recognition［J］. Neural Networks， 2019， 116： 257-268.
84	ZHAO S， DING G， HAN J， et al. Personality-aware personalized emotion recognition from physiological signals［C］// Proceedings of the 27th International Joint Conferences on Artificial Intelligence. California： IJCAI， 2018： 1660-1667.
85	ZHAO S， GHOLAMINEJAD A， DING G， et al. Personalized emotion recognition by personality-aware high-order learning of physiological signals［J］. ACM Transactions on Multimedia Computing， Communications， and Applications， 2019， 15（1s）： No.14.
86	ACER S， SELVITOPI O， AYKANAT C. Optimizing nonzero-based sparse matrix partitioning models via reducing latency［J］. Journal of Parallel and Distributed Computing， 2018， 122： 145-158.
87	ABUBAKER N， ACER S， AYKANAT C. True load balancing for matricized tensor times Khatri-Rao product［J］. IEEE Transactions on Parallel and Distributed Systems， 2021， 32（8）： 1974-1986.
88	DEMIRCI G V， FERHATOSMANOGLU H. Partitioning sparse deep neural networks for scalable training and inference［C］// Proceedings of the 35th ACM International Conference on Supercomputing. New York： ACM， 2021： 254-265.
89	KARUMBA S， KANHERE S S， JURDAK R， et al. HARB： a hypergraph-based adaptive consortium blockchain for decentralized energy trading［J］. IEEE Internet of Things Journal， 2022， 9（16）： 14216-14227.

应用方向	应用场景	建模方法	求解方法	代表论文	求解技术
资源和任务放置优化	数据放置优化	数据建模为顶点，查询操作建模为超边	超图划分和团块发现为主	文献［7］	启发式算法及转化为优化问题求解为主
	任务负载优化	设备、数据等任务需要资源建模为顶点，任务建模为超边		文献［8］
	资源分配优化	用户建模为顶点，资源分配建模为超边		文献［10］
	工作流优化	任务建模为顶点，工作流先后顺序建模为超边		文献［11］
D2D网络性能优化	信道分配优化	设备或用户建模为顶点，信道建模为超边	超图划分	文献［13］	超图染色
D2D网络性能优化	设备缓存优化	存储设备/缓存和用户建模为超边，资源请求行为建模为超边	超图划分	文献［14］	超图搜索，转化为优化问题求解

应用方向	应用场景	建模方法	求解方法	代表论文	求解技术
资源和任务放置优化	数据放置优化	数据建模为顶点，查询操作建模为超边	超图划分和团块发现为主	文献［7］	启发式算法及转化为优化问题求解为主
	任务负载优化	设备、数据等任务需要资源建模为顶点，任务建模为超边		文献［8］
	资源分配优化	用户建模为顶点，资源分配建模为超边		文献［10］
	工作流优化	任务建模为顶点，工作流先后顺序建模为超边		文献［11］
D2D网络性能优化	信道分配优化	设备或用户建模为顶点，信道建模为超边	超图划分	文献［13］	超图染色
D2D网络性能优化	设备缓存优化	存储设备/缓存和用户建模为超边，资源请求行为建模为超边	超图划分	文献［14］	超图搜索，转化为优化问题求解

应用方向	应用场景	建模方法	求解方法	代表论文	求解技术
图像检索	基于图片、文字信息检索图像	将图片、标签等信息作为顶点，视觉相似性低阶特征或社交关系等高阶特征构建超边	基于标签或视觉相似性确定图像之间的距离，进而进行检索	文献［28-30］	主要使用超图神经网络对特征与信息进行学习并计算相似性距离，还可利用图像哈希提高搜索效率
图像配准、融合和重建	图像配准，融合和重建	将图像中的视觉特征点作为顶点，根据图片中点集间相互关系构造超边	寻找超图全局或部分同构，进行超图匹配	文献［32-34］	主要通过谱分析和神经网络等超图学习方法学习超图模式并进行比较
目标分析	图像分类	以包含特定对象的图片作为顶点，然后根据视觉和语义相似性构造超边	主要使用超图划分和团块发现等思想提取图片中的目标	文献［35，37］	主要通过谱分析、神经网络等超图学习方法以及超图划分算法等超图上算法进行目标提取与分析
	目标检测	将目标作为顶点，根据时空和相似关系等构建超边		文献［39］
	图像分割	将像素块作为顶点，根据相似性等关系构造超边		文献［40］
情感分析	图像情感分析	将时间、情绪、视觉内容等作为顶点，利用超边包括这些顶点进行潜在模式学习	主要使用超图对视觉内容、时间演变、社会情境、位置影响等多模态数据进行表征学习	文献［43］	主要通过谱分析、神经网络等超图学习方法对复杂的多模态数据进行学习并推测情感
图像处理共性问题	高阶关系挖掘	通过流形寻找超图内的内在联系，简化后挖掘效果更好	结合流形学习思想进行降维	文献［45-46］	将超图流形降维后在重构超图上进行超图学习
图像处理共性问题	图像检索能力提升	提高图像检索能力主要将图片、标签等建模为顶点，根据相关性构建超图，实现标签标注任务	给图像赋予更加丰富的文字信息以方便检索	文献［48-49］	使用标签传播算法以及超图学习方法给图像增加文字信息

应用方向	应用场景	建模方法	求解方法	代表论文	求解技术
图像检索	基于图片、文字信息检索图像	将图片、标签等信息作为顶点，视觉相似性低阶特征或社交关系等高阶特征构建超边	基于标签或视觉相似性确定图像之间的距离，进而进行检索	文献［28-30］	主要使用超图神经网络对特征与信息进行学习并计算相似性距离，还可利用图像哈希提高搜索效率
图像配准、融合和重建	图像配准，融合和重建	将图像中的视觉特征点作为顶点，根据图片中点集间相互关系构造超边	寻找超图全局或部分同构，进行超图匹配	文献［32-34］	主要通过谱分析和神经网络等超图学习方法学习超图模式并进行比较
目标分析	图像分类	以包含特定对象的图片作为顶点，然后根据视觉和语义相似性构造超边	主要使用超图划分和团块发现等思想提取图片中的目标	文献［35，37］	主要通过谱分析、神经网络等超图学习方法以及超图划分算法等超图上算法进行目标提取与分析
	目标检测	将目标作为顶点，根据时空和相似关系等构建超边		文献［39］
	图像分割	将像素块作为顶点，根据相似性等关系构造超边		文献［40］
情感分析	图像情感分析	将时间、情绪、视觉内容等作为顶点，利用超边包括这些顶点进行潜在模式学习	主要使用超图对视觉内容、时间演变、社会情境、位置影响等多模态数据进行表征学习	文献［43］	主要通过谱分析、神经网络等超图学习方法对复杂的多模态数据进行学习并推测情感
图像处理共性问题	高阶关系挖掘	通过流形寻找超图内的内在联系，简化后挖掘效果更好	结合流形学习思想进行降维	文献［45-46］	将超图流形降维后在重构超图上进行超图学习
图像处理共性问题	图像检索能力提升	提高图像检索能力主要将图片、标签等建模为顶点，根据相关性构建超图，实现标签标注任务	给图像赋予更加丰富的文字信息以方便检索	文献［48-49］	使用标签传播算法以及超图学习方法给图像增加文字信息

应用方向	应用领域	建模方法	求解方法	代表论文	求解技术
利用社会关系增强推荐	音乐推荐、新闻推荐等	将需要推荐的内容、用户作为顶点，根据社交关系等关联关系构建超边	结合社会关系等数据增强推荐效果	文献［52-54， 57］	使用超图排序算法、超图学习等方法进行推荐
针对群体的推荐	针对群体的推荐	将用户、交互项、群组等作为顶点，根据群组内和群组之间关联交互关系构造超边	根据组交互从更高层级挖掘组模式，得出组偏好进行针对性推荐	文献［58-59］	主要使用超图神经网络方法从高层级挖掘组模式
序列推荐	时序推荐	每个时段构造交互超图，用户和推荐内容作为顶点，交互关系构造超边	基于多模态数据学习不同时刻的超图	文献［60-61］	主要利用超图神经网络方法和强化学习等手段对多个时刻的超图进行学习
	会话推荐	构造会话超图，用户和推荐内容作为顶点，交互关系构造超边		文献［63-64］
	时序会话推荐	时序和会话方式的综合		文献［66］
共性问题：推荐系统冷启动问题	推荐系统冷启动问题	都将用户和物品作为顶点，但是在构造超边上可以利用社会关系以及知识图谱等引入信息，也可以通过引入负例的方式构造符号超图更好地学习潜在关系	主要方法有：引入社会关系进行推荐，引入负例即不相似的项目，使用知识图谱添加信息	文献［67，70， 72］	使用多种方法添加信息后再进行超图学习提高训练效果

Survey on hypergraph application methods： issues， advances， and challenges

超图应用方法综述：问题、进展与挑战

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 89

Related Articles 15

Recommended Articles

Metrics

[1]	Tingjie TANG, Jiajin HUANG, Jin QIN. Session-based recommendation with graph auxiliary learning [J]. Journal of Computer Applications, 2024, 44(9): 2711-2718.
[2]	Yuanjiong LIU, Maozheng HE, Yibin HUANG, Cheng QIAN. Ship identification model based on ResNet50 and improved attention mechanism [J]. Journal of Computer Applications, 2024, 44(6): 1935-1941.
[3]	Kunting LU, Rongrong FEI, Xuande ZHANG. Remote sensing image pansharpening by convolutional neural network [J]. Journal of Computer Applications, 2023, 43(9): 2963-2969.
[4]	Junyu YANG, Yan DONG, Zhennan LONG, Xin YANG, Bin HAN. Rain detection algorithm based on event camera [J]. Journal of Computer Applications, 2023, 43(9): 2904-2909.
[5]	Yuan LIU, Yongquan DONG, Rui JIA, Haolin YANG. Hierarchical and phased attention network model for personalized course recommendation [J]. Journal of Computer Applications, 2023, 43(8): 2358-2363.
[6]	Yuanlong ZHAO, Yugang SHAN, Jie YUAN, Kangdi ZHAO. Object tracking based on instance segmentation and Pythagorean fuzzy decision-making [J]. Journal of Computer Applications, 2023, 43(6): 1930-1937.
[7]	Hao SUN, Jian CAO, Haisheng LI, Dianhui MAO. Session-based recommendation model based on enhanced capsule network [J]. Journal of Computer Applications, 2023, 43(4): 1043-1049.
[8]	Yue CHI, Zhengping LI, Chao XU, Bo FENG. Highlight removal algorithm for medical endoscopic images [J]. Journal of Computer Applications, 2023, 43(4): 1278-1283.
[9]	Xuanyu SUN, Yancui SHI. Session-based recommendation model by graph neural network fused with item influence [J]. Journal of Computer Applications, 2023, 43(12): 3689-3696.
[10]	Yu YANG, Weiwei DUAN. Spectral clustering based dynamic community discovery algorithm in social network [J]. Journal of Computer Applications, 2023, 43(10): 3129-3135.
[11]	GUO Keyou, LI Xue, YANG Min. Real‑time detection method of traffic information based on lightweight YOLOv4 [J]. Journal of Computer Applications, 2023, 43(1): 74-80.
[12]	Li’e WANG, Xiaocong LI, Hongyi LIU. News recommendation method with knowledge graph and differential privacy [J]. Journal of Computer Applications, 2022, 42(5): 1339-1346.
[13]	Jianmin ZHAO, Cheng ZHAO, Haiguang XIA. Cattle body size measurement method based on Kinect v4 [J]. Journal of Computer Applications, 2022, 42(5): 1598-1606.
[14]	Haifeng LI, Bifan ZHAO, Jinyi HOU, Huaichao WANG, Zhongcheng GUI. Automatic detection algorithm for underground target based on adaptive double threshold [J]. Journal of Computer Applications, 2022, 42(4): 1275-1283.
[15]	Junhua GU, Rui WANG, Ningning LI, Suqi ZHANG. Knowledge graph attention network fusing collaborative filtering information [J]. Journal of Computer Applications, 2022, 42(4): 1087-1092.