Spectral graph theory

Linear signals on graphs



Placeholder for the application of classic linear systems theory applied to networks in the form of spectral graph theory, which I split off from the networks notebook, since that started to feel like algebraic graph methods, mostly. As used in graph nueral networks.

I am interested in how filters can be defined on graphs; apparently they can?

Defferrard, Bresson, and Vandergheynst (2016) is credited with introducing localized Cheybshev filtering defined in terms of graph Laplacian to the neural nets. David I. Shuman, Vandergheynst, and Frossard (2011) seems to introduce this in a signal processing setting. (see overview in D. I. Shuman et al. (2013)). Isufi et al. (2017) defines an analogue of standard linear filters. There is a helpful visual comparison of both methods in Andreas Loukas’ blog post.

Many overlaps, different phrasing: matrix factorisation.

Tooling

Laplacians.jl (Julia):

Laplacians is a package containing graph algorithms, with an emphasis on tasks related to spectral and algebraic graph theory. It contains (and will contain more) code for solving systems of linear equations in graph Laplacians, low stretch spanning trees, sparsifiation, clustering, local clustering, and optimization on graphs.

All graphs are represented by sparse adjacency matrices. This is both for speed, and because our main concerns are algebraic tasks. It does not handle dynamic graphs. It would be very slow to implement dynamic graphs this way.

Much more tooling under graph neural networks.

References

Belkin, Mikhail, and Partha Niyogi. 2003. “Laplacian Eigenmaps for Dimensionality Reduction and Data Representation.” Neural Computation 15 (6): 1373–96. https://doi.org/10.1162/089976603321780317.
Butler, Steve, and Fan Chung. 2013. “Spectral Graph Theory.” In Handbook of Linear Algebra, 13. https://orion.math.iastate.edu/butler/papers/14_08_survey.pdf.
Chung, Fan R. K., and Fan Chung Graham. 1997. Spectral Graph Theory. American Mathematical Soc.
Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. 2016. “Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering.” In Advances In Neural Information Processing Systems. http://arxiv.org/abs/1606.09375.
Diaconis, Persi, and Daniel Stroock. 1991. “Geometric Bounds for Eigenvalues of Markov Chains.” The Annals of Applied Probability 1 (1): 36–61. https://doi.org/10.1214/aoap/1177005980.
Ding, C., X. He, and H. Simon. 2005. “On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering.” In Proceedings of the 2005 SIAM International Conference on Data Mining, 606–10. Proceedings. Society for Industrial and Applied Mathematics. http://ranger.uta.edu/~chqding/papers/NMF-SDM2005.pdf.
Hogben, Leslie, ed. 2014. Handbook of Linear Algebra. Second edition. Discrete Mathematics and Its Applications. Boca Raton, Florida: CRC Press/Taylor & Francis Group.
Isufi, Elvin, Andreas Loukas, Andrea Simonetto, and Geert Leus. 2017. “Autoregressive Moving Average Graph Filtering.” IEEE Transactions on Signal Processing 65 (2): 274–88. https://doi.org/10.1109/TSP.2016.2614793.
Kipf, Thomas N., and Max Welling. 2016. “Semi-Supervised Classification with Graph Convolutional Networks.” In arXiv:1609.02907 [Cs, Stat]. http://arxiv.org/abs/1609.02907.
Luxburg, Ulrike von. 2007. “A Tutorial on Spectral Clustering.”
Mahoney, Michael W. 2016. “Lecture Notes on Spectral Graph Methods.” arXiv Preprint arXiv:1608.04845. http://arxiv.org/abs/1608.04845.
Newman, M. E. J. 2006. “Modularity and Community Structure in Networks.” Proceedings of the National Academy of Sciences 103 (23): 8577–82. https://doi.org/10.1073/pnas.0601602103.
Shuman, D. I., S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. 2013. “The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains.” IEEE Signal Processing Magazine 30 (3): 83–98. https://doi.org/10.1109/MSP.2012.2235192.
Shuman, David I., Pierre Vandergheynst, and Pascal Frossard. 2011. “Chebyshev Polynomial Approximation for Distributed Signal Processing.” 2011 International Conference on Distributed Computing in Sensor Systems and Workshops (DCOSS), June, 1–8. https://doi.org/10.1109/DCOSS.2011.5982158.
Solé-Ribalta, A., M. De Domenico, N. E. Kouvaris, A. Díaz-Guilera, S. Gómez, and A. Arenas. 2013. “Spectral Properties of the Laplacian of Multiplex Networks.” Physical Review E 88 (3): 032807. https://doi.org/10.1103/PhysRevE.88.032807.
Spielman, Daniel A., and Shang-Hua Teng. 2008a. “Spectral Sparsification of Graphs.” arXiv:0808.4134 [Cs], August. http://arxiv.org/abs/0808.4134.
———. 2008b. “A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly-Linear Time Graph Partitioning.” arXiv:0809.3232 [Cs], September. http://arxiv.org/abs/0809.3232.
Xia, Feng, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, and Huan Liu. 2021. “Graph Learning: A Survey.” IEEE Transactions on Artificial Intelligence 2 (2): 109–27. https://doi.org/10.1109/TAI.2021.3076021.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.