論文の概要: Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks

• arxiv url: http://arxiv.org/abs/2210.11020v1
• Date: Thu, 20 Oct 2022 05:07:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-21 16:01:14.310059
• Title: Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks
• Title（参考訳）: 最大コモンサブグラフ誘導グラフ検索:後期および初期相互作用ネットワーク
• Authors: Indradyumna Roy, Soumen Chakrabarti and Abir De
• Abstract要約: 正確な MCES と MCCS の発見は難しいが、関連性によるコーパスグラフのランク付けが目的であれば不要である。 MCESとMCCSをよく近似する高速で訓練可能なニューラル関数を設計する。 我々の提案は、精度と速度の両面で、後期相互作用モデルよりも優れている。
• 参考スコア（独自算出の注目度）: 44.38220572296474
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The graph retrieval problem is to search in a large corpus of graphs for ones that are most similar to a query graph. A common consideration for scoring similarity is the maximum common subgraph (MCS) between the query and corpus graphs, usually counting the number of common edges (i.e., MCES). In some applications, it is also desirable that the common subgraph be connected, i.e., the maximum common connected subgraph (MCCS). Finding exact MCES and MCCS is intractable, but may be unnecessary if ranking corpus graphs by relevance is the goal. We design fast and trainable neural functions that approximate MCES and MCCS well. Late interaction methods compute dense representations for the query and corpus graph separately, and compare these representations using simple similarity functions at the last stage, leading to highly scalable systems. Early interaction methods combine information from both graphs right from the input stages, are usually considerably more accurate, but slower. We propose both late and early interaction neural MCES and MCCS formulations. They are both based on a continuous relaxation of a node alignment matrix between query and corpus nodes. For MCCS, we propose a novel differentiable network for estimating the size of the largest connected common subgraph. Extensive experiments with seven data sets show that our proposals are superior among late interaction models in terms of both accuracy and speed. Our early interaction models provide accuracy competitive with the state of the art, at substantially greater speeds.
• Abstract（参考訳）: グラフ検索問題は、クエリグラフに最もよく似たグラフの巨大なコーパスで検索することである。 類似性を評価するための一般的な考慮事項は、クエリとコーパスグラフの間の最大共通部分グラフ(MCS)であり、通常は共通エッジの数(MCES)をカウントする。 いくつかの応用では、共通部分グラフ、すなわち最大共通部分グラフ(mccs)が連結であることが望ましい。 正確な MCES と MCCS の発見は難しいが、関連性によるコーパスグラフのランク付けが目的であれば不要である。 MCESとMCCSをよく近似する高速で訓練可能なニューラル関数を設計する。 遅延相互作用法はクエリグラフとコーパスグラフの密表現を別々に計算し、これらの表現を最終段階で単純な類似度関数を用いて比較し、高度にスケーラブルなシステムへと導く。 初期相互作用法は、入力段階から両方のグラフからの情報を組み合わせるが、通常はかなり正確だが遅い。 遅くとも早期の相互作用型ニューラルネットワーク MCES と MCCS の定式化を提案する。 どちらもクエリとコーパスノード間のノードアライメントマトリックスの連続的な緩和に基づいている。 MCCSでは,最大連結部分グラフのサイズを推定する新しい微分可能なネットワークを提案する。 7つのデータセットによる大規模な実験により,提案手法は,精度と速度の両面で,遅延相互作用モデルよりも優れていることが示された。 我々の初期の相互作用モデルは、より高速で、最先端のテクノロジーと競合する精度を提供する。

関連論文リスト

• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• More Interpretable Graph Similarity Computation via Maximum Common Subgraph Inference [6.016052201518866]
  2つのグラフ間の距離/類似度を計算するグラフ類似度測定は、様々なグラフ関連タスクで発生する。 最近の学習に基づく手法では、2つのグラフ間の相互作用情報を1つの隠れベクターに直接変換し、それを類似度にマッピングするため、解釈可能性に欠ける。 本研究では、最大共通部分グラフ推論(INFMCS)による類似性という、グラフ類似性学習のためのより解釈可能なエンドツーエンドパラダイムを提案する。
  論文  参考訳（メタデータ） (2022-08-09T07:37:47Z)
• Beyond spectral gap: The role of the topology in decentralized learning [58.48291921602417]
  機械学習モデルのデータ並列最適化では、労働者はモデルの推定値を改善するために協力する。 本稿では、労働者が同じデータ分散を共有するとき、疎結合な分散最適化の正確な図面を描くことを目的とする。 我々の理論は深層学習における経験的観察と一致し、異なるグラフトポロジーの相対的メリットを正確に記述する。
  論文  参考訳（メタデータ） (2022-06-07T08:19:06Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Neural Subgraph Matching [57.05893848555512]
  NeuroMatchは、サブグラフマッチングに対する正確で効率的で堅牢な神経アプローチである。 NeuroMatchは、既存の幾何学的アプローチよりも100倍高速で、既存のサブグラフマッチング手法よりも18%精度が高い。
  論文  参考訳（メタデータ） (2020-07-06T22:06:38Z)
• CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
  グラフニューラルネットワーク(GNN)はこのタスクにデータ駆動型ソリューションを提供する。 既存のGNNベースの手法は、それぞれ2つのグラフを埋め込んだり、グラフ全体のクロスグラフインタラクションをデプロイしたりするが、まだ競合する結果が得られない。 このフレームワークは,まず適応的なプーリング操作で大きなグラフを埋め込んで粗くし,最後に類似点を求めるために粗いグラフにきめ細かな相互作用を展開させる。
  論文  参考訳（メタデータ） (2020-05-14T16:33:13Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)
• GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
  検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。 このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。 我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
  論文  参考訳（メタデータ） (2020-02-08T10:03:40Z)

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

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