Four-Cycle Counting in Low-Degeneracy Graph Streams

We study the problem of (1 + 𝜀)-approximating the number of fourcycles 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 𝑂 (𝜅𝑚/ √ 𝑇 ) space, where 𝑚 is the number of edges, 𝑇 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 Ω(𝑚/ √ 𝑇 ) lower bound up to lowerorder factors. Our second contribution is a one-pass algorithm that remains accurate when four-cycles are not highly concentrated around 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 twopass 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.

• Authors ordered alphabetically. 1 We write 𝑂 (•) to hide poly(log 𝑚, 1/𝜀 ) factors.