On the expressive power of linear algebra on graphs
From MaRDI portal
Publication:2035472
Abstract: 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.
Recommendations
Cites work
- A note on compact graphs
- A note on cospectral graphs
- Algebra I. Textbook for students of mathematics. Translated from the Russian
- An introduction to the theory of graph spectra
- An optimal lower bound on the number of variables for graph identification
- Coherent algebras and the graph isomorphism problem
- Cospectral graphs and the generalized adjacency matrix
- Descriptive complexity of linear equation systems and applications to propositional proof complexity
- Dimension reduction via colour refinement
- Eigenspaces of graphs
- Elements of finite model theory.
- Enumeration of cospectral graphs.
- Expressive power of SQL.
- Finding and counting given length cycles
- Fractional isomorphism of graphs
- Graph isomorphism and theorems of Birkhoff type
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3657843 (Why is no real title available?)
- scientific article; zbMATH DE number 979011 (Why is no real title available?)
- scientific article; zbMATH DE number 1054726 (Why is no real title available?)
- scientific article; zbMATH DE number 1131873 (Why is no real title available?)
- scientific article; zbMATH DE number 2018451 (Why is no real title available?)
- scientific article; zbMATH DE number 3377258 (Why is no real title available?)
- scientific article; zbMATH DE number 3072076 (Why is no real title available?)
- scientific article; zbMATH DE number 7650984 (Why is no real title available?)
- Linear algebra done right
- Logical hierarchies in PTIME
- Logics with aggregate operators
- Lov\'asz Meets Weisfeiler and Leman
- On matrices and \(K\)-relations
- On the combinatorial power of the Weisfeiler-Lehman algorithm
- On the Descriptive Complexity of Linear Algebra
- On the expressive power of linear algebra on graphs
- On the expressive power of query languages for matrices
- On the power of combinatorial and spectral invariants
- On Weisfeiler-Leman invariance: subgraph counts and related graph properties
- PEBBLE GAMES AND LINEAR EQUATIONS
- Rank logic is dead, long live rank logic!
- Sherali-Adams relaxations and indistinguishability in counting logics
- Sherali-Adams relaxations of graph isomorphism polytopes
- Spectra of graphs
- The main eigenvalues of a graph: a survey
- The semigroup of doubly-stochastic matrices
- The spectral approach to determining the number of walks in a graph
- Unitary and orthogonal equivalence of sets of matrices
- When Can Matrix Query Languages Discern Matrices
- Which graphs are determined by their spectrum?
Cited in
(12)- Vectorization hierarchies of some graph quantifiers
- Computing linear systems on metric graphs
- Correction to: ``On the expressive power of linear algebra on graphs
- Calculational proofs in relational graphical linear algebra
- On the expressiveness of \textsc{Lara}: a proposal for unifying linear and relational algebra
- On the expressive power of message-passing neural networks as global feature map transformers
- On the expressive power of query languages for matrices
- On the expressive power of linear algebra on graphs
- MATLANG
- On matrices and K-relations
- On matrices and \(K\)-relations
- On a hierarchy of spectral isomorphism invariants
This page was built for publication: On the expressive power of linear algebra on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2035472)
