Triangle and Four Cycle Counting with Predictions in Graph Streams
Authors: Justin Y Chen
Talya Eden
Piotr Indyk
Honghao Lin
Shyam Narayanan
Ronitt Rubinfeld
Sandeep Silwal
Tal Wagner
David Woodruff
Michael Zhang
Venue: ICLR 2022 Poster (2022)
Keywords: learning augmented
streaming
graph streaming
data driven
cycle counting
triangle counting

Abstract: We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, Hsu et al. (2019) and Jiang et al. (2020) applied machine learning techniques in other data stream problems, using a trained oracle that can predict certain properties of the stream elements to improve on prior “classical” algorithms that did not use oracles. In this paper, we explore the power of a “heavy edge” oracle in multiple graph edge streaming models. In the adjacency list model, we present a one-pass triangle counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle errs. Our methodology expands upon prior work on “classical” streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass or random order was used to implement the heavy edge oracle. Lastly, our experiments demonstrate advantages of the proposed method compared to state-of-the-art streaming algorithms.

Published as a conference paper at ICLR 2022
TRIANGLE AND FOUR CYCLE COUNTING WITH PRE- DICTIONS IN GRAPH STREAMS
Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, and Sandeep Silwal Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology Cambridge, MA 02139, USA {justc, indyk, shyamsn, ronitt, silwal edu
Honghao Lin, David P. Woodruff, Michael Zhang
Computer Science Department Carnegie Mellon University Pittsburgh, PA 15213, USA [honghaol, dwoodruf, (anyyoz)@andren cma edu
Tal Wagner
Talya Eden
Microsoft Research Redmond, WA 98052, USA wagner@gmail. com
Massachusetts Institute of Technology and Boston University Cambridge, MA 02139, USA teden@mit.edu
ABSTRACT
We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles, two fundamental problems in graph analytics that are widely studied in the graph data stream literature. Recently, Hsu et al. (2019a) and Jiang et al. (2020) applied machine learning techniques in other data stream problems, using trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms that did not use oracles. this paper, explore the power of a "heavy edge" oracle in multiple graph edge streaming models. counting algorithm improving upon the previous space upper bounds without such an oracle. In the arbitrary order model, we present algorithms for both triangle and four cycle estimation with fewer passes and the same space complexity as in previ- ous algorithms, and we show several of these bounds are optimal. We analyze our algorithms under several noise models, showing that the algorithms perform well even when the oracle eITs. Our methodology expands upon prior work on "clas- sical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases of our algorithms, where the first pass random order was used to implement the heavy edge oracle. Lastly, our experi- ments demonstrate advantages of the proposed method compared to state-of-the- art streaming algorithms.
the adjacency list model, we present one-pass triangle
INTRODUCTION
Counting the number of cycles in graph is fundamental problem in the graph stream model (e.g., Atserias et al. (2008); Bera & Chakrabarti (2017); Seshadhri et al. (2013); Kolountzakis et al. (2010); Bar- Ros-Yossef al. (2002); Kallaugher al. (2019)). The special case of counting triangles is widely studied, as it has a vast range of applications. In particular, it provides important insights into the structural properties of networks (Prat-Pérez al., 2012: Farkas al., 2011), and used to discover motifs in protein interaction networks (Milo et al., 2002), understand social networks (Foucault Welles et al., 2010), and evaluate large graph models (Leskovec al., 2008). See Al Hasan & Dave (2018) for survey of these and other applications.
'lll authors contributed equally.

---

Published as a conference paper at ICLR 2022
Because of its importance, a large body of research has been devoted to space-efficient streaming algorithms for (1 + -ppprooxietee triangle counting. Such algorithms perform computation in one or few passes over the data using only sub-linear amount of space. A common difficulty which arises in all previous works is the existence of heavy edges, i.e., edges that are incident to many triangles (four eycles). As sublinear space algorithms often rely on sampling of edges, and since single heavy edge can greatly affect the number of triangles (four cycles) in graph, sampling and storing these edges are often the key an accurate estimation. Therefore, multiple techniques have been developed to determine whether a given edge is heavy or not.
Recently, based on the observation that many underlying patterns in real-world data sets do not change quickly over time, machine learning techniques have been incorporated into the data stream model via the training of heavy-hitter oracles. Given access such a learning-bass -haiid oracle, wide range of significant problems in data stream processing - including frequency estimation, esti- mating the number of distinct elements, F- or (k: (t.pp-CCsccade Norms - can all achieve space bounds that are better than those provided by "classical" algorithms, see, c.g., Hsu et al. (2019a); Cohen et al. (2020); Jiang et al. (2020); Eden et al. (2021); Du et al. (2021). More gen- erally, learning- based approaches have had wide success in other algorithmic tasks, such data structures (Kraska et al., 2018 Ferragina et al., 2020; Mitzenmacher, 2018; Rae et al., 2019; Vaidya al., 2021), online algorithms (Lykouris & Vassilvtiskii, 2018; Purohit al., 2018 8; Gollapudi & Panigrahi, 2019; Rohatgi, 2020; Wei, 2020; Mitzenmacher, 2020; Lattanzi et al., 2020; Bamas et al., 2020), similarity search (Wang et al., 2016; Dong et al., 2020) and combinatorial optimization (Dai et al., 2017; Balcan et al.. 2017:
7: 201 8a:b; 2019). See the survey and references therein for additional works (Mitzenmacher & Vassilvitskii, 2020).
Inspired by these recent advancements, we ask: is it possible to utilize a learned heavy edge oracle to improve the space complexity of subgraph counting the graph stream model? Our results demonstrate that the answer is yes.
1.1 OUR RESULTS AND COMPARISON TO PREVIOUS THEORETICAL WORKS
We present theoretical and empirical results in several graph streaming models, and with several notions of prediction oracles. Conceptually, provide exact predictions. While instructive theoretically, such oracles are typically not available in practice. We then extend our theoretical results to noisy oracles that can provide inaccurate or wrong predictions. We validate the practicality of such oracles in two ways: by directly showing they can be constructed for multiple real datasets, and by showing that on those datasets, our algorithms attain significant empirical improvements over baselines, when given access to these oracles.
useful to begin by studying perfect oracles that
We proceed to a precise account of our results. Let = (V, E)) denote the input graph, and let n, m, and T denote the number of vertices, edges, and triangles (or four-cycles) in G, respectively. There are two major graph edge streaming models: the adjacency list model and the arbitrary order model. We show that training heavy edge oracles possible in practice in both models, and that such oracles make it possible to design new algorithms that significantly improve the space complexity of triangle and four-cycle counting, both in theory and in practice. Furthermore, our formalization of a heavy edge prediction framework makes it possible to show provable lower bounds as well. Our results are summarized in Table
In our algorithms, we assume that we know a large-constant approximation of T' for the purposes of setting various parameters. This standard practice in the subgraph counting streaming literature (e.g., see (Braverman et al., 2013, Section 1), (McGregor et al., 2016, Section 1.2) for an extensive discussions on this assumption). Moreover, when this assumption cannot be directly carried over in practice, in Subsection F.3 we discuss how to adapt our algorithms to overcome this issue.
1.1.1 PERFECT ORACLE
Our first results apply for the case that the algorithms given access to perfect heavy edge oracle. That is, for some threshold p, the oracle perfectly predicts whether or not a given edge is incident to at least p triangles (four cycles). We describe how to relax this assumption in Section 1.1.2.
Adjacency List Model All edges incident to the same node arrive together. We show:
2

---

Published as a conference paper at ICLR 2022
Our results compared existing theoretical algorithms. Ag (Av) denotes the maximum number of triangles incident to any edge (vertex), and к denotes the arboricity of the graph.
Table 1:
Problem
Previous Results (no oracle)
Our Results
Triangle,
O(min(E ((min(E=2m* 22 //2/5
O(e3m/ 1-pass (McGregor et al., 2016)
Adjacency
) 1-pass
Ólc-2m2/2/TT) 3-pass (McGregor et al., 2016)
Öle-2m Ole-mm/vT)) 2- 2-pass (McGregor et al., 2016)
O + mmr/T)), 1-pass
Triangle, Arbitrary
(Pagh & Tsourakakis, 2012)
((e-1(m// (t/./mmmm////// (2+
O(e O(e + mmmgmm// + my Av/T)), 2-pass
1-pass
(Kallaugher & Price, 2017)
Óppoly(c (m4g// T + my (T)) 1-pass
(Jayaram & Kallaugher, 2021)
Ópooly( ()oox(()))mxx(T))) multi-pass (Bera Sheshadhri, 2020)
4-cycle, Arbitrary
m(/22m/T1//4 3-pass (McGregor & Vorotnikova, 2020)
Õ + + mm//T/1/3)
O (kc22m// 3-pass (Vorotnikova, 2020)
1-pass
Theorem 1.1. There exists one-pass algorithm, Algorithm 1, with space complexity! O(min(c / cle, returns (1 = e) approximmaion the number T of triangles with probability at least 7/10.
in the adjacency list model that, using learning-based ora-
An overview of Algorithm is given in Section 2, and the full analysis is provided in Appendix B.
Arbitrary Order Model In this model, the edges arrive in the stream in an arbitrary order. We present one-pass algorithm for triangle counting and another one-pass algorithm for four cycle counting in this model, both reducing the number passes compared to the currently best known space complexity algorithms. Our next result is follows:
Theorem 1.2. There exists one-pass algorithm, Algorithm 4, with space complexity Ö (m/vV+ mm) in the arbitrary order model that, using a learning- -hased oracle, returns (1 )-approximaatin to the number T of triangles with probability at least 7 7/10.
An overview of Algorithm is given in Section 3, and full details are provided in Appendix C.
We also show non-trivial space lower bounds that hold even if appropriate predictors available. In Theorem C.2 in Appendix C.3, we provide a lower bound for this setting by giving a construction that requires (minn (aainn/////// /T, m/32//T1 space even with the help of an oracle, proving that our result nearly tight in some regimes. Therefore, the triangle counting problem remains non-trivial even when extra information available.
Four Cycle Counting. For four eycle counting in the arbitrary order model, we give Theorem 1.3 which is proven in Appendix D.
Theorem 1.3. There exists a one-pass algorithm, Algorithm 5, with space complexity Ö(T + 2m//T//3 in the arbitrary order model that, using learning-based oracle, returns (1 e)- approximation to the number T of four cycles with probability at least 7/10.
To summarize our theoretical contributions, for the first set of results of counting triangles in the adjacency list model, our bounds always improve on the previous state of the art due to McGregor et al. (2016) for all values m and T. For a concrete example, consider the case that = O(
We use Ō(f) to denote Off polylog(f))-
The success probability can he 6 by running log(1/6) copies of the algorithm and taking the median.
3

---

Published as a conference paper at ICLR 2022
In this setting previous bounds result in O(m3/4) -space algorithm, while our algorithm only requires O(ym) space (for constant e).
For the other two problems of counting triangles and 4-cycles in the arbitrary arrival model, our space bounds have an additional additive term compared to McGregor al. (2016) (for triangles) and Vorotnikova (2020) (for 4-cycles) but importantly run in a single pass rather than multiple passes. In the case where the input graph has high triangles density, = l(m/ee), our space bound is worse due to the additive factor. When T = O(m/c²), our results achieve the same dependence on m and as that of the previous algorithms with an improved dependency in 6. Moreover, the case T" S m/e² is natural for many real world datasets: for e 0.05, this condition holds for all of the datasets in our experimental results (see Table 2). Regardless of the triangle density, key benefit of our results is that they are achieved in single pass rather than multiple passes. Finally, our results are for general graphs, and make no assumptions on the input graph (unlike Pagh & Tsourakakis (2012); Kallaugher & Price (2017); Bera & Sheshadhri (2020)). Most of our algorithms are relatively simple and easy to implement and deploy. At the same time, some of our results require the use of novel techniques in this context, such the use of exponential random variables (see Section 2).
1.1.2 NOISY ORACLES
The aforementioned triangle counting results are stated under the assumption that the algorithms are given access to perfect heavy edge oracles. In practice, this assumption is sometimes unrealistic. Hence, we consider several types of noisy oracles. The first such oracle, which we refer to K K-noisy oracle, is defined below (see Figure
the Supplementary Section C.2).
Definition 1.1. For an edge = ry the stream, define Ne as the number of triangles that contain both x and y. For a fixed constant K 2 1 and for threshold p we say that oracle Op is K K-noisy oracle for every edge e, 1 K N. S Pr(OOpe)- HEAVY] S K No.
This oracle ensures that if an edge is extremely heavy or extremely light, it is classified correctly with high probability, but if the edge is close to the threshold, the oracle may be inaccurate. We further diseuss the properties of this oracle Section G.
For this oracle, we prove the following two theorems. First, in the adjacency list model, we prove:
Theorem 1.4. Suppose that the oracle given to Algorithm I is K K-noisy oracle as defined in Defimition 1.1. Then with probability 2/3, Algorithm 1 returns a value in (1 + VK e)T, and uses space most (0mine=22' / /T K E mm
Hence, even if our oracle is inaccurate for edges near the threshold, our algorithm still obtains an effective approximation with low space in the adjacency list model. Likewise, for the arbitrary order model, we prove in Theorem C.I that the O( -1 (mm/ /T + /m)) 1-pass algorithm of Theorem 1.2 also works when Algorithm 4 is only given access to a K K-noisy oracle.
The proof of Theorem 1.4 is provided in Appendix 1. and the proof of Theorem C.I is provided in Appendix C.2. We remark that Theorems 1.4 and C. automatically imply Theorems 1.1 and 1.2, since the perfect oracle is automatically a K K-noisy oracle.
(Noisy) Value Oracles In the adjacency list model, when we see an edge xy, we also have access to all the neighbors of either z or y, which makes it possible for the oracle give more accurate prediction. For an edge xy, let Rzy denote the number of triangles {x, 2, y) so that x precedes a and z precedes y in the stream arrival order. Formally, Ray = Iz : for, y, =} E A and <, = <. yl where & <. denotes that the adjacency list of x arrives before that of y in the stream.
Motivated by our empirical results in Section F.7, it is reasonable in some settings to assume have access to oracles that can predict good approximation to Rzy. We refer to such oracles as value oracles.
In the first version of this oracle, we assume that the probability of approximation error decays linearly with the error from above but exponentially with the error from below.
Definition 1.2. Given an edge e, an (a, B) value-prediction oracle outputs a random value p(e) where Epp(e)] S a aR. + B, and Pr(p(e) < R /] > for some constant K and any X > 1.
4

---

Published as a conference paper at ICLR 2022
For this variant, we prove the following theorem.
Theorem 1.5, Given an oracle with parameters (a, 3), there exists a one-pass algorithm, Algo- rithm 2. with space complexity log" returns a (1 + aapproxximatioon to the number of triangles T with probability at least 7/10.
+ mB/TT) in the adjacency list model that
In the second version of this noisy oracle, we assume that the probability of approximation error decays linearly with the error from both above and below. For this variant, we prove that we can achieve the same guarantees algorithms and proofs for both Theorem 1.5 and Theorem B.I appear in Appendix B.2.
Theorem 1.5 up to logarithmic factors (see Theorem B.1). The
Experiments We conduct experiments to verify our results for triangle counting on a variety of real world networks (see Table 2) in both the arbitrary and adjacency list models. Our algorithms use additional information through predictors to improve empirical performance. The predictors data dependent and include: memorizing heavy edges in small portion of the first graph in sequence of graphs, linear regression, and graph neural networks (GNNs). Our experimental results show that we can achieve up to 5x decrease in estimation error while keeping the same amount of edges as other state of the art empirical algorithms, For more details, see Section 4. In Section F.7, we show that our noisy oracle models are realistic for real datasets.
Related Empirical Works On the empirical side, most of the focus has been on triangle counting in the arbitrary order model for which there are several algorithms that work well in practice. We primarily focus on two state-of-the-arr baselines, ThinkD (Shin al., 2018) and WRS (Shin, 2017). In these works, the authors compare to previous empirical benchmarks such as the ones given in Stefani al. (2017); Han & Sethu (2017); Lim & Kang (2015) and demonstrate that their algorithms achieve superior estimates over these benchmarks. There are also other empirical works such as Ahmed et al. (2017) and Ahmed & Duffield (2020) studying this model but they do not compare to either ThinkD or WRS. While these empirical papers demonstrate that their algorithm returns unbiased estimates, their theoretical guarantees on space is incomparable to the previously stated space bounds for theoretical algorithms in Table 1. Nevertheless,
ThinkD and WRS as part of our benchmarks due to their strong practical performance and code accessibility.
Implicit Predictors in Prior Works The idea of using a predictor is implicit in many prior works. The optimal two pass triangle counting algorithm of McGregor et al. (2016) can be viewed as an implementation of a heavy edge oracle after the first pass. This oracle is even stronger than the K- noisy oracle it is equivalent to oracle that is always correct or is under the threshold by a constant multiplicative factor. This further supports our choice of oracles in our theoretical results, as a stronger version of our oracle can be implemented using one additional pass through the data stream (see Section G). Similarly, the optimal triangle counting streaming algorithm (assuming random order) given in McGregor & Vorotnikova (2020) also implicitly defines a heavy edge oracle using small initial portion of the random stream (see Lemma 2.2 in McGregor& Vorotnikova (2020)). The random order assumption allows for the creation of such an oracle since heavy edges are likely to have many of their incident triangle edges appearing in an initial portion of the stream. We view these two prior works as theoretical justification for our oracle definitions. Lastly, the WRS algorithm also shares the feature of defining implicit oracle: some space is reserved for keeping the most recent edges while the rest is used to keep a random sample of edges. This can be viewed specific variant of our model, where the oracle predicts recent edges as heavy.
edge if Ne either exceeds
Preliminaries. G = (V, E) denotes the input graph, and n, m and T denote the number of ver- tices, edges and triangles (or four-cycles) in G. respectively. We use (vv) to denote the set of neigh- bors of node v. and A to denote the set of triangles. In triangle counting, for each ay E E(G), recall that Nay
|2 : (,, E A is the number of triangles incident to edge zy, and Ray = |2 : {x. y, } E A, <, 2 <s yl is the number of triangles adjacent to xy with the third vertex z of the triangle between x and y in the adjacency list order. Table summarizes the notation.
TRIANGLE COUNTING IN THE ADIACENCY LIST MODEL
We describe algorithm with heavy edge oracle, and with a value oracle.
Heavy Edge Oracle. We present an overview of our one-pass algorithm, Algorithm 1, with space complexity of 2m / 1 m/2) given in Theorem 1.1. We defer the pseudocode
5

---

Published as a conference paper at ICLR 2022
and proof of the theorem Appendix B. The adaptations and proofs for Theorems 1.4, 1.5 and B.1 for the various noisy oracles appear in Appendix B.1 and Appendix B.2.
Our algorithm works differently depending on the value of T. We first consider the case that T 2 (m/c)l/2. Assume that for each sampled edge zy in the stream, we can exactly know the number of triangles Ray this edge contributes to T. Then the rate at which we would need to sample each edge would be proportional to Praice R E 2 A Lg/T, /T, where Ag is the maximum number of tri- angles incident to any edge. Hence, our first idea is to separately consider light and non-light edges using the heavy edge oracle. This allows us to sample edges that are deemed light by the oracle at lower rate, Pt. and compute their contribution by keeping track of Rey for each such sampled edge. Intuitively, light edges offer us more flexibility and thus we can sample them with a lower probability while ensuring the estimator's s error does not drastically increase. In order to estimate the contribution due to non-light edges, we again partition them into two types: medium and heavy, according to some threshold p. We then an observation from McGregor et al. (2016), that since for heavy edges Ray > p. it is sufficient to sample from the entire stream at rate ps ~ E <//p. in order to both detect if some edge ay is heavy and if so estimate Ray.
Therefore, it remains to estimate the contribution to T due to medium edges (these are the edges that are deemed non-light by the oracle, and also non-heavy according to the sub-sampling above). Since the number of triangles incident to medium edges is higher than that of light ones, we have to sample them some higher rate P2 > P1. However, since their number is bounded, this is still space efficient. We get the desired bounds by correctly setting the thresholds between light, medium and heavy edges.
When T < (m//)112 our algorithm becomes much simpler. We only consider two types of edges, light and heavy, according to some threshold T/p. To estimate the contribution due to heavy edges we simply store them and keep track of their Rey values. To estimate the contribution due to light edges we sub-sample them with rate e22 A = pp. The total space we use is Ō mm), which is optimal in this case. See Algorithm for more details of the implementation.
Value- Oracle. We also consider the setting where the predictor returns an estimate p(e) of Rg. and we assume R. S. p(e) S a Ree where a 2 1 is an approximation factor. We relax this assumption to also handle additive error as well as noise, but for intuition we focus on this case. The basue oracle setting requires the use of novel techniques, such as the use of exponential random variables (ERVs). Given this oracle, for an edge e, we compute p(e)/ue, were ue is standard ERV. We then store the (a log(1/c)) edges e for which p(c)/u, is largest. Since we are in the adjacency list model, once we start tracking edge e zy, we can also compute the true value R. of triangles that the edge e participates in (since for each future vertex we see, we can check if x and y are both neighbors of 2). Note that we track this quantity only for the (a (o/e) edges that we store. Using the max-stability property of ERVs, max, R /u, is equal in distribution to T/u, where u is another ERV. Importantly, using the density function of an ERV, one can show that the edge for which Re/u. Re/ue is largest is, with probability 1 - O(22). in our list of the O(a (og( largest p(e)/u, values that we store. Repeating this scheme r 0(1/2) times, we obtain independent estimates T "/u2...,,TT4f T//"", where u² ,",.",' are independent ERVs. Taking the median of these then gives a (1 + e) e)-aprroximation to the total number T of triangles. We note that ERVs are often used in data stream applications (see, e.g., Andoni (2017)), though to the best of our knowledge they have not previously been used in the context of triangle estimation. We also give an alternative algorithm, based on subsampling at O n) scales, which has worse logarithmic factors in theory but performs well empirically.
u²
3 TRIANGLE COUNTING IN THE ARBITRARY ORDER MODEL
In this section we discuss Algorithm 4 for estimating the number of triangles in an arbitrary order stream of edges. The pseudo-code of the algorithm as well as omitted proofs for the different oracles are given in Supplementary Section C. Here we give the intuition behind the algorithm. Our approach relies sampling the edges of the stream as they arrive and checking if every new edge forms a triangle with the previously sampled edges. However, as previously discussed, this approach alone fails if some edges have large number of triangles incident to them as "overlooking" such edges might lead to an underestimation of the number of triangles. Therefore, we utilize a heavy edge oracle, and refer to edges that are not heavy light. Whenever edge arrives, first.

---

Published as a conference paper at ICLR 2022
query the oracle to determine if the edge is heavy. If the edge is heavy keep it, and otherwise we sample it with some probability. As in the adjacency list arrival model case, this strategy allows us to reduce the variance of estimator. By balancing the sampling rate and our threshold for heaviness, we ensure that the space requirement is not too high, while simultaneousyy guaranteeing that our estimate is accurate.
In more detail, our algorithm works as follows. First, we set a heaviness threshold p. so that if we predict an edge
be part of p or more triangles, we label it heavy, We also set a sampling parameter p. We let H be the set of edges predicted to be heavy and let Sr. be random sample of edges predicted to be light. Then, we count three types of triangles. The first counter, 4,, counts the triangles A = (#1. e2, e), where the first two edges seen in this triangle by the algorithm, represented by e1 and 62, are both Sr. Note that we only count the triangle if e and e2, were both in Sr. at the time arrives in the stream. Similarly, l2 counts triangles whose first two edges are in Sy, and H (in either order), and la counts triangles whose first two edges are in H. Finally, we return the estimate L = f1/p² + 2//p f3. Note that if the first two edges in any triangle are light, they will both be in Sz with probability p², and if exactly one of the first two edges is light, will be in Sz with probability p. Therefore, divide & by p² and lg by p that l is an unbiased estimator.
EXPERIMENTS
We now evaluate our algorithm real and synthetic data whose properties are summarized in Table 2 (see Appendix F for more details).
Datasets used in our experiments. Snapshot graphs are sequence of graphs over time (the length of the sequence given parentheses) and temporal graphs are formed by edges appearing over time. The listed values for (number of vertices), (number of edges), and T (number of triangles) for Oregon and CAIDA are approximated across all graphs. The Oregon and CAIDA datasets come from Leskovec & Krevl (2014); Leskovec et al. (2005), the Wikibooks dataset comes from Rossi & Ahmed (2015), the Reddit dataset comes from Leskovec & Krevl (2014); Kumar et al. (2018), the Twitch dataset comes from Rozemberezki et al. (2019). the Wikipedia dataset comes from Rossi & Ahmed (2015), and the Powerlaw graphs are sampled from the Chung-Lu-Vi random graph model with expected degree of the i-th vertex proportional to 1/1² (Chung et al., 2003).
Table 2:
Name
Type
Predictor
m71
T
Oregon
Snapshot (9)
1st graph
10
2.2 10a
1.8 10a
CAIDA 2006
Snapshot (52)
1st graph
2.2 10a
~ 4.5 10a
~ -.4-
CAIDA 2007
Snapshot (46)
1st graph
~ 2.5 10
-01
~ 3.9-
Wikibooks
Temporal
Prefix
10
3.99
~.8- 10
Reddit
Temporal
Regression
~ 3.6
~ 1.2
~ -.
Twitch
GNN
10
~ 107
~ 5.4-
Wikipedia
GNN
10
104
9.9 104
Powerlaw
Synthetic
EV
1.7. 10
~ 10
3.9- 107
We now describe the edge heaviness predictors that we use (see also Table 2). Our predictors adapt to the type of dataset and information available for each dataset. Some datasets we use contain only the graph structure (nodes and edges) without semantic features, thus not enabling us to train classical machine learning predictor for edge heaviness. In those cases we use the true counts on a small prefix of the data (either 10% of the first graph in sequence of graphs, or prefix of edges in temporal graph) as predicted counts for subsequent data. However, we are able to create more sophisticated predictors on three of our datasets, using feature vectors in linear regression or a Graph Neural Network. Precise details of the predictors follow.
Snapshot: For Oregon / CAIDA graph datasets, which contain sequence of graphs, we use exact counting on small fraction of the first graph as the predictor for all the subsequent graphs. Specifically, we count the number of triangles per edge, Ne, on the first graph for each snapshot dataset. We then only store 10% of the top heaviest edges and use these values as estimates for edge heaviness in all later graphs. If a queried edge is not stored, its predicted N. value is 0.
7

---

Published as a conference paper at ICLR 2022
In the WikiBooks temporal graph, the exact Ne counts on the first half of the graph edges (when sorted by their timestamps) as the predicted values for the second half.
Prefix:
Linear Regression: In the Reddit Hyperlinks temporal graph, we use a separate dataset (Kumar et al., 2019) that contains 300-dimensional feature embeddings of subreddits (graph nodes). Two embeddings are close in the feature space if their associated subreddits have similar sub-communities. To produce an edge [(e) embedding for an edge e uv from the node embedding of its endpoints, f(u) and f(v). we use the 602-dimensional embedding - [I[(())
(f(u), f(v), given the edge embedding fe). Training is done on prefix of the first half of the edges.
- [l(ff())
(()) We then train a linear regressor to predict Ne.
Link Prediction (GNN): For each of the two networks, we start with a graph that has twice as many edges as listed in Table 2, (~ 1.1 - 10 edges for Twitch and 9.2 10 edges for Wikipedia). We then randomly remove 50% of the total edges to be the training data set, and use the remaining edges as the graph we test on. We use the method proposed in Zhang & Chen (2018) to train link prediction oracle using a Graph Neural Network (GNN) that will be used to predict the heaviness of the testing edges. For each edge that arrives in the stream of the test edges, we use the predicted likelihood of forming an edge given by the the neural network to the other vertices as our estimate for Nu.. the number of triangles edge wv. See Section F.2 for details of training methodology.
Expected Value (EV): In the Powerlaw graph, the predicted number of triangles incident to each No is its expected value, which can be computed analytically in the CLV random graph model.
Baselines. We compare our algorithms with the following baselines.
ThinkD and WRS (Arbitrary Order): These are the state the art empirical one-pass algorithms from Shin et al. (2018) and Shin (2017) respectively. The ThinkD paper presents two versions of the algorithm, called 'fast' and 'accurate'. We use the 'accurate' version since it provides better estimates. We the authors' code for our experiments (Shin et al., 2020; Shin, 2020).
MVV (Arbitrary Order and Adjacency List): We use the one pass streaming algorithms given in McGregor et al. (2016) for the arbitrary order model and the adjacency list model.
Error measurement. We measure accuracy using the relative error |1 - T/TT, where T is the true triangle count and T is the estimate returned by algorithm. Our plots show the space used by an algorithm (in terms of the number of edges) versus the relative error. We report median errors over 50 independent executions of each experiment, + one standard deviation.
4.1 RESULTS FOR ARBITRARY ORDER TRIANGLE COUNTING EXPERIMENTS
In this section, we give experimental results for Algorithm 4 which approximates the triangle count in arbitrary order streams. Note that need to set two parameters for Algorithm 4: p. which is the edge sampling probability, and p. which is the heaviness threshold. In our theoretical analysis, we assume knowledge of lower bound on T in order to set p and p. as is standard in the theoretical streaming literature. However, in practice, such an estimate may not be available; in most cases, the only parameter we are given is space bound for the number of edges that can be stored. To remedy this discrepancy, we modify our algorithm slightly by setting a fixed fraction of space to use for heavy edges (10% of space for all of our experiments) and setting p correspondingly to use up the rest of the space bound given as input. See details in Supplementary Section F.3.
Oregon and CAIDA In Figures ((a) and 1(b), we display the relative error as function of in- creasing space for graph #4 in the dataset for Oregon and graph #30 for CAIDA 2006. These figures show that our algorithm outperforms the other baselines by as much as factor of 5. We do not display the error bars for MVV and WRS for the sake of visual clarity, but they are comparable to larger than both ThinkD and our algorithm. A similar remark applies to all figures in Figure 1. As shown in Figure 2, these specific examples are reflective of the performance of our algorithm across the whole sequence of graphs for Oregon and CAIDA. We also show qualitatively similar results for CAIDA 2007 in Figure 4(a) in Supplementary Section F.4.
We also present accuracy results over the various graphs of the Oregon and CAIDA datasets. We fix the space to be 10% of the number of edges (which varies across graphs). Our results for the Oregon dataset are plotted in Figure 2(a) and the results for CAIDA 2006 and 2007 are plotted in
8

---

Published as a conference paper at ICLR 2022
Oesgen, Stope4e
CuRl-2305 Crastwo3
Ressltypatro Crast
Ourdip
T1a
Thikk
0.20
0.15
20.20
6.25
6:20
1:05
0:25
0.00
1:00
1:10
4:10
6:30
1-10
25
Spare
Space
(a) Oregon
(b) CAIDA 2006
(c) Reddit
3.40
Wiltoott Dugh
UNNcesaco Crach
Penetiow Depp
0.34
Cur
6.06
1.3--
3345
Think
00.37
0.32
Thin
0.12
6.00
0.24
Thi
3300
0.04
0.65
26:00
0.64
0.34
3.5
0.82
3.0
1:10
6.10
6:00
1:10" 2:10
6:30
Space
Spaie
Space
(d) Wikibooks
(c) Wikipedia
(f) Powerlaw
Figure 1: Error as function of space in the arbitrary order model.
OurAtg WAs
Our Agg MRRS
0.24
WRO
Faldiee Dre
8.15
0.00
0.65
6:00
0.4
0.2
038
(a) Oregon
(b) CAIDA 2006
(c) CAIDA 2007
Figure 2: Error across snapshot graphs with space 0. 0.1m in the arbitrary order model.
Figures 2(b) and 2(c), respectively. These figures illustrate that the quality of the predictor remains consistent over time even after a year has elapsed between when the first and the last graphs were created as our algorithm outperforms the baselines on average by up to a factor of 2.
Reddit Our results are displayed in Figure Icc). All four algorithms are comparable as we vary space. While we do not improve over baselines in this case, this dataset serves to highlight the fact that predictors can be trained using node or edge semantic information (i.e., features).
Wikibooks and Powerlaw For Wikibooks, we see in Figure ((d) that our algorithm is outperform- ing ThinkD and WRS by least a factor of 2, and these algorithms heavily outperform the MVV algorithm. Nonetheless, it is important to note that our algorithm uses the exact counts on the first half of the edges (encoded in the predictor), which encode a lot information not available to the baselines. Thus the takeaway is that in temporal graphs, where edges arrive continuously over time (e.g., citation networks, road networks, etc.), using a prefix of the edges to form noisy predictors can lead to significant advantage in handling future data on the same graph. Our results for Powerlaw are presented in Figure (ff). Here too we see that as the space allocation increases, our algorithm outperforms ThinkD, MVV, and WRS.
Twitch and Wikipedia In Figure I(e), we see that three algorithms, ours, MVV, and WRS, are all comparable we vary space. The qualitatively similar result for Twitch is given in Figure 4(b). These datasets serve to highlight that predictors can be trained using modern ML techniques such as Graph Neural Networks. Nevertheless, these predictors help our algorithms improve over baselines for experiments in the adjacency list model (see Section below).
Results for Adjacency List Experiments Our experimental results for adjacency list experiments, which are qualitatively similar to the arbitrary order experiments, are given in full detail in Sections F.5 and F.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
Justin is supported by the NSF Graduate Research Fellowship under Grant No. 1745302 and Math- Works Engineering Fellowship. Sandeep and Shyam are supported by the NSF Graduate Research Fellowship under Grant No. 1745302. Ronitt was supported by NSF awards CCF-2006664, DMS 2022448, and CCF- 1740751. Piotr was supported by the NSF TRIPODS program (awards CCF- 1740751 and DMS-2022448), NSF award CCF-2006798 and Simons Investigator Award. Talya supported in part by the NSF program, award CCF-174075 and Ben Gurion University Postdoctoral Scholarship. Honghao Lin and David Woodruff would like to thank for partial support from the National Science Foundation (NSF) under Grant No. CCF-1815840.
REFERENCES
Nesreen Ahmed and Nick Duffield. Adaptive shrinkage estimation for streaming graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 10595-10606. Curran Asso- ciates, Inc., 2020. URL https: httpps://proceeddnggs neurips wttparis..ccpppp..eeeeeap cccppaper/222//ELL TBC661ccba55c6000001110ccc.aa.11 Paper.... pdf.
Nesreen K. Ahmed, Nick Duffield. Theodore L. Willke, and Ryan A. Rossi. On sampling from massive graph streams. Proc. VLDB Endow. 10(11):1430-1441 August 2017. ISSN 2150- 8097. doi: 10. 10.1477783113662833376666 URL https: /ttp://oiiiio www.:oo...oo....ooooooeeooooo 14778 31376288 3137651.
Mohammad Al Hasan and Vachik S Dave. Triangle counting in large networks: review. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 8(2):e226, 2018.
Alexandr Andoni. High frequency moments via max-stability. In 2017 IEEE International Confer- ence on Acoustics, Speech and Signal Processing, ICASSP 2017, New Orleans, LA, USA, March 5-9, 2017, pp. 3364-6368 IEEE, 2017.
Alexandr Andoni, Collin Burns, Ying Li, Sepideh Mahabadi, and David P. Woodruff. Streaming complexity of svms. In APPROX-RANDOR 2020.
Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cam- bridge University Press, 1999. doi: 10.1017/CB0978051 1622666
Albert Atserias, Martin Grohe, and Daniel Marx. Size bounds and query plans for relational joins. In 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning-theoreti foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pp. 213-274. PMLR, 2017.
Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning branch. In International Conference Machine Learning, 2018a.
Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 603-614. IEEE, 2018b.
Maria-Florina Balcan, Travis Dick, and Manuel Lang. arXiv:1907.00533. 2019.
Learning to link. arXiv preprint
Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learning aug- mented algorithms. In Advances Neural Information Processing Systems, 2020.
Ziv Bar- Yosse, Ravi Kumar, and D. Sivakumar. Reductions in streaming algorithms, with ap- plication to counting triangles in graphs. In 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 2002.
Suman K. Bera and Amit Chakrabarti. Towards tighter space bounds for counting triangles and other substructures in graph streams. In Symposium on Theoretical Aspects of Computer Science (STACS 2017), 2017.
10

---

Published as a conference paper at ICLR 2022
Suman K. Bera and C. Sheshadhri. How the degeneracy helps for traingle counting in graph streams. In ACM Symposium on Principles of Database Systems, June 2020.
Vladimir Braverman, Rafail Ostrovsky, and Dan Vilenchik. How hard is counting triangles in the streaming model? In International Colloquium on Automata, Languages, and Programming, pp. 244-254 254. Springer, 2013.
Fan Chung, Linyuan Lu, and Van Vu. The spectra of random graphs with given expected degrees. In- ternet Math., 1(3):257-274, 2003. URL im. ht4/119919095
org: : 443/
Edith Cohen, Ofir Geri, and Rasmus Pagh. Composable sketches for functions of frequencies: Beyond the worst case. In International Conference on Machine Learning. PMLR, 2020.
Hanjun Dai, Elias Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp- 6351-6361 2017.
Michael Dinitz, Sungjin Im. Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. In Advances in Neural Information Processing Systems, 2021. URL atttss:/aaree org/ alss 021//.1000900 09770.
Yihe Dong, Piotr Indyk, Ilya P Razenshteyn, and Tal Wagner. Learning space partitions for nearest neighbor search. ICLR, 2020.
Elbert Du Franklyn Wang. and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In International Conference on Machine Learn- ing, 2021.
Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wagner. Learning-basse support estimation in sublinear time. In International Conference on Learning Representations, 2021. URL https::////oo.. opee owwerevveiieeeee ee. net. www.www..w..eeeee///e//e
forum? ficrummmmiiiii LOVEHA3YS.
Illes J Farkas, Imre Derényi, A-L Barabási, and Tamas Viesek. Spectra of" real-world graphs: Beyond the semicircle law. In The Structure and Dynamics of Networks, pp. 372-383. Princeton University Press, 2011.
Paolo Ferragina, Fabrizio Lillo, and Giorgio Vinciguerra. Why are learned indexes effective? In International Conference on Machine Learning, pp. 3123-3132. PMLR, 2020.
Brooke Foucault Welles, Anne Van Devender, and Noshir Contractor. Is a "friend" friend? investi- gating the structure of friendship networks in virtual worlds. In CHI 2010 The 28th Annual CHI Conference on Human Factors in Computing Systems, Conference Proceedings and Extended Ab- stracts, pp. 4027-4032 June 2010. ISBN 978 1605589312, doi: 10. 1454/753844..1 1754097. 28th Annual CHI Conference Human Factors in Computing Systems, CHI 2010: Conference date: 10-04-2010 Through 15-04-2010.
Sreenivas Gollapudi and Debmalya Panigrahi. Online algorithms for rent-or-buy with expert advice. In International Conference on Machine Learning, pp. 2319-2327. PMLR, 2019.
Heitor Murilo Gomes, Jesse Read, Albert Bifet, Jean Paul Barddal, and João Gama. Machine learning for streaming data: state of the art, challenges, and opportunities. SIGKDD Explor. 21:6-22 22, 2019.
Guyue Han and Harish Sethu. Edge sample and discard: A new algorithm for counting triangles in large dynamic graphs. In Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Nenworks Analysis and Mining 2017, ASONAM '17, pp. 44-99, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 4781499349932. 3110025.31 10061. URL. ht /tw.///o..oo//////
doi: 10.1145/ waddoi..o. cereii.rr//in 110 41/44//11000 1.5...10000 3110061.
Chen- Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning- algorithms. In International Conference on Learning Representations, 2019a. URL https: /pooereeviiw n form//ormmmmmmm 1eho@gy11.
beasdd based frequency estimation

---

Published as a conference paper at ICLR 2022
Chen-Yo Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning- bearning-based based frequency estimation algorithms. In International Conference on Learning Representations, 2019b.
Zachary Izzo, Sandeep Silwal, and Samson Zhou. Dimensionality reduction for wasserstein
barycenter. In Advances in Neural Information Processing Systems, 2021.
Rajesh Jayaram and John Kallaugher. An optimal algorithm for triangle counting in the stream.
In Approximation, Rundomization, and Combinutorial Oplimization. Algorithms and Techniques (APPROXRANDOM 2021). Schloss Dagstuhl-Leiibniz-Zeenne
für Informatik, 2021.
Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, and David P. Woodruff. Learning- augmented data stream algorithms. In International Conference on Learning Representations, 2020. URL
https: http::://ppprreeee wttp//venneeeeeeeeeeeeeeeeeeeeee net/ wwteeeoouumeieeeeeeeeeeeeettu Lorumm2
John Kallaugher and Eric Price. A hybrid sampling scheme for triangle counting. In Philip N. Klein (ed.), Proceedings of the Ewenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 1778-1797. SIAM, 2017.
John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova. The complexity of count- ing cycles in the adjacency list streaming model. In Proceedings of the 38th ACM SIGMOD- SIGACT-SIGAL Symposium on Principles of Database Systems, PODS '19. pp. 119-133, New York, NY, USA. 2019. Association for Computing Machinery. ISBN 9781450362276. doi: 10.1145/294052.33199666 URL https: http:/dtioooggr///////or /1/ 1141/1155/50 324405294552222 01144052..311990 3319706.
Mihail N. Kolountzakis, Gary L. Miller, Richard Peng, and Charalampos E. Tsourakakis. Efficient triangle counting in large graphs via degree-based vertex partitioning. Lecture Notes in Computer
Science, pp. 15-24, 2010. ISSN 161 1-3499 doi: 10.1007/978-3-644 3-0-778----42--80099 18009-5.. URL http:
//dx. do.. org 100011000000 000000797788 3- 642 125-44118000 642-14499-5--
Tim Kraska, Alex Beutel, Fd Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD), pp. 489-504. ACM, 2018
Srijan Kumar, William L Hamilton, Jure Leskovec, and Dan Jurafsky. Community interaction and conflict on the web. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, pp. 933-943. International World Wide Web Conferences Steering Committee, 2018.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in tem- poral interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1269-1278. ACM, 2019.
Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Online schedul- ing via learned weights. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1859-1877. SIAM, 2020.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http: // //snap. stw.ford..oo.oooo.ooooooooooo edu data, June 2014.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: Densification laws, shrinking diameters and possible explanations. In Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, KDD '05, pp. 177-187, New York, NY, USA. 2005. Association for Computing Machinery. ISBN 159593135X. doi: 10.1145/108 0055//0888800.00 870. 1081893. URL https:
wttg//..114//10..... 11111/001110...118... 1081893.
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, pp. 462-470, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605581934 //doi.org/// 10. 1145/11111111 890 401948.
doi: (0.1144/)001890.44414444 URL https:
Yongsub Lim and U Kang. Mascot: Memory-efficient and accurate sampling for counting local triangles in graph streams. In Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '15, pp. 685-694 New York. NY, USA, 2015. Association for Computing Machinery. ISBN 9781450336642. doi: 10.1145778325582288225 URL https: / /doi. wogg100.0000 11.10011450 /1////...115/278333553 .7832887
12

---

Published as a conference paper at ICLR 2022
Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mixture models at scale via coresets. Journal of Machine Learning Research, 18(160):1-25, 2018. URL http:/ "mmr.. wtw.:/..rggpaaess//..sse httpp/ppppssaaaaaaeeeeeeess http:////11111551111 html.
Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pp. 3296-3305, PMLR, 2018.
M. Mahoney. Large text compression benchmark., 2011.
Andrew McGregor and Sofya Vorotnikova. Triangle and four cycle counting in the data stream model. PODS' 20, pp. 445-456, New York, NY, USA, 2020. Association for Computing Machin- ery. ISBN 7781450371087, doi: 10.11553335399533886622 URL https: /ttp:::///oooooo////ooo 1145/3375392 3387652.
Andrew McGregor, Sofya Vorotnikova, and Hoa Vu. Better algorithms for counting triangles in data streams. In ACM June 2016.
Symposium on Principles of Database Systems,
R. Milo, S. Shen-Ore S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: Simple building blocks of complex networks. Science, 298(5594):824 827, 2002. ISSN 0036-8075. doi: 10.1126/science. 199885554.882 URL https:://scieeeeee http:://scceennccc.eeeeeeeeeeee sciencemag. org/ content/
Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems, 2018.
Michael Mitzenmacher. Scheduling with predictions and the price of misprediction. In ITCS, 2020.
Michael Mitzemmacher and Sergei Vassilvitskii. Algorithms with predictions. arXiv preprint SXXv:2000609123: 2020.
Rasmus Pagh and Charalampos E. Tsourakakis. Colorful triangle counting and a mapreduce im- plementation. Inf. Process. Lett. 112(7))777-281, 2012. doi: 10.1016fj...2201112.00.. URL 101 https:/ htttps://do..ogg 111.:/0...11/....... 2p1.:p11.................1...... 2011..2..0000
Arnau Prat-Pérez, David Dominguez-Sal, Josep M Brunat, and Josep-Lluis Larriba-Pey. Shaping communities out of triangles. In Proceedings of the 21st ACM international conference on Infor- mation and knowledge management, pp. 1677-1681, 2012.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. In Advances in Neural Information Processing Systems, pp. 9661-9670, 2018.
Jack Rae, Sergey Bartunov, and Timothy Lillicrap. Meta-learning neural bloom filters. In Interna- tional Conference on Machine Learning, pp. 5271-5280, 2019.
Piyush Rai. Hal Daumé, and Suresh Venkatasuuramannian. Streamed learning: One-pass svms.
ArXiv, abs/0908.0577 2009.
Dhruv Rohatgi. Near-optimal bounds for online caching with machine leamned advice. In Proceed- ings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1834-1845. SIAM, 2020.
Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL hatt:::/networrkeppattoooo com. com.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding, 2019.
C. Seshadhri, Ali Pinar, and Tamara G. Kolda. Fast triangle counting through wedge sampling. In the International Conference Data Mining (ICDM), 2013.
Kijung Shin. Wrs: Waiting room sampling for accurate triangle counting in real graph streams.
2017 IEEE International Conference on Data Mining (ICDM), pp. 1087-1092, 2017.
Kijung Shin. Wrs: Waiting room sampling for accurate triangle counting in real graph streams.
https: //gi::////ee htt///gtttttt thu.. com / jungs/jn//nna /waiiiiaa t bingg_nnnn room, 2020.
13

---

Published as a conference paper at ICLR 2022
Kijung Shin, Jisu Kim, Bryan Hooi, and Christos Faloutsos. Think before you discard: Accurate triangle counting in graph streams with deletions. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 141-157. Springer, 2018.
Kijung Shin, Jisu Kim, Bryan Hooi, and Christos Faloutsos. Think before you discard: Accu- rate triangle counting in graph streams with deletions. https://githhnn www/oiioiiiiee com/kijunga jungs// thinkd, 2020.
Lorenzo De Stefani, Alessandro Epasto, Matteo Riondato, and Eli Upfal. TriEst: Counting local and global triangles in fully dynamic streams with fixed memory size. ACM Trans. Knowl. Discov, Data, 11(4), June 2017. ISSN 1556-4681. doi: 10.1145/305919, URL https:///os 10. 10.1145/3059194
Kapil Vaidya, Eric Knorr, Tim Kraska, and Michael Mitzenmacher. Partitioned learned bloom filter. In International Conference on Learning Representations, 2021.
Sofya Vorotnikova. Improved 3-pass algorithm for counting 4-cycles in arbitrary order streaming. CoRR, 01//2007.13466 2020. URL https: wtwpr/ii.orr/ab////00000 13466.
Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. Learning to hash for indexing big data survey, Proceedings of the IEEE, 104(1):34-57, 2016.
Alexander Wei. Better and simpler learning-augmente online caching. Approximation, Ran- domization, and Combinatorial Optimization. Algorithmss and Techniques (APPROX/RANDOM 2020). Schloss Dagstuhl-Leibniz -Zenriu- für Informatik, 2020.
David P. Woodruff. Sketching tool for numerical linear algebra. Found. Trends Theor. Comput. Sci., 10:1-157, 2014.
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 5171-5181, 2018.
14

---

Published as a conference paper at ICLR 2022
A
NOTATIONS TABLE
Notation
Definition
G
graph G with vertex set V and edge set E
(V, E)
number of triangles
number of edges
T
number of triangles (or 4-cycles)
approximation parameter
total ordering on the vertices according to their arrival the adjacency list arrival model
<
A
set of triangles in G set of 4-cycles in G'
((v)
set of neighbors of node
number of triangles (4-cycles) incident to edge ry, i.e.,
Nau
K=|(z, 2) E AH ( [[w,zl(es y, w.z) [J]
number of triangles 2, where precedes and z precedes y the adjacency list arrival model, i.e.. K=](z, 2, v) A, <. <. v)1
Ray
Ag g
maximum number of triangles incident to any edge
Ay
maximum number of triangles incident to any vertex
Op heavy edge oracle with threshold p
B OMITTED PROOFS FROM SECTION 2
In this section, we prove correctness and bound the space of Algorithm 1, thus proving Theorem 1.1. In the adjacency list model, recall that we have total ordering on nodes <, based on the stream ordering, where <s if and only if the adjacency list of arrives before the adjacency list of in stream. For each ay E E(G), we define Ray |2 {a, y, =} E and x <, <. y/- Note that if y <, then Ray- = 0. It holds that EEyEE Ryy = T.
We first give detailed overview of the algorithm. We first consider the case when 2 (m/e)2/2, Let = (mT) We define the edge zy to be heavy Rey 2 p. light if Rzy S L. and medium T R.y < p. We train the oracle predict, upon seeing xy, whether Rey is light not. We define H, M, and as the set of heavy, medium, and light edges, respectively. Define Tr, = E Rey- We define Th and TM similarly. Since EnyeE Rey = T Tr + TM + Th. it suffices to estimate each these three terms.
P
For the light edges, shown in Lemma B.2, if we sample edges with rate pl - with high probability we obtain an estimate of Ty within error =eT. For the heavy edges, we recall an observation in McGregor et al. (2016): for an edge ry where Ray is large, even if we do not sample ay directly, if we sample from the stream (at rate P3 R 22pp), we are likely to sample some edges in the set az {ar, y, =} E and x <, z <. yl- We refer to the sampled set of these edges as Sawe-
Further, will show that not only can we use Saua to recognize whether Ray is large, but also to estimate Rzy (Lemma B.3). What remains to handle is medium edges. Since medium edges have higher values of Ray than light edges, we sample with larger rate, P2, to reduce variance. However, we show there cannot be too many medium edges, so we do not pay too much extra storage space. The overall space we use is Ō(E 2m333 1/3)..
When T (m/e)) our algorithm becomes much simpler. Let p vm/c. e. We define the edge xy to be heavy if Ryy T/p. and light otherwise (so in this case all the medium edges become heavy
15

---

Published as a conference paper at ICLR 2022
edges). We directly store all the heavy edges and sub-sample with rate < p estimate Tz. The total space we use Ö(E Vmm), which is optimal in this case. See Algorithm I for more details of the implementation.
Algorithm Counting Triangles in the Adjacency List Model
1: Input: Adjacency list edge stream and oracle O that outputs HEAVY if Rzy 2 T/p and LIGHT otherwise.
2: Output: An estimate of the triangle count T' 3: Initialize At, Am, An, = O, St, SM, Sauz 0
4: if 2 (m/c)!/2 then
5: Set p (mT) 1/3 pı ae 3/-3 min(3e (/T,BBE-p/T,,),_.1 log
6: else
7: Set p= m pı 0. P2 1, P3 7c-2/pp fa, 8, and yy large enough constants.)
8: while seeing edges adjacent to u do
9:
for all ab Sy. SM do
10:
if a. b E (Dv) then Cab Cah + 1. {Update the counter for all the sampled light and medium edges}
11:
for all av Saux do
BRd = {seen av twice). for each incident edge uu do
13:
W.p. Ps: Saux = {wu) Sauzi Bon 0
15:
if (wv) outputs LIGHT then
16:
uv E St then A = A + Cwv. {Finished counting R else w.p. P1, SL {Fu) U.L
17:
18:
else {ue is either MEDIUM or HEAVY)
19:
# = =1= u2 Sanzy Bus 1, N())
20:
# 2 Pap then {ue is HEAVY]
21:
A = An + #
22:
else if wv E SM then
Am Am Cau. (Finished counting R
24:
else
With probability p2. SM {mu} U SM return: A1/pi + Am/pr + An/p3-
25:
Remark B.1. In the adjacency list model, assume the oracle can predict whether Rzy > T or not, where Ray dependent on the node order. This may sometimes be impractical. However, observe that Nay 2 Ray and Σ Nay 3T. Hence, our proof still holds if we assume what the oracle can predict is whether Nay I, which could be more practical assumption.
Recall the following notation from Section 2. define the edge xy to heavy if Ray 2 p. light Rey I T. and medium if T < Rzz < p. We define H, M, and L as the set of heavy, medium, and light edges, respectively. Define Ty = ExgEL Rzy- We define Tи and Thi similarly. Also, recall that since Enyer Ray = = = Ty + TM + Th. it suffices to estimate of these three terms.
p
Lemma B.2. Let A an edge set such that for each edge xy E A, Rzy for some parameter c, and let be a subset of A such that every element in A is included in with probability = for t = 2 c/o, so that 1/T = ar -x-21 independently, for a sufficient large constant a. Then, with probability at least 9/10, have
Σ RyES
Ray
Σ zyEA
Rey + ET
16

---

Published as a conference paper at ICLR 2022
Proof. We let Y Eies R T Eiea fiR,, where f. when i S and f: otherwise. It follows that B[V] = TΛ. Then,
Var|Y] = E[ - E
72
I8
R
Σ
f.f
-Tï
IEA
iØj
S
R
Σ
Rg
-T
SEA
1.j
R
To bound this, we notice that R < I and Σ, R = TA IT, 50
T max R,
R4 ST
T -
T
1 T
EA
a
iEA
By Chebyshev's inequality, we have that
122
Pr[JY - Tal > cT <
T
The following lemma shows that for the heavy edges, we can use the edges we have sampled to recognize and estimate them.
Lemma B.3. Let xy be edge in E. Assume we sample the edges with rate pa Be log n/ in the stream for a sufficiently large constant 33 and consider the set
# = lxz has been sampled {x, y, 2 E A and < <a yl
Then we have the following: if Ray 2 2. with probability at least 1 - 1
noo we have P3 1-1 #
(1 = Buy If Rzy G. with probability at least 1 n. we have P3 < p.
Proof. We first consider the case when Ray 2 g.
{x, y, 2} E A and x <, <, yl. let X, = if i has been sampled, or X; otherwise. We can see the X; are i.i.d. Bernoulli random variables and E[X,] = Ps. By Chernoff bound we have
For each edge E |rz
Pr
ΣΣ X,
1 Pa 2 cp3 Roy S 2exp (-ēpp Ray/3) S n2
Therefore, we have
Pr [155 Alternatively, when Ray < G. we have
1 # Rayl 2 cRry]
=Pr P3 E X; Rayl 2 cRuy
5
n2
Pr P3 # Rayl 2 5
-Rayl
5
n
which means p. # < with probability at least 1 - n5.
We now ready prove Theorem 1.1, restated here for the sake of convenience.
17

---

Published as a conference paper at ICLR 2022
Theorem 1.1. There exists one-pass algorithm, Algorithm 1, with space complexity? O(min(c- 2/ 222/3 (TU/,,_mm!!22) in the adjacency list model that, using learning-baseee -aaggd ora- cle, returns (1 + -paaproxxmaation to the number T of triangles with probability at least 7 7/10.
Proof. We first consider the case when T (m/e)1/2
1- For each edge zy HI from Lemma B.3 we have that with probability at least 1- ,.. #/p3 (1 + Rxy in Algorithm 1. ay & H. then with probability 1 A zy will not contribute An- Taking a union bound, we have that with probability at least 1 1/n2.
An/pa (1
Σ Ray c)TH
ZyEH
We now turn to deal with the light and medium edges. For light edge ry, it satisfies Ray S T/p and therefore we can invoke Lemma B.2 with the parameter set to p. For a medium edge zy. it satisfies Ray S p = (T(T/p) p). and therefore we can invoke Lemma B.2 with the parameter e set to T/p. Hence, have that with probability 4/5,
Am/P2 = TM ET, Ar/pi = - ET.
Putting everything together, we have that with probability 7/10,
|Aa/Ps + Am/P2 + At/p1 T S 3cT.
Now we analyze the space complexity. We note that there are at most p medium edges. Hence, the expected total space we use is O(mps + PP2 + mp1) 2m233 / logn)².
When T (m/e)l/2, described in Section We will save all the heavy edges and use sub-sampling to estimate Tz. The analysis is almost the same.
only have classes of edges: heavy and light.
B. NOISY ORACLES FOR THE ADIACENCY LIST MODEL
Proof of Theorem 1.4. We first consider the case that T < (m/e))/2 Recall that at this time, our algorithms becomes that we save all the heavy edges zy such that p(e) 2 eT/ ymm and sampling the light edges with rate pt 6 6-1 m. We define L as the set of deemed light edges, H as the set of deemed heavy edges and C). H [71.. Let p = cT//m, then we have the condition that for every edge e,
S Pr(Ople) = HEAVY] K. R
1- K
Re
We will show that, (i) E[H) S ()+ -T (ii) Var[Ar/pil S (4K + 2222 Under the above appprxximaai
conditions we can get that with probability at least 9/10 we can get of T by Chebyshev's inequality.
For (i), we divide 7 Hn. U Hi, where the edges in Hn are indeed heavyedges, and the edges in Hi are indeed lightedges. Then, easy to see that Hal S T/p. For every light edges, the probability that it included in Hl is at most K- R. hence we have
H < K.
Σ oEH
R <K <
T
K mm
P
P
which implies E(H]- (K 1) m
For (ii), we also divide L = L U Lu similarly. Then we have [ar[Ar] < 2[Var[X] + Var(Y]).
where X Exety has been sampled P.. Y Ene Ln,, sampled R.. Similar to the proof in
Lemma B.2, we have
Var Sp Σ R S PI T p =PTPP P
WWe use Ö(f) to denote O(f .flylolll)))
*The success probability can he by running log(1 /5) copies of the algorithm taking the median.
Usinn Markov's 's inequality, we have that with probability at least 9/10, '0, the total space use is less than 10 times the expected total space.
18

---

Published as a conference paper at ICLR 2022
Now we bound Var[Y]. For every heavy edge we have that Pr/e Lnl S K R. Then, condition on the oracle Op, we have
B[Var[Y|Op]] P Σ
P Re
Rhe
SPiK
Σ
pR. PPKPT
eEHl
eER
Also, we have
Var[E[V|op]] < k
Σ P
EEN Re
From Var[X] = [[ + Var [ we know Var[Y] S 2p1 KPT, which means Var[Ar/pil S |. (4K + 2)pl (4K + 2)
When T 2 lm/ recall that the oracle Op only needs to predict the edges that are medium edges or light edges. So, we can use the same way to bound the expected space for the deemed medium edges and the variance of the deemed light edges.
B.2 A VALUE PREDICTION ORACLE FOR THE ADIACENCY LIST MODEL
In this section, consider two types of value- prediction oracles, and variants of Algorithm I that take advantage of these oracles. Recall that given an edge zy, Rzy = |a {x, y, 2} E A and x <a <, y/
Definition B.4. A value-prediction oracle with parameter (ox, 3) is oracle that, for any edge e, outputs value p(e) for which E[p(e)] S aRe + B, and Prip(e) < 4 B] S Ke for some constant K and any À 2
R.
Our algorithm based on the following stability property of exponential random variables (see e.g. Andoni (2017))
Lemma B.5. Let I1, 32, In > O be real numbers, and let u1, Un, be i.id standard exponential random variables with parameter X 1. Then have that the random variable max 21 Ne. ~ E. where a = E, xs and u ~ Exp(1).
Lemma B.6. Letr = 0(m(118)/e) and E S 1/3. we take independent samples X1, X2. .., X₁ from Exp(1) and let X = median (X1, X2, .... Xx), then with probability 1 6, X E [ <), 2 101++00 5.)].
c, 1/2 c). Proof. We first prove the following statement: with probability 1 1 5, F(X) E - where is the cumulative density function of a standard exponential random variable.
Consider the case when F(X) < 1/2 - We the indicator variable Z; where 7, if F(X,) S 1/2 < or Z; = 0 otherwise. Notice that when F(X) S 1/2 - c, at least half of the Z, are so Z Σ. Z; 2 r/2. On the other hand, have E[2] r/2 re, by Chernoff bound. We thus have
Pr[ E[Z]| 2 crl < 2e 2//3 2 8/2.
Therefore, we have with probability at most 8/2, F(X) < 1/2-c. Similarly, we have that with probability at most 6/2, F(X) 2 1/2+t + e. Taking a union bound, we have that with probability at least 1 - 8, F(X) E [1/2 e, 1,1/2
Now, condition on F(X) E [1/2-1 -,, 1/2 + c). Note that F-) = In(1 - x), so if we consider the two endpoints of F(X), we have
F- (1/2 - c) 1n-In(1//2
and
F (1/2+ - - In(1/2 < (1 + 5E) In
which indicates that X E [In 2(1 - 2n + 5c)].
The algorithm utilizing this oracle is shown in Algorithm 2. As described in Section 2. here runs ( copies of the subroutine and takes a medium of them. For each subroutine, we aim to output the maximum value max, Re/uc- ue- We will show that with high probability for each subroutine,
19

---

Published as a conference paper at ICLR 2022
the edge e, such that (Re - -B)/ug is larger than T/ log /). However, one issue here is we need the information of T. We can remove this assumption when 3 using the following way: probability, the total number of edges we save is less than H O ( log (K/e)(a
this maximum will be at least T/ (K/).. Hence, only need
will show that with high m33/T) T)/T)), so every time when a new edge comes, we can search the minimum value M such that the total number of edges& that in at least multiple times if it occurs in multiple subroutines), then use M as the threshold. We can see M will increase as the new edge arriving and it will be always less than H.
subroutine (p(e) + 3) the M is less than ((we count edge
Algorithm 2 Counting Triangles in the Adjacency List Model with Value Prediction Oracle
1: Input: Adjacency list edge stream and an value prediction oracle with parameter(a,
2: Output: An estimate of the number T of triangles.
3: Initialize X 0 and = O log" (K/c)(a + m3/T)), and let e be some large constant.
4: for i = 0 to ce -2 do (Initialize sets for -2 copies of samples, where S; stores edges, Q; stores all the exponential random variables for each sampled edge, and A; stores the current maximum of each sample}
5: S + 0, Q' - 0, and A'' +
6: while seeing edges adjacent to y in the stream do
7:
for - 0 to c do (Update the counters for each sample)
8:
For all ab E S:: if a, b E N (y) then C² t Cab +
9:
for each incident edge ye do for i = to ce - do
10:
if zy E St then (Finished counting Czys update the current maximum) } A max(A', Ciyy ("ay)
12:
else (Put yo into the sample sets temporarily] Let Ryr be the predicted value of Ryz. Ryg < Rye + S. Generate U/y ~ Exp(1). Set Q' < Q' U fui + S' {yz}.
15:
16:
17:
Set M to be the minimal integer such that Σ, 8 H. where s; kef E R./v, My)-
18:
for to do (Adjust the samples be within the space limit]
Let Q' + Q' S S³ {ab) if Rat/u's < M for all ab E E.
20: for i = 0 to c do
21:
X (A')
22:
return: 1n2 median(X)
We are now ready to prove Theorem 1.5. We first recall the theorem.
Theorem 1.5. Given an oracle with parameters (), there exists a one-pass algorithm, Algo- rithm 2, with space complexity O(c-2 (K/))(/ mB m)) in the adjacency list model that returns a (1 + -aapproxximation to the number of triangles T with probability at least 7/10.
Proof. is easy to see that for the i-th subroutine, the value f(i) max R, Re/uf is the sample from the distribution T/u, where ~ Exp(1). And if the edge e,, for which the true value Re./ / is the maximum value among E, is included in St, then the output of the i-th subroutine will be sample from T/u. Intuitively, the prediction value p(e) will help us find this edge.
We will first show that with probability at least 9/ 10 the following events will happen:
(i) f(i) aT/Loo(1// for all i, where c₁ is constant.
(ii) Let s; be the number of the edge e the i-th subroutine such that (p(e) + B)/W 2 GT/ (K/e), then Σ, s; I c2( log (K/ (/Ke)((aa + mB/T)) for some constant C2.
(iii) p(es) B (i) (/e( for all i.
20

---

Published as a conference paper at ICLR 2022
For (i), recall that f(i) T/u where Exp(1). Hence, we have
Pr(f(i) < CT//lo/(1//// = =e" log(1/e)/o1 < 100c c²
Taking an union bound we get that with probability at least 99/100, (i) will happen. For each edge have
Prip(e) + < Re/A] < Ke-A, similarly we can get that with probability at least 99/100, (iit) will happen.
For (it), we first bound the expectation of 8;. For each edge we have
Pr [p(()) + B)/u² 2 cTT/ log (K/c)] Priue ue S ci(p(e) (Kge
I (p(e) + log (K/c)/T
(Kg//)))
S (aR. + 23) log (K/e)/T.
Hence, we have
2 (aRe + 23) log (K/e) = (K/c)(( + m3/T)).
E[ss] Σ
T
Using Markov's inequality, we get that with probability at least 99/100, (ii) will happen. Finally, taking a union bound, we can get with probability least 9/10, all the three events will happen.
Now, conditioned on the above three events, we will show that the subroutine will output f(i). For the subroutine i, from (ix) we know that M will be always smaller than O(T/ (K/c)), and from (i) and (iit) we get that (p(e:) + / 2 Q(T log" (K/e)). Hence, the edge e, will be saved in the subroutine i. From Lemma B.6 get that with probability at least 7/10, can finally get (1 + J-approximation of T.
We note that when B O, the space complexity will become 0 (K/e)a),, and in this case we will not need lower bound of T.
We will also consider the following noise model.
Definition B.7. A value-prediction oracle with parameter (a. is an oracle that, for any edge e, outputs value p(e) for which Pr(p(e) > XaRe - 3] < X constant K and any À 2
K and Prip(e) < R
x B] < X for some
K
The algorithm for this oracle is shown in Algorithm 3.
We now state our theorem.
Theorem B.1. Given an oracle with parameter (a, 3), there exists a one-pass algorithm, Algo- rithm with space complexity O (a(logn)& log logn + mB/T)) in the adjacency list model that returns a (1 VK. -KKee))apppriiiii apppppoxximtoionn to T with probability at least 7/10.
Proof. Define q(e) = p(e) + 9, it easy to see that from the condition we can get that
Rs
Pr Pr(g(e) 22a S K_ when R. 23, Pr
q(e)
K
A
We define the set E, such that e e E, if and only if q(e) 4, We can see E|A pt]] EeEF, Re.
Now, we bound Var[A./p) when i 1.
Let X = EeEE, R. and Y = E,EE, Re, then we have Var[A,] 5 2[[Var[X]
(Yr(Y]).
Similar to the proof in Lemma B.2, we can get that
[ar[X] S ps
Σ
R <
(1(22+1B))
2i+13 p,2 2 BT.
T
52
21

---

Published as a conference paper at ICLR 2022
Algorithm 3 Counting Triangles in the Adjacency List Model with Value Prediction Oracle
1: Input: Adjacency list edge stream and value prediction oracle with parameter(a, B). 2: Output: An estimate of the number 7 of triangles.
3: Initialize 5 +- 0 and A <- O where i = O (log n) and j = O(log log n). Po = 22/ and p; = cc 2 (logn) /T for some constant c. Define Iu = [0, 26) and I; = 1, (3,2++11)
H f- 0.
4: while seeing edges adjacent to y in the stream do
5: For all ab E S af E (y) then Cas f Cab +
6:
for each incident edge ye do if ag E 5 then
7:
8:
A + A² Cyz
9:
else
10:
Let Ryy be the predicted value of Ryz-
11:
Search i such that (Ryz + (3) E 7,
For each j let S + Sy U {yr} with probability p..
13:
for = 0 to (log n) do
14:
H <- H + median(A!))
15:
return:
For Var[Y], recall that for an edge e such that R. 2 3, we have Prie E Fil S Then, condition on the oracle Og, we have
Kge)
S
R
2 K R.
2 B
V| Spp
Σ
K
Re
=
Σ
R. p:K2
Rr
R
Rs Re224188
And
24+1 3
Var[B|Y|Ool| < Ps
Σ
K
Re = P:K2
Rs
H. 22224+3
From Var = Var + Var [[y] we get that Var[y] S K2,K2 ST, from which (((l(// log TT Using Chebyshev's 's inequality and taking a median over (log log n) independent trials, we can get X, median(A)) satisfies |X -. Rel S vK(e/ / log n)T with probability - 0(1/log n). A similar argument also holds for To. which means that after taking union bound, with probability 9/10, the output of the algorithm 3 is a (1 + VK c)- approximation T.
get that Var(A:/p:] 2?
Var A.] ((((e/
Now we analyze the space complexity of Algorithm
For i 2 1, we have
Ta
E [[ E
Σ
E Esj
+
Σ
[eE E,)
SE
Σ
le E E.]
26-1
R. R.
n
R2,526-18/1
2K
R
Ta
Σ
K
R
+
Ta
I (K + 1) 25-13'
Ta
p(e)
2i-13
2
2
R. 22-22-11 B/a
12/2--//a
and |Fg < m. hence we have that the total expectation of the space is E,P.B( 3
O OK (a(log (lo log log m3/T)).
C OMITTED PROOFS FROM SECTION 3
We first present Algorithm 4, and then continue prove Theorem 1.2. In the following algorithm, for two sets A, B of edges, we let WAD represent the set pairs of edges (u, v), where u E A, e B, and u. share common vertex.
22

---

Published as a conference paper at ICLR 2022
Algorithm 4 Counting Triangles in the Arbitrary Order Model
1: Input: Arbitrary order edge stream and an oracle Op that outputs HEAVY if Nay > p and LIGHT otherwise.
2: Output: An estimate of the triangle count T:
3: Initialize p = max /m 11. p = C max
<2'
P 2.
for constant C.
'vT
4: Initialize f,, f, fa 0. and Sr, H 0.
5: for every arriving edge e in the stream do
6: if the oracle Op outputs HEAVY then
7: Add to H
8: else
9: Add e to St with probability
for each w E St do if (e, w) is triangle then Increment E & +
11:
for each w E WS,. do (e, w) is triangle then Increment la = 82 + 1. for each w E WH.H do 17: if (e, w) is triangle then
13:
14:
15:
16:
18:
Increment lg = l3 1. return: 8 = l//p² + l2pp Es-
19:
C.I
PROOF OF THEOREM 1.2
Recall that we first assume that Algorithm 4 is given access to perfect oracle Op. That is, for every edge e E E,
LIGHT if p HEAVY if > p.
Op(e)
where Ta as the number triangles incident to the edge e.
Theorem 1.2. First, assume that T = If not, our algorithm can just store all of the edges, since E _ m/VT.
For each integer i 2 1, let E(i denote the set of edges that are part of exactly i triangles, and let E, [[)]] Since each triangle has edges, we have that Σ i. E(i) = 37.
Let Ti denote the set of triangles whose first two edges in the stream are light (according to Op). For every triangle t, in T1. let X; denote the indicator of the event that the first two edges of t; sampled to Sz. and let l = E; Xt. Since each X is 1 with probability p². Ex[xi] p², and Var[xi] p²-p" < p². For any two variables Xi, Xj, they must be uncorrelated unless the triangles Xi,
4, share a light edge that is among the first two edges of f; and among the first two edges of tj- P(
Xj 1). This event only happens if the first two edges of both t; and t, are sampled in St. but due to the shared edge, this comprises edges in total, so IP(x= = Xj = 1) p². Hence, if we define 1,2 as the first two edges of 4 in the stream for each triangle t..
Moreover, in this case, Cov(x;, xyl I Ex[x,x3]
Ex[&]] = -Ti
and
Var [1
Σ p²
Σ
pd S PTTI +p3 Σ T
TET
tastyTTi <frre /0
T.Sp
= Ti +
> 2 E() <
(0² + 3p2 p) .T.
The first line follows by adding the covariance terms; the second line follows since each light edge has at most T pairs (t,,t, intersecting at e; the third line follows by summing over t = T., ranging from 1 to p. instead over e; and the last line follows since Ex21 t E()) = 37.
23

---

Published as a conference paper at ICLR 2022
Now, let T2 denote the set of triangles whose first two edges in the stream are light and heavy (in either order). For every triangle t = (e1, 62, 63) in T2, 61, 62 are sampled to St U. with probability p. Also all other triangles have chance to contribute to lz. Hence, Ex Ex[eg] two triangles 44, l E To that intersect on an edge e have Cov X²) * 0 only if is light and e E f22 1,2.. In this case.
p T2. Also,
Cov(X X²) & Ex|x,x] S P.
since if is added Sr. (which happens with probability p) then Xi = Xj the other edges in t ,t, are heavy and are added to H with probability 1. Therefore,
Var[42]
Σ p+
Σ
pz +p+ p) T
fET
4A ! me, Op(e)=LIOHT
by the same calculations as was done to compute Var[fi].
Finally, let T3 denote the set of triangles whose first two edges in the stream are heavy. Then ls T/ll
Now, using the well known fact that Var(X+> s 2 [Var Var for any (possibly correlated) random variables X, Y, we have that
Varlp Pl + p l2 + (s) 2 (p² + 3p² p)T + 30 3pp)TT
<TT 2 + 3p p):
since &a has no variance. Moreover, Ex(p 2( + 1 + Lg] = |Ti + T2 + 1Tl T. So, by
Chebyshev's inequality, since ( l + 22/p E3,
Pr|le - El' Var {
4(p + 3p
T
2.
Therefore, setting p = C max { with probability at least 2/3, l is a (1 + e)-multiplicaative estimate of
1/(E f/), m for some fixed constant C' implies that,
Furthermore, the expected space complexity is O(mp + H) = O(mp + T/p). Setting P = max m implies that the space complexity is "ttm///===mmm=="""" Vm--T/ 0(--Im/ e V T/T),, since are assuming that 7' 2 -2 Hence, assuming that T is constant factor approximation of T,, the space complexity is O 'mm/mm/ I
C.2 PROOF OF THEOREM 1.2 FOR THE K-NOISY ORACLE
In this section, we prove Theorem 1.2 for the case that the given oracle is a K K-noisy oracle, as defined in Definition 1.1. That is, we prove the following:
Theorem C.1. Suppose that the oracle in Algorithum 4 is K-noisy oracle as defined in Defini- tion 1.1 for a fixed constans K. Then with probability 2/3, Algorithu returns & E (1 (1+c)T, e)T, and uses space at most O (e- (m/VT++ +/m)
Recall that in Definition 1.1, defined K-noisy oracle if the following holds. For every edge e, 1-K K E Pr)(p(e) = HEAVY] < K Na, We first visualize this model. To visualize this error
model, Figure we have plotted N, versus the range [ K KK N. for K = 2. We set N. vary logarithmic scale for clarity. For example, if N. exceeds the threshold p by factor of 2, there is no restriction on the oracle output, whereas if N exceeds by a factor of 4, then the oracle must classify the edge as heavy with probability at least 0.5. contrast, the blue piece-wise line shows the probability (e) = HEAVY] if the oracle O, is a perfect oracle.
Proof of Theorem C.I. We follow the proof of Theorem 4.1 from the main paper. Let Tj be the set of triangles such that their first two edges in the stream are light according to the oracle. Let To be the set of triangles such that their first two edges in the stream are determined light and heavy according the oracle. Finally, let Ta be the set of triangles for which their first edges
24

---

Published as a conference paper at ICLR 2022
Probability of e being classified as heavy
0.5
0.0
p/B
P/4
0/2
2p
4p
Bp
Number of triangllss incident to edge
Figure 3: Plot of Ne, the number of triangles containing edge e, versus the allowed oracle probability range Pr(Op(e) HEAVy), shaded in orange. The blue piece-wise line shows the probability (r(Op(e) = HEAVY] if the oracle Op is a perfect oracle.
determined heavy by the oracle. Furthermore, define X for each triangle 44, t(e) for each edge and (i), E; for each 2 1 as done in Theorem 4.1. Finally, we define L(i) as the set of deemed light edges that are part of exactly triangles, and L(i) |C(i)).
First, note that the expectation (over the randomness of O₂)) of L(i) is at most E(i) K K. 4. since our assumption on Pr(Op(e) heavy] tells us that Pr(O,(e) light) < K- if t(e) Therefore, by the same computation as in Theorem 4.1, we have that, conditioning on the oracle, Ex(E1]O,) = (T) and
Var 1ar(4/1pp==
Σ p²
Σ p² &.TEETi
4ET
S <p11Ti +
t(e)2
light
= =>'ITi +
8 L())
But since Exo, [I(t)] K-p E(t) for all we have that
Exo, Var(&r10,]] < Exo,
1Til+++ Ee(())
= + Kpppp E()(
121
< < + +3Kp' p) T
similar analysis to the above shows that Ex(Ez] = pp . |T and that
Exo, (ar (22p S Exo, p. p-1 + +p (T)(1)
121
= + -Kppp
1- )(E()
121
< (p + 3Kp p) .T
Hence, in Theorem 4.1, we have Ex[[(0,] T' and Exo, [arl < 47 3Kp Thus, Ex[e] Ex [x = T and Var Exo, [ar Varo, [x[[[O,]] < 4T 2+
3Kp p)) by the laws of total expectation//aarince. Therefore, since K is constant, the variance is
25

---

Published as a conference paper at ICLR 2022
the same as in Theorem 4.1, up to constant. Therefore, still have that & (1 = O(c)) T with
probability at least 2/3.
Finally, the expected space complexity is bounded by
mpp + Σ Pr(OO(e)= = heavy] 5 mmp +
Σ
E(I)
t
6Em
121
K
- mp +
E(I)
P
121
= =0mpp+ T/p)),
since Σ121 E(t) == 3T and K = O(1). Hence, setting and as in the proof of Theorem 4.1 implies that the returned value is (1 = e)approximatiinn of T, and the the space complexity is O (m//mm/TTTT + vm) as before.
C.3 LOWER BOUND
In this section, we prove lower bound for algorithms in the arbitrary order model that have access perfect heavy edge oracle. Here heavy means Nov 2 T/c for a pre-determined threshold c, and we assume = o(m) and T/c > 1, as otherwise the threshold will be too small or too close to the average give an accurate prediction. The following theorem shows an (minnmm/ / m3/2 (T)) lower bound even with such an oracle.
Theorem C.2. Suppose that the threshold of the oracle e O(m)), where S g < Then for any T and m, T < m. there exists m' = (mm) and T = ((T) such that any one-pass arbi- trary order streaming algorithm that distinguishes between m' edge graphs with and T triangles with probability at least 2/3 requires (2m/vT) space. For any T and m, T [mm)++)) where max(0, 2) S 8 <. there exists m' = (m) and T = OTT) such that any one-pass arbitrary order streaming algorithm that distinguishes between m' edge graphs with 0 and T' triangles with probability at least 2/3 requires A(m3/22/T) space.
When T' S m, we consider the hubs graph mentioned in Kallaugher & Price (2017).
Definition C.3 (Hubs Graph, Kallaugher & Price (2017)). The hubs graph Hy consists of a single vertex with 2rd incident edges, and d edges connecting disjoint pairs of u's neighbors to form triangles.
is easy to see that in H, each edge has most one triangle. Hence, there will not be any heavy edges of this kind in the graph. In Kallaugher Price (2017), the authors show an M(r lower bound for the hubs graph.
Lemma C.4 (Kallaugher & Price (2017)). Given and d, there exist two distributions G1, G2 subgraphs G1 and G2 of Hy,d. such that any algorithm which distinguishes them with probability at least 2/3 requires M(r d) space, where G3 has ((rd) edges and T(G1) d. T(G2) = 0.
Now, given T and m, where T I m, we let r = O(m/T) and T. We can see Hy has O(m)
edges and 7' triangles, and we need ((rvd) = (mm/ space.
When T > m, we consider the following 3 lower bound in Bera & Chakrabarti (2017).
Let H be complete bipartite graph with b vertices each side (we denote the sides of vertices by A and B). We add an additional N vertex blocks Vi, Vy....V with each [V = d. Alice has an N N-dimensional binary vector x. Bob has an N-dimensional binary vector y. Both and y have exactly N/3 coordinates that are equal to 1. Then, we define the edge sets
Exlice
U ((u.v)u A. i=0;=1
and
EBS
U
B
26

---

Published as a conference paper at ICLR 2022
Let the final resulting graph be denoted by G (V, where V Va U V2 U E = Eµ U EAlice U EBob-
U Vy and
In Bera & Chakrabarti (2017), the authors show by a reduction to the DISJ N problem commu- nication complexity, that we need (NV) space to distinguish the case when G has triangles from the case when G has at least bdd triangles.
Given m and T, T ((m++6) where 5 1/2,, as shown in Bera & Chakrabarti (2017), we can set b = N and d = N where 5 1/(1 - 26). This will make m = ((N2) and T = @(N which will make the (2m3///T) lower bound hold. Note that at this time each edge will have an O 1 }-fraction of triangles or an O 1 )-fraction of triangles. Assume the m ' threshold of the oracle e = O When ó 2 max(0, 2). there will be no heavy edges in the graph.
m
Theorem C.2 follows from the above discussion.
D FOUR-CYCLE COUNTING IN THE ARBITRARY ORDER MODEL
In the 4-cycle counting problem, for each ay E E(G), define Nay |z, {1, v, 2, w) E 0 as the number of 4-cycles attached to edge zy.
In this section, we present the one-pass O + mm//1// space algorithm behind Theorem 1.3 and the proof of the theorem."
We begin with the following basic idea.
Initialize:
+ 0,S + 0. On the arrival edge we:
- With probability p. S + {ur} U.S
C- [[f 2} une, wz and zv E S.
* Return C/p².
Following the analysis in Vorotnikova (2020), we have Var[C] S O(Tp² + TAE + TAwP"),
where Ag and Aw denote the maximum number of 4-cycles sharing a single edge single wedge.
There are two important insights from the analysis: first, this simple sampling scheme can output a good estimate to the number of 4-cycles on graphs that do not have too many heavy edges and heavy wedges (the definitions of heavy will be shown later). Second, assuming that we can store all the heavy edges, then at the end of the stream we can also estimate the number of 4-cycles that have exactly one heavy edge but do not have heavy wedges.
For the 4-cycles that have heavy wedges, we use an idea proposed in McGregor & Vorotnikova (2020); Vorotnikova (2020): for any node pair and v, if know their number of common neigh- bors (denoted by k)), we can compute the exact number of 4-cycles with u, as diagonal pair (i.c., the four cycle contains two wedges with the endpoints u, v), and this counts to (+). Furthermore, if le is large (in this case we say all the wedges with endpoints u. V are heavy), we can detect it and obtain a good estimation to k by a similar vertex sampling method mentioned in Section 3. We can then estimate the total number of 4-cycles that have heavy wedges with our samples.
At this point, we have not yet estimated the number of 4-cycles having more than one heavy edge but without heavy wedges. However, McGregor & Vorotnikova (2020) shows this class of 4-cycles only takes up small fraction of T', and hence we can get (1 + appprxxiimtto to T even without counting this class 4-cycles.
The reader is referred to Algorithm 5 for detailed version of our one-pass, 4-cycle counting algo- rithm. Before the stream, we randomly select node set S, where each vertex is in S with probability
We assume тيल
O(e), which is the same assumption in previous work
27

---

Published as a conference paper at ICLR 2022
Algorithm 5 Counting 4-cycles in the Arbitrary Order Model
1: Input: Arbitrary Order Stream and an oracle that outputs TRUE if Nay T/p and FALSE
otherwise.
2: Output: An estimate of the number T of 4-cycles.
3: Initialize A + 0, AA, f 0, A. +- 0 Ez + 0 Ен 0, Es + 0, and W + 0. Set p T < ac- log n p for a sufficiently large a, and Let S be a random subset of nodes such that each node is in S with probability p.
4: while seeing edge uv in the stream do
5: if u S or v S then
6: Es + [uv} U Es
7:
if the oracle outputs FALSE then
8:
With probability Er, + {uv} E.
9:
Find pair (w, 2) such that uw, wz, and zu E Er, let D <- DU (u,, w, 2,
10: else
11:
EH E U Eh for each node pair (u, v) do
12:
13:
let q(u, v) be the number of wedges with center S and endpoints v and v.
14:
if q(1 v) 2 p/113 then
15:
A + + (9(0.0) W (
(
16:
17:
for each 4-cycle in D do
18:
if the end points of wedges in d are not in W then
At A
20:
for each edge we in EE do for each 4-cycle d formed with uv and E Eg do
22:
if the end points of wedges in d are not in W then
23:
A + An + return: Ar/p² + An/p² + Aw
24:
p independently, and we later store all edges that are incident to S during the stream. In the mean- time, we define the edge ue to be heavy if N.v 72/3 and train the oracle to predict whether heavy not when we see the edge during the stream. Let p Ö(E 2 /33. We store all the heavy edges and sample each light edge with probability during the stream. Upon seeing see light edge uv, we look for the 4-cycles that are formed by and the light edges that have been sampled before, and then record them in set D. At the end of the stream, we first find all the node pairs that share many common neighbors in S and identify them as heavy wedges. Then, for each 4-cycle d E D, we check if d has heavy wedges, and if so, remove it from D. Finally, for each heavy edge we indicated by the oracle, we compute the number of 4-cycles that are formed by we and the sampled light edges, and without heavy wedges. This completes all parts of our estimation procedure.
We now prove Theorem 1.3, restated here for the sake of convenience.
Theorem 1.3, There exists a one-pass algorithm, Algorithm 5, with space complexity Ö(T1/3 1/3 + m3//3333 the arbitrary order model that, using a learning-based oracle, returns a (1 + e)- approximation the number T of four cycles with probability at least 7/10.
Proof. From the Lemma 3 in Vorotnikova (2020), we know that with probability at least 9/10, we get an estimate A. such that
A, Tu, ET.
Where Tie is the number of the 4-cycles that have least one heavy wedge. We note that if a 4- cycle has two heavy wedges. it will be counted twice. However, Vorotnikova (2020) shows that this double counting is at most O(T2/3) = O(c)T.
For the edge sampling algorithm mentioned in D, from the analysis in Vorotnikova (2020), have
Var Bar[At/p3] O(T/p² TAp/p TAw/p²)
28

---

Published as a conference paper at ICLR 2022
Notice that in our algorithm, the threshold of the heavy edges and heavy wedges are Nuv T2/3 and Nw 2 71/3, respectively, which means Var A = O(c27) Hence, we can get an estimate A such that with probability least 9/10,
A Ti
where Tj is the number of 4-cycles that have no heavy edges. Similarly, we have with probability at least 9/10,
A = TT
where Ta is the number of 4-cycles that have at most one heavy edge.
One issue is that the algorithm has not yet estimated the number 4-cycles having more than one heavy edge, but without heavy wedges. However, from Lemma 1 in McGrregor & Vorotnikova (2020) we get that the number of this kind of 4-cycles is at most O(T5/6) O(e) Hence putting everything together, we have
|A/p2 An/p² + A TI S O()),,
which is what we need.
Now we analyze the space complexity. The expected number of light edges we sample is (mm)) = D(c-2m//T//) and the expected number of nodes in S and edges in Es is O(2mp) = 0(--2m/TL/3) The expected number of 4-cycles store in D is O(Tp²) O))- We store all the heavy edges, and the number of heavy edges is at most O(T1/3). Therefore, the expected total space is Ö(T1/3 + mm/TL/3)
E RUNTIME ANALYSIS
In this section, we verify the runtimes of our Algorithms 2, and 5. Proposition E.1. Algorithm runs in expected time at most Ô (min(e- /T1/3 cm1m)12) in the setting of Theorem 1.1, Ö 2mm/n //3 K - mm222) the setting of Theorem 1.4.
Proof. For each edge ab Sy SM, check whether see both and vb (lines 9-10) when looking at edges adjacent to v. So, this takes time |St.| + |Swr per edge in the stream. We similarly check for each edge in Souz (lines 11-12), so this takes time |Savr] Finally, for each edge ou (line 13), we note that lines 14-17 can trivially be implemented in O(1) time, along with call to the oracle. The remainder of the oracle simply involves looking through the set Souz and SM to search or count for elements. Thus, the overall runtime is O(Szz + [SM + [Saaa) per stream element, so the runtime is O (m ([5z) + [SMl + [Saux))).
This is at most O(m S), where S is the space used by the algorithm. So, the run- time is Ö (min(E (mmine-?m5/13 mm/33 / 1m in the setting of Theorem 1.1, and is at most Ō 2 /T1/3, K mm/22) in the setting of Theorem 1.4.
Proposition E.2. Algorithm 2 runs in time ( m3/TTmm
Proof. For each edge ab E S for each 0 S ct -2 we check whether we see both ya and yb in the stream when looking edges adjacent to y. So, lines 7-8 take time O (S"l) for each edge we see in the stream. By storing each St (and each Q*) in a balanced binary search tree or a similar data structure, 12-16 take time Olog n) (since insertion into the data structure for 5' can take time O n))) Since do this for each from 0 to and for each incident edge yæ we see, total we spend O log + S time up to line 16. The remainder of the lines take time O m log n)), since the slowest operation potentially deleting an edge from each S and value from each Q' up to m times (for each edge).
search for xy S in time O(log in line 11, and it is clear that lines
Overall, the runtime is 2 m m Elsi Ö(m S), where S is the total space used by the algorithm. Hence, the runtime is -2 + m33/T)m).
29

---

Published as a conference paper at ICLR 2022
Proposition E.3, Algorithm 3 runs in time Ö(Ke Pa m33
Proof. For each edge ab E S for each 1 I S ((lo n), 1 S S Ollog log n), we check whether we see both ya and yy in the stream when looking at edges adjacent to y. So, line 5 takes time O (s 1) for each edge we see in the stream. By storing each S in balanced binary search tree or similar data structure, we can search for xy St in time O(log n) in line 7, and it is clear that lines 8-12 take time O(log n) (since insertion into the data structure for O can take time (log n)). Since we do this for each i from O to cc 2 and for each incident edge yz we see, in total we spend poly logn- n O (St] time up to line 12. Finally, lines 13- 15 take time poly log n.
Overall, the runtime is Õmm- Σ (S1) = Ö(m- S), where S is the total space used by the algorithm. Hence, the runtime is Õ(Ke (ax + m3 m))
Proposition E.4. Algorithm 4 runs in time Ō m .m
Proof. For each edge e in the stream, first we check the oracle, and we either add e to H or to Sy. with probability p (lines 6-9), which take (1) time. The remaining lines (lines 10-18) involve operations that take ((1) time for each w which represents a pair (e1, 62) of edges where e1, E2 E S2 U H and (e, e e2) forms triangle. So, the runtime is bounded by the amount of time it takes to find all e1, C2 E St. U H such that (1, 62) forms a triangle. If the edge e = (u, v), we just find all edges in Sz. U H adjacent u, and all edges in St U H adjacent to u. Then, sort these edges based on their other endpoint and match the edges if they form triangles. So, the runtime is Ö + [H] per edge in the stream. Finally, line 19 takes 0(1) time.
Overall, the runtime is Ö( ([Sr. + [MD) = =(m S) where S is the total space of the algorithm. So, the runtime is Ô (m- m / + - - mm3/2)
Proposition E.S. Algorithm 5 runs in time Ô (c 2/2//11/3 (n3 +m²)).
Proof. We note that for each edge we in the stream (line 4), the code in the loop (lines 5-11) can be implemented using oracle call and Ö(Err) time. The only nontrivial step here is to find pairs (w, z) such that uw, w.z zu are all in Er. However, by storing E,. in a balanced binary search tree or similar data structure, one can enumerate through each edge wz E Eg and determine if uw and 2v are E, in Oloog [Ez)) time. So, lines 4-11 take time Ō Fz.) per stream element.
Next, lines 12-16 can easily be implemented in time O (S]), lines 17-19 can be easily imple- mented in time O(ID)) if the vertices in W are stored properly, and lines 20-23 can be done in Ö( (Er.)) time. The last part is true since we check each uv E En and e = ('',)') E Er,, and then check if w', o', form a 4-cycle by determining if u, u' and v, v' are in E, U Eh (which takes time (log Ez] + log [H )) time assuming EL, EH are stored in search tree or similar data structure).
Overall, we can bound the runtime as (mm- Er. +n². As each edge is in Eg with probability at most p and each edge is in S with probability at most p. the total runtime is O ((m² + n²) p) = Ō ( (n3 + m²)).
(El) Ö(m- [EI++n2-(S1).
F ADDITIONAL EXPERIMENTAL RESULTS
All of our graph experiments were done on a CPU with i5 2.7 GHz dual core and 8 GB RAM or a CPU with i7 1.9 GHz 8 core and 16GB RAM. The link prediction training was done on a single GPU.
F.1 DATASET DESCRIPTIONS
Oregon: 9 graphs sampled over 3 months representing a communication network of inter- net routers Leskovec & Krevl (2014); Leskovec al. (2005).
30

---

Published as a conference paper at ICLR 2022
98 graphs sampled approximately weekly over 2 years, representing communi- cation network of internet routers Leskovec & Krevl (2014); Leskovec et al. (2005).
CAIDA:
Reddit Hyperlinks: Network where nodes represent sub communities (subreddits) and edges represent posts that link two different sub communities Leskovec & Krevl (2014); Kumar et al. (2018).
WikiBooks: Network representing Wikipedia users and pages, with editing relationships between them Rossi & Ahmed (2015).
Twitch: A user-user social network of gamers who stream in a certain language. Vertices are the users themselves and the links are mutual friendships between them. Rozemberezki et al. (2019)
Wikipedia: This is a co-oceurrence network of words appearing in the first million bytes of the Wikipedia dump. Mahoney (2011)
Synthetic Power law: Power law graph sampled from the Chung-I.u- Vu (CLV) model with the expected degree of the ith vertex proportional to 1/6² Chung et al. (2003). To create this graph, the vertices are 'revealed' in order. When the jth vertex arrives, the probability of forming an edge between the jth vertex and ith vertex for < j is proportional to 1/(1))²
F.2 DETAILS ON LINK PREDICTION ORACLE
Our oracle for the Twitch and Wikipedia graphs is based on Link Prediction, where the task is to estimate the likelihood of the existence of edges or to find missing links in the network. Here we use the method and code proposed in Zhang Chen (2018). For each target link, it will extract a local enclosing subgraph around a node pair, and use a Graph Neural Network to learn general graph structure features for link prediction. For the Twitch network, we use all the training links as the training data for the graph neural network, while for the Wikipedia network, we use 30% of the training links as the training data due to memory limitations. For the Twitch network, our set of links that we will try to predict are between two nodes that have common neighbor in the training network, but do not form a link in the training network. This is about 3.8 million pairs, and we call this the candidate set. We do this for memory considerations. For the remaining node pairs, we set the probability they form a link to be O. For the Wikipedia network, we randomly select a link candidate set of size 20 times the number of edges (about million pairs) from the entire set of testing links. These link candidate sets will be used by the oracle to determine heaviness. Then, we use this network do our prediction for all links in our candidate sets for the two networks.
Now we are ready to build our heavy edge oracle. For the adjacency list model, when we see the edge uv in the stream, we know all the neighbors of u, and hence, we only need to predict the neighbors of v. Let deg(v) be the degree of e in the training graph. The training graph and testing graph are randomly split. Hence, we can use the training set to provide a good estimation to the degree of Next, we choose the largest deg(v) edges incident to from the candidate set, in terms of their predicted likelihood given by the the neural network, as our prediction of N (v)), which leads to estimate of Ruy- For the arbitrary order model, we use the same technique above to predict Nuu) and N (v), and estimate Nav-
F.3 PARAMETER SELECTION FOR ALGORITHM 2
We need set two parameters for Algorithm 2: p, which is the edge sampling probability, and 9, which is the heaviness threshold. In our theoretical analysis, we assume knowledge of lower bound on T in order to set p and 0, as is standard in the theoretical streaming literature. However, in practice, such an estimate may not be available; in most cases, the only parameter we are given is space bound for the number of edges that can be stored. To remedy this discrepancy, we modify our algorithm in experiments as follows.
First, we assume we only have access to the stream, a space parameter Z indicating the maximum number of edges that we are allowed to store, and an estimate of m, the number of edges in the stream. Given Z, we need to designate a portion of it for storing heavy edges, and the rest for storing light edges. The trade-off is that the more heavy edges we store, the smaller probability of light edges would be. We manage this trade off in our implementation by reserving 0.3 Z of the edge 'slots" for heavy edges. The constant 0.3 is fixed throughout all our experiments.
sampling
31

---

Published as a conference paper at ICLR 2022
We then set 0.7 Z/m. To improve the performance of our algorithm, optimize for space usage by always insuring that we are storing exactly Z space (after observing the first Z edges the stream). To do and still maintain theoretical guarantees, we perform the following procedure. Call the first Z edges of the stream the early phase and the rest of the edges the late phase.
We always keep edges in the early phase use our space allocation Z and also keep track of the 0.3-fraction of the heaviest edges. After the early phase is over, i.e., more than Z edges have passed in the stream, if new incoming edge heavier than the lightest of the stored heavy edges, we replace the least heavy stored edge with the new arriving edge and re-sample the replaced edge with probability p. Otherwise, if the new edge is not heavier than the lightest stored edge, we sample the new incoming edge with probability light edges sampled the early phase. Then similarly as before, we re-sample this replaced edge with probability p and continue this procedure until one of the early light edges has been evicted. In the case that there are no longer any of the light edges sampled in the early phase stored, we replace a late light edge and then any arbitrary edge (again performing the re-sampling procedure for the evicted edge).
If we exceed Z, the space threshold, we replace one of the
Note that in our modification, we only require our predictor be able to compare the heaviness be- tween two edges, i.e., we do not need the predictor to output an estimate of the number of triangles on an edge. This potentially allows for more flexibility in the choice of predictors.
If the given space bound meets the space requirements of Theorem C.I, then the theoretical guaran- tees of this modification simply carry over from Theorem 1.2: we always keep the heaviest edges and always sample light edges with probability at least p. In case the space requirements are not met, the algorithm stores the most heavy edges as reduce the overall variance.
F.4 ADDITIONAL FIGURES FROM ARBITRARY ORDER TRIANGLE COUNTING EXPERIMENTS
Additional figures for our arbitrary order triangle counting experiments are given in Figures 4 and 5.
Our Thrrk
Der NG Thxck MVV WRS
0.30
KWV
0.38
WRS
0.15
Reaaive Erre"
0.22
0.30
3.24
0.35
0.32
0.30
0
1:17
1.
5
122
107
10'
0.30
3.
10'
2:12
5:17
4:12
5 10'
(a) CAIDA 2007
(b) Twitch
Figure& 4: Error as a function of space for various graph datasets.
F.5 EXPERIMENTAL DESIGN FOR ADIACENCY LIST EXPERIMENTS
We now present our adjacenely list experiments. At high level overview, similarly the arbitrary order experiments, for our learning- storing the heavy edges. To do this in practice, we can maintain the heaviest edges currently seen so far and evict the smallest edge in the set when a new heavy edge is predicted by the oracle and we no longer have sufficient space. We also consider a multi- layer sub-sampling version of the algorithm in Section B.2. Here we use more information from the oracle by adapting the sub-sampling rates of edges based on their predicted value. For more details, see Section F.5. Our results are presented in Figure 6 (with additional plots given in Figure 7). Our algorithms soundly outperform the MVV bascline for most graph datasets. We only show the error bars for the multi-layer algorithm and MVV for clarity. Additional details follow.
algorithm, we reserve the top 10% of the total space for
We use the same predictor for Nay in Section 4 as a prediction for Rzy. The experiment is done under random vertex arrival order. For the leameng-basedd algorithm, suppose Z is the maximum number of edges that we are allowed to store. we set the k = 2/10 edges with the highest predicted Rwg values to be the heavy edges, and store them during the stream (i.e., we use 10% of the total
32

---

Published as a conference paper at ICLR 2022
Calce-203E, Geaphe923
Caids 2005. Greph-43
0.30
0.30
0.22
0.25
WRS
0.20
2.000
0.35
9.25
Space
Space
CAIDA 2006, Graph #20
(b) CAIDA 2006, Graph #-10
Orggen Sraphed
Otegon Grggta7
0.25
0.25
Think
Thrnk
HeV
Whs
Whs
0.25
0.02
0.20
0.:00
0.32
0.23
3
5-307
155-13
2-10P
0.00g
5.10'
2-307
Space
Space
(c) Oregon, Graph #3
(d) Oregon, Graph #7
Figure 5: Error as a function of space for various graph datasets.
space for storing the heavy edges). For the remaining edges, we use a similar sampling-based method. Note that it is impossible to know the k-heaviest edges before we see all the edges in the stream. However, in the implementation we can maintain the k heaviest edges we currently have seen so far, and evict the smallest edge in the set when a new heavy edge is predicted by the oracle.
We also consider the multi-layer sub-sampling algorithm mentioned in Section B.2, which uses more information from the oracle. We notice that in many graph datasets, most of the edges having very few number of triangles attached to. Taking an example of the Oregon and CAIDA graph, only about 3%-5% of edges will satisfy R. 2 under a random vertex arrival order. Hence, for this edges, intuitively we can estimate them using slightly smaller space.
For the implementation of this algorithm(we call it multi-layer version), we use 10% of the total space for storing the top k = 2/10 edges, and 70% of the space for sub-sampling the edges that the oracle predict value is very tihy threshold may be slightly different for different datasets, like for the Oregon and CAIDA graph, we set the threshold to be 5). Then, we use 20% of the space for sampling the remaining edges, for which we call them the medium edges.
F.6 FIGURES FROM ADIACENCY LIST TRIANGLE COUNTING EXPERIMENTS
0.35
Fivertiw
d Dun' ww
Alyira MW
Altreii NEV
8:25
0.09
3.54
0.04
8.00
3.44
0,52
8:25
6:00
Apoes
(a) CAIDA 2006
(b) Wikipedia
(c) Powerlaw
Figure 6: Error as function of space in the adjacency list model.
Additional figures from the adjacency list triangle counting experiments shown in Figure 7. They are qualitatively similar to the results presented in Figure 6 as the multi-layer sampling algorithm is superior over the MVV baseline for all of our datasets.
33

---

Published as a conference paper at ICLR 2022
Oregon P4
CMica-2037 #25
0.6
Wichoste
al) AlglmBBllaye)
6.32
laye?
0.32
0.5
2.30
0:30
Eree
0.00
0.00
2.04
0.64
0.02
6.1
5.00
12
+ 300
12 10
10:12
4:10
0.00
1 30
2:101
3-12
10
0.0
300
4:30
3:10
(a) Oregon
(b) CAIDA 2007
(c) Wikibooks
0.12
Out Ag
Out A lertlllllpp
0.01
WW
0.00
0.01
0.02
5.5-10f 3-30f
3.5 1000
2-30 Space
25 3-10"
(d) Twitch
Figure 7: Error as a function of space for various graph datasets.
F.7 ACCURACY OF THE ORACLE
In this section, we evaluate the accuracy of the predictions the oracle gives in our experiments.
Value Prediction Oracle We use the prediction of Nay in Section as a value prediction for Ray(2 (x S. y), under a fixed random vertex arrival order. The results are shown in Figure 8. For fixed approximation factor kt we compute the failure probability of the value prediction oracle as follows: 5 = # m, where m is the number of total edges and # equals to the number of edges that p(e) 2 kaRe + 3 or p(e) S Re - B. respectively. Here we set a = =1,3 = 10 for all graph datasets.
We can see for the smaller side, there are very few edges e such that p(e) S R. - 3. This meets the assumption of the exponential decay tail bound of the error. For the larger side, it also meets the assumption of the linear decay tail bound on most of the graph datasets.
F.8 DETAILS ON ORACLE TRAINING OVERHEAD
The overhead of the oracles used in our experiments vary from task to task. For the important case illustrated by the Oregon and CAIDA datasets in which we interested in repeatedly counting triangles over many related streams, we can pay a small upfront cost to create the oracle which can be reused over and over again. Thus, the time complexity of building the oracle can be amortized over many problem instances, and the space complexity of the oracle is relatively small as we only need store the top 10% of heavy edges from the first graph similar strategy used in prior work on learning-augnnn augmented algorithms in Hsu et al. (2019b)). To give more details, for this snapshot oracle, we simply calculate the Ne values for all edges only in the first graph. We then keep the heaviest edges to form our oracle. Note that this takes polynomial time to train. The time complexity of using this oracle in the stream as follows: when an edge in the stream comes, we simply check if it's among the predicted heavy edges in our oracle. This is simple lookup which can even be done in constant time using hashing.
For learning- based oracles like the linear regression predictor, we similarly need to pay upfront cost to train the model, but the space required to store the trained model depends on the dimension of the edge features. For the Reddit dataset with ~ 300 features, this means that the storage cost for the oracle is a small fraction of the space of the streaming algorithm. Training of this oracle can be done in polynomial time and can even be computed in stream via sketching and sampling
34

---

Published as a conference paper at ICLR 2022
3.00
Oregon
0.040
3,40
CA.ON 2007
(arger
b0gg
0122
0.035
2,035
0.030
2.000
0.020
2001
8.05
0.055
3.055
3.00
10
0.000
3,002
15
Apporemaiin
(a) Oregon
(b) CAIDA 2006
(c) CAIDA 2007
0.013
0.200
0.05
Seger ae
larprr sic
laggr 500
0,002
smaller size
small: skle
0.01
Sha ko skds
5,002
0.225
6.07
0.100
5,001
0.775
0.00
0.002
0.050
0.255
0.002
Aporosiaatinn Factor
Approiimaion Facark
App codmataooo on Foctor
(d) Wikibooks
(c) Twitch
Wikipedia
0.35
Santiom
0.20
2025
0.25
0.5
lagersice mma side
0.00
Aporoatnzinn Factor
gg)
Powerlaw
Figure 8: Failure probability as a function of approximation factor k for various graph datasets.
techniques which reduce the number of constraints from m (number of edges) to roughly linear in the number of features.
Our expected value oracle exploits the fact that our input graph is sampled from the CLV random graph model. Given this, we can explicitly calculate the expected value of N₂ for every edge which requires no training time and nearly constant space. For training details for our link prediction model, see Section F.2. Note that in general, there is a wide and rich family of predictors which can be trained using sublinear space or stream such as regression Woodruff (2014), classification for example using SVMs Andoni et al. (2020); Rai et al. (2009) and even deep learning modelsGomes al. (2019).
G IMPLICIT PREDICTOR IN PRIOR WORKS
We prove that the first pass of the two pass triangle counting Algorithm given in Section 3.1 of McGregor et al. (2016), satisfies the conditions of the K-noisy oracle in Definition 1.1. Therefore, our work can be seen as generalization of their approach when handling multiple related data sets, where instead of performing two passes on each data set and using the first of which to train the heavy edge oracle, we perform the training once according to the first related dataset, and we get a one pass algorithm for all remaining sets.
We first recall the first pass of (McGregor et al., 2016, Section 3.1):
1. Sample each node 2 of the graph with probability p = Ce 2 log m/p for some large con- stant C. 0. Let Z be the set of sampled nodes.
35

---

Published as a conference paper at ICLR 2022
2. Collect all edges incident on the set Z.
3. For any edge e = {u, w). let M(e ((= E 2 u, U. E [())] and define the oracle as
oracle(e) = LIGHT
if ((e) p HEAVY if P
Lemma G.1. For any edge e = (u,v), v), oracle(e) LIGUT implies Ne S 2p and oracle(e) =
HEAVY implies Ne > plv2 with failure probability at most 1/n 10
Proof. For any edge e, follows that t(e) Bin((Ne.P) Therefore if Ne > 2p.
Pr(((e) < < pl & exp(- p)) S 1/nnn
by picking C large enough in the definition of The other case follows similarly.
Lemma G.2. The expected space used by the above oracle is Opm.).
Proof. Each vertex is sampled in Z with probability and keep all of its incident edges. There- fore, the expected number of edges saved Opp E. de) = (pm)..
Note that the oracle satisfies the conditions of the K K-noisy oracle in Definition 1.1. For example. if No C'p for C" > 1, Definition 1.1 only assumes that we incorrectly classify e with probability 1/C', whereas the oracle presented above incorrectly classifies e with probability exp( exp(-C")/ which is much smaller than the required 1/C".
H LEARNABILITY RESULTS
In this section, we give formal learning bounds for efficient predictor learning for edge heaviness. In particular, wish say that good oracle predictor for edge heaviness and related graph parameters can be learned efficiently using few samples if we observe graph instances drawn from a distribution. We can view the result of this section, which will be derived via the PAC learning framework, as one formalization of data driven algorithm design. Our results are quite general but we state simple examples throughout the exposition for clarity. Our setting is formally the following.
Suppose there is an underlying distribution D which generates graph instances H1. H2. all on vertices. Note that this mirrors some of our experimental setting, particular our graph datasets which are similar snapshots of a dynamic graph across time.
Our goal is efficiently learn a good predictor f among some family of functions F. The input of each f is graph instance H and the output is feature vector in k dimensions. The feature vector represents the prediction of the oracle and can encapsulate a variety of different meanings. One example is when l = EL and f outputs
estimate of edge heaviness for all edges. Another when à << [E] and f outputs the id's of the heaviest edges. We also think of each input instance H as encoded a vector T&P for p Z (*) (for example, each instance represented as an
adjacency matrix). Note that we allow for > ( for example, each edge or vertex for H D also has an endowed feature vector.
To select the 'best' f. we need to precisely define the meaning of best. Note that in many settings, this involves loss function which captures the quality of solution. Indeed, suppose we have a loss function I x H - which represents how well a predictor f performs on some input H. An example of I. could be squared emror from the output of f to the true edge heaviness values of edges in H. Note that such loss function clearly optimizes for predicting the heavy edges well.
Our goal is to learn the best function f F which minimizes the following objective:
EH=D[L(f, H)).
Let f* be such the optimal f F, and assume that for each instance H and each f E F, (H) can be computed in time T(p, k). For example, suppose graphs drawn from D possess edge features in Rd and that our family F is parameterized by single vector 0 Rd and represents linear functions
36

---

Published as a conference paper at ICLR 2022
which outputs the dot product of each edge feature with A. Then it is clear that T(p, k) is (small) polynomial in the relevant parameters.
Our main result is the following.
Theorem H.1. There is algoritlu which after poly(T(p, k), k), samples, returns function f that satisfies
En- H)] s En-D|L("", H)] +e
with probability at least 9/10.
We remark that one can boost the probability of success to by taking additional log(1/6) multiplicative samples.
The above theorem is a PAC-style bound which shows that only a small number of samples are needed in order to ensure a good probability of learning an approximately-optina function f. The algorithm to compute f is the following: we simply minimize the empirical loss after an appropriate number of samples by Theorem H.3. Before introducing it, we need to define the concept of dimension for a function class which is the more familiar VC dimension, generalized to real functions.
drawn, i.e., we perform empirical risk minimization. This result proven
Definition H.2 be a set of functions from X the interval [0, Fix a set S {II.-... _nn X, set of real numbers R = {rr,..., Inn with r; E [0, 1] and a function f E F. The set S = {z; E f(x;) Z rs} is called the induced subset of S formed by and R. The set S with associated values R shattered by F y f f =F]== = 2". The pseudo-dimensie of F is the cardinality of the largest shattered subset of X (or oc).
Definition 9 Lucic et al. (2018)). Let be a ground set and F
The following theorem relates the performance of empirical risk minimization and the number of samples needed, to the notion escudo-dimension We specialize the theorem statement our situation at hand. For notational simplicity, we define A be the class of functions in f composed with
A: fEF).
Furthermore, by normalizing, can assume that the range of L is equal [0,
Theorem H.3 (Anthony Bartlett (1999)). Let 'D be distribution over graph instances and A be class of functions H1, H2...., then we have
H + [0,1] with pveudo-dimension d,A. Consider & i.i.d. samples .....,,,, Hr from D. There is a universal constant co, such that for any e > 0, ift 2 op da/e²,
Σ (H.))-H-DDa(R) Sc
for all a E A with probability al least 9/10.
The following corollary follows from the triangle inequality.
Corollary H.4. Consider set of independent samples Hı...., He from D and let à be a function in A which minimizes
Ei=1 H. If the number of samples t is chosen as in Theorem H.3, then Bn-n(ā(H)) < En-nla" (H)) + 2c
holds with probability at least 9/10.
The main challenge is to bound the pseudo-dimension of our given function class A. To do so, first relate the pseudo-dimension to the VC dimension of a related class of threshold functions. This relationship has been fruitful in obtaining learning bounds in variety of works such as Lucic et al. (2018); Izzo et al. (2021).
Lemma H.5 a A. let B, be the indicator function of the region on or below the graph of a, i.e. Ba y) sgn( (((2) (x) - y). The pseudo-dimension of A is equivalent the VC-dimension the subgraph class BA Ba A).
dimeesion to VC dimension, Lemma 10 in Lucic et al. (2018)). For any
Finally, the following theorem relates the VC dimension of given function class to its computa- tional complexity, i.c., the complexity of computing a function in the class in terms the number of operations needed.
37

---

Published as a conference paper at ICLR 2022
Lemma H.6 (Theorem 8.14 in Anthony & Bartlett (1999)). Let w:: R x R - {0, 13, determining the class
W {z w (0, 0 R*).
Suppose that any can be computed by algorithm that takes input the pair (0, (0,a) RRa x R and returns wi0, x) after no more than r of the following operations:
arithmetic operations +. X, and / on real numbers,
jumps conditioned on >, 2. <, S.= =, and comparisons of real numbers, and
output 0, 1,
then the VC dimension of is 0(a2 loga).
Combining the previous results allows prove Theorem H.1. At a high level, we are instantiating Lemma H.6 with the complexity computing any function in the function class A.
Proof of Theorem H.l. First by Theorem H.3 and Corollary H.4, it suffices bound the pseudo- dimension of the class A = Lo o F. Then from Lemmas H.5, the pseudo-dimension of AA is the VC dimension of threshold funetions defined by A. Finally from Lemma H.6, the VC dimension of the appropriate class of threshold functions is polynomial in the complexity of computing a member of the function class. other words, Lemma H.6 tells us that the VC dimension of Bд as defined in Lemma H.5 is polynomial in the number of arithmetic operations needed to compute the threshold function associated to some a E A. By our definition, this quantity polynomial in T(p, k)). Hence, the pseudo pseudo-dimension of G is also polynomial in T(p, k) and the result follows.
Note that we can consider initializing Theorem H.1 with specific predictions. If the family of oracles we are interested in efficient to compute (which is the case of the predictors we employ in our experiments), then Theorem H.1 assures us that only polynomially many samples are required (in terms of the computational complexity of our function class), be able to learn a nearly optimal oracle. Furthermore, computing the empirical risk minimizer needed in Theorem H. is also efficient for a wide verity function classes. For example in practice, we can simply use gradient descent stochastic gradient descent for range of predictor models, such regression even general neural networks.
We remark that our learnability result is in similar in spirit to one given in the recent learning- augmented paper Dinitz et al. (2021). There, they derive sample complexity learning bounds for the different algorithmic problem of computing matchings in graph (not in stream). Since they specialize their analysis to a specific function class and loss function, their bounds are tighter com- pared to the possibly loose polynomial bounds we have stated. However, analysis above is more general as it allows for a variety of predictors and loss functions to measure the quality of the predictions.
38


Reviews:
[{"review_id": "r2rZaHSmY4V", "reviewer": "Reviewer_tiRU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written, the code is provided, and has clean contributions to the problem of triangle counting, and counting cycles of length 4 in the stream. The mathematical formalizations of the oracles are natural, and lead to a nice framework for analyzing subgraph counting methods using an oracle. The proofs are clean, and rely of course on the formalization and the probabilistic method. My main comment is related to the practical relevance of the proposed scheme that is not clearly illustrated in the experiments. Specifically, the algorithms shown in Table 1 work extremely well in practice. It would have been nice to see the arboricity-dependent method of Bera and Sheshadhri, colorful triangle counting of Pagh and Tsourakakis, and the method of Kallaugher and  Price as competitors.  The proposed method improves the performance assuming an oracle, but the oracle has a computational overhead.  This overhead should be discussed in greater extent for the various learners the authors use in their experiments, and provide some comparison with those well-established methods.   Also a more detailed discussion on how the framework applies to dynamic graphs with both edge deletions and insertions (i.e., turnstile) would be great to have in the main text.   Finally, using bigger datasets would add to the experimental section significantly.\n\nTypo\n- In citations \"Sofya Vorotnikovs-->Vorotnikova\"", "summary_of_the_paper": "Counting small length cycles in graph streams is an important graph mining primitive. For example, triangles, i.e., cycles of length 3, play an important role in analyzing social networks. Due to the importance of triangle counting, a wide variety of streaming algorithms in different graph steaming models have been proposed over the years.  This work asks the following question: if there is an oracle than can provide information to whether an edge participates in many or few triangles, can we improve the space required?  This work comes as a natural contribution to  a recent series of works on streaming algorithms that assume the existence of an oracle of some form.  The authors formalize the notion of an oracle in two ways, similarly to classification and regression. The former is defined in definition 1.1 where the oracle decides whether or not an edge is \"heavy\", whereas the latter is termed as the \"noisy value oracle\" (definition 1.2). The authors contribute to the problem of counting C3s in the incidence and adjacency models assuming a learner, and for C4s in the edge stream model. The authors present first the key idea of their algorithm assuming a perfect oracle, and then show that under certain conditions it works for noisy oracles. For C4s  An overview of their results is given in Table 1, together with a nice overview of the state-of-the-art algorithms.  In terms of experiments, the authors illustrate a variety of learners, learned from in- and out-of-sample.  They show that their methods achieve for some learners non-trivial improvement over various other competitors.", "summary_of_the_review": "Overall this a well-written paper, with clear contributions to an important problem.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "cuUBNOVuENg", "reviewer": "Reviewer_oLhV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Major Strengths of the paper:\n1. Theoretical framework with the abstraction of oracles. This might be relevant in the future analysis of such problems\n2. Lower bounds for counting problems will be of interest to the community\n3. The results do not assume any properties of the graph, unlike some previous works. \n\nMajor Issues : \n1. Space complexity of oracles is not discussed. \n\n2. Time complexity of the algorithms is not discussed. \n\n3. Is it fair to compare algorithms in terms of the number of passes? Especially when \"learning oracle\" time is completely excluded in table 1? \nFor example, the authors say that the McGregor 2016 2-pass algorithm is a combination of  1) first-pass for heavy edge estimation and 2) second pass for triangle counting. Thus it is a particular case of the proposed framework. This exactly highlights the issue in table 1 where we do not involve oracle building time and space complexity which shows the proposed method in a better light than what it actually is.\n\nOther questions and comments :\n\n1. How do predictors used in experiments fit in abstractions used in theorems. i.e., to ask can we compute the $\\alpha,\\beta$ for valued oracle or $\\rho$ for heavy oracles?\n\n2. In the case of an arbitrary stream model, the space complexities are worse in terms of an additive term. However, the authors stress that the one-pass algorithm is the real contribution in these cases. In this particular case, it is even more important to establish that learning the oracle is a cheaper process. \n\n3. Theorems 1.4 and 1.5 do not show any dependence on K. Shouldn't it depend on the noisy-ness of Oracle? For example, what happens when the $K \\rightarrow \\infinity$? It would mean that Oracle is not at all informative. In such a case with non-informative oracle, it is not clear how do you still get a better space-bound\n\n4. How are the predictor types decided for a particular data set? In \"1st graph predictor\", does it require O(m) intermediate storage for obtaining exact top 10% edges?\n\n5. GNN with k layers requires access to the k-hop neighborhood of the node under consideration. To apply GNN for an edge, wouldn't you need to store the entire graph ( or subgraph of the same asymptotic size?) to perform the prediction? Also, it appears that for a given edge (u,v), the GNN prediction is applied to edges (u,z) and (v,z) for each z \\neq u or v. Wouldn't this be computationally prohibitive?\n\n\n", "summary_of_the_paper": "The line of research of improving sketching data structures/sampling with the help of learned models is becoming quite popular. This paper follows this line of research and applies this paradigm to the problem of cycle counting in graph streams ( specifically triangles and four-cycles).  It provides a theoretical framework for analyzing Oracle-based problems, analyzing the paradigm's space bounds in cycle counting, and providing lower bounds for the problems. ", "summary_of_the_review": "While some aspects of the paper are nice, such as theoretical framework and lower bounds, etc., the framework's value addition is not clear due to multiple reasons.\n\n1. Authors do not discuss the space complexity of oracles and time ( or number of passes) to train oracle.  This essentially makes me question the comparison in table 1 as indicative of valuable contribution.\n2. The experimental results look promising. But again, due to the lack of inclusion of memory required for oracle, it is not clear if the new method actually beats the old techniques in terms of space-complexity. \nAlso, the predictors that are used might require more auxiliary memory (see points 4,5 above). \n\nOverall, I believe the paper fails to justify the value of the new methods, and including a discussion on the lines of points raised in the review above should help strengthen the paper.  I would be happy to revise my score in case the authors address my concerns. \n\nUpdate: I have updated my score after the revision provided by the authors. There are some good theoretical contributions in this paper which I believe will be useful. The idea of using machine learning oracles with sketching algorithms is, in general, a established idea which deserves exploration in different problem. For this particular problem of counting, I am still a bit reserved on applicability of this framework to the specific problem at hand when accounting for all the meta costs (such as oracle learning etc). However, I am still of the opinion that this paper is worth the acceptance for its overall value to the community.\n\n\n\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BqbjXifrviy", "reviewer": "Reviewer_FczQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is well written and has some nice technical theoretical contributions. \nTo specifically mention about the strengths I feel those are mostly in terms of the theory and the models. \n1) Firstly its about augmenting the ML model with the other streaming models. \n2) Theoretically showing that these models have better space complexity as compared to the state of the art.\n3) Empirical results for different streaming models along with augmentation of the ML models/oracles.\n\n\nHere are the points (most of them from the experimental section) that I feel weighs the paper down (can be considered as weakness).\n1) The graphs used in the experiments are small in terms of the number of edges as compared to the ones the subgraph counting papers for eg. Bera & Shesadri 2020.\n2) Is the space here (in Fig. 1) in terms of the number of edges stored? I.e. is it so that the x-axis denote the number of edges stored? \n(It seems so, because in the paragraph above the authors mention that the \"only parameter given is a space bound for the number of edges that can be stored\")\n3) Except for the Powerlaw and Wikibooks graphs (Figures 1f, and 1d), in/for almost all other plots/graphs here, the first coordinate on the x-axis is around 25% of the total edges. Which seems high If I try to compare these values with the ones in the Bera and Sheshadri 2020.\n4) Was there any specific reason to select/choose graphs #4 and #30 from Oregon and CAIDA respectively in Fig 1? \nI see the results in Fig. 2 for these snapshot graphs with 10% of the edges. However, the amount/fraction of edges used to estimate the number of triangles in other papers for eg. Bera & Sheshadri 2020 and the baselines there, 10% seems high.\n5) The algorithm used by the authors, uses a good amount of exact information encoded in the form of the predictors for the experiments. However, it would be good to check if there is any simpler modification of the baseline algorithms of making them stronger by providing these additional information that the authors algorithm use. Otherwise, I am not completely sure if this is a head to head comparison of the algorithms. Or maybe is there a way to say that there is no easier way to incorporate these additional information in the  baseline algorithms?\n\n\n\nAdditional points:\n1) Introduction 3rd para first line -- \"patterns do not change quickly over time\" -- \nI think that this depends on the application that you are trying to target. Think of a situation where you keep a track on the number of triangles. You observe tweets on popular trending topics. Add an edge between two entities if they occur together in a tweet. And in this case, I feel the number of triangles can change quickly over time.\n\n2) Table 1: Bera & Sheshadri -- multipass algo:\nCan this not be done in a single-pass using -- https://arxiv.org/pdf/1811.08205.pdf -- obviously the complexity changes. \n\n3) Page 3 last para, 4th last line:\nThe results given by the authors are for general graphs --  would it not be interesting to look to see the relation of space complexity with factors such as arboricity, as observed in the cited papers?  \n\n4) It is not clear to me how efficient is it to maintain the oracle/ML model mentioned/used by the authors. \nI understand that that it is not the underlying question that the authors are trying to answer. ", "summary_of_the_paper": "The paper proposes a one pass streaming algorithms for estimating the number of triangles in adjacency list and arbitrary order models and 4-cycle in arbitrary edge arrival order. The authors propose algorithms for these streaming models under the assumption of a \"heavy\" edge oracle/ML model. The paper support theoretical claims with empirical experiments.", "summary_of_the_review": "In terms of the theoretical contributions, the heavy edge oracle and the information used from that seems to be a good amount of information in the model. Would be worthwhile to check if there is simpler version of the oracle.  \n\nIn terms of the empirical contributions, the graphs used in the experiments look small in size and space used in terms of the number of edges is more as compared to the other (random edge and random walk based) models. Thus, it would be great to compare the results with the random walk and u.a.r. edge based models with all the algorithms using similar number of edges.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed a novel one-pass efficient streaming algorithm for estimating the number of triangles and four cycles. The concerns raised by reviewers were nicely addressed in the rebuttal and all the reviewers agree that the paper is above bar for publication.
Decision: Accept (Poster)