On the expressive power of linear algebra on graphs
Not on the map. Why?
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.
Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Dec 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 6; 2023: 3; 2024: 4.
14 papers.
Sort:
- 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
- 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
- 2023Equivariant Polynomials for Graph Neural Networkscited by 38
- 2024Spatio-Spectral Graph Neural Networkscited by 17
- 2022Going Deeper into Permutation-Sensitive Graph Neural Networkscited by 15
- 2024A Characterization Theorem for Equivariant Networks with Point-wise Activationscited by 9
- 2022On the expressive power of message-passing neural networks as global feature map transformerscited by 8
- 2022Weisfeiler and Leman Go Walking: Random Walk Kernels Revisitedcited by 8
- 2023State of the Art and Potentialities of Graph-level Learningcited by 6
- 2022Incorporating Heterophily into Graph Neural Networks for Graph Classificationcited by 4
- 2024Foundations and Frontiers of Graph Learning Theorycited by 3
- 2022Beyond 1-WL with Local Ego-Network Encodingscited by 2
- 2024Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning2 Oct 2024
- 2024Foundations and Frontiers of Graph Learning Theory3 Jul 2024
- 2024Spatio-Spectral Graph Neural Networks29 May 2024
- 2024A Characterization Theorem for Equivariant Networks with Point-wise Activations17 Jan 2024
- 2023Technical report: Graph Neural Networks go Grammatical2 Mar 2023
- 2023Equivariant Polynomials for Graph Neural Networks22 Feb 2023
- 2023State of the Art and Potentialities of Graph-level Learning14 Jan 2023
- 2022Beyond 1-WL with Local Ego-Network Encodings27 Nov 2022
- 2022Going Deeper into Permutation-Sensitive Graph Neural Networks28 May 2022
- 2022Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited22 May 2022
- 2022Expressiveness and Approximation Properties of Graph Neural Networks10 Apr 2022
- 2022On the expressive power of message-passing neural networks as global feature map transformers17 Mar 2022
2 more
- 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
- 2022Expressiveness and Approximation Properties of Graph Neural Networkscited by 63
- 2023Equivariant Polynomials for Graph Neural Networkscited by 38
- 2024Spatio-Spectral Graph Neural Networkscited by 17
- 2022Going Deeper into Permutation-Sensitive Graph Neural Networkscited by 15
- 2024A Characterization Theorem for Equivariant Networks with Point-wise Activationscited by 9
- 2022On the expressive power of message-passing neural networks as global feature map transformerscited by 8
- 2022Weisfeiler and Leman Go Walking: Random Walk Kernels Revisitedcited by 8
- 2023State of the Art and Potentialities of Graph-level Learningcited by 6
- 2022Incorporating Heterophily into Graph Neural Networks for Graph Classificationcited by 4
- 2024Foundations and Frontiers of Graph Learning Theorycited by 3
- 2022Beyond 1-WL with Local Ego-Network Encodingscited by 2
12 most cited of 14 All 14 (JSON)
- 2024Finding path and cycle counting formulae in graphs with Deep Reinforcement Learning2 Oct 2024
- 2024Foundations and Frontiers of Graph Learning Theory3 Jul 2024
- 2024Spatio-Spectral Graph Neural Networks29 May 2024
- 2024A Characterization Theorem for Equivariant Networks with Point-wise Activations17 Jan 2024
- 2023Technical report: Graph Neural Networks go Grammatical2 Mar 2023
- 2023Equivariant Polynomials for Graph Neural Networks22 Feb 2023
- 2023State of the Art and Potentialities of Graph-level Learning14 Jan 2023
- 2022Beyond 1-WL with Local Ego-Network Encodings27 Nov 2022
- 2022Going Deeper into Permutation-Sensitive Graph Neural Networks28 May 2022
- 2022Weisfeiler and Leman Go Walking: Random Walk Kernels Revisited22 May 2022
- 2022Expressiveness and Approximation Properties of Graph Neural Networks10 Apr 2022
- 2022On the expressive power of message-passing neural networks as global feature map transformers17 Mar 2022
12 newest of 14 All 14 (JSON)