# On the expressive power of linear algebra on graphs

arXiv: https://arxiv.org/abs/1812.04379 · HTML: https://mlsanity.com/paper/1812.04379/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Dec 2018.

## Built on by (most cited first, 14 of 14)

- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [Expressiveness and Approximation Properties of Graph Neural Networks](https://mlsanity.com/paper/2204.04661/) (2022)
- [Equivariant Polynomials for Graph Neural Networks](https://mlsanity.com/paper/2302.11556/) (2023)
- [Spatio-Spectral Graph Neural Networks](https://mlsanity.com/paper/2405.19121/) (2024)
- [Going Deeper into Permutation-Sensitive Graph Neural Networks](https://mlsanity.com/paper/2205.14368/) (2022)
- [Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited](https://mlsanity.com/paper/2205.10914/) (2022)
- [A Characterization Theorem for Equivariant Networks with Point-wise Activations](https://mlsanity.com/paper/2401.09235/) (2024)
- [On the expressive power of message-passing neural networks as global feature map transformers](https://mlsanity.com/paper/2203.09555/) (2022)
- [State of the Art and Potentialities of Graph-level Learning](https://mlsanity.com/paper/2301.05860/) (2023)
- [Incorporating Heterophily into Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/2203.07678/) (2022)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Beyond 1-WL with Local Ego-Network Encodings](https://mlsanity.com/paper/2211.14906/) (2022)
- [Technical report: Graph Neural Networks go Grammatical](https://mlsanity.com/paper/2303.01590/) (2023)
- [Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning](https://mlsanity.com/paper/2410.01661/) (2024)

## Abstract (arXiv)

Most graph query languages are rooted in logic. By contrast, in this paper we consider graph query languages rooted in linear algebra. More specifically, we consider MATLANG, a matrix query language recently introduced, in which some basic linear algebra functionality is supported. We investigate the problem of characterising equivalence of graphs, represented by their adjacency matrices, for various fragments of MATLANG. A complete picture is painted of the impact of the linear algebra operations in MATLANG on their ability to distinguish graphs.