document: Correlation search in graph databases Correlation mining has gained great success in many application domains for its ability to capture the underlying dependency between objects . However , the research of correlation mining from graph databases is still lacking despite the fact that graph data , especially in various scientific domains , proliferate in recent years . In this paper , we propose a new problem of correlation mining from graph databases , called Correlated Graph Search ( CGS ) . CGS adopts Pearson 's correlation coefficient as a correlation measure to take into consideration the occurrence distributions of graphs . However , the problem poses significant challenges , since every subgraph of a graph in the database is a candidate but the number of subgraphs is exponential . We derive two necessary conditions which set bounds on the occurrence probability of a candidate in the database . With this result , we design an efficient algorithm that operates on a much smaller projected database and thus we are able to obtain a significantly smaller set of candidates . To further improve the efficiency , we develop three heuristic rules and apply them on the candidate set to further reduce the search space . Our extensive experiments demonstrate the effectiveness of our method on candidate reduction . The results also justify the efficiency of our algorithm in mining correlations from large real and synthetic datasets .
doc_bio_tags: B O O B I B O O O O O O O O O O O O O O O O O O O O O O O O O B O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O B I O O O O O O O O O O O O O B O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O