Node ordering permutation based adjacency matrix

Question

An undirected graph $G=(V, E)$ is defined by its node set $V=\left\{v_1, \ldots, v_n\right\}$ and edge set $E=\left\{\left(v_i, > v_j\right) \mid v_i, v_j \in V\right\}$. One common way to represent a graph is using an adjacency matrix, which requires a node ordering $\pi$ that maps nodes to rows/columns of the adjacency matrix. More precisely, $\pi$ is a permutation function over $V$ (i.e., $\left(\pi\left(v_1\right), \ldots, \pi\left(v_n\right)\right.$ ) is a permutation of $\left.\left(v_1, \ldots, v_n\right)\right)$. We define $\Pi$ as the set of all $n$ ! possible node permutations. Under a node ordering $\pi$, a graph $G$ can then be represented by the adjacency matrix $A^\pi \in \mathbb{R}^{n \times n}$, where $A_{i, > j}^\pi=\mathbb{1}\left[\left(\pi\left(v_i\right), > \pi\left(v_j\right)\right) \in E\right]$.

Note that elements in the set of adjacency matrices $A^{\Pi}=$ $\left\{A^\pi \mid \pi \in \Pi\right\}$ all correspond to the same underlying graph.

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.

Answer 2

Edit in response to the question in the bounty.

The nodes in the graph come you you in some particular order - they are numbered from $1`$ to $n$. $A^\pi_{i,j}$ is the adjacency matrix for the graph when you list the vertices in the order determined by the permutation $\pi$ of the sequence $\{1,2,\ldots,n\}$.

The meaning of the adjacency matrix is independent of $\pi$, which does nothing to the graph.

---

@dan_fulea has written a correct answer that may be more elaborate than what you need. This part of his last paragraph is what I think you are asking about:

The cited text is very pedant, puts the accent on some bureaucratic point, the order, then introduces a lot of notation for this,

For example, consider the graph with vertices $A,B,C$ and the single edge $AB$. If you write the vertices in that order tha adjacency matrix is

0 1 0
1 0 0
0 0 0

while if you write the nodes in order $A,C,B$ the same information is encoded in the matrix

0 0 1
0 0 0
1 0 0 

The long discussion of permutations just makes this obvious fact precise.