Rating Matrix, Adjacency Matrix, Degree Matrix, Laplacian Matrix
This article covers the rating matrix (preference matrix), Laplacian matrix, adjacency matrix, and degree matrix, essential in recommendation systems. We compute these matrices using Python’s Networkx library. These concepts are pivotal in graph theory and spectral graph theory.
Rating Matrix, Preference Matrix
In recommendation systems, the rating matrix captures user-item relationships numerically, with rows as users and columns as items, and each element representing the user’s rating.
Understanding user preferences involves “explicit feedback” (e.g., star ratings) and “implicit feedback” (e.g., browsing history). Explicit feedback is straightforward but biased; implicit feedback is extensive but complex. Combining these enhances recommendation accuracy.
For “explicit feedback,” ratings range from 1 to 5; for “implicit feedback,” they are binary (0 or 1). Below is data based on implicit feedback.
The rating matrix $\mathbf{R}$ is:
$$ R_{u, i}=\left\lbrace\begin{array}{lr} 1, & \text { if }(u, i) \text { interaction is observed } \\ 0, & \text { otherwise } \end{array}\right. $$
$$ \begin{array}{|l|r|r|r|r|} \hline & \text{ item1 } & \text{ item2 } & \text{ item3 } & \text{ item4 } \\ \hline \text{ user1 } & 0 & 1 & 0 & 0 \\ \hline \text{ user2 } & 0 & 0 & 1 & 1 \\ \hline \text{ user3 } & 1 & 0 & 0 & 0 \\ \hline \text{ user4 } & 0 & 1 & 0 & 0 \\ \hline \text{ user5 } & 1 & 0 & 1 & 0 \\ \hline \end{array} $$
Adjacency Matrix ($\mathbf{A}$)
The adjacency matrix $\mathbf{A}$ captures node connections in a graph.
- Definition: Rows and columns are nodes, with 1 if nodes are connected, 0 otherwise.
- Characteristics: Represents edge information directly.
- Applications: Used in network analysis and modeling user-item relationships in recommendation systems.
The adjacency matrix $\mathbf{A}$ is:
$$ \mathbf{A}=\left(\begin{array}{cc} \mathbf{0} & \mathbf{R} \\ \mathbf{R}^T & \mathbf{0} \end{array}\right) $$
Degree Matrix
The degree matrix $\mathbf{D}$ represents each node’s degree.
- Definition: Diagonal matrix with diagonal elements showing node degrees.
- Characteristics: Off-diagonal elements are 0.
- Applications: Used in constructing Laplacian matrices and network analysis.
$\mathbf{D}$ is:
$$ \mathbf{D}=\text{Diag}\left(\mathbf{A} \cdot \mathbf{1}\right) $$
Laplacian Matrix
The Laplacian matrix $\mathbf{L}$ is defined as:
$$ \mathbf{L} = \mathbf{D} - \mathbf{A} $$
- Characteristics: Diagonal elements show node degrees, off-diagonal elements are -1 or 0.
- Applications: Used in network connectivity, clustering, and spectral graph theory.
Visualizing the Matrices Using Python
GitHub
- The Jupyter notebook file is available here
Google Colaboratory
- To run on Google Colaboratory, use this link
Execution Environment
!sw_vers
ProductName: macOS
ProductVersion: 13.5.1
BuildVersion: 22G90
!python -V
Python 3.9.17
Import the basic libraries and check their versions. Use PyTorch for learning and Networkx for network-related tasks.
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
import networkx as nx
print('matplotlib : {}'.format(matplotlib.__version__))
print('networkx : {}'.format(nx.__version__))
print('numpy : {}'.format(np.__version__))
matplotlib : 3.8.1
networkx : 3.1
numpy : 1.25.2
Creating a Bipartite Graph, Calculating L, A, D, and Normalized Matrices
Based on the rating matrix, we use NetworkX to create the adjacency, degree, and Laplacian matrices, and visualize the graph structure.
The graph is represented as a bipartite graph, meaning no direct user-to-user relationships exist.
$$ \begin{array}{|l|r|r|r|r|} \hline & \text{ item1 } & \text{ item2 } & \text{ item3 } & \text{ item4 } \\ \hline \text{ user1 } & 0 & 1 & 0 & 0 \\ \hline \text{ user2 } & 0 & 0 & 1 & 1 \\ \hline \text{ user3 } & 1 & 0 & 0 & 0 \\ \hline \text{ user4 } & 0 & 1 & 0 & 0 \\ \hline \text{ user5 } & 1 & 0 & 1 & 0 \\ \hline \end{array} $$
# Define the graph
# Since it is a bipartite graph, we denote it as B
B = nx.Graph()
# Define the number of users and items
user_num = 5
item_num = 4
# Define the nodes
user_node_list = [i + 1 for i in range(user_num)]
item_node_list = [i + 1 for i in range(100, 100 + item_num)]
# Define nodes as a bipartite graph
B.add_nodes_from(user_node_list, bipartite=0)
B.add_nodes
_from(item_node_list, bipartite=1)
node_color = []
node_size = [600 for i in range(user_num + item_num)]
# Define the color for the graph in Networkx
for u in user_node_list:
node_color.append("red")
for i in item_node_list:
node_color.append("lightblue")
# Define the positions for the graph
pos = {}
for _i, u in enumerate(user_node_list):
pos[u] = np.array([-1, -1.75 * _i])
for _j, i in enumerate(item_node_list):
pos[i] = np.array([1, -1.75 * _j])
# User and item relationships obtained from implicit feedback
edge_nodes = [
(1, 102),
(2, 103),
(2, 104),
(3, 101),
(4, 102),
(5, 101),
(5, 103),
]
B.add_edges_from(edge_nodes)
nx.draw(B, pos=pos, with_labels=True, node_color=node_color, node_size=node_size)
plt.show()
Once the graph object B is defined, Networkx calculates the adjacency and Laplacian matrices for us.
A = np.array(nx.adjacency_matrix(B).todense())
A
array([[0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 1, 0],
[0, 0, 1, 0, 1, 0, 0, 0, 0],
[1, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 1, 0, 0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0, 0, 0, 0]])
L = np.array(nx.laplacian_matrix(B).todense())
L
array([[ 1, 0, 0, 0, 0, 0, -1, 0, 0],
[ 0, 2, 0, 0, 0, 0, 0, -1, -1],
[ 0, 0, 1, 0, 0, -1, 0, 0, 0],
[ 0, 0, 0, 1, 0, 0, -1, 0, 0],
[ 0, 0, 0, 0, 2, -1, 0, -1, 0],
[ 0, 0, -1, 0, -1, 2, 0, 0, 0],
[-1, 0, 0, -1, 0, 0, 2, 0, 0],
[ 0, -1, 0, 0, -1, 0, 0, 2, 0],
[ 0, -1, 0, 0, 0, 0, 0, 0, 1]])
The degree matrix can be calculated by $\mathbf{L} + \mathbf{A}$.
D = L + A
D
array([[1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 2, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 2, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 1]])
The preference matrix can also be obtained by taking a part of the adjacency matrix.
R = A[0:user_num, user_num:]
R
array([[0, 1, 0, 0],
[0, 0, 1, 1],
[1, 0, 0, 0],
[0, 1, 0, 0],
[1, 0, 1, 0]])
Normalized Adjacency Matrix, Normalized Laplacian Matrix
In algorithms for recommendation systems using graph theory, the normalized matrices are used instead of the raw adjacency or Laplacian matrices.
The normalized adjacency matrix is defined as follows:
$$ \mathbf{\hat{A}}=\text{Diag}\left(\mathbf{A} \cdot \mathbf{1}\right)^{-\frac{1}{2}} \cdot \mathbf{A} \cdot \text{Diag}\left(\mathbf{1}.T \cdot \mathbf{A} \right)^{-\frac{1}{2}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}} $$
Although it looks complex, the calculation is simple using numpy.
A_hat = np.diag(np.power(np.sum(A, axis=1), -1 / 2)) @ A @ np.diag(np.power(np.sum(A, axis=0), -1 / 2))
A_hat.round(2)
array([[0. , 0. , 0. , 0. , 0. , 0. , 0.71, 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0. , 0.5 , 0.71],
[0. , 0. , 0. , 0. , 0. , 0.71, 0. , 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0. , 0.71, 0. , 0. ],
[0. , 0. , 0. , 0. , 0. , 0.5 , 0. , 0.5 , 0. ],
[0. , 0. , 0.71, 0. , 0.5 , 0. , 0. , 0. , 0. ],
[0.71, 0. , 0. , 0.71, 0. , 0. , 0. , 0. , 0. ],
[0. , 0.5 , 0. , 0. , 0.5 , 0. , 0. , 0. , 0. ],
[0. , 0.71, 0. , 0. , 0. , 0. , 0. , 0. , 0. ]])
The normalized Laplacian matrix is defined using the normalized adjacency matrix as follows:
$$ \mathbf{\hat{L}} =\mathbf{D}^{-\frac{1}{2}}\mathbf{L}\mathbf{D}^{-\frac{1}{2}}= \mathbf{I} - \mathbf{\hat{A}} $$
The normalized Laplacian matrix can also be easily calculated using numpy.
L_hat = np.eye(A_hat.shape[0]) - A_hat
L_hat.round(2)
array([[ 1. , 0. , 0. , 0. , 0. , 0. , -0.71, 0. , 0. ],
[ 0. , 1. , 0. , 0. , 0. , 0. , 0. , -0.5 , -0.71],
[ 0. , 0. , 1. , 0. , 0. , -0.71, 0. , 0. , 0. ],
[ 0. , 0. , 0. , 1. , 0. , 0. , -0.71, 0. , 0. ],
[ 0. , 0. , 0. , 0. , 1. , -0.5 , 0. , -0.5 , 0. ],
[ 0. , 0. , -0.71, 0. , -0.5 , 1. , 0. , 0. , 0. ],
[-0.71, 0. , 0. , -0.71, 0. , 0. , 1. , 0. , 0. ],
[ 0. , -0.5 , 0. , 0. , -0.5 , 0. , 0. , 1. , 0. ],
[ 0. , -0.71, 0. , 0. , 0. , 0. , 0. , 0. , 1. ]])
In recommendation systems using Graph Neural Networks (GNN) or Graph Convolutional Networks (GCN), these normalized adjacency and Laplacian matrices are used.