Searching Correlated Patterns From Graph Streams

Abstract

Mining the correlation has attracted widespread attention in the research community because of its advantages in understanding the dependencies between objects. In this paper, a correlated graph pattern searching scheme has been proposed, that is, provided with a query g as a structured pattern (i.e., a graph), our algorithm is capable of retrieving the top-k graphs that most likely correlated with g. Traditional methods treat graph streams as static records, which is computational infeasible or ineffective because of the complexity of searching correlated patterns in a dynamic graph stream. In this paper, by relying on sliding windows to separate graph streams in chunks, we propose a Hoe-PGPL algorithm to handle the top-k correlated patterns searching from a dynamic perspective. Our algorithm applies Hoeffding bound and twolevel (Sliding window level and local batch level) candidate inspection to discover potential graph candidates and determine the similarity of these candidates without double-checking the previous stream. Theoretical analysis shows that our method can guarantee the quality of the returned answers, and our experiments also present that Hoe-PGPL has an excellent performance with aspects of precision, recall, runtime, and resource consumption.

Keywords

• Data streams
• graph streams
• correlated structure pattern query
• Pearson correlation coefficient