Laplacian Graph Embeddings with Weighted Graphs

Question

In "A Simple Baseline Algorithm for Graph Classification" it says your graph $G$ must be "undirected and unweighted". Why must it be unweighted? Looking through the equations it is not obvious why this must be the case. Is there a workaround to allow me to use weighted adjacency matrices?

Answer 1

This question is a bit open-ended. The authors may only deal with unweighted graphs for simplicity. In an unweighted graph, the unweighted adjacency matrix $A$ is equal to the weighted adjacency matrix $W$. This allows the authors to define the symmetric normalized Laplacian matrix:

$$L=I-D^{-1/2}AD^{-1/2}.$$ where $L$ denotes the Laplacian matrix, $D$ the degree matrix, and $A$ the adjacency matrix.

Using the symmetric normalized Laplacian matrix has many advantages; see https://www.math.ucsd.edu/~fan/research/cb/ch1.pdf.

You can still use the symmetric normalized Laplacian for a weighted graph, but the eigenvalue theorems cited in the paper you linked may no longer apply.