Matrix Factorization-Based Approach

Matrix factorization

We have seen that graphs are represented as matrices using a node adjacency matrix. There are other ways to represent graphs as matrices, like the LaplacianThe Laplacian matrix is a mathematical tool that describes the connections between the nodes of a graph. It is a square matrix that is derived from the adjacency matrix of the graph. or Katz similarity matrixThe Katz similarity matrix is a method that measures the similarity between pairs of nodes in a graph based on their paths and connections.. In a case where the resulting matrix is positive semidefinite (a Hermitian matrix with nonnegative eigenvalues, for example), we can do the eigenvalue decomposition to find the embedding matrix. For other matrices, we use gradient descent methods. Below is a list of algorithms that use the matrix factorization approach.

Locally linear embedding (LLE)

Here, we assume that every node in the graph is a weighted linear combination of its neighbors. Based on this assumption, the aim is to find the $K$-nearest neighbors for each node, where $K$ is a hyperparameter of the LLE algorithm. We take the weighted aggregation of the neighbors of each node and build a cost function to be minimized.