Local Graph Isomorphism to construct Global Graph Isomorphism

Question

Does there exist a Graph Isomorphism Algorithm that uses Local Isomorphism to construct a Global Isomorphism?

For example, two graphs are given, say, $H, G$. it is asked to determine whether $G\simeq H$.

Now assume there exists an algorithm that splits graph $G$ in to Subgraph $G_1, G_2$(in $G$, $G_1$ and $G_2$ are connected through a set of edges, say, $R_1$) and finds Isomorphism to corresponding graph $H_1 , H_2$(Local Isomorphism), then merge those Isomorphism to check whether $G\simeq H$ (Global isomorphism).

Does there exist such algorithm in Graph Isomorphism Literature ?

EDIT:

I apologize for a vague description, I should be more specific, but it is really hard to specify at the moment. For the time being, note that I do not mean a splitting based on vertex classification entirely or something like that. An algorithm that is based on $K$ Dimensional Weisfeiler-lehman(depth $K$ neighborhoods) entirely, is not what I meant, that is for sure**. if $K=1$, then it can not handle regular graph. You can "construct" graph that makes $K$ Dimensional Weisfeiler-lehman ineffective, for example Cai-Furer-Immerman pair. Certainly I do not mean that.Note that NAUTY uses 1 Dimensional Weisfeiler-Lehman method.

This question is the closest I got to mine, but it does not answer my query.

Answer 1

This is actually how many graph isomorphism algorithms work (often in combination with Weisfeiler-Lehman). For example, bounded color class isomorphism (Luks 1983) works by first finding isomorphisms within each color class, then combining those using the edges between color classes. Zemlyachenko's trick could then be used to individualize $\tilde{O}(\sqrt{n})$ vertices, so that the resulting graph had bounded color classes (which led to the previous-best algorithm for GI).

Babai's recent algorithm does another kind of divide-and-conquer that is sort of along the lines you mention. It either finds a partition of the graph into small parts (where "small" here means some constant fraction smaller than the original graph; the result is that such recursion can only happen $O(\log n)$ times) or finds a large embedded Johnson scheme. In the latter case, it handles the Johnson scheme by a different recursive technique, but then handles the vertices that aren't in the Johnson scheme essentially along the lines you suggest. (Indeed, if you look at the table of contents of Babai's paper you will see there is quite a lot of talk about "local to global" principles, though it's not really the same "local to global" you're talking about here.)

Answer 2

NAUTY "colors" nodes with constant depth neighborhood canonical forms. Babai's new algo does likewise with log size neighborhoods.

The kicker is that in a random graph the diameter is about log n, so you end up gobbling the whole thing.

Definitely worth doing for sparse graphs, can really cut down the state space you need to search. Also when you have to go brute force, only check repeated prime cycles, not all k! https://oeis.org/A186202