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 , GAT 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:
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.
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
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.
- 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).