# Streaming algorithm for counting triangles in a graph

As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $$\hat T$$ for the # of triangles in a given graph $$G = (V, E)$$, denoted $$T$$. It is written that "it can easily be shown" that $$E[\hat T] = T$$ But unfortunately, I'm not seeing it. Trying to analyze $$E[\hat T]$$, I think as follows:

• At line 1, denote the probability to randomly (and uniformly) choose an edge which is part of a triangle as $$p$$. Since triangles can share edges, $$\frac T m \le p \le \frac {3T} m$$ For example, consider the following case:

The central triangle doesn't add new edges to the # of possibilities to choose an edge which is part of a triangle. You can imagine a different configuration, in which there are only the 3 outer triangles and they don't touch each other (in this configuration, we won't see the central 4th triangle). In both cases ((case i) 4 triangles as seen in the image; (case ii) 3 disjoint triangles), the probability to choose an edge which is part of a triangle is 1 (although the # of triangles is different).

• At line 2, the probability to choose uniformly at random a vertex which "closes a triangle" with the edge from the previous step is exactly $$\frac 1 {n-2}$$.

Therefore I only see that

$$T \le E[\hat T] \le 3T$$

What am I missing?

Another question I have is regarding line 3. The stream is ordered, and we first pick a random edge $$(u, v)$$ (line 1), then a random vertex $$w$$ from $$V \backslash \{u, v\}$$ (line 2). I feel that the analysis should take into account that at line 3 we check whether $$(u, w)$$ and $$(v, w)$$ appear after $$(u, v)$$ in the stream. Maybe after I'll understand the answer to my first question, it will be clearer.

Algorithm:

1. Pick an edge $$(u, v)$$ uniformly at random from the stream.
2. Pick a vertex $$w$$ uniformly at random from $$V \backslash \{u, v\}$$
3. If $$(u, w)$$ and $$(v, w)$$ appear after $$(u, v)$$ in the stream, then output $$m(n-2)$$. Else, output $$0$$.

Also, although I didn't see it written, I believe there's an assumption that $$V$$ is known ahead.

Reference: Data streams lecture notes by Prof. Amit Chakrabarti, section "15.3 Triangle Counting", https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf

Best regards

Let $$(u,v,w)$$ be a particular triangle in the stream, and suppose that the edge $$(u,v)$$ appears first. The probability that we chose $$(u,v)$$ in the first step is $$1/m$$. The probability that we chose $$w$$ in the second step is $$1/(n-2)$$. Hence the probability that we chose the triangle $$(u,v,w)$$ is $$1/[m(n-2)]$$. Let us denote this event by $$E_{u,v,w}$$.
If $$(u_1,v_1,w_1)$$ and $$(u_2,v_2,w_2)$$ are two different triangles that the events $$E_{u_1,v_1,w_1}$$ and $$E_{u_2,v_2,w_2}$$ are disjoint (note that the triangles don't have to be disjoint). Therefore if there are $$T$$ triangles, then the probability that we chose one of them is exactly $$T/[m(n-2)]$$. Therefore the expected output of the algorithm is exactly $$T$$.
• Thank you. Now I see why $E[\hat T] = T$. But I have a followup question: How to take into account the fact that in step 1 we use an algorithm which only approximately uniform at random (like Reservoir)? Only when ignoring that, I showed that with high probability $\left| \hat T - T \right| < \epsilon T$: I showed that $Var \left[ \hat T \right] \le O(T^2)$, by running $O(\frac {mn} t)$ copies of the above algorithm (each report $\hat T_i$), and report their average $T$. Then using Chebychev inequality, $\Pr \left[ \left| \hat T - T \right| < \epsilon T \right] \ge 1 - \frac 1 {\epsilon^2}$. – keyboardAnt Jun 30 '20 at 17:06
• Thank you for correcting me. Now I'm a bit confused regarding the storage analysis. To show that $\Pr \left[ \left| \hat T - T \right| < \epsilon T \right] \ge 1 - \frac 1 {\epsilon^2}$ I used only $O(\frac {mn} t)$ storage words. Nevertheless, the reference claim to use $O(\epsilon^{-2} \frac {mn} t \log \frac 1 \delta)$ storage to achieve $(\epsilon, \delta)$-approximation, which I'm not sure how to show (without choosing a specific $\delta$). – keyboardAnt Jun 30 '20 at 17:21