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).