Neural Subgraph Matching

• URL: http://arxiv.org/abs/2007.03092v2
• Date: Tue, 27 Oct 2020 17:48:05 GMT
• Title: Neural Subgraph Matching
• Authors: Rex (Zhitao) Ying, Zhaoyu Lou, Jiaxuan You, Chengtao Wen, Arquimedes Canedo, Jure Leskovec
• Abstract summary: NeuroMatch is an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch is 100x faster than existing geometric approaches and 18% more accurate than existing subgraph matching methods.
• Score: 57.05893848555512
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Subgraph matching is the problem of determining the presence and location(s) of a given query graph in a large target graph. Despite being an NP-complete problem, the subgraph matching problem is crucial in domains ranging from network science and database systems to biochemistry and cognitive science. However, existing techniques based on combinatorial matching and integer programming cannot handle matching problems with both large target and query graphs. Here we propose NeuroMatch, an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch decomposes query and target graphs into small subgraphs and embeds them using graph neural networks. Trained to capture geometric constraints corresponding to subgraph relations, NeuroMatch then efficiently performs subgraph matching directly in the embedding space. Experiments demonstrate NeuroMatch is 100x faster than existing combinatorial approaches and 18% more accurate than existing approximate subgraph matching methods.

Related papers

• xNeuSM: Explainable Neural Subgraph Matching with Graph Learnable Multi-hop Attention Networks [2.084955943646144]
  Subgraph matching is a challenging problem with a wide range of applications in database systems, biochemistry, and cognitive science. Traditional graph-matching algorithms provide precise results but face challenges in large graph instances due to the NP-complete problem. This article introduces Graph Learnable Multi-hop Attention Networks (GLeMA) that adaptively learns the parameters governing the attention factor decay for each node across hops.
  arXiv  Detail & Related papers  (2023-12-04T04:03:30Z)
• 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)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  We propose a general learnable graph matching method to address these issues. Our method achieves state-of-the-art performance on several MOT datasets. For image matching, our method outperforms state-of-the-art methods on a popular indoor dataset, ScanNet.
  arXiv  Detail & Related papers  (2023-03-27T17:39:00Z)
• 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)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  Subgraph Matching is a core operation in graph database search, biomedical analysis, social group finding, etc. In this paper, we propose a novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs. Experiments on five large real-world target graphs show that N-BLS can significantly improve the subgraph matching performance.
  arXiv  Detail & Related papers  (2022-07-21T04:47:21Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Interactive Visual Pattern Search on Graph Data via Graph Representation Learning [20.795511688640296]
  We propose a visual analytics system GraphQ to support human-in-the-loop, example-based, subgraph pattern search. To support fast, interactive queries, we use graph neural networks (GNNs) to encode a graph as fixed-length latent vector representation. We also propose a novel GNN for node-alignment called NeuroAlign to facilitate easy validation and interpretation of the query results.
  arXiv  Detail & Related papers  (2022-02-18T22:30:28Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Neural Bipartite Matching [19.600193617583955]
  This report describes how neural execution is applied to a complex algorithm. It is achieved via neural execution based only on features generated from a single GNN. The evaluation shows strongly generalising results with the network achieving optimal matching almost 100% of the time.
  arXiv  Detail & Related papers  (2020-05-22T17:50:38Z)

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.