Laurent Bulteau
email: l.bulteau@gmail.com

Vincent Froese
email: vincent.froese@tu-berlin.de

Konstantin Kutzkov

Rasmus Pagh

Triangle Counting in Dynamic Graph Streams

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

Many relationships between real life objects can be abstractly represented as graphs. The discovery of certain structural properties in a graph, which abstractly describes a given real-life problem, can often provide important insights into the nature of the original problem. The number of triangles, and the closely related clustering and transitivity coefficients, have proved to be an important measure used in applications ranging from social network analysis and spam detection to motif detection in protein interaction networks. We refer to [START_REF] Tsourakakis | Triangle Sparsifiers[END_REF] for a detailed discussion on the applications of triangle counting.

The best known algorithm for triangle counting in the RAM model runs in time O(m 2ω ω+1 ) [START_REF] Alon | Finding and Counting Given Length Cycles[END_REF] where ω is the matrix multiplication exponent, the best known bound is ω = 2.3727 [START_REF] Williams | Multiplying matrices faster than Coppersmith-Winograd[END_REF]. However, this algorithm is mainly of theoretical importance since exact fast matrix multiplication algorithms do not admit an efficient implementation for input matrices of reasonable size.

The last decade has witnessed a rapid growth of available data. This has led to a shift in attitudes in algorithmic research and solutions storing the whole input in main memory are not any more considered a feasible choice for many real-life problems. Classical algorithms have been adjusted in order to cope with the new requirements and many new techniques have been developed. This has led to the streaming model of computation where only a single scan of the data is possible. Both efficient algorithms and impossibility results have shed light on the computational complexity of many problems in the model [START_REF] Muthukrishnan | Data Streams: Algorithms and Applications[END_REF].

Approximate triangle counting in streamed graphs. For many applications one is satisfied with a good approximation of the number of triangles instead of their exact number, thus researchers have designed randomized approximation algorithms returning with high probability a precise estimate using only small amount of main memory. Two models of streamed graphs have been considered in the literature. In the incidence list stream model the edges incident to each vertex arrive consecutively and in the adjacency stream model edges arrive in arbitrary order. Also, a distinction has been made between algorithms using only a single pass over the input, and algorithms assuming that the input graph can be persistently stored on a secondary device and multiple passes are allowed. A simple approach for estimating the number of triangles in insert-only streams is to sample a certain number of 2-paths, then compute the ratio of 2-paths in the sample that are completed to triangles and multiply the obtained number with the total number of 2-paths in the graphs. For incidence list streams this is easy since we can assume that the stream consists of (an implicit representation of) all 2-paths [START_REF] Buriol | Counting triangles in data streams[END_REF]. For the more difficult model of adjacency streams where edges arrive in arbitrary order the approach was adjusted such that we sample a random 2-path [START_REF] Jha | A space efficient streaming algorithm for triangle counting using the birthday paradox[END_REF][START_REF] Pavan | Counting and Sampling Triangles from a Graph Stream[END_REF]. The one-pass algorithm with the best known space complexity and constant processing time per edge for adjacency streams is due to Pavan et al. [START_REF] Pavan | Counting and Sampling Triangles from a Graph Stream[END_REF], and when several passes are allowed -by Kolountzakis et al. [START_REF] Kolountzakis | Efficient Triangle Counting in Large Graphs via Degree-based Vertex Partitioning[END_REF]. For a more detailed overview of results and developed techniques we refer to [START_REF] Tsourakakis | Triangle Sparsifiers[END_REF]. Dynamic graph streams have a wider range of applications. Consider for example a social network like Facebook where one is allowed to befriend and "unfriend" other members, or join and leave groups of interest. Estimating the number of triangles in a network is a main building block in algorithms for the detection of emerging communities [START_REF] Berry | Tolerating the Community Detection Resolution Limit with Edge Weighting[END_REF], and thus it is required that triangle counting algorithms can also handle edge deletions. The problem of designing triangle counting algorithms for dynamic streams matching the space and time complexity of algorithms for insert-only streams has been presented as an open question in the 2006 IITK Workshop on Algorithms for Data Streams [START_REF] Leonardi | List of Open Problems in Sublinear Algorithms: Problem 11[END_REF]. The best known algorithms for insert-only streams work by sampling a non-empty subgraph on three vertices from the stream (e.g. an edge (u, v) and a vertex w). Then one checks whether the arriving edges will complete the sampled subgraph to a triangle (we look for (u, w) and (v, w)). The approach does not work for dynamic streams because an edge in the sampled subgraph might be deleted later. Proposed solutions [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF][START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF][START_REF] Jowhari | New Streaming Algorithms for Counting Triangles in Graphs[END_REF] have explored different ideas. These approaches, however, only partially resolve the open problem from [START_REF] Leonardi | List of Open Problems in Sublinear Algorithms: Problem 11[END_REF] because of high processing time per edge update, see Section 3 for more details.

Our contribution. In this work we propose a method to adjust sampling to work in dynamic streams and show that for graphs with constant transitivity coefficient, a ubiquitous assumption for real-life graphs, we can achieve constant processing time per edge. We also show that some assumption on the graph is needed to be able to estimate small triangle counts, by showing a lower bound on the space usage in terms of the number of edges and triangles, matching the upper bound of Manjunath et al. [START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF] for constant approximation factor.

At a very high level, the main technical contribution of the present work can be summarized as follows: For dynamic graph streams sampling-based approaches fail because we don't know how many of the sampled subgraphs will survive after edges have been deleted. On the other hand, graph sparsification approaches [START_REF] Pagh | Colorful triangle counting and a MapReduce implementation[END_REF][START_REF] Tsourakakis | DOULION: counting triangles in massive graphs with a coin[END_REF][START_REF] Tsourakakis | Triangle Sparsifiers[END_REF] can handle edge deletions but the theoretical guarantees on the complexity of the algorithms depend on specific properties of the underlying graph, e.g., the maximum number of triangles an edge is part of. The main contribution in the present work is a novel technique for sampling 2-paths after the stream has been processed. It is based on the combination of standard 2-path sampling with graph sparsification. The main technical challenge is to show that sampling at random a 2-path in a sparsified graph is (almost) equivalent to sampling at random a 2-path in the original graph. In the course of the analysis, we also obtain combinatorial results about general graphs that might be of independent interest.

Preliminaries

Notation. A simple undirected graph without loops is denoted as G = (V, E) with V = {1, 2, . . . , n} being a set of vertices and E a set of edges. The edges are provided as a stream of insertions and deletions in arbitrary order. We assume the strict turnstile model where each edge can be deleted only after being inserted. We assume that n is known in advance1 and that the number of edges cannot exceed m. For an edge connecting the vertices u and v we write (u, v) and u and v are the endpoints of the edge (u, v). Vertex u is neighbor of v and vice versa and N (u) is the set of u's neighbors. We say that edge (u, v) is isolated if |N (u)| = |N (v)| = 1. We consider only edges (u, v) with u < v. A 2-path centered at v, (u, v, w), consists of the edges (u, v) and (v, w). A k-clique in G is a subgraph of G on k vertices v 1 , . . . , v k such that (v i , v j ) ∈ E for all 1 ≤ i < j ≤ k. A 3-clique on u, v, w is called a triangle on u, v, w, and is denoted as u, v, w . We denote by P 2 (v) the number of 2-paths centered at a vertex v, and P 2 (G) = v∈V P 2 (v) and T 3 (G) the number of 2-paths and number of triangles in G, respectively. We will omit G when clear from the context.

We say that two 2-paths are independent if they have at most one common vertex. The transitivity coefficient of G is

α(G) = 3T 3 v∈V dv 2 = 3T 3 P 2 ,
i.e., the ratio of 2-paths in G contained in a triangle to all 2-paths in G. When clear from the context, we will omit G.

Hashing. A family F of functions from U to a finite set S is k-wise independent if for a function f : U → S chosen uniformly at random from F it holds

Pr[f (u 1 ) = c 1 ∧ f (u 2 ) = c 2 ∧ • • • ∧ f (u k ) = c k ] = 1/s k
for s = |S|, distinct u i ∈ U and any c i ∈ S and k ∈ N. We will call a function chosen uniformly at random from a k-wise independent family k-wise independent function and a function f : U → S fully random if f is |U |-wise independent. We will say that a function f : U → S behaves like a fully random function if for any set of input from U , with high probability f has the same probability distribution as a fully random function.

We will say that an algorithm returns an (ε, δ)-approximation of some quantity q if it returns a value q such that (1 -ε)q ≤ q ≤ (1 + ε)q with probability at least 1 -δ for every 0 < ε, δ < 1.

Probability inequalities. In the analysis of the algorithm we use the following inequalities.

• Chebyshev's inequality. Let X be a random variable and λ > 0. Then

Pr[|X -E[X]| ≥ λσ(X)] ≤ 1 λ 2
• Chernoff 's inequality. Let X 1 , . . . , X be independent identically distributed Bernoulli random variables and E[X i ] = µ. Then for any ε > 0 we have

Pr[| 1 i=1 X i -µ| > εµ] ≤ 2e -ε 2 µ /2

Results

The following theorem is our main result.

Space

Update time Ahn et al. [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF] O( mn

ε 2 T3 1 log 1 δ ) O(n log n) Manjunath et al. [18] O( m 3 ε 2 T 2 3 log 1 δ ) O( m 3 ε 2 T 2 3 log 1 δ ) Section 5 Ω( m 3 T 2 3 ) - Section 4 O( √ m ε 3 α log 1 δ ) O( 1 ε 2 α log 1 δ )
Table 1: Overview of time and space bounds.

n log n m 3 /T 2 3 z < 1/2 T 3 = ω(C 2 /(n 2z log n)) T 3 = o(Cn 2-z ) 1/2 < z < 1 T 3 = ω(C 2 /(n log n)) T 3 = o(Cn 3-3z ) z > 1 T 3 = ω(C 2 /(n log n)) T 3 = o(C)
Table 2: Comparison of the theoretical guarantees for the per edge processing time for varying z.

Theorem 1 Let G = (V, E) be a graph given as a stream of edge insertions and deletions with no isolated edges and vertices, V = {1, 2, . . . , n} and |E| ≤ m. Let P 2 , T 3 and α be the number of 2-paths, number of triangles and the transitivity coefficient of G, respectively. Let ε, δ ∈ (0, 1) be user defined. Assuming fully random hash functions, there exists a one-pass algorithm running in expected space O(

√ m ε 3 α log 1 δ ) and O( 1 ε 2 α log 1 δ )
processing time per edge. After processing the stream, an (ε, δ)-approximation of T 3 can be computed in expected time O( log n ε 2 α log 1 δ ) and worst case time O( log 2 n ε 2 α log 1 δ ) with high probability. (For simplicity, we assume that there are no isolated edges in G. More generally, the result holds by replacing n with n C , where n C is the number of vertices in connected components with at least two edges. We assume m and n can be described in O(1) words.)

Before presenting the algorithm, let us compare the above to the bounds in [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF][START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF]. The algorithm in [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF] estimates T 3 by applying 0 sampling [START_REF] Frahling | Sampling in dynamic data streams and applications[END_REF] to non-empty subgraphs on 3 vertices. There are O(mn) such subgraphs, thus O( mn ε 2 T3 log 1 δ ) samples are needed for an (ε, δ)-approximation. However, each edge insertion or deletion results in the update of n -2 non-empty subgraphs on 3 vertices. Using the 0 sampling algorithm from [START_REF] Jowhari | Tight bounds for Lp samplers, finding duplicates in streams, and related problems[END_REF], this results in processing time of O(n log n) per edge. The algorithm by Manjunath et al. [START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF] (which builds upon the the work of Jowhari and Ghodsi [START_REF] Jowhari | New Streaming Algorithms for Counting Triangles in Graphs[END_REF]) estimates the number of triangles (and more generally of cycles of fixed length) in streamed graphs by computing complex valued sketches of the stream. Each of them yields an unbiased estimator of T 3 . The average of O( m 3

ε 2 T 2 3 log 1
δ ) estimators is an (ε, δ)-approximation of T 3 . However, each new edge insertion or deletion has to update all estimators, resulting in update time of O( m 3 ε 2 T 2 3 log 1 δ ). The algorithm was generalized to counting arbitrary subgraphs of fixed size in [START_REF] Kane | Counting Arbitrary Subgraphs in Data Streams[END_REF].

The time and space bounds are summarized in Table 1. Comparing our space complexity to the bounds in [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF][START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF], we see that for several graph classes our algorithm is more time and space efficient. (We ignore ε and δ and logarithmic factors in n for the space complexity.) For d-regular graphs the processing time per edge is better than

O(n log n) for T 3 = ω(d 2 / log n), and better than O(m 3 /T 2 3 ) for T 3 = o(n 2 d).
Our space bound is better than O(mn/T 3 ) when d = o(n 1/3 ), and better than O(m 3 /T 2 3 ) for

T 3 = o(n 3/2 d 1/2
). Most real-life graphs exhibit a skewed degree distribution adhering to some form of power law, see for example [START_REF] Aiello | A random graph model for massive graphs[END_REF]. Assume vertices are sorted according to their degree in decreasing order such that the ith vertex has degree C/i z for some C ≤ n, and constant z > 0, i.e., we have Zipfian distribution with parameter z. It holds 2 summarizes for which values of T 3 our algorithm achieves faster processing time than [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF][START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF], and Table 3 -for which values of C our algorithm is more space-efficient than [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF], and for which values of T 3 -more space-efficient than [START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF].

n i=1 i -z = O(n 1-z ) for z < 1 and n i=1 i -z = O(1) for z > 1. Table
mn/T 3 m 3 /T 2 3 z < 1/2 C = o(n 1/3+z ) T 3 = o(C 1/2 n 3-z 2 )) 1/2 < z < 1 C = o(n 1-z/3 ) T 3 = o(C 1/2 n 5-5z 2 ) z > 1 C = o(n 2/3 ) T 3 = o(C 1/2 )
Table 3: Comparison of the theoretical guarantees for the space usage for varying z.

However, the above values are for arbitrary graphs adhering to a certain degree distribution. We consider the main advantage of the new algorithm to be that it achieves constant processing time per edge for graphs with constant transitivity coefficient. This is a common assumption for real-life networks, see for instance [START_REF] Albert | Statistical mechanics of complex networks[END_REF][START_REF] Buriol | Counting triangles in data streams[END_REF]. Note that fast update is essential for real life applications. Consider for example the Facebook graph. In May 2011, for less than eight years existence, there were about 69 billion friendship links [START_REF] Backstrom | Four degrees of separation[END_REF]. This means an average of above 300 new links per second, without counting deletions and peak hours.

In Section 6 we compare the theoretical guarantees for several real life graphs. While such a comparison is far from being a rigorous experimental evaluation, it clearly indicates that the processing time per edge in [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF][START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF] is prohibitively large and the assumption that the transitivity coefficient is constant is justified. Also, for graphs with a relatively small number of triangles our algorithm is much more space-efficient.

Our algorithm

The main idea behind our algorithm is to design a new sampling technique for dynamic graph streams. It exploits a combination of the algorithms by Buriol et al. [START_REF] Buriol | Counting triangles in data streams[END_REF] for the incidence stream model, and the Doulion algorithm [START_REF] Tsourakakis | DOULION: counting triangles in massive graphs with a coin[END_REF] and its improvement [START_REF] Pagh | Colorful triangle counting and a MapReduce implementation[END_REF]. Let us briefly describe the approaches.

The Buriol et al. algorithm for incidence list streams. Assume we know the total number of 2paths in G. One chooses at random one of them, say (u, v, w), and checks whether the edge (u, w) appears later in the stream. For a triangle u, v, w the three 2-paths (u, v, w), (w, u, v), (v, w, u) appear in the incidence list stream, thus the probability that we sample a triangle is exactly α. One chooses independently at random K 2-paths and using standard techniques shows that for K = O( 1 ε 2 α log 1 δ ) we compute an (ε, δ)approximation of α(G). One can get rid of the assumption that the number of 2-paths is known in advance by running O(log n) copies of the algorithm in parallel, each guessing the right value. The reader is referred to the original work for more details. For incidence streams, the number of 2-paths in G can be computed exactly by updating a single counter, thus if α is an (ε, δ)-approximation of the transitivity coefficient then T3 = αP 2 is an (ε, δ)-approximation of T 3 .

Doulion and monochromatic sampling. The Doulion algorithm [START_REF] Tsourakakis | DOULION: counting triangles in massive graphs with a coin[END_REF] is a simple and intuitive sparsification approach. Each edge is sampled independently with probability p and added to a sparsified graph G S . We expect pm edges to be sampled and a triangle survives in G S with probability p 3 , thus multiplying the number of triangles in G S by 1/p 3 we obtain an estimate of T 3 . The algorithm was improved in [START_REF] Pagh | Colorful triangle counting and a MapReduce implementation[END_REF] by using monochromatic sampling. Instead of throwing a biased coin for each edge, we uniformly at random color each vertex with one of 1/p colors. Then we keep an edge in the sparsified graph iff its endpoints have the same color. A triangle survives in G S with probability p 2 . It is shown that for a fully random coloring the variance of the estimator is better than in Doulion. However, in both algorithms it depends on the maximum number of triangles an edge is part of, and one might need constant sampling probability in order to obtain an (ε, δ)-approximation on T 3 . The algorithm can be applied to dynamic streams because one counts the number of triangles in the sparsified graph after all edges have been processed. However, it can be expensive to obtain an estimate since the exact number of triangles in G S is required.

Combining the above approaches. The basic idea behind the new algorithm is to use the estima-tor of Buriol et al. for the incidence stream model: (i) estimate the transitivity coefficient α(G) by choosing a sufficiently large number of 2-paths at random and check which of them are part of a triangle, and (ii) estimate the number of 2-paths P 2 in the graph. We first observe that estimating P 2 in dynamic graph streams can be reduced to second moment estimation of streams of items in the turnstile model, see e.g. [START_REF] Thorup | Tabulation based 4-universal hashing with applications to second moment estimation[END_REF]. For (i), we will estimate α(G) by adjusting the monochromatic sampling approach. Its main advantage compared to the sampling of edges separately is that if we have sampled the 2-path (u, v, w), then we must also have sampled the edge (u, w), if existent. So, the idea is to use monochromatic sampling and then in the sparsified graph to pick up at random a 2-path and check whether it is part of a triangle. Instead of random coloring of the vertices, we will use a suitably defined hash function and we will choose a sampling probability guaranteeing that for a graph with no isolated edges (or rather a small number of isolated edges) the sparsified graph will contain a sufficiently big number of 2-paths. A 2-path in the sparsified graph picked up at random, will then be used to estimate α(G). Thus, unlike in [START_REF] Buriol | Counting triangles in data streams[END_REF], we sample after the stream has been processed and this allows to handle edge deletions. The main technical obstacles are to analyze the required sampling probability p and to show that this sampling approach indeed provides an unbiased estimator of α(G). We will obtain bounds on p and show that even if the estimator might be biased, the bias can be made arbitrarily small and one can still achieve an (ε, δ)-approximation of α(G). Also, we present an implementation for storing a sparsified graph G S such that each edge is added or deleted in constant time and a random 2-path in G S , if existent, can be picked up without explicitly considering all 2-paths in G S .

Algorithm details

Pseudocode description of the algorithm is given in Figure 1. We assume that the graph is given as a stream S of pairs ((u, v), $), where (u, v) ∈ E and $ ∈ {+, -} with the obvious meaning that the edge (u, v) is inserted or deleted from G. In EstimateNumberOfTwoPaths each incoming pair ((u, v), $) is treated as the insertion, respectively deletion, of two items u and v, and these update a second moment estimator SM E, working as a blackbox algorithm. We refer to the proof of Lemma 1 for more details. In SparsifyGraph we assume access to a fully random coloring hash function f :

V → C. Each edge (u, v) is inserted/deleted to/from a sparsified graph G S iff f (u) = f (v).
At the end G S consists of all monochromatic edges that have not been deleted. In EstimateNumberOfTriangles we run in parallel the algorithm estimating P 2 and K copies of SampleRandom2Path. For each G i S , 1 ≤ i ≤ K, with at least s pairwise independent 2-paths we choose at random a 2-path and check whether it is a triangle. (Note that we require the existence of s pairwise independent 2-paths but we choose a 2-path at random from all 2-paths in G S .) The ratio of triangles to all sampled 2-paths and the estimate of P 2 are then used to estimate T 3 . In the next section we obtain bounds on the user defined parameters C, K and s. In Lemma 7 we present en efficient implementation of G S that guarantees constant time updates and allows the sampling of a random 2-path in expected time O(log n) and worst case time O(log 2 n) with high probability.

Theoretical analysis

We will prove the main result in several lemmas. The first lemma provides an estimate of P 2 using an estimator for the second frequency moment of data streams [START_REF] Thorup | Tabulation based 4-universal hashing with applications to second moment estimation[END_REF].

Lemma 1 Let G be a graph with no isolated edges given as a stream of edge insertions and deletions. There exists an algorithm returning an (ε, δ)-approximation of the number of 2-paths in G in one pass over the stream of edges which needs O( 1 ε 2 log 1 δ ) space and O(log 1 δ ) processing time per edge. Proof: We show that EstimateNumberOfTwoPaths in Figure 1 returns an (ε, δ)-approximation of the number of 2-paths in G. We reduce the problem of computing the number of 2-paths in dynamic graph streams to the problem of estimating the second frequency moment in streams of items in the turnstile model. By associating vertices with items and treating each incoming pair ((u, v), $) as the insertion, respectively deletion, of two new items u and v, it is a simple observation that the second moment of the so defined EstimateNumberOfTwoPaths Input: stream of edge deletions and insertions S, algorithm SM E estimating the second moment items streams 1: m = 0 2: for each ((u, v), $) in S do

: V → C 1: G S = ∅ 2: for each ((u, v), $) ∈ S do 3: if f (u) = f (v) then 4: if $= + then 5: G S = G S ∪ (u, v).
G S = G S \(u, v). 8: Return G S .

SampleRandom2Path

Input: sparsified graph G S 1: choose at random a 2-path (u, v, w) in G S 2: if the vertices {u, v, w} form a triangle then return 0 EstimateNumberOfTriangles Input: streamed graph S, set of K independent fully random coloring functions F, algorithm SM E estimating the second moment of streams of items, threshold s 1: run in parallel EstimateNumberOfTwoPaths(S, SM E) and let P2 be the returned estimate 2: run in parallel K copies of SparsifyGraph(S, f i ), f i ∈ F 3: = 0 4: for each G i S with at least s pairwise independent 2-paths do 5:

X+ = SampleRandom2Path(G i S )
6: Since G contains no isolated edges, for each edge (u, v) we can assume that at least one of its endpoints has degree more than one, w.l.o.g. d u ≥ 2. Thus, (u, v) must be part of at least one 2-path, namely a 2-path centered at u. Each edge can be assigned thus to at least one 2-path and this implies a lower bound on the number of 2-paths in G, v∈V dv 2 ≥ m/2, thus

+ = 1 7: α = X/ 8: return α P2 3
F 2 = 2 v∈V d v 2 + 2m ≥ 3m.
Assume now that we have computed an (1 ± ε/2)-approximation of F 2 and we have the exact value of m.

Then the over-and underestimation returned by EstimateNumberOfTwoPaths is bounded by (ε/2)F 2 .

For

F 2 ≥ 3m it holds (ε/2)F 2 ≤ ε(F 2 -m) = εP 2 .
As for the complexity of EstimateNumberOfTwoPaths, we observe that recording the exact value of m requires constant processing time per edge and O(log n) bits. For SM E, we use the algorithm from [START_REF] Thorup | Tabulation based 4-universal hashing with applications to second moment estimation[END_REF] for the estimation of the second moment, which computes an (ε, δ)-approximation of v∈V d 2 v with the claimed time and space complexity.

The next two lemmas show a lower bound of Ω(m) on the number of pairwise independent 2-paths in a graph without isolated edges. The result is needed in order to obtain bounds on the required sampling probability. We first show that in order to obtain a lower bound for general graphs it is sufficient to consider bipartite connected graphs. This is true because every connected graph contains a cut with at least m/2 edges such that the bipartite graph between the two vertex subsets is connected. We prove this first. Proof: Let G = (V, E) be a connected graph. We first show that there exists (U, W ) such that B contains at least m/2 edges. To this end, initialize U := ∅ and W := V . Now, as long as there either exists a

vertex v ∈ W with |N G (v) ∩ W | > |N G (v) ∩ U | or a vertex v ∈ U with |N G (v) ∩ U | > |N G (v) ∩ W |,
we exchange this vertex v, that is, in the first case, we add v to U and delete it from W and vice versa in the second case. Clearly, this increases the number of edges between U and W ; hence, this procedure terminates after a finite number of steps. Moreover, after termination, it holds

|N G (v) ∩ W | ≤ |N G (v) ∩ U | for each v ∈ W and |N G (v) ∩ U | ≤ |N G (v) ∩ W | for each v ∈ U . Thus, there are at least m/2 edges in B.
Assume now that B is not connected and let B 1 , . . . , B c denote the c ≥ 2 connected components of B and let U i ⊆ U , W i ⊆ W be the bipartition of B i . We simply "swap" an arbitrary component, say B 1 , that is, we delete the vertices U i from U and add them to W and delete the vertices W i from W adding them to U . Clearly, the edges between U i and W i remain in B. Additionally, the edges between U i and U \ U i as well as the edges between W i and W \ W i are added to B. Hence, the number of edges in B increased. Moreover, since G is connected, the component B 1 is now connected to some other component in B and thus the number of connected components decreased. This proves the claim.

We also need, for the case where there are few edges in the graph, the following lower bound.

Lemma 3 Let G = (V, E) be a connected graph. The number of independent 2-paths in G is at least |V |/2 -1.
Proof: This can easily be obtained by taking a rooted spanning tree T of G. Assuming |V | ≥ 3, take any leaf u of T with maximum depth (distance to the root). Let v be the parent of u. If v has another child w, then w is a leaf of T . Select the 2-path {{u, v}, {v, w}}, remove vertices u and w from V , and start again. Otherwise, v has a parent w: Similarly, select the 2-path {{u, v}, {v, w}}, remove vertices u and v from V , and start again. The set of 2-paths thus selected is independent (each one uses 2 new vertices) and contains at least (m -1)/2 = (|V | -2)/2 2-paths.

We now prove the lower bound for bipartite connected graphs.

Lemma 4 Let G = (V, E) with |E| = m be a connected bipartite graph. The number of independent 2-paths in G is at least m/9 .

Proof: We say that a set of independent 2-paths P is maximal if for any 2-path P of G not yet in P, P ∪ {P } is not independent. We first prove the following property by induction on |E|:

In any bipartite graph G = (V, E), if P is a maximal set of independent 2-paths, then

|P| ≥ m 6 - |V | 4 .
Let F be the set of edges which are not used in any 2-path of P. Note that |P| = m-|F |

2

. We consider the subgraph H := (V, F ) of G. First, consider the easy case where all vertices have degree at most 1 in H.

It follows that |F | ≤ |V | 2 . Thus, |P| ≥ m -|V | 2 2 ≥ m 6 - |V | 4 .
Otherwise, pick a vertex u having maximum degree in H, write k for its degree (k ≥ 2), and N (u) for the set of its k neighbors in H. Consider any two distinct vertices v, v ∈ N (u). Then {{v, u}, {u, v }} is a 2-path of G. Since P is maximal, this 2-path must be in conflict with some selected 2-path P v,v ∈ P. So, P v,v covers two vertices among {v, u, v }. Since the graph is bipartite, and P v,v does not use the edges {u, v}, {u, v } ∈ F , it follows that P v,v must cover both vertices v and v . Let F (u) ⊆ F be the subset of edges of F which are incident to a vertex of N (u). Note that |F (u)| ≤ k 2 . Indeed, N (u) contains k vertices, all of them having degree at most k in H. Let P (u) ⊆ E \ F be the subset of E containing all edges used by a 2-path P v,v ∈ P for any pair v, v ∈ N (u), then |P (u)| = 2 k 2 = k(k -1). Indeed, there are k 2 pairs v, v ∈ N (u), and each of them yields a unique 2-path P v,v containing two edges (two 2-paths cannot share any edge since they are independent). Now, we define

E := E \ (P (u) ∪ F (u)) and P := P \ {P v,v | v = v ∈ N (u)},
and claim that P is a maximal set of 2-paths of the subgraph G := (V, E ). Assume towards a contradiction that there is a 2-path P * in G which is not in conflict with any 2-path of P . Since G is a subgraph of G, and P is maximal, it follows that P * is in conflict with some P v,v ∈ P \ P . Thus, P * contains at least one of the two vertices v, v , and must contain an edge in F (u) ⊆ E \ E ; a contradiction. Hence, P is maximal for the bipartite graph G and, by induction, we have

|P | ≥ |E | 6 - |V | 4 .
Putting everything together, we have

|P | = |P| - k 2 and |E | ≥ |E| -k(k -1) -k 2 ,
which yields

|P| = |P | + k 2 ≥ |E | 6 - |V | 4 + k 2 ≥ |E| -k(k -1) -k 2 6 - |V | 4 + k 2 = |E| 6 - |V | 4 + 2k(k -1) -k 2 6 ≥ |E| 6 - |V | 4 (since 2k(k -1) ≥ k 2 for all k ≥ 2).
This completes the proof of the induction property.

To prove the lemma, it remains to distinguish between the following two cases:

• If m = |E| ≥ 9|V | 2
, then with the induction property above, any maximal set of independent 2-paths has size at least

m 6 - |V | 4 ≥ m 6 - 1 4 • 2m 9 = 3m -m 18 ≥ m 9 .
• If m = |E| < 9|V | 2 , then with Lemma 3, there exists a set of independent 2-paths with size at least

|V | 2 -1 ≥ m 9 -1 = m 9 .
Proof: We analyze how much differs the probability between 2-paths to be selected by SampleRan-dom2Path. Consider a given 2-path (u, v, w). It will be sampled if the following three events occur:

1. (u, v, w) is monochromatic, i.e., it is in the sparsified graph G S .

2. There are i ≥ 18/ε 2 pairwise independent 2-paths in G S .

3. (u, v, w) is selected by SampleRandom2Path.

The first event occurs with probability p 2 . Since f is fully random, the condition that (u, v, w) is monochromatic does not alter the probability for any 2-path independent from (u, v, w) to be also monochromatic. The probability to be in G S changes only for 2-paths containing two vertices from {u, v, w}, which in turn changes the number of 2-paths in G S and thus probability for (u, v, w) to be picked up by SampleRan-dom2Path. In the following we denote by p G S the probability that a given 2-path is monochromatic and there are at least 18/ε 2 pairwise independent 2-paths in G S , note that p G S is equal for all 2-paths. Consider a fixed coloring to V \{u, v, w}. We analyze the difference in the number of monochromatic 2-paths depending whether f (u) = f (v) = f (w) or not. There are two types of 2-paths that can become monochromatic conditioning on f (u) = f (v) = f (w): either (i) 2-paths with two endpoints in {u, v, w} centered at some {u, v, w}, or (ii) 2-paths with two vertices in {u, v, w} centerer at a vertex x / ∈ {u, v, w}. For the first case assume w.l.o.g. there is a 2-path (u, v, w) ∈ G S centered at v and let d

f (v) v = |{z ∈ N (v)\{u, w} : f (z) = f (v)}|, i.e., d f (v) v
is the number of v's neighbors different from u and w, having the same color as v. Thus, the number of monochromatic 2-paths centered at v varies by 2d

f (v) v
conditioning on the assumption that f (u) = f (v) = f (w). The same reasoning applies also to the 2-paths centered at u and w. For the second case consider the vertices u and v. Conditioning on f (u) = f (w), we additionally add to G S 2-paths (u, x i , w) for which f (x i ) = f (u) = f (w) and x i ∈ N (u) ∩ N (w). The number of such 2-paths is at most min(d

f (u) u , d f (w) w
). The same reasoning applies to any pair of vertices from {u, v, w}. Therefore, depending on whether f (u) = f (v) = f (w) or not, the number of monochromatic 2-paths centered at a vertex from {u, v, w} varies between Set k = 18/ε 2 . Consider now two different, but not necessarily independent, 2-paths (u 1 , v 1 , w 1 ), (u 2 , v 2 , w 2 ) ∈ G. We analyze the probability for each of them to be selected by SampleRandom2Path. Let C be a partial coloring to V \{u j , v j , w j }, j = 1, 2. If C is completed to a coloring of all vertices such that both (u 1 , v 1 , w 1 ) and (u 2 , v 2 , w 2 ) are monochromatic, then clearly they are picked up with the same probability. Assume that with probability p i , i -1 2-paths are colored monochromatic by C and consider extensions of C that make exactly one of (u 1 , v 1 , w 1 ) and (u 2 , v 2 , w 2 ) monochromatic. Under the assumption there are i ≥ k 2-paths in G S and following the above discussion about the number of 2-paths with at least two vertices from {u j , v j , w j }, we see that the number of monochromatic 2-paths can vary between i and i + 3 √ 2i. Thus, the probability for (u 1 , v 1 , w 1 ) and (u 2 , v 2 , w 2 ) to be sampled varies between

p G S i≥k p i i and p G S i≥k p i i + 3 √ 2i .
We assume G S contains at least k 2-paths, thus i≥k p i = 1 and there exists r ≥ k, r ∈ R such that i≥k p i i -1 = 1/r. Thus we bound

i≥k p i i + 3 √ 2i = i≥k p i i(1 + 3 2/i) ≥ 1 1 + 3 2/k i≥k p i i = 1 r(1 + 3 2/k) .
Proof: (of Theorem 1). Assume EstimateNumberOfTriangles runs K copies in parallel of SparsifyGraph with p = 5 ε √ b for b = m/18 . By Lemma 2, Lemma 4 and and Lemma 5 with probability 3/4 we have a sparsified graph with at least s = 18/ε 2 pairwise independent 2-paths. Thus, we expect to obtain from 3K/4 of them an indicator random variable. A standard application of Chernoff's inequality yields that with probability O(2 -K/36 ) we will have ≥ K/2 indicator random variables X i denoting whether the sampled 2-path is part of a triangle. By Lemma 6 we have (1 -ε)α ≤ E[X i ] ≤ (1 + ε)α and as an estimate of α we return i=1 X i / . Observe that (1 + ε/3) 2 ≤ 1 + ε, respectively (1 -ε/3) 2 ≥ 1 -ε. From the above discussion and applying Chernoff's inequality and the union bound, we see that for K = 36 ε 2 α log 2 δ , we obtain an (ε, δ/2)-approximation of α. By Lemma 1 we can compute an (ε, δ/2)-approximation of the number of 2-paths in space O( 1 ε 2 log 1 δ ) and O(log 1 δ ) per edge processing time. It is trivial to show that this implies an (3ε, δ)-approximation of the number of triangles for ε < 1/3. Clearly, one can rescale ε in the above, i.e. ε = ε/3, such that EstimateNumberOfTriangles returns an (ε, δ)-approximation.

By Lemma 7, each sparsified graph with m edges uses space O(m ) and each update takes constant time with high probability, thus we obtain that each edge is processed with high probability in time O(K). Each monochromatic edge and its color can be represented in O(log n) bits.

By Lemma 7, in expected time O(log n) and worst case time O(log 2 n) with high probability we sample uniformly at random a 2-path from each G S with at least 18/ε 2 pairwise independent 2-paths.

Lower bound

Pavan et al. [START_REF] Pavan | Counting and Sampling Triangles from a Graph Stream[END_REF] show that every streaming algorithm approximating the number of triangles in adjacency streams (edges are inserted in arbitrary order) needs space ω(1/α(G)). For the general case, we show another lower bound on the memory needed which matches the upper bound by Manjunath at al. [START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF]. Our lower bound works for the promise version of this problem where the algorithm is required to distinguish between the case where there are no triangles and the case where there are at least T 3 triangles, for a parameter T 3 . The behavior if the number of triangles is between 1 and T 3 -1 is unspecified, i.e., the algorithm may return any result. Clearly this problem is solved as a special case by any streaming algorithm that is able to approximate the number of triangles, so our space lower bound will also apply to the setting of our upper bound.

Theorem 3 Let G = (V, E) be a graph over m vertices. Any one-pass streaming algorithm distinguishing between the cases where G has at least T 3 triangles and G is triangle-free, needs Ω(m 3 /T 2 3 ) bits.

Proof: We obtain the lower bound by a reduction from 1-way protocols for the Index problem in communication complexity. In this problem Alice is given a bit string x ∈ {0, 1} a and needs to send a message to Bob who holds an index i, such that Bob is able to output x i with probability at least 2/3 (where the probability is over random coin tosses made by Alice and Bob). It is known that this problem requires a message of size Ω(a) [START_REF] Kremer | On Randomized One-Round Communication Complexity[END_REF].

From a streaming algorithm with space usage s that distinguishes the cases of 0 and ≥ T 3 triangles we obtain a communication protocol for the indexing problem with a = Θ(m 3 /T 2 3 ). The reduction is as follows: Consider a vertex disjoint bicliques C 1 , . . . , C a with Θ(T 3 /m) vertices on each side, and form the stream with edge set ∪ i,xi=1 C i . The number of edges in this stream is Θ(a(T 3 /m) 2 ), which is Θ(m). Adjusting constants we can make the number of edges less than m/2. Alice can simulate the streaming algorithm on this input and send its state of s bits to Bob. In order to determine the value of x i Bob now connects Θ(m 2 /T 3 ) new (i.e., previously isolated) vertices to all vertices in C i . Adjusting constants this gives another m/2 edges, and will create either no triangles (if C i was not in the stream simulated by Alice) or Θ((m 2 /T 3 )(T 3 /m) 2 ) = Θ(T 3 ) triangles (if C i was in the stream). Thus, if the streaming algorithm succeeds with probability 2/3, so does Bob. In conclusion we must have a space usage of s = Ω(a) bits, which is Ω(m 3 /T 6 Comparison on the theoretical guarantee for real graphs

In Table 4 we compare the theoretical guarantee on the complexity of our algorithm to the ones shown in [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF][START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF] for real graphs. We used the publicly available information from the Stanford Large Network Dataset Collection2 . (Note that there the transitivity coefficient is called fraction of closed triangles.) As can be seen, the transitivity coefficient α appears to be constant. The update time of O(n log n) from [START_REF] Ahn | Graph sketches: sparsification, spanners, and subgraphs[END_REF] is always impractical, and for [START_REF] Manjunath | Approximate Counting of Cycles in Streams[END_REF] it is almost always prohibitively large, the only exception being the Facebook graph for which the m 3 /T 2 3 is small. (Note that this is a graph collected from users who used the Social Circles application and does not reflect the structure of the whole social network graph.) The space usage of our algorithm is also much better for several graphs which are not very dense with respect to the number triangles.

  update(u, 1), SM E.update(v, 1) 6:

  update(u, -1), SM E.update(v, -1) 9: return SM E.estimate/2 -m SparsifyGraph Input: stream of edge deletions and insertions S, coloring function f

Figure 1 :

 1 Figure 1: Estimating the number of 2-paths in G, the transitivity coefficient and the number of triangles.

Lemma 2

 2 Let G = (V, E) be an arbitrary connected graph with |E| = m. There exists a bipartition (U, W ) of V such that the bipartite graph B := (V, E ) with E := E ∩ {{u, w} | u ∈ U, w ∈ W } is connected and |E | ≥ m/2.

Table 4 :

 4 Comparison of the theoretical guarantees for several real-life graphs, b = max(n, P 2 /n). The lowest space usage in each row is given in bold font.

	2 3 ) as desired.

More generally, our results hold when the n vertices come from some arbitrary universe U known in advance.

http://snap.stanford.edu/data/index.html

Supported by the DFG project DAMM (NI 369/13). ‡ kutzkov, Work done while the author was at IT University of Copenhagen and supported by the Danish National Research Foundation under the Sapere Aude program.

§ pagh@itu.dk, Supported by the Danish National Research Foundation under the Sapere Aude program.

Combining Lemmas 2 and 4 we obtain that any connected graph has at least m 18 independent 2-paths. For dense graphs, Lemma 4 gives a lower bound of m 12 -|V | 4 ∼ m 12 . This yields the following result:

Theorem 2 Let G = (V, E) with |E| = m be a connected graph. The number of independent 2-paths in G is in Ω(m).

Next we obtain bounds on the sampling probability such that we can guarantee there are sufficiently many pairwise independent 2-paths in G S . As we show later, this is needed to guarantee that SampleRan-dom2Path will return an almost unbiased estimator of the transitivity coefficient. The events for two 2-paths being monochromatic are independent, thus the next lemma follows from Theorem 2 and Chebyshev's inequality. Note that we still don't need the coloring function f to be fully random.

Lemma 5 Let f be 6-wise independent and p ≥ 5 ε √ b where b is the number of independent 2-paths in G and ε ∈ (0, 1]. Then with probability at least 3/4 SparsifyGraph returns G S such that there are at least 18/ε 2 independent 2-paths in G S .

Proof: Let D 2 be a set of pairwise independent 2-paths in G, |D 2 | = b. Clearly, each 2-path in D 2 is monochromatic with probability p 2 . Consider two pairwise independent 2-paths (u 1 , v 1 , w 1 ) and (u 2 , v 2 , w 2 ). If they do not share a vertex, then since f is 6-wise independent, the two of them are monochromatic with probability p 4 . Otherwise, assume w.l.o.g. u 1 = u 2 . Under the assumption that f (u 1 ) = c for some c ∈ C, we have that evaluating f on v i , w i , i = 1, 2, is 5-wise independent. Thus, Pr[f

The events of sampling the two 2-paths are thus independent. We introduce an indicator random variable

and since the events that any two 2-paths in D 2 are sampled are independent, we have V [X] ≤ E[X]. From Chebyshev's inequality with some algebra we then obtain that with probability at least 3/4 we have at least 18/ε 2 monochromatic pairwise independent 2-paths in G S .

Lemma 6 Assume we run EstimateNumberOfTriangles with s = 18/ε 2 and let X be the value returned by SampleRandom2Path.

Since the function f is fully random, each coloring is equally probable. The above reasoning applies to any pair of 2-paths in G, thus for any 2-path the probability to be sampled varies between

Assume first the extreme case that 2-paths which are not part of a triangle are sampled with probability 1 r and 2-paths part of a triangle with probability 1 (1+ε)r . We have X = (u,v,w)∈P2 I (u,v,w) , where I (u,v,w) is an indicator random variable denoting whether (u, v, w) is part of a triangle. Thus

On the other extreme, assuming that we select 2-paths part of triangles with probability 1 r and 2-paths not part of a triangle with probability 1 r(1+ε) , using similar reasoning we obtain

Applying a variation of rejection sampling, in the next lemma we show how to store a sparsified graph G S such that we efficiently sample a 2-path uniformly at random and G S is updated in constant time.

Lemma 7 Let G S = (V, E S ) be a sparsified graph over m monochromatic edges. There exists an implementation of G S in space O(m ) such that an edge can be inserted to or deleted from G S in constant time with high probability. A random 2-path, if existent, can be selected from G S in expected time O(log n) and O(log 2 n) time with high probability.

Proof: We implement G S as follows. Let ∆ ≤ n be the maximum vertex degree in G S . We maintain a hash table

, there are between 2 i and 2 i+1 -1 2-paths centered at v. The hash table contains a vertex v as a key together with the set of its neighbors N (v). We also store the vertices with only one neighbor in G S in a hashtable H ∅ . (Note that if there are no vertices in a given H i , we don't maintain H i .)

In another hash table T we maintain for each vertex incident to at least one sampled edge, a link to the H i it is contained in. Whenever a new edge (u, v) is inserted or deleted from G S , we first look-up in T for the H i containing u and v and then update the corresponding numbers of 2-paths centered at u and v. It may happen that we need to move u and/or v from a hashtable H i to a hashtable H i±1 . For each H i we also maintain the total number of 2-paths centered at vertices v ∈ H i , denote this number as P 2 (H i ). Implementing T and the H i using the implementation from [START_REF] Arbitman | Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation[END_REF], each update takes constant time with high probability and the total space is O(m ).

We sample a 2-path from G S at random as follows. We compute P 2 (G S ) = i H i and select an H i where each H i has a chance of being picked up of P 2 (H i )/P 2 (G S ). This is done by generating a random number r ∈ (0, 1] and then computing a prefix-sum of P 2 (H i )'s until the sum reaches r in time O(log n). Once we have chosen an H i , we select a vertex v ∈ H i at random as follows. Assume we maintain the set of vertices in each H i in a dynamic dictionary V i implemented as a hashtable using tabulation hashing. We assume that the longest chain in V i is bounded by a κ = O(log n/ log log n) [START_REF] Pǎtraşcu | The Power of Simple Tabulation Hashing[END_REF]. We select a chain in V i at random and keep it with probability /κ, where ≥ 0 is the length of the selected chain, otherwise we reject it and repeat the step until a chain is kept. Then, we select at random one of the vertices on the chain, let this be v. We apply one more time rejection sampling in order to decide whether we keep v or not: Let q = 2 i+1 -1. We get the value d v from H i and keep v with probability dv 2 /q and reject it with with probability 1 -dv 2 /q. Once we keep a vertex v, we choose at random two of its neighbors in G S which constitutes the sampled 2-path. The expected number of sampling a chain and a random vertex until we keep a vertex is O(log n/ log log n), thus the expected number of trials is O(log n) and with high probability we determine a 2-path in time O(log 2 n). It is easy to see that each 2-path is selected with equal probability p such that 1 2κP2(G S ) ≤ p ≤ 1 P2(G S ) , thus we sample uniformly at random from the set P 2 (G S ). Now we have all components in order to prove the main result.