論文の概要: Distances for Markov Chains, and Their Differentiation

• arxiv url: http://arxiv.org/abs/2302.08621v2
• Date: Fri, 16 Feb 2024 21:58:00 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-21 07:23:24.944993
• Title: Distances for Markov Chains, and Their Differentiation
• Title（参考訳）: マルコフ鎖の距離とその分化
• Authors: Tristan Brug\`ere, Zhengchao Wan and Yusu Wang
• Abstract要約: ノード属性を持つ有向グラフを持つマルコフ連鎖の距離を生成する統一的なフレームワークを提案する。 割引されたWL距離は理論的性質に優れており,既存のOTCおよびWL距離のいくつかの制限に対処できることを示す。
• 参考スコア（独自算出の注目度）: 6.534615862914506
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: (Directed) graphs with node attributes are a common type of data in various applications and there is a vast literature on developing metrics and efficient algorithms for comparing them. Recently, in the graph learning and optimization communities, a range of new approaches have been developed for comparing graphs with node attributes, leveraging ideas such as the Optimal Transport (OT) and the Weisfeiler-Lehman (WL) graph isomorphism test. Two state-of-the-art representatives are the OTC distance proposed in (O'Connor et al., 2022) and the WL distance in (Chen et al., 2022). Interestingly, while these two distances are developed based on different ideas, we observe that they both view graphs as Markov chains, and are deeply connected. Indeed, in this paper, we propose a unified framework to generate distances for Markov chains (thus including (directed) graphs with node attributes), which we call the Optimal Transport Markov (OTM) distances, that encompass both the OTC and the WL distances. We further introduce a special one-parameter family of distances within our OTM framework, called the discounted WL distance. We show that the discounted WL distance has nice theoretical properties and can address several limitations of the existing OTC and WL distances. Furthermore, contrary to the OTC and the WL distances, our new discounted WL distance can be differentiated after a entropy-regularization similar to the Sinkhorn distance, making it suitable to use in learning frameworks, e.g., as the reconstruction loss in a graph generative model.
• Abstract（参考訳）: ノード属性を持つ(直接)グラフは、様々なアプリケーションで一般的なタイプのデータであり、それを比較するためのメトリクスや効率的なアルゴリズムの開発には膨大な文献がある。 近年、グラフ学習と最適化のコミュニティでは、最適なトランスポート(ot)やweisfeiler-lehman(wl)グラフ同型テストのようなアイデアを活用して、グラフとノード属性を比較するための新しいアプローチが開発されている。 2つの最先端の代表者は(O'Connor et al., 2022)で提案されたOCC距離と(Chen et al., 2022)WL距離である。 興味深いことに、これらの2つの距離は異なるアイデアに基づいて開発されているが、グラフをマルコフ連鎖とみなし、深く結びついている。 実際,本論文では,OTC と WL の両方を包含する Optimal Transport Markov (OTM) 距離と呼ばれるマルコフ連鎖(ノード属性を持つ(直接)グラフを含む)距離を生成する統一的なフレームワークを提案する。 さらに,OTMフレームワーク内に,ディスカウントWL距離と呼ばれる,特別な1パラメータ距離ファミリを導入する。 割引されたWL距離は理論的性質に優れており,既存のOTCおよびWL距離のいくつかの制限に対処できることを示す。 さらに,OTCとWL距離とは対照的に,新しい割引されたWL距離はシンクホーン距離と同様のエントロピー規則化後に区別することができ,例えばグラフ生成モデルにおける再構成損失として,学習フレームワークでの使用に適している。

関連論文リスト

• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• Exploiting Edge Features in Graphs with Fused Network Gromov-Wasserstein Distance [18.522233517515975]
  ノードとエッジが特徴を持つグラフを比較するために,Gromov-Wasserstein距離の拡張を導入する。 入力空間または出力空間でグラフが発生する学習タスクにおいて、新しい距離の有効性を実証的に示す。
  論文  参考訳（メタデータ） (2023-09-28T17:05:03Z)
• Markovian Sliced Wasserstein Distances: Beyond Independent Projections [51.80527230603978]
  我々は、射影方向にマルコフ構造を課す新しいSW距離の族、Markovian sliced Wasserstein (MSW) 距離を導入する。 フロー,色移動,深部生成モデルなどの様々な応用において,従来のSW変種との距離を比較し,MSWの良好な性能を示す。
  論文  参考訳（メタデータ） (2023-01-10T01:58:15Z)
• Wasserstein Graph Distance Based on $L_1$-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees [17.855077077275567]
  Weisfeiler-Lehman (WL) テストはグラフ機械学習において広く使われているアルゴリズムである。 この問題に対処するために,WWLS(Wasserstein WL Subtree)距離と呼ばれる新しいグラフ測度を提案する。 提案したWWLS距離は,計量検証およびグラフ分類実験において,ベースラインよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-07-09T07:45:16Z)
• Template based Graph Neural Network with Optimal Transport Distances [11.56532171513328]
  現在のグラフニューラルネットワーク(GNN)アーキテクチャは、2つの重要なコンポーネントに依存している。 本稿では,学習可能なグラフテンプレートとの距離をグラフ表現のコアに配置する新しい視点を提案する。 この距離埋め込みは、Fused Gromov-Wasserstein (FGW) 距離という最適な輸送距離によって構築される。
  論文  参考訳（メタデータ） (2022-05-31T12:24:01Z)
• On a linear fused Gromov-Wasserstein distance for graph structured data [2.360534864805446]
  埋め込み間のユークリッド距離として定義される2つのグラフ間の新しい距離である線形FGWを提案する。 提案した距離の利点は2つある: 1) ノードの特徴とグラフの構造を考慮して、カーネルベースのフレームワークにおけるグラフ間の類似性を測定する。
  論文  参考訳（メタデータ） (2022-03-09T13:43:18Z)
• Weisfeiler-Lehman meets Gromov-Wasserstein [8.142448470345762]
  ラベル付きマルコフ連鎖間の距離の概念であるWeisfeiler-Lehman距離を提案する。 WL距離は時間計算可能であり、WLテストとも互換性がある。 LMMC上のニューラルネットワークアーキテクチャを同定し、連続関数の普遍的なw.r.t.連続関数であることが判明した。
  論文  参考訳（メタデータ） (2022-02-05T05:53:31Z)
• FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
  グラフ比較は、グラフ間の類似点と相違点の識別を扱う。 大きな障害は、グラフの未知のアライメントと、正確で安価な比較指標の欠如である。 本研究では,フィルタグラフ距離近似を導入する。
  論文  参考訳（メタデータ） (2021-09-09T17:43:07Z)
• Embedding Signals on Knowledge Graphs with Unbalanced Diffusion Earth Mover's Distance [63.203951161394265]
  現代の機械学習では、多くの領域における観測間の相互作用や類似性によって生じる大きなグラフに遭遇することが一般的である。 本研究では,地球移動器距離(EMD)と測地コストを基礎となるグラフ上で比較し,グラフ信号のデータセットを整理する。 いずれの場合も,UDEMDをベースとした埋め込みは,他の手法と比較して高精度な距離を求めることができる。
  論文  参考訳（メタデータ） (2021-07-26T17:19:02Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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