h1

000785831 001__ 785831
000785831 005__ 20230411160923.0
000785831 0247_ $$2HBZ$$aHT020407174
000785831 0247_ $$2datacite_doi$$a10.18154/RWTH-2020-03508
000785831 0247_ $$2Laufende Nummer$$a39126
000785831 037__ $$aRWTH-2020-03508
000785831 041__ $$aEnglish
000785831 082__ $$a004
000785831 1001_ $$0P:(DE-588)1207424838$$aKiefer, Sandra$$b0$$urwth
000785831 245__ $$aPower and limits of the Weisfeiler-Leman algorithm$$cvorgelegt von Sandra Kiefer, Master of Science$$honline
000785831 246_3 $$aStärken und Grenzen des Weisfeiler-Leman-Algorithmus$$yGerman
000785831 260__ $$aAachen$$c2020
000785831 300__ $$a1 Online-Ressource (viii, 249 Seiten) : Illustrationen
000785831 3367_ $$02$$2EndNote$$aThesis
000785831 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000785831 3367_ $$2BibTeX$$aPHDTHESIS
000785831 3367_ $$2DRIVER$$adoctoralThesis
000785831 3367_ $$2DataCite$$aOutput Types/Dissertation
000785831 3367_ $$2ORCID$$aDISSERTATION
000785831 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
000785831 502__ $$aDissertation, RWTH Aachen University, 2020$$bDissertation$$cRWTH Aachen University$$d2020$$gFak01$$o2020-03-16
000785831 5203_ $$aDer Weisfeiler-Leman (WL) Algorithmus ist eine wichtige kombinatorische Technik, die in den 1960er Jahren entwickelt wurde und vorrangig zur Klassifizierung von Graphen und anderen relationalen Strukturen verwendet wird. Er findet in zahlreichen Bereichen der theoretischen und praktischen Informatik Anwendung, darunter Modelltheorie, deskriptive Komplexitätstheorie, Beweiskomplexität und maschinelles Lernen. Der Algorithmus ist vor allem für seine zentrale Rolle in Graphisomorphie-Algorithmen bekannt. Besonders erwähnenswert ist Babais bahnbrechender Quasipolynomialzeit-Isomorphietest aus dem Jahr 2016, der als ein Kernstück eine hochdimensionale Version des WL Algorithmus beinhaltet. Für jede natürliche Zahl k berechnet die k-dimensionale Version (k-WL) iterativ eine Färbung der k-Tupel von Knoten des Eingabegraphen. Je größer k, desto ausdrucksstärker ist k-WL. Dennoch gibt es keine Dimension k, die Graphisomorphie im Allgemeinen korrekt entscheidet. Andererseits ist es oft schwierig zu entscheiden, ob und wann k-WL zwei konkrete Graphen unterscheidet. Diese Arbeit untersucht diese Wissensgrenze und zielt darauf, das Verständnis der Funktionsweise, der Ausdrucksstärke und der Grenzen des WL Algorithmus zu verbessern. Durch seine Verbindungen zu vielen Forschungsbereichen sind elegante und überraschende Charakterisierungen von k-WL entdeckt worden. Beispielsweise entspricht die Ausdrucksstärke von k-WL jener der Zähllogik C^(k+1) und lässt sich mit Gewinnstrategien in einem Ehrenfeucht-Fraïssé-Spiel beschreiben. Diese Arbeit kombiniert die drei Charakterisierungen des Algorithmus zu effektiven Beweistechniken. Zunächst untersuchen wir die Iterationenzahl des Algorithmus, welche einen direkten Bezug zur Quantorentiefe von C^k-Formeln hat. Mittels einer Konstruktion von unendlichen Graphfamilien zeigen wir, dass die triviale obere Schranke von n-1 an die Iterationszahl von 1-WL auf Graphen mit n Knoten (bis auf eine additive Konstante von 1) scharf ist. Dies verbessert die bisherige untere Schranke von n-sqrt(n). Für 2-WL sieht die Situation komplett anders aus: Wir zeigen, dass die triviale obere Schranke an die Iterationszahl nicht einmal asymptotisch scharf ist. Selbst wenn k-WL wenige Iterationen zur Berechnung seiner Ausgabe benötigt, gilt keinesfalls, dass er den gegebenen Graphen von allen anderen unterscheidet. Bezüglich seiner Ausdrucksstärke ist viel eher die Dimension des Algorithmus zu betrachten. Hierzu präsentieren wir eine vollständige Charakterisierung der Graphen und aller relationalen Strukturen, für die 1-WL Isomorphie korrekt entscheidet. Am Übergang zu höheren Dimensionen studieren wir die Fähigkeit des Algorithmus, Graphen zu zerlegen. Wir wenden die Ergebnisse an, um zu zeigen, dass 3-WL jeden planaren Graphen identifiziert, was eine drastische Verbesserung gegenüber allen bisherigen bekannten Schranken darstellt. Planare Graphen stellen den Basisfall in unserer weiteren Betrachtung von Graphklassen dar, die durch ihren Euler-Genus parametrisiert sind. Wir zeigen, dass die WL Dimension jedes Graphen höchstens linear in seinem Euler-Genus ist. Dieses Resultat ist die erste explizite Parametrisierung der WL Dimension durch den Euler-Genus des Eingabegraphen.$$lger
000785831 520__ $$aThe Weisfeiler-Leman (WL) algorithm is a fundamental combinatorial technique used to classify graphs and other relational structures. It dates back to the 1960s and has applications in numerous fields of theoretical and practical computer science, such as finite model theory, descriptive complexity theory, propositional proof complexity, and machine learning. Recently discovered links to graph kernels and neural networks demonstrate the persisting importance of the algorithm. It finds particularly prominent use in approaches to the graph isomorphism problem, the task to decide whether two graphs are structurally equivalent or not. Most notably, Babai's breakthrough result from 2016, a quasipolynomial-time graph isomorphism test, relies heavily on a high-dimensional version of the algorithm. Roughly speaking, for every natural number k, the k-dimensional version of the algorithm (k-WL) iteratively computes a colouring of the vertex k-tuples of the input graph. The larger k, the more powerful k-WL becomes. Still, there is no fixed dimension which decides graph isomorphism in general. On the other hand, it is usually highly non-trivial to tell if and when k-WL distinguishes two particular graphs. This thesis explores that frontier and aims at providing a better understanding of the dynamics, the power, and the limits of the WL algorithm. Through its connections to many research areas, beautiful and surprising characterisations of k-WL have been discovered. For example, its expressive power is captured by the counting logic C^(k+1) and also by a certain type of Ehrenfeucht-Fraïssé game. This thesis combines the three characterisations of the algorithm to obtain powerful proof techniques. We first study the number of iterations of the algorithm until stabilisation, which is closely connected to the quantifier depth of a distinguishing C^k-formula. Via the construction of infinite graph families, we show that the trivial upper bound n-1 on the number of iterations of 1-WL on n-vertex graphs is tight (up to an additive constant of 1). This improves upon the previous best lower bound of n-sqrt(n). In contrast to this, the situation for 2-WL is quite different: we prove that the trivial upper bound on the iteration number is not tight, not even asymptotically. As simple examples show, even if the algorithm needs few iterations to compute its output, this does not imply that it distinguishes the given graph from all others. The parameter to study concerning the expressive power of the algorithm is its dimension. In this direction, we present a complete characterisation of the graphs and all relational structures for which 1-WL correctly decides isomorphism. Proceeding to higher dimensions, we investigate the ability of the algorithm to decompose graphs. By applying the results, we show that 3-WL identifies every planar graph, which drastically improves upon all previously known bounds. Planar graphs constitute the base case in our further consideration of graph classes parameterised by their Euler genus. We show that the WL dimension of every graph is at most linear in its Euler genus. This result is the first explicit parametrisation of the WL dimension by the Euler genus of the input graph.$$leng
000785831 588__ $$aDataset connected to Lobid/HBZ
000785831 591__ $$aGermany
000785831 653_7 $$aWeisfeiler-Leman algorithm
000785831 653_7 $$aWeisfeiler-Leman dimension
000785831 653_7 $$acolour refinement
000785831 653_7 $$acounting logic
000785831 653_7 $$apebble games
000785831 7001_ $$0P:(DE-82)IDM00084$$aGrohe, Martin$$b1$$eThesis advisor$$urwth
000785831 7001_ $$0P:(DE-82)189768$$aSchweitzer, Pascal$$b2$$eThesis advisor
000785831 7001_ $$aImmerman, Neil$$b3$$eThesis advisor
000785831 8564_ $$uhttps://publications.rwth-aachen.de/record/785831/files/785831.pdf$$yOpenAccess
000785831 8564_ $$uhttps://publications.rwth-aachen.de/record/785831/files/785831_source.zip$$yRestricted
000785831 8564_ $$uhttps://publications.rwth-aachen.de/record/785831/files/785831.gif?subformat=icon$$xicon$$yOpenAccess
000785831 8564_ $$uhttps://publications.rwth-aachen.de/record/785831/files/785831.jpg?subformat=icon-180$$xicon-180$$yOpenAccess
000785831 8564_ $$uhttps://publications.rwth-aachen.de/record/785831/files/785831.jpg?subformat=icon-700$$xicon-700$$yOpenAccess
000785831 909CO $$ooai:publications.rwth-aachen.de:785831$$popenaire$$popen_access$$pVDB$$pdriver$$pdnbdelivery
000785831 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-588)1207424838$$aRWTH Aachen$$b0$$kRWTH
000785831 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00084$$aRWTH Aachen$$b1$$kRWTH
000785831 9141_ $$y2020
000785831 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000785831 9201_ $$0I:(DE-82)122910_20140620$$k122910$$lLehrstuhl für Informatik 7 (Logik und Theorie diskreter Systeme)$$x0
000785831 9201_ $$0I:(DE-82)120000_20140620$$k120000$$lFachgruppe Informatik$$x1
000785831 961__ $$c2020-05-12T08:18:38.012831$$x2020-03-23T09:22:25.477195$$z2020-05-12T08:18:38.012831
000785831 9801_ $$aFullTexts
000785831 980__ $$aI:(DE-82)120000_20140620
000785831 980__ $$aI:(DE-82)122910_20140620
000785831 980__ $$aUNRESTRICTED
000785831 980__ $$aVDB
000785831 980__ $$aphd