1
$\begingroup$

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:

Improve this question
$\endgroup$
2
  • $\begingroup$ can you clarify canonical order here? do you mean for example the order by the vertex degrees or something else? $\endgroup$
    – Ameer Jewdaki
    Commented Jun 14, 2021 at 16:37
  • $\begingroup$ 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...) $\endgroup$
    – Joppy
    Commented Jun 15, 2021 at 7:54

1 Answer 1

Reset to default
1
$\begingroup$

If we had a way to canonicalize graphs efficiently, then we could canonicalize the graph before feeding it to the ML.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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