A parallel algorithm for maximal cliques enumeration to improve hypergraph construction

Xiang Gao

doi:10.1016/j.jocs.2022.101905

2022-11-01

PRE

DOI：10.1016/j.jocs.2022.101905

原文链接

摘要

En 中文

Hypergraphs have become a powerful tool in many research fields that benefit from its high-order characteristics, such as network analysis, data mining and deep learning. The construction of hypergraphs plays an important role in subsequent tasks that are based on the hypergraph structure. The k-nearest neighbor method is widely used in hypergraph construction because of its low computational complexity and high data density. However, it only considers the relationship between the central vertex and the k nearest neighbors (or adjacent vertices) and does not consider if the other vertices are adjacent as well. Maximal clique enumeration algorithms can construct hyperedges where all vertices are adjacent, but the time cost is relatively large. In this paper, we introduce a CLIQUES-SEED algorithm, based on CLIQUES algorithm, which reduces the number of recursions required in the search process, and transforms the time complexity into space complexity, reducing the time complexity from O(3(n/3)) to O(n(2)/3) in the worst case. We implemented the algorithm on FPGA to realize the parallel algorithm. We also conducted experiments on the hypergraph neural networks using the CLIQUES-SEED algorithm to improve the hypergraphs construction in hypergraph neural networks. The maximum classification accuracy improvement rate was 6.7% compared with the k-nearest neighbor method. The results show that our method can quickly obtain more accurate hypergraphs using maximal clique enumeration algorithm.

Keyword:

Hypergraph construction

Maximal clique enumeration (MCE)

Hypergraph neural networks (HGNN)

k-nearest neighbor(kNN)

Field programmable gate array (FPGA)