論文の概要: Uncertainty-aware Efficient Subgraph Isomorphism using Graph Topology
- arxiv url: http://arxiv.org/abs/2209.09090v3
- Date: Mon, 23 Jun 2025 02:13:34 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-24 19:06:36.082672
- Title: Uncertainty-aware Efficient Subgraph Isomorphism using Graph Topology
- Title（参考訳）: グラフトポロジーを用いた不確実性を考慮した効率的な部分グラフ同型
- Authors: Arpan Kusari, Wenbo Sun,
- Abstract要約: 部分グラフ同型 (subgraph isomorphism) あるいは部分グラフマッチング (subgraph matching) は一般にNP完全問題とみなされる。
本稿では,ノードラベルのない不正確な場合において,サブグラフとフルグラフのノード対応を同定する手法を提案する。
- 参考スコア（独自算出の注目度）: 10.922787879808576
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Subgraph isomorphism, also known as subgraph matching, is typically regarded as an NP-complete problem. This complexity is further compounded in practical applications where edge weights are real-valued and may be affected by measurement noise and potential missing data. Such graph matching routinely arises in applications such as image matching and map matching. Most subgraph matching methods fail to perform node-to-node matching under presence of such corruptions. 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. To demonstrate the effectiveness of the proposed method, a simulation is performed on the Erdos-Renyi random graphs and two case studies are performed on the image-based affine covariant features dataset and KITTI stereo dataset respectively. 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.
- Abstract（参考訳）: 部分グラフ同型 (subgraph isomorphism) あるいは部分グラフマッチング (subgraph matching) は一般にNP完全問題とみなされる。
この複雑さは、エッジウェイトが実際に評価され、測定ノイズや潜在的な欠落データの影響を受けうる実用的な応用においてさらに複雑である。
このようなグラフマッチングは、画像マッチングやマップマッチングといったアプリケーションで日常的に発生する。
ほとんどのサブグラフマッチング手法は、そのような汚職の存在下でノード間マッチングを行うことができない。
ノードラベルを2段階に含まない不正確な場合において,サブグラフとフルグラフのノード対応を同定する手法を提案する。
(a)部分グラフから最小一意位相保存部分集合を抽出し、全グラフでその実現可能なマッチングを見つけ、
(b) 境界可換性に基づく一意経路のペア化により一致したノード集合を拡張するためのコンセンサスに基づくアルゴリズムを実装する。
提案手法の有効性を実証するため,エルドス・レーニランダムグラフ上でシミュレーションを行い,画像ベースアフィン共変特徴データセットとKITTIステレオデータセットで2つのケーススタディを行った。
提案手法は,既存のサブグラフマッチング手法を超越して,現実的なサブ線形計算効率,ランダムな計測ノイズに対する頑健性,優れた統計特性を有することを示す。
また, 本手法は, 一般性を失うことなく, 正確な整合性にも容易に適用可能である。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。