3
$\begingroup$

I was wondering if someone has a good idea for checking whether two graphs are the same (for example, based on an adjacency matrix). Ideally, in a computational efficient manner that can be done on large collections of small graphs (3-30 nodes)

To illustrate the probblem, depending on how I enumerate the different nodes in the same graph, the same nodes may appear in different places of the adjacency matrix. Or in other words, we have a many-to-one mapping scenario where many different adjacency matrix can encode the same graph.

For instance, assume I have a undirected, unweighted graph like this:

enter image description here

a) The adjacency matrix rotated, transposed, or otherwise modified could yield the same graph. Similar, changing the node numbering in the graph

enter image description here

would result in a adjacency matrix that has different entries as the one shown above but encodes the same graph:

$$ \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 \end{bmatrix} $$

Do you know a way for checking whether two adjacency matrices encode the same graph?

$\endgroup$
1
  • $\begingroup$ 30 nodes graphs are very small. I do not think you will have problems. Basic backtracking is enough. $\endgroup$ Feb 15, 2020 at 1:37

1 Answer 1

2
$\begingroup$

Graph matching is the process of finding a correspondence between the nodes and theedges of two graphs that satisfes some (more or less stringent) constraints ensuring that similar substructures in one graph are mapped to similar substructures in the other.

People usually divide the matching methods into two broad categories: the first contains exact matching methods that require a strict correspondence among the two objects being matched or at least among their subparts.The second category defines inexact matching methods, where a matching can occur even if the two graphs being compared are structurally different to some extent.

Most of the algorithms for exact graph matching are based on some form of tree search with backtracking.

For the case of inexact graph matching algorithms, the matching between two nodes that do not satisfy the edge-preservation requirements of the matching type is not forbidden. Instead, it is penalized by assigning to it a cost that may take into account other differences. So the algoriths must find a mapping that minimizes the matching cost.

There are many variations of both algorithms for both cases.

One faster possibility is to take a look at eigenvalue similarity, but keep in mind that this is not a correspondence. It may happen that graphs that are similar in terms of eigenvalues are not the same.

Some reviews of the problem may be found in:

1) THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION - International Journal of Pattern Recognition and Artificial Intelligence Vol. 18, No. 03, pp. 265-298 (2004) - D. CONTE, P. FOGGIA, C. SANSONE and M. VENTO (where I got most information above).

2) Algorithms for graph similarity

If you are a Python user, you may find routines here: Python functions measuring similarity using graph edit distance.

$\endgroup$
1
  • 1
    $\begingroup$ That's a very informative summary, thanks a lot. Will also be reading through that review. Thanks! $\endgroup$
    – resnet
    Feb 15, 2020 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.