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

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

Written by