Maximal clique searching algorithm for hypergraphs

doi:10.11772/j.issn.1001-9081.2022091334

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (8): 2319-2324.DOI: 10.11772/j.issn.1001-9081.2022091334

• The 19th International Conference on Web Information Systems and Applications (WISA 2022) • Next Articles

Maximal clique searching algorithm for hypergraphs

Lantian XU¹, Ronghua LI¹, Yongheng DAI², Guoren WANG¹

^1.School of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，China
^2.Diankeyun （Beijing） Technology Company Limited，Beijing 100041，China

Received:2022-09-06 Revised:2022-09-23 Accepted:2022-10-08 Online:2022-11-02 Published:2023-08-10
Contact: Ronghua LI
About author:XU Lantian， born in 1997， M. S. candidate. His research interests include graph data mining.
DAI Yongheng， born in 1983， Ph. D.， engineer. His research interests include domain modeling， expert knowledge structuring， integrated machine learning.
WANG Guoren， born in 1966， Ph. D.， professor. His research interests include data mining.
Supported by:
National Natural Science Foundation of China(62072034);National Key Research and Development Program of China(2021YFB3301301)

面向超图的极大团搜索算法

徐兰天¹, 李荣华¹, 戴永恒², 王国仁¹

^1.北京理工大学计算机学院，北京 100081
^2.电科云（北京）科技有限公司，北京 100041

通讯作者: 李荣华
作者简介:徐兰天（1997—），男，河北唐山人，硕士研究生，主要研究方向：图数据挖掘
戴永恒（1983—），男，北京人，工程师，博士，主要研究方向：领域建模、专家知识结构化、融合的机器学习
王国仁（1966—），男，北京人，教授，博士，CCF会员，主要研究方向：数据挖掘。
基金资助:
国家自然科学基金资助项目(62072034);国家重点研发计划课题(2021YFB3301301)

Abstract

Abstract:

Most of entity relationships in the real world cannot be represented by simple binary relations， and hypergraph can represent the n-ary relations among entities well. Therefore， definitions of hypergraph clique and maximal clique were proposed， and the exact algorithm and approximation algorithm for searching hypergraph maximal clique were given. First， the reason why the existing maximal clique searching algorithms on ordinary graphs cannot be applied to hypergraphs directly was analyzed. Then， based on the characteristics of hypergraph and the definition of maximal clique， a novel data structure for preserving the adjacency relations among hyperpoints was proposed， and an accurate maximal clique searching algorithm on hypergraph was proposed. As the running of the exact algorithm is slow， the pruning idea of pivots was combined with， the number of recursive layers was reduced， and an approximation maximal clique searching algorithm on hypergraph was proposed. Experimental results on multiple real hypergraph datasets show that under the premise finding most maximal cliques， the proposed approximation algorithm improves the search speed. When the number of test hypergraph cliques on 3-uniform hypergraph is 22， the acceleration ratio reaches over 1 000.

Key words: hypergraph, maximal clique, set enumeration, approximation algorithm, pivot

摘要：

现实世界中的实体关系大多不能用简单的二元关系来表示，而超图能很好地表示实体间的多元关系。因此，提出超图团和极大团的定义，并给出了搜索超图极大团的精确算法和近似算法。首先，分析了现有的普通图上的极大团搜索算法无法直接应用到超图上的原因。然后，基于超图的特性和极大团的定义，提出了一种新颖的保存超点间邻接关系的数据结构，并提出了一种超图上的精确极大团搜索算法。由于精确算法的速度较慢，因此结合支撑点（pivot）的剪枝思想，削减递归层数，提出了一种超图上的近似极大团搜索算法。在多个真实超图数据集上的实验结果显示，所提近似算法在找到大多数极大团的前提下，提高了搜索速度，当在3-uniform超图上，测试超图团的点数为22时，加速比达到了1 000以上。

关键词: 超图, 极大团, 集合枚举, 近似算法, 支撑点

CLC Number:

TP311.1

Lantian XU, Ronghua LI, Yongheng DAI, Guoren WANG. Maximal clique searching algorithm for hypergraphs[J]. Journal of Computer Applications, 2023, 43(8): 2319-2324.

徐兰天, 李荣华, 戴永恒, 王国仁. 面向超图的极大团搜索算法[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2319-2324.

Figures/Tables 8

Fig. 1 Four-hclique

Fig. 2 Adjacency relationships in hgroup

Fig. 3 R，P，X sets of BKH algorithm

Fig. 4 d-edge to r-edges

Tab. 1 Comparison of running time of hypergraph maximal clique searching algorithms

K	r	edge	搜索K，r超图团的时间/s		加速比
K	r	edge	BKH	BKHpivot	加速比
12	3	220	0.07	0.01	7.00
12	4	495	0.14	0.07	2.00
14	3	364	0.26	0.03	8.67
14	4	1 001	0.49	0.21	2.33
16	3	560	1.03	0.05	20.60
16	4	1 820	2.88	0.31	9.29
18	3	816	5.11	0.04	127.75
18	4	3 060	14.49	1.07	13.54
20	3	1 140	25.73	0.04	643.25
20	4	4 845	87.75	1.75	50.14
22	3	1 540	123.08	0.09	1 367.56
22	4	7 315	438.73	6.79	64.61

Tab. 2 Basic information about dataset

数据集	$\| E \| = m$	$\| V \| = n$
contact-primary-school	106 879	242
contact-high-school	172 035	327
email-Eu	234 760	1 005

Tab. 2 Basic information about dataset

数据集	$\| E \| = m$	$\| V \| = n$
contact-primary-school	106 879	242
contact-high-school	172 035	327
email-Eu	234 760	1 005

Tab. 3 Comparison of search results of hypergraph maximal clique

r	数据集	edge	BKH			BKHpivot
r	数据集	edge	num	time/s	memory/KB	num	time/s	memory/KB
3	contact-primary-school	5 139	3 469	0.040	4 804	3 085	0.030	4 808
	contact-high-school	2 370	1 633	0.025	4 500	1 483	0.020	4 352
	email-Eu	160 605	6 330	42 905.000	13 248	3 806	1.488	13 304
4	contact-primary-school	381	345	0.008	4 072	340	0.008	4 028
	contact-high-school	238	210	0.006	3 788	205	0.007	4 072
	email-Eu	714 535	2 750	226 458.000	61 576	2 392	16.899	61 484

Fig. 5 Number of hypergraph maximal cliques for two algorithms

References 16

1	HAO F， LI S， MIN G Y， et al. An efficient approach to generating location-sensitive recommendations in ad-hoc social network environments［J］. IEEE Transactions on Services Computing， 2015， 8（3）： 520-533. 10.1109/tsc.2015.2401833
2	SHANG H L， TAO Y D， GAO Y， et al. An improved invariant for matching molecular graphs based on VF2 algorithm［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2015， 45（1）： 122-128. 10.1109/tsmc.2014.2327058
3	LIU J Z， LEE Y T. Graph-based method for face identification from a single 2D line drawing［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2001， 23（10）： 1106-1119. 10.1109/34.954601
4	LI R H， GAO S， QIN L， et al. Ordering heuristics for k-clique listing［J］. Proceedings of the VLDB Endowment， 2020， 13（12）： 2536-2548. 10.14778/3407790.3407843
5	BRON C， KERBOSCH J. Algorithm 457： finding all cliques of an undirected graph［J］. Communications of the ACM， 1973， 16（9）： 575-577. 10.1145/362342.362367
6	TOMITA E， TANAKA A， TAKAHASHI H. The worst-case time complexity for generating all maximal cliques and computational experiments［J］. Theoretical Computer Science， 2006， 363（1）： 28-42. 10.1016/j.tcs.2006.06.015
7	MITZENMACHER M， PACHOCKI J， PENG R， et al. Scalable large near-clique detection in large-scale networks via sampling［C］// Proceedings of the 21st ACM Special Interest Group on Knowledge Discovery and Data Mining. New York： ACM， 2015： 815-824. 10.1145/2783258.2783385
8	WU Q H， HAO J K， GLOVER F. Multi-neighborhood tabu search for the maximum weight clique problem［J］. Annals of Operations Research， 2012， 196（1）： 611-634. 10.1007/s10479-012-1124-3
9	CHIBA N， NISHIZEKI T. Arboricity and subgraph listing algorithms［J］. SIAM Journal on Computing， 1985， 14（1）： 210-223. 10.1137/0214017
10	MAKINO K， UNO T. New algorithms for enumerating all maximal cliques［C］// Proceedings of the 2004 Scandinavian Workshop on Algorithm Theory， LNCS 3111. Berlin： Springer， 2004： 260-272.
11	ÖSTERGÅRD P R J. A fast algorithm for the maximum clique problem［J］. Discrete Applied Mathematics， 2002， 120（1/2/3）： 197-207. 10.1016/s0166-218x(01)00290-6
12	DANISCH M， BALALAU O， SOZIO M. Listing k-cliques in sparse real-world graphs［C］// Proceedings of the 2018 World Wide Web Conference. Republic and Canton of Geneva： International World Wide Web Conferences Steering Committee， 2018： 589-598. 10.1145/3178876.3186125
13	JAIN S， SESHADHRI C. A fast and provable method for estimating clique counts using Turán’s theorem［C］// Proceedings of the 26th International Conference on World Wide Web. Republic and Canton of Geneva： International World Wide Web Conferences Steering Committee， 2017： 441-449. 10.1145/3038912.3052636
14	EDEN T， RON D， SESHADHRI C. On approximating the number of k-cliques in sublinear time［J］. SIAM Journal on Computing， 2020， 49（4）： 747-771. 10.1137/18m1176701
15	LIU E L L， WANG J. The maximum number of cliques in hypergraphs without large matchings［J］. The Electronic Journal of Combinatorics， 2020， 27（4）： No.P4.14. 10.37236/9604
16	BENSON A R， ABEBE R， SCHAUB M T， et al. Simplicial closure and higher-order link prediction［J］. Proceedings of the National Academy of Sciences of the United States of America， 2018， 115（48）： E11221-E11230. 10.1073/pnas.1800683115

[1]	Xuanfeng LI, Shengcai LIU, Ke TANG. Novel genetic algorithm for solving chance-constrained multiple-choice Knapsack problems [J]. Journal of Computer Applications, 2024, 44(5): 1378-1385.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	Yang WANG, Shijie JIANG, Yucong CAO, Chuanwen LI. Parallel pivoted subgraph matching with multiple coding trees on GPU [J]. Journal of Computer Applications, 2022, 42(1): 132-139.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	XU Qian, CHEN Hongchang, WU Zheng, HUANG Ruiyang. User identification method across social networks based on weighted hypergraph [J]. Journal of Computer Applications, 2017, 37(12): 3435-3441.
[13]	LI Chunying, TANG Yong, TANG Zhikang, HUANG Yonghang, YUAN Chengzhe, ZHAO Jiandong. Community detection model in large scale academic social networks [J]. Journal of Computer Applications, 2015, 35(9): 2565-2568.
[14]	GAO Wenyu, LI Hua. Approximation algorithm of cluster vertex deletion [J]. Journal of Computer Applications, 2015, 35(8): 2137-2139.
[15]	. Mapping from XML schema to relation mode based on pivot node [J]. Journal of Computer Applications, 2009, 29(08): 2303-2305.

Maximal clique searching algorithm for hypergraphs

面向超图的极大团搜索算法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 16

Related Articles 15

Recommended Articles

Metrics