1 Introduction

All graphs, considered in this paper, are looples, without multiple edges, non-oriented or partially oriented graphs. Graphs of the first type are called simple, and second-type graphs are called mixed.

Let G and H be simple graphs. For the pair (G, H), the subgraph matching problem, briefly called the SM problem, is to find all the subgraphs of G, each of which is isomorphic to H. The subgraph counting problem for (G, H) is to determine the quantity of these subgraphs. Sometimes, G is called a data graph and H is called a query graph.

The SM problem and its counting variant are fundamental with numerous applications in network science, including social network analysis and bioinformatics. In protein research, the physical contacts between proteins in the cell are represented as a network, and this protein-protein interaction network (PPIN) helps to develop new drugs. Large PPINs may contain millions of interactions, while they usually contain repeated local structures. Finding and counting these subgraphs is essential to compare different PPINs. In social network analysis, graph sizes could even reach trillion of edges, where a subgraph could be a group of users, sharing specific interests. Studying these groups improves the design of social networks and searching algorithms in them.

Triangles (or 3-cliques) and, more generally, k-cliques, i.e., sets of k pairwise adjacent vertices, are important types of subgraphs, arising in applications and being basic structures for matching/counting more complex fragments. For example, triangles counting is used in computing the local clustering coefficient, which is an important measure of the ability for nodes to form clusters [37].

All the algorithms for the SM problem can be classified by the execution model and the type of data graphs reading. Sequential algorithms run on a single processing machine only, but parallel algorithms can be executed on multiple simultaneously working processors. A full computational (or static) algorithm is an algorithm, where the data graph is explicitly given at once. In incremental algorithms, the data graph is accumulated by arriving its previously unknown simple parts, called batches. In fully dynamic algorithms, the vertex set is fixed and edges can be both added and deleted. In batch-dynamic algorithms, the set of vertices is not fixed, but batch updates can be both for insertions and deletions of edges.

There are several full computational sequential and parallel algorithms for matching/counting cliques [8, 12, 16, 19, 23, 24, 29,30,31, 33, 36]. For some other types of queries, like small-size subgraphs, paths, cycles and etc., efficient full computational sequential and parallel algorithms have also been developed, see [1, 3, 7, 9, 13, 22, 32, 35]. There are several efficient algorithms, see [4, 10, 11, 14, 15, 20, 27], for dynamically given data graphs and some types of queries.

In many applications of the SM problem, the sizes of data graphs are huge. Therefore, the use of parallel rather than sequential computations is the only way to obtain a result in reasonable time. Using the linear algebraic (briefly, LA) approach, i.e., the only matrix–vector instructions, is a natural choice to organize parallelism efficiently. Indeed, LA algorithms can be easily implemented, parallelized and have a small loss of performance under their scalability.

Only a few LA algorithms for the SM problem are known. For all the 4-vertex queries but the 4-clique, full computational LA algorithms have been developed in [18]. Exploiting the idea of color coding from [2], a full computational LA algorithm was proposed in the paper [6], when H is a tree. Apparently, according to ideas from [5], the approach from [6] can be extended to queries with tree-width at most 2.

The old paper [30] by J. Nešetřil and S. Poljak contains a reduction of the SM problem to its subproblem, where the only clique-queries are considered. This reduction is completely combinatorial. It has two drawbacks. The first of them is the absence of a bijection between solutions of the original and reduced SM problem. The second one is memory overflow, because of the simultaneous use of the data graph and its complement graph. In this paper, we present the first LA version of the Nešetřil-Poljak’s reduction, correcting these drawbacks.

Additionally, the paper [30] also presents a full computational algorithm for matching/counting k-cliques, which is almost completely combinatorial, except that it uses the fast matrix multiplication to match/count triangles in some graphs. In this article, we give a completely LA full computational version of their algorithm. Moreover, for matching/counting k-cliques, we present another full computational LA algorithm and an incremental LA algorithm, which have several handles for tuning their performance. For the k-clique counting problem, we provide results of computational experiments of our full computational solver for some large graphs and several k, which speed up results of several recent solvers for it.

2 Some definitions and notations

As usual, for sets A and B, by \(A\cap B,A\cup B,A-B,A\times B\), we denote their intersection, union, difference, Cartesian product, respectively. For any set A, the cardinality of A is denoted by |A|. For any natural n, the notation [n] means the set \(\{1,2,\ldots ,n\}\).

In this paper, we consider real-valued matrices only. For matrices \(\textbf{A}\) and \(\textbf{B}\) of the corresponding sizes, by

$$\begin{aligned} \textbf{A}+\textbf{B},\textbf{A}\cdot \textbf{B},\textbf{A}\otimes \textbf{B}, \textbf{A}\circ \textbf{B} \end{aligned}$$

we denote their sum, the (usual) product, Kronecker product, Hadamard product, respectively. If \(\textbf{A}\) and \(\textbf{B}\) are binary matrices of the corresponding sizes, then \(\textbf{A}\vee \textbf{B},\textbf{A}|\textbf{B},\textbf{A}\bullet \textbf{B}\) mean the sum, difference, and product over the logical semiring, i.e., we have

$$\begin{aligned} (\textbf{A}\vee \textbf{B})_{ij}=(\textbf{A})_{ij}\vee (\textbf{B})_{ij},(\textbf{A}|\textbf{B})_{ij}=(\textbf{A})_{ij}|(\textbf{B})_{ij},(\textbf{A}\bullet \textbf{B})_{ij}=\bigvee \limits _{k}((\textbf{A})_{ik}\wedge (\textbf{B})_{kj}). \end{aligned}$$

Let \(\textbf{A}\) be a matrix, subsets I and J be some sets of its rows and columns. By \(\textbf{A}^T\), we denote the transposed matrix of \(\textbf{A}\). The notation \(\textbf{A}[I][J]\) means the submatrix of \(\textbf{A}\) with rows from I and columns from J. If I coincides with the set of all the rows or J coincides with the set of all the columns, then we write \(I=*\) or \(J=*\), respectively. By \(\textbf{I}_n,\textbf{0}_n\), and \(\textbf{1}_n\), we denote the identity, all-zeroes matrices, and all-ones vector of the order n, respectively. By \(SUM(\textbf{A})\), we denote the sum of all the elements of \(\textbf{A}\). This sum for \(n\times m\) matrices \(\textbf{A}\) can be computed as the product \((\textbf{1}_n)^T\cdot \textbf{A}\cdot \textbf{1}_m\). For n-ary vector \(\textbf{v}\), by \(nnz(\textbf{v})\), we denote the set \(\{i:~\textbf{v}[i]\ne 0\}\).

For a (simple or mixed) graph G, by V(G) and E(G), we denote its vertex set \(\{v_1,\ldots ,v_n\}\) and edge set \(\{e_1,\ldots ,e_m\}\), respectively. By \(\textbf{A}_G\), we denote the adjacency matrix of G, i.e., the Boolean \(n\times n\) matrix, such that, for any \(i,j\in [n]\), its ij-th element is equal to one iff \((v_i,v_j)\in E(G)\). Assuming that G is simple, by \(\textbf{I}_G\), we denote its incidence matrix, i.e., the \(n\times m\) Boolean matrix, in which, for any \(i\in [n],j\in [m]\), the ij-th element is one iff \(v_i\) is incident to \(e_j\).

For \(v,u\in V(G)\), by \(d_G(v,u)\) we denote the distance between v and u. If G is connected, then diam(G) denotes the diameter of G, i.e. \(\max \limits _{v,u\in V(G)} d_G(v,u)\). For a vertex v of a oriented graph G, the left and right neighborhoods of v, denoted by \(N_l(v)\) and \(N_r(v)\), respectively, are defined as follows:

$$\begin{aligned} N_l(v)=\{u\in V(G):~(u,v)\in E(G)\},N_r(v)=\{u\in V(G):~(v,u)\in E(G)\}. \end{aligned}$$

For a vertex v of a simple graph G, the open and closed neighborhoods of v, denoted by N(v) and N[v], respectively, are defined as follows:

$$\begin{aligned} N(v)=\{u\in V(G):~\{v,u\}\in E(G)\}, N[v]=N(v)\cup \{v\}. \end{aligned}$$

Suppose that G is simple. By \({\overline{G}}\), we denote the complement graph of G. For any \(V'\subseteq V(G)\), by \(G{\setminus } V'\) we denote the resultant graph after deletion of all the vertices from \(V'\) with their incident edges.

By Aut(G) and Orbits(G), we denote the automorphism group of G and the set of all its orbits, respectively. Recall that a permutation \(\pi \) on V(G) is an automorphism of G iff

$$\begin{aligned} \forall \{v,u\}\in E(G) \longleftrightarrow \{\pi (v),\pi (u)\}\in E(G). \end{aligned}$$

The orbit, generated by a vertex \(v\in V(G)\), is defined as the set

$$\begin{aligned} \{u:~\exists \pi \in Aut(G),\pi (v)=u\}. \end{aligned}$$

The set orbits gives a disjunctive partition of V(G). By Sym(n) and \(Sym(n_1)\times \ldots \times Sym(n_l)\), we denote the symmetric group over n elements and the direct product of symmetric groups over \(n_1,\ldots ,n_l\) elements, respectively.

3 A linear algebraic version of the Nešetřil-Poljak’s reduction

For given a simple data graph G and a simple query graph H, it is proposed in [30] to deal with a special graph F, such that all the entries of H into G correspond to k-cliques of F, where \(k=|V(H)|\) and \(n=|V(G)|\). In other words, it reduces the general case to the case of clique-queries. More precisely, the graph F is defined as a graph on the vertex set \(V(G)\times V(H)\), having the edge set

$$\begin{aligned} \{\{(g_1,h_1), (g_2,h_2)\}:~\{h_1,h_2\}\in E({\overline{H}})\vee (\{g_1,g_2\}\in E(G)\wedge \{h_1,h_2\}\in E(H))\}. \end{aligned}$$

The set \(\{(g_1,h_1),\ldots ,(g_k,h_k)\}\) is a k-clique in F iff G has an entry of H on the vertex set \(\{g_1,\ldots ,g_k\}\) with the set of edges, formed by the rule

$$\begin{aligned} \{g_i,g_j\}~\text {is an edge iff}~\{h_i,h_j\}\in E(H). \end{aligned}$$

Unfortunately, the algorithm from [30] could match entries of H into G with multiplicities, i.e., distinct k-cliques of F may correspond to the same containment, due to automorphisms of H. Moreover, it involves simultaneous working with G and \({\overline{G}}\), at least one of them is not sparse. This section is aimed to present the first LA version of the Nešetřil-Poljak’s reduction, which completely avoids the mentioned multiplicities and avoids in part a possible memory overflow.

It is known that, for any graphs \(G_1\) and \(G_2\), possibly mixed, \(\textbf{A}_{G_1}\otimes \textbf{A}_{G_2}\) is the adjacency matrix of the graph

$$\begin{aligned} (V(G_1)\times V(G_2),\{((v_1,u_1),(v_2,u_2)):~(v_1,v_2)\in E(G_1), (u_1,u_2)\in E(G_2)\}). \end{aligned}$$

Hence, to obtain F, one may use the formula

$$\begin{aligned} \textbf{A}_F=\textbf{A}_G\otimes \textbf{A}_H+\textbf{A}_G\otimes \textbf{A}_{{{\overline{H}}}}+\textbf{A}_{{{\overline{G}}}}\otimes \textbf{A}_{{{\overline{H}}}}. \end{aligned}$$
(1)

Indeed, \(\textbf{A}_G\otimes \textbf{A}_H,\textbf{A}_G\otimes \textbf{A}_{{{\overline{H}}}},\textbf{A}_{{{\overline{G}}}}\otimes \textbf{A}_{{{\overline{H}}}}\) correspond to the conformity of edges of H to edges of G, non-edges of H to edges of G, non-edges of H to non-edges of G, respectively.

To avoid repetitions, according to automorphisms of H, i.e., to produce a bijection between all the k-cliques of F and all the entries of H into G, we will use special orientations for E(G) and for some parts of E(H) and \(E({\overline{H}})\). Firstly, we arbitrarily acyclically orient all the edges of G and \({\overline{G}}\), for example, by numbering vertices of G with numbers in [n] and orienting each edge from the smallest number to the biggest number. Further, we identify vertices and their numbers. The resultant graphs are denoted by \(\overrightarrow{G}\) and \(\overrightarrow{{\overline{G}}}\), respectively.

Next, we will work with the automorphism groups of H and some its induced subgraphs. There are several combinatorial algorithms for computing the automorphism group of a given graph, see, for example, the papers [26, 28, 34] and references therein. When H is small, one can simply split V(H) into subsets \(V_1,\ldots ,V_l\) of vertices of the same degrees \(d_1,\ldots ,d_l\) and put \(n_i=|V_i|\), for any \(i\in [l]\). Then,

$$\begin{aligned} Aut(H)\subseteq Sym(n_1)\times \ldots \times Sym(n_l), \end{aligned}$$

and we enumerate all the l-tuples \(\pi =(\pi _1,\ldots ,\pi _l)\), where \(\pi _i\) is a permutation of \(V_i\), and check whether \(\pi \) is an automorphism of H by verifying whether

$$\begin{aligned} \forall \{x,y\}\in E(H) \longleftrightarrow \{\pi (x),\pi (y)\}\in E(H). \end{aligned}$$

To find Orbits(H), we enumerate all the vertices of H and find sets of vertices, to which vertices of H are transferred by permutations from Aut(H). Finally, we apply the following combinatorial algorithm:

figure a

The proposed algorithm can be explained as follows. It supports the invariant that Aut is the automorphism group of \(H\setminus S\) and Orbits is the set of its orbits. Hence, vertices from any orbit of Aut have equal rights between each other. Therefore, in each entry of H into G, any orbit’s element can be identified with the minimum vertex among G’s vertices, corresponding to elements of the orbit. The orientation of edges from x arranges x to be a minimum vertex for elements from the x’s orbit. Algorithm 1 is finished, when Aut is constituted by the trivial permutation only.

The resultant mixed graphs after orientation above are denoted by \(\overrightarrow{H}\) and \(\overrightarrow{{\overline{H}}}\), respectively. Hence, the formula (1) can be rewritten as follows

$$\begin{aligned} \textbf{A}_{\overrightarrow{F}}=\textbf{A}_{\overrightarrow{G}}\otimes \textbf{A}_{\overrightarrow{H}}+\textbf{A}_{\overrightarrow{G}}\otimes \textbf{A}_{\overrightarrow{{{\overline{H}}}}}+\textbf{A}_{\overrightarrow{{{\overline{G}}}}}\otimes \textbf{A}_{\overrightarrow{{{\overline{H}}}}}. \end{aligned}$$
(2)

The adjacency matrices \(\textbf{A}_{\overrightarrow{G}}\) and \(\textbf{A}_{\overrightarrow{{{\overline{G}}}}}\) could be too dense to apply the multiplications with them. To overcome this phenomena, one may use some filtering technique for edges and non-edges of G and possible sequential splitting the resultant graphs into batches for incremental keeping \(\overrightarrow{F}\) and using an incremental algorithm for the k-clique matching problem.

Suppose that G and H are both connected. Let us note that if \(\hbox {v,u}\in E({\overline{G}}) \)corresponds to \(\{x,y\}\in E({\overline{H}})\) of some copy of H in G, then \(d_H(v,u)\le d_G(x,y)\). Hence, we do not need those anti-edges \(\{v,u\}\) of G that \(d_G(v,u)>diam(H)\). This idea can be implemented and improved as follows. The distances in G and H can be found, using a LA form of Breadth First Search, see, for example, page 33 from [21]. For any \(i\in [diam(H)]\), the v-th column of \(\textbf{D}^i_{G}\), where \(v\in V(G)\), keeps the mask of \(\{u\in V(G):~d_{G}(v,u)=i\}\), and the x-th column of \(\textbf{D}^i_H\), where \(x\in V(H)\), keeps the mask of \(\{y\in V(H):~d_H(x,y)=i\}\). By \(\textbf{SD}^{i}_{G}\), we denote the matrix \(\bigvee \limits _{j=1}^{i}\textbf{D}^{j}_{G}\).

More precisely, we use the following algorithm:

figure b

For any \(x\in V(H)\), by V(x), we denote the set

$$\begin{aligned}{} & {} \{v\in V(G):~\forall i\in [diam(H)]~|\{y:~d_H(x,y)=i\}|\le |\{u:~d_{G}(v,u)\le i\}|\}\\{} & {} =\{v\in V(G):~\forall i\in [diam(H)]~SUM(\textbf{D}^i_{H}[*][x])\le SUM(\textbf{SD}^i_{G}[*][v])\}. \end{aligned}$$

Therefore, for any \(x\in V(H)\), the only vertices from V(x) can correspond to x in copies of H in G.

For any edge or anti-edge e of H, the matrix \(\textbf{A}_e\) denotes the adjacency matrix of the graph on V(H) with the unique edge e. Then, the formula (2) can be rewritten as

$$\begin{aligned} \begin{aligned} \textbf{A}_{\overrightarrow{F}}=\bigvee \limits _{e=(x,y)\in E(\overrightarrow{H})}(\textbf{A}_{\overrightarrow{G}}[V_x\cup V_y][V_x\cup V_y]\otimes \textbf{A}_{e}){} & {} \\ +\bigvee \limits _{e=(x,y)\in E(\overrightarrow{{\overline{H}}})}(\textbf{SD}^{d_H(x,y)}_{\overrightarrow{G}}[V_x\cup V_y][V_x\cup V_y]\otimes \textbf{A}_{e}), \end{aligned} \end{aligned}$$
(3)

where \(\textbf{SD}^{i}_{\overrightarrow{G}}[v][u]=\textbf{SD}^{i}_{G}[v][u]\), if \(v<u\), otherwise, \(\textbf{SD}^{i}_{\overrightarrow{G}}[v][u]=0\).

The graph \(\overrightarrow{F}\) is an acyclically completely oriented graph, in which all the oriented k-cliques bijectively correspond to all the entries of H into G. To reduce the amount of used memory, edges and non-edges of G can be split into parts to obtain, according to (3), the graph \(\overrightarrow{F}\) incrementally. Full computational and incremental LA algorithms for k-clique matching and counting will be presented in the next sections.

4 Full computational LA algorithms for the k-clique matching and counting problems

4.1 The Nešetřil-Poljak’s algorithm for k-clique matching/counting and its LA version

The paper [30] also presents a combinatorial full computational algorithm for matching/counting k-cliques. Its idea is to use a recursion and matching/counting triangles in auxiliary graphs. For the simplicity, let us assume that \(k=3l\). For a given simple graph G, its auxiliary graph \(G'\) is defined as

$$\begin{aligned} V(G')=\{X\subseteq V(G):~X~\text {is a}~l\text {-clique in}~G\}, \end{aligned}$$
$$\begin{aligned} E(G')=\{\{X,Y\}:~X\cup Y~\text {is a}~2l\text {-clique in}~G\}. \end{aligned}$$

Clearly that, to match/count 3l-cliques in G, one only needs to match/count triangles in \(G'\). This idea via the fast matrix multiplication was used for designing full computational [12] and fully dynamic [10] algorithms. Unfortunately, these algorithms do not explain how to construct and keep the graph \(G'\). In this subsection, we overcome this difficulty and show how the algorithm from [30] can be completely implemented as a LA algorithm. It uses the following classical LA algorithm for matching/counting triangles:

figure c

Indeed, ones of \((\textbf{A}_{\overrightarrow{G}})^2\) correspond to end-vertices of oriented 2-paths, i.e., paths with 2 edges, in \(\overrightarrow{G}\). Ones of \((\textbf{A}_{\overrightarrow{G}})^2\circ \textbf{A}_{\overrightarrow{G}}\) mean that edges connect end-vertices of oriented 2-paths, meaning that triangles are formed. Hence, \(SUM(\textbf{A}^*)\) is the number of triangles. Algorithm 3 can also be used for matching triangles. To this end, for any \(v,v''\in V(G)\), such that \(\textbf{A}^*[v][v'']\ne 0\), we find

$$\begin{aligned} N_r(v)\cap N_l(v'')=nnz(\textbf{A}_{\overrightarrow{G}}[v][*]\circ (\textbf{A}_{\overrightarrow{G}}[*][v''])^T). \end{aligned}$$

In the following algorithm, \(\textbf{Inc}_s\) is the incidence matrix, which rows correspond to vertices of G and columns are masks of all the ordered s-cliques of G.

figure d

The matrices \(\textbf{A}_{\overrightarrow{G}}\cdot \textbf{Inc}_{3p}\) and \(\textbf{A}_{\overrightarrow{G}} \cdot \textbf{Inc}_{3p+1}\) show the sizes of vertex right neighborhoods in all the ordered 3p- and \(3p+1\)-cliques of G. Rows and columns of \((\textbf{Inc}_p)^T\cdot \textbf{A}_G \cdot \textbf{Inc}_p\) are all the p-cliques of G, and all its elements are the quantities of edges between pairs of p-cliques. These properties certify the correctness of Algorithm 4.

Even for counting k-cliques, Algorithm 4 may consume a large amount of memory, as it uses the incidence matrix of ordered \(\lfloor \frac{k}{3}\rfloor \)-cliques to vertices. It may be impractical even for relatively small k. A more efficient full computational LA algorithm will be described in the next subsection.

4.2 Another LA full computational k-clique matching/counting algorithm

Our algorithm can be briefly explained as follows: firstly, possibly, use a preprocessing step, secondly, somehow acyclically orient the remaining subgraph, finally, use descending to 3- or 4-cliques by right neighborhoods with subsequent matching/counting for k-cliques of the original graph. For deleting redundant vertices and edges, i.e., as a preprocessing step, we propose the following LA procedures:

figure e

The vector \(\textbf{v}\) keeps degrees of all the vertices of G. Any its vertex of degree at most \(k-2\) cannot belong to any k-clique of G. This certifies the correctness of Algorithm 5.

figure f

For any \(x\in V(G)\), the x-th row of \(\textbf{A}'\) keeps \(|N(x)\cap N(y)|\), for any \(y\in N(x)\). Therefore, edges \(\{x,y\}\) of G with \(\textbf{A}'[x][y]\le k-3\) cannot belong to any its k-clique, and they can be removed. After that vertices of G of degree at most \(k-2\) can also be deleted, as they cannot belong to any k-clique. This explains Algorithm 6.

Our full computational LA algorithm for matching/counting k-cliques with descending to 3-cliques is presented in the following pseudocode below:

figure g

In the last loop of Algorithm 7, instead of matching/counting triangles, one may use the following LA full computational algorithms for matching/counting 4-cliques:

figure h
figure i

The correctness of Algorithm 8 is obvious. Let us certify the correctness of Algorithm 9. For any \(v\in V(G)\), \(SUM(\textbf{A}^*_v)\) is the number of triangles with the \(\min \)- and \(\max \)-vertices from \(N_r(v)\). Hence, to compute the number of 4-cliques in G with the \(\min \)-vertex v, it is sufficient to substract

$$\begin{aligned} \sum \limits _{\{v',v''':~\textbf{A}^*_v[v'][v''']\ne 0\}}|N_r(v')\cap N_l(v''')-N_r(v)| \end{aligned}$$

from \(SUM(\textbf{A}^*_v)\). Therefore, the number of 4-cliques equals

$$\begin{aligned} \sum \limits _{v\in V(G)} (SUM(\textbf{A}^*_v)-SUM(\textbf{A}^{**}_v)). \end{aligned}$$

To match 4-cliques, we find

$$\begin{aligned} N_r(v)\cap N_r(v')\cap N_l(v''')=nnz(\textbf{A}^{'}_v[v'][*]\circ (\textbf{A}^{'}_v[*][v'''])^T), \end{aligned}$$

for any \(v,v',v'''\in V(G)\), such that \(\textbf{A}'_v[v'][v''']\ne 0\).

5 An incremental LA algorithm for the k-clique matching/counting problem

We assume that edge-disjoint batches \(G_1,\ldots ,G_T\) of G follow one by one, such that \(V(G)=\bigcup \limits _{i=1}^{T} V(G_i)\) and \(E(G)=\bigsqcup \limits _{i=1}^{T} E(G_i)\). For any \(i\in [T]\), accumulated \(G^{(i-1)}=\bigcup \limits _{j=1}^{i-1} G_j\), where \(G_0=(\emptyset ,\emptyset )\), and given \(G_i\), the incremental k-clique matching/counting problem asks to match/count all the k-cliques Q of \(G^{(i)}\) with \(Q\cap E(G_i)\ne \emptyset \).

Full computational and incremental algorithms for the k-clique matching/counting problem can be useful for each other. For example, after applying the removing procedure by Algorithm 5 or 6 to G, the resultant graph can be split into batches and an incremental algorithm can be used. In incremental algorithms, for working with \(G_1\), when it is large enough, one may use a full computational algorithm.

The main idea of our algorithm is to split \(E(G_i)\) into classes, such that any two edges from the same class cannot belong to a common k-clique of \(G^{(i)}\), to consider the classes one by one, and to match/count \((k-2)\)-cliques in parallel in the subgraphs, induced by common neighbors of x and y in \(G^{(i)}\), for any \(\{x,y\}\in E(G_i)\).

The next procedure, for a given simple graph \(G'=(V',E'),V'=\{1,2,\ldots ,n'\}\), gives an edge-disjoint partition \(E'=\bigsqcup \limits _{i=1}^{s'} Cl'[i]\) into classes with a heuristic minimization of \(s'\). It uses the set of arrays \(\{Forb'[v']: v'\in V'\}\), where, for any \(v'\in V'\), we have

$$\begin{aligned} Forb'[v']=\{i':~ \exists \{a',b'\}\in Cl'[i'], N[v']\cap \{a',b'\}\ne \emptyset \}. \end{aligned}$$
figure j

At each step of Algorithm 10, the minimum number class is searched, such that \(e'\) can be put in it without forming triangles by edges from the same class, which is guaranteed by updating \(Forb'[w']\) with \(w'\in N[v']\cap N[u']\). Using the intersection of \(N[v']\) and \(N[u']\) instead of their union decreases the quantity of used edge classes. This certifies the correctness of Algorithm 10.

Our incremental k-clique matching/counting LA algorithm is presented in the following pseudocode:

figure k

The induced subgraphs, appearing in Algorithm 11, can be obtained by masking adjacency matrices of their supergraphs. If \(i=1\), then the only matching/counting phase of Algorithm 7 can be used without splitting the edge set into classes. Vertex and edge deletions by Algorithms 5 and 6 can also be used for \(G'_i\) after its definition and/or in the first for-cycle.

6 Computational experiments

In this section, we provide results of computational experiments for four known datasets, the graphs \(com-dblp,com-orkut,com-friendster,com-lj\), see [25], whose quantities of vertices and edges are shown in Table 1 below:

Table 1 Quantities of vertices and edges
Full size table

We considered the only counting variant of the k-clique matching problem and full computational algorithms for it, based on Algorithm 7, with three handles for tuning. The first of them is a choice between the absence of any graph reduction and the use of Algorithm 5 or 6. The second one is a choice between downing to 3-cliques and using Algorithm 3 and downing to 4-cliques and using Algorithm 8 or 9. The third one is a choice between the following three orientations:

  • from smaller end-vertices to bigger end-vertices, called the id orientation,

  • from smaller-degree end-vertices to bigger-degree end-vertices, if these degrees are distinct, otherwise, the id orientation between these vertices is used, called the degree orientation,

  • the \(\epsilon \)-Goodrich-Pszona orientation, for \(\epsilon \in \{0.1,0.2,0.5,1,2,5,10\}\).

The \(\epsilon \)-Goodrich-Pszona orientation is a generalization of the degree orientation, see [17] or the pseudocode below:

figure l

The \(\epsilon \)-Goodrich-Pszona orientation guarantees that the right neighborhood of any vertex is relatively small, see, for example, [33], for more details.

For any of these 72 possibilities, generated by concrete choices in the handles, and considered pairs (dataset, k), we chose the best computation time. Our hardware was one machine CPU: Kunpeng 920 4826 2.6GHz*2 (128 physical cores, one thread per core), 950 GiB of main memory, the used API is GraphBLAS.

We compared our solution with the methods, called Arb-count [33], BinaryJoin [29], kClist [8], Pivoter [19], WCO [23]. For now, Arb-count seems to be a state-of-the-art algorithm for k-clique counting. Unfortunately, we did not find open code for BinaryJoin and were not able to execute Pivoter and WCO on our cluster in the parallel regime of computations. The method Arb-count has not been launched on our machine.

So, we could provide experiments on our machine only with kClist and choosing the best option from the edge and vertex parallelisms. For the remaining approaches, we took runtimes from Table 2 of [33], which have been obtained on a machine with 30 two-way hyper-threading cores with 3.8GHz Intel Xeon Scalable (Cascade Lake) processors and 240 GiB of main memory. To make the conditions of experiments more comparable, we divided these times by \(\frac{128*2.6}{30*3.8}\approx 2.919\). The results are shown in Table 2 below:

Table 2 Best runtimes in seconds
Full size table

For kClist, we provided the computation times in integer number of seconds. The first- and second-best times are emphasized with the bold and italic environments, respectively. In the cases, where it is not possible to select the best and second-best times, we do not use any emphasizing. The footnote \(^{*}\) means that we use the id orientation, Algorithm 5, descending to 4-cliques by Algorithms 7 and 8. The footnote \(^{**(\epsilon )}\) refers to the use of the \(\epsilon \)-Goodrich-Pszona orientation, Algorithm 5, descending to 4-cliques by Algorithms 7 and 8.

For many pairs (dataset, k), Arb-count showed the best results. For \(com-dblp\) and \(6\le k\le 11\), our approach gave 2.06-\(-\)24.6-speedups over the second-best solution. For \(com-friendster\) and \(k\in \{10,11\}\), our approach gave 1.15- and 4.22-speedups over the second-best solution. For \(com-lj\) and \(k\in \{6,7\}\), our approach gave 1.01- and 2.01-speedups over the second-best solution.

To clarify the situation for \(com-dblp\) and large values of k, we conducted an additional experiment. The experiment showed the following results, where we everywhere used the conditions of \(^{**(5)}\), see Table 3:

Table 3 Runtimes for \((com-dblp,k)\) and \(12\le k\le 20\) in seconds
Full size table

Our solver showed good results for \(12\le k\le 20\).

7 Conclusions and future work

In this paper, we considered the subgraph matching problem, which is, for given simple graphs G and H, to find all the entries of H in G. Linear algebraic (LA, for short) algorithms are well suited for parallelisation of computational process. Prior to this paper, LA algorithms for the subgraph matching problem were known only for a few types of H. The first LA algorithm for this problem and general H was presented in this paper. It uses a LA reduction to the case, when H is a clique. Specifically for k-clique matching/counting, we presented a LA algorithm with several optimization techniques. Conducted computational experiments for its counting variant, several large graphs, and values of k showed the viability of our approaches. Developing new LA algorithms for the subgraph matching problem and improving the existing ones is a challenging research problem for possible future research.