{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,24]],"date-time":"2024-07-24T07:18:44Z","timestamp":1721805524133},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>\n            We propose\n            <jats:italic>quasi-stable coloring<\/jats:italic>\n            , an approximate version of stable coloring. Stable coloring, also called color refinement, is a well-studied technique in graph theory for classifying vertices, which can be used to build compact, lossless representations of graphs. However, its usefulness is limited due to its reliance on strict symmetries. Real data compresses very poorly using color refinement. We propose the first, to our knowledge, approximate color refinement scheme, which we call quasi-stable coloring. By using approximation, we alleviate the need for strict symmetry, and allow for a tradeoff between the degree of compression and the accuracy of the representation. We study three applications: Linear Programming, Max-Flow, and Betweenness Centrality, and provide theoretical evidence in each case that a quasi-stable coloring can lead to good approximations on the reduced graph. Next, we consider how to compute a maximal quasi-stable coloring: we prove that, in general, this problem is NP-hard, and propose a simple, yet effective algorithm based on heuristics. Finally, we evaluate experimentally the quasi-stable coloring technique on several real graphs and applications, comparing with prior approximation techniques.\n          <\/jats:p>","DOI":"10.14778\/3574245.3574264","type":"journal-article","created":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:14:12Z","timestamp":1677021252000},"page":"803-815","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Quasi-Stable Coloring for Graph Compression"],"prefix":"10.14778","volume":"16","author":[{"given":"Moe","family":"Kayali","sequence":"first","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,21]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2013. Max-flow problem instances in vision. https:\/\/vision.cs.uwaterloo.ca\/data\/maxflow  2013. Max-flow problem instances in vision. https:\/\/vision.cs.uwaterloo.ca\/data\/maxflow"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2012.0375"},{"key":"e_1_2_1_3_1","volume-title":"Emergence of scaling in random networks. science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. science 286, 5439 ( 1999 ), 509--512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. science 286, 5439 (1999), 509--512."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9686-0"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"key":"e_1_2_1_7_1","unstructured":"The dblp team. [n.d.]. DBLP computer science bibliography. https:\/\/dblp.uni-trier.de\/  The dblp team. [n.d.]. DBLP computer science bibliography. https:\/\/dblp.uni-trier.de\/"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_11_1","volume-title":"ESA (Lecture Notes in Computer Science","volume":"477","author":"Goldberg Andrew V.","year":"2008","unstructured":"Andrew V. Goldberg . 2008 . The Partial Augment-Relabel Algorithm for the Maximum Flow Problem . In ESA (Lecture Notes in Computer Science , Vol. 5193). Springer, 466-- 477 . Andrew V. Goldberg. 2008. The Partial Augment-Relabel Algorithm for the Maximum Flow Problem. In ESA (Lecture Notes in Computer Science, Vol. 5193). Springer, 466--477."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020","author":"Grohe Martin","year":"2020","unstructured":"Martin Grohe . 2020 . word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data . In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020 , Portland, OR, USA , June 14-19, 2020, Dan Suciu, Yufei Tao, and Zhewei Wei (Eds.). ACM, 1--16. Martin Grohe. 2020. word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, Dan Suciu, Yufei Tao, and Zhewei Wei (Eds.). ACM, 1--16."},{"key":"e_1_2_1_13_1","volume-title":"The Logic of Graph Neural Networks. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021","author":"Grohe Martin","year":"2021","unstructured":"Martin Grohe . 2021 . The Logic of Graph Neural Networks. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021 , Rome, Italy, June 29 - July 2, 2021. IEEE, 1--17. Martin Grohe. 2021. The Logic of Graph Neural Networks. In 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021. IEEE, 1--17."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"M. Grohe and Association for Symbolic Logic. 2017. Descriptive Complexity Canonisation and Definable Graph Structure Theory. Cambridge University Press.  M. Grohe and Association for Symbolic Logic. 2017. Descriptive Complexity Canonisation and Definable Graph Structure Theory. Cambridge University Press.","DOI":"10.1017\/9781139028868"},{"key":"e_1_2_1_15_1","volume-title":"Color Refinement and its Applications","author":"Grohe Martin","unstructured":"Martin Grohe , Kristian Kersting , Martin Mladenov , and Pascal Schweitzer . 2021. Color Refinement and its Applications . MIT Press . Martin Grohe, Kristian Kersting, Martin Mladenov, and Pascal Schweitzer. 2021. Color Refinement and its Applications. MIT Press."},{"key":"e_1_2_1_16_1","volume-title":"European Symposium on Algorithms. Springer, 505--516","author":"Grohe Martin","year":"2014","unstructured":"Martin Grohe , Kristian Kersting , Martin Mladenov , and Erkal Selman . 2014 . Dimension reduction via colour refinement . In European Symposium on Algorithms. Springer, 505--516 . Martin Grohe, Kristian Kersting, Martin Mladenov, and Erkal Selman. 2014. Dimension reduction via colour refinement. In European Symposium on Algorithms. Springer, 505--516."},{"key":"e_1_2_1_17_1","first-page":"11","article-title":"The Graph Isomorphism","volume":"63","author":"Grohe Martin","year":"2020","unstructured":"Martin Grohe and Pascal Schweitzer . 2020 . The Graph Isomorphism Problem. Commun. ACM 63 , 11 (Oct. 2020), 128--134. Martin Grohe and Pascal Schweitzer. 2020. The Graph Isomorphism Problem. Commun. ACM 63, 11 (Oct. 2020), 128--134.","journal-title":"Problem. Commun. ACM"},{"key":"e_1_2_1_18_1","volume-title":"Multi-object Graph-based Segmentation with Non-overlapping Surfaces. In CVPR Workshops. Computer Vision Foundation \/ IEEE, 4204--4212","author":"Jensen Patrick M.","year":"2020","unstructured":"Patrick M. Jensen , Anders B. Dahl , and Vedrana Andersen Dahl . 2020 . Multi-object Graph-based Segmentation with Non-overlapping Surfaces. In CVPR Workshops. Computer Vision Foundation \/ IEEE, 4204--4212 . Patrick M. Jensen, Anders B. Dahl, and Vedrana Andersen Dahl. 2020. Multi-object Graph-based Segmentation with Non-overlapping Surfaces. In CVPR Workshops. Computer Vision Foundation \/ IEEE, 4204--4212."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.4905882"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.16"},{"key":"e_1_2_1_21_1","unstructured":"Bryan Klimt and Yiming Yang. 2004. Introducing the Enron Corpus. In CEAS.  Bryan Klimt and Yiming Yang. 2004. Introducing the Enron Corpus. In CEAS."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_24_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_25_1","volume-title":"Computing Maximum Flow with Augmenting Electrical Flows. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016","author":"Madry Aleksander","year":"2016","unstructured":"Aleksander Madry . 2016 . Computing Maximum Flow with Augmenting Electrical Flows. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016 , 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, Irit Dinur (Ed.). IEEE Computer Society, 593--602. Aleksander Madry. 2016. Computing Maximum Flow with Augmenting Electrical Flows. In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, Irit Dinur (Ed.). IEEE Computer Society, 593--602."},{"key":"e_1_2_1_26_1","volume-title":"McAuley and Jure Leskovec","author":"Julian","year":"2012","unstructured":"Julian J. McAuley and Jure Leskovec . 2012 . Learning to Discover Social Circles in Ego Networks. In NIPS. 548--556. Julian J. McAuley and Jure Leskovec. 2012. Learning to Discover Social Circles in Ego Networks. In NIPS. 548--556."},{"key":"e_1_2_1_27_1","unstructured":"Hans Mittelmann. 2022. Benchmark of Barrier LP solvers. http:\/\/plato.asu.edu\/ftp\/lpbar.html  Hans Mittelmann. 2022. Benchmark of Barrier LP solvers. http:\/\/plato.asu.edu\/ftp\/lpbar.html"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012, La Palma, Canary Islands, Spain, April 21-23, 2012 (JMLR Proceedings","volume":"797","author":"Mladenov Martin","year":"2012","unstructured":"Martin Mladenov , Babak Ahmadi , and Kristian Kersting . 2012 . Lifted Linear Programming . In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012, La Palma, Canary Islands, Spain, April 21-23, 2012 (JMLR Proceedings , Vol. 22), Neil D. Lawrence and Mark A. Girolami (Eds.). JMLR.org, 788-- 797 . http:\/\/proceedings.mlr.press\/v22\/mladenov12.html Martin Mladenov, Babak Ahmadi, and Kristian Kersting. 2012. Lifted Linear Programming. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2012, La Palma, Canary Islands, Spain, April 21-23, 2012 (JMLR Proceedings, Vol. 22), Neil D. Lawrence and Mark A. Girolami (Eds.). JMLR.org, 788--797. http:\/\/proceedings.mlr.press\/v22\/mladenov12.html"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021","author":"Morris Christopher","year":"2021","unstructured":"Christopher Morris , Matthias Fey , and Nils M. Kriege . 2021. The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs . In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021 , Virtual Event \/ Montreal, Canada , 19-27 August 2021 , Zhi-Hua Zhou (Ed.). ijcai.org, 4543--4550. Christopher Morris, Matthias Fey, and Nils M. Kriege. 2021. The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event \/ Montreal, Canada, 19-27 August 2021, Zhi-Hua Zhou (Ed.). ijcai.org, 4543--4550."},{"key":"e_1_2_1_30_1","volume-title":"Borgwardt","author":"Morris Christopher","year":"2021","unstructured":"Christopher Morris , Yaron Lipman , Haggai Maron , Bastian Rieck , Nils M. Kriege , Martin Grohe , Matthias Fey , and Karsten M . Borgwardt . 2021 . Weisfeiler and Leman go Machine Learning : The Story so far. CoRR abs\/2112.09992 (2021). arXiv:2112.09992 Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten M. Borgwardt. 2021. Weisfeiler and Leman go Machine Learning: The Story so far. CoRR abs\/2112.09992 (2021). arXiv:2112.09992"},{"key":"e_1_2_1_31_1","volume-title":"Gaurav Rattan, and Martin Grohe.","author":"Morris Christopher","year":"2019","unstructured":"Christopher Morris , Martin Ritzert , Matthias Fey , William L. Hamilton , Jan Eric Lenssen , Gaurav Rattan, and Martin Grohe. 2019 . Weisfeiler and Leman Go Neural: Higher- Order Graph Neural Networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019. AAAI Press , 4602--4609. Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019. AAAI Press, 4602--4609."},{"key":"e_1_2_1_32_1","unstructured":"University of Tsukuba. 2001. Tsukuba Stereo Datasets. https:\/\/vision.middlebury.edu\/stereo\/data\/scenes2001\/  University of Tsukuba. 2001. Tsukuba Stereo Datasets. https:\/\/vision.middlebury.edu\/stereo\/data\/scenes2001\/"},{"key":"e_1_2_1_33_1","unstructured":"Google OR-Tools. [n.d.]. Setting solver limits. https:\/\/developers.google.com\/optimization\/cp\/cp_tasks#time-limit  Google OR-Tools. [n.d.]. Setting solver limits. https:\/\/developers.google.com\/optimization\/cp\/cp_tasks#time-limit"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"e_1_2_1_35_1","unstructured":"Jani Patokallio. 2014. OpenFlights. https:\/\/openflights.org\/data.html#route  Jani Patokallio. 2014. OpenFlights. https:\/\/openflights.org\/data.html#route"},{"key":"e_1_2_1_36_1","volume-title":"Domingos","author":"Richardson Matthew","year":"2003","unstructured":"Matthew Richardson , Rakesh Agrawal , and Pedro M . Domingos . 2003 . Trust Management for the Semantic Web. In ISWC (Lecture Notes in Computer Science , Vol. 2870). Springer, 351-- 368 . Matthew Richardson, Rakesh Agrawal, and Pedro M. Domingos. 2003. Trust Management for the Semantic Web. In ISWC (Lecture Notes in Computer Science, Vol. 2870). Springer, 351--368."},{"key":"e_1_2_1_37_1","volume-title":"Kornaropoulos","author":"Riondato Matteo","year":"2014","unstructured":"Matteo Riondato and Evgenios M . Kornaropoulos . 2014 . Fast approximation of betweenness centrality through sampling. In WSDM. ACM , 413--422. Matteo Riondato and Evgenios M. Kornaropoulos. 2014. Fast approximation of betweenness centrality through sampling. In WSDM. ACM, 413--422."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411866"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014573219977"},{"key":"e_1_2_1_40_1","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"Schrijver A.","unstructured":"A. Schrijver . 2003. Combinatorial Optimization - Polyhedra and Efficiency . Springer . A. Schrijver. 2003. Combinatorial Optimization - Polyhedra and Efficiency. Springer."},{"key":"e_1_2_1_41_1","volume-title":"Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held","author":"Shervashidze Nino","year":"2009","unstructured":"Nino Shervashidze and Karsten M. Borgwardt . 2009. Fast subtree kernels on graphs . In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009 , Vancouver, British Columbia, Canada, Yoshua Bengio, Dale Schuurmans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta (Eds.). Curran Associates, Inc., 1660--1668. Nino Shervashidze and Karsten M. Borgwardt. 2009. Fast subtree kernels on graphs. In Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, Yoshua Bengio, Dale Schuurmans, John D. Lafferty, Christopher K. I. Williams, and Aron Culotta (Eds.). Curran Associates, Inc., 1660--1668."},{"key":"e_1_2_1_42_1","volume-title":"Enumerative combinatorics","author":"Stanley Richard P.","unstructured":"Richard P. Stanley . 2012. Enumerative combinatorics . Volume 1 ( second ed.). Cambridge Studies in Advanced Mathematics, Vol. 49. Cambridge University Press , Cambridge. xiv+626 pages. Richard P. Stanley. 2012. Enumerative combinatorics. Volume 1 (second ed.). Cambridge Studies in Advanced Mathematics, Vol. 49. Cambridge University Press, Cambridge. xiv+626 pages."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-020-00200-8"},{"key":"e_1_2_1_44_1","volume-title":"7th International Conference on Learning Representations, ICLR 2019","author":"Xu Keyulu","year":"2019","unstructured":"Keyulu Xu , Weihua Hu , Jure Leskovec , and Stefanie Jegelka . 2019 . How Powerful are Graph Neural Networks? . In 7th International Conference on Learning Representations, ICLR 2019 , New Orleans, LA, USA , May 6-9, 2019. OpenReview.net. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1086\/jar.33.4.3629752"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3574245.3574264","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T23:15:05Z","timestamp":1677021305000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3574245.3574264"}},"subtitle":["Approximating Max-Flow, Linear Programs, and Centrality"],"short-title":[],"issued":{"date-parts":[[2022,12]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.14778\/3574245.3574264"],"URL":"https:\/\/doi.org\/10.14778\/3574245.3574264","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,12]]},"assertion":[{"value":"2023-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}