  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.
