[Math] Node ordering permutation based adjacency matrix

Question

I was reading a research paper where I came across this definition of an adjacency matrix based on a node ordering function. I am a beginner in graph theory hence was not able to understand the concept of node permutation. Any help is appreciated.

• paper: https://arxiv.org/abs/1802.08773 GraphRNN by Stanford CS.
• Quora: https://www.quora.com/unanswered/What-does-the-adjacency-matrix-for-permutation-mean-in-the-GraphRNN-paper
• reddit: https://www.reddit.com/r/learnmachinelearning/comments/nx06n0/what_does_the_adjacency_matrix_for_permutation/

Answer 1

I will give an example, and to make the typing as economical as possible, i will use sage:

sage: G = graphs.PetersenGraph()
sage: G
Petersen graph: Graph on 10 vertices
sage: G.adjacency_matrix()
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: G.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: G.show()
Launched png viewer for Graphics object consisting of 26 graphics primitives

Above, the rows and the columns of the matrix are labeled $0,1,2,3,4,5,6,7,8,9$ and considered with this order of them. For instance, $6$ and $9$ are joined by an edge, because of this we have the $\boxed 1$ entry in row $6$ column $9$ (and vice versa):

$$ \left[\begin{array}{rrrrrrrrrr} 0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & \boxed 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & \boxed 1 & 1 & 0 & 0 \end{array}\right] \ . $$ The first row is 0 1 0 0 1 1 0 0 0 0 corresponding to the columns $0,1,2,3,4,5,6,7,8,9$, and the ones are corresponding to $1,4,5$, which are the neighbours of $0$ in the graph.

---

Now it is possible that an alien prefers an other order, for instance $9,6,7,2,1,3,5,4,0,8$. Then he/she/it should write an other matrix. The corresponding boxed entries are now $$ \left[\begin{array}{rrrrrrrrrr} 0 & \boxed 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \boxed 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \end{array}\right] $$ The first row is 0 1 1 0 0 0 0 1 0 0 corresponding to the columns $9,6,7,2,1,3,5,4,0,8$, and the ones are corresponding to $6,7,4$, which are the neighbours of $9$ in the graph.

The following code was used to get he new matrix for the new order.

sage: L = [9,6,7,2,1,3,5,4,0,8]
sage: A = G.adjacency_matrix()
sage: B = matrix(ZZ, 10, 10, [A[m,n] for m in L for n in L] )
sage: latex(B)

Note: The cited text is very pedant, puts the accent on some bureaucratic point, the order, then introduces a lot of notation for this, a permutation $\pi$, the space of permutations, makes it part of the structure. This is maybe misleading at least in the same measure i am in similar situations.