Neural Subgraph Matching

Definition

Neural subgraph matching is a model desinged to solve the subgraph matching problem using neural networks.

Architecture

Consider a subgraph $G_Q$ and a target graph $G_T$

Embedding

For each node in the query $G_Q$ and target graph $G_T$, obtain a $k$-hop neighborhood around the anchor. The neighborhoods are embedded using GNN by computing the embeddings for the anchor nodes in their respective neighborhoods. The GNN is trained to have partial order relation in its embedding space.

Order Embedding

Order embedding enforces a partial order relationship between node embeddings of the sub graphs. It is used to capture the hierarchical relationship between graphs and subgraphs. A partial order is defined in the embedding space where larger graphs are located above of their subgraphs.

Subgraph isomorphism relationship can be encoded in order embedding space ${\forall }_{i=1}^d,{\mathbf{z}}_q[i]\le {\mathbf{z}}_t[i]\iff G_q\subset G_t$ where $d$ is the dimension of the embedding space, and ${\mathbf{z}}_q[i]$ is the $i$-th value of the embedding vector of subgraph anchor $q$.

The GNN for the embedding is trained by minimizing a max-margin loss with Contrastive Learning examples. The margin between graph embedding of $G_q$ and $G_t$ are defined as $E({\mathbf{z}}_q,{\mathbf{z}}_t)=\sum _{i=1}^d(\max (0,{\mathbf{z}}_q[i]-{\mathbf{z}}_t[i]){)}^2$ The max-margin loss is defined as $\mathcal{L}=\sum _{({\mathbf{z}}_q,{\mathbf{z}}_t)\in P}E({\mathbf{z}}_q,{\mathbf{z}}_t)+\sum _{({\mathbf{z}}_q,{\mathbf{z}}_t)\in N}\max (0,\alpha -E({\mathbf{z}}_q,{\mathbf{z}}_t))$ where $P$ is a set of positive pairs, and $N$ is a set of negative pairs.

Max-margin loss prevents the model from embedding all vectors to far from the origin.

Subgraph Prediction

Consider a query graph $G_q$ anchored at node $q$, and a target graph $G_t$ anchored at node $t$. By using the margin used for embedding, we can check whether $G_q$ is a node-anchored subgraph of the target graph $G_t$. $f({\mathbf{z}}_q,{\mathbf{z}}_t)=\{\begin{array}{ll}1& E({\mathbf{z}}_q,{\mathbf{z}}_t)<ϵ\\ 0& \text{otherwise}\end{array}$ where $ϵ$ is a hyperparameter works as a threshold.

To check if $G_Q$ is isomorphic to a subgraph of $G_T$, repeat this process for all $q\in G_Q$ and $t\in G_T$ and aggregate the result to make the binary prediction for the decision problem of subgraph matching. Here $G_q$ is the neighborhood around the anchor node $q\in G_Q$.