Graph summarization with bounded error

ABSTRACT

We propose a highly compact two-part representation of a given graph G consisting of a graph summary and a set of corrections. The graph summary is an aggregate graph in which each node corresponds to a set of nodes in G, and each edge represents the edges between all pair of nodes in the two sets. On the other hand, the corrections portion specifies the list of edge-corrections that should be applied to the summary to recreate G. Our representations allow for both lossless and lossy graph compression with bounds on the introduced error. Further, in combination with the MDL principle, they yield highly intuitive coarse-level summaries of the input graph G. We develop algorithms to construct highly compressed graph representations with small sizes and guaranteed accuracy, and validate our approach through an extensive set of experiments with multiple real-life graph data sets.

To the best of our knowledge, this is the first work to compute graph summaries using the MDL principle, and use the summaries (along with corrections) to compress graphs with bounded error.

REFERENCES

• 1: Micah Adler , Michael Mitzenmacher, Towards Compressing Web Graphs, Proceedings of the Data Compression Conference (DCC '01), p.203, March 27-29, 2001
• 2: Vincent D. Blondel , Anahí Gajardo , Maureen Heymans , Pierre Senellart , Paul Van Dooren, A Measure of Similarity between Graph Vertices: Applications to Synonym Extraction and Web Searching, SIAM Review, v.46 n.4, p.647-666, 2004 [doi>10.1137/S0036144502415960]
• 3: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 5: Deepayan Chakrabarti, AutoPart: parameter-free graph partitioning and outlier detection, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.112-124, September 20-24, 2004, Pisa, Italy
• 6: Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
• 7: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 8: Inderjit Dhillon , Yuqiang Guan , Brian Kulis, A fast kernel-based multilevel algorithm for graph clustering, 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.1081948]
• 9: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 10: Harold N. Gabow, An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.448-456, December 1983 [doi>10.1145/800061.808776]
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: David Gibson , Ravi Kumar , Andrew Tomkins, Discovering large dense subgraphs in massive graphs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 14: Marios Iliofotou , Prashanth Pappu , Michalis Faloutsos , Michael Mitzenmacher , Sumeet Singh , George Varghese, Network monitoring using traffic dispersion graphs (tdgs), Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298349]
• 15: Yannis E. Ioannidis , Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.174-185, September 07-10, 1999
• 16: H. V. Jagadish , J. Madar , Raymond T. Ng, Semantic Compression and Pattern Extraction with Fascicles, Proceedings of the 25th International Conference on Very Large Data Bases, p.186-198, September 07-10, 1999
• 17: George Karypis , Vipin Kumar, A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs, SIAM Journal on Scientific Computing, v.20 n.1, p.359-392, Aug. 1998 [doi>10.1137/S1064827595287997]
• 18: Exploiting Local Similarity for Indexing Paths in Graph-Structured Data, Proceedings of the 18th International Conference on Data Engineering, p.129, February 26-March 01, 2002
• 19: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 20: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Extracting Large-Scale Knowledge Bases from the Web, Proceedings of the 25th International Conference on Very Large Data Bases, p.639-650, September 07-10, 1999
• 21: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Trawling the Web for emerging cyber-communities, Proceedings of the eighth international conference on World Wide Web, p.1481-1493, May 1999, Toronto, Canada
• 22: Laks V. S. Lakshmanan , Raymond T. Ng , Christine Xing Wang , Xiaodong Zhou , Theodore J. Johnson, The generalized MDL approach for summarization, Proceedings of the 28th international conference on Very Large Data Bases, p.766-777, August 20-23, 2002, Hong Kong, China
• 23: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceedings of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 24: A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, pages 849--856, 2001.
• 25: Neoklis Polyzotis , Minos Garofalakis, XSKETCH synopses for XML data graphs, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1014-1063, September 2006 [doi>10.1145/1166074.1166082]
• 26: S. Raghavan and H. Garcia-Molina. Representing web graphs. In ICDE, pages 405--416, 2003.
• 27: Keith H. Randall , Raymie Stata , Janet L. Wiener , Rajiv G. Wickremesinghe, The Link Database: Fast Access to Graphs of the Web, Proceedings of the Data Compression Conference (DCC '02), p.122, April 02-04, 2002
• 28: J. Rissanen. Modelling by the shortest data description. Automatica, 14:465--471, 1978.
• 29: P. Shannon, A. Markiel, O. Ozier, N. Baliga, J. Wang, D. Ramage, N. Amin, B. Schwikowski, and T. Ideker. Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome Res., 13(11):2498--504, 2003.
• 30: Torsten Suel , Jun Yuan, Compressing the Graph Structure of the Web, Proceedings of the Data Compression Conference (DCC '01), p.213, March 27-29, 2001
• 31: Godfrey Tan , Massimiliano Poletto , John Guttag , Frans Kaashoek, Role classification of hosts within enterprise networks based on connection patterns, Proceedings of the annual conference on USENIX Annual Technical Conference, p.2-2, June 09-14, 2003, San Antonio, Texas

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage

General Terms:
Algorithms

Keywords:
approximation, graph compression, minimum description length