Online Dense Subgraph Discovery via Blurred-Graph Feedback
This work addresses a practical limitation in graph mining for applications where edge weight data is aggregated or noisy, offering a solution for scenarios like network analysis or recommendation systems, though it is incremental in adapting existing dense subgraph methods to a new query model.
The paper tackles the problem of dense subgraph discovery in edge-weighted graphs where individual edge weights are not directly accessible, by introducing a novel learning problem where queries involve subsets of edges and observe noisy sums of weights. They propose polynomial-time and scalable algorithms that achieve nearly-optimal solutions with high probability, as demonstrated through computational experiments on real-world graphs.
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.