Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

• URL: http://arxiv.org/abs/2506.08405v1
• Date: Tue, 10 Jun 2025 03:22:49 GMT
• Title: Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
• Authors: Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu,
• Abstract summary: We propose a new query model regarding the number of connected components.<n>We show that $Omega(n2)$ non-adaptive queries are required, even when $m = O(n)$.<n>We also provide an $O(mlog n + nlog2 n)$ query algorithm using only two rounds of adaptivity.
• Score: 16.68420358221284
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The graph reconstruction problem has been extensively studied under various query models. In this paper, we propose a new query model regarding the number of connected components, which is one of the most basic and fundamental graph parameters. Formally, we consider the problem of reconstructing an $n$-node $m$-edge graph with oracle queries of the following form: provided with a subset of vertices, the oracle returns the number of connected components in the induced subgraph. We show $\Theta(\frac{m \log n}{\log m})$ queries in expectation are both sufficient and necessary to adaptively reconstruct the graph. In contrast, we show that $\Omega(n^2)$ non-adaptive queries are required, even when $m = O(n)$. We also provide an $O(m\log n + n\log^2 n)$ query algorithm using only two rounds of adaptivity.

Related papers

• Graph Inference with Effective Resistance Queries [2.2349172369559156]
  We study graph inference using an oracle that returns the effective resistance (ER) between a pair of vertices.<n>Although it is known that an $n$-vertex graph can be uniquely reconstructed from all possible ER queries, little else is known.
  arXiv  Detail & Related papers  (2025-02-25T16:37:25Z)
• Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
  Complex logical query answering (CLQA) is a recently emerged task of graph machine learning. We introduce the concept of Neural Graph Database (NGDBs) NGDB consists of a Neural Graph Storage and a Neural Graph Engine.
  arXiv  Detail & Related papers  (2023-03-26T04:03:37Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
  arXiv  Detail & Related papers  (2022-08-18T09:19:01Z)
• Learning Graph Partitions [2.3224617218247126]
  Given a partition of a graph into connected components, the membership oracle asserts whether any two vertices of the graph lie in the same component or not. We prove that for $nge kge 2$, learning the components of an $n$-vertex hidden graph with $k$ components requires at least $frac12(n-k)(k-1)$ membership queries.
  arXiv  Detail & Related papers  (2021-12-15T05:28:45Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Outlining and Filling: Hierarchical Query Graph Generation for Answering Complex Questions over Knowledge Graph [16.26384829957165]
  We propose a new two-stage approach to build query graphs. In the first stage, the top-$k$ related instances are collected by simple strategies. In the second stage, a graph generation model performs hierarchical generation.
  arXiv  Detail & Related papers  (2021-11-01T07:08:46Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• 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)
• Classical algorithms for Forrelation [2.624902795082451]
  We study the forrelation problem: given a pair of $n$-bit Boolean functions $f$ and $g$, estimate the correlation between $f$ and the Fourier transform of $g$. This problem is known to provide the largest possible quantum speedup in terms of its query complexity. We show that the graph-based forrelation problem can be solved on a classical computer in time $O(n)$ for any bipartite graph.
  arXiv  Detail & Related papers  (2021-02-13T17:25:41Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)
• Quantum algorithms for graph problems with cut queries [17.149741568581096]
  We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d log(n)2)$ many cut queries. We also show that a quantum algorithm can learn a general graph with $O(sqrtm log(n)3/2)$ many cut queries.
  arXiv  Detail & Related papers  (2020-07-16T12:21:01Z)
• Partial Recovery in the Graph Alignment Problem [0.0]
  We consider the problem of recovering, given two graphs, a one-to-one mapping between nodes that maximizes edge overlap. This problem can be viewed as a noisy version of the well-known graph isomorphism problem. We show that it is possible to achieve partial recovery in the $nqs=Theta(1)$ regime under certain additional assumptions.
  arXiv  Detail & Related papers  (2020-07-01T14:57:53Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  Existing deep neural methods require $Omega(n2)$ complexity by building up the adjacency matrix. We develop a novel autoregressive model, named BiGG, that utilizes this sparsity to avoid generating the full adjacency matrix. During training this autoregressive model can be parallelized with $O(log n)$ synchronization stages.
  arXiv  Detail & Related papers  (2020-06-28T04:37:57Z)

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.