論文の概要: Scalable Pattern Matching in Computation Graphs
- arxiv url: http://arxiv.org/abs/2402.13065v2
- Date: Wed, 26 Mar 2025 11:51:45 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-27 20:07:57.775847
- Title: Scalable Pattern Matching in Computation Graphs
- Title（参考訳）: 計算グラフにおけるスケーラブルなパターンマッチング
- Authors: Luca Mondada, Pablo Andrés-Martínez,
- Abstract要約: グラフ書き換えは、コンパイラ、機械学習、量子コンピューティングといった分野におけるグラフ表現の最適化と修正に人気のあるツールである。
ポートグラフにおけるパターンマッチングの新しい解法を提案する。
提案アルゴリズムは,量子回路を記述した10000の実世界のパターンのデータセット上で,現在の実装よりも20倍の高速化を実現する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: Graph rewriting is a popular tool for the optimisation and modification of graph expressions in domains such as compilers, machine learning and quantum computing. The underlying data structures are often port graphs - graphs with labels at edge endpoints. A pre-requisite for graph rewriting is the ability to find graph patterns. We propose a new solution to pattern matching in port graphs. Its novelty lies in the use of a pre-computed data structure that makes the pattern matching runtime complexity independent of the number of patterns. This offers a significant advantage over existing solutions for use cases with large sets of small patterns. Our approach is particularly well-suited for quantum superoptimisation. We provide an implementation and benchmarks showing that our algorithm offers a 20x speedup over current implementations on a dataset of 10000 real world patterns describing quantum circuits.
- Abstract（参考訳）: グラフ書き換えは、コンパイラ、機械学習、量子コンピューティングといった分野におけるグラフ表現の最適化と修正に人気のあるツールである。
基盤となるデータ構造は、しばしばポートグラフ(エッジエンドポイントのラベル付きグラフ)である。
グラフの書き直しの前提条件は、グラフパターンを見つける能力である。
ポートグラフにおけるパターンマッチングの新しい解法を提案する。
その斬新さは、あらかじめ計算されたデータ構造を使用することで、パターンの数によらず、パターンマッチングランタイムの複雑さを独立させる。
これは、小さなパターンのセットの大きなユースケースに対して、既存のソリューションよりも大きなアドバンテージを提供します。
我々のアプローチは特に量子超最適化に適している。
我々は,量子回路を記述した10000の実世界のパターンのデータセット上で,我々のアルゴリズムが現在の実装よりも20倍高速であることを示す実装とベンチマークを提供する。
関連論文リスト
- Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
モチーフと呼ばれる小さな部分グラフの数を数えることは、ソーシャルネットワークの分析とグラフマイニングの根本的な問題である。
本稿では,時間的経路サンプリングの新しい手法を用いて,この問題に対処するアルゴリズムTEACUPSを提案する。
数十億のエッジを持つBitcoinグラフの場合、TEACUPSは1分以内で実行され、正確なカウントアルゴリズムは1日以上かかる。
論文 参考訳（メタデータ） (2024-09-13T16:48:39Z) - Representation Learning for Frequent Subgraph Mining [64.32430554934021]
Subgraph Pattern Miner (SPMiner) は、大きなターゲットグラフに頻繁なサブグラフを見つけるための新しいニューラルネットワークである。
5ノードと6ノードのモチーフでは、SPMinerは正確な列挙法よりも100倍速く、最も頻繁なモチーフをほぼ完全に識別できる。
SPMinerは、10ノードの頻繁なモチーフを確実に特定できる。
論文 参考訳（メタデータ） (2024-02-22T08:11:22Z) - SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
複素構造特性をチェックできるグラフ同型を一般化する。
この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。
本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-15T18:12:44Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
量子回路におけるパターンマッチングを同時に行うアルゴリズムを提案する。
量子回路の場合、量子ビットの最大数から得られる境界を表現することができる。
論文 参考訳（メタデータ） (2023-02-13T22:09:02Z) - Learning to Count Isomorphisms with Graph Neural Networks [16.455234748896157]
グラフ上の部分グラフ同型カウントは重要な問題である。
本稿では,グラフアイソモーフィズムカウントのための新しいグラフニューラルネットワークであるCount-GNNを提案する。
論文 参考訳（メタデータ） (2023-02-07T05:32:11Z) - Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph
Matching [68.35685422301613]
そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。
ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。
合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
論文 参考訳（メタデータ） (2023-01-07T05:14:45Z) - Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors
to Sequences [55.329402218608365]
本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。
1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。
その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
論文 参考訳（メタデータ） (2022-02-07T16:38:36Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳（メタデータ） (2020-07-03T09:30:07Z) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。
我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。
トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文 参考訳（メタデータ） (2020-06-28T04:37:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。