There is a book I would like to recommend, as it was not mentioned. The book "Graph algorithms in the language of linear algebra"[1] gives an overview and intuition of different graph algorithms expressed in linear algebra using semirings. The concept of expressing graphs as adjacency matrices (or incidence matrices) is quite old and was already noted by Koenig[4][5]. I remember the duality was used in some proofs and algorithms while doing my CS degree, e.g., see the Floyd–Warshall algorithm.
One advantage of using linear algebra, apart from the beauty of it, is that naturally, vectorization and parallelization strategies become easier to implement. In practice, sparse linear algebra is used to reduce space and computational complexity. This is done by storing the matrices in compressed formats, such as COO/CSR/ELLPack.
In HPC, there are multiple frameworks to do distributed sparse linear algebra, and also more graph and GPU focussed frameworks using semirings as the abstraction layer (CombBLAS[2], GraphBLAST[3]).
References:
[1] Kepner, Jeremy, and John Gilbert, eds. Graph algorithms in the language of linear algebra. Society for Industrial and Applied Mathematics, 2011.
[2] Buluç, Aydın, and John R. Gilbert. "The Combinatorial BLAS: Design, implementation, and applications." The International Journal of High Performance Computing Applications 25.4 (2011): 496-509.
[3] Yang, Carl, Aydın Buluç, and John D. Owens. "GraphBLAST: A high-performance linear algebra-based graph framework on the GPU." ACM Transactions on Mathematical Software (TOMS) 48.1 (2022): 1-51.
[4] D. Konig. Graphen und Matrizen (Graphs and matrices). Matematikai
Lapok, 38:116–119, 1931.
[5] D. Konig. Theorie der endlichen und unendlichen graphen (Theory of Finite and Infinite Graphs). Leipzig: Akademie Verlag M.B.H. 1936.
In HPC, there are multiple frameworks to do distributed sparse linear algebra, and also more graph and GPU focussed frameworks using semirings as the abstraction layer (CombBLAS[2], GraphBLAST[3]).
References:
[1] Kepner, Jeremy, and John Gilbert, eds. Graph algorithms in the language of linear algebra. Society for Industrial and Applied Mathematics, 2011.
[2] Buluç, Aydın, and John R. Gilbert. "The Combinatorial BLAS: Design, implementation, and applications." The International Journal of High Performance Computing Applications 25.4 (2011): 496-509.
[3] Yang, Carl, Aydın Buluç, and John D. Owens. "GraphBLAST: A high-performance linear algebra-based graph framework on the GPU." ACM Transactions on Mathematical Software (TOMS) 48.1 (2022): 1-51.
[4] D. Konig. Graphen und Matrizen (Graphs and matrices). Matematikai Lapok, 38:116–119, 1931.
[5] D. Konig. Theorie der endlichen und unendlichen graphen (Theory of Finite and Infinite Graphs). Leipzig: Akademie Verlag M.B.H. 1936.