# Row Normalizing Graph Adjacency Matrices

Graphical representations are increasingly getting popular in machine learning (ML) and data science research. Skimming recent literature in geometric learning and/or Graphical Neural Networks (GNNs) techniques like GCN [1], GAT[2] can be befuddling for fresh eyes. Thus, in a series of succinct posts, I will elucidate atomic/foundational concepts that can be helpful in the long run to grasp the overall concepts.

Before delving into topics like ‘**Graph Laplacians**’ and subsequent computations, let’s start things off with a very simple atomic concept: **row normalizing adjacency matrices of a graph**.

As a recap, for a graph with `n`

vertices, the entries of the `n * n`

**adjacency matrix**, A are defined by:

For example:

Adjacency matrices for real world (large) graphs are represented using sparse matrices. The COO (coordinate) or CSR (compressed sparse row) are most common formats for such representations.

The `coefficients`

variable in the above diagram represents a graph `Gu_matched`

with 10 vertices (or nodes) and 8 edges. The tuple is of the form (row, col, weight). The edges `e_ij`

connects node `i`

in row to another node `j`

in col, with weight `1`

.

Similarly, `coefficients`

var for a simpler graph `Gs`

with just 5 nodes can be like this: `[(0, 0, 0, 0, 1, 2, 3, 4), (1, 2, 3, 4, 0, 0, 0, 0), (1, 1, 1, 1, 1, 1, 1, 1]`

In COO format:

In dense matrix format:

*But what does ‘row-normalizing’ mean*? Basically, for the above dense matrix A, if we sum all the values row-wise, then we will get a `5 by 1`

vector `[4, 1, 1, 1, 1]`

. Row-normalizing simply means normalizing this vector so the rows all sum to `1`

i.e. [1 , 1, 1, 1, 1] (if you thought of the `softmax(A)`

function, then kudos). This trick has **down-stream applications for various ML and graphical computations** (e.g. graph laplacians). We will keep it simple, and atomic, so those are for another blog.

The following code-snippet shows the code for row-normalizing an adjacency matrix.

`r_mat_inv`

looks like:

And, the resulting normalized matrix looks like:

As you can see, the rows all sum to `1`

as desired.

**Reference**

- Kipf, Thomas N., and Max Welling. “Semi-supervised classification with graph convolutional networks.”
*arXiv preprint arXiv:1609.02907*(2016). - Veličković, Petar, et al. “Graph attention networks.”
*arXiv preprint arXiv:1710.10903*(2017).