The Similarity Matrix of graph Laplacian Matrix has different names. What's the difference between these names?

Question

The graph Laplacian is defined:

$$L=D-W$$

Where $W$ is the Similarity Matrix of the graph and $D$ is a diagonal matrix whose entries are column sums of $W$ (or row sums, by symmetry of $W$).

$W$ has multiple names:

• the similarity matrix
• the weight matrix
• the affinity matrix
• the adjacency matrix etc.

Are these names equivalent? Or are there subtle differences in their use?

---

References:

• Graph Regularized Nonnegative Matrix Factorization for Data Representation (p.3) The $W$ is called the weight matrix.

• Co-Clustering on Manifolds (p.2) The $W$ is called the affinity matrix.

Answer 1

They're all the same. Different communities use different names. In graph theory, it's always called "adjacency matrix" in unweighted graphs, and sometimes the "weight matrix" if the graphs are weighted. "Affinity" and "similarity" are sometimes used in data science when the weights are computed using some similarity score between the points in a point cloud data set.

Answer 2

Term	Context
Adjacency matrix	Term used in graph theory when the underlying object is a graph.
Weight matrix	Term sometimes used in graph theory when they underlying object is a weighted graph.
Similarity matrix	Term generally used in machine learning when the underlying object is a collection of data points in $\mathbb{R}^n$, from which a graph representation is created using a similarity measure. This is equivalent to the adjacency matrix of this graph.
Affinity matrix	Synonym for Similarity matrix (via affinity measure as a synonym of similarity measure).