Title | ||
---|---|---|
ORIGAMI: A Novel and Effective Approach for Mining Representative Orthogonal Graph Patterns |
Abstract | ||
---|---|---|
In this paper, we introduce the concept of α-orthogonal patterns to mine a representative set of graph patterns. Intuitively, two graph patterns are α-orthogonal if their similarity is bounded above by α. Each α-orthogonal pattern is also a representative for those patterns that are at least β similar to it. Given user defined α, β ∈ [0, 1], the goal is to mine an α-orthogonal, β-representative set that minimizes the set of unrepresented patterns. We present ORIGAMI, an effective algorithm for mining the set of representative orthogonal patterns. ORIGAMI first uses a randomized algorithm to randomly traverse the pattern space, seeking previously unexplored regions, to return a set of maximal patterns. ORIGAMI then extracts an α-orthogonal, β-representative set from the mined maximal patterns. We show the effectiveness of our algorithm on a number of real and synthetic datasets. In particular, we show that our method is able to extract high-quality patterns even in cases where existing enumerative graph mining methods fail to do so. Copyright © 2008 Wiley Periodicals, Inc., A Wiley Company Statistical Analy Data Mining 1: 000-000, 2008 The first two authors contributed equally for this research. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1002/sam.v1:2 | Statistical Analysis and Data Mining |
Keywords | Field | DocType |
randomized algorithm,data mining,statistical analysis | Randomized algorithm,Data mining,Graph,Graph patterns,Two-graph,Computer science,Bounded set,Artificial intelligence,Machine learning,Traverse | Journal |
Volume | Issue | Citations |
1 | 2 | 23 |
PageRank | References | Authors |
1.09 | 17 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Vineet Chaoji | 1 | 428 | 19.50 |
Mohammad Al Hasan | 2 | 427 | 35.08 |
Saeed Salem | 3 | 182 | 17.39 |
Jérémy Besson | 4 | 407 | 24.00 |
Mohammed Javeed Zaki | 5 | 7972 | 536.24 |