論文の概要: Distance Measures for Geometric Graphs
- arxiv url: http://arxiv.org/abs/2209.12869v1
- Date: Mon, 26 Sep 2022 17:35:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-27 17:43:27.177714
- Title: Distance Measures for Geometric Graphs
- Title（参考訳）: 幾何学グラフの距離測定
- Authors: Sushovan Majhi and Carola Wenk
- Abstract要約: 幾何編集距離 (GED) と幾何グラフ距離 (GGD) の2つの距離測度について検討する。
GEDは1つのグラフを編集してもう1つのグラフに変換するという考え方に基づいているが、GGDはグラフの不正確なマッチングにインスパイアされている。
GGDが計算に$mathcalNP$-hard、たとえ計算に$mathcalNP$-hardであっても、計算に$mathcalNP$-hardであることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A geometric graph is a combinatorial graph, endowed with a geometry that is
inherited from its embedding in a Euclidean space. Formulation of a meaningful
measure of (dis-)similarity in both the combinatorial and geometric structures
of two such geometric graphs is a challenging problem in pattern recognition.
We study two notions of distance measures for geometric graphs, called the
geometric edit distance (GED) and geometric graph distance (GGD). While the
former is based on the idea of editing one graph to transform it into the other
graph, the latter is inspired by inexact matching of the graphs. For decades,
both notions have been lending themselves well as measures of similarity
between attributed graphs. If used without any modification, however, they fail
to provide a meaningful distance measure for geometric graphs -- even cease to
be a metric. We have curated their associated cost functions for the context of
geometric graphs. Alongside studying the metric properties of GED and GGD, we
investigate how the two notions compare. We further our understanding of the
computational aspects of GGD by showing that the distance is
$\mathcal{NP}$-hard to compute, even if the graphs are planar and arbitrary
cost coefficients are allowed.
- Abstract（参考訳）: 幾何学グラフ(英: geometry graph)は、ユークリッド空間への埋め込みから継承される幾何学を持つ組合せグラフである。
2つの幾何学的グラフの組合せ構造と幾何学的構造の両方における(非)相似性の有意義な尺度の定式化は、パターン認識において難しい問題である。
幾何学的編集距離 (ged) と幾何学的グラフ距離 (ggd) と呼ばれる幾何学的グラフに対する距離測度の概念について検討した。
前者は、あるグラフを編集して別のグラフに変換するというアイデアに基づいているが、後者は、グラフの不正確なマッチングから着想を得ている。
何十年もの間、両方の概念は、帰属グラフ間の類似性の尺度として、自分自身を貸し出している。
しかし、修正なしで使用しても、幾何グラフに対して有意義な距離測度を提供することができない。
幾何グラフの文脈に対するそれらの関連コスト関数をキュレートした。
ged と ggd の計量特性を研究するとともに,この2つの概念を比較した。
さらに,グラフが平面であり,任意のコスト係数が許される場合でも,距離が$\mathcal{NP}$-hardであることを示すことにより,GGDの計算面の理解を深める。
関連論文リスト
- A Survey of Geometric Graph Neural Networks: Data Structures, Models and
Applications [67.33002207179923]
本稿では、幾何学的GNNに関するデータ構造、モデル、および応用について調査する。
幾何学的メッセージパッシングの観点から既存のモデルの統一的なビューを提供する。
また、方法論開発と実験評価の後の研究を促進するために、アプリケーションと関連するデータセットを要約する。
論文 参考訳（メタデータ） (2024-03-01T12:13:04Z) - A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
我々は、非ユークリッドグラフを学習可能なグラフワードに変換するGraph2Seqエンコーダを特徴とするGraphsGPTを紹介する。
GraphGPTデコーダは、元のグラフをGraph Wordsから再構成し、情報等価性を保証する。
論文 参考訳（メタデータ） (2024-02-04T12:29:40Z) - A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph
Coarsening [19.09507367362567]
この研究はグラフの粗大化を別の観点から研究し、グラフ距離を保存する理論を発展させた。
幾何学的アプローチは、グラフ分類や回帰のようなグラフの集合を扱う際に有用である。
この差を最小化するには、一般的な重み付きカーネル$K$-means法を用いる。
論文 参考訳（メタデータ） (2023-06-15T04:47:26Z) - Graph Mover's Distance: An Efficiently Computable Distance Measure for
Geometric Graphs [0.0]
幾何グラフ距離(GGD)は、2つの幾何学グラフ間の類似性の有意義な尺度として最近研究されている。
本稿では,地球移動機の距離の例として定式化されたグラフ・モーバー距離(GMD)を提案する。
論文 参考訳（メタデータ） (2023-06-03T15:06:12Z) - Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。
幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。
次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
論文 参考訳（メタデータ） (2023-05-05T14:04:52Z) - CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph
Similarity Learning [65.1042892570989]
自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。
我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。
我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
論文 参考訳（メタデータ） (2022-05-30T13:20:26Z) - Joint Deep Multi-Graph Matching and 3D Geometry Learning from
Inhomogeneous 2D Image Collections [57.60094385551773]
非均質な画像コレクションから変形可能な3Dジオメトリモデルを学ぶためのトレーニング可能なフレームワークを提案する。
さらに,2次元画像で表現された物体の3次元形状も取得する。
論文 参考訳（メタデータ） (2021-03-31T17:25:36Z) - Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching [3.655021726150369]
我々は、様々な正確かつ不正確なグラフマッチング技術の広範な調査を紹介します。
グラフマッチングアルゴリズムのカテゴリが提示され、重要でないノードを除去することでグラフのサイズを小さくする。
幾何グラフを用いたグラフ類似度測定の新しい手法を提案する。
論文 参考訳（メタデータ） (2020-12-30T18:51:06Z) - Distance-Geometric Graph Convolutional Network (DG-GCN) for
Three-Dimensional (3D) Graphs [0.8722210937404288]
距離幾何学グラフ表現に基づくメッセージパッシンググラフ畳み込みネットワークを提案する。
距離からフィルタ重みの学習を可能にし、3次元グラフの幾何学をグラフ畳み込みに組み込む。
本研究は3次元グラフ,特に分子グラフ上でのエンドツーエンドディープラーニングにおけるDG-GCNの有用性と価値を示す。
論文 参考訳（メタデータ） (2020-07-06T15:20:52Z) - Geometric Graph Representations and Geometric Graph Convolutions for
Deep Learning on Three-Dimensional (3D) Graphs [0.8722210937404288]
ノードとエッジからなる三次元(3次元)グラフの幾何学は、多くの重要な応用において重要な役割を果たす。
我々は3種類の幾何グラフ表現を定義する: 位置、角度幾何学、距離幾何学である。
概念実証には幾何学的グラフ畳み込みに距離幾何学的グラフ表現を用いる。
ESOLおよびFreesolデータセットの幾何グラフ畳み込みの結果は、標準グラフ畳み込みよりも大幅に改善されている。
論文 参考訳（メタデータ） (2020-06-02T17:08:59Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。