FURL: Fixed-memory and uncertainty reducing local triangle counting for multigraph streams

Given a multigraph stream (e.g., Facebook messages or network traffic) where duplicate edges arrive continuously, how can we accurately and memory-efficiently estimate local triangles for all nodes? Local triangle counting in a graph stream is one of the fundamental tasks in graph mining with important applications including anomaly detection, social role identification, community detection, etc. Many recent graph streams include duplicate edges, hence form multigraph streams: e.g., many network packets might have a same (source, destination) pair. Although there have been several local triangle counting methods for multigraph streams, they have problems in terms of accuracy and memory efficiency; furthermore, most methods support either binary or weighted counting, and thus cannot find anomalies whose detection requires both types of counting. In this paper, we propose FURL, a memory-efficient and accurate local triangle counting method for multigraph streams. FURL has two main advantages. First, FURL improves accuracy by (1) reducing the variance of its estimation via a regularization strategy, and (2) sampling more triangles than the state-of-the-art methods do, by using its memory space efficiently. Second, FURL finds anomalies which state-of-the-art methods cannot discover. Experimental results show that FURL outperforms state-of-the-art methods in terms of accuracy and memory efficiency. Thanks to FURL, we discover interesting anomalies from a Bitcoin network.

This work was supported by AFOSR/AOARD under the Grant No. FA2386-16-1-4044. This work was also supported by Institute for Institute of Information and Communications Technology Planning and Evaluation (IITP) grant funded by the Korea government (MSIT) (No. R0190-15-2012, High Performance Big Data Analytics Platform Performance Acceleration Technologies Development). The Institute of Engineering Research at Seoul National University provided research facilities for this work. The ICT at Seoul National University provides research facilities for this study.

Authors and Affiliations

1. Seoul National University, Seoul, South Korea

   Minsoo Jung, Sunmin Lee & U. Kang

2. MakinaRocks, Seoul, South Korea

   Yongsub Lim

Corresponding author

Correspondence to U. Kang.

Responsible editor: Derek Greene, Bjørn Bringmann, Elisa Fromont, Jesse Davis.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix A Proofs of Lemmas and Theorems

Theorem 1

Let \(\varDelta _u\) be the true local triangle count for a node u, and \(c_u\) be the estimation given by \({{\textsc {FURL}}\hbox {-}{\textsc {0}}_{\textsc {B}}}\). For every node u, \( \mathbb {E}\left[ c_u\right] = \varDelta _u. \)

Proof

Let \(T_\lambda \) be the time \(\lambda \) is formed and \(T_M\) be the last time we have the exact triangle counts. Let \(\varLambda _u^{-}\) be the set of triangles containing node u that are formed when we have the exact triangle counts, i.e. \(T_\lambda \le T_M\) , and \(\varLambda _u^{+}\) be the set of triangles containing node u that are formed when we do not have the exact triangle counts, i.e. \(T_\lambda > T_M\). Note that every triangle containing node u is included in either \(\varLambda _u^{-}\) or \(\varLambda _u^{+}\).

We define random variables \(X_\lambda ^{-}\) and \(X_\lambda ^{+}\) as follows:

For a triangle \(\lambda \in \varLambda _u^{-}\), \(\mathbb {E}\left[ X_{\lambda }^{-}\right] =1 \times \Pr \left[ \lambda \ is \ counted \right] = 1\) since all edges are unconditionally sampled at \(T\le T_M\).

Now we show \(\mathbb {E}\left[ X_{\lambda }^{+}\right] =1\) for each triangle \(\lambda \in \varLambda _u^{+}\). Let \(u(T) \ge M\) be the number of unique edges that have arrived so far in the stream at time T. Considering repeated edges as one edge, we get a refined stream that can be viewed as a sequence of independent random variables \(h_i(1 \le i \le u(T_\lambda ))\) that has a uniform distribution in range (0, 1). \(h_{max}\) can be viewed as the Mth smallest value among \(u(T_\lambda )\) number of random variables since D keeps the M minimum values. Then \(h_{max} \sim Beta(M,u(T_\lambda )+1-M)\) by the rule of kth order statistic in uniform distribution (Gentle 2009). Thus its probability density function \(f(x)=\frac{\gamma (u(T_\lambda )+1)}{\gamma (M) \cdot \gamma (u(T_\lambda )+1-M)} \cdot x^{M-1} \cdot (1-x)^{u(T_\lambda )-M}\). \(\Pr \left[ \lambda ~is ~counted \right] = \frac{M(M-1)(M-2)}{u(T_\lambda )(u(T_\lambda )-1)(u(T_\lambda )-2)}\) since it is the probability that 3 edges of \(\lambda \) are stored in the buffer D simultaneously. Note that \(\Pr \left[ \lambda ~is ~counted \right] \) is independent of the event \(h_{max}=x\).

Therefore, \( \mathbb {E}\left[ c_u\right] = \sum \limits _{\lambda \in \varLambda _u^{-}} \mathbb {E}\left[ X_{\lambda }^{-}\right] + \sum \limits _{\lambda \in \varLambda _u^{+}} \mathbb {E}\left[ X_{\lambda }^{+}\right] = \varDelta _u. \)\(\square \)

Theorem 2

Let \(\varDelta _u\) be the true local triangle count for a node u, and \(c_u\) be the estimation given by \({{\textsc {FURL}}\hbox {-}{\textsc {0}}_{\textsc {W}}}\). For every node u, \( \mathbb {E}\left[ c_u\right] = \varDelta _u. \)

Proof

We define random variables \(X_\lambda ^{-}\) and \(X_\lambda ^{+}\) which have 1 and \(q_{T_\lambda }=\frac{M-2}{M} \cdot \frac{1}{h_{max}^2}\) respectively if \(\lambda \) is counted, or 0 otherwise.

Then, \( \mathbb {E}\left[ c_u\right] = \sum \limits _{\lambda \in \varLambda _u^{-}} \mathbb {E}\left[ X_{\lambda }^{-}\right] + \sum \limits _{\lambda \in \varLambda _u^{+}} \mathbb {E}\left[ X_{\lambda }^{+}\right] \).

In \({{\textsc {FURL}}\hbox {-}{\textsc {0}}_{\textsc {W}}}\), although \(\lambda \) updates the estimation, the buffer does not meet a new edge at \(T_\lambda \) yet since a triangle is updated before sampling the edge. Then \(h_{max}\) can be viewed as the Mth smallest value among \(u(T_\lambda -1)\) number of random variables in range (0, 1) and \(h_{max} \sim Beta(M,u(T_\lambda -1)+1-M)\). Thus its probability density function is given as \(g(x)=\frac{\gamma (u(T_\lambda -1)+1)}{\gamma (M) \cdot \gamma (u(T_\lambda -1)+1-M)} \cdot x^{M-1} \cdot (1-x)^{u(T_\lambda -1)-M}\).

The probability that a triangle \(\lambda \) is counted is \(\frac{M(M-1)}{u(T_\lambda -1)(u(T_\lambda -1)-1)}\) because \(\lambda \) is counted if an arriving edge e forms \(\lambda \) with the other two edges in the buffer regardless of sampling e.

Therefore, \( \mathbb {E}\left[ c_u\right] = \sum \limits _{\lambda \in \varLambda _u^{-}} \mathbb {E}\left[ X_{\lambda }^{-}\right] + \sum \limits _{\lambda \in \varLambda _u^{+}} \mathbb {E}\left[ X_{\lambda }^{+}\right] = \varDelta _u. \)\(\square \)

Lemma 1

Let \(b_\lambda > 0\) be the bucket where a triangle \(\lambda \) is formed and \(Y_\lambda \) be the estimated count of a triangle \(\lambda \) by \({{\textsc {FURL}}_{\textsc {B}}}\). Then,

where \(\phi (i) = \delta ^{b-i+1}\) and b is the current bucket.

Proof

Let \(W(i)=(1-\delta )\delta ^{b-i}\) for \(i\ge 1\) and \(q_{T_\lambda } = \frac{(T-1)(T-2)}{M(M-1)}\). By definition, for \(\lambda \) appearing in bucket \(b_\lambda \), \(Y_\lambda \) becomes \(q_{T_\lambda } W(b_\lambda ) + q_{T_\lambda } W(b_\lambda +1) + \cdots + q_{T_\lambda } W(b)\) if \(\lambda \) is counted; if \(\lambda \) is not counted, \(Y_\lambda =0\). Thus, we obtain

\(\square \)

Lemma 2

Let \(b_\lambda > 0\) be the bucket where a triangle \(\lambda \) is formed and \(Y_\lambda \) be the estimated count of a triangle \(\lambda \) by \({{\textsc {FURL}}_{\textsc {B}}}\). Then,

where \(T_\lambda \) is the first time all three edges of \(\lambda \) arrive, \(k_{T_\lambda } = \frac{(M-3)(u(T_\lambda )-3)(u(T_\lambda )-4)(u(T_\lambda )-5)}{M(M-4)(M-5)(M-6)}\), \(\phi (i) = \delta ^{b-i+1}\), and b is the current bucket.

Proof

Following the definition \(\mathrm {Var}\left[ Y_\lambda \right] = \mathbb {E}\left[ Y_\lambda ^2\right] - \mathbb {E}\left[ Y_\lambda \right] ^2\) with Lemma 1, the proof is done. \(\square \)

Theorem 3

Let \(Y_\lambda \) and \(X_\lambda \) be the estimated counts of a triangle \(\lambda \) by \({{\textsc {FURL}}_{\textsc {B}}}\) and \({{\textsc {FURL}}\hbox {-}{\textsc {0}}_{\textsc {B}}}\), respectively. Consider any triangle \(\lambda \) that is counted at time \(T_\lambda > T_M\). Let u(T) be the number of unique edges that have arrived at time T. If \(u(T_\lambda ) \ge \root 3 \of {\frac{1+\alpha }{\alpha }}M + 3\), the interval by \(\mathbb {E}\left[ Y_\lambda \right] \pm \alpha \cdot \mathrm {Var}\left[ Y_\lambda \right] \) is strictly included in that by \(\mathbb {E}\left[ X_\lambda \right] \pm \alpha \mathrm {Var}\left[ X_\lambda \right] \) for any \(\alpha \).

Proof

We first show that \(\mathbb {E}\left[ Y_u\right] - \alpha \cdot \mathrm {Var}\left[ Y_u\right] > \mathbb {E}\left[ X_u\right] - \alpha \cdot \mathrm {Var}\left[ X_u\right] \).

Let \(\psi _\lambda =1-\delta ^{b-b_\lambda +1}\); we will find the condition satisfying \( \psi _\lambda - \alpha \psi _\lambda ^2\left( k_{T_\lambda }-1\right) - 1 + \alpha (k_{T_\lambda }-1) > 0, \) which is developed as follows.

Below, we will show the condition under which Eq. (1) holds. Let \(u(T_\lambda ) - 3 = \beta M\). By definition,

Then,

Now we examine the left term of Eq. (1). Since \(1\le b_\lambda \le b\), the lower bound of \(\psi _\lambda \) becomes \(\psi _\lambda \ge 1 - \delta \). Then, we obtain a sufficient condition for (1) as follows:

For \(\beta \ge \root 3 \of {\frac{1+\alpha }{\alpha }}\), Eq. (3) always holds since the upper bound of the right term becomes \(\frac{1+\alpha }{\alpha }\). Note that \(0\le \delta <1\). Thus, we finally obtain the condition under which Eq. (1) holds as follows:

Due to the underestimation of \({{\textsc {FURL}}_{\textsc {B}}}\), \(\mathbb {E}\left[ Y_\lambda \right] + \alpha \cdot \mathrm {Var}\left[ Y_\lambda \right] < \mathbb {E}\left[ X_\lambda \right] + \alpha \cdot \mathrm {Var}\left[ X_\lambda \right] \) always holds, which completes the proof. \(\square \)

Lemma 3

Let \(b_\lambda \) be the bucket where \(\lambda \) is formed and \(Y_\lambda \) be the estimated count of a triangle \(\lambda \) with \(b_\lambda >0\) by \({{\textsc {FURL}}_{\textsc {W}}}\). For every triangle \(\lambda \),

where \(\phi (i) = \delta ^{b-i+1}\) and b is the current bucket.

Proof

The lemma is proved in the same way as in Lemma 1. \(\square \)

Lemma 4

Let \(b_\lambda \) be the bucket where \(\lambda \) is formed and \(Y_\lambda \) be the estimated count of a triangle \(\lambda \) with \(b_\lambda >0\) by \({{\textsc {FURL}}_{\textsc {W}}}\). For every triangle \(\lambda \),

where \(T_\lambda \) is the first time all three edges of \(\lambda \) arrive, \(l_{T_\lambda } = \frac{(M-2)(u(T_\lambda -1)-2)(u(T_\lambda -1)-3)}{M(M-3)(M-4)}\), \(\phi (i) = \delta ^{b-i+1}\), and b is the current bucket.

Proof

The lemma is proved in the same way as in Lemma 2. \(\square \)

Theorem 4

Let \(Y_\lambda \) and \(X_\lambda \) be the estimated counts of a triangle \(\lambda \) by \({{\textsc {FURL}}_{\textsc {W}}}\) and \({{\textsc {FURL}}\hbox {-}{\textsc {0}}_{\textsc {W}}}\), respectively. Consider any triangle \(\lambda \) that is counted at time \(T_\lambda > T_M\). If \(u(T_\lambda -1) \ge \sqrt{\frac{1+\alpha }{\alpha }}M + 2\), the interval by \(\mathbb {E}\left[ Y_\lambda \right] \pm \alpha \cdot \mathrm {Var}\left[ Y_\lambda \right] \) is strictly included in that by \(\mathbb {E}\left[ X_\lambda \right] \pm \alpha \cdot \mathrm {Var}\left[ X_\lambda \right] \) for any \(\alpha \).

Proof

We first show that \(\mathbb {E}\left[ Y_\lambda \right] - \alpha \cdot \mathrm {Var}\left[ Y_\lambda \right] > \mathbb {E}\left[ X_\lambda \right] - \alpha \cdot \mathrm {Var}\left[ X_\lambda \right] \).

Let \(\psi _\lambda =1-\delta ^{B-b_\lambda +1}\); we will find the condition satisfying:

Let \(u(T_\lambda -1) - 2 = \beta M\). Then,

Since \(1\le b_\lambda \le B\), the lower bound of \(\psi _\lambda \) becomes \(\psi _\lambda \ge 1 - \delta \). Then, we obtain a sufficient condition for (4) as follows:

For \(\beta \ge \sqrt{\frac{1+\alpha }{\alpha }}\), Eq. (5) always holds since the upper bound of the right term becomes \(\frac{1+\alpha }{\alpha }\). Note that \(0\le \delta <1\). Thus, we finally obtain the condition under which Eq. (4) holds as follows:

Due to the underestimation of \({{\textsc {FURL}}_{\textsc {W}}}\), \(\mathbb {E}\left[ Y_\lambda \right] + \alpha \cdot \mathrm {Var}\left[ Y_\lambda \right] < \mathbb {E}\left[ X_\lambda \right] + \alpha \cdot \mathrm {Var}\left[ X_\lambda \right] \) always holds, which completes the proof. \(\square \)

Lemma 5

Let \(\varDelta _u\) be the true local triangle count for a node u and \(Y_u\) be the estimation given by FURL for node u. Then,

Proof

Let \(X_\lambda \) and \(Y_\lambda \) be the estimated count of a triangle \(\lambda \) by FURL-0 and FURL respectively, \(T_\lambda \) be the time \(\lambda \) is formed, and \(T_M\) be the last time we have the exact triangle counts. Let \(\varLambda _u^{-}\) be the set of triangles containing node u that are formed when we have the exact triangle counts, i.e. \(T_\lambda \le T_M\), and \(\varLambda _u^{+}\) be the set of triangles containing node u that are formed when we do not have the exact triangle counts, i.e. \(T_\lambda > T_M\). Note that every triangle containing node u is included in either \(\varLambda _u^{-}\) or \(\varLambda _u^{+}\).

For triangle \(\lambda ^{-} \in \varLambda _u^{-}\),

and for triangle \(\lambda ^{+} \in \varLambda _u^{+}\),

where \(b_\lambda \) is the bucket where a triangle \(\lambda \) is formed and \(W(i)=(1-\delta )\delta ^{b-i}\). Then,

\(1 \le b_{\lambda ^{+}} \le b\) and \(0< \delta < 1\). Thus,

\(\square \)

Lemma 6

Let \(X_u\) and \(Y_u\) be the estimated local triangle count for a node u given by FURL-0 and FURL respectively, \(\varLambda _u\) be the set of triangles containing node u.

where b is the current bucket.

Proof

Let \(X_\lambda \) and \(Y_\lambda \) be the estimated count of a triangle \(\lambda \) by FURL-0 and FURL respectively. Let \(\varLambda _u^{-}\) be the set of triangles containing node u that are formed when we have the exact triangle counts and \(\varLambda _u^{+}\) be the set of triangles containing node u that are formed when we do not have the exact triangle counts.

For triangle \(\lambda ^{-} \in \varLambda _u^{-}\),

and for triangle \(\lambda ^{+} \in \varLambda _u^{+}\),

where \(b_\lambda \) is the bucket where a triangle \(\lambda \) is formed. Let \(\varLambda _u\) be the set of triangles containing node u. Then,

\(1 \le b_{\lambda ^{+}} \le b\) and \(0< \delta < 1\). Thus,

\(\square \)

Theorem 5

Let u(T) be the number of unique edges that have arrived at time T. If \(\delta ^b > 1 - \sqrt{1 - \frac{\mathbb {E}\left[ X_u\right] }{\alpha \mathrm {Var}\left[ X_u\right] }}\), the interval by \(\mathbb {E}\left[ Y_u\right] \pm \alpha \mathrm {Var}\left[ Y_u\right] \) is strictly included in that by \(\mathbb {E}\left[ X_u\right] \pm \alpha \mathrm {Var}\left[ X_u\right] \) for any \(\alpha \).

Proof

We first show that \(\mathbb {E}\left[ Y_u\right] - \alpha \mathrm {Var}\left[ Y_u\right] > \mathbb {E}\left[ X_u\right] - \alpha \mathrm {Var}\left[ X_u\right] \). By Lemmas 5 and 6,

which is developed as follows.

\(0< \delta < 1\). Then, we obtain a sufficient condition as follows:

Thus, we finally obtain the condition as follows:

Due to the underestimation of FURL-0, \(\mathbb {E}\left[ Y_u\right] + \alpha \mathrm {Var}\left[ Y_u\right] < \mathbb {E}\left[ X_u\right] + \alpha \mathrm {Var}\left[ X_u\right] \) always holds, which completes the proof. \(\square \)

Reprints and permissions