On the Expressive Power of Linear Algebra on Graphs
Tóm tắt
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 show 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.
Tài liệu tham khảo
Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209–223 (1997). https://doi.org/10.1007/BF02523189
Angles, R., Arenas, M., Barceló, P., Hogan, A., Reutter, J., Vrgoč, D.: Foundations of modern query languages for graph databases. ACM Comput. Surv. 50(5), 68:1–68:40 (2017). https://doi.org/10.1145/3104031
Arvind, V., Fuhlbrück, F., Köbler, J., Verbitsky, O.: On weisfeiler-leman invariance: Subgraph counts and related graph properties. CoRR, arXiv:1811.04801 (2018)
Atserias, A., Maneva, E.N.: Sherali-Adams relaxations and indistinguishability in counting logics. SIAM J. Comput. 42(1), 112–137 (2013). https://doi.org/10.1137/120867834
Axler, S.: Linear Algebra Done Right, 3rd edn. Springer, Berlin, (2015). https://doi.org/10.1007/978-3-319-11080-6
Barceló, P.: Querying graph databases. In: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pp. 175–188. https://doi.org/10.1145/2463664.2465216 (2013)
Barceló, P., Higuera, N., Pėrez, J., Subercaseaux, B.: On the expressiveness of LARA: A unified language for linear and relational algebra. In: proceedings of the 23rd International Conference on Database Theory, ICDT, pp. 6:1–6:20. https://doi.org/10.4230/LIPIcs.ICDT.2020.6 (2020)
Bastert, O.: Stabilization procedures and applications. PhD thesis, Technical University Munich, Germany, http://nbn-resolving.de/urn:nbn:de:bvb:91-diss2002070500045 (2001)
Boehm, M., Dusenberry, M.W., Eriksson, D., Evfimievski, A.V., Manshadi, F.M., Pansare, N., Reinwald, B., Reiss, F.R., Sen, P., Surve, A.C., Shirsih, T.: SystemML: Declarative machine learning on Spark. Proc. VLDB Endowment 9(13), 1425–1436 (2016). https://doi.org/10.14778/3007263.3007279
Boehm, M., Reinwald, B., Hutchison, D., Sen, P., Evfimievski, A.V., Pansare, N.: On optimizing operator fusion plans for large-scale machine learning in SystemML. Proc. VLDB Endowment 11(12), 1755–1768 (2018). https://doi.org/10.14778/3229863.3229865
Brijder, R., Geerts, F., den Bussche, J.V., Weerwag, T.: On the expressive power of query languages for matrices. In: 21st International Conference on Database Theory, ICDT, 10:1–10:17. https://doi.org/10.4230/LIPIcs.ICDT.2018.10 (2018)
Brijder, R., Geerts, F., den Bussche, J.V., Weerwag, T.: On the expressive power of query languages for matrices. ACM Trans on Database Systems. To appear (2019)
Brijder, R., Gyssens, M., den Bussche, J.V.: On matrices and K-relations. In: Proceedings of the 11th International Symposium on Foundations of Information and Knowledge Systems, FoIKS, volume 12012 of Lecture Notes in Computer Science, pp. 42–57. Springer. https://doi.org/10.1007/978-3-030-39951-1_3 (2020)
Brouwer, A.E., Haemers, W.H.: Spectra of graphs universitext. Springer. https://doi.org/10.1007/978-1-4614-1939-6 (2012)
Cai, J.-Y., Fürer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), 389–410 (1992). https://doi.org/10.1007/BF01305232
Chan, A., Godsil, C.D.: Symmetry and eigenvectors. In: Graph symmetry (Montreal, PQ, 1996), volume 497 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pp. 75–106. Kluwer Acad. Publ., Dordrecht. https://doi.org/10.1007/978-94-015-8937-6_3(1997)
Chen, L., Kumar, A., Naughton, J., Patel, J.M.: Towards linear algebra over normalized data. Proc. VLDB Endowment 10(11), 1214–1225 (2017). https://doi.org/10.14778/3137628.3137633
Cvetković, D.M.: Graphs and their spectra. Publikacije Elektrotehničkog fakulteta. Serija Matematika i fizika, 354/356, 1–50. http://www.jstor.org/stable/43667526 (1971)
Cvetković, D.M.: The main part of the spectrum, divisors and switching of graphs. Publ. Inst. Math. (Beograd) (N.S.), 23(37), 31–38. http://elib.mi.sanu.ac.rs/files/journals/publ/43/6.pdf (1978)
Cvetković, D.M., Rowlinson, P., Simić, S.: Eigenspaces of Graphs: Encyclopedia of Mathematics and its Applications. Cambridge University Press. https://doi.org/10.1017/CBO9781139086547 (1997)
Cvetković, D.M., Rowlinson, P., Simić, S.: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts. Cambridge University Press. https://doi.org/10.1017/CBO9780511801518 (2009)
Dawar, A.: On the descriptive complexity of linear algebra. In: Proceedings of the 15th International Workshop on Logic, Language, Information and Computation, WoLLIC, pp. 17–25. https://doi.org/10.1007/978-3-540-69937-8_2 (2008)
Dawar, A., Grohe, M., Holm, B., Laubner, B.: Logics with rank operators. In: Proceedings of the 24th Annual IEEE Symposium on Logic In Computer Science, LICS, pp. 113–122. (2009)
Dawar, A., Holm, B.: Pebble games with algebraic rules. Fund. Inform. 150(3-4), 281–316 (2017). https://doi.org/10.3233/FI-2017-1471
Dawar, A., Severini, S., Zapata, O.: Descriptive complexity of graph spectra. In: Proceedings of the 23rd International Workshop on Logic, Language, Information and Computation, WoLLIC, pp. 183–199. https://doi.org/10.1007/978-3-662-52921-8_12(2016)
Dawar, A., Severini, S., Zapata, O.: Descriptive complexity of graph spectra. Ann. Pure Appl. Log. 170(9), 993–1007 (2019). https://doi.org/10.1016/j.apal.2019.04.005
Dell, H., Grohe, M., Rattan, G.: Lovȧsz meets Weisfeiler and Lehman. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 40:1–40:14. https://doi.org/10.4230/LIPIcs.ICALP.2018.40 (2018)
Elgohary, A., Boehm, M., Haas, P.J.: Frederick R. Reiss, and Berthold Reinwald. Compressed linear algebra for large-scale machine learning. The VLDB Journal, 1–26. https://doi.org/10.1007/s00778-017-0478-1 (2017)
Farahat, H. K.: The semigroup of doubly-stochastic matrices. Proc. Glasgow Math. Assoc. 7 (4), 178–183 (1966). https://doi.org/10.1017/S2040618500035401
Friedland, S.: Coherent algebras and the graph isomorphism problem. Discret. Appl. Math. 25(1), 73–98 (1989). https://doi.org/10.1016/0166-218X(89)90047-4
Fürer, M.: On the power of combinatorial and spectral invariants. Linear Algebra Appl. 432(9), 2373–2380 (2010). https://doi.org/10.1016/j.laa.2009.07.019
Fürer, M., Paschos, V.Th.: On the combinatorial power of the Weisfeiler-Lehman algorithm. In: Pagourtzis, A. (ed.) Algorithms and Complexity. https://doi.org/10.1007/978-3-319-57586-5_22, pp 260–271. Springer (2017)
Geerts, F.: On the expressive power of linear algebra on graphs. In: Proceedings of the 22nd International Conference on Database Theory, ICDT, pp. 7:1–7:19. https://doi.org/10.4230/LIPIcs.ICDT.2019.7 (2019)
Geerts, F.: When can matrix query languages discern matrices? In: Proceedings of the 23nd International Conference on Database Theory ICDT. https://doi.org/10.4230/LIPIcs.ICDT.2020.12 (2020)
Godsil, C., Royle, G.F.: Algebraic Graph Theory volume 207 of Graduate Texts in Mathematics. Springer. https://doi.org/10.1007/978-1-4613-0163-9 (2001)
Gorodentsev, A.L.: Algebra I: Textbook for Students of Mathematics. Springer. https://doi.org/10.1007/978-3-319-45285-2 (2016)
Grȧdel, E, Pakusa, W.: Rank logic is dead, long live rank logic! In: 24th EACSL Annual Conference on Computer Science Logic, CSL, pp. 390–404. https://doi.org/10.4230/LIPIcs.CSL.2015.390 (2015)
Grohe, M., Kersting, K., Mladenov, M., Selman, E.: Dimension reduction via colour refinement. In: 22th Annual European Symposium on Algorithms, ESA, pp. 505–516. https://doi.org/10.1007/978-3-662-44777-2_42 (2014)
Grohe, M., Otto, M.: Pebble games and linear equations. J. Symbol. Log. 80(3), 797–844 (2015). https://doi.org/10.1017/jsl.2015.28
Grohe, M., Pakusa, W.: Descriptive complexity of linear equation systems and applications to propositional proof complexity. In: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS, 1–12. https://doi.org/10.1109/LICS.2017.8005081(2017)
Haemers, W.H., Spence, E.: Enumeration of cospectral graphs. Eur. J. Combin. 25(2), 199–211 (2004). https://doi.org/10.1016/S0195-6698(03)00100-8
Harary, F., Schwenk, A.J.: The spectral approach to determining the number of walks in a graph. Pacif. J. Math. 80(2), 443–449. https://projecteuclid.org:443/euclid.pjm/1102785717 (1979)
Hella, L.: Logical hierarchies in PTIME. Inf. Comput. 129(1), 1–19 (1996). https://doi.org/10.1006/inco.1996.0070
Hella, L.auri, Libkin, L., Nurmonen, J., Wong, L.: Logics with aggregate operators. J. ACM 48(4), 880–907 (2001). https://doi.org/10.1145/502090.502100
Holm, B.: Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge (2010)
Hutchison, D., Howe, B., Suciu, D.: LaraDB: A minimalist kernel for linear and relational algebra computation. In: Proceedings of the 4th ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, BeyondMR, pp. 2:1–2:10. https://doi.org/10.1145/3070607.3070608 (2017)
Immerman, N., Lander, E.: Describing graphs: A first-order approach to graph canonization. In: Selman, A.L. (ed.) Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday. https://doi.org/10.1007/978-1-4612-4478-3_5, pp 59–81. Springer (1990)
Jing, N.: Unitary and orthogonal equivalence of sets of matrices. Linear Algebra Appl. 481, 235–242 (2015). https://doi.org/10.1016/j.laa.2015.04.036
Johnson, C.R., Newman, M.: A note on cospectral graphs. J. Comb. Theory Ser. B 28(1), 96–103 (1980). https://doi.org/10.1016/0095-8956(80)90058-1
Kaplansky, I.: Linear Algebra and Geometry. A Second Course. Chelsea Publishing Company (1974)
Kersting, K., Mladenov, M., Garnett, R., Grohe, M.: Power iterated color refinement. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI’14, pp. 1904–1910. AAAI Press. https://www.aaai.org/ocs/index.php/AAAI/AAAI14/paper/view/8377 (2014)
Kunft, A., Alexandrov, A., Katsifodimos, A., Markl, V.: Bridging the gap Towards optimization across linear and relational algebra. In: Proceedings of the 3rd ACM SIGMOD Workshop on Algorithms and Systems for MapReduce and Beyond, BeyondMR, pp. 1:1–1:4. https://doi.org/10.1145/2926534.2926540 (2016)
Kunft, A., Katsifodimos, A., Schelter, S., Rabl, T., Markl, V.: Blockjoin: Efficient matrix partitioning through joins. Proc. VLDB Endowment 10 (13), 2061–2072 (2017). https://doi.org/10.14778/3151106.3151110
Libkin, L.: Expressive power of SQL. Theor. Comput. Sci. 296, 379–404 (2003). https://doi.org/10.1016/S0304-3975(02)00736-3
Libkin, L.: Elements of Finite Model Theory. Texts in Theoretical Computer Science: An EATCS series. Springer. https://doi.org/10.1007/978-3-662-07003-1 (2004)
Luo, S., Gao, Z.J., Gubanov, M., Perez, L.L., Jermaine, C.: Scalable linear algebra on a relational database system. SIGMOD Rec. 47(1), 24–31 (2018). https://doi.org/10.1145/3277006.3277013
Malkin, P.N.: Sherali–Adams relaxations of graph isomorphism polytopes. Discret. Optim. 12, 73–97 (2014). https://doi.org/10.1016/j.disopt.2014.01.004
Ngo, H.Q., Nguyen, X., Olteanu, D., Schleich, M.: In-database factorized learning. In: Proceedings of the 11th Alberto Mendelzon International Workshop on Foundations of Data Management and the Web, AMW. http://ceur-ws.org/Vol-1912/paper21.pdf (2017)
Otto, M.: Bounded Variable Logics and Counting: A Study in Finite Models, volume 9 of Lecture Notes in Logic. Springer. https://doi.org/10.1017/9781316716878(1997)
Pech, C.: Coherent algebras. https://doi.org/10.13140/2.1.2856.2248 (2002)
Perlis, S: Theory of matrices. Addison-Wesley Press, Inc, Cambridge Mass (1952)
Ramana, M.V., Scheinerman, E.R., Ullman, D.: Fractional isomorphism of graphs. Discret. Math. 132(1-3), 247–265 (1994). https://doi.org/10.1016/0012-365X(94)90241-0
Roberson, D.: Co-spectral fractional isomorphic graphs with different laplacian spectrum. MathOverflow. https://mathoverflow.net/q/334539
Rowlinson, P.: The main eigenvalues of a graph: A survey. Appl. Anal. Discret. Math. 1(2), 455–471. http://www.jstor.org/stable/43666075 (2007)
Scheinerman, E.R., Ullman, D.H.: Fractional Graph Theory: a Rational Approach to the Theory of Graphs. Wiley. https://www.ams.jhu.edu/ers/wp-content/uploads/sites/2/2015/12/fgt.pdf (1997)
Schleich, M., Olteanu, D., Ciucanu, R: Learning linear regression models over factorized joins. In: Proceedings of the 2016 International Conference on Management of Data, SIGMOD, pp. 3–18. https://doi.org/10.1145/2882903.2882939 (2016)
Thüne, M.: Eigenvalues of Matrices and Graphs. PhD thesis, University of Leipzig (2012)
Tinhofer, G.: Graph isomorphism and theorems of Birkhoff type. Computing 36 (4), 285–300 (1986). https://doi.org/10.1007/BF02240204
Tinhofer, G.: A note on compact graphs. Discret. Appl. Math. 30(2), 253–264 (1991). https://doi.org/10.1016/0166-218X(91)90049-3
van Dam, E.R., Haemers, W.H.: Which graphs are determined by their spectrum? Linear Algebra Appl. 373, 241–272 (2003). https://doi.org/10.1016/S0024-3795(03)00483-X
Van Dam, E.R., Haemers, W.H., Koolen, J.H.: Cospectral graphs and the generalized adjacency matrix. Linear Algebra Appl. 423(1), 33–41 (2007). https://doi.org/10.1016/j.laa.2006.07.017
Weisfeiler, B.J., Lehman, A.A.: A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Tech.Inform. 2(9), 12–16. https://www.iti.zcu.cz/wl2018/pdf/wl_paper_translation.pdf (1968)