論文の概要: Multiscale Graph Comparison via the Embedded Laplacian Distance

• arxiv url: http://arxiv.org/abs/2201.12064v1
• Date: Fri, 28 Jan 2022 12:13:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-31 14:33:31.231788
• Title: Multiscale Graph Comparison via the Embedded Laplacian Distance
• Title（参考訳）: 埋め込みラプラシア距離によるマルチスケールグラフの比較
• Authors: Edric Tam, David Dunson
• Abstract要約: 非常に異なるサイズのグラフを比較するために,埋め込みラプラシアン距離 (ELD) を提案する。 我々のアプローチはまず、図形構造を尊重する共通の低次元ラプラシア埋め込み空間にグラフを投影する。 距離は自然スライスされたワッサーシュタインアプローチによって効率的に計算できる。
• 参考スコア（独自算出の注目度）: 6.09170287691728
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We introduce a simple and fast method for comparing graphs of different sizes. Existing approaches are often either limited to comparing graphs with the same number of vertices or are computationally unscalable. We propose the Embedded Laplacian Distance (ELD) for comparing graphs of potentially vastly different sizes. Our approach first projects the graphs onto a common, low-dimensional Laplacian embedding space that respects graphical structure. This reduces the problem to that of comparing point clouds in a Euclidean space. A distance can then be computed efficiently via a natural sliced Wasserstein approach. We show that the ELD is a pseudo-metric and is invariant under graph isomorphism. We provide intuitive interpretations of the ELD using tools from spectral graph theory. We test the efficacy of the ELD approach extensively on both simulated and real data. Results obtained are excellent.
• Abstract（参考訳）: 異なるサイズのグラフを比較するための単純かつ高速な手法を提案する。 既存のアプローチは、しばしば同じ頂点数のグラフの比較に制限されるか、計算不可能である。 我々は,潜在的に異なるサイズのグラフを比較するために,埋め込みラプラシアン距離(ELD)を提案する。 我々のアプローチはまず、図形構造を尊重する共通の低次元ラプラシア埋め込み空間にグラフを投影する。 これにより、ユークリッド空間内の点雲を比較する問題になってしまう。 距離は自然スライスされたwassersteinアプローチによって効率的に計算できる。 ELDは擬測度であり、グラフ同型の下で不変であることを示す。 スペクトルグラフ理論のツールを用いて,EDDの直観的な解釈を行う。 シミュレーションデータと実データの両方を用いて, ELD アプローチの有効性を検証した。 結果は良好である。

関連論文リスト

• Separation-based distance measures for causal graphs [15.37737222790121]
  最先端因果探索法は単一の因果グラフを出力するのではなく、それらの等価クラス(MEC)を出力する。 本稿では,分離距離の差が評価に適さないような距離の付加的な測定法を提案する。 我々は,既存の比較指標の違いを明らかにする実験と,おもちゃの例を用いて理論的解析を補完する。
  論文  参考訳（メタデータ） (2024-02-07T15:36:53Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。 我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
  論文  参考訳（メタデータ） (2023-05-13T17:29:18Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
  ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。 我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。 特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
  論文  参考訳（メタデータ） (2022-06-15T18:20:01Z)
• Structure from Voltage [6.212269948361801]
  有効抵抗(ER)はグラフの構造を問う魅力的な方法である。 我々は、$n$の頂点が$n2$のグラフにおけるスケーリング抵抗を使用することで、電圧と有効抵抗の有意義な制限が得られることを示す。 また、計量グラフに「基底」ノードを加えることで、選択された点から他のすべての点までのすべての距離を計算する単純で自然な方法が得られることを示す。
  論文  参考訳（メタデータ） (2022-02-28T20:06:10Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
  グラフ比較は、グラフ間の類似点と相違点の識別を扱う。 大きな障害は、グラフの未知のアライメントと、正確で安価な比較指標の欠如である。 本研究では,フィルタグラフ距離近似を導入する。
  論文  参考訳（メタデータ） (2021-09-09T17:43:07Z)
• Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
  我々は、様々な正確かつ不正確なグラフマッチング技術の広範な調査を紹介します。 グラフマッチングアルゴリズムのカテゴリが提示され、重要でないノードを除去することでグラフのサイズを小さくする。 幾何グラフを用いたグラフ類似度測定の新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-12-30T18:51:06Z)
• 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)

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

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