pith. sign in

arxiv: 2604.12584 · v1 · submitted 2026-04-14 · 💻 cs.DS · cs.DM

Robust Graph Isomorphism, Quadratic Assignment and VC Dimension

Anatole Dahan , Martin Grohe , Daniel Neuen , Tom\'a\v{s} Novotn\'y This is my paper

Pith reviewed 2026-05-10 14:24 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords graph edit distanceVC dimensionquadratic assignmentWeisfeiler-Lemanapproximation algorithmsgraph isomorphismrobust testing
0
0 comments X

The pith

VC-bounded graphs allow additive εn² approximation to graph edit distance in time n to the O(d/ε²).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes approximation algorithms for graph edit distance and quadratic assignment that run in time whose exponent depends on the VC-dimension d of the input rather than on log n. This produces an additive εn² guarantee for GED on n-vertex graphs of VC-dimension d in time n^{O(d/ε²)}, recovering earlier results as the special case d = O(log n). The same machinery yields a low-dimensional Weisfeiler-Leman test for the robust isomorphism problem in which non-isomorphic pairs are promised to be at least εn² apart in edit distance.

Core claim

We present an additive εn²-approximation algorithm for the Graph Edit Distance problem on graphs of VC dimension d running in time n^{O(d/ε²)}. Similar techniques give an εn²-approximation for quadratic assignment problems with a suitable VC-dimension notion in time n^{O(ε^{-2}(d + log ε^{-1}))}. For the ε-GI problem of distinguishing isomorphic graphs from those at edit distance at least εn², the Weisfeiler-Leman algorithm with dimension O(ε^{-1}d log(ε^{-1})) suffices on VC-dimension d graphs, while dimension O(ε^{-1} log n) works for arbitrary graphs.

What carries the argument

The VC-dimension of graphs or QAP instances, which bounds the diversity of neighborhoods inducible by vertex subsets and thereby controls the search space for near-optimal alignments.

Load-bearing premise

The input graphs or QAP instances have bounded VC-dimension d.

What would settle it

A pair of VC-dimension-d graphs at edit distance at least εn² that the Weisfeiler-Leman algorithm of dimension O(ε^{-1} d log(ε^{-1})) fails to distinguish would disprove the robust isomorphism claim.

read the original abstract

We present an additive $\varepsilon n^{2}$-approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension $d$ running in time $n^{O(d/\varepsilon^{2})}$. In particular, this recovers a previous result by Arora, Frieze, and Kaplan [Math. Program. 2002] who gave an $\varepsilon n^{2}$-approximation running in time $n^{O(\log n/\varepsilon^{2})}$. Similar to the work of Arora et al., we extend our results to arbitrary Quadratic Assignment problems (QAPs) by introducing a notion of VC dimension for QAP instances, and giving an $\varepsilon n^{2}$-approximation for QAPs with bounded weights running in time $n^{O(\varepsilon^{-2}(d + \log\varepsilon^{-1}))}$. As a particularly interesting special case, we further study the problem $\varepsilon$-$\mathsf{GI}$, which entails determining if two graphs $G,H$ over $n$ vertices are isomorphic, when promised that if they are not, their graph edit distance is at least $\varepsilon n^{2}$. We show that the standard Weisfeiler--Leman algorithm of dimension $O(\varepsilon^{-1}d\log(\varepsilon^{-1}))$ solves this problem on graphs of VC dimension $d$. We also show that dimension $O(\varepsilon^{-1}\log n)$ suffices on arbitrary $n$-vertex graphs, while $k$-WL fails on instances at distance $\Omega(n^{2}/k)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper presents an additive εn²-approximation algorithm for the Graph Edit Distance (GED) problem on n-vertex graphs of VC-dimension d, running in time n^{O(d/ε²)}. It recovers the Arora-Frieze-Kaplan result as the special case d=Θ(log n). The authors extend the approach to Quadratic Assignment Problems (QAPs) by defining an analogous VC-dimension parameter for QAP instances and obtain an εn²-approximation for bounded-weight QAPs in time n^{O(ε^{-2}(d + log ε^{-1}))}. As a special case they study the ε-GI promise problem and prove that the Weisfeiler-Leman algorithm of dimension O(ε^{-1}d log(ε^{-1})) solves it on VC-dimension-d graphs, while dimension O(ε^{-1} log n) suffices for arbitrary graphs and k-WL fails on instances at distance Ω(n²/k).

Significance. If the claimed runtime and approximation guarantees hold, the work improves the state of the art for structured instances of GED and QAP by replacing the log n factor with the (potentially much smaller) VC-dimension d. The ε-GI results give matching upper and lower bounds on the Weisfeiler-Leman dimension needed for robust isomorphism testing, directly relating combinatorial dimension to algorithmic complexity. The manuscript ships explicit algorithmic reductions to the Arora et al. framework together with new VC-dimension arguments for both graphs and QAPs.

major comments (2)
  1. [§3] §3 (or the section containing the main GED algorithm): the reduction from bounded-VC-dimension GED to the Arora-Frieze-Kaplan framework appears to rely on a sampling argument whose sample size is stated as O(d/ε²); a concrete bound on the failure probability and on how the VC-dimension controls the shattering of the sampled edit sets is needed to confirm that the overall runtime remains n^{O(d/ε²)} rather than incurring an extra log n factor.
  2. [QAP section] Definition of VC-dimension for QAP instances (the paragraph immediately preceding the QAP theorem): the definition is given only for bounded-weight instances; it is unclear whether the same parameter controls the approximation when weights are unbounded, and whether the stated runtime n^{O(ε^{-2}(d + log ε^{-1}))} continues to hold without the bounded-weight hypothesis.
minor comments (2)
  1. [ε-GI section] The statement of the ε-GI result for arbitrary graphs claims dimension O(ε^{-1} log n) suffices; the proof sketch should explicitly cite which theorem of Arora et al. is invoked and how the log n term arises from the general-case VC-dimension bound.
  2. [Throughout] Notation: the symbol d is overloaded for both graph VC-dimension and the QAP parameter; a brief remark distinguishing the two (or a subscript) would prevent confusion when the two results are read together.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and the recommendation of minor revision. We are pleased that the significance of the results on approximating GED and QAP for low VC-dimension instances, as well as the connections to Weisfeiler-Leman dimension, is recognized. We address the major comments below.

read point-by-point responses

  1. Referee: [§3] §3 (or the section containing the main GED algorithm): the reduction from bounded-VC-dimension GED to the Arora-Frieze-Kaplan framework appears to rely on a sampling argument whose sample size is stated as O(d/ε²); a concrete bound on the failure probability and on how the VC-dimension controls the shattering of the sampled edit sets is needed to confirm that the overall runtime remains n^{O(d/ε²)} rather than incurring an extra log n factor.

    Authors: We appreciate this observation. The sampling argument in Section 3 relies on the fact that the class of possible edit sets has VC-dimension at most d. By the standard uniform convergence bounds for VC-classes, a sample of size O(d/ε²) suffices to ensure that the empirical edit distance approximates the true value within additive ε n² with constant probability (at least 2/3), independently of n. There is no need for a failure probability that decreases with n, as the algorithm is Monte Carlo and a constant success probability is acceptable; repetitions to boost the probability incur only a polynomial factor in n, which is absorbed into the n^{O(d/ε²)} runtime bound. We will add this explicit reference to the VC uniform convergence theorem and the constant-probability analysis in the revised version to make the argument fully rigorous. revision: yes

  2. Referee: [QAP section] Definition of VC-dimension for QAP instances (the paragraph immediately preceding the QAP theorem): the definition is given only for bounded-weight instances; it is unclear whether the same parameter controls the approximation when weights are unbounded, and whether the stated runtime n^{O(ε^{-2}(d + log ε^{-1}))} continues to hold without the bounded-weight hypothesis.

    Authors: The VC-dimension for QAP instances is defined specifically for bounded-weight instances, as the subsequent theorem and runtime bound are stated under the bounded-weight hypothesis. For unbounded weights, the discretization step in the reduction does not apply directly, and the approximation may not hold with the same guarantees. We will revise the paragraph to explicitly state that the definition and results apply to bounded-weight QAPs, and add a remark clarifying that the bounded-weight assumption is necessary for our current techniques. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The central results—an εn²-approximation for GED/QAP on VC-dimension-d graphs in time n^{O(d/ε²)}, plus WL-dimension bounds for ε-GI—build directly on the external Arora-Frieze-Kaplan algorithm and the standard Weisfeiler-Leman procedure. The VC-dimension parameter d enters the runtime as an explicit input hypothesis rather than a fitted or self-defined quantity. No equations reduce a claimed prediction to a prior fit by construction, no uniqueness theorem is imported from the authors' own prior work, and no ansatz is smuggled via self-citation. The abstract recovers the d=Θ(log n) case as a special instance of the new bound, confirming the argument is non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review based on abstract only; full technical details unavailable. The central claims rest on the assumption that inputs have bounded VC-dimension and on the correctness of the Weisfeiler-Leman procedure.

axioms (1)
  • domain assumption Input graphs or QAP instances have bounded VC-dimension d
    Invoked to obtain the improved runtime; without it the algorithm reverts to slower bounds.

pith-pipeline@v0.9.0 · 5598 in / 1330 out tokens · 43836 ms · 2026-05-10T14:24:21.050287+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    A new rounding procedure for the assign- ment problem with applications to dense graph arrangement problems

    Sanjeev Arora, Alan Frieze, and Haim Kaplan. “A new rounding procedure for the assign- ment problem with applications to dense graph arrangement problems”. In:Mathematical Programming92.1 (2002), pp. 1–36.doi:10.1007/s101070100271

    work page doi:10.1007/s101070100271 2002

  2. [2]

    Approximate Graph Isomorphism

    Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Yadu Vasudev. “Approximate Graph Isomorphism”. In:Mathematical Foundations of Computer Science 2012 - 37th In- ternational Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings. Ed. by Branislav Rovan, Vladimiro Sassone, and Peter Widmayer. Vol. 7464. Lecture Notes in Computer ...

    work page doi:10.1007/978-3-642-32589-2_12 2012

  3. [3]

    Sherali-Adams Relaxations and Indistinguishability in Counting Logics

    Albert Atserias and Elitza N. Maneva. “Sherali-Adams Relaxations and Indistinguishability in Counting Logics”. In:SIAM J. Comput.42.1 (2013), pp. 112–137.doi: 10 . 1137 / 120867834

    work page 2013

  4. [4]

    Semidefinite Progr ams on Sparse Random Graphs and /T_heir Application to Community Detection

    László Babai. “Graph isomorphism in quasipolynomial time [extended abstract]”. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. Ed. by Daniel Wichs and Yishay Mansour. 2016, pp. 684–697.doi:10.1145/2897518.2897542

    work page doi:10.1145/2897518.2897542 2016

  5. [5]

    Twin-width I: tractable FO model checking

    Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. “Twin-width I: Tractable FO Model Checking”. In:J. ACM69.1 (2022), 3:1–3:46.doi:10.1145/3486655. 18

    work page doi:10.1145/3486655 2022

  6. [6]

    An optimal lower bound on the number of variables for graph identification

    Jin-yi Cai, Martin Fürer, and Neil Immerman. “An optimal lower bound on the number of variables for graph identification”. In:Comb.12.4 (1992), pp. 389–410.doi:10.1007/ BF01305232

    work page 1992

  7. [7]

    Tight pair query lower bounds for matching and earth mover’s distance

    Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng. “Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension”. In:66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025. IEEE, 2025, pp. 2728–2765.doi:10.1109/FO...

    work page doi:10.1109/focs63196.2025.00140 2025

  8. [8]

    Upper bounds to the clique width of graphs

    Bruno Courcelle and Stephan Olariu. “Upper bounds to the clique width of graphs”. In: Discret. Appl. Math.101.1-3 (2000), pp. 77–114.doi:10.1016/S0166-218X(99)00184-5

    work page doi:10.1016/s0166-218x(99)00184-5 2000

  9. [9]

    Lovász Meets Weisfeiler and Leman

    Holger Dell, Martin Grohe, and Gaurav Rattan. “Lovász Meets Weisfeiler and Leman”. In:45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13, 2018. Ed. by Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella. LIPIcs. Schloss Dagstuhl - Leibniz- Zentrum für Informatik, ...

    work page doi:10.4230/lipics.icalp.2018.40 2018

  10. [10]

    Reinhard Diestel.Graph theory. 6th. Vol. 173. Graduate Texts in Mathematics. Springer, Berlin, 2025, pp. xx+454.doi:10.1007/978-3-662-70107-2

    work page doi:10.1007/978-3-662-70107-2 2025

  11. [11]

    First-Order Model Checking on Monadically Stable Graph Classes

    Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, and Szymon Torunczyk. “First-Order Model Checking on Monadically Stable Graph Classes”. In:65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024. IEEE, 2024, pp. 21–30.doi:10.1109/FOCS61266. 2024.00012

    work page doi:10.1109/focs61266 2024

  12. [12]

    How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs , booktitle =

    Jan Dreier and Szymon Torunczyk. “Merge-Width and First-Order Model Checking”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025. Ed. by Michal Koucký and Nikhil Bansal. ACM, 2025, pp. 1944–1955.doi:10.1145/3717823.3718259

    work page doi:10.1145/3717823.3718259 2025

  13. [13]

    Diameter, Eccentricities and Distance Oracle Computations onH-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik-Chervonenkis Dimension

    Guillaume Ducoffe, Michel Habib, and Laurent Viennot. “Diameter, Eccentricities and Distance Oracle Computations onH-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik-Chervonenkis Dimension”. In:SIAM J. Comput.51.5 (2022), pp. 1506–1534.doi: 10.1137/20M136551X

    work page doi:10.1137/20m136551x 2022

  14. [14]

    Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs

    Lech Duraj, Filip Konieczny, and Krzysztof Potepa. “Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs”. In:32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024. Ed. by Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman. Vol. 308. LIPI...

    work page doi:10.4230/lipics.esa.2024.51 2024

  15. [15]

    On recognizing graphs by numbers of homomorphisms

    Zdeněk Dvořák. “On recognizing graphs by numbers of homomorphisms”. In:J. Graph Theory64.4 (2010), pp. 330–342.doi:10.1002/JGT.20461

    work page doi:10.1002/jgt.20461 2010

  16. [16]

    Graph Similarity Based on Matrix Norms

    Timo Gervens and Martin Grohe. “Graph Similarity Based on Matrix Norms”. In:47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022, Vienna, Austria, August 22-26, 2022. Ed. by Stefan Szeider, Robert Ganian, and Alexandra Silva. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 52:1–52:15.doi: 10.4230/LIPIcs....

    work page doi:10.4230/lipics.mfcs.2022.52 2022

  17. [17]

    Goodman, Joseph O’Rourke, and Csaba D

    Jacob E. Goodman, Joseph O’Rourke, and Csaba D. Tóth, eds.Handbook of Discrete and Computational Geometry. 3rd ed. Discrete Mathematics and Its Applications. Third Edition, xxix + 1927 pages. Boca Raton, FL: CRC Press / Chapman & Hall, 2017.isbn: 978-1-4987-1139-5. 19

    work page 1927

  18. [18]

    Recent advances on the graph isomorphism problem

    Martin Grohe and Daniel Neuen. “Recent advances on the graph isomorphism problem”. In:Surveys in Combinatorics 2021. Ed. by Konrad K. Dabrowski, Maximilien Gadouleau, Nicholas Georgiou, Matthew Johnson, George B. Mertzios, and Daniël Paulusma. London Mathematical Society Lecture Note Series. Cambridge University Press, 2021, pp. 187–234. doi:10.1017/97810...

    work page doi:10.1017/9781009036214.006 2021

  19. [19]

    Pebble Games and linear equations

    Martin Grohe and Martin Otto. “Pebble Games and linear equations”. In:J. Symb. Log. 80.3 (2015), pp. 797–844.doi:10.1017/jsl.2015.28

    work page doi:10.1017/jsl.2015.28 2015

  20. [20]

    Graph Similarity and Approx- imate Isomorphism

    Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger. “Graph Similarity and Approx- imate Isomorphism”. In:43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, Liverpool, UK, August 27-31, 2018. Ed. by Igor Potapov, Paul G. Spirakis, and James Worrell. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, 20...

    work page doi:10.4230/lipics.mfcs.2018.20 2018

  21. [21]

    ε-nets and simplex range queries

    David Haussler and Emo Welzl. “ε-nets and simplex range queries”. In:Discret. Comput. Geom.2 (1987), pp. 127–151.doi:10.1007/BF02187876

    work page doi:10.1007/bf02187876 1987

  22. [22]

    Logical Hierarchies in PTIME

    Lauri Hella. “Logical Hierarchies in PTIME”. In:Inf. Comput.129.1 (1996), pp. 1–19.doi: 10.1006/inco.1996.0070

    work page doi:10.1006/inco.1996.0070 1996

  23. [23]

    Balay, W

    Neil Immerman and Eric Lander. “Describing Graphs: A First-Order Approach to Graph Canonization”. In:Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988. Ed. by Alan L. Selman. New York, NY: Springer New York, 1990, pp. 59–81.isbn: 978-1-4612-4478-3.doi:10.1007/978-1-4612- 4478-3\_5

    work page doi:10.1007/978-1-4612- 1988

  24. [24]

    2020 , url =

    Sandra Kiefer. “The Weisfeiler-Leman algorithm: an exploration of its power”. In:ACM SIGLOG News7.3 (2020), pp. 5–27.doi:10.1145/3436980.3436982

    work page doi:10.1145/3436980.3436982 2020

  25. [25]

    Spectrally Robust Graph Isomorphism

    Alexandra Kolla, Ioannis Koutis, Vivek Madan, and Ali Kemal Sinop. “Spectrally Robust Graph Isomorphism”. In:45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13, 2018. Ed. by Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella. LIPIcs. Schloss Dagstuhl - Leibniz-Ze...

    work page 2018

  26. [26]

    32 Hung Le and Christian Wulff-Nilsen

    Hung Le and Christian Wulff-Nilsen. “VC Set Systems in Minor-free (Di)Graphs and Applications”. In:Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024. Ed. by David P. Woodruff. SIAM, 2024, pp. 5332–5360.doi:10.1137/1.9781611977912.192

    work page doi:10.1137/1.9781611977912.192 2024

  27. [27]

    Long, and Aravind Srinivasan

    Yi Li, Philip M. Long, and Aravind Srinivasan. “Improved Bounds on the Sample Com- plexity of Learning”. In:J. Comput. Syst. Sci.62.3 (2001), pp. 516–527.doi:10.1006/ jcss.2000.1741

    work page arXiv 2001

  28. [28]

    Sherali-Adams relaxations of graph isomorphism polytopes

    Peter N. Malkin. “Sherali-Adams relaxations of graph isomorphism polytopes”. In:Discret. Optim.12 (2014), pp. 73–97.doi:10.1016/j.disopt.2014.01.004

    work page doi:10.1016/j.disopt.2014.01.004 2014

  29. [29]

    Jiří Matoušek.Geometric discrepancy: An illustrated guide. Vol. 18. Algorithms and Combinatorics. Springer-Verlag, Berlin, 1999, pp. xii+288.isbn: 3-540-65528-X.doi: 10.1007/978-3-642-03942-3

    work page doi:10.1007/978-3-642-03942-3 1999

  30. [30]

    Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe

    Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. “Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks”. In:The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019. AAAI Press, 2019, pp. 4602–4609.doi:...

    work page doi:10.1609/aaai.v33i01.33014602 2019

  31. [31]

    Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs

    Ryan O’Donnell, John Wright, Chenggang Wu, and Yuan Zhou. “Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs”. In:Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014. Ed. by Chandra Chekuri. SIAM, 2014, pp. 1659–1677. doi:10.1137/1.9781611973402.120

    work page doi:10.1137/1.9781611973402.120 2014

  32. [32]

    An analytic approach to stability

    Oleg Pikhurko. “An analytic approach to stability”. In:Discret. Math.310.21 (2010), pp. 2951–2964.doi:10.1016/j.disc.2010.07.002

    work page doi:10.1016/j.disc.2010.07.002 2010

  33. [33]

    LasserreHierarchyforGraphIsomorphismandHomo- morphism Indistinguishability

    DavidE.RobersonandTimSeppelt.“LasserreHierarchyforGraphIsomorphismandHomo- morphism Indistinguishability”. In:TheoretiCS3, 20 (2024).doi: 10.46298/theoretics. 24.20

    work page doi:10.46298/theoretics 2024

  34. [34]

    1972 , _month = jul, journal =

    Norbert Sauer. “On the Density of Families of Sets”. In:J. Comb. Theory A13.1 (1972), pp. 145–147.doi:10.1016/0097-3165(72)90019-2

    work page doi:10.1016/0097-3165(72)90019-2 1972

  35. [35]

    Natural language processing (almost) from scratch,

    Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. “Weisfeiler-Lehman Graph Kernels”. In:J. Mach. Learn. Res.12 (2011), pp. 2539–2561.doi:10.5555/1953048.2078187

    work page doi:10.5555/1953048.2078187 2011

  36. [36]

    The reduction of a graph to canonical form and the algebra which appears therein

    Boris Y. Weisfeiler and Andrei A. Leman. “The reduction of a graph to canonical form and the algebra which appears therein”. In:NTI, Series 2(1968). English translation by Grigory Ryabov available athttps://www.iti.zcu.cz/wl2018/pdf/wl_paper_ translation.pdf

    work page 1968

  37. [37]

    How Powerful are Graph Neural Networks?

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. “How Powerful are Graph Neural Networks?” In:7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.url:https:// openreview.net/forum?id=ryGs6iA5Km. A Assignment problems Let us consider the following generalisation of the ass...

    work page 2019