Online Dense Subgraph Discovery via Blurred-Graph Feedback

Yuko Kuroki, Atsushi Miyauchi, Junya Honda, Masashi Sugiyama
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:5522-5532, 2020.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-kuroki20a, title = {Online Dense Subgraph Discovery via Blurred-Graph Feedback}, author = {Kuroki, Yuko and Miyauchi, Atsushi and Honda, Junya and Sugiyama, Masashi}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {5522--5532}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/kuroki20a/kuroki20a.pdf}, url = {https://proceedings.mlr.press/v119/kuroki20a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Online Dense Subgraph Discovery via Blurred-Graph Feedback %A Yuko Kuroki %A Atsushi Miyauchi %A Junya Honda %A Masashi Sugiyama %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-kuroki20a %I PMLR %P 5522--5532 %U https://proceedings.mlr.press/v119/kuroki20a.html %V 119 %X 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.
APA
Kuroki, Y., Miyauchi, A., Honda, J. & Sugiyama, M.. (2020). Online Dense Subgraph Discovery via Blurred-Graph Feedback. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:5522-5532 Available from https://proceedings.mlr.press/v119/kuroki20a.html.

Related Material