arXiv-2020 Neural Subgraph Matching

2020-07-03 · arXiv· ML · GNN

Paper: Neural Subgraph Matching

Code: https://github.com/snap-stanford/neural-subgraph-learning-GNN

NeuroMatch: Subgraph Matching via Graph Decomposition

Abstract

NeuroMatch is a graph neural network (GNN) architecture for efficient subgraph matching. Given a large target graph and a small query graph, NeuroMatch identifies neighborhoods of the target graph that contain the query graph as a subgraph. NeuroMatch uses a GNN to learn graph embeddings in an ordered embedding space that reflects structural properties of the subgraph relation (transitivity, antisymmetry, and nontrivial intersection), enabling real-time approximate subgraph matching at scales that were previously infeasible: it can match a 100-node query graph in target graphs of size 500k. Experiments show that NeuroMatch is 100× faster than existing combinatorial methods and 18% more accurate than existing approximate subgraph matching methods.

Introduction

Subgraph isomorphism matching has many applications:

In the social sciences, subgraph analysis plays a major role in studying network effects in social networks.
Information retrieval systems use subgraph structure in knowledge graphs for semantic generalization, analogical reasoning, and relation prediction.
In chemistry, subgraph matching is a robust and accurate way to measure similarity between compounds.
In biology, subgraph matching is essential for analyzing protein–protein interaction networks, where identifying and predicting functional motifs is a primary tool for understanding biological mechanisms such as disease, aging, and medicine.

The target graph (G_T) and query graph (G_Q) are decomposed into many small overlapping graphs, and a graph neural network (GNN) embeds each piece so that we can quickly decide whether one graph is a subgraph of another.

There are two stages: an embedding stage and a query stage. In the embedding stage, the target graph (G_T) is decomposed into multiple subnetworks (G_u): for each node (u), a subnetwork (G_u) around (u) is extracted and a GNN yields an embedding for (u) that captures the neighborhood structure around (u). In the query stage, the embedding of each node (q) in the query graph (G_q) is computed from the neighborhood of (q). Embeddings of all pairs ((q, u)) are then compared to determine whether (G_Q) is a subgraph of (G_T).

NeuroMatch Architecture

Problem Setup

Problem 1. Matching query to datasets

Given a target graph (G_T) and a query graph (G_Q), predict whether (G_Q) is isomorphic to a subgraph of (G_T).

Problem 2. Matching neighborhoods

Given a neighborhood (G_u) around node (u) and a query (G_Q) anchored at node (q), make a binary prediction of whether (G_q) is a subgraph of (G_u), where node (q) corresponds to (u).

Overview of NeuroMatch

Embedding stage

In the embedding stage, (G_T) is decomposed into a collection of subgraphs; each node (u) is represented by the embedding of its neighborhood.

Query stage

A subgraph prediction function is designed to decide whether the query subgraph (G_q) anchored at (q) is a subgraph of the target neighborhood (G_u).

Practical considerations and design choices

The number of layers (k) must account for the size of the query graph; (k) is at least the diameter of the graph.

Experiments use a variant of GIN combined with skip connections to encode the query graph and neighborhoods.

Subgraph Prediction Function (f(Z_q, Z_u))

Given the target node embedding (z_u) and a center node (q \in G_Q), the subgraph prediction function decides whether (u \in G_T) has a (k)-hop neighborhood that is isomorphic to the role of (q) in (G_Q). The key point is that the subgraph prediction function makes its decision using only the embeddings (z_q) and (z_u) of nodes (q) and (u).