import marimo as mo
Networks, Adjacency and Laplacian Matrices¶
In Basic pathpyG Concepts, we have seen how we can create (un)directed Graph objects with node-, edge- and graph-level attributes. In this tutorial, we build on this and show how we can represent networks as adjacency and Laplacian matrices, two important mathematical representations of networks that we will use throughout the following tutorials.
We first import pathpyG and torch:
import torch
import pathpyG as pp
We create two small example networks: an undirected triangle graph with integer node indices, and a directed network with string node IDs where edges have a numerical edge_type attribute.
g1 = pp.Graph.from_edge_list([(0, 1), (1, 2), (2, 0)])
g2 = g1.to_undirected()
print(g2)
Undirected graph with 3 nodes and 3 edges
{'Edge Attributes': {}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
n_1 = pp.Graph.from_edge_list([('Tom', 'Bert'), ('Bert', 'Bill'), ('Bill', 'Tom')])
n_1.data.edge_type = torch.tensor([[1], [2], [1]])
print(n_1)
Directed graph with 3 nodes and 3 edges
{'Edge Attributes': {'edge_type': "<class 'torch.Tensor'> -> torch.Size([3, 1])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
Adjacency and Laplacian matrices¶
Adjacency matrices and Laplacian matrices are important mathematical representations of networks.
Adjacency matrix¶
The topology of a graph can be represented in the entries of a matrix $A$, where an entry $A[i,j]=1$ indicates that an edge exists from the i-th to the j-th node of the network. The absence of edges is encoded by zero entries. The size of an adjacency matrix representation of a network with n nodes is generally $n^2$, which is not suitable for networks with thousands or millions of nodes. pathpyG nevertheless supports efficient adjacency matrix calculation for sparse networks, i.e. networks where the majority of node pairs are not connected by an edge. Instead of a fully populated matrix, a call to Graph.sparse_adj_matrix() returns a sparse matrix object, which is an efficient adjacency-list representation capturing the indices and values of non-zero entries.
Laplacian matrix¶
The Laplacian matrix is a second, closely related representation that plays a central role in spectral graph theory. For an undirected graph with adjacency matrix $A$ and diagonal degree matrix $D$ (where $D_{ii}$ is the degree of the $i$-th node), the (unnormalized) Laplacian is defined as
$$ L = D - A $$
The eigenvalues and eigenvectors of $L$ reveal important structural properties of a graph. For instance, the multiplicity of the eigenvalue zero corresponds to the number of connected components of the graph, and the eigenvector belonging to the second-smallest eigenvalue (the so-called Fiedler vector) can be used to detect natural cluster structure in a graph. We will use exactly this idea to construct a simple, unsupervised node embedding technique called Laplacian eigenmaps in a later notebook of this tutorial. Just like for the adjacency matrix, pathpyG provides a convenience function Graph.laplacian() that directly returns a sparse matrix representation of the Laplacian.
print(n_1.sparse_adj_matrix())
<COOrdinate sparse matrix of dtype 'float32' with 3 stored elements and shape (3, 3)> Coords Values (0, 1) 1.0 (1, 2) 1.0 (2, 0) 1.0
This enables us to directly apply matrix algebra operations from the sparse linear algebra module that is contained in scipy. If we instead want a dense matrix that includes zero entries, we can write:
print(n_1.sparse_adj_matrix().todense())
[[0. 1. 0.] [0. 0. 1.] [1. 0. 0.]]
The fact that the matrix is assymetric tells us that this is a directed network. By default, a binary matrix representation is returned where entries store the presence or absence of edges as 0 or 1 entries. If we want to use numerical attributes of edges instead, we can pass the name of a numerical attribute that should be used:
print(n_1.sparse_adj_matrix(edge_attr='edge_type').todense())
[[0 1 0] [0 0 2] [1 0 0]]
How does pathpyG populate adjaecency matrices if the network contains multiple edges between the same pair of nodes? Let's try this by creating another edge between Tom and Bert, and let's further add a strength attribute:
n_2 = pp.Graph.from_edge_list([('Tom', 'Bert'), ('Bert', 'Bill'), ('Bill', 'Tom'), ('Tom', 'Bert')])
n_2.data.edge_weight = torch.tensor([[2], [0.5], [1.2], [3.7]])
print(n_2)
Directed graph with 3 nodes and 4 edges
{'Edge Attributes': {'edge_weight': "<class 'torch.Tensor'> -> torch.Size([4, 1])"}, 'Graph Attributes': {'num_nodes': "<class 'int'>"}, 'Node Attributes': {}}
If we now generate an adjacency matrix, the entries contain the number of different edge objects between pairs of nodes:
n_2.sparse_adj_matrix().todense()
matrix([[0., 1., 0.],
[0., 0., 1.],
[2., 0., 0.]], dtype=float32)
If we use a numerical attribute to calculate the matrix entries in such a network, the attributes of all edges between the same pair of nodes is automatically summed:
n_2.sparse_adj_matrix(edge_attr='edge_weight').todense()
matrix([[0. , 2. , 0. ],
[0. , 0. , 0.5],
[4.9, 0. , 0. ]], dtype=float32)
Let's compute the Laplacian matrix for the undirected triangle graph g2 that we created at the beginning of this notebook:
print(g2.laplacian().todense())
[[ 2. -1. -1.] [-1. 2. -1.] [-1. -1. 2.]]
Since g2 is the undirected triangle graph on three nodes (each node has degree two), the diagonal entries of $L$ are all equal to two, while the off-diagonal entries are $-1$ for every pair of adjacent nodes (and would be zero for non-adjacent nodes). We can double check this by manually computing $D - A$ from the adjacency matrix and the node degrees:
import scipy as sp
A = g2.sparse_adj_matrix()
D = sp.sparse.diags(g2.degrees(mode='in', return_tensor=True).numpy())
L = D - A
print(L.todense())
/tmp/marimo_36005/__marimo__cell_ulZA_.py:4: FutureWarning: Input has data type int32, but the output has been cast to float64. In the future, the output data type will match the input. To avoid this warning, set the `dtype` parameter to `None` to have the output dtype match the input, or set it to the desired output data type. D = sp.sparse.diags(g2.degrees(mode='in', return_tensor=True).numpy())
[[ 2. -1. -1.] [-1. 2. -1.] [-1. -1. 2.]]
In many applications it is useful to work with a normalized Laplacian instead, since the unnormalized Laplacian is dominated by nodes with high degree. pathpyG supports two common normalization schemes, which can be selected via the normalization argument of Graph.laplacian():
normalization='sym'gives the symmetric normalized Laplacian $L_{sym} = I - D^{-1/2} A D^{-1/2}$normalization='rw'gives the random-walk normalized Laplacian $L_{rw} = I - D^{-1} A$, which is closely related to the transition matrix of a random walk on the graph
Let's compute the symmetric normalized Laplacian of our example graph:
print(g2.laplacian(normalization='sym').todense())
[[ 1. -0.49999997 -0.49999997] [-0.49999997 1. -0.49999997] [-0.49999997 -0.49999997 1. ]]