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:

Image for post
Image for post

For example:

Image for post
Image for post

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:

Image for post
Image for post

In dense matrix format:

Image for post
Image for post

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:

Image for post
Image for post

And, the resulting normalized matrix looks like:

Image for post
Image for post

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

Researcher/Historian [RIT-2119 cohort]. I specialize in classical roboquity era and 4th industrial era robotic evolution. Covering human AI research 2020–2042

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store