論文の概要: Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching

• arxiv url: http://arxiv.org/abs/2012.15279v1
• Date: Wed, 30 Dec 2020 18:51:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-18 05:56:22.322436
• Title: Some Algorithms on Exact, Approximate and Error-Tolerant Graph Matching
• Title（参考訳）: Exact, Approximate, Error-Tolerant Graph Matchingのアルゴリズム
• Authors: Shri Prakash Dwivedi
• Abstract要約: 我々は、様々な正確かつ不正確なグラフマッチング技術の広範な調査を紹介します。 グラフマッチングアルゴリズムのカテゴリが提示され、重要でないノードを除去することでグラフのサイズを小さくする。 幾何グラフを用いたグラフ類似度測定の新しい手法を提案する。
• 参考スコア（独自算出の注目度）: 3.655021726150369
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The graph is one of the most widely used mathematical structures in engineering and science because of its representational power and inherent ability to demonstrate the relationship between objects. The objective of this work is to introduce the novel graph matching techniques using the representational power of the graph and apply it to structural pattern recognition applications. We present an extensive survey of various exact and inexact graph matching techniques. Graph matching using the concept of homeomorphism is presented. A category of graph matching algorithms is presented, which reduces the graph size by removing the less important nodes using some measure of relevance. We present an approach to error-tolerant graph matching using node contraction where the given graph is transformed into another graph by contracting smaller degree nodes. We use this scheme to extend the notion of graph edit distance, which can be used as a trade-off between execution time and accuracy. We describe an approach to graph matching by utilizing the various node centrality information, which reduces the graph size by removing a fraction of nodes from both graphs based on a given centrality measure. The graph matching problem is inherently linked to the geometry and topology of graphs. We introduce a novel approach to measure graph similarity using geometric graphs. We define the vertex distance between two geometric graphs using the position of their vertices and show it to be a metric over the set of all graphs with vertices only. We define edge distance between two graphs based on the angular orientation, length and position of the edges. Then we combine the notion of vertex distance and edge distance to define the graph distance between two geometric graphs and show it to be a metric. Finally, we use the proposed graph similarity framework to perform exact and error-tolerant graph matching.
• Abstract（参考訳）: このグラフは、その表現力とオブジェクト間の関係を示す固有の能力から、工学や科学において最も広く使われている数学的構造の一つである。 本研究の目的は,グラフの表現力を利用した新しいグラフマッチング手法を導入し,構造的パターン認識に適用することである。 本稿では,様々な正確かつ不正確なグラフマッチング手法について広範な調査を行う。 準同型の概念を用いたグラフマッチングについて述べる。 グラフマッチングアルゴリズムのカテゴリが提示され、関係性のある指標を用いて重要でないノードを除去することでグラフサイズを小さくする。 本稿では,より少ない次数ノードを縮合することで,与えられたグラフを別のグラフに変換するノード収縮を用いた誤り耐性グラフマッチング手法を提案する。 この手法を用いてグラフ編集距離を延長し,実行時間と精度のトレードオフとして利用することができる。 本稿では,各ノードの集中度情報を利用することで,グラフマッチングのアプローチについて述べる。 グラフマッチング問題は本質的にグラフの幾何学と位相に関係している。 幾何グラフを用いたグラフ類似度測定の新しい手法を提案する。 2つの幾何グラフ間の頂点距離を頂点の位置を用いて定義し、頂点のみを持つすべてのグラフの集合上の計量であることを示す。 辺の角方向,長さ,位置に基づいて2つのグラフ間の辺距離を定義する。 次に頂点距離と辺距離の概念を組み合わせて、2つの幾何グラフの間のグラフ距離を定義し、それを計量であることを示す。 最後に,提案するグラフ類似性フレームワークを用いて,正確かつエラーに耐性のあるグラフマッチングを行う。

関連論文リスト

• Graphons of Line Graphs [6.822247359790484]
  スパースグラフのサブセットに光を放つ簡単な方法を示す。 グラフが特定の性質を満たすことを示し、この2次性質はスパースであるが、密度の高い線グラフをもたらす。 特に、星グラフは、密度の高い直線グラフと直線グラフのゼロでないグラフを生じる2次特性を満たす。
  論文  参考訳（メタデータ） (2024-09-03T06:50:03Z)
• A Gromov--Wasserstein Geometric View of Spectrum-Preserving Graph Coarsening [19.09507367362567]
  この研究はグラフの粗大化を別の観点から研究し、グラフ距離を保存する理論を発展させた。 幾何学的アプローチは、グラフ分類や回帰のようなグラフの集合を扱う際に有用である。 この差を最小化するには、一般的な重み付きカーネル$K$-means法を用いる。
  論文  参考訳（メタデータ） (2023-06-15T04:47:26Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。 ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
  論文  参考訳（メタデータ） (2023-06-11T22:04:28Z)
• Distance Measures for Geometric Graphs [0.0]
  幾何編集距離 (GED) と幾何グラフ距離 (GGD) の2つの距離測度について検討する。 GEDは1つのグラフを編集してもう1つのグラフに変換するという考え方に基づいているが、GGDはグラフの不正確なマッチングにインスパイアされている。 GGDが計算に$mathcalNP$-hard、たとえ計算に$mathcalNP$-hardであっても、計算に$mathcalNP$-hardであることを示す。
  論文  参考訳（メタデータ） (2022-09-26T17:35:29Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  自己教師付きグラフ類似性学習のためのコントラストグラフマッチングネットワーク(CGMN)を提案する。 我々は,効率的なノード表現学習のために,クロスビューインタラクションとクロスグラフインタラクションという2つの戦略を用いる。 我々はノード表現をグラフ類似性計算のためのプール演算によりグラフレベル表現に変換する。
  論文  参考訳（メタデータ） (2022-05-30T13:20:26Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。 このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。 本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。 特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
  論文  参考訳（メタデータ） (2020-10-20T05:54:31Z)
• Multilevel Graph Matching Networks for Deep Graph Similarity Learning [79.3213351477689]
  グラフ構造オブジェクト間のグラフ類似性を計算するためのマルチレベルグラフマッチングネットワーク(MGMN)フレームワークを提案する。 標準ベンチマークデータセットの欠如を補うため、グラフグラフ分類とグラフグラフ回帰タスクの両方のためのデータセットセットを作成し、収集した。 総合的な実験により、MGMNはグラフグラフ分類とグラフグラフ回帰タスクの両方において、最先端のベースラインモデルより一貫して優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-08T19:48:19Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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