Exact Learning of Weighted Graphs Using Composite Queries
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Community Detection: Exact Recovery in Weighted Graphs
In community detection, the exact recovery of communities (clusters) has been mainly investigated under the general stochastic block model with edges drawn from Bernoulli distributions. This paper considers the exact rec…
Community DetectionStochastic Block ModelEfficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficiency on small-treewidth graphs (e.g., roa…
On the exact learnability of graph parameters: The case of partition functions
We study the exact learnability of real valued graph parameters $f$ which are known to be representable as partition functions which count the number of weighted homomorphisms into a graph $H$ with vertex weights $\alpha…
Exact Clustering of Weighted Graphs via Semidefinite Programming
As a model problem for clustering, we consider the densest k-disjoint-clique problem of partitioning a weighted complete graph into k disjoint subgraphs such that the sum of the densities of these subgraphs is maximized.…
ClusteringWeighted Theta Functions and Embeddings with Applications to Max-Cut, Clustering and Summarization
We introduce a unifying generalization of the Lovász theta function, and the associated geometric embedding, for graphs with weights on both nodes and edges. We show how it can be computed exactly by semidefinite program…
ClusteringDiversityDocument SummarizationGraph Embedding