  A bipartite graph extensively models relationships between real-world
entities of two different types, such as user-product data in e-commerce. Such
graph data are inherently becoming more and more streaming, entailing
continuous insertions and deletions of edges. A butterfly (i.e., 2x2 bi-clique)
is the smallest non-trivial cohesive structure that plays a crucial role.
Counting such butterfly patterns in streaming bipartite graphs is a core
problem in applications such as dense subgraph discovery and anomaly detection.
Yet, existing approximate solutions consider insert-only streams and, thus,
achieve very low accuracy in fully dynamic bipartite graph streams that involve
both insertions and deletions of edges. Adapting them to consider deletions is
not trivial either, because different sampling schemes and new accuracy
analyses are required. In this paper, we propose Abacus, a novel approximate
algorithm that counts butterflies in the presence of both insertions and
deletions by utilizing sampling. We prove that Abacus always delivers unbiased
estimates of low variance. Furthermore, we extend Abacus and devise a parallel
mini-batch variant, namely, Parabacus, which counts butterflies in parallel.
Parabacus counts butterflies in a load-balanced manner using versioned samples,
which results in significant speedup and is thus ideal for critical
applications in the streaming environment. We evaluate Abacus/Parabacus using a
diverse set of real bipartite graphs and assess its performance in terms of
accuracy, throughput, and speedup. The results indicate that our proposal is
the first capable of efficiently providing accurate butterfly counts in the
most generic setting, i.e., a fully dynamic graph streaming environment that
entails both insertions and deletions. It does so without sacrificing
throughput and even improving it with the parallel version.
