Parallel K-clique counting on GPUs
Mohammad Almasri, Izzat El Hajj, Rakesh Nagi, Jinjun Xiong, Wen‐mei Hwu
Abstract
Counting k-cliques in a graph is an important problem in graph analysis with many applications such as community detection and graph partitioning. Counting k-cliques is typically done by traversing search trees starting at each vertex in the graph. Parallelizing k-clique counting has been well-studied on CPUs and many solutions exist. However, there are no performant solutions for k-clique counting on GPUs.
Topics & Concepts
Clique graphCliqueComputer scienceSimplex graphGraphClique problemTraverseCounting problemVertex (graph theory)Parallel computingCombinatoricsTheoretical computer scienceMathematicsAlgorithmGraph powerLine graphPathwidthGeodesyGeographyGraph Theory and AlgorithmsComplex Network Analysis TechniquesAdvanced Graph Neural Networks