論文の概要: fGOT: Graph Distances based on Filters and Optimal Transport

• arxiv url: http://arxiv.org/abs/2109.04442v1
• Date: Thu, 9 Sep 2021 17:43:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-10 16:12:11.189351
• Title: fGOT: Graph Distances based on Filters and Optimal Transport
• Title（参考訳）: fGOT:フィルタと最適輸送に基づくグラフ距離
• Authors: Hermina Petric Maretic, Mireille El Gheche, Giovanni Chierchia, Pascal Frossard
• Abstract要約: グラフ比較は、グラフ間の類似点と相違点の識別を扱う。 大きな障害は、グラフの未知のアライメントと、正確で安価な比較指標の欠如である。 本研究では,フィルタグラフ距離近似を導入する。
• 参考スコア（独自算出の注目度）: 62.779521543654134
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph distance. It is an optimal transport based distance which drives graph comparison through the probability distribution of filtered graph signals. This creates a highly flexible distance, capable of prioritising different spectral information in observed graphs, offering a wide range of choices for a comparison metric. We tackle the problem of graph alignment by computing graph permutations that minimise our new filter distances, which implicitly solves the graph comparison problem. We then propose a new approximate cost function that circumvents many computational difficulties inherent to graph comparison and permits the exploitation of fast algorithms such as mirror gradient descent, without grossly sacrificing the performance. We finally propose a novel algorithm derived from a stochastic version of mirror gradient descent, which accommodates the non-convexity of the alignment problem, offering a good trade-off between performance accuracy and speed. The experiments on graph alignment and classification show that the flexibility gained through filter graph distances can have a significant impact on performance, while the difference in speed offered by the approximation cost makes the framework applicable in practical settings.
• Abstract（参考訳）: グラフ比較は、グラフ間の類似点と相違点の識別を扱う。 主な障害は、未知のグラフのアライメントと、正確で安価な比較指標の欠如である。 本稿では,フィルタグラフ距離について述べる。 フィルタされたグラフ信号の確率分布を通してグラフ比較を駆動する最適輸送ベース距離である。 これは非常にフレキシブルな距離を生み出し、観測されたグラフで異なるスペクトル情報を優先し、比較計量に対して幅広い選択肢を提供する。 グラフ比較問題を暗黙的に解く新しいフィルタ距離を最小化するグラフ置換を計算することで,グラフアライメントの問題に取り組む。 次に,グラフ比較に固有の多くの計算困難を回避し,性能を犠牲にすることなく鏡面勾配降下などの高速アルゴリズムを活用できる新しい近似コスト関数を提案する。 最終的に、アライメント問題の非凸性に対応し、性能精度と速度の良好なトレードオフを提供するミラー勾配降下の確率バージョンから導出した新しいアルゴリズムを提案する。 グラフアライメントと分類実験により,フィルタグラフ距離で得られる柔軟性は性能に大きな影響を与えるが,近似コストによる速度の差は実用的な設定で適用できることを示した。

関連論文リスト

• Fairness-aware Optimal Graph Filter Design [25.145533328758614]
  グラフは、複雑な現実世界の相互接続システムを表現するために使用できる数学的ツールである。 グラフ上の機械学習(ML)は、最近大きな注目を集めている。 グラフ信号処理からの洞察を借りて,グラフ学習におけるバイアス緩和の問題を新たに検討する。
  論文  参考訳（メタデータ） (2023-10-22T22:40:40Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Graph Matching via Optimal Transport [11.93151370164898]
  グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。 現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。 我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
  論文  参考訳（メタデータ） (2021-11-09T19:18:18Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Graph Coarsening with Neural Networks [8.407217618651536]
  本稿では、粗いアルゴリズムの品質を測定するためのフレームワークを提案し、目標に応じて、粗いグラフ上のLaplace演算子を慎重に選択する必要があることを示す。 粗いグラフに対する現在のエッジウェイト選択が準最適である可能性が示唆され、グラフニューラルネットワークを用いて重み付けマップをパラメータ化し、教師なし方法で粗い品質を改善するよう訓練する。
  論文  参考訳（メタデータ） (2021-02-02T06:50:07Z)
• Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
  本稿では,従来のグラフ信号フィルタリングと深い特徴学習を併用して,競合するハイブリッド設計を提案する。 解釈可能な低パスグラフフィルタを用い、最先端のDL復調方式DnCNNよりも80%少ないネットワークパラメータを用いる。
  論文  参考訳（メタデータ） (2020-10-21T20:04:22Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)
• Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs [6.72542623686684]
  本研究では,数十億のノードとエッジを持つグラフ間のスペクトル距離を計算するための,効率的かつ効率的な近似手法であるSLaQを提案する。 SLaQは既存の手法よりも優れており、近似精度は数桁向上することが多い。
  論文  参考訳（メタデータ） (2020-03-03T01:25:07Z)

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

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