通过复合查询精准重构带权图，突破传统最短路径查询的局限
Exact Learning of Weighted Graphs Using Composite Queries
- 设计复合查询机制，整合多个简单查询以高效获取图结构信息
- 在特定条件下仅需亚二次数量的查询即可完全恢复图的边与权重
- 适用于需要精确图重建的网络分析、生物信息学等场景
本文研究带权图的精确学习问题，已知顶点集 $V$，但未知边集 $E$ 与边权 $w$。目标是通过向预言机提问来完全确定所有边及其权重。我们发现，仅使用简单的最短路径长度查询通常不足以重构图。因此，研究了若干可行场景，在这些场景下可通过组合两个或三个简单查询的复合查询，以亚二次数量完成精确学习。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。