Scalable Pattern Matching in Computation Graphs

• URL: http://arxiv.org/abs/2402.13065v1
• Date: Tue, 20 Feb 2024 15:02:24 GMT
• Title: Scalable Pattern Matching in Computation Graphs
• Authors: Luca Mondada and Pablo Andr\'es-Mart\'inez
• Abstract summary: Graph rewriting is a popular tool for optimisation and modification of graph expressions. We propose a new solution to pattern matching in port graphs. Our algorithm offers a 20x speedup over current implementations on a dataset of 10'000 real world patterns.
• Score: 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.

Related papers

• Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
  Counting the number of small subgraphs, called motifs, is a fundamental problem in social network analysis and graph mining. We propose an algorithm, TEACUPS, that addresses this problem using a novel technique of temporal path sampling. For a Bitcoin graph with hundreds of millions of edges, TEACUPS runs in less than 1 minute, while the exact counting algorithm takes more than a day.
  arXiv  Detail & Related papers  (2024-09-13T16:48:39Z)
• Representation Learning for Frequent Subgraph Mining [64.32430554934021]
  Subgraph Pattern Miner (SPMiner) is a novel neural approach for finding frequent subgraphs in a large target graph. For 5- and 6-node motifs, SPMiner can almost perfectly identify the most frequent motifs while being 100x faster than exact enumeration methods. SPMiner can also reliably identify frequent 10-node motifs, which is well beyond the size limit of exact enumeration approaches.
  arXiv  Detail & Related papers  (2024-02-22T08:11:22Z)
• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  We propose a generalization of graph isomorphism that allows one to check complex structural properties. This specification is given in the form of a Regular Graph Pattern (ReGaP), a special type of graph inspired by regular expressions. We propose a SAT-based algorithm for checking if a target graph matches a given ReGaP.
  arXiv  Detail & Related papers  (2023-12-15T18:12:44Z)
• Sparsity exploitation via discovering graphical models in multi-variate time-series forecasting [1.2762298148425795]
  We propose a decoupled training method, which includes a graph generating module and a GNNs forecasting module. First, we use Graphical Lasso (or GraphLASSO) to directly exploit the sparsity pattern from data to build graph structures. Second, we fit these graph structures and the input data into a Graph Convolutional Recurrent Network (GCRN) to train a forecasting model.
  arXiv  Detail & Related papers  (2023-06-29T16:48:00Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
  We give an algorithm to perform pattern matching in quantum circuits for many patterns simultaneously. In the case of quantum circuits, we can express the bound obtained in terms of the maximum number of qubits.
  arXiv  Detail & Related papers  (2023-02-13T22:09:02Z)
• Learning to Count Isomorphisms with Graph Neural Networks [16.455234748896157]
  Subgraph isomorphism counting is an important problem on graphs. In this paper, we propose a novel graph neural network (GNN) called Count-GNN for subgraph isomorphism counting.
  arXiv  Detail & Related papers  (2023-02-07T05:32:11Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  We propose a novel non-parametric subgraph matching framework, dubbed MatchExplainer, to explore explanatory subgraphs. It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance. Experiments on synthetic and real-world datasets show the effectiveness of our MatchExplainer by outperforming all state-of-the-art parametric baselines with significant margins.
  arXiv  Detail & Related papers  (2023-01-07T05:14:45Z)
• Forecasting Graph Signals with Recursive MIMO Graph Filters [24.003433487241246]
  Forecasting time series on graphs is a fundamental problem in graph signal processing. Existing approaches resort to the use of product graphs to combine this multidimensional information, at the expense of creating a larger graph. In this paper, we show the limitations of such approaches, and propose extensions to tackle them.
  arXiv  Detail & Related papers  (2022-10-27T08:25:31Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  We propose the Neighbor2Seq to transform the hierarchical neighborhood of each node into a sequence. We evaluate our method on a massive graph with more than 111 million nodes and 1.6 billion edges. Results show that our proposed method is scalable to massive graphs and achieves superior performance across massive and medium-scale graphs.
  arXiv  Detail & Related papers  (2022-02-07T16:38:36Z)
• Accurate Learning of Graph Representations with Graph Multiset Pooling [45.72542969364438]
  We propose a Graph Multiset Transformer (GMT) that captures the interaction between nodes according to their structural dependencies. Our experimental results show that GMT significantly outperforms state-of-the-art graph pooling methods on graph classification benchmarks.
  arXiv  Detail & Related papers  (2021-02-23T07:45:58Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  We propose a new algorithm for graph matching under probabilistic models. Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$. This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
  arXiv  Detail & Related papers  (2021-01-28T02:39:27Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  We present the PPRGo model which utilizes an efficient approximation of information diffusion in GNNs. In addition to being faster, PPRGo is inherently scalable, and can be trivially parallelized for large datasets like those found in industry settings. We show that training PPRGo and predicting labels for all nodes in this graph takes under 2 minutes on a single machine, far outpacing other baselines on the same graph.
  arXiv  Detail & Related papers  (2020-07-03T09:30:07Z)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  Existing deep neural methods require $Omega(n2)$ complexity by building up the adjacency matrix. We develop a novel autoregressive model, named BiGG, that utilizes this sparsity to avoid generating the full adjacency matrix. During training this autoregressive model can be parallelized with $O(log n)$ synchronization stages.
  arXiv  Detail & Related papers  (2020-06-28T04:37:57Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.