{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T09:09:46Z","timestamp":1790845786735,"version":"4.1.0"},"reference-count":72,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,10,4]],"date-time":"2020-10-04T00:00:00Z","timestamp":1601769600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,4]],"date-time":"2020-10-04T00:00:00Z","timestamp":1601769600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00224-020-09990-9","type":"journal-article","created":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T23:03:41Z","timestamp":1601766221000},"page":"179-239","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On the Expressive Power of Linear Algebra on Graphs"],"prefix":"10.1007","volume":"65","author":[{"given":"Floris","family":"Geerts","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,10,4]]},"reference":[{"issue":"3","key":"9990_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997). https:\/\/doi.org\/10.1007\/BF02523189","journal-title":"Algorithmica"},{"issue":"5","key":"9990_CR2","doi-asserted-by":"publisher","first-page":"68:1","DOI":"10.1145\/3104031","volume":"50","author":"R Angles","year":"2017","unstructured":"Angles, R., Arenas, M., Barcel\u00f3, P., Hogan, A., Reutter, J., Vrgo\u010d, D.: Foundations of modern query languages for graph databases. ACM Comput. Surv. 50(5), 68:1\u201368:40 (2017). https:\/\/doi.org\/10.1145\/3104031","journal-title":"ACM Comput. Surv."},{"key":"9990_CR3","doi-asserted-by":"crossref","unstructured":"Arvind, V., Fuhlbr\u00fcck, F., K\u00f6bler, J., Verbitsky, O.: On weisfeiler-leman invariance: Subgraph counts and related graph properties. CoRR, arXiv:1811.04801 (2018)","DOI":"10.1007\/978-3-030-25027-0_8"},{"issue":"1","key":"9990_CR4","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1137\/120867834","volume":"42","author":"A Atserias","year":"2013","unstructured":"Atserias, A., Maneva, E.N.: Sherali-Adams relaxations and indistinguishability in counting logics. SIAM J. Comput. 42(1), 112\u2013137 (2013). https:\/\/doi.org\/10.1137\/120867834","journal-title":"SIAM J. Comput."},{"key":"9990_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11080-6","volume-title":"Linear Algebra Done Right","author":"S Axler","year":"2015","unstructured":"Axler, S.: Linear Algebra Done Right, 3rd edn. Springer, Berlin, (2015). https:\/\/doi.org\/10.1007\/978-3-319-11080-6","edition":"3rd edn."},{"key":"9990_CR6","doi-asserted-by":"publisher","unstructured":"Barcel\u00f3, P.: Querying graph databases. In: Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS, pp. 175\u2013188. https:\/\/doi.org\/10.1145\/2463664.2465216 (2013)","DOI":"10.1145\/2463664.2465216"},{"key":"9990_CR7","doi-asserted-by":"publisher","unstructured":"Barcel\u00f3, P., Higuera, N., P\u0117rez, 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\u20136:20. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2020.6 (2020)","DOI":"10.4230\/LIPIcs.ICDT.2020.6"},{"key":"9990_CR8","unstructured":"Bastert, O.: Stabilization procedures and applications. PhD thesis, Technical University Munich, Germany, http:\/\/nbn-resolving.de\/urn:nbn:de:bvb:91-diss2002070500045 (2001)"},{"issue":"13","key":"9990_CR9","doi-asserted-by":"publisher","first-page":"1425","DOI":"10.14778\/3007263.3007279","volume":"9","author":"M Boehm","year":"2016","unstructured":"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\u20131436 (2016). https:\/\/doi.org\/10.14778\/3007263.3007279","journal-title":"Proc. VLDB Endowment"},{"issue":"12","key":"9990_CR10","doi-asserted-by":"publisher","first-page":"1755","DOI":"10.14778\/3229863.3229865","volume":"11","author":"M Boehm","year":"2018","unstructured":"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\u20131768 (2018). https:\/\/doi.org\/10.14778\/3229863.3229865","journal-title":"Proc. VLDB Endowment"},{"key":"9990_CR11","doi-asserted-by":"publisher","unstructured":"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\u201310:17. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2018.10 (2018)","DOI":"10.4230\/LIPIcs.ICDT.2018.10"},{"key":"9990_CR12","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1145\/3331445"},{"key":"9990_CR13","doi-asserted-by":"publisher","unstructured":"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\u201357. Springer. https:\/\/doi.org\/10.1007\/978-3-030-39951-1_3 (2020)","DOI":"10.1007\/978-3-030-39951-1_3"},{"key":"9990_CR14","doi-asserted-by":"publisher","unstructured":"Brouwer, A.E., Haemers, W.H.: Spectra of graphs universitext. Springer. https:\/\/doi.org\/10.1007\/978-1-4614-1939-6 (2012)","DOI":"10.1007\/978-1-4614-1939-6"},{"issue":"4","key":"9990_CR15","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/BF01305232","volume":"12","author":"J-Y Cai","year":"1992","unstructured":"Cai, J.-Y., F\u00fcrer, M., Immerman, N.: An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), 389\u2013410 (1992). https:\/\/doi.org\/10.1007\/BF01305232","journal-title":"Combinatorica"},{"key":"9990_CR16","doi-asserted-by":"publisher","unstructured":"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\u2013106. Kluwer Acad. Publ., Dordrecht. https:\/\/doi.org\/10.1007\/978-94-015-8937-6_3(1997)","DOI":"10.1007\/978-94-015-8937-6_3"},{"issue":"11","key":"9990_CR17","doi-asserted-by":"publisher","first-page":"1214","DOI":"10.14778\/3137628.3137633","volume":"10","author":"L Chen","year":"2017","unstructured":"Chen, L., Kumar, A., Naughton, J., Patel, J.M.: Towards linear algebra over normalized data. Proc. VLDB Endowment 10(11), 1214\u20131225 (2017). https:\/\/doi.org\/10.14778\/3137628.3137633","journal-title":"Proc. VLDB Endowment"},{"key":"9990_CR18","unstructured":"Cvetkovi\u0107, D.M.: Graphs and their spectra. Publikacije Elektrotehni\u010dkog fakulteta. Serija Matematika i fizika, 354\/356, 1\u201350. http:\/\/www.jstor.org\/stable\/43667526 (1971)"},{"key":"9990_CR19","unstructured":"Cvetkovi\u0107, D.M.: The main part of the spectrum, divisors and switching of graphs. Publ. Inst. Math. (Beograd) (N.S.), 23(37), 31\u201338. http:\/\/elib.mi.sanu.ac.rs\/files\/journals\/publ\/43\/6.pdf (1978)"},{"key":"9990_CR20","doi-asserted-by":"publisher","unstructured":"Cvetkovi\u0107, D.M., Rowlinson, P., Simi\u0107, S.: Eigenspaces of Graphs: Encyclopedia of Mathematics and its Applications. Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9781139086547 (1997)","DOI":"10.1017\/CBO9781139086547"},{"key":"9990_CR21","doi-asserted-by":"publisher","unstructured":"Cvetkovi\u0107, D.M., Rowlinson, P., Simi\u0107, S.: An Introduction to the Theory of Graph Spectra. London Mathematical Society Student Texts. Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511801518 (2009)","DOI":"10.1017\/CBO9780511801518"},{"key":"9990_CR22","doi-asserted-by":"publisher","unstructured":"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\u201325. https:\/\/doi.org\/10.1007\/978-3-540-69937-8_2 (2008)","DOI":"10.1007\/978-3-540-69937-8_2"},{"key":"9990_CR23","doi-asserted-by":"crossref","unstructured":"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\u2013122. (2009)","DOI":"10.1109\/LICS.2009.24"},{"issue":"3-4","key":"9990_CR24","doi-asserted-by":"publisher","first-page":"281","DOI":"10.3233\/FI-2017-1471","volume":"150","author":"A Dawar","year":"2017","unstructured":"Dawar, A., Holm, B.: Pebble games with algebraic rules. Fund. Inform. 150(3-4), 281\u2013316 (2017). https:\/\/doi.org\/10.3233\/FI-2017-1471","journal-title":"Fund. Inform."},{"key":"9990_CR25","doi-asserted-by":"publisher","unstructured":"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\u2013199. https:\/\/doi.org\/10.1007\/978-3-662-52921-8_12(2016)","DOI":"10.1007\/978-3-662-52921-8_12"},{"issue":"9","key":"9990_CR26","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1016\/j.apal.2019.04.005","volume":"170","author":"A Dawar","year":"2019","unstructured":"Dawar, A., Severini, S., Zapata, O.: Descriptive complexity of graph spectra. Ann. Pure Appl. Log. 170(9), 993\u20131007 (2019). https:\/\/doi.org\/10.1016\/j.apal.2019.04.005","journal-title":"Ann. Pure Appl. Log."},{"key":"9990_CR27","doi-asserted-by":"publisher","unstructured":"Dell, H., Grohe, M., Rattan, G.: Lova\u0307sz meets Weisfeiler and Lehman. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP, pp. 40:1\u201340:14. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.40 (2018)","DOI":"10.4230\/LIPIcs.ICALP.2018.40"},{"key":"9990_CR28","doi-asserted-by":"publisher","unstructured":"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\u201326. https:\/\/doi.org\/10.1007\/s00778-017-0478-1 (2017)","DOI":"10.1007\/s00778-017-0478-1"},{"issue":"4","key":"9990_CR29","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1017\/S2040618500035401","volume":"7","author":"HK Farahat","year":"1966","unstructured":"Farahat, H. K.: The semigroup of doubly-stochastic matrices. Proc. Glasgow Math. Assoc. 7 (4), 178\u2013183 (1966). https:\/\/doi.org\/10.1017\/S2040618500035401","journal-title":"Proc. Glasgow Math. Assoc."},{"issue":"1","key":"9990_CR30","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0166-218X(89)90047-4","volume":"25","author":"S Friedland","year":"1989","unstructured":"Friedland, S.: Coherent algebras and the graph isomorphism problem. Discret. Appl. Math. 25(1), 73\u201398 (1989). https:\/\/doi.org\/10.1016\/0166-218X(89)90047-4","journal-title":"Discret. Appl. Math."},{"issue":"9","key":"9990_CR31","doi-asserted-by":"publisher","first-page":"2373","DOI":"10.1016\/j.laa.2009.07.019","volume":"432","author":"M F\u00fcrer","year":"2010","unstructured":"F\u00fcrer, M.: On the power of combinatorial and spectral invariants. Linear Algebra Appl. 432(9), 2373\u20132380 (2010). https:\/\/doi.org\/10.1016\/j.laa.2009.07.019","journal-title":"Linear Algebra Appl."},{"key":"9990_CR32","doi-asserted-by":"publisher","unstructured":"F\u00fcrer, 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\u2013271. Springer (2017)","DOI":"10.1007\/978-3-319-57586-5_22"},{"key":"9990_CR33","doi-asserted-by":"publisher","unstructured":"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\u20137:19. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2019.7 (2019)","DOI":"10.4230\/LIPIcs.ICDT.2019.7"},{"key":"9990_CR34","doi-asserted-by":"publisher","unstructured":"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)","DOI":"10.4230\/LIPIcs.ICDT.2020.12"},{"key":"9990_CR35","doi-asserted-by":"publisher","unstructured":"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)","DOI":"10.1007\/978-1-4613-0163-9"},{"key":"9990_CR36","doi-asserted-by":"publisher","unstructured":"Gorodentsev, A.L.: Algebra I: Textbook for Students of Mathematics. Springer. https:\/\/doi.org\/10.1007\/978-3-319-45285-2 (2016)","DOI":"10.1007\/978-3-319-45285-2"},{"key":"9990_CR37","doi-asserted-by":"publisher","unstructured":"Gra\u0307del, E, Pakusa, W.: Rank logic is dead, long live rank logic! In: 24th EACSL Annual Conference on Computer Science Logic, CSL, pp. 390\u2013404. https:\/\/doi.org\/10.4230\/LIPIcs.CSL.2015.390 (2015)","DOI":"10.4230\/LIPIcs.CSL.2015.390"},{"key":"9990_CR38","doi-asserted-by":"publisher","unstructured":"Grohe, M., Kersting, K., Mladenov, M., Selman, E.: Dimension reduction via colour refinement. In: 22th Annual European Symposium on Algorithms, ESA, pp. 505\u2013516. https:\/\/doi.org\/10.1007\/978-3-662-44777-2_42 (2014)","DOI":"10.1007\/978-3-662-44777-2_42"},{"issue":"3","key":"9990_CR39","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1017\/jsl.2015.28","volume":"80","author":"M Grohe","year":"2015","unstructured":"Grohe, M., Otto, M.: Pebble games and linear equations. J. Symbol. Log. 80(3), 797\u2013844 (2015). https:\/\/doi.org\/10.1017\/jsl.2015.28","journal-title":"J. Symbol. Log."},{"key":"9990_CR40","doi-asserted-by":"publisher","unstructured":"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\u201312. https:\/\/doi.org\/10.1109\/LICS.2017.8005081(2017)","DOI":"10.1109\/LICS.2017.8005081"},{"issue":"2","key":"9990_CR41","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0195-6698(03)00100-8","volume":"25","author":"WH Haemers","year":"2004","unstructured":"Haemers, W.H., Spence, E.: Enumeration of cospectral graphs. Eur. J. Combin. 25(2), 199\u2013211 (2004). https:\/\/doi.org\/10.1016\/S0195-6698(03)00100-8","journal-title":"Eur. J. Combin."},{"key":"9990_CR42","doi-asserted-by":"crossref","unstructured":"Harary, F., Schwenk, A.J.: The spectral approach to determining the number of walks in a graph. Pacif. J. Math. 80(2), 443\u2013449. https:\/\/projecteuclid.org:443\/euclid.pjm\/1102785717 (1979)","DOI":"10.2140\/pjm.1979.80.443"},{"issue":"1","key":"9990_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0070","volume":"129","author":"L Hella","year":"1996","unstructured":"Hella, L.: Logical hierarchies in PTIME. Inf. Comput. 129(1), 1\u201319 (1996). https:\/\/doi.org\/10.1006\/inco.1996.0070","journal-title":"Inf. Comput."},{"issue":"4","key":"9990_CR44","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1145\/502090.502100","volume":"48","author":"Lauri Hella","year":"2001","unstructured":"Hella, L.auri, Libkin, L., Nurmonen, J., Wong, L.: Logics with aggregate operators. J. ACM 48(4), 880\u2013907 (2001). https:\/\/doi.org\/10.1145\/502090.502100","journal-title":"J. ACM"},{"key":"9990_CR45","unstructured":"Holm, B.: Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge (2010)"},{"key":"9990_CR46","doi-asserted-by":"publisher","unstructured":"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\u20132:10. https:\/\/doi.org\/10.1145\/3070607.3070608 (2017)","DOI":"10.1145\/3070607.3070608"},{"key":"9990_CR47","doi-asserted-by":"publisher","unstructured":"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\u201381. Springer (1990)","DOI":"10.1007\/978-1-4612-4478-3_5"},{"key":"9990_CR48","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/j.laa.2015.04.036","volume":"481","author":"N Jing","year":"2015","unstructured":"Jing, N.: Unitary and orthogonal equivalence of sets of matrices. Linear Algebra Appl. 481, 235\u2013242 (2015). https:\/\/doi.org\/10.1016\/j.laa.2015.04.036","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"9990_CR49","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0095-8956(80)90058-1","volume":"28","author":"CR Johnson","year":"1980","unstructured":"Johnson, C.R., Newman, M.: A note on cospectral graphs. J. Comb. Theory Ser. B 28(1), 96\u2013103 (1980). https:\/\/doi.org\/10.1016\/0095-8956(80)90058-1","journal-title":"J. Comb. Theory Ser. B"},{"key":"9990_CR50","unstructured":"Kaplansky, I.: Linear Algebra and Geometry. A Second Course. Chelsea Publishing Company (1974)"},{"key":"9990_CR51","doi-asserted-by":"crossref","unstructured":"Kersting, K., Mladenov, M., Garnett, R., Grohe, M.: Power iterated color refinement. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI\u201914, pp. 1904\u20131910. AAAI Press. https:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI14\/paper\/view\/8377 (2014)","DOI":"10.1609\/aaai.v28i1.8992"},{"key":"9990_CR52","doi-asserted-by":"publisher","unstructured":"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\u20131:4. https:\/\/doi.org\/10.1145\/2926534.2926540 (2016)","DOI":"10.1145\/2926534.2926540"},{"issue":"13","key":"9990_CR53","doi-asserted-by":"publisher","first-page":"2061","DOI":"10.14778\/3151106.3151110","volume":"10","author":"A Kunft","year":"2017","unstructured":"Kunft, A., Katsifodimos, A., Schelter, S., Rabl, T., Markl, V.: Blockjoin: Efficient matrix partitioning through joins. Proc. VLDB Endowment 10 (13), 2061\u20132072 (2017). https:\/\/doi.org\/10.14778\/3151106.3151110","journal-title":"Proc. VLDB Endowment"},{"key":"9990_CR54","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/S0304-3975(02)00736-3","volume":"296","author":"L Libkin","year":"2003","unstructured":"Libkin, L.: Expressive power of SQL. Theor. Comput. Sci. 296, 379\u2013404 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00736-3","journal-title":"Theor. Comput. Sci."},{"key":"9990_CR55","doi-asserted-by":"publisher","unstructured":"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)","DOI":"10.1007\/978-3-662-07003-1"},{"issue":"1","key":"9990_CR56","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3277006.3277013","volume":"47","author":"S Luo","year":"2018","unstructured":"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\u201331 (2018). https:\/\/doi.org\/10.1145\/3277006.3277013","journal-title":"SIGMOD Rec."},{"key":"9990_CR57","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.disopt.2014.01.004","volume":"12","author":"PN Malkin","year":"2014","unstructured":"Malkin, P.N.: Sherali\u2013Adams relaxations of graph isomorphism polytopes. Discret. Optim. 12, 73\u201397 (2014). https:\/\/doi.org\/10.1016\/j.disopt.2014.01.004","journal-title":"Discret. Optim."},{"key":"9990_CR58","unstructured":"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)"},{"key":"9990_CR59","doi-asserted-by":"publisher","unstructured":"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)","DOI":"10.1017\/9781316716878"},{"key":"9990_CR60","doi-asserted-by":"publisher","unstructured":"Pech, C.: Coherent algebras. https:\/\/doi.org\/10.13140\/2.1.2856.2248 (2002)","DOI":"10.13140\/2.1.2856.2248"},{"key":"9990_CR61","unstructured":"Perlis, S: Theory of matrices. Addison-Wesley Press, Inc, Cambridge Mass (1952)"},{"issue":"1-3","key":"9990_CR62","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0012-365X(94)90241-0","volume":"132","author":"MV Ramana","year":"1994","unstructured":"Ramana, M.V., Scheinerman, E.R., Ullman, D.: Fractional isomorphism of graphs. Discret. Math. 132(1-3), 247\u2013265 (1994). https:\/\/doi.org\/10.1016\/0012-365X(94)90241-0","journal-title":"Discret. Math."},{"key":"9990_CR63","unstructured":"Roberson, D.: Co-spectral fractional isomorphic graphs with different laplacian spectrum. MathOverflow. https:\/\/mathoverflow.net\/q\/334539"},{"key":"9990_CR64","doi-asserted-by":"crossref","unstructured":"Rowlinson, P.: The main eigenvalues of a graph: A survey. Appl. Anal. Discret. Math. 1(2), 455\u2013471. http:\/\/www.jstor.org\/stable\/43666075 (2007)","DOI":"10.2298\/AADM0702445R"},{"key":"9990_CR65","unstructured":"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)"},{"key":"9990_CR66","doi-asserted-by":"publisher","unstructured":"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\u201318. https:\/\/doi.org\/10.1145\/2882903.2882939 (2016)","DOI":"10.1145\/2882903.2882939"},{"key":"9990_CR67","unstructured":"Th\u00fcne, M.: Eigenvalues of Matrices and Graphs. PhD thesis, University of Leipzig (2012)"},{"issue":"4","key":"9990_CR68","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/BF02240204","volume":"36","author":"G Tinhofer","year":"1986","unstructured":"Tinhofer, G.: Graph isomorphism and theorems of Birkhoff type. Computing 36 (4), 285\u2013300 (1986). https:\/\/doi.org\/10.1007\/BF02240204","journal-title":"Computing"},{"issue":"2","key":"9990_CR69","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0166-218X(91)90049-3","volume":"30","author":"G Tinhofer","year":"1991","unstructured":"Tinhofer, G.: A note on compact graphs. Discret. Appl. Math. 30(2), 253\u2013264 (1991). https:\/\/doi.org\/10.1016\/0166-218X(91)90049-3","journal-title":"Discret. Appl. Math."},{"key":"9990_CR70","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/S0024-3795(03)00483-X","volume":"373","author":"ER van Dam","year":"2003","unstructured":"van Dam, E.R., Haemers, W.H.: Which graphs are determined by their spectrum? Linear Algebra Appl. 373, 241\u2013272 (2003). https:\/\/doi.org\/10.1016\/S0024-3795(03)00483-X","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"9990_CR71","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.laa.2006.07.017","volume":"423","author":"ER Van Dam","year":"2007","unstructured":"Van Dam, E.R., Haemers, W.H., Koolen, J.H.: Cospectral graphs and the generalized adjacency matrix. Linear Algebra Appl. 423(1), 33\u201341 (2007). https:\/\/doi.org\/10.1016\/j.laa.2006.07.017","journal-title":"Linear Algebra Appl."},{"key":"9990_CR72","unstructured":"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\u201316. https:\/\/www.iti.zcu.cz\/wl2018\/pdf\/wl_paper_translation.pdf (1968)"}],"updated-by":[{"DOI":"10.1007\/s00224-020-10020-x","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,1,11]],"date-time":"2021-01-11T00:00:00Z","timestamp":1610323200000}}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09990-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09990-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09990-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T02:33:51Z","timestamp":1669084431000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09990-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,4]]},"references-count":72,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["9990"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09990-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,4]]},"assertion":[{"value":"4 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2021","order":2,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published: <ExternalRef><RefSource>https:\/\/doi.org\/10.1007\/s00224-020-10020-x<\/RefSource><RefTarget Address=\"10.1007\/s00224-020-10020-x\" TargetType=\"DOI\"\/><\/ExternalRef>","order":4,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}