論文の概要: Efficient Subgraph Isomorphism using Graph Topology

• arxiv url: http://arxiv.org/abs/2209.09090v1
• Date: Thu, 15 Sep 2022 02:45:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-20 15:40:16.253343
• Title: Efficient Subgraph Isomorphism using Graph Topology
• Title（参考訳）: グラフトポロジーを用いた効率的な部分グラフ同型
• Authors: Arpan Kusari and Wenbo Sun
• Abstract要約: 部分グラフ同型 (subgraph isomorphism) あるいは部分グラフマッチング (subgraph matching) は一般にNP完全問題と考えられる。 ほとんど全てのサブグラフマッチング手法はノードラベルを使用してノード-ノードマッチングを行う。 本稿では,ノードラベルのない不正確な場合において,サブグラフとフルグラフのノード対応を同定する手法を提案する。
• 参考スコア（独自算出の注目度）: 10.332465264309693
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Subgraph isomorphism or subgraph matching is generally considered as an NP-complete problem, made more complex in practical applications where the edge weights take real values and are subject to measurement noise and possible anomalies. To the best of our knowledge, almost all subgraph matching methods utilize node labels to perform node-node matching. In the absence of such labels (in applications such as image matching and map matching among others), these subgraph matching methods do not work. We propose a method for identifying the node correspondence between a subgraph and a full graph in the inexact case without node labels in two steps - (a) extract the minimal unique topology preserving subset from the subgraph and find its feasible matching in the full graph, and (b) implement a consensus-based algorithm to expand the matched node set by pairing unique paths based on boundary commutativity. Going beyond the existing subgraph matching approaches, the proposed method is shown to have realistically sub-linear computational efficiency, robustness to random measurement noise, and good statistical properties. Our method is also readily applicable to the exact matching case without loss of generality. To demonstrate the effectiveness of the proposed method, a simulation and a case study is performed on the Erdos-Renyi random graphs and the image-based affine covariant features dataset respectively.
• Abstract（参考訳）: 部分グラフ同型 (subgraph isomorphism) あるいは部分グラフマッチング (subgraph matching) は一般にNP完全問題(NP完全問題)とみなされ、エッジウェイトが実値をとり、測定ノイズと可能な異常にさらされる実用的な応用においてより複雑である。 我々の知る限り、ほとんどのサブグラフマッチング手法はノードラベルを用いてノード-ノードマッチングを行う。 このようなラベルが存在しない場合(画像マッチングやマップマッチングなどのアプリケーションでは)、これらのサブグラフマッチングメソッドは動作しない。 ノードラベルを2段階に含まない不正確な場合において,サブグラフとフルグラフのノード対応を同定する手法を提案する。 (a)部分グラフから最小一意位相保存部分集合を抽出し、全グラフでその実現可能なマッチングを見つけ、 (b)境界可換性に基づく一意経路をペアリングすることによりマッチングノード集合を拡張するためのコンセンサスベースアルゴリズムの実装。 提案手法は,既存のサブグラフマッチング手法を超えて,現実的なサブ線形計算効率,ランダムな計測ノイズに対する頑健性,および優れた統計特性を有することを示す。 本手法は一般性を損なうことなく正確なマッチングケースにも容易に適用できる。 提案手法の有効性を実証するために,エルドス・レーニランダムグラフと画像に基づくアフィン共変特徴データセットを用いて,シミュレーションとケーススタディを行った。

関連論文リスト

• Topograph: An efficient Graph-Based Framework for Strictly Topology Preserving Image Segmentation [78.54656076915565]
  位相的正しさは多くの画像分割タスクにおいて重要な役割を果たす。 ほとんどのネットワークは、Diceのようなピクセル単位の損失関数を使って、トポロジカルな精度を無視して訓練されている。 トポロジ的に正確な画像セグメンテーションのための新しいグラフベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-11-05T16:20:14Z)
• Differentiable Proximal Graph Matching [40.41380102260085]
  微分可能近位グラフマッチング(DPGM)と呼ばれる近位演算子に基づくグラフマッチングアルゴリズムを提案する。 アルゴリズム全体をグラフ親和性行列からノード対応の予測への微分可能な写像とみなすことができる。 数値実験により、PGMは様々なデータセット上で既存のグラフマッチングアルゴリズムより優れていることが示された。
  論文  参考訳（メタデータ） (2024-05-26T08:17:13Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• ProvG-Searcher: A Graph Representation Learning Approach for Efficient Provenance Graph Search [13.627536649679577]
  ProvG-Searcherは,システムセキュリティログ内の既知のAPT動作を検出する新しい手法である。 グラフマッチング問題として前駆体グラフを探索するタスクを定式化し,グラフ表現学習法を用いる。 標準データセットに対する実験結果から,ProvG-Searcherはクエリの振る舞いを検出する精度が99%を超え,優れたパフォーマンスを実現していることが示された。
  論文  参考訳（メタデータ） (2023-09-07T11:29:01Z)
• The PWLR Graph Representation: A Persistent Weisfeiler-Lehman scheme with Random Walks for Graph Classification [0.6999740786886536]
  グラフ表現のための永続Weisfeiler-Lehmanランダムウォークスキーム(PWLR)。 我々はWeisfeiler-Lehmanプロシージャの多くの変種を一般化する。
  論文  参考訳（メタデータ） (2022-08-29T08:50:37Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm [21.1095092767297]
  グラフマッチングの精度、構造的不整合(SI)を測定するための新しい基準を提案する。 具体的には、SIは、グラフのマルチホップ構造に対応するために熱拡散ウェーブレットを組み込む。 ミラー降下法を用いて,新しいK-ホップ構造に基づくマッチングコストでGromov-Wasserstein距離を解くことにより,SIGMAを導出可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-06T15:18:37Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)

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

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