Paper Info
Title
Frequent subgraph pattern mining on uncertain graph data
Abstract
Graph data are subject to uncertainties in many applications due to incompleteness and imprecision of data. Mining uncertain graph data is semantically different from and computationally more challenging than mining exact graph data. This paper investigates the problem of mining frequent subgraph patterns from uncertain graph data. The frequent subgraph pattern mining problem is formalized by designing a new measure called expected support. An approximate mining algorithm is proposed to find an approximate set of frequent subgraph patterns by allowing an error tolerance on the expected supports of the discovered subgraph patterns. The algorithm uses an efficient approximation algorithm to determine whether a subgraph pattern can be output or not. The analytical and experimental results show that the algorithm is very efficient, accurate and scalable for large uncertain graph databases.
Year
DOI
Venue
2009
10.1145/1645953.1646028
CIKM
Keywords
Field
DocType
approximate set,subgraph pattern,approximate mining algorithm,uncertain graph data,exact graph data,large uncertain graph databases,frequent subgraph pattern mining,frequent subgraph pattern,efficient approximation algorithm,graph data,data mining
Data mining,Graph database,Planarity testing,Computer science,Molecule mining,Induced subgraph isomorphism problem,Graph bandwidth,Factor-critical graph,Subgraph isomorphism problem,Graph (abstract data type)
Conference
Citations 
PageRank 
References 
28
0.91
28
Authors
4
Name
Order
Citations
PageRank
Zhaonian Zou133115.78
Jianzhong Li23196304.46
Hong Gao31086120.07
Shuo Zhang42119.44