Neural Subgraph Matching
40
Citation
42
Reference
10
Related Paper
Citation Trend
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.Keywords:
Subgraph isomorphism problem
Factor-critical graph
Graph factorization
Subgraph isomorphism problem
Graph isomorphism
Graph factorization
Isomorphism (crystallography)
Factor-critical graph
Representation
Cite
Citations (1)
Subgraph isomorphism problem
Graph factorization
Factor-critical graph
Graph isomorphism
Distance-hereditary graph
Cite
Citations (7)
Subgraph isomorphism problem
Factor-critical graph
Graph factorization
Cite
Citations (16)
Subgraph Matching is a fundamental problem in graph analysis, and is widely used in many application scenarios in biology, chemistry and social network. Given a data graph and a query graph, subgraph matching aims to compute all subgraphs of the data graph that are isomorphic to the query graph. The problem is computationally expensive as the core operation it depends on, known as subgraph isomorphism, is NP-complete. In recent years, graph is increasing extensively and it is hard to compute subgraph matching on massive graph data using existing serial algorithm. Meanwhile, there exist distributed solutions, but they are mostly limited to the case where the graphs are unlabelled. In response to this gap, we study the subgraph matching problem in the multi-core environment. From the algorithm level, we propose a multi-core parallel subgraph matching algorithm called MPMatch. From the research level, we explore the concurrent allocation of subgraph matching search space to approach load balancing. We conduct extensive empirical studies on real and synthetic graphs to demonstrate that our techniques improve the performance of serial subgraph matching algorithm via parallelization and well-developed load balancing schema.
Subgraph isomorphism problem
Factor-critical graph
Graph factorization
Distance-hereditary graph
Graph isomorphism
Cite
Citations (8)
Subgraph isomorphism problem
Graph factorization
Graph isomorphism
Factor-critical graph
Graph homomorphism
Isomorphism (crystallography)
Cite
Citations (82)
Subgraph isomorphism problem
Factor-critical graph
Graph factorization
Distance-hereditary graph
Cite
Citations (23)
Subgraph query in graph set returns data graph containing query graph.When the query graph and data graph both are uncertain,this paper proposes a definition of subgraph isomorphism between uncertain graphs and a definition of α-β subgraph isomorphism matching.Expectation subgraph isomorphism between uncertain graphs is a direct extension of subgraph isomorphism between deterministic graphs on probability graph model.There are two parameters α and β which are the thresholds to restrict quality of matching between query graph and data graph.This paper elaborates features of α-β subgraph isomorphism matching in detail,analyzes the differences between it and expectation subgraph isomorphism,meanwhile proposes α-β subgraph isomorphism matching decision algorithm.
Subgraph isomorphism problem
Graph isomorphism
Graph factorization
Distance-hereditary graph
Factor-critical graph
Graph automorphism
Graph homomorphism
Graph property
Cite
Citations (0)
Subgraph isomorphism problem
Graph factorization
Factor-critical graph
Graph isomorphism
Distance-hereditary graph
Cite
Citations (2)
Subgraph isomorphism problem
Graph isomorphism
Factor-critical graph
Isomorphism (crystallography)
Graph factorization
Distance-hereditary graph
Cite
Citations (0)
The subgraph isomorphism problem is the problem of whether one graph is contained in another graph, given two graphs. An enormous calculation cost is necessary for this problem when large quantities of graphs are handled because it is NP complete. Messmer et al. propose the algorithm to solve this problem efficiently based on graph decomposition. We improve the Messmer’s approach so that connected graphs are formed in the decomposition of each graph and information produced by graph decomposition is used in subgraph isomorphism detection. Keyword Subgraph isomorphism,Graph decomposition,Graph matching
Subgraph isomorphism problem
Graph isomorphism
Distance-hereditary graph
Graph factorization
Factor-critical graph
Graph homomorphism
Cograph
Graph property
Modular decomposition
Graph automorphism
Block graph
Cite
Citations (0)