Utilizing common substructures to speedup tensor factorization for mining dynamic graphs

Liu, W, Chan, J, Bailey, J, Leckie, C and Ramamohanarao, K 2012, 'Utilizing common substructures to speedup tensor factorization for mining dynamic graphs', in Proceedings of 21st ACM International Conference on Information and Knowledge Management (CIKM 2012), Maui, United States, 29 October - 2 November 2012, pp. 435-444.


Document type: Conference Paper
Collection: Conference Papers

Title Utilizing common substructures to speedup tensor factorization for mining dynamic graphs
Author(s) Liu, W
Chan, J
Bailey, J
Leckie, C
Ramamohanarao, K
Year 2012
Conference name 21st ACM International Conference on Information and Knowledge Management (CIKM 2012)
Conference location Maui, United States
Conference dates 29 October - 2 November 2012
Proceedings title Proceedings of 21st ACM International Conference on Information and Knowledge Management (CIKM 2012)
Publisher Association for Computing Machinery
Place of publication United States
Start page 435
End page 444
Total pages 10
Abstract In large and complex graphs of social, chemical/biological, or other relations, frequent substructures are commonly shared by different graphs or by graphs evolving through different time periods. Tensors are natural representations of these complex time-evolving graph data. A factorization of a tensor provides a high-quality low-rank compact basis for each dimension of the tensor, which facilitates the interpretation of frequent substructures of the original graphs. However, the high computational cost of tensor factorization makes it infeasible for conventional tensor factorization methods to handle large graphs that evolve frequently with time. To address this problem, in this paper we propose a novel iterative tensor factorization (ITF) method whose time complexity is linear in the cardinalities of all dimensions of a tensor. This low time complexity means that when using tensors to represent dynamic graphs, the computational cost of ITF is linear in the size (number of edges/vertices) of graphs and is also linear in the number of time periods over which the graph evolves. More importantly, an error estimation of ITF suggests that its factorization correctness is comparable to that of the standard factorization method. We empirically evaluate our method on publication networks and chemical compound graphs, and demonstrate that ITF is an order of magnitude faster than the conventional method and at the same time preserves factorization quality. To the best of our knowledge, this research is the first work that uses important frequent substructures to speed up tensor factorizations for mining dynamic graphs.
Subjects Pattern Recognition and Data Mining
Copyright notice © 2012 ACM
ISBN 9781450311564
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 6 times in Scopus Article | Citations
Access Statistics: 146 Abstract Views  -  Detailed Statistics
Created: Thu, 06 Aug 2015, 07:34:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us