論文の概要: Exact Learning of Weighted Graphs Using Composite Queries
- arxiv url: http://arxiv.org/abs/2511.14882v1
- Date: Tue, 18 Nov 2025 20:02:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-20 15:51:28.512931
- Title: Exact Learning of Weighted Graphs Using Composite Queries
- Title（参考訳）: 複合クエリを用いた重み付きグラフのエクササイズ学習
- Authors: Michael T. Goodrich, Songyu Liu, Ioannis Panageas,
- Abstract要約: 問題は、オラクルから$G$に関する質問をすることで、その重みを含む$E$のすべてのエッジを決定することである。
合成クエリのサブクワッド数を用いて$G$を学習できるシナリオを多数検討する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 本稿では、重み付きグラフの頂点集合である$V$, 重み付きグラフの$G=(V,E,w)$が与えられるという、重み付きグラフの正確な学習問題を考察するが、$E$は与えられない。
グラフ再構成とも呼ばれるこの問題は、オラクルから$G$に関する質問をすることで、その重みを含む$E$のすべてのエッジを決定することである。
このように、単純なショートパス長のクエリは、一般に重み付きグラフを学ぶのに十分ではない。
そこで本研究では,2つないし3つの単純なクエリを組み合わせた合成クエリのサブクワッドラティック数を用いて,$G$を学習可能なシナリオを多数検討する。
関連論文リスト
- Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs [16.68420358221284]
本稿では,接続コンポーネント数に関する新しいクエリモデルを提案する。
たとえ$m = O(n)$であっても、$Omega(n2)$非適応クエリが要求されることを示す。
また2ラウンドの適応性のみを用いた$O(mlog n + nlog2 n)$クエリアルゴリズムも提供する。
論文 参考訳（メタデータ） (2025-06-10T03:22:49Z) - Graph Inference with Effective Resistance Queries [2.2349172369559156]
一対の頂点間の有効抵抗(ER)を返すオラクルを用いてグラフ推論を研究する。
ERクエリから$n$-vertexグラフを一意に再構築できることは知られているが、他にはほとんど知られていない。
論文 参考訳（メタデータ） (2025-02-25T16:37:25Z) - Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs [60.71360240206726]
大規模言語モデル(LLM)は、特に知識集約的なタスクにおいて幻覚に悩まされる。
既存の研究は、外部知識コーパスから取得した個々のテキスト単位でLLMを拡張することを提案する。
本稿では,グラフを反復的に推論することで,LLMをグラフで拡張するためのGraph Chain-of-thinkt (Graph-CoT) というフレームワークを提案する。
論文 参考訳（メタデータ） (2024-04-10T15:41:53Z) - A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。
特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-28T21:23:40Z) - Rule-based Graph Repair using Minimally Restricted Consistency-Improving
Transformations [65.268245109828]
一貫性の維持と一貫性の向上という,一貫性の新たな概念を導入します。
本稿では, 規則に基づくグラフ修復手法を提案する。
論文 参考訳（メタデータ） (2023-07-18T11:20:54Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Learning Graph Partitions [2.3224617218247126]
グラフの連結成分への分割が与えられたとき、会員オラクルはグラフの任意の2つの頂点が同じ成分に含まれるか否かを主張する。
我々は$nge kge 2$の場合、$k$コンポーネントで$n$-vertex隠れグラフのコンポーネントを学ぶには、少なくとも$frac12(n-k)(k-1)$メンバシップクエリが必要であることを証明している。
論文 参考訳（メタデータ） (2021-12-15T05:28:45Z) - Outlining and Filling: Hierarchical Query Graph Generation for Answering
Complex Questions over Knowledge Graph [16.26384829957165]
クエリグラフを構築するための新しい2段階のアプローチを提案する。
最初の段階では、上位$kの関連インスタンスは単純な戦略で収集される。
第2段階では、グラフ生成モデルが階層生成を行う。
論文 参考訳（メタデータ） (2021-11-01T07:08:46Z) - Query2box: Reasoning over Knowledge Graphs in Vector Space using Box
Embeddings [84.0206612938464]
query2boxは、不完全な知識グラフ上の任意のクエリを推論するための埋め込みベースのフレームワークである。
query2boxは、スケーラブルな方法で$wedge$, $vee$, $exists$で任意の論理クエリを処理可能であることを示す。
本稿では,3つの大規模KGに対するQuery2boxの有効性を示すとともに,クエリ2boxが技術状況に対して最大25%の相対的な改善を達成可能であることを示す。
論文 参考訳（メタデータ） (2020-02-14T11:20:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。