A Comparison Study of Graph Laplacian Computation

Graphs provide a powerful and intuitive way to represent the physical world, especially when the data is defined on an irregular domain. The pairwise relationship between the nodes of the graph is described by edges and can be modeled by a matrix called an adjacency matrix or, more generally, a similarity matrix. Additionally, the graph Laplacian, derived from the similarity matrix, serves as a fundamental tool in graph signal processing. However, when the data size is large, constructing the similarity matrix and, consequently, the graph Laplacian becomes a computational burden. This paper compares three methods to construct approximations to the symmetric normalized Laplacian and reports their performance in terms of their accuracy and efficiency. We also investigate the influence of weight computation on three prototypical applications in data science: classification, clustering, and computed tomography (CT) reconstruction. Our results provide some rules of thumb for graph-based data processing applications.