Structural similarity of graphs: graphons and homomorphism densities

Böker, Jan Wilhelm; Kráľ, Daniel; Grohe, Martin

doi:HT030877383

Structural similarity of graphs: graphons and homomorphism densities = Strukturelle Ähnlichkeit von Graphen: Graphone und Homomorphismendichten

Böker, Jan Wilhelm^RWTH*

2024

Verantwortlichkeitsangabevorgelegt von Jan Wilhelm Böker, M. Sc.

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2024

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grohe, Martin (Thesis advisor)^RWTH* ; Kráľ, Daniel (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2024-09-27

Online
DOI: 10.18154/RWTH-2024-09270
URL: https://publications.rwth-aachen.de/record/994434/files/994434.pdf

Einrichtungen

Projekte

SymSim - Symmetry and Similarity (101054974) (101054974)

Inhaltliche Beschreibung (Schlagwörter)
Baum-Schnittdistanz (frei) ; Graphähnlichkeit (frei) ; Homomorphismendichten (frei) ; Rekonstruierbarkeit (frei) ; Weisfeiler-Leman (frei) ; graph similarity (frei) ; homomorphism densities (frei) ; reconstructability (frei) ; tree cut distance (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Die Fülle an Daten in Form von Graphen in Bereichen wie der Bioinformatik hat zu der Popularität von sowohl Grapheneinbettungen als auch neuronalen Graphennetzen als Techniken für maschinelles Lernen auf Graphen geführt. Die Weiterentwicklung dieses Gebiets wird allerdings hauptsächlich von Intuition und Empirismus vorangetrieben. Es fehlt eine theoretische Grundlage, die sowohl den Erfolg als auch die Beschränkungen dieser Techniken erklärt. Ein Satz von Lovász besagt, dass ein Graph durch das Zählen von Homomorphismen von allen Graphen in diesen Graphen bis auf Isomorphie vollständig beschrieben wird. Dieses Ergebnis stellt den Anfang der Theorie der Grenzwerte dichter Graphen und den der Theorie der Homomorphismenununterscheidbarkeit dar, welche die Verwendung von Homomorphismenanzahlen motivieren, um Grapheneinbettungen zu erhalten. Insbesondere die Verwendung von Baumhomomorphismenanzahlen ist reizvoll, um Grapheneinbettungen zu definieren, die nicht nur die strukturelle Ähnlichkeit von Graphen einfangen, sondern auch effizient berechenbar sind. Graphone ergaben sich als die Grenzwertobjekte in der Theorie der Grenzwerte dichter Graphen und stellen eine Verallgemeinerung von Graphen auf messbare Funktionen dar. Wir entwickeln eine Rahmenstruktur für Graphonähnlichkeit basierend auf iterierten Gradmaßen, die vor Kurzem von Grebík und Rocha für eine Verallgemeinerung der Farbverfeinerung, einer bekannten Heuristik für Graphisomorphietests, auf Graphone eingeführt wurden. Wir zeigen, dass sich neuronale Nachrichtenaustausch-Graphennetze neben Baumhomomorphismendichten in diese Rahmenstruktur integrieren lassen. Wir integrieren eine metrische Variante der Farbverfeinerung in unsere Rahmenstruktur. Weiterhin führen wir die Baum-Schnittdistanz ein, eine Variante der Schnittdistanz aus der Theorie der Grenzwerte dichter Graphen. Unsere Rahmenstruktur ermöglicht es uns, zu zeigen, dass diese vier Konzepte allesamt denselben Ähnlichkeitsbegriff auf Graphonen liefern: Ähnlichkeit in einem impliziert Ähnlichkeit in den anderen. Insbesondere begründen wir damit eine Theorie der Grenzwerte dichter Graphen bezüglich Baumhomomorphismendichten. In dem Spezialfall von Graphen liefert unsere Rahmenstruktur vier Ähnlichkeitsmaße, die nicht nur äquivalent sind, sondern auch effizient berechnet werden können. Wir betrachten auch kurz die Berechnungskomplexität des Homomorphismenrekonstruierbarkeitsproblems, das fragt, ob ein gegebener Vektor natürlicher Zahlen tatsächlich durch Homomorphismenanzahlen in einen Graphen realisiert werden kann. Wir zeigen, dass dieses Problem auch in einer stark eingeschränkten Form NP-schwer ist. Der k-dimensionale Weisfeiler-Leman-Algorithmus ist eine Verallgemeinerung der Farbverfeinerung auf höhere Dimensionen. Um die Entwicklung einer höherdimensionalen Variante unserer Rahmenstruktur für Graphonähnlichkeit einzuleiten, verallgemeinern wir diesen Algorithmus und mehrere seiner Charakterisierungen auf Graphone und beweisen die Äquivalenz dieser. Insbesondere erhalten wir eine Charakterisierung mittels Homomorphismendichten von Multigraphen beschränkter Baumweite. Wir zeigen, dass auch eine Charakterisierung mittels einfacher Graphen beschränkter Baumweite durch eine Variante des Algorithmus erhalten werden kann.

The abundance of graph-structured data in domains like bioinformatics has led to the popularity of both graph embeddings and graph neural networks as techniques for machine learning on graphs. Advancements in this field, however, are mostly driven by intuition and empiricism, and there is a lack of a theoretical foundation that explains both the success and the limits of these techniques. A theorem of Lovász states that a graph is characterized up to isomorphism by counting homomorphisms from all graphs to it. It presents the starting point of both the theory of dense graph limits and the theory of homomorphism indistinguishability, which then motivate the use of homomorphism counts to obtain graph embeddings. In particular, the use of tree homomorphism counts is appealing in order to define graph embeddings that not only reflect the structural similarity of graphs well but also are efficiently computable. Graphons emerged as the limit objects in the theory of dense graph limits and are a generalization of graphs to measurable functions. We develop a framework for graphon similarity based on iterated degree measures, which were recently introduced by Grebík and Rocha in a generalization of Color Refinement, a popular heuristic algorithm for graph isomorphism testing, to graphons. We show that, besides tree homomorphism densities, also message-passing graph neural networks integrate into this framework. We integrate a metric variant of Color Refinement into our framework. Furthermore, we introduce the tree cut distance, a variant of the cut distance from the theory of dense graph limits. Our framework allows us to prove that these four concepts all yield the same notion of similarity of graphons: similarity in one notion implies similarity in the others. In particular, this establishes a theory of dense graph limits with respect to tree homomorphism densities. In the special case of graphs, our framework gives us four similarity measures that are not only equivalent but can also be computed efficiently. We also briefly study the computational complexity of the homomorphism reconstructability problem, which asks whether a given vector of natural numbers can actually be realized as homomorphism counts to a graph. We show that this problem is NP-hard even in a severely restricted form. The k-dimensional Weisfeiler-Leman algorithm is a generalization of Color Refinement to higher dimensions. To initiate the development of a higher-dimensional variant of our framework for graphon similarity, we generalize this algorithm and various of its characterizations to graphons and prove their equivalence. In particular, we obtain a characterization in terms of homomorphism densities from multigraphs of bounded treewidth. We show that also a characterization in terms of simple graphs of bounded treewidth can be obtained by a variant of the algorithm.

OpenAccess:
PDF
(additional files)