Counting Cohesive Subgraphs with Hereditary Properties

The clique model has properties of hereditariness and cohesiveness. Here hereditary property means a subgraph of a clique is still a clique. Counting small cliques in a graph is a fundamental operation of numerous applications. However, the clique model are often too restrictive for practical use, leading to the focus on other relaxedcliques with properties of hereditariness and cohesiveness. To address this issue, we investigate a new problem of counting general hereditary cohesive subgraphs (HCS). All subgraphs with properties of hereditariness and cohesiveness can be called a kind of HCS. To count HCS, we propose a general framework called HCSPivot, which can be applied to count all kinds of HCS. HCSPivot can count most HCS in a combinatorial manner without explicitly listing them. Two additional noteworthy features of HCSPivot is its ability to (1) simultaneously count HCSs of any size and (2) simultaneously count HCSs for each vertex or each edge. The implementation of HCSPivot for clique counting is exactly the state-of-the-art clique counting algorithm PIVOTER [33] . We focus specifically on two HCS: 𝑠-defective clique and 𝑠-plex. We also propose several nontrivial pruning techniques to enhance the efficiency. We conduct extensive experiments on 8 large real-world graphs, and the results demonstrate the high efficiency and effectiveness of our solutions.