Mining tree-query associations in graphs

The problem of mining patterns in graph-structured data has received considerable attention in recent years, as it has many interesting applications in such diverse areas as biology, the life sciences, the World Wide Web, or social sciences. In the present work we introduce a novel class of patterns, called tree queries, and we present algorithms for mining these tree queries and tree-query associations in a large data graph. This article is based on two earlier conference papers [17, 20]. Tree queries are powerful tree-shaped patterns, inspired by conjunctive database queries [18]. In comparison to the kinds of patterns used in most other graph mining approaches, tree queries have some extra features: - Patterns may have"existential" nodes: any occurrence of the pattern must have a copy of such a node, but existential nodes are not counted when determining the number of occurrences.