Online Dense Subgraph Discovery via Blurred-Graph Feedback

• URL: http://arxiv.org/abs/2006.13642v1
• Date: Wed, 24 Jun 2020 11:37:33 GMT
• Title: Online Dense Subgraph Discovery via Blurred-Graph Feedback
• Authors: Yuko Kuroki, Atsushi Miyauchi, Junya Honda, Masashi Sugiyama
• Abstract summary: We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
• Score: 87.9850024070244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  Graph-based algorithms have demonstrated state-of-the-art performance in the nearest neighbor search (NN-Search) problem. There exists a practice-to-theory gap in the graph-based NN-Search algorithms. We present theoretical guarantees of solving NN-Search via greedy search on ANN-Graph for low dimensional and dense vectors.
  arXiv  Detail & Related papers  (2023-03-10T21:18:34Z)
• Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams [35.943447765433774]
  We propose a weighted sampling algorithm called WSD for estimating the subgraph count in a fully dynamic graph stream. We determine the weights of edges in a data-driven fashion, using a novel method based on reinforcement learning.
  arXiv  Detail & Related papers  (2022-11-13T03:01:34Z)
• LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation [6.316693022958222]
  We propose a reinforcement learning algorithm that learns how to navigate the space of possible subgraphs using an Euclidean subgraph embedding as its map. LeNSE identifies small subgraphs yielding solutions comparable to those found by running the embeddings on the entire graph, but at a fraction of the total run time.
  arXiv  Detail & Related papers  (2022-05-20T11:54:03Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics. We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
  arXiv  Detail & Related papers  (2021-12-08T08:23:37Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  The planted densest subgraph detection problem refers to the task of testing whether in a given (random) graph there is a subgraph that is unusually dense. In this paper, we consider a natural variant of the above problem, where one can only observe a relatively small part of the graph using adaptive edge queries. For this model, we determine the number of queries necessary and sufficient (accompanied with a quasi-polynomial optimal algorithm) for detecting the presence of the planted subgraph.
  arXiv  Detail & Related papers  (2021-10-02T07:41:17Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner? Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.
  arXiv  Detail & Related papers  (2021-06-08T16:10:36Z)
• The Generalized Mean Densest Subgraph Problem [30.33731479053404]
  We introduce a new family of dense subgraph objectives, parameterized by a single parameter $p$. Our objective captures both the standard densest subgraph problem and the maximum $k$-core as special cases. A major contribution of our work is analyzing the performance of different types of peeling algorithms for dense subgraphs both in theory and practice.
  arXiv  Detail & Related papers  (2021-06-02T02:58:35Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods [44.007522460918565]
  Mining dense subgraphs is an important primitive across a spectrum of graph-mining tasks. We show that mining cliques and quasi-cliques of non-trivial sizes from real-world graphs is often not a difficult problem.
  arXiv  Detail & Related papers  (2020-08-18T15:50:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.