research-article

Colibri: fast mining of large static and dynamic graphs

Authors:

Spiros Papadimitriou,

Christos FaloutsosAuthors Info & Claims

KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 686 - 694

https://doi.org/10.1145/1401890.1401973

Published: 24 August 2008 Publication History

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]

D. Achlioptas and F. McSherry. Fast computation of low-rank matrix approximations. J. ACM, 54(2), 2007.

Digital Library

[2]

R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world wide web. Nature, (401):130--131, 1999.

[3]

L. Backstrom, D. P. Huttenlocher, J. M. Kleinberg, and X. Lan. Group formation in large social networks: membership, growth, and evolution. In KDD, pages 44--54, 2006.

Digital Library

[4]

A. Broder, R. Kumar, F. Maghoul1, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web: experiments and models. In WWW Conf., 2000.

Digital Library

[5]

Y. Chi, X. Song, D. Zhou, K. Hino, and B. L. Tseng. Evolutionary spectral clustering by incorporating temporal smoothness. In KDD, pages 153--162, 2007.

Digital Library

[6]

S. Dorogovtsev and J. Mendes. Evolution of networks. Advances in Physics, 51:1079--1187, 2002.

[7]

P. Drineas, R. Kannan, and M. W. Mahoney. Fast monte carlo algorithms for matrices i: Approximating matrix multiplication. SIAM Journal of Computing, 2005.

Digital Library

[8]

P. Drineas, R. Kannan, and M. W. Mahoney. Fast monte carlo algorithms for matrices iii: Computing a compressed approximate matrix decomposition. SIAM Journal of Computing, 2005.

Digital Library

[9]

P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Relative-error cur matrix decompositions. CoRR, abs/0708.3696, 2007.

[10]

M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. SIGCOMM, pages 251--262, Aug-Sept. 1999.

Digital Library

[11]

G. Flake, S. Lawrence, C. L. Giles, and F. Coetzee. Self-organization and identification of web communities. IEEE Computer, 35(3), Mar. 2002.

Digital Library

[12]

D. Gibson, J. Kleinberg, and P. Raghavan. Inferring web communities from link topology. In Ninth ACM Conference on Hypertext and Hypermedia, pages 225--234, New York, 1998.

Digital Library

[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]

S. Guha, D. Gunopulos, and N. Koudas. Correlating synchronous and asynchronous data streams. In KDD, pages 529--534, 2003.

Digital Library

[16]

P. Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. In FOCS, pages 189--197, 2000.

Digital Library

[17]

K. V. R. Kanth, D. Agrawal, and A. K. Singh. Dimensionality reduction for similarity searching in dynamic databases. In SIGMOD Conference, pages 166--176, 1998.

Digital Library

[18]

D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. KDD, 2003.

Digital Library

[19]

J. Leskovec, J. M. Kleinberg, and C. Faloutsos. Graphs over time: densification laws, shrinking diameters and possible explanations. In KDD, pages 177--187, 2005.

Digital Library

[20]

M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45:167--256, 2003.

Digital Library

[21]

J.-Y. Pan, H.-J. Yang, C. Faloutsos, and P. Duygulu. Automatic multimedia cross-modal correlation discovery. In KDD, pages 653--658, 2004.

Digital Library

[22]

J.-Y. Pan, H.-J. Yang, C. Faloutsos, and P. Duygulu. Automatic multimedia cross--modal correlation discovery. In KDD, pages 653--658, 2004.

Digital Library

[23]

S. Papadimitriou, J. Sun, and C. Faloutsos. Streaming pattern discovery in multiple time-series. In VLDB, pages 697--708, 2005.

Digital Library

[24]

W. Piegorsch and G. E. Casella. Inverting a sum of matrices. In SIAM Review, volume 32, pages 470--470, 1990.

Digital Library

[25]

J. Sun, C. Faloutsos, S. Papadimitriou, and P. S. Yu. Graphscope: parameter-free mining of large time-evolving graphs. In KDD, pages 687--696, 2007.

Digital Library

[26]

J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos. Neighborhood formation and anomaly detection in bipartite graphs. In ICDM, pages 418--425, 2005.

Digital Library

[27]

J. Sun, D. Tao, and C. Faloutsos. Beyond streams and graphs: dynamic tensor analysis. In KDD, pages 374--383, 2006.

Digital Library

[28]

J. Sun, Y. Xie, H. Zhang, and C. Faloutsos. Less is more: Compact matrix decomposition for large sparse graphs. In SDM, 2007.

[29]

H. Tong, C. Faloutsos, and J.-Y. Pan. Random walk with restart: Fast solutions and applications. Knowledge and Information Systems: An International Journal (KAIS), 2008.

Digital Library

[30]

D. Xin, J. Han, X. Yan, and H. Cheng. Mining compressed frequent-pattern sets. In VLDB, pages 709--720, 2005

Digital Library

Cited By

Bagheri SCheung GEadie TOrtega A(2024)Joint Signal Interpolation / Time-Varying Graph Estimation Via Smoothness and Low-Rank PriorsICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10447459(9646-9650)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10447459
Zaccardi SFrantz TBeckwée DSwinnen EJansen B(2023)On-Device Execution of Deep Learning Models on HoloLens2 for Real-Time Augmented Reality Medical ApplicationsSensors10.3390/s2321869823:21(8698)Online publication date: 25-Oct-2023
https://doi.org/10.3390/s23218698
Sharma KSingh A(2023)A Systematic Review: Detection of Anomalies in Social Networks2023 International Conference on Sustainable Computing and Data Communication Systems (ICSCDS)10.1109/ICSCDS56580.2023.10104612(1470-1476)Online publication date: 23-Mar-2023
https://doi.org/10.1109/ICSCDS56580.2023.10104612
Show More Cited By

Index Terms

Colibri: fast mining of large static and dynamic graphs
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners

This paper presents a parallel preconditioning method for distributed sparse linear systems, based on an approximate inverse of the original matrix, that adopts a general framework of distributed sparse matrices and exploits domain ...
Image compressed sensing based on non-convex low-rank approximation

Nonlocal sparsity and structured sparsity have been evidenced to improve the reconstruction of image details in various compressed sensing (CS) studies. The nonlocal processing is achieved by grouping similar patches of the image into the groups. To ...
Non-negative residual matrix factorization: problem definition, fast solutions, and applications

Matrix factorization is a very powerful tool to find graph patterns, e.g. communities, anomalies, etc. A recent trend is to improve the usability of the discovered graph patterns, by encoding some interpretation-friendly properties e.g., non-negativity, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2008

1116 pages

ISBN:9781605581934

DOI:10.1145/1401890

General Chair:
Ying Li
Microsoft adCenter Labs
,
Program Chairs:
Bing Liu
University of Illinois at Chicago
,
Sunita Sarawagi
Indian Institute of Technology, Bombay

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD08

Sponsor:

KDD08: The 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 24 - 27, 2008

Nevada, Las Vegas, USA

Acceptance Rates

KDD '08 Paper Acceptance Rate 118 of 593 submissions, 20%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
1,003
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)3

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bagheri SCheung GEadie TOrtega A(2024)Joint Signal Interpolation / Time-Varying Graph Estimation Via Smoothness and Low-Rank PriorsICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10447459(9646-9650)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10447459
Zaccardi SFrantz TBeckwée DSwinnen EJansen B(2023)On-Device Execution of Deep Learning Models on HoloLens2 for Real-Time Augmented Reality Medical ApplicationsSensors10.3390/s2321869823:21(8698)Online publication date: 25-Oct-2023
https://doi.org/10.3390/s23218698
Sharma KSingh A(2023)A Systematic Review: Detection of Anomalies in Social Networks2023 International Conference on Sustainable Computing and Data Communication Systems (ICSCDS)10.1109/ICSCDS56580.2023.10104612(1470-1476)Online publication date: 23-Mar-2023
https://doi.org/10.1109/ICSCDS56580.2023.10104612
Mahdi MHosny KElhenawy I(2021)Scalable Clustering Algorithms for Big Data: A ReviewIEEE Access10.1109/ACCESS.2021.30840579(80015-80027)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3084057
Feroze ADaud AAmjad THayat M(2021)Group Anomaly Detection: Past Notions, Present Insights, and Future ProspectsSN Computer Science10.1007/s42979-021-00603-x2:3Online publication date: 16-Apr-2021
https://doi.org/10.1007/s42979-021-00603-x
Ma GAhmed NWillke TYu P(2021)Deep graph similarity learning: a surveyData Mining and Knowledge Discovery10.1007/s10618-020-00733-535:3(688-725)Online publication date: 24-Mar-2021
https://doi.org/10.1007/s10618-020-00733-5
Ida YKanai SFujiwara YIwata TTakeuchi KKashima HDaumé HSingh A(2020)Fast deterministic CUR matrix decomposition with accuracy assuranceProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525365(4594-4603)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525365
Lin HLiu GWu JZuo YWan XLi H(2020)Fraud Detection in Dynamic Interaction NetworkIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.291281732:10(1936-1950)Online publication date: 1-Oct-2020
https://doi.org/10.1109/TKDE.2019.2912817
Chen CXia YZang HLi JLiu HTong H(2020)Incremental one-class collaborative filtering with co-evolving side networksKnowledge and Information Systems10.1007/s10115-020-01511-xOnline publication date: 17-Sep-2020
https://doi.org/10.1007/s10115-020-01511-x
Srikanth TShashi M(2019)An effective preprocessing algorithm for model building in collaborative filtering-based recommender systemInternational Journal of Business Intelligence and Data Mining10.1504/ijbidm.2019.09996414:4(489-503)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1504/ijbidm.2019.099964
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents