論文の概要: Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound

• arxiv url: http://arxiv.org/abs/2205.05838v1
• Date: Thu, 12 May 2022 02:10:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-13 12:26:38.417814
• Title: Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound
• Title（参考訳）: 効率的な下界を持つ直交グロモフ-ワッセルシュタインの不一致
• Authors: Hongwei Jin, Zishun Yu, Xinhua Zhang
• Abstract要約: Gromov-Wasserstein (GW) は、最適な輸送データセットに基づいて、構造化されたデータ間のノードグラフを定式化する。 本稿では,代入問題との関係から着想を得て,GWの代理としてGromov-Wasserstein離散性を提案する。
• 参考スコア（独自算出の注目度）: 11.086440815804226
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Comparing structured data from possibly different metric-measure spaces is a fundamental task in machine learning, with applications in, e.g., graph classification. The Gromov-Wasserstein (GW) discrepancy formulates a coupling between the structured data based on optimal transportation, tackling the incomparability between different structures by aligning the intra-relational geometries. Although efficient local solvers such as conditional gradient and Sinkhorn are available, the inherent non-convexity still prevents a tractable evaluation, and the existing lower bounds are not tight enough for practical use. To address this issue, we take inspiration from the connection with the quadratic assignment problem, and propose the orthogonal Gromov-Wasserstein (OGW) discrepancy as a surrogate of GW. It admits an efficient and closed-form lower bound with the complexity of $\mathcal{O}(n^3)$, and directly extends to the fused Gromov-Wasserstein (FGW) distance, incorporating node features into the coupling. Extensive experiments on both the synthetic and real-world datasets show the tightness of our lower bounds, and both OGW and its lower bounds efficiently deliver accurate predictions and satisfactory barycenters for graph sets.
• Abstract（参考訳）: 異なる測度空間からの構造化データを比較することは、例えばグラフ分類などの機械学習における基本的なタスクである。 グロモフ・ワッサーシュタイン(Gromov-Wasserstein、GW)は、最適輸送に基づく構造データ間の結合を定式化し、関係空間内を整列させることによって異なる構造間の非互換性に取り組む。 条件勾配やシンクホーンのような効率的な局所解法が利用できるが、固有の非凸性は依然としてトラクタブルな評価を防ぎ、既存の下界は実用には十分ではない。 この問題に対処するために、二次代入問題との結びつきから着想を得て、GWの代理として直交したGromov-Wasserstein(OGW)の不一致を提案する。 これは効率良く閉じた形の下界と$\mathcal{o}(n^3)$の複雑さを許容し、結合にノードの特徴を組み込んだグロモフ=ワッセルシュタイン距離(fgw)に直接拡張する。 合成と実世界の両方のデータセットに対する大規模な実験は、我々の下限の厳密さを示し、OGWとその下限は、グラフ集合に対して正確な予測と満足のいくバリセンタを効率的に提供する。

関連論文リスト

• Combining Optimal Transport and Embedding-Based Approaches for More Expressiveness in Unsupervised Graph Alignment [19.145556156889064]
  教師なしグラフアライメントは、グラフ構造とノード特徴のみを利用して、属性グラフのペア間の1対1ノード対応を見つける。 モデル表現性の理論的解析によって動機付けられたそれらの利点を組み合わせるための原理的アプローチを提案する。 我々は,問題を最大重み付けに還元することで,一対一のマッチング制約を最初に保証する。
  論文  参考訳（メタデータ） (2024-06-19T04:57:35Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Outlier-Robust Gromov-Wasserstein for Graph Data [31.895380224961464]
  我々は、Gromov-Wasserstein (GW) 距離のRGWと呼ばれる新しい頑健なバージョンを導入する。 RGWは、クルバック・リーバーの発散に基づくあいまいさ集合の中で楽観的に摂動する限界制約を特徴とする。 サブグラフマッチングや部分形状対応などの実世界のグラフ学習におけるRGWの有効性を示す。
  論文  参考訳（メタデータ） (2023-02-09T12:57:29Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Asymmetric Transfer Hashing with Adaptive Bipartite Graph Learning [95.54688542786863]
  既存のハッシュ法では、クエリと検索サンプルは同じドメイン内の同質な特徴空間にあると仮定する。 教師なし/半教師付き/教師付き実現のための非対称トランスファーハッシュ(ATH)フレームワークを提案する。 非対称ハッシュ関数と二部グラフを共同最適化することにより、知識伝達が達成できるだけでなく、特徴アライメントによる情報損失も回避できる。
  論文  参考訳（メタデータ） (2022-06-25T08:24:34Z)
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent [69.47594803719333]
  幾何学的中央値 (textGm) は、未破損データのロバストな推定を達成するための統計学における古典的な方法である。 本稿では,テキストscGmを一度に選択した座標ブロックにのみ適用することにより,スムーズな非テキスト問題に対して0.5の分解点を保持することができることを示す。
  論文  参考訳（メタデータ） (2021-06-16T15:55:50Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。 グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
  論文  参考訳（メタデータ） (2021-06-02T12:50:56Z)
• Quantized Gromov-Wasserstein [10.592277756185046]
  Quantized Gromov Wasserstein(qGW)は、部品を基本的なオブジェクトとして扱い、問題の理論上の上限の階層に収まるメトリクスです。 最適なgwマッチングを近似するアルゴリズムを開発し,アルゴリズムによる高速化とメモリ複雑性の低減を実現する。 我々は、最先端の状況を超えて、既存の文献よりも桁違いに大きいスケールでGWマッチングを適用することができる。
  論文  参考訳（メタデータ） (2021-04-05T17:03:20Z)
• Hogwild! over Distributed Local Data Sets with Linearly Increasing Mini-Batch Sizes [26.9902939745173]
  Hogwild!は非同期のGradient Descentを実装し、複数のスレッドが並列に、トレーニングデータを含む共通のリポジトリにアクセスする。 通信コストを削減するため,ローカルな計算ノードがより小さなミニバッチサイズを選択し始める方法を示す。
  論文  参考訳（メタデータ） (2020-10-27T03:46:09Z)
• Towards Deeper Graph Neural Networks with Differentiable Group Normalization [61.20639338417576]
  グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。 オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。 2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
  論文  参考訳（メタデータ） (2020-06-12T07:18:02Z)
• Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces [62.35667646858558]
  本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。 我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。 AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
  論文  参考訳（メタデータ） (2020-02-05T03:09:23Z)

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

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