论文标题
在线密集的子图通过模糊反馈发现
Online Dense Subgraph Discovery via Blurred-Graph Feedback
论文作者
论文摘要
密集的子图发现旨在在边缘加权图中找到密集的组件。这是一项基本的图形挖掘任务，具有各种应用程序，因此最近受到了很多关注。尽管大多数现有方法都假定每个单个边缘重量都很容易获得，但是在实践中，这种假设不一定有效。在本文中，我们为密集的子图发现了一个新颖的学习问题，其中学习者查询边缘子集，而不是单个边缘，并观察到查询子集中的边缘权重。对于这个问题，我们首先提出了一种多项式时算法，该算法获得了具有很高概率的几乎最佳溶液。此外，要处理大型图，我们设计了具有理论保证的更可扩展的算法。使用实际图的计算实验证明了我们算法的有效性。
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.
