Affiliations: [a] School of EECS, Washington State University, Pullman, Washington, WA, USA | [b] LTCI, Télécom ParisTech, Paris 75013, France
Correspondence:
[*]
Corresponding author: Abhik Ray, School of EECS, Washington State University, Pullman, Washington, WA, USA. E-mail: abhik.ray@wsu.edu.
Abstract: We propose an efficient, approximate algorithm to solve the problem of finding frequent subgraphs in large streaming graphs. The graph stream is treated as batches of labeled nodes and edges. Our proposed algorithm finds the set of frequent subgraphs as the graph evolves after each batch. The computational complexity is bounded to linear limits by looking only at the changes made by the most recent batch, and the historical set of frequent subgraphs. As a part of our approach, we also propose a novel sampling algorithm that samples regions of the graph that have been changed by the most recent update to the graph. The performance of the proposed approach is evaluated using five large graph datasets, and our approach is shown to be faster than the state of the art large graph miners while maintaining their accuracy. We also compare our sampling algorithm against a well known sampling algorithm for network motif mining, and show that our sampling algorithm is faster, and capable of discovering more types of patterns. We provide theoretical guarantees of our algorithm’s accuracy using the well known Chernoff bounds, as well as an analysis of the computational complexity of our approach.
