# Online Dense Subgraph Discovery via Blurred-Graph Feedback

arXiv: https://arxiv.org/abs/2006.13642 · HTML: https://mlsanity.com/paper/2006.13642/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2020.

## Built on by (most cited first, 4 of 4)

- [A Survey on the Densest Subgraph Problem and Its Variants](https://mlsanity.com/paper/2303.14467/) (2023)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems](https://mlsanity.com/paper/2505.17443/) (2025)

## Abstract (arXiv)

Dense subgraph discovery aims to find a dense component in edge-weighted graphs. This is a fundamental graph-mining task with a variety of applications and thus has received much attention recently. Although most existing methods assume that each individual edge weight is easily obtained, such an assumption is not necessarily valid in practice. In this paper, we introduce a novel learning problem for dense subgraph discovery in which a learner queries edge subsets rather than only single edges and observes a noisy sum of edge weights in a queried subset. For this problem, we first propose a polynomial-time algorithm that obtains a nearly-optimal solution with high probability. Moreover, to deal with large-sized graphs, we design a more scalable algorithm with a theoretical guarantee. Computational experiments using real-world graphs demonstrate the effectiveness of our algorithms.