Matching nodes in two directed graphs

Question

How to match a node of graph X with the same node in graph G if:

1. Every node has only one feature: text string, and

2. Nodes in different graphs are considered to be equal if:

      2.1 Nodes have the same value of text feature, and  
      2.2 Nodes have the same edges connecting them to the same neighbours
   

For example:

G = {S1, S2, S3}
X = {S4, S5, S2, S6}
S2 = {N1, N2, N3, N4}

where:
G - is a directed graph that has S1, S2 and S3 subgraphs
X - is another directed graph that has S4, S5, S2 and S6 subgraphs
N1,.., N4 - are S2 nodes

G subgraph connections: S1 -> S2; S1 -> S3
X subgraph connections: S4 -> S5 -> S2; S5 -> S6

In general case X subgraph connections are not known, we only assume that X has S2 subgraph with a N3 node that we want to find. In this example X also has S4, S5, and S6 subgraphs that we don't care about. These subgraphs are used here just to illustrate a fact that X may be quite different from G.

Task: Find N3 node in X graph.

Is it possible to train Graph Convolutional Network (GCN) or GNN of another type to solve this problem in general?

Please, advise on direction of research to to solve this problem.

Answer 1

Brief Answer

You are probably looking for sub graph matching algorithms to find a subgraph (e.g. S2) in the graph X. There are several graph theory algorithms and packages available for that and they do not need any training or Graph Convolutional Networks. Although you can also find such approaches if you really want to do the training.

More Details

As far as I understand the question, you are looking for one specific node (N3) in the graph X. In this case, you could extract a subgraph from G that contains N3 and all it's neighbors. I assume S2 is meant to be exactly this.

Given this setting, your task is to find the subgraph S2 in X where the node labels and the edges match. A quick search gave me for example this link: https://stackoverflow.com/questions/15671522/networkx-subgraph-isomorphism-by-edge-and-node-attributes When S2 is matched, it is easy to identify N3 in the match.

Choice of algorithms

Depending on the size of your problem, you might want to look for an exact matching (which definitely leads to graph theoretical algorithms). But if the size of S2 and X are large, you might prefer to look for an approximate algorithm (which can be both graph theoretical or machine learning based).

Restrictions / Variants

• The Subgraph Matching in this form allows N3 to have additional edges in X, e.g. if the edge S5-->S2 ends in N3, the algorithm would still find the match. If this is not desired, you would need to look for a modified algorithm
• This subgraph matching approach looks for one specific subgraph S2 and does not identify all possible subgraphs from G that can be found in X