Abstract | ||
---|---|---|
As many data mining applications involve networked data with dynamically increasing volumes, graph stream classification has recently extracted significant research interest. The aim of graph stream classification is to learn a discriminative model from a stream of graphs represented by sets of edges on a complex network. In this paper, we propose a fast graph stream classification method using DIscriminative Clique Hashing (DICH). The main idea is to employ a fast algorithm to decompose a compressed graph into a number of cliques to sequentially extract clique-patterns over the graph stream as features. Two random hashing schemes are employed to compress the original edge set of the graph stream and map the unlimitedly increasing clique-patterns onto a fixed-size feature space, respectively. The hashed cliques are used to update an "in-memory" fixed-size pattern-class table, which will be finally used to construct a rule-based classifier. DICH essentially speeds up the discriminative clique-pattern mining process and solves the unlimited clique-pattern expanding problem in graph stream mining. Experimental results on two real-world graph stream data sets demonstrate that DICH can clearly outperform the compared state-of-the-art method in both classification accuracy and training efficiency. © Springer-Verlag 2013. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-642-37453-1_19 | PAKDD |
Keywords | Field | DocType |
cliques,graph classification,graph streams,hashing | Graph,Feature vector,Pattern recognition,Clique,Computer science,Hash function,Complex network,Artificial intelligence,Classifier (linguistics),Discriminative model,Machine learning,Fold (higher-order function) | Conference |
Volume | Issue | ISSN |
7818 LNAI | PART 1 | 16113349 |
Citations | PageRank | References |
15 | 0.76 | 14 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lianhua Chi | 1 | 79 | 7.82 |
Bin Li | 2 | 694 | 50.02 |
Xingquan Zhu | 3 | 3086 | 181.95 |