Faster and Efficient Density Decomposition via Proportional Response with Exponential Momentum

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. 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. 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. 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.