I would love to know whether there are some practical (non-math/cs-user facing) problems which can be solved with graph (iso,sub-iso,mono,epi,...) morphism algorithms.
Sure, there's a lot you can do with it in the math and theoretical cs world, probably in chemistry (derivation of chemical reactions?) and maybe bioinformatics as well.
But despite the power of the approach - general comparison of structures and/or combinatoric enumeration of all "instances" of pattern in data graph - are there any success stories of companies with products which are killing it because of using graph morphisms under the hood? (or maybe even directly exposing pattern/data graph relations to the user)
The major use I know of is finding symmetries in other search problems.
Take your problem in Constraint Programming / Mixed Integer Programming / SAT / SMT, generate a parse tree, turn that parse tree into a graph, and find symmetries of that graph.
If done in the right way, symmetries of the graph are symmetries of the original problem, and knowledge of these symmetries can be used to avoid redundant symmetric search. This is done all the time in combinatorial search systems.
One problem for many other real-world problems is it is much more common to want "almost symmetries" (for various definitions of almost symmetry). It turns out this is a much harder problem, and algorithms for "pure" graph isomorphism can't be easily modified, to solve the 'almost symmetry' problem.
not disagreeing with you at all, more like expanding your comment.
for some definitions of 'almost', especially the vague human ones, there are very surprising results (well, not for people with CS education, but for the other ones). e.g. 2-SAT vs 3-SAT, hamiltonian path (visit all nodes on a graph) vs eulerian path (visit all edges), shortest path vs longest path, etc. like i said, the 'almost' is debatable, but for the untrained eye the problems are very similar.
Could you please state some examples of these real-world problems where "almost symmetry" would help?
Face/shape recognition comes to mind, where inexact graph matching would be useful, but are there any others?
I'm not trolling, just interested in graph matching in general as amateur. I have this feeling that there should be many more applications of these techniques, but amusingly, in practice there's always a more specialized, non matching algorithm used. (probably because of matching's algorithm complexity which doesn't scale for larger problems...)
Anytime where knowing a permutation of thing1 is the same as thing2 allows you to treat both thing1 and thing2 in a similar fashion. A related problem in canonization, finding a normal form you can put both thing1 and thing2 into knowing that if the normal form is the same they are isomorphic.
Compiler optimization, generating hardware layouts of circuits, and helping neural nets scale. Brute force isomorphism (where you check permutations but don't care if the object under study is a graph) is a bit lower than the n! naive method Babai uses as a subroutine in the paper, https://oeis.org/A186202
There are a couple of problems in cheminformatics that can be/are solved with graph isomorphism algorithms: maximum common substructure, graph edit distance, etc., the latter is quite useful to determine molecule similarity but very computationally expensive, especially compared to topological hashing algorithms.
Sure, there's a lot you can do with it in the math and theoretical cs world, probably in chemistry (derivation of chemical reactions?) and maybe bioinformatics as well.
But despite the power of the approach - general comparison of structures and/or combinatoric enumeration of all "instances" of pattern in data graph - are there any success stories of companies with products which are killing it because of using graph morphisms under the hood? (or maybe even directly exposing pattern/data graph relations to the user)