Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Low-rank approximations of the adjacency matrix of a graph are essential in finding patterns (such as communities) and detecting anomalies. Additionally, it is desirable to track the low-rank structure as the graph evolves over time, efficiently and within limited storage. Real graphs typically have thousands or millions of nodes, but are usually very sparse. However, standard decompositions such as SVD do not preserve sparsity. This has led to the development of methods such as CUR and CMD, which seek a non-orthogonal basis by sampling the columns and/or rows of the sparse matrix.

However, these approaches will typically produce overcomplete bases, which wastes both space and time. In this paper we propose the family of Colibri methods to deal with these challenges. Our version for static graphs, Colibri-S, iteratively finds a non-redundant basis and we prove that it has no loss of accuracy compared to the best competitors (CUR and CMD), while achieving significant savings in space and time: on real data, Colibri-S requires much less space and is orders of magnitude faster (in proportion to the square of the number of non-redundant columns). Additionally, we propose an efficient update algorithm for dynamic, time-evolving graphs, Colibri-D. Our evaluation on a large, real network traffic dataset shows that Colibri-D is over 100 times faster than the best published competitor (CMD).

REFERENCES

• 1: Dimitris Achlioptas , Frank Mcsherry, Fast computation of low-rank matrix approximations, Journal of the ACM (JACM), v.54 n.2, p.9-es, April 2007 [doi>10.1145/1219092.1219097]
• 2: R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world wide web. Nature, (401):130--131, 1999.
• 3: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 4: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.309-320, June 2000, Amsterdam, The Netherlands
• 5: Yun Chi , Xiaodan Song , Dengyong Zhou , Koji Hino , Belle L. Tseng, Evolutionary spectral clustering by incorporating temporal smoothness, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281212]
• 6: S. Dorogovtsev and J. Mendes. Evolution of networks. Advances in Physics, 51:1079--1187, 2002.
• 7: Petros Drineas , Ravi Kannan , Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication, SIAM Journal on Computing, v.36 n.1, p.132-157, 2006 [doi>10.1137/S0097539704442684]
• 8: Petros Drineas , Ravi Kannan , Michael W. Mahoney, Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition, SIAM Journal on Computing, v.36 n.1, p.184-206, 2006 [doi>10.1137/S0097539704442702]
• 9: P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Relative-error cur matrix decompositions. CoRR, abs/0708.3696, 2007.
• 10: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States [doi>10.1145/316188.316229]
• 11: Gary William Flake , Steve Lawrence , C. Lee Giles , Frans M. Coetzee, Self-Organization and Identification of Web Communities, Computer, v.35 n.3, p.66-71, March 2002 [doi>10.1109/2.989932]
• 12: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 13: M. Girvan and M. E. J. Newman. Community structure is social and biological networks.
• 14: G. H. Golub and C. F. Van-Loan. Matrix Computations. The Johns Hopkins University Press, Baltimore, 2nd edition, 1989.
• 15: Sudipto Guha , D. Gunopulos , Nick Koudas, Correlating synchronous and asynchronous data streams, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956814]
• 16: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 17: K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.166-176, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/276304.276320]
• 18: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 19: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 20: M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.
• 21: Jia-Yu Pan , Hyung-Jeong Yang , Christos Faloutsos , Pinar Duygulu, Automatic multimedia cross-modal correlation discovery, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014135]
• 22: Jia-Yu Pan , Hyung-Jeong Yang , Christos Faloutsos , Pinar Duygulu, Automatic multimedia cross-modal correlation discovery, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014135]
• 23: Spiros Papadimitriou , Jimeng Sun , Christos Faloutsos, Streaming pattern discovery in multiple time-series, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 24: Walter W. Piegorsch , George Casella, Erratum: inverting a sum of matrices, SIAM Review, v.32 n.3, p.470, Sep. 1990 [doi>10.1137/1032080]
• 25: Jimeng Sun , Christos Faloutsos , Spiros Papadimitriou , Philip S. Yu, GraphScope: parameter-free mining of large time-evolving graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281266]
• 26: Jimeng Sun , Huiming Qu , Deepayan Chakrabarti , Christos Faloutsos, Neighborhood Formation and Anomaly Detection in Bipartite Graphs, Proceedings of the Fifth IEEE International Conference on Data Mining, p.418-425, November 27-30, 2005 [doi>10.1109/ICDM.2005.103]
• 27: Jimeng Sun , Dacheng Tao , Christos Faloutsos, Beyond streams and graphs: dynamic tensor analysis, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150445]
• 28: J. Sun, Y. Xie, H. Zhang, and C. Faloutsos. Less is more: Compact matrix decomposition for large sparse graphs. In SDM, 2007.
• 29: Hanghang Tong , Christos Faloutsos , Jia-Yu Pan, Random walk with restart: fast solutions and applications, Knowledge and Information Systems, v.14 n.3, p.327-346, March 2008 [doi>10.1007/s10115-007-0094-2]
• 30: Dong Xin , Jiawei Han , Xifeng Yan , Hong Cheng, Mining compressed frequent-pattern sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation

Keywords:
graph mining, low-rank approximation, scalability