{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:50:52Z","timestamp":1774986652372,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Hong Kong RGC","award":["17201823, 17203122, 17202121"],"award-info":[{"award-number":["17201823, 17203122, 17202121"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>Graphs are crucial for modeling complex relationships in fields like social networks and biology. A key aspect in graph theory is identifying dense subgraphs, with applications in various domains. Density decomposition refines this by analyzing a graph's global density structure. This concept has been independently rediscovered in research areas like graph mining, algorithm design, and economics.<\/jats:p>\n                  <jats:p>Recent advancements in maximum-flow algorithms allow for nearly-linear time computation of the density vector, but they struggle with large real-world graphs. To address this, iterative first-order methods based on convex optimization, such as the Frank-Wolfe algorithm and momentum-based methods like accelerated FISTA, have been developed to approximate density vectors.<\/jats:p>\n                  <jats:p>This work explores density decomposition through market dynamics, where edges represent buyers and nodes represent sellers in a Fisher market model. The iterative proportional response process, which converges to the Fisher market equilibrium, provides an alternative interpretation of density decomposition. In each step, agents allocate resources based on the proportion of benefit received, moving the system toward equilibrium.<\/jats:p>\n                  <jats:p>Since each proportional response update can be seen as a gradient descent step, we investigate whether momentum methods can speed up convergence. Traditional momentum uses a linear combination of current and previous solutions, whereas our novel exponential momentum variant uses geometric interpolation, aligning better with proportional adjustments. Empirical evaluations on large-scale real-world and synthetic graphs confirm the effectiveness of our methods. Notably, the proportional response algorithm with exponential momentum outperforms existing methods, delivering improvements by several orders of magnitude in some cases. This advancement is significant, as the resulting density vector is crucial for many downstream tasks in graph mining and algorithm design.<\/jats:p>","DOI":"10.1145\/3725405","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:22:29Z","timestamp":1750281749000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-5939-7271","authenticated-orcid":false,"given":"Quan","family":"Xue","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8340-235X","authenticated-orcid":false,"given":"T-H. Hubert","family":"Chan","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_2_2_2_1","volume-title":"Matrix Scaling and Fair Allocation. In WAOA (Lecture Notes in Computer Science","volume":"274","author":"Bansal Nikhil","year":"2021","unstructured":"Nikhil Bansal and Ilan Reuven Cohen. 2021. Contention Resolution, Matrix Scaling and Fair Allocation. In WAOA (Lecture Notes in Computer Science, Vol. 12982). Springer, 252--274."},{"key":"e_1_2_2_3_1","unstructured":"Richard E. Barlow David J. Bartholomew J. M. Bremner and H. D. Brunk. 1972. Statistical Inference Under Order Restrictions: The Theory and Application of Isotonic Regression. Wiley."},{"key":"e_1_2_2_4_1","series-title":"SIAM journal on imaging sciences","volume-title":"A fast iterative shrinkage-thresholding algorithm for linear inverse problems","author":"Beck Amir","year":"2009","unstructured":"Amir Beck and Marc Teboulle. 2009. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM journal on imaging sciences , Vol. 2, 1 (2009), 183--202."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3344999"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993594"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Benjamin E. Birnbaum Nikhil R. Devanur and Lin Xiao. 2011b. Distributed algorithms via gradient descent for fisher markets. In EC. ACM 127--136.","DOI":"10.1145\/1993574.1993594"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380140"},{"key":"e_1_2_2_9_1","article-title":"Spectral Properties of Hypergraph Laplacian and Approximation Algorithms","volume":"65","author":"Hubert Chan T.-H.","year":"2018","unstructured":"T.-H. Hubert Chan, Anand Louis, Zhihao Gavin Tang, and Chenzi Zhang. 2018. Spectral Properties of Hypergraph Laplacian and Approximation Algorithms. J. ACM, Vol. 65, 3 (2018), 15:1--15:48.","journal-title":"J. ACM"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2020.08.010"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_2_12_1","volume-title":"Torres","author":"Chekuri Chandra","year":"2022","unstructured":"Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. In SODA. SIAM, 1531--1555."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_2_14_1","volume-title":"Maximilian Probst Gutenberg, and Sushant Sachdeva","author":"Chen Li","year":"2022","unstructured":"Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. 2022. Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. In FOCS. IEEE, 612--623."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch T.-H. Hubert Chan and Mauro Sozio. 2017. Large Scale Density-friendly Graph Decomposition via Convex Programming. In WWW. ACM 233--242.","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1513876.1513879"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_2_19_1","volume-title":"Hypergraph models of biological networks to identify genes critical to pathogenic viral response. BMC bioinformatics","author":"Feng Song","year":"2021","unstructured":"Song Feng, Emily Heath, Brett Jefferson, Cliff Joslyn, Henry Kvinge, Hugh D. Mitchell, Brenda Praggastis, Amie J. Eisfeld, Amy C. Sims, Larissa B. Thackray, Shufang Fan, Kevin B. Walters, Peter J. Halfmann, Danielle Westhoff-Smith, Qing Tan, Vineet D. Menachery, Timothy P. Sheahan, Adam S. Cockrell, Jacob F. Kocher, Kelly G. Stratton, Natalie C. Heller, Lisa M. Bramer, Michael S. Diamond, Ralph S. Baric, Katrina M. Waters, Yoshihiro Kawaoka, Jason E. McDermott, and Emilie Purvine. 2021. Hypergraph models of biological networks to identify genes critical to pathogenic viral response. BMC bioinformatics, Vol. 22, 1 (2021), 1--287."},{"key":"e_1_2_2_20_1","volume-title":"Mathematical Investigations in the Theory of Value and Prices. (","author":"Fisher Irving","year":"1892","unstructured":"Irving Fisher. 1892. Mathematical Investigations in the Theory of Value and Prices. ( 1892)."},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"Eugene Fratkin Brian T. Naughton Douglas L. Brutlag and Serafim Batzoglou. 2006. MotifCut: regulatory motifs finding with maximum density subgraphs. In ISMB (Supplement of Bioinformatics). 156--157.","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.2.186"},{"key":"e_1_2_2_23_1","unstructured":"David Gibson Ravi Kumar and Andrew Tomkins. 2005. Discovering Large Dense Subgraphs in Massive Graphs. In VLDB. ACM 721--732."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_2_2_25_1","unstructured":"Andrew V Goldberg. 1984. Finding a maximum density subgraph. (1984)."},{"key":"e_1_2_2_26_1","unstructured":"Elfarouk Harb Kent Quanrud and Chandra Chekuri. 2022. Faster and Scalable Algorithms for Densest Subgraph and Decomposition. In NeurIPS."},{"key":"e_1_2_2_27_1","first-page":"1","article-title":"Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing. In ESA (LIPIcs, Vol. 274)","volume":"56","author":"Harb Elfarouk","year":"2023","unstructured":"Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. 2023. Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing. In ESA (LIPIcs, Vol. 274). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 56:1--56:17.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588923"},{"key":"e_1_2_2_29_1","volume-title":"ICML (1) (JMLR Workshop and Conference Proceedings","author":"Jaggi Martin","unstructured":"Martin Jaggi. 2013. Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization. In ICML (1) (JMLR Workshop and Conference Proceedings, Vol. 28). JMLR.org, 427--435."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.11.011"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3653298"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3399676"},{"key":"e_1_2_2_35_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5906"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00029"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551826"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00587-4"},{"key":"e_1_2_2_41_1","first-page":"543","article-title":"A method for solving the convex programming problem with convergence rate O(1\/k2)","volume":"269","author":"Nesterov Yurii","year":"1983","unstructured":"Yurii Nesterov. 1983. A method for solving the convex programming problem with convergence rate O(1\/k2). Proceedings of the USSR Academy of Sciences , Vol. 269 (1983), 543--547. https:\/\/api.semanticscholar.org\/CorpusID:145918791","journal-title":"Proceedings of the USSR Academy of Sciences"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120206"},{"key":"e_1_2_2_43_1","doi-asserted-by":"crossref","unstructured":"Lu Qin Rong-Hua Li Lijun Chang and Chengqi Zhang. 2015. Locally Densest Subgraph Discovery. In KDD. ACM 965--974.","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0058"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_2_46_1","volume-title":"Density-friendly graph decomposition. ACM Transactions on Knowledge Discovery from Data (TKDD)","author":"Tatti Nikolaj","year":"2019","unstructured":"Nikolaj Tatti. 2019. Density-friendly graph decomposition. ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 13, 5 (2019), 1--29."},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_2_48_1","doi-asserted-by":"crossref","unstructured":"Xiaowei Ye Rong-Hua Li Lei Liang Zhizhen Liu Longlong Lin and Guoren Wang. 2024. Efficient and Effective Anchored Densest Subgraph Search: A Convex-programming based Approach. In KDD. ACM 3907--3918.","DOI":"10.1145\/3637528.3671727"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02930-1_48"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725405","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:59:55Z","timestamp":1774983595000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725405"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725405"],"URL":"https:\/\/doi.org\/10.1145\/3725405","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}