We study the problem of (1+ε)-approximating the number of four-cycles in graphs given as arbitrary order edge streams. We propose two new algorithms based on sampling induced subgraphs. Our first contribution is a two-pass algorithm that uses Õ(κm / √T) space, where m is the number of edges, T is the number of four-cycles, and κ is the graph's degeneracy. This algorithm improves upon existing theoretical bounds and is provably optimal for constant-degeneracy graphs, matching the known Ω(m/√T) lower bound up to lower-order factors. Our second contribution is a one-pass algorithm that remains accurate when four-cycles are not highly concentrated on individual nodes, edges, or wedges; this structural property is common in sparse social and collaboration networks. We evaluate both algorithms on a variety of real-world graph streams. The two-pass algorithm consistently outperforms state-of-the-art methods, using substantially less space to achieve a desired accuracy. The one-pass algorithm is competitive when four cycles are evenly distributed, matching our theoretical analysis. Unlike several recent works, our algorithms perform well even on non-bipartite graphs such as social networks.

We study four-cycle counting in arbitrary order graph streams. We present a 3-pass algorithm for \((1 + \varepsilon)\)-approximating the number of four-cycles using \(\tilde O(m/\sqrt T)\) space, where \(m\) is the number of edges and \(T\) the number of four-cycles in the graph. This improves upon a 3-pass algorithm by Vorotnikova using space \(\tilde O(m/T^{1/3})\) and matches a multi-pass lower bound of \(\Omega(m/\sqrt T)\) by McGregor and Vorotnikova.