Identifying identical graphs or adjacency matrices of graphs

Question

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:

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

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?

Answer 1

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.