Fugu-MT 論文翻訳(概要): Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

論文の概要: Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

arxiv url: http://arxiv.org/abs/2506.08405v1
Date: Tue, 10 Jun 2025 03:22:49 GMT
ステータス: 翻訳完了
システム内更新日: 2025-06-29 09:28:14.739465
Title: Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Title（参考訳）: 導出された部分グラフ中の連結成分の計数による最適グラフ再構成
Authors: Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu,
Abstract要約: 本稿では,接続コンポーネント数に関する新しいクエリモデルを提案する。たとえ$m = O(n)$であっても、$Omega(n2)$非適応クエリが要求されることを示す。また2ラウンドの適応性のみを用いた$O(mlog n + nlog2 n)$クエリアルゴリズムも提供する。
参考スコア（独自算出の注目度）: 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.
Abstract（参考訳）: グラフ再構成問題は、様々なクエリモデルの下で広く研究されている。本稿では,最も基本的で基本的なグラフパラメータである連結成分の数に関する新しいクエリモデルを提案する。形式的には、以下の形のオラクルクエリで$n$-node $m$-edgeグラフを再構築する問題を考察する。グラフを適応的に再構築するには,期待するクエリが十分かつ必要であることを示す。対照的に、$m = O(n)$ であっても、$\Omega(n^2)$ 非適応的なクエリが必要であることを示す。また、適応性の2ラウンドのみを用いた$O(m\log n + n\log^2 n)$クエリアルゴリズムも提供する。

関連論文リスト

Graph Inference with Effective Resistance Queries [2.2349172369559156]
一対の頂点間の有効抵抗(ER)を返すオラクルを用いてグラフ推論を研究する。 ERクエリから$n$-vertexグラフを一意に再構築できることは知られているが、他にはほとんど知られていない。
論文参考訳（メタデータ） (2025-02-25T16:37:25Z)
Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases [63.96793270418793]
複雑な論理クエリ応答(CLQA)は、グラフ機械学習の最近登場したタスクである。ニューラルグラフデータベース(NGDB)の概念を紹介する。 NGDBはNeural Graph StorageとNeural Graph Engineで構成されている。
論文参考訳（メタデータ） (2023-03-26T04:03:37Z)
Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文参考訳（メタデータ） (2022-08-18T09:19:01Z)
Learning Graph Partitions [2.3224617218247126]
グラフの連結成分への分割が与えられたとき、会員オラクルはグラフの任意の2つの頂点が同じ成分に含まれるか否かを主張する。我々は$nge kge 2$の場合、$k$コンポーネントで$n$-vertex隠れグラフのコンポーネントを学ぶには、少なくとも$frac12(n-k)(k-1)$メンバシップクエリが必要であることを証明している。
論文参考訳（メタデータ） (2021-12-15T05:28:45Z)
AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文参考訳（メタデータ） (2021-11-12T07:08:13Z)
Outlining and Filling: Hierarchical Query Graph Generation for Answering Complex Questions over Knowledge Graph [16.26384829957165]
クエリグラフを構築するための新しい2段階のアプローチを提案する。最初の段階では、上位$kの関連インスタンスは単純な戦略で収集される。第2段階では、グラフ生成モデルが階層生成を行う。
論文参考訳（メタデータ） (2021-11-01T07:08:46Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文参考訳（メタデータ） (2021-10-02T07:41:17Z)
Classical algorithms for Forrelation [2.624902795082451]
1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
論文参考訳（メタデータ） (2021-02-13T17:25:41Z)
Partial Recovery in the Graph Alignment Problem [0.0]
エッジオーバーラップを最大化するノード間の1対1のマッピングである2つのグラフが与えられた場合、回復する問題を考察する。この問題は、よく知られたグラフ同型問題のノイズバージョンと見なすことができる。我々は、ある追加仮定の下で$nqs=Theta(1)$ regimeで部分的回復を達成することができることを示す。
論文参考訳（メタデータ） (2020-07-01T14:57:53Z)
Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文参考訳（メタデータ） (2020-06-28T04:37:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。