論文の概要: Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing

• arxiv url: http://arxiv.org/abs/2609.03094v1
• Date: Wed, 02 Sep 2026 19:08:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-04 18:28:38.841265
• Title: Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing
• Title（参考訳）: 離散Gromov-Wasserstein双対性:アルゴリズムと同型テスト
• Abstract要約: グロモフ・ワッサーシュタイン距離(Gromov-Wasserstein distance, GW)は、その内在的構造のみに基づいて測度(mm)空間を整列する原理的な枠組みを提供する。 近年,2乗ユークリッド分布と内積コストとのGW距離の双対形式が導出された。 この研究は、エントロピー正則化と非非負のGW距離に対する新しい双対性結果を与える。 本稿では,正規化GW問題に対する正規化保証の対象となる新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 15.240268958496172
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Gromov-Wasserstein (GW) distance provides a principled framework for aligning metric measure (mm) spaces based solely on their intrinsic structure. Its ability to identify isomorphic representations of distributions across spaces renders it valuable for comparing data where equality up to isomorphism occurs naturally such as in graphs or, more generally, distributions on graphs. Recently, a type of dual form for the GW distance between Euclidean distributions with the squared Euclidean or inner product costs was derived, spurring the development of new statistical and algorithmic results for this setting. This work furnishes a novel duality result for GW distances with and without entropic regularization that is applicable to all finitely supported mm spaces. Leveraging this result, we derive the sample complexity of empirical GW distances between finite mm spaces, as well as limit distributions under proper centering and scaling. Furthermore, we propose new algorithms for solving the regularized GW problem which are subject to formal convergence guarantees. These statistical and algorithmic advancements give rise to a principled and efficient framework for testing whether two distributions on the set of graphs with a fixed number of nodes are isomorphic based on samples.
• Abstract（参考訳）: グロモフ・ワッサーシュタイン距離(Gromov-Wasserstein distance, GW)は、その内在的構造のみに基づいて測度(mm)空間を整列する原理的な枠組みを提供する。 空間にまたがる分布の同型表現を識別する能力は、グラフやより一般的にはグラフ上の分布のように、同型への等式が自然に発生するようなデータを比較するのに価値がある。 近年, ユークリッド分布と2乗ユークリッド分布, 内積コストとの間のGW距離の2つの形式が導出され, 新たな統計的およびアルゴリズム的な結果が得られた。 この研究は、すべての有限支持mm空間に適用可能なエントロピック正規化および非エントロピック正規化を伴うGW距離に対する新しい双対性結果を与える。 この結果を利用して、有限mm空間間の経験的GW距離のサンプル複雑さと、適切な集中とスケーリングの下での極限分布を導出する。 さらに,正規化GW問題に対する正規化GW問題の解法を提案する。 これらの統計的およびアルゴリズム的な進歩は、固定数のノードを持つグラフの集合上の2つの分布がサンプルに基づいて同型であるかどうかをテストするための原理的かつ効率的な枠組みを生み出す。

関連論文リスト

• $k$-Nearest Neighbors in Gromov--Wasserstein Space [0.0]
  我々はGromov-Wasserstein(GW)とfGW距離を用いて、$k$-nearest neighbors(k$-NN)分類を実装した。 我々は、GW-$k$-NNとfGW-$k$-NNが、複数のグラフデータセットで一貫してよく動作することを示す。
  論文  参考訳（メタデータ） (2026-06-09T01:33:01Z)
• Convex Distance Operator Transport: A Convex and Geometry-Preserving Formulation [9.94046521985351]
  異種領域間の分散を整列する最初の凸最適輸送フレームワークであるConvex Distance Transport Operator (CDOT)を紹介する。 CDOTは、距離と条件付き期待演算子を導入することで集約された距離構造を整列する演算子ベースの正規化を用いる。
  論文  参考訳（メタデータ） (2026-06-01T10:38:09Z)
• GMapLatent: Geometric Mapping in Latent Space [51.317738404571514]
  エンコーダ-デコーダAIアーキテクチャに基づくドメイン間の生成モデルは、現実的な画像の生成に大きな注目を集めている。 幾何学的マッピングに基づく正準潜在空間表現を導入し、領域間潜在空間を厳密かつ正確に整列する。 グレースケールおよびカラー画像の実験は、GMapLatentの有効性、有効性および適用性を検証する。
  論文  参考訳（メタデータ） (2025-03-30T12:02:36Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Outlier-Robust Gromov-Wasserstein for Graph Data [31.895380224961464]
  我々は、Gromov-Wasserstein (GW) 距離のRGWと呼ばれる新しい頑健なバージョンを導入する。 RGWは、クルバック・リーバーの発散に基づくあいまいさ集合の中で楽観的に摂動する限界制約を特徴とする。 サブグラフマッチングや部分形状対応などの実世界のグラフ学習におけるRGWの有効性を示す。
  論文  参考訳（メタデータ） (2023-02-09T12:57:29Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。 アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
  論文  参考訳（メタデータ） (2021-06-04T16:37:19Z)
• Distributional Sliced Embedding Discrepancy for Incomparable Distributions [22.615156512223766]
  Gromov-Wasserstein (GW) 距離は多様体学習とクロスドメイン学習の鍵となるツールである。 本稿では,分散スライシング,埋め込み,スライスされた分布間の閉形式ワッサーシュタイン距離の計算という2つの計算分布を比較する新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-04T15:11:30Z)
• Quantized Gromov-Wasserstein [10.592277756185046]
  Quantized Gromov Wasserstein(qGW)は、部品を基本的なオブジェクトとして扱い、問題の理論上の上限の階層に収まるメトリクスです。 最適なgwマッチングを近似するアルゴリズムを開発し,アルゴリズムによる高速化とメモリ複雑性の低減を実現する。 我々は、最先端の状況を超えて、既存の文献よりも桁違いに大きいスケールでGWマッチングを適用することができる。
  論文  参考訳（メタデータ） (2021-04-05T17:03:20Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。 複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。 これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
  論文  参考訳（メタデータ） (2021-03-25T14:35:07Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。