A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs

Analyzing the occurrences of a small pattern graph $H$ in a large input graph $G$ is a central problem in computer science. The theoretical study has led to a rich and immensely deep theory [39, 20, 30, 24, 40, 2, 23, 45, 51, 17, 16]. The applications of graph pattern counts occur across numerous scientific areas, including logic, biology, statistical physics, database theory, social sciences, machine learning, and network science [34, 19, 22, 18, 27, 13, 29, 42, 59, 45, 25, 44]. (Refer to the tutorial [53] for more details on applications.)

A common formalism used for graph pattern counting is homomorphism counting. The pattern graph is denoted $H=(V(H),E(H))$ and is assumed to have constant size. The input graph is denoted $G=(V(G),E(G))$. Both graphs are simple and do not contain self-loops. An $H$-homomorphism is a map $f:V(H)\to V(G)$ that preserves edges. Formally, $\forall(u,v)\in E(H)$, $(f(u),f(v))\in E(G)$. Let $\mathrm{Hom}_{H}(G)$ denote the number of distinct $H$-homomorphisms in $G$.

Given the importance of graph homomorphism counts, the study of efficient algorithms for this problem is a subfield in itself [35, 3, 18, 27, 26, 24, 13, 23, 14, 51]. The simplest version of this problem is when $H$ is a triangle, itself a problem that attracts much attention. Let $n=|V(G)|$ and $k=|V(H)|$. Computing $\mathrm{Hom}_{H}(G)$ is $\#W[1]$-hard when parameterized by $k$ (even when $H$ is a $k$-clique), so we do not expect $n^{o(k)}$ algorithms for general $H$ [24]. Much of the algorithmic study of homomorphism counting is in understanding conditions on $H$ and $G$ when the trivial $n^{k}$ running time bound can be beaten.

Our work is inspired by the challenges of modern applications of homomorphism counting, especially in network science. Typically, $n$ is extremely large, and only near-linear time ($n\cdot\mathrm{poly}(\log{n})$) algorithms are feasible. Inspired by a long history and recent theory on this topic, we focus on bounded degeneracy input graphs (we say bounded degeneracy graphs to refer to graphs belonging to classes of graphs with bounded degeneracy). This includes all non-trivial minor-closed graph families, such as planar graphs, bounded genus graphs, and bounded tree-width graphs. Many practical algorithms for large-scale graph pattern counting use algorithms for bounded degeneracy graphs [2, 38, 45, 43, 37, 44]. Real-world graphs typically have a small degeneracy, comparable to their average degree ([32, 37, 55, 5, 9], also Table 2 in [5]).

Secondly, many modern applications for homomorphism counting require more fine-grained statistics than just the global count $\mathrm{Hom}_{H}(G)$. The aim is to find, for every vertex $v$ of $G$, the number of homomorphisms that $v$ participates in. Seminal work in network analysis for bioinformatics plots the distributions of these per-vertex counts to compare graphs [36, 46]. Orbit counts can be used to generate features for vertices, sometimes called the graphlet kernel [54]. In the past few years, there have been many applications of these per-vertex counts [10, 59, 52, 57, 4, 58, 50, 60, 61].

Algorithms for this problem require considering the “roles” that $v$ could play in a homomorphism. For example, in a $7$-path (a path of length $6$) there are $4$ different roles: a vertex $v$ could be in the middle, could be at the end, or at two other positions. These roles are colored in Fig. 1. The roles are called orbits (defined in the Section 3), and the problem of $H$-homomorphism orbit counting is as follows: for every orbit $\psi$ in $H$ and every vertex $v$ in $G$, output the number of homomorphisms of $H$ where $v$ participates in the orbit $\psi$. This is the main question addressed by our work:

What are the pattern graphs $H$ for which the $H$-homomorphism orbit counting problem is computable in near-linear time (when $G$ has bounded degeneracy)?

Recent work of Bressan followed by Bera-Pashanasangi-Seshadhri introduced the question of homomorphism counting for bounded degeneracy graphs, from a fine-grained complexity perspective [14, 8]. A dichotomy theorem for near-linear time counting of $\mathrm{Hom}_{H}(G)$ was provided in subsequent work [6]. Assuming fine-grained complexity conjectures, $\mathrm{Hom}_{H}(G)$ can be computed in near-linear time iff the longest induced cycle of $H$ has length at most $5$. It is natural to ask whether these results extend to orbit counting.

Homomorphism and subgraph counting on graphs is an immense topic with an extensive literature in theory and practice. For a detailed discussion of practical applications, we refer the reader to a tutorial [53].

Homomorphism counting is intimately connected with the treewidth of the pattern $H$. The notion of tree decomposition and treewidth were introduced in a seminal work by Robertson and Seymour [47, 48, 49]; although it has been discovered before under different names [11, 33]. A classic result of Dalmau and Jonsson [24] proved that $\mathrm{Hom}_{H}(G)$ is polynomial time solvable if and only if $H$ has bounded treewidth, otherwise it is $\#W[1]$-complete. Díaz et al [26] gave an algorithm for homomorphism counting with runtime $O(2^{k}n^{t(H)+1})$ where $t(H)$ is the treewidth of the pattern graph $H$ and $k$ the number of vertices of $H$.

To improve on these bounds, recent work has focused on restrictions on the input $G$ [51]. A natural restriction is bounded degeneracy, which is a nuanced measure of sparsity introduced by early work of Szekeres-Wilf [56]. Many algorithmic results exploit low degeneracy for faster subgraph counting problems [20, 28, 2, 38, 45, 43, 37, 44].

Pioneering work of Bressan introduced the concept of DAG-treewidth for faster algorithms for homomorphism counting in bounded degeneracy graphs [14]. Bressan gave an algorithm for counting $\mathrm{Hom}_{H}(G)$ running in time essentially $m^{\tau(H)}$, where $\tau$ denotes the DAG-treewidth. The result also proves that (assuming ETH) there is no algorithm running in time $m^{o(\tau(H)/\log\tau(H))}$.

Bera-Pashanasangi-Seshadhri build on Bressan’s methods to discover a dichotomy theorem for linear time homomorphism counting in bounded degeneracy graphs [7, 8]. Gishboliner, Levanzov, and Shapira independently proved the same characterization using slightly different methods [31, 6].

We give a short discussion of the Triangle Detection Conjecture. Itai and Rodeh [35] gave the first non-trivial algorithm for the triangle detection and finding problem with $O(m^{3/2})$ runtime. The current best known algorithm runs in time $O(\min\{n^{\omega},m^{{2\omega}/{(\omega+1)}}\})$ [3], where $\omega$ is the matrix multiplication exponent. Even for $\omega=2$, the bound is $m^{4/3}$ and widely believed to be a lower bound. Many classic graph problems have fine-grained complexity hardness based on Triangle Detection Conjecture [1].

Homomorphism or subgraph orbit counts have found significant use in network analysis and machine learning. Przulj introduced the use of graphlet (or orbit count) degree distributions in bioinformatics [46]. The graphlet kernel of Shervashidze-Vishwanathan-Petri-Mehlhorn-Borgwardt uses vertex orbits counts to get embeddings of vertices in a network [54]. Four vertex subgraph and large cycle and clique orbit counts have been used for discovering special kinds of vertices and edges [59, 50, 60, 61]. Orbits counts have been used to design faster algorithms for finding dense subgraphs in practice [10, 52, 57, 4, 58].

We use $G$ to denote the input graph and $H$ to denote the pattern graph, both $G=(V(G),E(G))$ and $H=(V(H),E(H))$ are simple, undirected and connected graphs. We denote $|V(G)|$ and $|E(G)|$ by $n$ and $m$ respectively and $|V(H)|$ by $k$.

A pattern graph $H$ is divided into orbits, we use the definition from Bondy and Murty (Chapter $1$, Section $2$ [12]):

We refer to the set of orbits in $H$ as $\Psi(H)$ and to individual orbits in $\Psi(H)$ as $\psi$. Note that every vertex $h\in V(H)$ belongs to exactly one orbit. We can represent an orbit by a canonical (say lexicographically least) vertex in the orbit. Somewhat abusing notation, we can think of the set of orbits as a subset of vertices of $H$, where each vertex plays a “distinct role” in $H$. Fig. 1 has examples of different graphs with their separate orbits.

We now define homomorphisms.

We now define a series of counts.

• •

  $\mathrm{Hom}_{H}(G)$: This is the count of $H$-homomorphisms in $G$. So $\mathrm{Hom}_{H}(G)=|\Phi(H,G)|$.

• •

  $\mathrm{OrbitHom}_{H,\psi}(v)$: For a vertex $v\in V(G)$, $\mathrm{OrbitHom}_{H,\psi}(v)$ is the number of $H$-homomorphisms that map any vertex in the orbit $\psi$ to $v$. Formally, $\mathrm{OrbitHom}_{H,\psi}(v)=|\{\phi\in\Phi(H,G)\colon\exists u\in\psi,\,\phi(u)=v\}|$.

• •

  $\mathrm{OrbitHom}_{H,\psi}(G),\mathrm{OrbitHom}_{H}(G)$: We use $\mathrm{OrbitHom}_{H,\psi}(G)$ to denote the list/vector of counts $\{\mathrm{OrbitHom}_{H,\psi}(v)\}$ over all $v\in V(G)$. Similarly, $\mathrm{OrbitHom}_{H}(G)$ denotes the sequence of lists of counts $\mathrm{OrbitHom}_{H,\psi}(G)$ over all orbits $\psi$.

Our aim is to compute $\mathrm{OrbitHom}_{H}(G)$, which are a set of homomorphism counts. We use existing algorithmic machinery to compute homomorphism counts per vertex of $H$, so part of our analysis will consist of figuring out how to go between these counts. As we will see, this is where the LIPCO parameter makes an appearance.

We define vertex-centric homomorphism counts, which allows us to ignore orbits and symmetries in $H$. Quite simply, for vertices $h\in V(H)$ and $v\in V(G)$, we count the number of homomorphisms from $H$ to $G$ that map $h$ to $v$.

We can show that the vertex-centric counts can be obtained in near-linear time when $LICL(H)\leq 5$:

Before proving this theorem we need to introduce two more lemmas. First, we invoke the following lemma from [15]:

Second, we show how to use the output of Bressan’s algorithm to obtain the Vertex-centric counts:

We can now complete the proof of Theorem 4.2:

We now show how to go from vertex-centric to orbit counts, using inclusion-exclusion. Much of our insights are given by the following definitions.

We state two more tools in our analysis. The first lemma relates the counts obtained in the previous section ($\mathrm{VertexHom}_{H_{S}}(G)$) to the desired output ($\mathrm{OrbitHom}_{H}(G)$).

In order to prove this lemma, we need to define the Signature of a homomorphisms. Let $\phi$ be a homomorphism from $H$ to $G$, we define $\text{Sig}(\phi,\psi,v)$ to be the subset of vertices from the orbit $\psi$ that are mapped to $v$ in $\phi$. Formally $\text{Sig}(\phi,\psi,h)=\{h\in\psi:\phi(h)=v\}$.

We prove a series of claims regarding the signature.

The next claim allows us to relate the Signature with the Homomorphism Orbit Counts.

Now, we will relate the Signature with the Vertex-centric Counts:

Let $\Phi^{\prime}=\Phi(H_{S},G)$ be the set of homomorphism from $H_{S}$ to $G$. When $S$ forms an independent set there is an equivalence between the homomorphisms in $\Phi^{\prime}$ that map $h_{S}$ to $v$ and the set of homomorphisms in $\Phi(H,G)$ that map all the vertices of $S$ to $v$. In fact we can prove the following claim:

We will show one last claim that will be important when deriving the inclusion-exclusion formula: