poster

Compression of weighted graphs

Authors:

Hannu Toivonen,

Aleksi Hartikainen,

Atte HinkkaAuthors Info & Claims

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

Pages 965 - 973

https://doi.org/10.1145/2020408.2020566

Published: 21 August 2011 Publication History

Abstract

We propose to compress weighted graphs (networks), motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplification, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized.

In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of 'generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with different balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.

References

[1]

M. Adler and M. Mitzenmacher. Towards compressing web graphs. In Data Compression Conference, pages 203--212, 2001.

Digital Library

[2]

P. Boldi and S. Vigna. The webgraph framework I: compression techniques. In WWW '04: Proceedings of the 13th international conference on World Wide Web, pages 595--602, New York, NY, USA, 2004. ACM.

Digital Library

[3]

S. P. Borgatti and M. G. Everett. Regular blockmodels of multiway, multimode matrices. Social Networks, 14:91--120, 1992.

[4]

C. Chen, C. Lin, M. Fredrikson, M. Christodorescu, X. Yan, and J. Han. Mining graph patterns efficiently via randomized summaries. In 2009 Int. Conf. on Very Large Data Bases, pages 742--753, Lyon, France, August 2009. VLDB Endowment.

Digital Library

[5]

C. Chen, X. Yan, F. Zhu, J. Han, and P. Yu. Graph OLAP: Towards online analytical processing on graphs. In ICDM '08: Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, pages 103--112, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[6]

U. Elsner. Graph partitioning - a survey. Technical Report SFB393/97--27, Technische Universität Chemnitz, 1997.

[7]

C. Faloutsos, K. S. McCurley, and A. Tomkins. Fast discovery of connection subgraphs. In KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 118--127, New York, NY, USA, 2004. ACM.

Digital Library

[8]

P.-O. Fjällström. Algorithms for graph partitioning: A Survey. In Linköping Electronic Atricles in Computer and Information Science, 3, 1998.

[9]

S. Hauguel, C. Zhai, and J. Han. Parallel PathFinder Algorithms for Mining Structures from Graphs. In 2009 Ninth IEEE International Conference on Data Mining, pages 812--817. IEEE, 2009.

Digital Library

[10]

P. Hintsanen and H. Toivonen. Finding reliable subgraphs from large probabilistic graphs. Data Mining and Knowledge Discovery, 17:3--23, 2008.

Digital Library

[11]

F. Lorrain and H. C. White. Structural equivalence of individuals in social networks. Journal of Mathematical Sociology, 1:49--80, 1971.

[12]

S. Navlakha, R. Rastogi, and N. Shrivastava. Graph summarization with bounded error. In SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 419--432, New York, NY, USA, 2008. ACM.

Digital Library

[13]

S. Navlakha, M. Schatz, and C. Kingsford. Revealing Biological Modules via Graph Summarization. Presented at the RECOMB Systems Biology Satellite Conference. J. Comp. Bio., 16:253--264, 2009.

[14]

Y. Tian, R. Hankins, and J. Patel. Efficient aggregation for graph summarization. In SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pages 567--580, New York, NY, USA, 2008. ACM.

Digital Library

[15]

H. Toivonen, S. Mahler, and F. Zhou. A framework for path-oriented network simplification. In Advances in Intelligent Data Analysis IX, volume 6065/2010, pages 220--231, Berlin/Heidelberg, May 2010. Springer-Verlag.

Digital Library

[16]

G. T. Toussaint. The relative neighbourhood graph of a finite planar set. Pattern Recognition, 12(4):261--268, 1980.

[17]

N. Zhang, Y. Tian, and J. Patel. Discovery-driven graph summarization. In Data Engineering (ICDE), 2010 IEEE 26th International Conference on, pages 880--891. IEEE, 2010.

Cited By

Sun ZZeng G(2024)A Two-stage Coarsening Method for a Streaming Graph with Preserving Key FeaturesProceedings of the 2024 International Conference on Generative Artificial Intelligence and Information Security10.1145/3665348.3665392(253-260)Online publication date: 10-May-2024
https://dl.acm.org/doi/10.1145/3665348.3665392
Chu DZhang FZhang WZhang YLin X(2024)Graph Summarization: Compactness Meets EfficiencyProceedings of the ACM on Management of Data10.1145/36549432:3(1-26)Online publication date: 30-May-2024
https://doi.org/10.1145/3654943
Yanagiya KHara JHigashi HTanaka YOrtega A(2024)Lossy Compression of Adjacency Matrices by Graph Filter BanksICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10448045(9386-9390)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10448045
Show More Cited By

Index Terms

Compression of weighted graphs
1. Information systems
  1. Information systems applications
    1. Data mining
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Claw Conditions for Heavy Cycles in Weighted Graphs

A graph is called a weighted graph when each edge e is assigned a nonnegative number w ( e ), called the weight of e . For a vertex v of a weighted graph, d ^w( v ) is the sum of the weights of the edges incident with v . For a subgraph H ...
Heavy cycles passing through some specified vertices in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex υ is called the weighted degree of υ. The weight of a cycle is defined as the sum of the ...
Ore-type degree condition for heavy paths in weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number w(e), called the weight of e. For a vertex v of a weighted graph, d^w(v) is the sum of the weights of the edges incident to v. And the weight of a path is the sum of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

August 2011

1446 pages

ISBN:9781450308137

DOI:10.1145/2020408

General Chair:
Chid Apte
IBM Research
,
Program Chairs:
Joydeep Ghosh
UT Austin
,
Padhraic Smyth
UC Irvine

Copyright © 2011 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: 21 August 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

KDD '11

Sponsor:

KDD '11: The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2011

California, San Diego, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

93
Total Citations
View Citations
1,032
Total Downloads

Downloads (Last 12 months)113
Downloads (Last 6 weeks)8

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sun ZZeng G(2024)A Two-stage Coarsening Method for a Streaming Graph with Preserving Key FeaturesProceedings of the 2024 International Conference on Generative Artificial Intelligence and Information Security10.1145/3665348.3665392(253-260)Online publication date: 10-May-2024
https://dl.acm.org/doi/10.1145/3665348.3665392
Chu DZhang FZhang WZhang YLin X(2024)Graph Summarization: Compactness Meets EfficiencyProceedings of the ACM on Management of Data10.1145/36549432:3(1-26)Online publication date: 30-May-2024
https://doi.org/10.1145/3654943
Yanagiya KHara JHigashi HTanaka YOrtega A(2024)Lossy Compression of Adjacency Matrices by Graph Filter BanksICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10448045(9386-9390)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10448045
Anagnostopoulos AArrigoni VGullo FSalvatori GSeverini L(2024)General-purpose query processing on summary graphsSocial Network Analysis and Mining10.1007/s13278-024-01314-w14:1Online publication date: 9-Aug-2024
https://doi.org/10.1007/s13278-024-01314-w
Hughes JHoughten SDubé MAshlock DBrown JAshlock WStoodley MHughes JHoughten SDubé MAshlock DBrown JAshlock WStoodley M(2024)Graph CompressionAI Versus Epidemics10.1007/978-3-031-64373-6_3(21-38)Online publication date: 25-Sep-2024
https://doi.org/10.1007/978-3-031-64373-6_3
Beldi ASassi SChbeir RJemai A(2023)DG_summ: A schema-driven approach for personalized summarizing heterogeneous data graphsComputer Science and Information Systems10.2298/CSIS230331062B20:4(1591-1638)Online publication date: 2023
https://doi.org/10.2298/CSIS230331062B
Merchant AMathioudakis MWang YChua TLauw HSi LTerzi ETsaparas P(2023)Graph Summarization via Node Grouping: A Spectral AlgorithmProceedings of the Sixteenth ACM International Conference on Web Search and Data Mining10.1145/3539597.3570441(742-750)Online publication date: 27-Feb-2023
https://dl.acm.org/doi/10.1145/3539597.3570441
Malak D(2023)Weighted Graph Coloring for Quantized Computing2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206523(2290-2295)Online publication date: 25-Jun-2023
https://doi.org/10.1109/ISIT54713.2023.10206523
Du JWu YAi WMeng TXie CLi K(2023)Fast Butterfly-Core Community Search For Large Labeled Graphs2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00066(390-396)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00066
Rutkowski EHoughten SBrown J(2023)A multi-objective genetic algorithm for compression of weighted graphs to simplify epidemic analysisApplied Soft Computing10.1016/j.asoc.2023.110486144(110486)Online publication date: Sep-2023
https://doi.org/10.1016/j.asoc.2023.110486
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