Fast Graph Stream Classification Using Discriminative Clique Hashing

Publisher:
Springer
Publication Type:
Journal Article
Citation:
Lecture Notes in Computer Science, 2013, 7818 pp. 225 - 236
Issue Date:
2013-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2012001874OK.pdf316.97 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: