+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 27. September 2024, 10:00 Uhr Ort: Raum 9222 (Informatikzentrum E3, Ahornstraße 55) Referent: Jan Wilhelm Böker, M.Sc. Lehrstuhl für Logik und Theorie diskreter Systeme (Informatik 7) Thema: Structural Similarity of Graphs: Graphons and Homomorphism Densities Abstract: The abundance of graph-structured data in domains like bio-informatics 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. The use of tree homomorphism counts is appealing in order to define graph embeddings that not only are well-founded theoretically but also 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. 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. Es laden ein: die Dozentinnen und Dozenten der Informatik