On the Expressive Power of Linear Algebra on Graphs
- PDF / 9,629,113 Bytes
- 61 Pages / 439.642 x 666.49 pts Page_size
- 35 Downloads / 159 Views
On the Expressive Power of Linear Algebra on Graphs Floris Geerts1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract There is a long tradition in understanding graphs by investigating their adjacency matrices by means of linear algebra. Similarly, logic-based graph query languages are commonly used to explore graph properties. In this paper, we bridge these two approaches by regarding linear algebra as a graph query language. 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 the equivalence of graphs, represented by their adjacency matrices, for various fragments of MATLANG. That is, we are interested in understanding when two graphs cannot be distinguished by posing queries in MATLANG on their adjacency matrices. Surprisingly, a complete picture can be painted of the impact of each of the linear algebra operations supported in MATLANG on their ability to distinguish graphs. Interestingly, these characterisations can often be phrased in terms of spectral and combinatorial properties of graphs. Furthermore, we also establish links to logical equivalence of graphs. In particular, we 1show that MATLANG-equivalence of graphs corresponds to equivalence by means of sentences in the three-variable fragment of first-order logic with counting. Equivalence with regards to a smaller MATLANG fragment is shown to correspond to equivalence by means of sentences in the two-variable fragment of this logic. Keywords Linear algebra · Graphs · Query languages
1 Introduction Motivated by the importance of linear algebra for machine learning on big data [9, 10, 17, 58, 66] there is a current interest in languages that combine matrix operations This article belongs to the Topical Collection: Special Issue on Database Theory (ICDT 2019) Guest Editor: Pablo Bacel´o Floris Geerts
[email protected] 1
Department of Mathematics and Computer Science, University of Antwerp, Middelheimlaan 1, B-2020 Antwerp, Belgium
Theory of Computing Systems
with relational query languages in database systems [28, 46, 52, 53, 56]. Such hybrid languages raise many interesting questions from a database theoretical point of view. The Lara language is one such proposal [46] and its connections to classical database query languages has been recently explored [7]. It seems natural, however, to first consider query languages for matrices alone. These are the focus of this paper. More precisely, we continue the investigation of the expressive power of the matrix query language MATLANG, recently introduced by Brijder et al. [11, 12], as an analog for matrices of the relational algebra on relations. Intuitively, queries in MATLANG are built up by composing several linear algebra operations commonly found in linear algebra packages. When arbitrary matrices are concerned, it is known that MATLANG is subsumed by aggregate logic with only three non-numerical variables. This implies, among
Data Loading...
