In this guide we discuss how to use the implementations of Danisch et al.'s k-clique counting algorithm.
The algorithm builds for each node in the current graph a subgraph induced by its neighbours. Then it recurses on the subgraphs and, at the last level, counts the k-cliques.
The k-clique benchmarks are built with the pipeline benching-variant. For more information see Pipeline Interface
Note that the verifier is the original plain C code by Danisch et al., whereas the actual kernels are optimized and slightly adapted C++ reimplementations. The verifiers work in Debug and Release mode.
The k-clique kernels require as input an undirected, unweighted graph and the size of the cliques that should be counted. Below is an excerpt of the available options. Call any of the kernels with
-h to see the full list of available options.
OPTIONS-t, --threadsspecify the number of threads used-n, --num-trialsnumber of iterations for the benchmark-p, --param set kernel specific parametersclique-size=, cs=the clique size (default: 8)-f, --file read graph from the specified file-g, --gen generate graph with the specified generator<scale> size of the generated graph = 2^scale
As you can see, there is one benchmark-specific parameter for k-clique counting.
The syntax to specify it is
The default graph representation is
CSRGraph, which can be specified by the
CGraph template parameter.
Be aware, that changing the graph representation also requires changing the subgraph builders (see below) and kernel code.
As the kernel currently relies on reordering the neighborhoods with swaps, currently the only supported graph for k-clique counting is
Compressible graphs don't support this operation at this time, and would thus require a strategy with an additional index vector for the ordering information.
To use a new representation, change in
k_clique_list/clique_counting.h a function pointer to use your desired graph representation:
// oldtemplate <class CGraph = CSRGraph>constexpr auto NP_kclisting= Parallelize::node<Builders::SubGraphBuilder<CGraph>, KcListing<CGraph>, CGraph>;// newtemplate <class CGraph = CUSTOM_GRAPH<NodeId>>constexpr auto NP_kclisting= Parallelize::node<CUSTOM_BUILDER<CGraph>,KcListing<CGraph>, CGraph>;
Using different preprocessing functions
Danisch's algorithm relies on a directed acyclic graph (DAG) to correctly count all k-cliques. The properties of the DAG (such as maximal out-degree and degree distribution) influence the performance of the algorithm. The default is a degeneracy order.
You can replace it by any scheme that ranks the vertices according to a total order. Take a look at the preprocessing functions of the
CliqueCountPipeline class in
k_clique_list/bench_helper.h for reference.
Using different parallelization schemes
Danisch's recursive counting kernel is parallelized in two ways:
- over the nodes
- over the edges
- mixed over the nodes and edges (Note: this is untested) To add your own parallelization scheme, implement it with the following interface:
template<typename Builder_T, typename Counter_T, typename CGraph = CSRGraph>unsigned long long CustomParallel(CGraph& g, const CLApp& cli);
For your own convenience, you can define a new function pointer for it in
k_clique_list/clique_counting.h or directly call the function.
Using different subgraph builders
Danisch's algorithm relies on induced subgraphs, the construction of which potentially heavily influences the runtime. There are two subgraph builder classes available in
SubGraphBuilder: Builds the direct induced subgraph. Only includes the out-edges
SubGraphBuilderWInverse: Builds the direct induced subgraph. Also includes the in-edges. Both classes are able to build the subgraphs induced by the neighborhood (out-edges) of a vertex or the common neighborhood of two vertices (ideally belonging to the same edge, though this is not strictly required). To add your own subgraph builder, its best to adhere to the interface defined by the existing classes.