# Why does it take O(n!) time to specify a canonical ordering for learning flatten adjacency matrices/graphs?

I was reading a paper for learning graphs (paper is GraphRNN) and it says in section 2.2 (emphasis by me):

Vector-representation based models. One naive approach would be to represent G by flattening $$A^π$$ into a vector in $$R^{n^2}$$, which is then used as input to any off-the-shelf generative model, such as a VAE or GAN. However, this approach suffers from serious drawbacks: it cannot naturally generalize to graphs of varying size, and requires training on all possible node permutations or specifying a canonical permutation,both of which require O(n!) time in general

I understand how flattening the adjacency matrix would require the algorithm to receive all possible orderings and thus it takes $$O(n!)$$ to learn it - but I don't understand why specifying a canonical ordering has that issue to. With some abuse of notation just do $$\pi(G,A) = G^\pi,A^\pi$$ for all graphs before giving them to the training algorithm. Something like (say we have $$N$$ graphs with $$n$$ verticies and we loop T times):

for t in T
for G,A in Graphs.Dataset
Gpi, Api = pi(G,A)  # takes worst case O(n^2) to at least do print the adj matrix
y = mdl(Gpi, Api)
loss(y,Gpi,Api).backward().sgd() # assume we are doing SGD or something


The run time seems $$O(N)*O(n^2)$$ not $$O(N)*O(n!)$$. So I am not sure why the canonical representation takes $$O(n!)$$ (note I am aware that just multiplying big-Os like that can lead to problems but specifying the summation explicitly in this case I think leads to no issues).

Thanks for the help!

cross:

• can you clarify canonical order here? do you mean for example the order by the vertex degrees or something else? Commented Jun 14, 2021 at 16:37
• A "canonical permutation" in the sense of the authors would accept an adjacency matrix $A$, and return a permutation $\pi_A$, so that two adjacency matrices $A$ and $B$ represent the same underlying undirected graph if and only if $\pi_A(A) = \pi_B(B)$. In particular this could be used to solve the graph isomorphism problem, which is known to be hard (but not factorially-hard...) Commented Jun 15, 2021 at 7:54

Unfortunately, no polynomial-time algorithm for graph canonization is known. One naive algorithm for graph canonization runs in $$O(n!)$$ time. I don't believe the claim is literally correct that graph canonization requires $$O(n!)$$ time, but a plausible conjecture is that there is no polynomial-time algorithm for graph canonization. I suspect that's what that quote is trying to express.