Mining Graph Patterns - Frequent Pattern Mining - page 331

8 Conclusions

Frequent subgraph mining is one of the fundamental tasks in graph data mining. The
inherent complexity in graph data causes the combinatorial explosion problem. As
a result, a mining algorithm may take a long time or even forever to complete the
mining process on some real graph datasets.
In this chapter, we introduced several state-of-the-art methods that mine a compact
set of significant or representative subgraphs without generating the complete set
of graph patterns. The proposed mining and pruning techniques were discussed in
details. These methods greatly reduce the computational cost, while at the same time,
increase the applicability of the generated graph patterns. Other variations of frequent
subgraph patterns include dense subgraphs, reliable subgraphs and so on. The new
application scenarios also call for new graph pattern mining algorithms, for example,
mining graphs patterns in a graph stream or in uncertain graphs. We also introduced
the state-of-the-art research results under such settings. These research results have
made significant progress on graph mining research with many new applications.

References

1. C. C. Aggarwal, Y. Li, P. S. Yu, and R. Jin. On dense pattern mining in graph streams. PVLDB ,
3(1):975-984, 2010.
2. M. Al Hasan, V. Chaoji, S. Salem, J. Besson, and M. J. Zaki. ORIGAMI: Mining representative
orthogonal graph patterns. In Proc. 2007 Int. Conf. Data Mining (ICDM'07) , pages 153-162,
2007.
3. A. Angel, N. Koudas, N. Sarkas, and D. Srivastava. Dense subgraph maintenance under
streaming edge weight updates for real-time story identification. PVLDB , 3(5):574-585, 2012.
4. T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Satamoto, and S. Arikawa. Efficient substruc-
ture discovery from large semi-structured data. In Proc. 2002 SIAM Int. Conf. Data Mining
(SDM'02) , pages 158-174, 2002.
5. B. Bahmani, R. Kumar, and S. Vassilvitskii. Densest subgraph in streaming and MapReduce.
PVLDB , 5(5):454-465, 2012.
6. A. Bifet, G. Holmes, B. Pfahringer, and R. Gavalda. Mining frequent closed graphs on evolving
data streams. In KDD , pages 591-599, 2011.
7. C. Borgelt and M. R. Berthold. Mining molecular fragments: Finding relevant substructures of
molecules. In Proc. 2002 Int. Conf. Data Mining (ICDM'02) , pages 211-218, 2002.
8. B. Bringmann and S. Nijssen. What is frequent in a single graph? In Proc. 2008 Pacific-Asia
Conf. Knowledge Discovery and Data Mining (PAKDD'08) , pages 858-863, 2008.
9. H. Cheng, X. Yan, J. Han, and C.-W. Hsu. Discriminative frequent pattern analysis for effective
classification. In Proc. 2007 Int. Conf. Data Engineering (ICDE'07) , pages 716-725, 2007.
10. J. Cheng, Y. Ke, A. Fu, J. X. Yu, and L. Zhu. Finding maximal cliques in massive networks by
H*-graph. In SIGMOD , pages 447-458, 2010.
11. J. Cheng, Y. Ke, S. Chu, and M. T. Ozsu. Efficient core decomposition in massive networks.
In ICDE , pages 51-62, 2011.
12. J. Cheng, L. Zhu, Y. Ke, and S. Chu. Fast algorithms for Maximal Clique Enumeration with
Limited Memory. In KDD , pages 1240-1248, 2012.
13. Y. Chi, Y. Xia, Y. Yang, and R. Muntz. Mining closed and maximal frequent subtrees from
databases of labeled rooted trees. IEEE Trans. Knowledge and Data Eng. , 17:190-202, 2005.