Width of Graph Decompositions Eva Fluck [ati][speaker=https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~ryzs/Eva-Fluck/] Tree and Path decompositions of graphs are an important and well studied topic in theoretical computer science and discrete math, since at least the Graph Minors project of Robertson and Seymour. Recently a generalization to graph classes beyond paths and trees emerged. In this talk we will look at a possible width measure for general graph decompositions, since considering the size of the bag no longer suffices for a rich theory. Furthermore we try to find an analog to Robertsons and Seymours Excluded Gird Theorem for tree width. That is we try to find substructures that have to be present in graphs of large width. We are able to proof a theorem for our width measure on path decompositions and give a conjecture for all minor closed classes of graphs. Joint work with Sandra Albrechtsen, Reinhard Diestel, Ann-Kathrin Elm, Raphael W. Jacobs, Paul Knappe and Paul Wollan.
23/06/2022 11:00 - 11:45
MSc
Hierarchical Message Passing for Constraint Satisfaction Problems Moritz Rösgen RUN-CSP is a graph neural network solving optimization problems modelled as constraint satisfaction problems (CSPs) by performing message passing on the graph representation of said problems. It is a generic architecture that can be trained unsupervised on any binary CSPs. We introduce an extension for RUN-CSP that additionally performs message passing on the tree decomposition of the input graph. Our goal is to use a tree decomposition that captures the global structure of the graph and allow messages to be passed through the graph in less steps. To this end we experiment with different algorithms for computing tree decompositions. In these experiments we compare our extension with the original architecture. It shows that we were not able to improve the results of RUN-CSP significantly. Neither on instances that were originally used to evaluate RUN-CSP nor on instances that we generated with a small treewidth.
21/06/2022 11:00 - 11:30
BSc
The Complexity of Counting Small Patterns in Graphs and Relational Structures Daniel Quirmbach In der Präsentation wird die Komplexität des Zählens von Mustern auf Graphen und relationalen Strukturen untersucht. Hierzu wird das Konzept der Graphmotivparameter vorgestellt, um eine geschlossene Vorgehensweise für die Komplexitätsabschätzung der Zählprobleme #Hom, #Sub und #IndSub zu erhalten, die entweder die Anzahl an Homomorphismen oder an (induzierten) Teilgraphen eines Musters H zu beziehungsweise auf einem Graphen G zählen sollen. Ausgehend vom Dichotomiecharakters der Komplexität vom Problem #Hom untersuchen wir die Komplexität von Linearkombinationen von Problemen in #Hom. Durch eine Darstellung der Probleme #Sub und #IndSub als Linearkombinationen von Homomorphismenproblemen erhalten wir auch eine Dichotomie für diese Klassen. Wir erweitern die Idee der Graphmotivparameter auf relationale Strukturen und zeigen mithilfe einer Dichotomie des Problems $#Hom$ für relationale Strukturen, dass auch die Probleme #Sub und #IndSub durch ihre Darstellung als Linearkombination von Problemen in #Hom immer entweder in polynomieller Zeit lösbar oder #W[1]-schwer sind. Zudem identifizieren wir anhand der Baumweite ein Dichotomiekriterium, welches uns ermöglicht einzelne Probleminstanzen einer der beiden oben genannter Komplexitätsklassen zuzuordnen.
23/05/2022 11:00 - 11:45
MSc
Approximate Probabilistic Query Evaluation Oliver Feith [master]Probabilistic databases model uncertain data as a probability space over traditional relational databases. Evaluating queries in probabilistic databases hence requires computing confidences for the answers, which is#P-hard even for (some) conjunctive queries. Therefore, new methods are needed to obtain practical solutions. We survey the computational complexity ofapproximatelyevaluat- ing queries. In particular, we study the data complexity of queries with regard to additive and multiplicative approximation. We adapt algorithms and techniques for proving hardness-of-approximation re- sults from related fields to show that these approximation paradigms give rise to a strict hierarchy under common complexity-theoretic assumptions: While exact evaluation is tractable for only select con- junctive queries, the class of (unions of) conjunctive queries admits a multiplicative FPRAS. However, we identify other seemingly simple queries which resist multiplicatively approximate evaluation entirely. By contrast, all queries can be evaluated using an additive FPRAS.
20/05/2022 10:30 - 11:30
ATI
The solidarity cover problem Eran Rosenbluth Various real-world problems consist of partitioning a set of locations into disjoint subsets such that each subset covers the whole set with a certain radius. Given a finite set S, a metric d, and a radius r, define a subset S' ⊆ S to be an *r-cover* if and only if ∀s ∈ S ∃s' ∈ S' : d(s, s') ≤ r. We examine the problem of determining whether there exist m disjoint r-covers, naming it the Solidarity Cover Problem (SCP). We consider as well the related optimization problems of maximizing the number of r-covers, referred to as the partition size, and minimizing the radius. We analyze the relation between the SCP and a graph problem known as the Domatic Number Problem (DNP), both hard problems in the general case. We show that the SCP is hard already in the Euclidean 2D setting, implying hardness of the DNP already in the unit disc graph setting. As far as we know, the latter is a result yet to be shown. We use the tight approximation bound of (1 + o(1))ln(n) for the DNP’s general case, shown by U. Feige, M. Halldórsson, G. Kortsarz, and A. Srinivasan (SIAM 15 Journal on computing, 2002), to deduce the same bound for partition-size approximation of the SCP in the Euclidean space setting. We show an upper bound of 3 and lower bounds of 2 and √2 for approximating the minimal radius in different settings of the SCP. Lastly, in the Euclidean 2D setting we provide a bicriteria-approximation of ( 1/16, 2) for the partition size and radius respectively. Joint work with Britta Peis and Laura Vargas Koch.
13/05/2022 10:30 - 11:30
ATI
Solving AC Power Flow with Graph Neural Networks under Realistic Constraints Hinrikus Wolf We propose a graph neural network architecture solving the AC power flow problem under realistic constraints. While the energy transition is changing the energy industry to a digitalized and decentralized energy system, the challenges are increasingly shifting to the distribution grid level to integrate new loads and generation technologies. To ensure a save and resilient operation of distribution grids, AC power flow calculations are the means of choice to determine grid operating limits or analyze grid asset utilization in planning procedures. In our approach we demonstrate the development of a framework which makes use of graph neural networks to learn the physical constraints of the power flow. We present our model architecture on which we perform unsupervised training to learn a general solution of the AC power flow formulation that is independent of the specific topologies and supply tasks used for training. Finally, we demonstrate, validate and discuss our results on medium voltage benchmark grids.
Integer Factorization Using Graph Neural Networks Raman Daoud In this thesis, an efficient algorithm was implemented that encodes integer factorisation instances as CSPs and SAT instances. In addition, experiments were performed to test the performance of GNN-based CSP and SAT solvers for the factorisation problem.
01/04/2022 10:30 - 11:15
MSc
The Iteration Number of the Weisfeiler-Leman Algorithm Athena Riazsadri The Weisfeiler-Leman (WL) algorithm is a simple combinatorial algorithm with widespread applications, most prominently as a subroutine for competitive graph isomorphism solvers. The number of iterations until it reaches termination is crucial for the parallelized running time of the algorithm. For each integer k, there is a k-dimensional version of the algorithm. While Lichter et al. (LICS 2019) provided an upper bound of O(n*log n) on the iteration number of 2-WL on input graphs of order n, there have been no improvements over the trivial upper bound of O(n^k) on the iteration number of the k-dimensional version of the algorithm for k>2 and input graphs of order n. We will present the proof to the currently best known upper bound of O(n*log n) on the iteration number of 2-WL and provide a parameterized upper bound on the iteration number of k-WL for k>2.
01/04/2022 10:30 - 11:15
MSc
The Iteration Number of the Weisfeiler-Leman Algorithm Athena Riazsadri The Weisfeiler-Leman (WL) algorithm is a simple combinatorial algorithm with widespread applications, most prominently as a subroutine for competitive graph isomorphism solvers. The number of iterations until it reaches termination is crucial for the parallelized running time of the algorithm. For each integer k, there is a k-dimensional version of the algorithm. While Lichter et al. (LICS 2019) provided an upper bound of O(n*log n) on the iteration number of 2-WL on input graphs of order n, there have been no improvements over the trivial upper bound of O(n^k) on the iteration number of the k-dimensional version of the algorithm for k>2 and input graphs of order n. We will present the proof to the currently best known upper bound of O(n*log n) on the iteration number of 2-WL and provide a parameterized upper bound on the iteration number of k-WL for k>2.
31/03/2022 15:00 - 15:30
BSc
Characterising Fragments of First-Order Logic by Counting Homomorphisms Gian Luca Spitzer Two graphs G, G' are homomorphism-indistinguishable over a class S of graphs if for each F in S, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'. Results by Dvořák (2010) and Grohe (2020) show that homomorphism-indistinguishability over the class of graphs of tree-width at most k coincides with logical equivalence in the (k+1)-variable fragment of first-order logic with counting, while homomorphism-indistinguishability over the class of graphs of tree-depth at most q coincides with equivalence in the quantifier-rank-q fragment. We introduce the graph parameter of elimination-order and prove that two graphs are equivalent in the k-variable, quantifier-rank-q fragment of counting first-order logic if and only if they are homomorphism-indistinguishable over the class of graphs of elimination-order (k,q).
31/03/2022 15:45 - 16:30
MSc
Variants of the Weisfeiler-Leman Algorithm Sebastian Issel [master]The expressiveness of different variants of the k-dimensional Weisfeiler-Leman algorithm and related concepts is compared. The relation of the classical coloring, the bijective pebble game and counting logics will be generalized to these variants with similar results.The variants are obtained by relaxing the coloring of tuples to sets or multisets ofvertices. This reduces the needed memory to calculate the coloring. Some upper and lower bounds of their expressiveness, compared to the classical version, are shown. As an additional viewpoint, a linear equation system will be defined which turns out to be solvable precisely if the algorithm cannot differentiate the graphs. This system stems from an adaptation of the Sherali-Adams relaxation for integer linear programming.
31/03/2022 15:00 - 15:30
BSc
Characterising Fragments of First-Order Logic by Counting Homomorphisms Gian Luca Spitzer Two graphs G, G' are homomorphism-indistinguishable over a class S of graphs if for each F in S, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'. Results by Dvořák (2010) and Grohe (2020) show that homomorphism-indistinguishability over the class of graphs of tree-width at most k coincides with logical equivalence in the (k+1)-variable fragment of first-order logic with counting, while homomorphism-indistinguishability over the class of graphs of tree-depth at most q coincides with equivalence in the quantifier-rank-q fragment. We introduce the graph parameter of elimination-order and prove that two graphs are equivalent in the k-variable, quantifier-rank-q fragment of counting first-order logic if and only if they are homomorphism-indistinguishable over the class of graphs of elimination-order (k,q).
31/03/2022 15:45 - 16:30
MSc
Variants of the Weisfeiler-Leman Algorithm Sebastian Issel [master]The expressiveness of different variants of the k-dimensional Weisfeiler-Leman algorithm and related concepts is compared. The relation of the classical coloring, the bijective pebble game and counting logics will be generalized to these variants with similar results.The variants are obtained by relaxing the coloring of tuples to sets or multisets ofvertices. This reduces the needed memory to calculate the coloring. Some upper and lower bounds of their expressiveness, compared to the classical version, are shown. As an additional viewpoint, a linear equation system will be defined which turns out to be solvable precisely if the algorithm cannot differentiate the graphs. This system stems from an adaptation of the Sherali-Adams relaxation for integer linear programming.
25/03/2022 10:30 - 11:15
The Expressiveness of Convolutions and Random Walks in Graph Learning//Fabian Bender In the field of graphlearning, the well-known Weisfeiler-Leman algorithm imposes a hierarchy that theoreticallybinds the expressive powers of a wide group of modern learning architectures.This establishes impossibility constraints hindering these architectures to useimportant insights into graphs for real-world predictions. Provably not subject to this hierarchy, the work of [Toenshoff et al., 2021]introduces a new approach called CRAWL, which leverages 1D convolutions andrandom walks to capture the underlying structure of graphs. However, thetheoretical promises raise no guarantee in practical performance. In thisthesis, the abilities of the design to detect cycles and count various smallerstructures called graphlets in graphs are investigated. The expressiveness ofCRAWL and the influence of its hyperparameters is evaluated and compared to standardmessage-passing architectures as well as higherlevel approaches.
18/03/2022 10:30 - 11:15
BSc
Query Evaluation in Symmetric Probabilistic Databases Adrian Voß [bachelor] In 2011 van den Broeck et al. proposed an algorithm which is able to compute the symmetric weighted model count of a first-order sentence in CNF, which is effectively a probabilistic inference problem. In their subsequent research, van den Broeck et al. showed that their method is guaranteed to solve the problem in polynomial time for sentences with a most 2 logical variables. The algorithm can be applied to arbitrary first-order sentences using a novel Skolemization algorithm, which retains the model count of a first-order sentence. The naturally arising question about sentences with at least 3 variables has been answered negatively by Suciu et al. 2015. In 2014 van den Broeck et al. also claimed that their algorithm is applicable to symmetric probabilistic databases, for which it solves the query evaluation problem in polynomial time. In this thesis we expand on the latter and construct the relation between first-order models and probabilistic databases. We build a cohesive algorithm from the various sources, expand the descriptions from the original papers to detailed proofs and give examples which illustrate the application of the method, such that the algorithm can be used in probabilistic database applications directly.
11/03/2022 10:30 - 11:15
BSc
The Real Complexity of Query Evaluation in Probabilistic Databases János Arpasi [bachelor]Abstract: Probabilistic databases constitute probability distributions over relational databases. Of great interest for research have been the tuple independent probabilistic databases, where it was proven that for every UCQ that the evaluation problem is either computable in polynomial time or #P hard, but until now this always assumed all occurring probabilities are rational, so the case for arbitrary real numbers was not sorted out yet. We will therefore give an introduction into computable real numbers and functions, review some complexity theory for continuous data and show that the dichotomy holds true also for real numbers.
11/02/2022 10:30 - 11:30
ATI
Separating Rank Logic from Polynomial Time Moritz Lichter In the search for a logic capturing polynomial time the most promising candidates are Choiceless Polynomial Time (CPT) and rank logic. Rank logic extends fixed-point logic with counting by a rank operator over prime fields. In this talk I will discuss a recent construction that is a variant of the so called CFI graphs that defines them over Z_{2^i} rather than Z_2. The isomorphism problem of these CFI graphs over Z_{2^i} cannot be defined in rank logic, even if the base graph is totally ordered. However, CPT can define this isomorphism problem. The argument therefore separates rank logic from CPT and in particular from polynomial time. The key idea to argue that rank logic does not define the isomorphism problem of CFI graphs over Z_{2^i} constructs matrices over CFI graphs. These show that certain sequences of other matrices are simultaneously similar. I will also discuss arising challenges and hint at their solutions providing overall overview of the arguments, in particular of the construction of said matrices.
28/01/2022 10:00 - 11:00
ATI
Blind Extraction of Equitable Partitions From Graph Signals Michael Scholkemper Finding equitable partitions is closely related to the extraction of graph symmetries and of interest in a variety of applications such as node role detection, cluster synchronization, consensus dynamics, and network control problems. In this work we study a blind identification problem in which we aim to recover an equitable partition of a network without the knowledge of the network's edges but based solely on the observations of the outputs of an unknown graph filter. Specifically, we consider two settings. First, we consider a scenario in which we can control the input to the graph filter and present a method to extract the partition inspired by the well-known Weisfeiler-Lehman (color refinement) algorithm. Second, we generalize this idea to a setting where we only observe the outputs to random, low-rank excitations of the graph filter, and present a simple spectral algorithm to extract the relevant equitable partitions.
27/01/2022 15:00 - 16:00
BSc
The Logical Strength of Graph Neural Networks on Knowledge Graphs Fabian Hamm Abstract The 1-dimensional Weisfeiler–Leman algorithm and graph neural networks (GNNs) have prominently been defined on undirected non edge-labeled vertex-labeled graphs. It has been shown that they hold the same expressiveness when it comes to distinguishing graphs, which can also be defined in terms of the logic C_2, the first order logic with counting quantifiers and two variables. This talk will recapitulate this and other results, as well as extend them to directed edge-labeled graphs, which are also known as knowledge graphs.
[ati][speaker=https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~fvvzk/Christoph-Standke/] Typically, probabilistic databases (PDBs) are probability distributions over the subsets of a finite set of facts. The problem of evaluating a query on such set-PDBs, known as probabilistic query evaluation, is well-understood for unions of conjunctive queries (UCQs): it is either in polynomial time, or #P-hard (Dalvi and Suciu, JACM 2012). However, many practical implementations of relational databases use a bag semantics that allows multiple copies of a fact. For this reason, we study the query evaluation problem over PDBs with bag semantics (bag PDBs). As we will see, this setting differs substantially from the set-version. This talk will give an introduction to probabilistic query evaluation. We start by reviewing the case of set-PDBs and then present current results on querying bag-PDBs. This is joint work with Martin Grohe and Peter Lindner.
17/12/2021 10:00 - 11:00
ATI
Constructing deterministic ω-automata from examples by an extension of the RPNI algorithm León Bohn The RPNI algorithm (Oncina, Garcia 1992) constructs deterministic finite automata from finite sets of negative and positive example words. We propose and analyze an extension of this algorithm to deterministic ω-automata with different types of acceptance conditions. In order to obtain this generalization of RPNI, we develop algorithms for the standard acceptance conditions of ω-automata that check for a given set of example words and a deterministic transition system, whether these example words can be accepted in the transition system with a corresponding acceptance condition. Based on these algorithms, we can define the extension of RPNI to infinite words. We prove that it can learn all deterministic ω-automata with an informative right congruence in the limit with polynomial time and data. We also show that the algorithm, while it can learn some automata that do not have an informative right congruence, cannot learn deterministic ω-automata for all regular ω-languages in the limit. Finally, we also prove that active learning with membership and equivalence queries is not easier for automata with an informative right congruence than for general deterministic ω-automata.
10/12/2021 10:00 - 11:00
ATI
Graph Learning with 1D Convolutions on Random Walks Jan Tönshoff Graphs are a very general form of data that naturally occurs across a wide range of applications, from cheminformatics to social network analysis. Due to this ubiquity, Machine Learning on graph-structured data is both crucial and challenging. We propose CRaWl (CNNs for Random Walks), a novel neural network architecture for graph learning. It is based on processing sequences of small subgraphs induced by random walks with standard 1D CNNs. Thus, CRaWl is fundamentally different from typical message passing graph neural network architectures. It is inspired by techniques counting small subgraphs, such as the graphlet kernel and motif counting, and combines them with random walk based techniques in a highly efficient and scalable neural architecture. CRaWl is not constraint by the well known limitations of the standard message passing framework, which currently dominates graph learning. In particular, it can detect arbitrary substructures up to a chosen window size. We demonstrate empirically that CRaWl matches or outperforms state-of-the-art GNN architectures across a multitude of benchmark datasets for graph learning.
03/12/2021 10:00 - 11:00
ATI
Untangling Gaussian Mixtures Eva Fluck Tangles were originally introduced as a concept to formalize regions of high connectivity in graphs. In recent years, they were also discovered as a link between structural graph theory and data science: when interpreting similarity in data sets as connectivity between points, finding clusters in the data sets essentially amounts to finding tangles in the underlying graphs. This talk further explores the potential of tangles in data sets as a means for a formal study of clusters. Real-world data often follow a normal distribution. Accounting for this, we develop a quantitative theory of tangles in data sets drawn from Gaussian mixtures. To this end, we equip the data with a graph structure that models similarity between the points and allows to interpret the graph tangles as clusters in the data. We provide explicit conditions under which tangles associated with the marginal Gaussian distributions exist asymptotically almost surely. This is joint work with Sandra Kiefer and Christoph Standke.
03/12/2021 10:00 - 11:00
ATI
Untangling Gaussian Mixtures Eva Fluck Tangles were originally introduced as a concept to formalize regions of high connectivity in graphs. In recent years, they were also discovered as a link between structural graph theory and data science: when interpreting similarity in data sets as connectivity between points, finding clusters in the data sets essentially amounts to finding tangles in the underlying graphs. This talk further explores the potential of tangles in data sets as a means for a formal study of clusters. Real-world data often follow a normal distribution. Accounting for this, we develop a quantitative theory of tangles in data sets drawn from Gaussian mixtures. To this end, we equip the data with a graph structure that models similarity between the points and allows to interpret the graph tangles as clusters in the data. We provide explicit conditions under which tangles associated with the marginal Gaussian distributions exist asymptotically almost surely. This is joint work with Sandra Kiefer and Christoph Standke.
26/11/2021 10:00 - 11:00
ATI
Homomorphism Tensors and Linear Equations Tim Seppelt Lovász (1967) showed that two graphs $G$ and $H$ are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph $F$, the number of homomorphisms from $F$ to $G$ equals the number of homomorphisms from $F$ to $H$. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems. In this talk, a unified algebraic framework for such results is introduced by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. This is joint work with Martin Grohe and Gaurav Rattan.
19/11/2021 14:15 - 15:15
ATI
The Effects of Randomness on the Stability of Node Embeddings Hinrikus Wolf We systematically evaluate the (in-)stability of state-of-the-art node embedding algorithms due to randomness, i.e., the random variation of their outcomes given identical algorithms and networks. We ap- ply five node embeddings algorithms—HOPE, LINE, node2vec, SDNE, and GraphSAGE—to assess their stability under randomness with respect to their performance in downstream tasks such as node classification and link prediction. We observe that while the classification of individual nodes can differ substantially, the overall accuracy is mostly unaffected by the geometric instabilities in the underlying embeddings. In link prediction, we also observe high stability in the overall accuracy and a higher stability in individual predictions than in node classification. While our work highlights that the overall performance of downstream tasks is largely unaffected by randomness in node embeddings, we also show that individual predictions might be dependent solely on randomness in the underlying embeddings. Our work is relevant for researchers and engineers interested in the effectiveness, reliability, and reproducibility of node embedding approaches.
11/11/2021 13:00 - 14:00
Graph Embeddings Based on Homomorphism Counts Pascal Kühner A graph homomorphism is a mapping from the nodes of one graph F to the nodes of another graph G. The number of homomorphisms from each graph F in a fixed set F to an arbitrary graph G can be used as a graph embedding for G. We can make many statements on graph similarity (e.g. fractional isomorphisms) if F is fixed to certain natural graph classes as trees, cycles or paths. This makes these embeddings an interesting option in a machine learning context. Within this thesis, we explore these embeddings and conduct various experiments on graph classification, node classification and graph regression tasks. These experiments show, that these embeddings can achieve similar performance as well-known graph kernels on many of these machine learning tasks. Yet, practicability of homomorphism count embeddings remains questionable, as they can be hardly computed on bigger graphs and in addition there are problems with embedding additional information as node labels or edge features.
05/11/2021 10:00 - 11:00
ATI
Weisfeiler-Leman Indistinguishability of Graphons Jan Böker The color refinement algorithm is mainly known as a heuristic for graph isomorphism. It computes a coloring of the vertices of a graph, and if these colorings of two graphs do not match, they cannot be isomorphic. Indistinguishability by the color refinement algorithm can be characterized in various different ways, e.g., fractional isomorphism or tree homomorphism counts, and has recently been generalized from graphs to graphons, a natural notion for the limit of a sequence of graphs (Grebík and Rocha, 2021). The k-dimensional Weisfeiler-Leman algorithm is a more powerful generalization of color refinement that colors k-tuples instead of single vertices. We show how indistinguishability by the $k$-dimensional Weisfeiler-Leman algorithm generalizes from graphs to graphons.
29/10/2021 10:00 - 11:00
ATI
Spectral Graph Similarity Timo Gervens The graph similarity problem is an optimization version of the graph isomorphism problem. Given two graphs G, H with the same number of nodes, the goal is to find a correspondence pi between the nodes of G and H that minimizes some matching error. In this talk, we choose the matching error to be the matrix p-norm of |pi(A_G)-A_H| but focus on the spectral norm / matrix 2-norm which leads to the spectral graph similarity problem. We investigate how this similarity measure behaves and under which restrictions it is efficiently computable or approximable.
14/10/2021 15:00 - 16:00
MSc
Master-Kolloquium Zeno Bitter Title: Weisfeiler–Leman Invariant Induced Subgraph Counts Speaker: Zeno Bitter Time and Place: Thursday, October 14, 15:00, seminar room of chair computer science 7 and on Zoom Please make sure you observe the current RWTH rules for tackling the Covid-19 pandemic when attending the talk in person. You may only participate if you are vaccinated against, tested negative for or recovered from Covid-19. https://rwth.zoom.us/j/98409488429?pwd=YkkycFR5S0N6TGRWeHBiR3FQVDNHUT09 Meeting ID: 984 0948 8429 Passcode: 396495 Abstract: The $k$-dimensional Weisfeiler–Leman ($k$-WL) algorithm is a strong graph invariant which sees wide use in both theoretical and practical algorithms for the Graph Isomorphism Problem (textbf{GI}), and in machine learning applications as a graph kernel. As $k$-WL falls short deciding textbf{GI} for all $k$, it gives rise to a coarser equivalence relation on the class of all graphs based on indistinguishability. In this work we study invariant functions under these equivalence relations, with a focus on induced subgraph counts and small $kin{1,2}$. For the case of $k=1$ we obtain a complete description of the induced subgraphs whose counts are invariant, while for $k=2$ we obtain results for path, cycle and matching graphs. In both cases we match known results for non-induced subgraphs.
12/10/2021 11:15 - 12:00
BSc
The Complexity of Homomorphism Indistinguishability Duc Khuat The foundation of Homomorphism Indistinguishability was laid by Lovász’ Theorem in 1966, stating that a graph is defined up to isomorphism by the number of homomorphism from all graphs to the studied graph and from the studied graphs to all other graphs, respectively. Collecting these numbers in an infinite vector, motivates the notion of homomorphism vectors. Now, as an infinite dimensional vector we define projections onto entries corresponding to a fixed subset of the set of all graphs. We call two graphs homomorphism indistinguishability over this subset if the projection image of the graphs are equal. Strong recent results characterize homomorphism indistinguishability over some natural classes such as the class of planar graphs, class of bounded tree depth and tree width, respectively with well studied notions, combining results of the past forty years with this single framework. In my thesis I provide an overview and a list of references, combining the ideas and the machineries used to establish the recent results but also well known results from the fields of logic, graph theory, combinatorics and quantum and game theory. A proper focus lies on the analysis of complexity of homomorphism indistinguishability. From the characterisations emerging complexity results will be explicated and extended by an algorithm deciding homomorphism in- distinguishability over graphs of bounded tree depth in polynomial time and the fpt-intractability of first order logic of bounded quantifier rank equiva- lence.
12/10/2021 12:00 - 12:45
BSc
Lower Bounds for Learning Logical Concepts Constantin Rettig We study the complexity of learning concepts definable in first-order or monadic second-order logic for relational structures. We introduce a uniform notation for the framework, with which we will remove irregularities among related work. The main focus here lies on the lower bound on the running time for logic learning algorithms. We go over results for string structures, showing that for unary and binary FO formulas there is no consistent learning algorithm running in sublinear time in the size of the structure. For tree structures we show the same results and in addition see that the sublinear bound on logic learning holds for quantifier free formulas. It is shown that for structures with small degree the sublinear time bound holds for logic learning algorithms given local access. After that, we present a section over parameter learning, showing that parameter learning is not possible in sublinear time for structures of small degree. In addition, we show that the parameter learning problem on structures with no degree restrictions is as hard as solving the q-CLIQUE problem on graphs. In the last section we show that concept learning (also in the Probably Approximately Correct (PAC) setting) is as hard as the first-order model-checking problem in the parametrised setting. In the conclusion we sum up the presented results and give a outlook on possible future work.
07/10/2021 10:00 - 11:00
BSc
Graph Neural Networks for MAX-SAT Mert Basaran
[bachelor]
We present RUN-SAT, a novelrecurrent message passing neural network. RUN-SAT learns to approximate MAX-SATin an unsupervised manner. The architecture can be applied to arbitrary CNFformulas. We experimentally evaluate our approach on the SAT and MAX-SATproblems and compare the performance to conventional solvers, heuristics andother neural architectures.
23/09/2021 14:00 - 15:00
Learning on graphs with logic and neural networks Martin Ritzert https://rwth.zoom.us/j/95250295111?pwd=cjhFMGk0bStZcGNvcmYrYURPWnQ0dz09 In the domain of graphs we show strong connections between logic and machine learning in both theory and practice. In a purely theoretical framework we develop sublinear machine learning algorithms for supervised learning of logical formulas on various graph classes. Further we show that learning first-order logic on arbitrary graphs is intractable unless P=NP. At the intersection of theory and practice, we prove an equivalence between graph neural networks and the 1-dimensional Weisfeiler-Leman algorithm. As a practical application, we approximate combinatorial problems with recurrent graph neural networks. The proposed architecture is unsupervised and can be applied to all maximum constraint satisfaction problems.
09/09/2021 11:00 - 11:30
MSc
Nondeterministic Deep Weisfeiler Leman Louis Härtel https://rwth.zoom.us/j/5419503919?pwd=enlnbm1mclNBNkVQZTgvVXR4RTRHZz09
06/09/2021 14:00 - 15:00
BSc
Bachelor-Kolloquium Matthäus Micun Counting and Sampling based on Nondeterministic Logspace Transducers Abstract: Transducers are Turing machines that, instead of deciding problems, compute witnesses. Additionally, non-deterministic Transducers compute relations of witnesses. In this paper, we discuss non-deterministic logspace transducers (NL transducers), as well as their unambiguous version (UL transducers). More specifically, we prove that for any relation computed by an NL transducer, we can enumerate the witnesses of a given word w with polynomial delay, count the number of all witnesses using a fully polynomial randomized approximation scheme (FPRAS), and uniformly generate a witness using a pre-processing polynomial time Las Vegas uniform generator (PPLVUG). Additionally, we connect these properties to non-deterministic finite automata, and prove that the #NFA problem admits an FPRAS.
02/09/2021 15:00 - 16:00
Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs, Daniel Neuen Abstract: Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. In this talk I discuss a framework for obtaining n^{O(sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an n^{O(sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{O(sqrt{k} polylog(k))}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain such (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set.
02/09/2021 15:00 - 16:00
Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs, Daniel Neuen Abstract: Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. In this talk I discuss a framework for obtaining n^{O(sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an n^{O(sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{O(sqrt{k} polylog(k))}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain such (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set.
11/08/2021 15:00 - 15:30
Facility Location and Clustering on Planar and Almost Planar Graphs Sebastian Schaub Masterkolloquium
Abstract: In this thesis we will reflect the current state of research for the uniform facility location problem and k-Clustering in terms of approximability. We will focus our attention on the special case of the planar graph metric, because for the problems with general metric no polynomial-time approximation scheme exist. To illustrate this we will depict and explain four recent results which use different techniques for the analysis of the algorithms, including Voronoi Diagrams, r-divisions and coresets. The first result is an algorithm accuracy analysis for the uniform facility location, where we show that a commonly known local search algorithm is a polynomial-time approximation scheme. The second result is an efficient polynomial-time randomised approximation scheme, where we use an algorithm for the k-Median problem as a subroutine to derive a solution. For the third result we have another polynomial-time approximation scheme with a local search algorithm for the k-Clustering problems k-Median and k-Means. And the fourth result is a fully polynomial-time randomised approximation scheme for the k-Median problem, where the algorithm is based on constructing coresets.
29/07/2021 11:00 - 12:00
Simulation Relations for Symbolic Automata, Robert Funk, Masterkolloquium
29/07/2021 11:00 - 12:00
Simulation Relations for Symbolic Automata, Robert Funk, Masterkolloquium
21/07/2021 10:00 - 11:00
Learning and Minimization of omega-Automata in the Presence of Don’t CareWords, Max Stachon Masterkollquium
The Logical Expressiveness of Graph
Neural Networks Attila Lischka https://rwth.zoom.us/j/95314638975?pwd=bForQjRoZXN1YlhRd29IQlFVQkNuQT09
28/06/2021 12:30 - 13:30
BSc
The Logical Expressiveness of Graph
Neural Networks Attila Lischka https://rwth.zoom.us/j/95314638975?pwd=bForQjRoZXN1YlhRd29IQlFVQkNuQT09
14/06/2021 16:00 - 16:30
A Decomposition-Compatible Canonization Framework for the Graph
Isomorphism Problem Daniel Wiebking https://rwth.zoom.us/j/94470149252?pwd=ZnYwVXQrbStveVdDNDk1V1BlN1lJUT09