論文の概要: Scalable Pattern Matching in Computation Graphs
- arxiv url: http://arxiv.org/abs/2402.13065v1
- Date: Tue, 20 Feb 2024 15:02:24 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-21 14:40:29.547474
- Title: Scalable Pattern Matching in Computation Graphs
- Title（参考訳）: 計算グラフにおけるスケーラブルパターンマッチング
- Authors: Luca Mondada and Pablo Andr\'es-Mart\'inez
- Abstract要約: グラフの書き直しは、グラフ表現の最適化と修正に人気のあるツールである。
ポートグラフにおけるパターンマッチングの新しい解法を提案する。
我々のアルゴリズムは、10万の現実世界のパターンのデータセット上での現在の実装の20倍のスピードアップを提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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. These port labels greatly simplify pattern matching.
A pre-requisite for graph rewriting is the ability to find subgraphs of the
input that match known graph identities: the pattern matching problem. 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. The runtime is bound
by the maximum width $w$ and depth $d$ of the patterns, as well as the input
graph size $|G|$ as $O(|G| \cdot c^w / w^{1/2} \cdot d)$ with $c = 6.75$. This
offers a significant advantage over existing solutions for use cases where
patterns have low width and the set of patterns is large and fixed ahead of
time.
In the context of quantum circuits, pattern width can be limited to qubit
number. Quantum superoptimisers may use thousands of rewrite rules on circuits
with less than 5 qubits, making them an ideal use case. We provide benchmarks
showing that our algorithm offers a 20x speedup over current implementations on
a dataset of 10'000 real world patterns describing quantum circuits.
- Abstract（参考訳）: グラフ書き換えは、コンパイラ、機械学習、量子コンピューティングといった分野におけるグラフ表現の最適化と修正に人気のあるツールである。
基盤となるデータ構造は、しばしばポートグラフ(エッジエンドポイントのラベル付きグラフ)である。
これらのポートラベルはパターンマッチングを大幅に単純化する。
グラフ書き換えの前提条件は、既知のグラフのアイデンティティと一致する入力のサブグラフを見つける能力である。
ポートグラフにおけるパターンマッチングの新しいソリューションを提案する。
その斬新さは、あらかじめ計算されたデータ構造を使用することで、パターンの数に依存しないパターンマッチングランタイムの複雑さを実現する。
ランタイムは最大幅$w$と深さ$d$と、入力グラフサイズ$|G|$を$O(|G| \cdot c^w / w^{1/2} \cdot d)$として$c = 6.75$と結合する。
これは、パターンの幅が低く、パターンのセットが大きく、事前に固定されているユースケースにおいて、既存のソリューションよりも大きな利点を提供する。
量子回路の文脈では、パターン幅は量子ビット数に制限することができる。
量子スーパーオプティマイザは5量子ビット未満の回路で何千もの書き換え規則を使うことができるため、理想的なユースケースである。
量子回路を記述する10万の実世界パターンのデータセット上の現在の実装よりも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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。