Abstract 1 Introduction 2 Technical overview 3 Preliminaries 4 Algorithm 5 Lower bound 6 Conclusion References

Arboricity Matters in Triangle Counting with Random Edges

Arijit Bishnu ORCID Indian Statistical Institute, Kolkata, India    Debarshi Chanda ORCID Indian Statistical Institute, Kolkata, India    Gopinath Mishra ORCID Institute of Mathematical Sciences, Chennai, India
Abstract

Given a simple, unweighted, undirected graph G=(V,E) with |V|=n and |E|=m, and parameters 0<ε,δ<1, along with Degree, Neighbour, Pair and RandomEdge query access to G, we provide a query-based randomized algorithm to generate an estimate T^ of the number of triangles T in G, such that T^∈[(1−ε)⁢T,(1+ε)⁢T] with probability at least 1−δ. The query complexity of our algorithm is O~⁢(m⁢α⁢log⁡(1/δ)/ε3⁢T), where α is the arboricity of G. Our work can be seen as a natural progression to the line of recent works [Eden et al., SIAM J Comp., 2017; Assadi et al., ITCS 2019; Eden et al., SODA 2020] that considered subgraph or triangle counting with or without the use of RandomEdge query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work is the first to consider how RandomEdge query can leverage the structural property of arboricity. Furthermore, continuing in the line of work of Assadi et al. [APPROX/RANDOM 2022], we also provide a lower bound of Ω~⁢(m⁢α⁢log⁡(1/δ)/ε2⁢T) that matches the upper bound exactly on arboricity, δ, and almost on ε.

Keywords and phrases:
Triangle counting, Sublinear algorithms, Subgraph counting
Category:
RANDOM
Copyright and License:
[Uncaptioned image] © Arijit Bishnu, Debarshi Chanda, and Gopinath Mishra; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Streaming, sublinear and near linear time algorithms
Related Version:
Full Version: https://arxiv.org/abs/2502.15379
Editors:
Mohit Singh and Tom Gur

1 Introduction

Counting the number of triangles present in graphs is a classical problem [20, 5, 53, 4, 10]. Researchers in the streaming (sub-linear space) community have studied this problem for the last two decades; see [10, 11, 35, 2, 17, 6, 36, 18, 22, 55, 41] for a sample of such works. The problem has also been studied by researchers in the property testing (sub-linear time) community in the last decade [26, 48, 39, 11, 13, 28, 35]. Here, graphs can be accessed only through certain queries. On the other hand, starting with the work of [20], the graph parameter called arboricity has also found its use in triangle counting [28]. Our work shows the use of arboricity in triangle counting where the graph can be accessed through random edge queries along with other standard queries like Degree, Neighbour and Pair.

Counting triangles has been a well-motivated problem with applications across various domains like optimizing query size in database join problems [10, 9, 7], computing clustering coefficients, transitivity ratio [1, 46, 60, 44], studying structures in web graphs [25, 23] etc. For a more thorough overview, see the surveys [3, 57]. The parametrization based on arboricity is also of practical interest due to the occurrence of low-arboricity graphs in various real-world scenarios [24, 42, 50, 31, 12, 23, 54].

Formally, we are given a simple, unweighted, undirected graph G=(V,E) with |V|=n, and |E|=m. The neighbours of v is denoted 𝖭⁢(v) = {u|(u,v)∈E} and the degree of the vertex v is denoted degv=|𝖭⁢(v)|. We are given the following queries to access the graph:

  • ■

    Degree⁢(v): Given a vertex v, return degv.

  • ■

    Neighbour⁢(v,i): Given a vertex v∈V and i∈[n], return the i-th vertex u∈𝖭⁢(v) if it exists; otherwise, we get ⟂.

  • ■

    Pair⁢(u,v): Given two vertices u,v∈V, return 1 if (u,v)∈E, and 0, otherwise.

  • ■

    RandomEdge: Return an edge e∈E uniformly at random.

We will call the Degree, Neighbour and Pair queries taken together to be local queries [7]. Now, we formally state our problem:

Triangle Estimation:

Given ε,δ with 0<ε,δ<1, obtain an estimate T^ of the number of triangles T in

the graph G, such that T^∈[(1−ε)⁢T,(1+ε)⁢T] with probability at least 1−δ.

From now on, we refer T^ to be an (ε,δ) estimate of T. One of the graph parameters that has been relevant to quantify the complexity of triangle counting algorithms within the context of RAM model [20], streaming model [13], distributed model [34, 56, 30, 45] and query model [29], is the arboricity of the graph G, denoted α. The arboricity of a graph can be seen as a measure of the density of the graph.

Definition 1 (Arboricity(α)).

The arboricity of a graph G=(V,E), denoted α, is the minimum number of spanning forests that E can be partitioned into.

Recent works have established various ways to construct lower bounds incorporating the impact of ε and δ both in graph property testing [8] and other problems [58]. Our lower bounds will also involve ε and δ. To illustrate the dependence of ε, δ, and polylog terms on the query complexity of our algorithm, we will use two notations at times in place of O⁢(∙) – O~⁢(∙) hides polylog factors only but shows dependence on ε and δ, whereas O~ε,δ⁢(∙) hides both ε, δ and polylog terms.

1.1 Our results

In this section, we present the main results of this work.

Upper bound

We show that using random edge queries in addition to local queries, we can obtain an (ε,δ) estimate of T where the query complexity is parametrized by arboricity apart from the usual parameters of edge, vertex, the number of triangles, ε, and δ. The work of [20] established the role of arboricity in the problem of triangle counting giving an O⁢(m⁢α) time algorithm to exactly count the number of triangles T in the RAM model. In recent works in the property testing model, [26] gave an algorithm that uses local queries and requires O~ε,δ⁢(nT1/3+min⁡{m,m3/2T}) queries to obtain an (ε,δ) estimate T^ of T. Using RandomEdge in addition to the local queries, [7] proposed an algorithm that uses O~⁢(m3/2⁢log⁡(1/δ)ε2⁢T) queries. Following this, [28] was introduces the parameter of arboricity to triangle counting in the query based setup. They proposed an algorithm that uses O~⁢(nT1/3+m⁢α⁢log3⁡(1/δ)ε5⁢T) local queries to obtain an (ε,δ) estimate T^ of T. Our work follows in the line of the works of [26, 7, 28], where we use RandomEdge in addition to local queries to obtain an algorithm that uses O~⁢(m⁢α⁢log⁡(1/δ)ε3⁢T) queries (see the last row in Table 1). Formally,

Theorem 2 (Upper bound).

Given a simple, unweighted and undirected graph G=(V,E) with |V|=n, |E|=m and arboricity α, and access to the graph via Degree, Neighbour, Pair and RandomEdge queries, an (ε,δ) estimate T^ of T can be obtained using O~⁢(m⁢α⁢log⁡(1/δ)ε3⁢T) queries.

A constant-pass O~⁢(m⁢κε4⁢T) space streaming algorithm was proposed in [13] for obtaining an (ε,δ)-estimate of the number of triangles in a graph, where κ is the degeneracy of the graph. Our algorithm can be directly extended to a constant pass streaming algorithm using O~⁢(m⁢αε3⁢T) space. By the fact that α≤κ≤2⁢α, our algorithm’s space complexity is as good as the algorithm of [13] in terms of the graph parameters, and asymptotically better in terms of the approximation factor ε.

Lower bound

We also establish a lower bound involving the arboricity and the parameters ε and δ. Reductions from communication complexity is a well studied method to establish lower bound results in terms of query complexity [15, 29, 32]. Using only Degree and Neighbour queries, triangle counting requires Ω⁢(m) queries [33]. Including Pair with the previous two queries, [26] established a lower bound of Ω⁢(nT1/3+m3/2T) queries which matches their upper bound up to p⁢o⁢l⁢y⁢(log⁡(n/δ)ε) factors. Later, a simpler proof was proposed for the same bound through reduction from communication complexity problems [29]. This was subsequently extended to incorporate arboricity with a bound of Ω⁢(nT1/3+m⁢αT) queries [28] which again matched their proposed upper bound up to p⁢o⁢l⁢y⁢(log⁡(n/δ)ε) factors. If RandomEdge query is allowed along with all three local queries, the above lower bounds of Ω⁢(nT1/3+m3/2T) and Ω⁢(nT1/3+m⁢αT) become Ω⁢(m3/2/T) [29] and Ω⁢(m⁢α/T) [28], respectively. 111Though [28] does not mention about Ω⁢(m⁢α/T) explicitly, it is not difficult to see it from their construction. Also, this lower bound of Ω⁢(m⁢α/T) matches with our upper bound (stated in Theorem 2) in terms of dependence on m,T, and α. As we have mentioned, for general graphs, there is an algorithm that makes O~⁢(m3/2⁢log⁡(1/δ)ε2⁢T) queries, where each query is either a local query or a RandomEdge query [7]. Recently, in [8], it has been shown that the algorithm of [7] is optimal (up to p⁢o⁢l⁢y⁢(log⁡(n)) factors) in terms of all parameters including ε and δ through a lower bound of Ω⁢(m3/2⁢log⁡(1/δ)ε2⁢T) queries for obtaining an (ε,δ) estimate of T using local and RandomEdge queries. However, this does not consider the dependency of the query complexity on arboricity of the graph. Like our upper bound, the lower bound of our work also captures the role of arboricity and the parameters ε, and δ when the queries allowed are the local and the RandomEdge queries. Moreover, our lower bound combines the parametrization of [8] and [28] in terms of ε, δ, and α, respectively, to establish an improved lower bound.

Theorem 3 (Lower bound).

Given a simple, unweighted and undirected graph G=(V,E) with |V|=n, |E|=m and arboricity α, and access to the graph via Degree, Neighbour, Pair and RandomEdge queries, obtaining an (ε,δ) estimate T^ of T requires Ω⁢(m⁢α⁢log⁡(1/δ)ε2⁢T) queries.

Table 1: Upper and lower bounds for the Triangle Counting problem. Entries marked with an asterisk (∗) are our results proved in this paper.
Without RandomEdge With RandomEdge
Without Arboricity UB: O~ε,δ⁢(nT1/3+m3/2T) [26] UB: O~⁢(m3/2⁢log⁡(1/δ)ε2⁢T) [7]
LB: Ω~⁢(m3/2⁢log⁡(1/δ)ε2⁢T) [8] LB: Ω~⁢(m3/2⁢log⁡(1/δ)ε2⁢T) [8]
With Arboricity UB: O~⁢(nT1/3+m⁢α⁢log3⁡(1/δ)ε5⁢T) [28] (∗) UB: O~⁢(m⁢α⁢log⁡(1/δ)ε3⁢T)
(∗) LB: Ω⁢(m⁢α⁢log⁡(1/δ)ε2⁢T) (∗) LB: Ω⁢(m⁢α⁢log⁡(1/δ)ε2⁢T)

Table 1 describes the upper and lower bounds across different query accesses and parametrization for the triangle counting problem, with our contributions in this work highlighted with an asterisk (∗) mark. Table 1 shows that it is only natural to study the problem of triangle estimation with the use of RandomEdge and arboricity as a parameter after the works of [26, 28, 7, 8]. We believe our work also raises some new questions: (a) it opens up the question of quantifying the impact of α to count other subgraphs (e.g., k-cliques) using RandomEdge and other local queries; (b) there remains a small gap of 1/ε between our upper and lower bounds that remain to be resolved.

1.2 Related work in other models

The problem of triangle counting is a problem that has been extensively studied across various models of computation. Here, we discuss the works in RAM and streaming models.

RAM model.

The work of [20] proposed an O⁢(m⁢αT) algorithm in the RAM model that remains the best known till date. Recent works have shown it to be conditionally optimal under the 3SUM [43] and APSP hypotheses [59].

Streaming model.

In the data streaming model, a long line of work [51, 52] has culminated in an O~⁢(mT⁢(ΔE+ΔV))-space one-pass streaming algorithm for insertion only model [39] that has been shown to be optimal through the combined lower bounds proposed in [16, 39]. Here, ΔE (ΔV) denote the maximum number of triangles incident on an edge e (a vertex v) in the graph G. There have been works on triangle counting in multi-pass setup as well as in other streaming models (e.g., turnstile, cash-register etc.) [48, 11, 39, 37, 38, 40, 13].

1.3 Paper organization

Section 2 discusses a broad overview of the techniques we use, and contextualizes it with respect to the relevant prior works. Section 3 sets up the preliminaries for our proofs, including the structural results involving arboricity of a graph. Section 4 discusses the query-based algorithm by breaking the discussion into several parts: a weight function (Section 4.1), an oracle based algorithm (Sections 4.2) and its implementation (Section 4.3) and the final algorithm (Section 4.4). The lower bounds are discussed in Section 5. Some of the proofs are deferred to the Appendix. We have also included the full version of the paper in the Appendix.

2 Technical overview

In this section, we give a broad overview of the techniques used in this work. We denote by Te the number of triangles incident on the edge e, and the degree of an edge by dege =deg(u,v)=min⁡{degu,degv}.

2.1 Upper bound

Our starting point is to use RandomEdge queries to obtain S, a random sample of edges of size s and try to estimate the number of triangles T incident on the edges of S. As the RandomEdge query samples edges uniformly at random, the expected number of triangles each sampled edge participates in is Tm. Hence, an obvious approach to estimate T would be to count the number of triangles Te each edge e participates in, and take their average for the sampled edges and scale it appropriately. However, there are two issues with this approach.

Firstly, counting the number of triangles an edge e participates in exactly would require Ω⁢(dege) local queries. Therefore, we have to sample sufficiently many neighbour vertices for each edge e and check if it forms a triangle or not to obtain a good estimate of Te.

Secondly, even though the expected number of triangles incident on each edge is Tm, individual edges e can participate in a large number of triangles, i.e., Te can be Ω⁢(T). This makes the variance of the estimate too high, and requires s to be large to obtain a good estimate. To work around this issue, we fix a threshold τ based on the arboricity α of the graph, that has a connection to the number of triangles in the graph. We call edges that participates in more than τ triangles τ-heavy edges. Correspondingly, any edge that participates in less than τ triangles is called τ-light edges. For now, assume we are given access to an oracle Heavy to decide whether an edge is light or heavy. We call the triangles consisting exclusively of heavy edges as heavy triangles, and the remaining triangles as light triangles. The threshold τ is set at an appropriate multiple of α so that heavy triangles constitute only ε fraction of the triangles. Thus, we can forget about the τ-heavy edges and focus only on counting the light triangles. This brings us to the issue of sampling light triangles uniformly at random. We define a weight function on the edges that assigns each light triangle to one of its constituent light edges. The weight function is defined to be the number of light triangles assigned to the edge, with each heavy edge being assigned a value of 0.

Now the algorithm’s objective is to estimate this weight function, which cannot be accessed or sampled directly. Observe that there can be multiple assignments of the light triangles to the edges, and consequently multiple weight functions. It suffices for the algorithm to estimate any one of them. In that regard, for all the light edges in our sample S, we maintain a partial non-conflicting assignment. Such an assignment can be extended to a valid assignment, and consequently, a valid weight function. Based on this assignment, we obtain an estimate of the corresponding weight function, which, given an appropriately fixed threshold τ=Θ⁢(αε), and setting s to O~⁢(m⁢αε3⁢T⁢log⁡1δ) will give an (ε,δ) estimate of T.

To design the oracle Heavy for a given edge e, we estimate the number of triangles each edge participates in. We can estimate it by sampling each triangle independently through the corresponding neighbouring vertex of e. The probability of obtaining a triangle for an edge e through a random neighbour is Tedege. Hence, for the heavy edges where Te≥τ, Te can be estimated using sufficiently small number of queries. For the light edges where Te≤τ, the probability of obtaining a triangle through a random neighbour can be arbitrarily low. However, note that the lower probability of obtaining triangles allows for high approximation error. We then design a bucketing trick to exploit this trade-off to implement an efficient algorithm to decide whether an edge is heavy or light. For full details, see Section 4.

2.2 Lower bound

Several lower bounds for triangle counting problems based on reductions from the disjointness problem in communication complexity [29, 7, 28] are often close to the best possible upper bounds. It is not clear whether this approach can give tight bounds involving ε and δ. Recently, Assadi and Nguyen [8] showed that any algorithm to find an (ε,δ)-estimate of the number of triangles T must make at least Ω⁢(m3/2⁢log⁡(1/δ)ε2⁢T) queries, where each query is either a local query or a RandomEdge query.222Note that this lower bound matches exactly with the corresponding upper bound in [7]. To prove the lower bound, they introduced a new query problem called the Popcount Thresholding Problem (PTP), and gave reductions from this problem to triangle estimation, instead of using disjointness. We also show a reduction from PTP. In particular, we show that for any value of arboricity α, we can design a graph G with arboricity α such that finding an (ε,δ)-estimate in it using Ω⁢(m⁢α⁢log⁡(1/δ)ε2⁢T) queries would violate the lower bound of PTP.

In the PTPM,k,γ problem, we are given query access to a binary string x∈{0,1}M and must decide whether it was generated from one of two similar distributions. In the first distribution, denoted 𝒟0, each bit of the string is independently set to 1 with probability (1−2⁢γ)⁢k/M; in the second distribution, denoted 𝒟1, each bit is independently set to 1 with probability (1+2⁢γ)⁢k/M. The objective is to distinguish between these two cases by adaptively querying bits of x. For suitable choice of k,γ, and δ, with probability at least 1−δ, a string from 𝒟0 will have fewer than (1−γ)⁢k 1s and a string from 𝒟1 will have more than (1+γ)⁢k 1s. Hence, to distinguish whether x is generated from 𝒟0 or 𝒟1, it suffices to estimate the number of 1s present in x, i.e. ‖x‖1 upto multiplicative approximation factor γ. Assadi et al. [8] showed that (under suitable choice of parameters) Ω⁢(M⁢log⁡(1/δ)γ2⁢k) queries to x are needed to distinguish between the case whether x∼𝒟0 and x∼𝒟1 with probability 1−δ.

We now describe the hard graph instance Gx⁢(Vx,Ex) used in the reduction. The core structure of Vx consists of three vertex sets: A, B, and R, where |A|=|B|=Θ⁢(m/α) and |R|=Θ⁢(α). Every vertex in A∪B is connected to all vertices in R, forming a bipartite clique between A∪B and R. The subgraph induced by A∪B contains Θ⁢(m) edges, with each vertex having degree at most O⁢(α). We associate each index i∈[M] from the PTPM,k,γ instance with a potential edge between A and B, and include the edge if and only if xi=1. Thus, the number of edges between A and B equals ‖x‖1, and the total number of triangles in the graph Gx is ‖x‖1⋅|R|. By choosing parameters such that M=Θ⁢(m), k=Θ⁢(T/α), and γ=Θ⁢(ε), distinguishing whether x is drawn from 𝒟0 or 𝒟1 becomes equivalent to distinguishing whether the number of triangles in the graph is at most (1−ε)⁢T or at least (1+ε)⁢T. To complete the reduction, we show that each local query and RandomEdge query to Gx can be simulated using only a constant number of queries to x. To enable this, we extend the construction by introducing two additional disjoint vertex sets A′ and B′, resulting in five disjoint sets: A, B, R, A′, and B′. All triangles in the graph are confined to the sets A, B, and R, while the sets A′ and B′ are added to ensure that the degree of each vertex in Vx remains identical regardless of whether x is drawn from 𝒟0 or 𝒟1. With this construction, every allowable query to the graph can be simulated with O⁢(1) queries to x. For full details, see Section 5.

2.3 Contextualizing with relevant prior work

Our work follows as a natural progression to the works of [26, 7, 28] in the property testing framework. So, let us review the algorithmic techniques at play in them.

We start by describing a simple randomized algorithm due to Assadi et al. [7] for estimating the number of triangles in a graph when we have access to queries like Degree, Neighbour, Pair, and RandomEdge. First, pick a random edge {u,v} and let degu≤degv. If degu≤τd, pick a random neighbour w of u and check if {u,v,w} forms a triangle in the correct order, i.e., in the increasing degree sequence. The probability of sampling a triangle in this case is 12⁢m⋅1degu⋅deguτd=12⁢m⁢τd. If degu>τd, pick a vertex w at random with probability proportional to its degree. This is possible because RandomEdge allows sampling vertices proportional to their degrees. The probability of sampling a triangle in this case is 12⁢m⋅degw2⁢m≥τd4⁢m2. By setting τd=2⁢m, we can ensure that the algorithm works effectively. This process finds a triangle with probability Ω⁢(T/m3/2). Finally, by repeating this process O~⁢(m3/2⁢log⁡(1/δ)/ε2⁢T) times, we can estimate the total number of triangles.

The setting τd=Θ⁢(m) seems to be the optimal choice for the general case. We do not see a way to generalize the above idea when parametrized by arboricity. In bounded arboricity graphs, the structure and degree distribution of the graph may not align with this approach. So, a different strategy would be required for graphs with bounded arboricity to achieve the desired bound of O~⁢(m⁢α⁢log⁡(1/δ)/ε3⁢T).

Our approach is more closely aligned with the framework of triangle counting developed by Eden et al. [26] with access to local queries only. The algorithm by Eden et al. [26] starts by picking a small set of vertices at random and for each sampled vertex, the algorithm tries to estimate the number of triangles it participates in. Some vertices appear in many triangles and are called heavy, while others are called light. To keep the estimate as desired, the algorithm limits the contribution of heavy vertices and focuses mainly on light ones. It gives more weight to triangles that have more light vertices. Since the number of triangles a vertex participates in cannot be obtained directly, the algorithm estimates this by sampling edges incident on the sampled vertices and checking if they close triangles with neighbouring vertices of those edges. The above framework has also been subsequently extended for clique counting in general graphs [28] and that in bounded arboricity graphs [28].

In summary, the idea of dividing the triangles in terms of their constituent edges or vertices into heavy and light, and dealing with them separately has been a long-standing technique for subgraph counting in sublinear models [48, 26, 11, 27, 38, 28, 13]. The algorithmic techniques vary on how to set and leverage this thresholding behaviour for the specific problems and models. Furthermore, allowing RandomEdge queries has yielded simpler algorithms for subgraph counting problems [7]. The usage of RandomEdge enables us to design a simple algorithm that uses the structural parameter of arboricity.

The lower bounds for the triangle counting problem in the query model have come from indistinguishability arguments [26] or reduction from communication problems, particularly set-disjointness [29, 7, 28] with [28] establishing arboricity-sensitive lower bounds. On the other hand, several recent works [14, 8] have established lower bounds for property testing problems through reductions to query problems that are sensitive to ε and δ. In this work, we extend the ε,δ-sensitive lower bound of [8] to the triangle counting problem for any value of arboricity α.

3 Preliminaries

3.1 Notations

The set of positive integers {1,2,…,x} is denoted [x]. The set of triangles in G is denoted Δ, and individual triangles are denoted 𝗍. (v,e) denotes a triangle formed by the vertices v and the endpoints of the edge e. Unif⁢(S) denotes an element of S is chosen uniformly at random.

3.2 Arboricity and its properties

As arboricity plays a crucial role in our work, we put together all the structural results that involve arboricity here. Let us restate the definition once more.

Definition 4 (Arboricity(α)).

The arboricity of a graph G=(V,E), denoted by αG, is the minimum number of spanning forests that E can be partitioned into.

The arboricity of a graph can be seen as a measure of the density of the graph. αG can be at least ⌈m/(n−1)⌉. Also, αG≥αH where H is any subgraph of G. We will write α instead of αG when the underlying graph is understood. We introduce the following result due to [20] on the sum of edge degrees over all edges in the graph.

Lemma 5 (Sum of dege [20]).

Given a graph G=(V,E) with arboricity α and |E|=m, ∑e∈Edege≤2⁢m⁢α.

The following result due to [28] builds on the work of [20] to bound the number of triangles based on the number of edges m and arboricity α.

Lemma 6 (Triangle upper bound [28]).

Given a graph G=(V,E) with arboricity α and |E|=m, the graph G has at most m⁢α triangles.

Note that this upper bound is also tight, i.e., there exists graphs that contain m edges and Ω⁢(m⁢α) triangles. Additionally, arboricity α can be at most O⁢(m) [28]. Thus, all our results can be reformulated by plugging in this upper bound.

3.3 Chernoff bounds

We will be using the following variation of the Chernoff bound that bounds the deviation of the sum of independent Poisson trials [49].

Lemma 7 (Multiplicative Chernoff bound).

Given i.i.d. random variables X1,X2,…,Xt where Pr⁡[Xi=1]=p and Pr⁡[Xi=0]=(1−p), define X=∑i∈[t]Xi. Then, we have:

Pr⁡[X≤(1−ε)⁢𝔼[X]] ≤exp⁡(−𝔼[X]⁡ε23) 0≤ε<1
Pr⁡[X≥(1+ε)⁢𝔼[X]] ≤exp⁡(−ε2⁢𝔼[X]2+ε) 0≤ε

4 Algorithm

This section describes the algorithm and its related concepts. Section 4.1 formally defines the weight function for edges and associated structural results. Section 4.2 describes the algorithm assuming access to an idealized oracle that can decide if an edge is heavy or light (based on whether the edge has many or few incident triangles). Section 4.3 describes how to actually implement this oracle within the problem setup. Section 4.4 puts everything together to develop the final algorithm.

4.1 Weight function

In this section, we formalize the ideas of heavy and light edges and weight function for the edges.

Heavy and light edges and triangles

First, we define heavy and light edges and correspondingly, heavy and light triangles.

Definition 8 (τ-heavy and τ-light edges).

An edge e∈E is defined to be a τ-heavy (resp. τ-light) edge if it participates in more than τ (resp. ≤τ) triangles.

Definition 9 (τ-heavy and τ-light triangles).

A triangle 𝗍∈Δ is called a τ-heavy triangle if all its three edges are τ-heavy edges. A triangle that is not τ-heavy is a τ-light triangle.

We denote by TLτ and THτ the number of τ-light and τ-heavy triangles in the graph G, respectively. The following lemma bounds the number of τ-heavy triangles in a graph using the parameter of arboricity.

Lemma 10 (Upper bound on THτ).

Given a graph G=(V,E) with T triangles, the number of τ-heavy triangles is at most 3⁢T⁢ατ.

Proof.

Note that the graph G=(V,E) has T triangles containing at most 3⁢T edges. By Definition 9, τ-heavy triangles have all three of their edges to be τ-heavy edges, τ or more triangles incident on each of them. Hence, the number of τ-heavy edges in G is at most 3⁢Tτ .

Now consider the subgraph H=(VH,EH) of G induced by the τ-heavy edges in G. We know, EH≤3⁢Tτ. Also, αH≤αG=α (see Section 3.2). Hence, by Lemma 6, we know that H contains at most 3⁢T⁢ατ triangles. ◀

The following corollary follows from Lemma 10 and the fact that T=TLτ+THτ.

Corollary 11 (Lower bound on TLτ).

Given a graph G=(V,E), there are at least (1−3⁢ατ)⁢T τ-light triangles.

Weight function for the edges

Now, we define a weight function for the edges. As a triangle is incident to multiple edges, the objective of a weight function is to charge each of the light triangles to exactly one of its participating light edges. To ensure this, we do not charge any light triangle to any heavy edge that it may be incident on. Each light edge e can be charged by at most Te triangles, i.e., all the triangles the edge e participates in. To avoid over-counting, we ensure that the sum of the weight function over all edges is equal to the number of light triangles, TLτ. (𝗍,𝖾) denotes that the triangle 𝗍 is charged to the edge e.

Definition 12 (Triangle weight function (w)).

We define a function w:E→ℕ to be a triangle weight function if it satisfies the following two conditions:

Condition (1):w⁢(e)≤{Teif e is a light edge0if e is a heavy edgeCondition (2):∑e∈Ew⁢(e)=TLτ

Observe that there are multiple such weight functions (e.g., a triangle with 3 light edges can be assigned to any one of these 3 edges). Henceforth, we denote the set consisting of valid triangle weight functions by 𝒲. We now state a property of valid weight functions. Note that this property is true for any w∈𝒲.

Lemma 13 (Expectation of w⁢(e)).

Consider any triangle weight function w∈𝒲. If we select an edge e∈E uniformly at random, then the expected value of w⁢(e) is TLτm, i.e., 𝔼e∼Unif⁢(E)w⁢(e)=TLτm.

Proof.

Given that the edges have been chosen uniformly at random and the condition of the triangle weight function (Definition 12), we have:

𝔼e∼Unif⁢(E)w⁢(e)=∑e∈Unif⁢(E)1m⁢w⁢(e) =1m∑e∈Ew(e)=TLτm.

◀

4.2 Oracle based algorithm

Our algorithm, due to its usage of the triangle weight function, requires knowledge of whether an edge is heavy or light. The problem of deciding whether an edge is heavy is non-trivial as it directly relates to number of triangles the edge participates in. In this section, we assume black-box access to an oracle HeavyOracle that helps us determine if an edge is heavy.

HeavyOracle⁢(e,α,ε) ={1if edge e is a h⁢αε-heavy edge, i.e., τ=h⁢αε0if edge e is a l⁢αε-light edge, i.e., τ=l⁢αε

Here h and l (h>l) are constants to be determined later. We will discuss an efficient implementation of this oracle later.

Let us first consider the case where we are given an oracle that given an edge e, returns the exact value of a weight function, w⁢(e). Given we can sample edges uniformly at random through the RandomEdge query, we can compute 𝔼e∼Unif⁢(E)[w⁢(e)]=TLl⁢αε using this oracle on the sampled edges. However, no such oracle exists in our model. Hence, we try to simulate one through an empirical estimate of the weight function, w^⁢(e). Recall the fact that there are many valid weight functions, each being characterized by every light triangle being charged to one of its constituent light edges. Our algorithm will work if the empirical weight function w^ estimates any one of these weight functions. We achieve this by ensuring that a triangle is not sampled through more than one edge (see Line 17 of Algorithm 1). Thus, the assignments that we consider can be extended to a valid weight function w, and our algorithm can be thought of as estimating this weight function through w^. We develop our initial algorithm (Algorithm 1) assuming T~, an estimate of T satisfying T~≤2⁢T.

In Algorithm 1, we assume that we know m exactly. In fact, our algorithm and analysis work even if we have a constant factor approximation of m. This can be achieved by using O~ε,δ⁢(1) queries [7].

We now state and analyse the algorithm.

Algorithm 1 Triangle Counting Algorithm - with access to Heavy, and knowledge of T~.
Lemma 14 (Expectation of Algorithm 1).

Algorithm 1 ensures that 𝔼[w^⁢(ei)]=TLl⁢αε/m, and 𝔼[T^]=TLl⁢αε.

Proof.

Let ℰi be the event that the edge e is chosen as the i-th edge sample. We proceed with the proof by considering two different cases: dege<α and dege≥α.

Case I: (deg𝒆<𝜶).

When dege<α, re is set to 0 with probability 1−dege/α and 1 with probability dege/α, and w^⁢(e) is evaluated through a single query. Thus,

𝔼[w^⁢(ei)|ℰi] =degeα⁢∑k∈[w⁢(e)]1dege⁢α+(1−degeα)⋅0=w⁢(e) (1)
Case II: (deg𝒆≥𝜶).

On the other hand, when dege≥α, let Zj,j∈[re] be the contribution of each re queries made for the edge e to the weight function estimate. Then,

𝔼[Zj|ℰi] =∑k∈[w⁢(e)]1dege⁢dege=w⁢(e) (2)

Correspondingly, we have by linearity of expectation and Equation (2):

𝔼[w^⁢(ei)|ℰi]=1re⁢∑j∈[re]𝔼[Zj|ℰi]=𝔼[Zj|ℰi]=w⁢(e) (3)

Given that we draw each edge e∈S uniformly at random, we now have by Equations (1), (3), and Lemma 13:

𝔼[w^⁢(ei)]=𝔼e∼Unif⁢(E)w⁢(e)=TLl⁢αε/m

By linearity of expectations, we obtain

𝔼[T^]=𝔼[ms⁢∑i∈sw^⁢(ei)]=TLl⁢αε

◀

Note that Lemma 14 holds irrespective of whether the assumption T~≤2⁢T is satisfied or not. Next, we turn our attention to the variance of w^⁢(e).

Lemma 15 (Variance of Algorithm 1).

Algorithm 1 ensures that Var[w^⁢(ei)]≤(1+h)⁢αε⋅𝔼e∼Unif⁢(E)[w⁢(e)].

Proof.

Again, we consider two different cases as in the proof of Lemma 14.

Case I: (deg𝒆<𝜶).

When dege<α, Algorithm 1 makes at most 1 query as r≤1. As w^⁢(e)≤α, we have

Var[w^⁢(ei)|ℰi]≤𝔼[w^⁢(ei)2|ℰi]≤α⁢𝔼[w^⁢(ei)|ℰi] (4)
Case II: (deg𝒆≥𝜶).

Now we consider the case dege≥α which is more involved as r≥1. We first estimate the variance of each Zj individually as defined in Lemma 14. We condition on the event that edge e is chosen as the i-th edge sample, denoted by ℰi. If HeavyOracle⁢(e,α,ε)=1, then V⁢a⁢r⁢[Zj]=0,∀j∈[r]. Hence, we condition on the event that HeavyOracle⁢(e,α,ε)=0 from now on. As Zj≤dege,

Var[Zj|ℰi]≤𝔼[Zj2|ℰi]≤degei⁢𝔼[Zj|ℰi] (5)

After having bounded the variance of the contribution of each query, we now obtain the variance of the weight estimate of the edge.

Var[w^⁢(ei)|ℰi] =Var[1rei⁢∑j∈reiZj|ℰi]
=1rei2⁢∑j∈reiVar[Zj|ℰi] (Zj are i.i.d. given ℰi)
=degeirei⁢∑j∈rei1rei⁢𝔼[Zj|ℰi] (by Equation (5) and linearity of expectation)
≤α⁢𝔼[w^⁢(ei)|ℰi] (as ⁢rei=⌈degeα⌉) (6)

Now, we remove the conditioning on ℰi using the law of total variance:

Var[w^⁢(ei)] =𝔼ei[Var[w^⁢(ei)|ℰi]]+Varei[𝔼[w^⁢(ei)|ℰi]] (by the law of total variance)
≤𝔼ei[α𝔼[w^(ei)|ℰi]]+𝔼ei[𝔼[w^(ei)|ℰi]2] (by Equations (4) and (6))
≤α⁢𝔼ei[𝔼[w^⁢(ei)|ℰi]]+h⁢αε⋅𝔼ei[𝔼[w^⁢(ei)|ℰi]] (as HeavyOracle⁢(e)=0, h⁢αε≥|Te|)
≤(1+h)⁢αε⋅𝔼[w⁢(e)]

◀

Theorem 16 (Performance guarantees of Algorithm 1 ).

Algorithm 1 makes c⁢(1+h)⁢ε−3⁢(m⁢α/T~)⁢log⁡n queries, and c⁢(1+h)⁢ε−3⁢(m⁢α/T~) log⁡n calls to HeavyOracle, and given T~ satisfying the assumption that T~≤2⁢T, returns T^ such that Pr⁡(|T^−TLl⁢αε|≥ε⁢TLl⁢αε)≤1c⁢log⁡n.

Proof.

The algorithm calls HeavyOracle for each of the s edges in S, resulting in a total of c⁢(1+h)⁢ε−3⁢(log⁡n)⁢(m⁢α/T~) calls.

The algorithm makes s RandomEdge queries, 2⁢s Degree queries, and 2⁢re Neighbour query for each edge e∈S. All edges in S are sampled uniformly at random from E. Hence, the expected number of Neighbour queries made are:

𝔼e∼Unif⁢(E)[⌈degeα⌉]=∑e∈E1m⁢⌈degeα⌉≤1m⁢∑e∈E1+degeα=1+1m⁢∑e∈Edegeα≤1+2⁢m⁢αm⁢α=3

The last inequality in the above step follows from Lemma 5. Hence, the algorithm makes at most 9⁢s=c⁢(1+h)⁢ε−3⁢(m⁢α/T~)⁢log⁡n queries in expectation. Here the inequality is due to the fact that for a heavy edge e in S, re=0. Furthermore, we bound the variance of the estimate T^ as:

Var[T^]=Var[ms⁢∑i∈sw^⁢(ei)]≤(1+h)⁢α⁢m2⁢𝔼[w⁢(e)]ε⁢s≤(1+h)⁢m⁢α⁢𝔼[T^]ε⁢s.

The last two steps follow from Lemma 15 and the fact that 𝔼[T^]=m⁢𝔼[w⁢(e)]. We now use Chebyshev’s inequality on T^:

Pr⁡(|T^−𝔼[T^]|≤ε⁢𝔼[T^]) ≤Var[T^]ε2𝔼[T^]2 (Chebyshev’s inequality)
≤(1+h)⁢m⁢αε3⁢s⁢𝔼[T^] (by Lemma 15)
≤(1+h)⁢m⁢αε3⋅4⁢c⁢(1+h)⁢ε−3⁢(m⁢α/T~)⁢log⁡n⋅TLl⁢αε (by Lemma 14)
≤1c⁢log⁡n (as TLl⁢αε>T/2≥T~/4)

where the last inequality uses the fact T/2≥T~/4 due to the assumption that T~≤2⁢T. ◀

4.3 Implementing the oracle

Rather than the exact oracle (HeavyOracle) that we assumed in Algorithm 1, we would design an oracle (called Heavy) that given arboricity α, and parameters ε and δ, accepts edges participating in at most α2⁢ε triangles as light, and rejects edges participating in at least 2⁢αε triangles as heavy, with probability at least 1−δ. The algorithm works by estimating the number of triangles each edge participates in. However, in this case, each Neighbour and Pair queries generate i.i.d. random variables denoting the existence of triangle through that neighbouring vertex. Thus, our analysis uses the multiplicative Chernoff bound to obtain high probability guarantees for each individual edge.

Algorithm 2 Heavy(e, α, ε, δ).
Lemma 17 (Estimation guarantee of Heavy).

The algorithm Heavy⁢(e,α,ε,δ) satisfies the following properties with probability at least 1−δ: (i) returns 1 edge e if it is 2⁢αε-heavy; (ii) returns 0 edge e if it is α2⁢ε-light.

Proof.

For (i), we only consider edges that have at least 2⁢αε triangles. In this case, the random variables Yi (Yi as in Algorithm 2; Yi=1 if vi and e form a triangle; 0, otherwise) are i.i.d. Bernoulli random variables taking value 1 with probability at least 2⁢αε⁢dege. Hence, we have the following using linearity of expectation: 𝔼[Y]=𝔼[1r⁢∑i∈[r]Yi]=𝔼[Yi]>2⁢αε⁢dege

As Y=1r⁢∑iYi, we can upper bound the probability of the algorithm returning 0 for the edge e, by a multiplicative Chernoff bound (Lemma 7) as follows:

Pr⁡[Y≤αε⁢dege]≤ Pr⁡[Y≤(1−12)⁢𝔼[Y]] (𝔼[Y]>2⁢αε⁢dege)
≤ exp⁡(−r⁢𝔼[Y]12) (by multiplicative Chernoff bound)
≤ exp⁡(−r⁢α6⁢dege⁢ε) (𝔼[Y]>2⁢αε⁢dege)
≤ δ (r=16⁢ε⁢degeα⁢log⁡(1δ))

For (ii), we do not have a lower bound on the probability of success (Yi=1) in general and hence we cannot obtain a lower bound on 𝔼[Y]. Now, observe that for the edges that participate in very few triangles, the probability of finding triangles (i.e., getting Yi=1) is low. However, such light edges can still tolerate a high approximation error to be accepted (as a light edge). To account for the trade-off between the lower bound on the probability of Yi=1 and the upper bound on the approximation factor, we divide the edges participating in at most α2⁢ε triangles into [⌈log⁡(αε)⌉] buckets with each bucket being defined as the set of edges ℬk={e|α2k+1⁢ε≤Te<α2k⁢ε}. For each of these buckets, observe that when Heavy is called for an edge belonging to the bucket, we have Pr⁡[Yi=1]=𝗍𝖾dege≥α2k+1⁢ε⁢dege, and hence 𝔼[Y]=𝔼[Yi]≥α2k+1⁢ε⁢dege.

On the other hand, we have 𝔼[Y]<α2k⁢ε⁢dege, and hence, (1+2k−1)⁢𝔼[Y]<αε⁢dege. Using these observations, we complete the proof by considering any e in these buckets:

Pr⁡[Y≥αε⁢dege]≤ Pr⁡[Y≥(1+2k−1)⁢𝔼[Y]] ((1+2k−1)⁢𝔼[Y]<αε⁢dege)
≤ exp⁡(−22⁢k−2⁢r⁢𝔼[Y]2+2k−1) (by multiplicative Chernoff bound)
≤ exp⁡(−22⁢k⁢r⁢𝔼[Y]2k+3) (k≥1)
≤ exp⁡(−r⁢α16⁢ε⁢dege) (𝔼[Y]>α2k+1⁢ε⁢dege)
≤ δ (r=16⁢ε⁢degeα⁢log⁡(1δ))

◀

Lemma 17 shows that Algorithm 2 can decide whether an edge is heavy or not with probability at least 1−δ using 16⁢ε⁢degeα⁢log⁡(1δ) iterations; making 2 Degree, 1 Neighbour and 1 Pair queries in each iteration. For an individual edge, dege can be at most n−1, and hence the subroutine might contribute to additional queries for each edge. However, as part of Algorithm 1, Heavy is called on a set of edges drawn uniformly at random. Hence, in the following lemma, we bound the expected number of queries made by Heavy when called on edges that were drawn uniformly at random.

Lemma 18 (Query complexity of Heavy).

Heavy⁢(e,α,ε,δ) makes c⁢ε⁢log⁡(1δ) queries in expectation on an edge e∼Unif⁢(E).

Proof.

For edge e, Heavy⁢(e,α,ε,δ) makes ⌈16⁢ε⁢degeα⁢log⁡(1δ)⌉ iterations with each iteration making 4 queries. Hence, the expected number of queries is:

𝔼e∼Unif⁢(E)[4⁢⌈16⁢ε⁢degeα⁢log⁡(1δ)⌉]≤ 64⁢εα⁢log⁡(1δ)⁢𝔼e∼Unif⁢(E)[dege]+4
= 64⁢εα⁢log⁡(1δ)⁢1m⁢∑e∈Edege+4
≤ 64⁢εα⁢log⁡(1δ)⁢1m⁢2⁢m⁢α+4 (by Lemma 5)
≤ 132⁢ε⁢log⁡(1δ) (ε⁢log⁡(1δ)≥1)

◀

4.4 Finalizing the algorithm

In this section, we combine the algorithms discussed above to obtain our final algorithm. Our goal is to call Heavy with appropriate parameters instead of HeavyOracle so that the approximation error due to the heavy triangles not being counted remains small. We also derive the query complexity of the algorithm including the queries made through Heavy.

4.4.1 Algorithm with an estimate 𝑻~

Algorithm 3 Triangle Counting Algorithm - with T~.
Theorem 19 (Performance guarantees of Algorithm 3).

Algorithm 3 makes at most c⁢ε−3⁢(m⁢α/T~)⁢log2⁡n queries in expectation and returns T^ such that Pr⁡[T^∈[(1−ε)⁢T,(1+ε)⁢T]]≥1−1c⁢log⁡n.

Proof.

Algorithm 3 will make the same number of calls to Heavy as did Algorithm 1 to HeavyOracle. By Theorem 16, Algorithm 3 makes c⁢(1+h)⁢ε−3⁢(m⁢α/T~)⁢log⁡n queries and c⁢(1+h)⁢ε−3⁢log⁡(n)(m⁢α/T~) calls to Heavy. By Lemma 18, each call to Heavy requires c⁢ε⁢log⁡n queries in expectation. Combining with the fact that we have h=24, the algorithm requires (c+c⁢ε⁢log⁡n)⁢(ε−3⁢(m⁢α/T~)⁢c⁢log⁡n)≤c⁢ε−3⁢(m⁢α/T~)⁢log2⁡n queries in expectation.

By Lemma 17, we can use Heavy⁢(e,α,ε/6,1m⁢n) as an implementation of the idealized HeavyOracle⁢(e,α,ε). This ensures that a 6⁢αε-light edge is accepted and a 24⁢αε-heavy edge is rejected with probability at least 1−1m⁢n. By union bound, the algorithm accepts all 6⁢αε-light edges and rejects all 24⁢αε-heavy edges in S with probability at least 1−1n. Hence, by Corollary 11 and Lemma 14, we have,

𝔼[T^]=TL6⁢αε∈[(1−ε/2)⁢T,T] (7)

By Theorem 16, we have that:

Pr⁡[T^∈[(1−ε/2)⁢TL6⁢αε,(1+ε/2)⁢TL6⁢αε]]≥1−1c⁢log⁡n (8)

Combining Equations (7) and (8) and using union bound on the event that all oracle calls were executed correctly, for large enough n:

Pr⁡[T^∈[(1−ε)⁢T,(1+ε)⁢T]]≥1−1c⁢log⁡n

◀

4.4.2 Getting rid of the assumption on 𝑻~

In this section, we describe the steps to obtain Theorem 22 from Theorem 19. First, we remove the assumption on the knowledge of T~ for Algorithm 3. To achieve that, we search for an appropriate choice of T~ starting from t¯=n3 and halving it each time we fail to find a T~ satisfying the assumption that T~≤2⁢T. We must also bound the probability of t¯ deviating significantly below T. To ensure that, for each value of t¯, we run Algorithm 3 using values of T~ as n3,n3/2,…,t¯.

Algorithm 4 Triangle Counting Algorithm.

First we bound the probability that the Algorithm 4 terminates at a choice of T~ that does not satisfy the assumption that T~≤2⁢T.

Lemma 20 (Termination bound of Algorithm 4).

When T~>2⁢T, the algorithm terminates with probability at most 1c⁢log2⁡n.

Proof.

By Lemma 14, we have from Markov’s inequality:

Pr⁡[T^>2⁢T]≤𝔼[T^]2⁢T≤12

Now, we have Pr⁡[X≥T~]≤Pr⁡[∩iXi≥T~]≤1c⁢log2⁡n ◀

Lemma 21 (Lower bound of t¯ for Algorithm 4).

The algorithm reaches a value of t¯≤T/2k (k≥1) with probability at most 1(c⁢log⁡n)k.

Proof.

For every such value of t¯, we have a T~ in Line 2 of Algorithm 4 such that T~≤T/2. By Theorem 19, the algorithm returns an estimate Xi≥T/2≥T~ with probability at least 1−1c⁢log⁡n. Taking a union bound over possible values of i∈[2⁢log⁡(c⁢log⁡n)], we have Algorithm 4 returning an X such that X≥T/2≥T~ with probability at least 1−1c⁢log⁡n, and the algorithm terminates.

Hence, to get to a t¯≤T2k, Algorithm 4 must have failed to terminate for all previous values of t¯, which happens with probability at most 1(c⁢log⁡n)k. ◀

Finally we combine Lemmas 20 and 21 to obtain the following theorem quantifying the estimation guarantees and query complexity of Algorithm 4. The following theorem formalizes the Theorem 2 of Section 1.1.

Theorem 22 (Upper bound - Formal).

There exists an algorithm that makes O~⁢(m⁢α⁢log⁡1δε3⁢T) queries in expectation, and returns X∈[(1−ε)⁢T,(1+ε)⁢T] with probability at least 1−δ.

Proof.

The algorithm runs through at most log2⁡n values of T~ such that T~>2⁢T. By Lemma 20, the algorithm terminates in each such case with probability at most 1/c⁢log2⁡n. For each value of t¯≤2⁢T, by Theorem 19, the algorithm returns a wrong value with probability at most 1/c⁢log⁡n. There are at most 3⁢log⁡n such values of t¯. Taking an union bound and fixing the constant c appropriately, the algorithm returns a correct output with probability at least 5/6.

For each t¯ in Line 1 of Algorithm 4, by Theorem 19, the algorithm makes O~⁢((m⁢α/ε3⁢t¯)) queries. Hence, till t¯≤T/2, the algorithm makes O~⁢((m⁢α/ε3⁢T)) queries. Additionally, by Lemma 21, the queries beyond t¯≤T can be bounded as:

∑i∈log⁡(n)1(c⁢log⁡n)k⋅2k⋅O~⁢(m⁢αε3⁢T) =O~⁢(m⁢αε3⁢T)

By the well-known median trick [19], the median of O⁢(log⁡1δ) independent runs of Algorithm 4 establishes the result. ◀

5 Lower bound

In this section, we prove a lower bound that accounts for ε, δ, and the arboricity α of the graph by extending the ideas proposed in [8]. Our lower bound almost matches our proposed upper bound stated in Theorem 22. We first state the problem Popcount Thresholding Problem (referred to as PTP) in the query framework:

Definition 23 (PTPM,k,γ).

Given a string x∈{0,1}M, the problem PTPM,k,γ is to distinguish whether x is generated by i.i.d. samples from 𝒟0 or 𝒟1 defined as follows:

  • ■

    𝓓𝟎 : For all i∈[M], xi is set to 1 with probability (1−2⁢γ)⁢kM, and set to 0, otherwise.

  • ■

    𝓓𝟏 : For all i∈[M], xi is set to 1 with probability (1+2⁢γ)⁢kM, and set to 0, otherwise.

The problem is to decide if x is generated from 𝒟0 or 𝒟1 by querying x at any of its M bits.

We state the following lemma [8] quantifying the query complexity of PTPM,k,γ.

Lemma 24 (PTP Query Lower Bound [8]).

For any γ∈(0,1/4), δ∈(0,1/100), and integers M≥1, log⁡(1/δ)⋅12/γ2≤k≤M/6, Rδ⁢(PTPM,k,γ)≥M⁢log⁡(1/4⁢δ)24⁢γ2⁢k where Rδ⁢(PTPM,k,γ) is the randomized query complexity to decide PTPM,k,γ problem with probability at least 1−δ.

We also state the following lemma, establishing bounds on the ℓ1-norm of x, which was partially proved in [8].

Lemma 25.

In PTPM,k,γ, for any γ∈(0,1/4), δ∈(0,1/100), and integers M≥1, log⁡(1/δ)⋅12/γ2≤k≤M/6, let ‖x‖1 denote the number of 1’s in the string x, then:

  1. (i)

    Pr⁡[‖x‖1>(1−γ)⋅k|x∼𝒟0]≤δ;

  2. (ii)

    Pr⁡[‖x‖1⁢<(1+γ)⋅k|⁢x∼𝒟1]≤δ;

  3. (iii)

    Pr⁡[‖x‖1<(1−4⁢γ)⋅k]≤δ;

In [8], (i) and (ii) have been shown using Chernoff bound. (iii) can also be shown by using Chernoff bound. We combine two results to obtain the result. First we state the lemma due to [8]:

Lemma 26 ([8]).

In PTPM,k,γ, for any γ∈(0,1/4), δ∈(0,1/100), and integers M≥1, log⁡(1/δ)⋅12/γ2≤k≤M/6,

  1. (i)

    Pr⁡[‖x‖1>(1−γ)⋅k|x∼𝒟0]≤δ;

  2. (ii)

    Pr⁡[‖x‖1⁢<(1+γ)⋅k|⁢x∼𝒟1]≤δ

where ‖x‖1 denotes the number of 1’s in the string x.

We introduce another lemma to lower bound the ℓ1 norm of x for 𝒟0.

Lemma 27.

In PTPM,k,γ, for any γ∈(0,1/4), δ∈(0,1/100), and integers M≥1, log⁡(1/δ)⋅12/γ2≤k≤M/6, Pr⁡[‖x‖1⁢<(1−4⁢γ)⋅k|⁢x∼𝒟0]≤δ

Proof.

By definition of 𝒟0 and linearity of expectations, we have:

𝔼[‖x‖1]=∑i∈[M]𝔼[xi]=(1−2⁢γ)⁢k

Now, given the independence of each xi, we can use Chernoff bound (Lemma 7) to obtain:

Pr⁡[‖x‖1<(1−4⁢γ)⁢k]
= Pr⁡[‖x‖1−𝔼[‖x‖1]>2⁢γ1−2⁢γ⁢𝔼[‖x‖1]]
≤ exp⁡(−4⁢γ2⁢𝔼[‖x‖1]3⁢(1−2⁢γ)2) (by Chernoff bound)
≤ exp⁡(−48⁢γ2⁢log⁡(1/δ)3⁢γ2⁢(1−2⁢γ)) (𝔼[‖x‖1]=(1−2⁢γ)⁢k,k≥log⁡(1/δ)⋅12/γ2)
≤ δ (γ<1/4)

◀

Combining Lemma 26 and 27, we obtain the desired result.

Figure 1: Lower Bound Graph Construction.

The following theorem formalizes the Theorem 3 of Section 1.1.

Theorem 28 (Lower bound - Formal).

Any algorithm that solves triangle estimation problem with ε≤18 using Degree, Neighbour, Pair and RandomEdge for any graph with m edges, T triangles, and arboricity α such that T=Ω⁢(α⁢log⁡(1/δ)ε2) requires Ω⁢(m⁢α⁢log⁡(1/δ)ε2⁢T) queries.

Proof.

We want to show that given a graph G, it takes Ω⁢(m⁢α⁢log⁡(1/δ)ε2⁢T) queries to obtain an estimate T~ such that T~∈(1±ε)⁢T with probability at least 1−δ. For a contradiction, let us assume that there exists an algorithm 𝒜T that, for some arboricity α, computes an estimate T~ such that T~∈(1±ε)⁢T with probability at least 1−δ using o⁢(m⁢α⁢log⁡(1/δ)ε2⁢T) queries.

To show the contradiction, we design an algorithm that solves PTPM,k,γ in less than M⁢log⁡(1/4⁢δ)24⁢γ2⁢k queries using 𝒜T. Given an instance of x generated from PTPM,k,γ, we consider a graph Gx=(Vx,Ex) defined as:

The vertex set 𝑽𝒙.

The vertex set Vx consists of 5 sets of disjoint and independent set of vertices A,A′,B, B′, and R, with |A|=|A′|=|B|=|B′|=M/α, and |R|=α. Vertices of A, A′, B and B′ will be named as a, a′, b and b′, respectively.

The edge set 𝑬𝒙.

There exists an edge between every vertex in A∪B to every vertex in R. Observe that this makes sure that the arboricity of Gx is at least the average degree of the subgraph induced by A∪B∪R, i.e., Ω⁢(α). If a bit of x is 1 (resp. 0), there will be an edge from a vertex in A (resp. A) to a vertex in B (resp. A′), and an edge from a vertex in A′ (resp. B) to a vertex in B′ (resp. B′).

We index the problem instance x of length M as [Mα]×[α], denoting x(i−1)×α+j as xi,j, where i∈[Mα] and j∈[α]. We add an edge (ai,ai+j′), and an edge (bi,bi+j′) if xi,j=0. We add an edge (ai,bi+j), and an edge (ai′,bi+j′) if xi,j=1. All (i+j) additions here are modulo [Mα].

Consider the orientation of edges such that all edges from R is oriented outwards, and other edges are oriented arbitrarily. This gives a DAG with the out-degree of each edge being bounded by 2⁢α. As a DAG with out-degree at most α ensures that the arboricity of the graph Gx is at most α[28, 47, 21], the graph has arboricity at most 2⁢α. Hence, the arboricity of Gx is Θ⁢(α), as we have already shown it to be Ω⁢(α).

From the construction, observe that the number of edges between A and B is ‖x‖1. Moreover, each edge between A and B adds α triangles. Hence, the number of triangles in Gx is exactly ‖x‖1⁢α. Also note that we have added 2⁢M edges between A∪B and R, and further 2⁢M edges (in the subgraph induced by Vx∖S) according to the entries of x, 2 for each bit xi. Hence, we have m=4⁢M, and we fix ε=γ.

We now describe 𝒜TPTP an algorithm that uses 𝒜T to solve PTPM,k,γ using less than M⁢log⁡(1/4⁢δ)24⁢γ2⁢k queries. Given a string x, we generate Gx and estimate the number of triangles T^ by calling 𝒜T using m⁢log⁡(1/4⁢δ)200⁢ε2⁢k=M⁢log⁡(1/4⁢δ)50⁢γ2⁢k queries. If T^<(1−γ2)⁢k⁢α, it outputs x∼𝒟0; otherwise, it outputs x∼𝒟1. Also, observe that by Lemma 25, we have T=α⁢‖x‖1≥α⁢(1−4⁢γ)⁢k≥α⁢k2 with probability at least 1−δ, where the last inequality follows from the fact that γ=ε≤14. Lemma 25 is applicable due to the fact that T=Ω⁢(α⁢log⁡(1/δ)ε2). Hence, we have m⁢log⁡(1/4⁢δ)200⁢ε2⁢k≥m⁢α⁢log⁡(1/4⁢δ)200⁢ε2⁢T. Thus, 𝒜T is allowed to make o⁢(m⁢α⁢log⁡(1/δ)ε2⁢T) queries under the given query bound.

By Lemma 25, to distinguish between whether x is generated from 𝒟0 or 𝒟1 with probability at least 1−δ, it suffices to show that we can use 𝒜T to distinguish between the instance where ‖x‖1>(1+γ)⁢k and the instance where ‖x‖1<(1−γ)⁢k instance with probability at least 1−δ2. We now show that 𝒜TPTP outputs 𝒟1 with probability at least 1−δ2 given ‖x‖1>(1+γ)⁢k, and outputs 𝒟0 with probability at least 1−δ2 given ‖x‖1<(1−γ)⁢k. We consider the two cases separately:

Case I: (‖𝒙‖𝟏>(𝟏+𝜸)⁢𝒌).

Our construction ensures that the number of triangles in Gx is T=‖x‖1⁢α>(1+γ)⁢k⁢α=(1+ε)⁢k⁢α. Additionally, by our assumption on 𝒜T, it outputs an estimate T^≥(1−ε)⁢T with probability 1−δ2. Thus, we have T~≥(1−ε2)⁢k⁢α with probability at least 1−δ2.

Case II: (‖𝒙‖𝟏<(𝟏−𝜸)⁢𝒌).

Our construction ensures that the number of triangles in Gx is T=‖x‖1⁢α<(1−γ)⁢k⁢α=(1−ε)⁢k⁢α. Additionally, by our assumption on 𝒜T, it outputs an estimate T^≤(1+ε)⁢T with probability 1−δ2. Thus, we have T~≤(1−ε2)⁢k⁢α with probability at least 1−δ2.

Now we state how to simulate the required queries used by the algorithm:

  • ■

    Degree⁢(𝒗): For a vertex v∈A∪B∪A′∪B′, return α, and for a vertex v∈R, return 2⁢Mα. Hence, for Degree queries, no queries are made to the string.

  • ■

    Neighbour⁢(𝒗,𝒊): For a vertex v∈A∪B∪A′∪B′, w.l.o.g assume v to be aj∈A. Return ai+j′ if xi,j=0, and bi+j otherwise. For a vertex v∈R, if i≤mα, return ai, else return bi−mα. Hence, for Neighbour queries, a single query is made to the string.

  • ■

    Pair(u,v): Given a vertex pair (v,u), there can be 3 cases: (a) If the vertex v∈A∪B, w.l.o.g assume v to be ai∈A, if u∈R, return 1, else if u=bj∈B and xi,j−i=1, return 1, else if u=aj′∈A′ and xi,j−i=0, return 1, else return 0. (b) If a vertex v∈A′∪B′, w.l.o.g assume the v to be ai′∈A′, if u=aj∈A, return 1 if xj,i−j=0, else if u=bj′∈B′, return 1 if xj,i−j=1, else return 0. If v∈R, return 1 if u∈A∪B, else return 0. (c) If a vertex v∈R, return 1 if u∈A∪B, return 0 otherwise. Hence, for Pair queries, a single query is made to the string.

  • ■

    RandomEdge: Sample a vertex v with probability degv4⁢M. Choose i∈deg(v) uniformly at random, query u=Neighbour⁢(v,i) and return (v,u). Hence, for RandomEdge queries, a single query is made to the string for the Neighbour query.

◀

The following corollary is a direct implication from Theorem 28 due to the fact that we consider a weaker model (without access to RandomEdge queries) compared to Theorem 28.

Corollary 29 (Lower Bound for Local Queries).

Any algorithm that solves triangle estimation problem with ε≤14 using Degree, Neighbour, and Pair requires Ω⁢(m⁢α⁢log⁡(1/δ)ε2⁢T) queries.

6 Conclusion

In this paper, we present an almost optimal algorithm for triangle counting in graphs of bounded arboricity, assuming access to both local queries and RandomEdge queries. In particular, the query complexity of our algorithm is O⁢(m⁢α/T).333In this section, we suppress the dependence on polylogarithmic factors, for simplicity of presentation. Extending our result to clique counting remains an interesting open question. Eden et al. [28] showed that the number of k-cliques can be estimated using O⁢(n/Tk1/k+mk/2/Tk) local queries, where Tk denotes the number of k-cliques in the graph. When RandomEdge queries are also available, Assadi et al. [7] established a bound of O⁢(mk/2/Tk). For graphs with arboricity bounded by α, Eden et al. [28] showed that O⁢(n/Tk1/k+m⁢αk−2/Tk) local queries suffice. We believe that, when RandomEdge queries are available in addition to local queries, the bound can be improved to O⁢(m⁢αk−2/Tk). However, establishing the complexity of clique counting (when RandomEdge is available along with local queries) remains an open question. A similar open question was posed in the streaming model by Bera and Seshadri [13].

References

  • [1] Charu Aggarwal and Karthik Subbian. Evolutionary network analysis: A survey. ACM Comput. Surv., 47(1), May 2014. doi:10.1145/2601412.
  • [2] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’12, pages 5–14, New York, NY, USA, 2012. Association for Computing Machinery. doi:10.1145/2213556.2213560.
  • [3] Mohammad Al Hasan and Vachik S. Dave. Triangle counting in large networks: a review. WIREs Data Mining and Knowledge Discovery, 8(2):e1226, 2018. doi:10.1002/widm.1226.
  • [4] N. Alon. Testing Subgraphs in Large Graphs. In IEEE 54th Annual Symposium on Foundations of Computer Science, page 434, Los Alamitos, CA, USA, October 2013. IEEE Computer Society. doi:10.1109/SFCS.2001.959918.
  • [5] Noga Alon, Tali Kaufman, Michael Krivelevich, and Dana Ron. Testing triangle-freeness in general graphs. SIAM J. Discret. Math., 22(2):786–819, 2008. doi:10.1137/07067917X.
  • [6] Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209–223, 1997. doi:10.1007/BF02523189.
  • [7] Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:20, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2019.6.
  • [8] Sepehr Assadi and Hoai-An Nguyen. Asymptotically optimal bounds for estimating h-index in sublinear time with applications to subgraph counting. In Amit Chakrabarti and Chaitanya Swamy, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference), volume 245 of LIPIcs, pages 48:1–48:20, Illinois, Urbana-Champaign, USA (Virtual Conference), 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.48.
  • [9] Albert Atserias, Martin Grohe, and Dániel Marx. Size bounds and query plans for relational joins. SIAM Journal on Computing, 42(4):1737–1767, 2013. doi:10.1137/110859440.
  • [10] Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with an application to counting triangles in graphs. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’02, pages 623–632, USA, 2002. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=545381.545464.
  • [11] Suman K. Bera and Amit Chakrabarti. Towards tighter space bounds for counting triangles and other substructures in graph streams. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 11:1–11:14, Hannover, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.STACS.2017.11.
  • [12] Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:21, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2020.11.
  • [13] Suman K. Bera and C. Seshadhri. How the degeneracy helps for triangle counting in graph streams. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS’20, pages 457–467, New York, NY, USA, 2020. Association for Computing Machinery. doi:10.1145/3375395.3387665.
  • [14] Lorenzo Beretta and Jakub Tětek. Better sum estimation via weighted sampling. ACM Trans. Algorithms, 20(3), June 2024. doi:10.1145/3650030.
  • [15] Eric Blais, Joshua Brody, and Kevin Matulef. Property testing lower bounds via communication complexity. computational complexity, 21(2):311–358, May 2012. doi:10.1007/s00037-012-0040-x.
  • [16] Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? In 40th International Colloquium on Automata, Languages, and Programming (ICALP 2013), ICALP’13, pages 244–254, Berlin, Heidelberg, 2013. Springer-Verlag. doi:10.1007/978-3-642-39206-1_21.
  • [17] Laurent Bulteau, Vincent Froese, Konstantin Kutzkov, and Rasmus Pagh. Triangle counting in dynamic graph streams. Algorithmica, 76(1):259–278, September 2016. doi:10.1007/s00453-015-0036-4.
  • [18] Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler. Counting triangles in data streams. In Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS ’06, pages 253–262, New York, NY, USA, 2006. Association for Computing Machinery. doi:10.1145/1142351.1142388.
  • [19] Amit Chakrabarti. Data stream algorithms. Computer Science, 49:149, 2015.
  • [20] Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM J. Comput., 14(1):210–223, 1985. doi:10.1137/0214017.
  • [21] Marek Chrobak and David Eppstein. Planar orientations with low out-degree and compaction of adjacency matrices. Theoretical Computer Science, 86(2):243–266, 1991. doi:10.1016/0304-3975(91)90020-3.
  • [22] Graham Cormode and Hossein Jowhari. A second look at counting triangles in graph streams (corrected). Theoretical Computer Science, 683:22–30, 2017. doi:10.1016/j.tcs.2016.06.020.
  • [23] Maximilien Danisch, Oana Balalau, and Mauro Sozio. Listing k-cliques in sparse real-world graphs*. In Proceedings of the 2018 World Wide Web Conference, WWW ’18, pages 589–598, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee. doi:10.1145/3178876.3186125.
  • [24] Michal Dory, Mohsen Ghaffari, and Saeed Ilchi. Near-optimal distributed dominating set in bounded arboricity graphs. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, pages 292–300, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519270.3538437.
  • [25] Jean-Pierre Eckmann and Elisha Moses. Curvature of co-links uncovers hidden thematic layers in the world wide web. Proceedings of the National Academy of Sciences of the United States of America, 99:5825–5829, 2001. URL: https://api.semanticscholar.org/CorpusID:2618949.
  • [26] Talya Eden, Amit Levi, Dana Ron, and C. Seshadhri. Approximately counting triangles in sublinear time. SIAM Journal on Computing, 46(5):1603–1646, 2017. doi:10.1137/15M1054389.
  • [27] Talya Eden, Dana Ron, and C. Seshadhri. On approximating the number of k-cliques in sublinear time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 722–734, New York, NY, USA, 2018. Association for Computing Machinery. doi:10.1145/3188745.3188810.
  • [28] Talya Eden, Dana Ron, and C. Seshadhri. Faster sublinear approximation of the number of k-cliques in low-arboricity graphs. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, pages 1467–1478, USA, 2020. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611975994.89.
  • [29] Talya Eden and Will Rosenbaum. Lower Bounds for Approximating Graph Parameters via Communication Complexity. In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:18, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX-RANDOM.2018.11.
  • [30] Irene Finocchi, Marco Finocchi, and Emanuele G. Fusco. Clique counting in mapreduce: Algorithms and experiments. ACM J. Exp. Algorithmics, 20, October 2015. doi:10.1145/2794080.
  • [31] Gaurav Goel and Jens Gustedt. Bounded arboricity to determine the local structure of sparse graphs. In Proceedings of the 32nd International Conference on Graph-Theoretic Concepts in Computer Science, WG’06, pages 159–167, Berlin, Heidelberg, 2006. Springer-Verlag. doi:10.1007/11917496_15.
  • [32] Oded Goldreich. On the communication complexity methodology for proving lower bounds on the query complexity of property testing, pages 87–118. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag, Germany, April 2020. doi:10.1007/978-3-030-43662-9_7.
  • [33] Mira Gonen, Dana Ron, and Yuval Shavitt. Counting stars and other small subgraphs in sublinear-time. SIAM Journal on Discrete Mathematics, 25(3):1365–1411, 2011. doi:10.1137/100783066.
  • [34] Shweta Jain and C. Seshadhri. A fast and provable method for estimating clique counts using turán’s theorem. In Proceedings of the 26th International Conference on World Wide Web, WWW ’17, pages 441–449, Republic and Canton of Geneva, CHE, 2017. International World Wide Web Conferences Steering Committee. doi:10.1145/3038912.3052636.
  • [35] Rajesh Jayaram and John Kallaugher. An Optimal Algorithm for Triangle Counting in the Stream. In APPROX/RANDOM 2021, volume 207 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:11, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.11.
  • [36] Madhav Jha, C. Seshadhri, and Ali Pinar. A space-efficient streaming algorithm for estimating transitivity and triangle counts using the birthday paradox. ACM Trans. Knowl. Discov. Data, 9(3), February 2015. doi:10.1145/2700395.
  • [37] John Kallaugher, Michael Kapralov, and Eric Price. The sketching complexity of graph and hypergraph counting. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 556–567. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00059.
  • [38] John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The complexity of counting cycles in the adjacency list streaming model. In Dan Suciu, Sebastian Skritek, and Christoph Koch, editors, Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019, pages 119–133. ACM, 2019. doi:10.1145/3294052.3319706.
  • [39] John Kallaugher and Eric Price. A hybrid sampling scheme for triangle counting. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’17, pages 1778–1797, USA, 2017. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974782.116.
  • [40] John Kallaugher and Eric Price. Separations and equivalences between turnstile streaming and linear sketching. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1223–1236. ACM, 2020. doi:10.1145/3357713.3384278.
  • [41] Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun. Counting arbitrary subgraphs in data streams. In Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming - Volume Part II, ICALP’12, pages 598–609, Berlin, Heidelberg, 2012. Springer-Verlag. doi:10.1007/978-3-642-31585-5_53.
  • [42] Christian Konrad, Andrew McGregor, Rik Sengupta, and Cuong Than. Matchings in Low-Arboricity Graphs in the Dynamic Graph Stream Model. In Siddharth Barman and Sławomir Lasota, editors, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024), volume 323 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:15, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.FSTTCS.2024.29.
  • [43] Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’16, pages 1272–1287, USA, 2016. Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611974331.CH89.
  • [44] Jure Leskovec, Lars Backstrom, Ravi Kumar, and Andrew Tomkins. Microscopic evolution of social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, pages 462–470, New York, NY, USA, 2008. Association for Computing Machinery. doi:10.1145/1401890.1401948.
  • [45] Quanquan C. Liu and C. Seshadhri. Brief announcement: Improved massively parallel triangle counting in o(1) rounds. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC ’24, pages 519–522, New York, NY, USA, 2024. Association for Computing Machinery. doi:10.1145/3662158.3662819.
  • [46] Duncan Luce and Albert D. Perry. A method of matrix analysis of group structure. Psychometrika, 14:95–116, 1949. URL: https://api.semanticscholar.org/CorpusID:16186758.
  • [47] David W. Matula and Leland L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417–427, July 1983. doi:10.1145/2402.322385.
  • [48] Andrew McGregor, Sofya Vorotnikova, and Hoa T. Vu. Better algorithms for counting triangles in data streams. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’16, pages 401–411, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2902251.2902283.
  • [49] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge, 2005. doi:10.1017/CBO9780511813603.
  • [50] Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic mis in uniformly sparse graphs. ACM Trans. Algorithms, 16(2), March 2020. doi:10.1145/3378025.
  • [51] Rasmus Pagh and Charalampos E. Tsourakakis. Colorful triangle counting and a mapreduce implementation. Inf. Process. Lett., 112(7):277–281, 2012. doi:10.1016/J.IPL.2011.12.007.
  • [52] A. Pavan, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Counting and sampling triangles from a graph stream. Proc. VLDB Endow., 6(14):1870–1881, 2013. doi:10.14778/2556549.2556569.
  • [53] Thomas Schank and Dorothea Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Sotiris E. Nikoletseas, editor, Experimental and Efficient Algorithms, pages 606–609, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/11427186_54.
  • [54] Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. Patterns and anomalies in k-cores of real-world graphs with applications. Knowl. Inf. Syst., 54(3):677–710, March 2018. doi:10.1007/s10115-017-1077-6.
  • [55] Kijung Shin, Sejoon Oh, Jisu Kim, Bryan Hooi, and Christos Faloutsos. Fast, accurate and provable triangle counting in fully dynamic graph streams. ACM Trans. Knowl. Discov. Data, 14(2), February 2020. doi:10.1145/3375392.
  • [56] Siddharth Suri and Sergei Vassilvitskii. Counting triangles and the curse of the last reducer. In Proceedings of the 20th International Conference on World Wide Web, WWW ’11, pages 607–614, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1963405.1963491.
  • [57] Charalampos Tsourakakis, Mihail Kolountzakis, and Gary Miller. Triangle sparsifiers. Journal of Graph Algorithms and Applications, 15(6):703–726, October 2011. doi:10.7155/jgaa.00245.
  • [58] Jakub Tětek. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 107:1–107:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2022.107.
  • [59] Virginia Vassilevska Williams and Yinzhan Xu. Monochromatic triangles, triangle listing and APSP. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 786–797, Durham,NC,USA, 2020. IEEE. doi:10.1109/FOCS46700.2020.00078.
  • [60] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442, 1998. doi:10.1038/30918.