  Counting small cohesive subgraphs in a graph is a fundamental operation with
numerous applications in graph analysis. Previous studies on cohesive subgraph
counting are mainly based on the clique model, which aim to count the number of
$k$-cliques in a graph with a small $k$. However, the clique model often proves
too restrictive for practical use. To address this issue, we investigate a new
problem of counting cohesive subgraphs that adhere to the hereditary property.
Here the hereditary property means that if a graph $G$ has a property
$\mathcal{P}$, then any induced subgraph of $G$ also has a property
$\mathcal{P}$. To count these hereditary cohesive subgraphs (\hcss), we propose
a new listing-based framework called \hcslist, which employs a backtracking
enumeration procedure to count all \hcss. A notable limitation of \hcslist is
that it requires enumerating all \hcss, making it intractable for large and
dense graphs due to the exponential growth in the number of \hcss with respect
to graph size. To overcome this limitation, we propose a novel pivot-based
framework called \hcspivot, which can count most \hcss 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, while \hcslist is only
capable of counting a specific size of \hcs and obtaining a total count of
\hcss in a graph. We focus specifically on two \hcs: $s$-defective clique and
$s$-plex, with several non-trivial 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.
