Related papers: Exact Learning of Weighted Graphs Using Composite Queries

Exact Learning of Weighted Graphs Using Composite Queries

URL: http://arxiv.org/abs/2511.14882v1
Date: Tue, 18 Nov 2025 20:02:02 GMT
Title: Exact Learning of Weighted Graphs Using Composite Queries
Authors: Michael T. Goodrich, Songyu Liu, Ioannis Panageas,
Abstract summary: The problem is to determine all the edges of $E$, including their weights, by asking queries about $G$ from an oracle.<n>We study a number of scenarios where it is possible to learn $G$ using a subquadratic number of composite queries.
Score: 15.854004861956552
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper, we study the exact learning problem for weighted graphs, where we are given the vertex set, $V$, of a weighted graph, $G=(V,E,w)$, but we are not given $E$. The problem, which is also known as graph reconstruction, is to determine all the edges of $E$, including their weights, by asking queries about $G$ from an oracle. As we observe, using simple shortest-path length queries is not sufficient, in general, to learn a weighted graph. So we study a number of scenarios where it is possible to learn $G$ using a subquadratic number of composite queries, which combine two or three simple queries.

Related papers

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs [16.68420358221284]
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.
arXiv Detail & Related papers (2025-06-10T03:22:49Z)
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)
Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
Large language models (LLMs) suffer from hallucinations, especially on knowledge-intensive tasks. Existing works propose to augment LLMs with individual text units retrieved from external knowledge corpora. We propose a framework called Graph Chain-of-thought (Graph-CoT) to augment LLMs with graphs by encouraging LLMs to reason on the graph iteratively.
arXiv Detail & Related papers (2024-04-10T15:41:53Z)
A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
We present an algorithm that learns the edges of $G$ in at most $tildeO(d2m3/4)$ quantum queries. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in $tildeO(sqrtm)$ quantum queries.
arXiv Detail & Related papers (2024-02-28T21:23:40Z)
Rule-based Graph Repair using Minimally Restricted Consistency-Improving Transformations [65.268245109828]
We introduce new notions of consistency, which we call consistency-maintaining and consistency-increasing transformations and rules. We present an rule-based graph repair approach that is able to repair so-called emphcircular conflict-free constraints.
arXiv Detail & Related papers (2023-07-18T11:20:54Z)
Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
We prove that the minimax regret is proportional to $R*$ for any graph and time horizon $T$. Introducing an intricate exploration strategy, we define the mainAlgorithm algorithm that achieves the minimax optimal regret bound.
arXiv Detail & Related papers (2023-06-05T15:35:00Z)
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)
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)
Query2box: Reasoning over Knowledge Graphs in Vector Space using Box Embeddings [84.0206612938464]
query2box is an embedding-based framework for reasoning over arbitrary queries on incomplete knowledge graphs. We show that query2box is capable of handling arbitrary logical queries with $wedge$, $vee$, $exists$ in a scalable manner. We demonstrate the effectiveness of query2box on three large KGs and show that query2box achieves up to 25% relative improvement over the state of the art.
arXiv Detail & Related papers (2020-02-14T11:20:10Z)

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