Space-efficient algorithms for counting triangles in data streams using trained oracles

In this paper, we study data stream algorithms for approximating the number of triangles under the assumption that the algorithm has access to an oracle that answers certain queries about the input graph. Specifically, we present algorithms that process the input graph given as a sequence of edges (or vertices) and output an estimate of the number of triangles in the given graph. We consider algorithms that, while processing the input stream, have access to a degree oracle (given a vertex, the oracle provides the degree of the queried vertex) or an edge triangle oracle where the oracle answers whether an edge (u,v) participates in a triangle or not. We implement two single-pass algorithms and the associated oracles in both the edge-arrival and the vertex-arrival models, and evaluate their performance on real-world datasets. Despite the inaccuracies of the oracles used in our experiments, our study shows that they can improve the performance of state-of-the-art triangle counting algorithms on some real-world graphs.

کلیدواژه ها:

Counting Triangles ، Data Stream Model ، Learning-Augmented Algorithms