Distributed Subgraph Finding: Progress and Challenges

Distributed subgraph finding is motivated by considering a user in a network whose connections are unknown to its users. Typical examples could be friends or followers in social networks, or computing devices in large networks. A prime question is what is the local structure of the network, e.g., do two connected users share common connections, or are they part of a slightly larger cycle or clique? While some social networks provide the user with information about common connections they have with their connections, the general fundamental question that arises is that of finding small subgraphs in such distributed settings. This type of questions also emerges when processing huge graphs by distributed systems. For example, Hirvonen, Rybicki, Schmid, and Suomela [HRSS17] study distributed algorithms for finding large cuts in triangle-free graphs, and Pettie and Su [PS13] study coloring in triangle-free graphs.

This article surveys the state-of-the-art in distributed subgraph finding. We focus on synchronous settings, in which the main complexity measure is the number of communication rounds that is required in order to find a subgraph $H$. We will elaborate on the computational models and on the possible interpretations of what it means to find a subgraph, but let us start with a warm-up.

Warm-up: locality. The first simple observation is that in a synchronous network with no additional restrictions, the round complexity of finding a subgraph $H$ by the devices in the network is $\Theta(k)$, where $k$ is the diameter of $H$. The reason for this is that in a single round of communication, all nodes of the network can learn the neighbors of their neighbors,¹¹1This assumes that all nodes begin with knowledge of their neighbors. Removing this assumption incurs another round of communication to this argument. and by induction, within $t$ rounds each node can learn the topology within its $t$-neighborhood.

To be more precise, what we get is that within $O(k)$ rounds, each node is able to list all the instances of $H$ to which it belongs. This is the most powerful variant of subgraph finding.

The clear drawback of the above example is that it sweeps the under the carpet the complexity of sending potentially very large messages in a single round. Therefore, while the above classic $\mathsf{LOCAL}$ model [Lin92] is suitable for studying many other tasks, it misrepresents the complexity of subgraph finding. We will thus focus mainly on two distributed settings that capture limited bandwidth, and in which the complexity of some subgraph finding problems is related. Additional settings will be discussed towards the end of the survey.

Computational models. The standard model that imposes restrictions on the bandwidth over the above setting is the $\mathsf{CONGEST}$ model [Pel00]. This is a synchronous model, in which each of $n$ nodes can send a message to each of its neighbors in every round, where the size of messages is bounded by $O(\log{n})$ bits. This choice of this bound on the size of messages allows sending a node identifier within a single message. Typically, the graph that is processed is the graph that underlies the communication network.

Another important model is the $\mathsf{CONGESTED~{}CLIQUE}$ model [LPPP05], which we will abbreviate as the $\mathsf{CLIQUE}$ model in this document, in which the $n$ nodes are part of a fully connected network, with the same message bound of $O(\log{n})$ bits as in the $\mathsf{CONGEST}$ model. Here, the input graph is an arbitrary graph $G$ on $n$ nodes, which is typically assigned through a bijection to the nodes of the $\mathsf{CLIQUE}$, such that each node receives as input the edges in $G$ that are adjacent to its assigned node.

Subgraph finding. The extreme case mentioned above, where each node in the system lists all instances of $H$ to which it belongs is referred to as membership listing (or sometimes local listing or local enumeration). In settings with bounded bandwidth, this is typically a difficult variant that is known to require many rounds of computation for many subgraphs (see, e.g., discussion about triangle finding in Section 2). A weaker variant is that of listing or enumeration, in which it is required that every instance of the subgraph $H$ is output by some node, but not necessarily a node which belongs to that instance.

Apart from these two listing variants, it is in many cases important to merely detect whether the input contains a copy of $H$ or not. The standard formalization of distributed detection is that if there is no copy of $H$ then all nodes output false, and otherwise at least one node outputs true. The reason for not demanding a unanimous output is to avoid incurring an overhead just for propagating the information of existence of $H$, for example if a graph contains a single copy of $H$ and has many nodes that are very far from that instance.

Similarly to the case of listing, the detection problem also has a membership variant, which requires each node to output true or false based on whether it is a part of a copy of $H$ or not.

Outline. Section 2 overviews the case in which $H$ is a triangle. It covers both the $\mathsf{CLIQUE}$ and the $\mathsf{CONGEST}$ models. Sections 3 and 4 address larger cliques and larger cycles in both models, respectively. Finally, Section 5 briefly mentions additional subgraphs and additional settings.

A naïve simulation of the warm-up algorithm for membership listing in the $\mathsf{CONGEST}$ or $\mathsf{CLIQUE}$ models, in which all neighbors are sent to each other neighbor one by one, gives a trivial $O(\Delta)$-round algorithm for triangle membership listing, where $\Delta$ is the maximum degree in the graph. However, it is possible to do better, as we overview in this section.

The $\mathsf{CLIQUE}$ model: The deterministic triangle listing algorithm of [DLP12] for the $\mathsf{CLIQUE}$ model can be easily generalized to list larger cliques. To find cliques of size $p$ for some integer $p\geq 3$, the set of nodes is partitioned into $n^{1/p}$ sets. Each node is assigned a $p$-tuple of sets and learns all edges between any two of its sets. A similar argument to that of triangles shows that indeed all $p$-cliques are listed by this algorithm, and that its round complexity is $O(n^{1-2/p}/\log{n})$. In fact, it is easy to see that this algorithm lists all instances of any subgraph $H$ of $p$ nodes.

This complexity is optimal, due to a lower bound of $\tilde{\Omega}(n^{1-2/p})$ rounds by Fischer, Gonen, Kuhn, and Oshman [FGKO18], which generalizes the aforementioned lower bound for triangle listing of [PRS18] and [ILG17], using additional machinery. In the $\mathsf{BROADCAST~{}CONGESTED~{}CLIQUE}$ model, Drucker, Kuhn, and Oshman [DKO14] show that $\Omega(n/\log{n})$ rounds are needed for $p$-cliques, even for the stronger detection variant, for almost all values of $p\geq 4$ (as long as $p\leq(1-\epsilon)n$ for some constant $\epsilon>0$).

For sparse graphs, Censor-Hillel, Le Gall, and Leitersdorf [CGL20] show that listing can be complete within $\tilde{O}(m/n^{1+2/p}+1)$ rounds, for $p\geq 3$. This follows from their $\mathsf{CONGEST}$ approach which is discussed below, and is tight up to polylogarithmic factors using the lower bound technique of [FGKO18, PRS18, ILG17]. This complexity was later obtained in a deterministic manner by Censor-Hillel, Fischer, Gonen, Le Gall, Leitersdorf, and Oshman [CFG⁺20].

As opposed to the listing variant, for $p$-clique detection the aforementioned hardness of obtaining lower bounds in the $\mathsf{CLIQUE}$ model by [DKO14] kicks in, and we do not know any non-constant lower bound (or any larger than 1 lower bound, for that matter), leaving the complexity of $p$-clique detection open for $p>4$.

The $\mathsf{CONGEST}$ model: Algorithms for finding larger cliques in the $\mathsf{CONGEST}$ model, as in the case of triangles, are also based on the conductance decomposition algorithms of Chang, Pettie, and Zhang [CPZ19] and of Chang and Saranurak [CS19]. The first sublinear algorithms for larger cliques in $\mathsf{CONGEST}$ are due to Eden, Fiat, Fischer, Kuhn, and Oshman [EFF⁺21]. They show that $4$-cliques can be listed in $\tilde{O}(n^{5/6+o(1)})$ rounds and that $5$-cliques can be listed in $\tilde{O}(n^{73/75+o(1)})$ rounds, w.h.p. These listing algorithms are more involved compared with the triangle listing algorithm, due to the need to handle, for example, a $4$-clique with one edge within a certain component and another edge within a different component, which imposes a complex challenge that becomes even worse as $p$ grows.

Following [EFF⁺21], the work of Censor-Hillel, Le Gall, and Leitersdorf [CGL20] provided algorithms for listing $p$-cliques in $\tilde{O}(n^{p/(p+2)})$ rounds, w.h.p., for all $p\geq 4$ except for $p=5$. For $p=5$, this work gave an algorithm which completes in $\tilde{O}(n^{3/4+o(1)})$ rounds, w.h.p. The main approach of these algorithms is iterating over the decomposition in a way that balances the minimum degree and the arboricity thresholds. Within each cluster, sparsity-aware listing helps speeding up the computation. While these algorithms improved upon the state-of-the-art for $p=4,5$ and were the first sublinear algorithms for $p\geq 6$, they fell short of the [FGKO18] lower bound of $\tilde{\Omega}(n^{1-2/p})$ rounds. The question of whether clique listing in the $\mathsf{CONGEST}$ model is as easy as, or harder than, its $\mathsf{CLIQUE}$ counterpart, was recently answered by Censor-Hillel, Chang, Le Gall, and Leitersdorf [CCGL21], using the newer conductance decomposition of Chang and Saranurak [CS19] and additional mechanisms for optimal sparsity-aware listing and for efficient transmission of edges in the clusters. Deterministic algorithms for $p$-clique listing were given by Censor-Hillel, Leitersdorf, and Vulakh [CLV22], with round complexities of $n^{1-2/p+o(1)}$. As is the case for triangles, these complexities are optimal up to the small $n^{o(1)}$ factor that arises from the expander routing procedure of Chang and Saranurak [CS20]. Later, the aforementioned improved deterministic expander routing of Chang, Huang, and Su [CHS24] was plugged into the framework of [CLV22] to obtain a round complexity of $\tilde{O}(n^{1-2/p})$, leaving only a $\operatorname{polylog}{n}$ gap compared with the lower bound.

For $p=4$, the tight listing of [CCGL21] also implies that $4$-clique detection is not easier than its listing counterpart in the $\mathsf{CONGEST}$ model. This is due to a lower bound of $\tilde{\Omega}(n^{1/2})$ for $4$-clique detection in $\mathsf{CONGEST}$, by Czumaj and Konrad [CK18]. The lower bound of [CK18] is more general, and says that detecting $p$-cliques in the $\mathsf{CONGEST}$ model requires $\tilde{\Omega}(n^{1/2}/p)$ rounds for $p\leq n^{1/2}$, and $\tilde{\Omega}(n/p)$ rounds for $p\geq n^{1/2}$. Thus, for values of $p$ larger than $4$, there is still a gap between detection and listing.

The lower bound of [CK18] uses a reduction from 2-party set disjointness. The same work also shows that listing can be done sufficiently fast by the two parties, which shows that if the detection problems are harder, a different lower bound technique must be used.

The $\mathsf{CLIQUE}$ model: Since the algorithm of [DLP12] easily lists any subgraph of $p$ nodes, we have that, in particular, $p$-cycles can be listed in the $\mathsf{CLIQUE}$ model within $O(n^{1-2/p})$ rounds (deterministically).

The detection variant was then addressed by Censor-Hillel, Kaski, Korhonen, Lenzen, Paz, and Suomela [CKK⁺19], who show a deterministic constant-round algorithm for detecting $4$-cycles. In addition, they show an $O(n^{0.158})$-round algorithm for detecting $p$-cycles, for any constant $p$. More accurately, the complexity is $2^{O(p)}n^{0.158}$ rounds. This is a randomized algorithm that relies on the color coding technique of Alon, Yuster, and Zwick [AYZ95], in order to avoid too much congestion that would be caused by collecting all possible candidates for cycle nodes. More recently, Censor-Hillel, Fischer, Gonen, Le Gall, Leitersdorf, and Oshman [CFG⁺20] showed that $2p$-cycles can be detected in $O(1)$ rounds for any $p$, using a technique which also allows fast girth approximation. This is, notably, a deterministic algorithm. For odd values of $p$, it is still not known whether there is a constant-round $p$-cycle detection algorithm.

For the parametrized version, in which the complexity depends on the number of $p$-cycles in the graph, the aforementioned work of Censor-Hillel, Even, and Vassilevska Williams [CEV24] gives a complexity of $\tilde{O}(p^{O(p)}\cdot n^{0.1567}/(t^{\frac{0.4617}{p-0.82408}}+1))$ rounds.

The $\mathsf{CONGEST}$ model: For $4$-cycle detection, Drucker, Kuhn, and Oshman [DKO14] provide a tight complexity of $\tilde{\Theta}(n^{1/2})$, by providing both an algorithm and a lower bound. They also show that for any odd value of $p$, detecting $p$-cycles requires $\tilde{\Omega}(n)$ rounds. The upper bound is obtained by setting a threshold of $T=2n^{1/2}$, and defining heavy nodes as nodes with at least $T$ neighbors. First, all non-heavy nodes send all their neighbors to all their neighbors, in $T$ rounds. This detects $4$-cycles which have at least 2 non-neighboring non-heavy nodes. Then, a heavy node $v$ with more than $T$ heavy neighbors reports that there exists a $4$-cycle. Finally, a heavy node $v$ with at most $T$ heavy neighbors sends its heavy neighbors to all of its neighbors, again in $T$ rounds. The reason for which too many heavy neighbors imply a $4$-cycle is because this means that the total number of neighbors of heavy neighbors is at least $T^{2}$, which is more than $2n$, and so there must be a node other than $v$ which is connected to two of the neighbors of $v$, and hence we have a $4$-cycle. Otherwise, if $v$ sends its heavy neighbors to all of its neighbors, then any $4$-cycle with two neighboring nodes that are heavy is detected by one of its nodes (by a simple case analysis).

The matching lower bound for $4$-cycles is a good point of reference for understanding lower bounds for the $\mathsf{CONGEST}$ model that rely on reductions from 2-party communication complexity. It relies on the fact that there is a $4$-cycle-free graph $G$ on $n$ nodes with $\Theta(n^{3/2})$ edges, due to Erdös [Erd38], whose work implies that this is the Turán Number of $4$-cycles [Tur41]. The setting is as follows. Each of two players, Alice and Bob, has an input string of $k$ bits, $x=(x_{1},\dots,x_{k})$ and $y=(y_{1},\dots,y_{k})$, respectively. By communicating with each other, the players need to compute the set disjointness function $Disj(x,y)$, whose value is 1 if and only if the input strings represent disjoint subsets of the set $\{1,\dots,k\}$, that is, if and only if there is no index $1\leq i\leq k$ such that $x_{i}=y_{i}=1$. The 2-party set disjointness problem is known to require exchanging $\Omega(k)$ bits, even by randomized protocols due to Kalyanasundaram and Schnitger [KS92], Razborov [Raz90], and Bar-Yossef, Jayram, Kumar, and Sivakumar [BJKS04]. The reduction to distributed detection of $4$-cycles is as follows. Each of the two players takes a subgraph of the $4$-cycle free graph $G$ according to their respective input. That is, the edges of $G$ are mapped to the set $\{1,\dots,k\}$, with a value of $n$ for which $k=\Theta(n^{3/2})$. Each player imagines a subgraph of $G$ that has an edge for any index in which their input is 1. The players then imagine that their two subgraphs are connect by a perfect matching: each node in Alice’s subgraph is connected to the respective node in Bob’s subgraph (the nodes of both subgraphs are the nodes of $G$). Now, it is easy to see that the combined graph contains a $4$-cycle if and only if the input strings $x,y$ are disjoint, as the only $4$-cycles that can occur are those that have two edges from the perfect matching, and two edges that represent the same index in the bit strings of the players. Thus, if Alice and Bob can simulate a distributed algorithm for $4$-cycle detection, they solve set disjointness. They simulate a given algorithm as follows. Any message that the algorithm sends between two nodes that are in the same subgraph (either that of Alice of that of Bob) can be internally simulated by the respective player. The only messages that need to be explicitly sent between the two players are those that are sent along the edges of the perfect matching. There are $n$ such edges, and so simulating a round of the detection algorithms costs $O(n\log(n))$ bits of communication between the two players. Since $\Omega(k)=\Omega(n^{3/2})$ is a lower bound on the total number of bits that need to be exchanged for solving set disjointness, we get that the distributed $4$-cycle detection algorithm must consist of at least $\Omega(k/n\log(n))=\Omega(n^{3/2}/n\log(n))=\tilde{\Omega}(n^{1/2})$ rounds.

A remark on triangle detection: While this approach for reductions which imply $\mathsf{CONGEST}$ lower bounds is heavily used in the literature, it is doomed to fail for triangle detection. The reason is that any triangle in a graph has at least one player which knows at least two of its nodes and thus all of its edges, which nullifies any attempt for a lower bound constructions, regardless of the 2-party problem or the graph construction.

Korhonen and Rybicki [KR17] then showed that the $\tilde{\Omega}(n^{1/2})$ lower bound for $4$-cycles can be extended and applies to $p$-cycles for all even values of $p$. Notably, in the spirit of the results of [DKO14], it is shown in Censor-Hillel, Fischer, Gonen, Oshman, Le Gall, and Leitersdorf [CFG⁺20] that going above this lower bound for $p=6$ would imply new lower bounds in circuit complexity, which are considered hard to obtain. The reason that this barrier for lower bounds works in the $\mathsf{CONGEST}$ model is because it is shown that it is sufficient to consider high-conductance clusters, and that these can simulate circuits in a similar manner to the $\mathsf{CLIQUE}$ model.

On the upper bound side, Korhonen and Rybicki [KR17] showed that $p$-cycle detection for any constant $p$ can be done in a linear in $n$ number of rounds. For odd values of $p$, this is optimal due to the above lower bound. They also showed that this can be done faster for degenerate graphs. Fischer, Gonen, Kuhn, and Oshman [FGKO18] showed how to detect $2p$-cycles within $O(n^{1-1/p(p-1)})$ rounds, for $p\geq 2$. This was subsequently improved by Eden, Fiat, Fischer, Kuhn, and Oshman [EFF⁺21], who showed how to detect $2p$-cycles in $\tilde{O}_{p}(n^{1-2/(p^{2}-p+2)})$ rounds for odd $p\geq 3$, and in $\tilde{O}_{p}(n^{1-2/(p^{2}-2p+4)})$ rounds for even $p\geq 4$. They also show that as opposed to the case of $4$-cliques, the listing variant of $4$-cycles is harder than its detection counterpart, requiring $\tilde{\Omega}(n)$ rounds. For $p=3,4,5$, Censor-Hillel, Fischer, Gonen, Oshman, Le Gall, and Leitersdorf [CFG⁺20] then showed improved algorithms (randomized) for detecting $2p$-cycles, which completes within $\tilde{O}(n^{1-1/p})$ rounds. Later, Fraigniaud, Luce, and Todinca [FLT23] showed that the technique of [CFG⁺20] provably cannot go beyond these values of $p$. Following this, Fraigniaud, Luce, Magniez, and Todinca [FLMT24] showed a major enhancement of this technique which does apply to larger values of $p$, yielding a complexity of $\tilde{O}(n^{1-1/p})$ rounds for detecting $2p$-cycles for any value of $p$.

Still, the upper bounds here are above the respective $\tilde{\Omega}(n^{1/2})$ lower bound.

Finding induced cycles is a different task, as it is insufficient to have edges that form a cycle, but rather also requires no other edges between nodes of the cycle. This question was addressed by Le Gall and Miyamoto [GM21a], who showed a lower bound of $\tilde{\Omega}(n)$ rounds for detecting induced $p$-cycles for any $p\geq 4$. This implies that detection of induced cycles is strictly harder than the non-induced case. This bound is tight for $p=4$, and this work also shows that obtaining a higher lower bound for $p=5,6,7$ cannot be done using the standard framework of reductions from 2-party communication complexity problems. For larger values of $p\geq 8$, a lower bound of $\tilde{\Omega}(n^{2-\Theta(1/p)})$ is given. In addition, this work studies the problem of finding induced diamonds, which are $4$-cycles with exactly one additional edge.

Finding Other Subgraphs: The literature has also been studying additional subgraphs, apart from cliques and cycles.

Drucker, Kuhn, and Oshman [DKO14] study the complexity of finding trees and complete bipartite subgraphs in the $\mathsf{BROADCAST~{}CONGESTED~{}CLIQUE}$ model. Korhonen and Rybicki [KR17] show that trees can be detected in $O(1)$ rounds in the $\mathsf{BROADCAST~{}CONGEST}$ model. Nikabadi and Korhonen [NK21] show algorithms for induced subgraphs, and lower bounds for induced cycles were given by Le Gall and Miyamoto [GM21b].

On the lower bound front, Gonen and Oshman [GO17] showed lower bounds for finding subgraphs that are created from smaller ones using certain allowed operations. Fischer, Gonen, Kuhn, and Oshman [FGKO18] showed that for any $p\geq 4$, there exists a subgraph $H$ of size $p$ such that $H$ detection requires $\tilde{\Omega}(n^{2-\Theta(1/p)})$ rounds. Eden, Fiat, Fischer, Kuhn, and Oshman [EFF⁺21] showed that this complexity is roughly the right one, by providing an upper bound of $\tilde{O}(n^{2-2/(3p+1)}+o(1))$ rounds. In particular, their result shows that there does not exist a constant-sized subgraph for which detection requires a truly quadratic number of rounds.

Subgraph Freeness Testing: The variant of testing for $H$-freeness has also been studied in the distributed setting, initially introduced by Brakerski and Patt-Shamir [BP11].

The definition of distributed testing for $H$-freeness requires that if there is no instance of $H$ in the graph then all the nodes output true, but instead of requiring at least one node to output false in case there is an instance of $H$ as would be an analog to the detection problem, testing only requires at least one node to output false in case the graph is far from being $H$-free. Here, being $\epsilon$-far from having a property is the same as its standard definition by Goldreich, Goldwasser, and Ron [GGR98], and means that no matter which $\epsilon$-fraction of the graph is changed (removed, in the case of $H$-freeness), the resulting graph must still have a copy of $H$. For triangles and other small subgraphs, this typically means that there are many instances of $H$ in a graph that is far from being $H$-free.

For testing triangle-freeness, Censor-Hillel, Fischer, Schwartzman, and Vasudev [CFSV19] showed a $O(1/\epsilon^{2})$-round algorithm. This was later improved by Even, Fischer, Fraigniaud, Gonen, Levi, Medina, Montealegre, Olivetti, Oshman, Rapaport, and Todinca [EFF⁺17] and Fraigniaud and Olivetti [FO17] to a complexity of $O(1/\epsilon)$ rounds. These, along with the work of Fraigniaud, Rapaport, Salo, and Todinca [FRST16] also show fast testing for larger cliques, cycles, and additional subgraphs.

Somewhat related is the work of Censor-Hillel and Khoury [CK24], which showed upper and lower bounds for computing and approximating the distance of a graph to being triangle-free.

Subgraph Finding in Dynamic Networks: Subgraph finding has also been studied from the perspective of dynamic networks. Bonne and Censor-Hillel [BC19] characterize the bandwidth that is required for various clique finding problems by algorithms that work in a dynamic setting and must produce the correct answer immediately at the end of the round in which a topology change occurs.

Subgraph finding in a harsh dynamic setting in which the number of topology changes per round is unlimited, was studied by Censor-Hillel, Kolobov, and Schwartzman [CKS21], who showed upper and lower bounds for small subgraphs.

Subgraph Finding in Quantum Networks: Izumi, Le Gall, and Magniez [ILM20] have shown that in a quantum $\mathsf{CONGEST}$ model, triangle detection can be solved within $\tilde{O}(n^{1/4})$ rounds, using a distributed version developed by Izumi and Le Gall in [IG19] of a Grover Search [Gro96]. Later, Censor-Hillel, Fischer, Le Gall, Leitersdorf, and Oshman showed quantum triangle detection in $\tilde{O}(n^{1/4})$ rounds and clique detection for larger cliques, using nested Grover searchers [CFL⁺22]. Later, van Apeldoorn and de Vos [vAdV22] have shown algorithms for cycle detection and girth computation in the quantum $\mathsf{CONGEST}$ model. The work of Fraigniuad, Luce, Magniez, and Todinca [FLMT24] further provides faster algorithms for cycle detection in the quantum $\mathsf{CONGEST}$ model.

The aforementioned cycle detection algorithm of [CEV24] in the $\mathsf{CLIQUE}$ model, gives a triangle detection algorithm in the quantum $\mathsf{CLIQUE}$ model. Intuition of why this currently does not extend to larger cycles is given therein.

We note that the listing variant for triangles cannot be improved using quantum tools, since it is obtained through information theoretic arguments, which apply to this setting as well.

Acknowledgements. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement no. 755839. The author thanks Francois Le Gall for clarifications and Dean Leitersdorf for useful feedback on a preliminary version of this survey.