How is the adjacency matrix of a directed graph normalized

adjacency matrixdirected graphsgraph theoryspectral-graph-theory

For an undirected graph with adjacency matrix $A$, it is straightforward to define the normalized adjacency matrix as
$$ A'=D^{-1/2}AD^{-1/2}$$
where D is the diagonal matrix of degrees of the nodes of the graph.

For a directed graph, however, I'm unclear on how to best define the normalized adjacency matrix. It seems like the most direct extension is to simply consider the diagonal matrix of in- or out-degrees, instead. However, selecting one versus the other would appear to give very different results.

Is there a standard way to define the normalized adjacency matrix for directed graphs?

Best Answer

According to my research, you can normalize directed adjacency graph either by rows or columns.

$A'=D^{−1}A$ or $A'= A D^{−1}$.

Supporting Evidence:

  1. Official Answer from Kipf (TF-GCN repo), https://github.com/tkipf/gcn/issues/91;
  2. Interpretation of Symmetric Normalised Graph Adjacency Matrix?;
  3. CVPR paper "Skeleton-Based Action Recognition with Directed Graph Neural Networks", Section 3.3.2;

Hope this helps.

Related Question