Talks (Archive)
Showing 1  50 of 236 Results

DateTitle

01/09/2022
15:00  16:00BScArithmetic with Bounded Depth Threshold Circuits
Elena Küchle[bachelor]Feedforward neural networks (FNNs) have gained considerable attention in recent years due to their success in dealing with a number of machine learning problems. One way to model such networks is by means of threshold (LT) circuits. Threshold circuits are a wellstudied extension of the traditional model of boolean circuits. However, little to no research has been conducted on the arithmetic of rational numbers using threshold circuits. First, we assess the state of the art knowledge of the basic arithmetic functions on integers with bounded depth LT circuits. In addition, we show that these results also hold for the arithmetic on rationals. Lastly, we approximate nonrational functions, such as the exponential and the natural logarithm functions, using LT circuits. 
01/09/2022
15:00  16:00BScArithmetic with Bounded Depth Threshold Circuits
Elena Küchle[bachelor]Feedforward neural networks (FNNs) have gained considerable attention in recent years due to their success in dealing with a number of machine learning problems. One way to model such networks is by means of threshold (LT) circuits. Threshold circuits are a wellstudied extension of the traditional model of boolean circuits. However, little to no research has been conducted on the arithmetic of rational numbers using threshold circuits. First, we assess the state of the art knowledge of the basic arithmetic functions on integers with bounded depth LT circuits. In addition, we show that these results also hold for the arithmetic on rationals. Lastly, we approximate nonrational functions, such as the exponential and the natural logarithm functions, using LT circuits. 
24/08/2022
14:00  15:00Ensemble Graph Neural Networks for Constraint Satisfaction Problems
Combinatorial optimization is a crucial research area in the field of operations research and computer science. Over the years, there has been a recent surge in solving combinatorial optimization tasks using machine learning and especially Graph Neural Networks (GNNs). Due to their scalability and inherent graphbased design, GNNs present an alternative platform to build largescale combinatorial heuristics. A recent example of this is RUNCSP, which is a highly scalable, heuristic solver for binary MaximumConstraint Satisfaction Problems (MaxCSPs). This thesis aims to empirically evaluate the performance improvement on MaxCSPs like MaxkCOL using ensemble based learning techniques with RUNCSP as their base architecture. 
15/08/2022
10:00  10:45MScPliability and the Approximability of Maximum Constraint Satisfaction Problems
Benedikt Mews
[master] The constraint satisfaction problem (CSP) generalizes several common NPcomplete problems and is therefore computationally hard to solve. It gained interest in the computational complexity community for the many natural ways it can be restricted to achieve tractable problems. For each of these restrictions, the aim is to identify a dichotomy, a property that splits CSPs strictly into the complexity classes NPhard and PTIME. Among these restrictions, this master thesis focuses on the structurally restricted optimization variant of CSP under polynomial time approximation scheme (PTAS)approximation, for which a dichotomy has recently been conjectured.
This potential dichotomy is based on a property called pliability, which describes classes of graphs that are similar to treelike graphs under consideration of valued constraints. Pliability has been found to have several interesting aspects that underline its importance: We can exchange the graph property treewidth in its definition with a few other graph properties and still achieve the exact same graph class, it unifies different graph classes for which previous PTASapproaches were known and it has close connections to other relevant graph properties, namely fragility and hyperfiniteness.
In this talk, we give an overview over the complexity theoretical landscape that surrounds pliability, study the series of results that led up to pliability and put the relevant concepts into relation. Finally, we investigate the computational complexity of recognizing the graph properties that are related to pliability.

13/07/2022
15:00  15:45MScThe Computational Power of Transformer Neural Networks
Lionel Damtew
The Transformer Neural Network Architecture, proposed by Vaswani et al. in 2017, proved to be very successful on machine translation tasks as well as other natural language processing tasks. Pérez, Marinković and Barceló studied the computational power of the transformer neural networks and proved them to be Turing complete under specific circumstances. This thesis presents this proof and studies the restrictions under which transformer neural networks are Turing complete and how their computational power depends on these restrictions, with a focus on the activation function and the precision of the numbers used. It shows how the computational power of the architecture is drastically reduced, when fixed precision numbers are used within the computation of the transformers, such that even some regular languages can not be recognized. Additionally, the computational power of a slightly modified architecture where the precision depends on the input length is analysed. 
01/07/2022
10:30  11:30ATIOn the Parameterised Complexity of Learning FirstOrder Logic
Steffen van Bergerem
We analyse the complexity of learning firstorder queries in a modeltheoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004). Previous research on the complexity of learning in this framework focused on the question of when learning is possible in time sublinear in the background structure. Here we study the parameterised complexity of the learning problem. We have two main results. The first is a hardness result, showing that learning firstorder queries is at least as hard as the corresponding modelchecking problem, which implies that on general structures it is hard for the parameterised complexity class AW[*]. Our second main contribution is a fixedparameter tractable agnostic PAC learning algorithm for firstorder queries over sparse relational data (more precisely, over nowhere dense background structures). 
01/07/2022
10:30  11:30ATIOn the Parameterised Complexity of Learning FirstOrder Logic
Steffen van Bergerem
We analyse the complexity of learning firstorder queries in a modeltheoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004). Previous research on the complexity of learning in this framework focused on the question of when learning is possible in time sublinear in the background structure. Here we study the parameterised complexity of the learning problem. We have two main results. The first is a hardness result, showing that learning firstorder queries is at least as hard as the corresponding modelchecking problem, which implies that on general structures it is hard for the parameterised complexity class AW[*]. Our second main contribution is a fixedparameter tractable agnostic PAC learning algorithm for firstorder queries over sparse relational data (more precisely, over nowhere dense background structures). 
24/06/2022
10:30  11:30ATIWidth of Graph Decompositions
Eva Fluck[ati][speaker=https://www.lics.rwthaachen.de/cms/LICS/DerLehrstuhl/Team/WissenschaftlicheMitarbeiterinnenundM/~ryzs/EvaFluck/]
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, AnnKathrin Elm, Raphael
W. Jacobs, Paul Knappe and Paul Wollan. 
23/06/2022
11:00  11:45MScHierarchical Message Passing for Constraint Satisfaction Problems
Moritz Rösgen
RUNCSP 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 RUNCSP 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 RUNCSP significantly. Neither on instances that were originally used to evaluate RUNCSP nor on instances that we generated with a small treewidth. 
21/06/2022
11:00  11:30BScThe 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:45MScApproximate 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 #Phard even for (some) conjunctive queries. Therefore, new
methods are needed to obtain practical solutions.
We survey the computational complexity of approximately evaluat
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 hardnessofapproximation re
sults from related fields to show that these approximation paradigms
give rise to a strict hierarchy under common complexitytheoretic
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:30ATIThe solidarity cover problem
Eran Rosenbluth
Various realworld 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 *rcover* if and only if ∀s ∈ S ∃s' ∈ S' : d(s, s') ≤ r. We examine the problem of determining whether there exist m disjoint rcovers, naming it the Solidarity Cover Problem (SCP). We consider as well the related optimization problems of maximizing the number of rcovers, 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 partitionsize 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 bicriteriaapproximation 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:30ATISolving 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. 
06/05/2022
10:30  11:30ATIOutoftheordinary ATI talk
Eva Fluck 
14/04/2022
13:00  13:45BScInteger 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 GNNbased CSP and SAT solvers for the factorisation problem. 
01/04/2022
10:30  11:15MScThe Iteration Number of the WeisfeilerLeman Algorithm
Athena Riazsadri
The WeisfeilerLeman (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 kdimensional version of the algorithm. While Lichter et al. (LICS 2019) provided an upper bound of O(n*log n) on the iteration number of 2WL 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 kdimensional 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 2WL and provide a parameterized upper bound on the iteration number of kWL for k>2. 
01/04/2022
10:30  11:15MScThe Iteration Number of the WeisfeilerLeman Algorithm
Athena Riazsadri
The WeisfeilerLeman (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 kdimensional version of the algorithm. While Lichter et al. (LICS 2019) provided an upper bound of O(n*log n) on the iteration number of 2WL 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 kdimensional 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 2WL and provide a parameterized upper bound on the iteration number of kWL for k>2. 
31/03/2022
15:00  15:30BScCharacterising Fragments of FirstOrder Logic by Counting Homomorphisms
Gian Luca Spitzer
Two graphs G, G' are homomorphismindistinguishable 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 homomorphismindistinguishability over the class of graphs of treewidth at most k coincides with logical equivalence in the (k+1)variable fragment of firstorder logic with counting, while homomorphismindistinguishability over the class of graphs of treedepth at most q coincides with equivalence in the quantifierrankq fragment. We introduce the graph parameter of eliminationorder and prove that two graphs are equivalent in the kvariable, quantifierrankq fragment of counting firstorder logic if and only if they are homomorphismindistinguishable over the class of graphs of eliminationorder (k,q). 
31/03/2022
15:45  16:30MScVariants of the WeisfeilerLeman Algorithm
Sebastian Issel[master]The expressiveness of different variants of the kdimensional WeisfeilerLeman 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 SheraliAdams relaxation for integer linear programming. 
31/03/2022
15:00  15:30BScCharacterising Fragments of FirstOrder Logic by Counting Homomorphisms
Gian Luca Spitzer
Two graphs G, G' are homomorphismindistinguishable 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 homomorphismindistinguishability over the class of graphs of treewidth at most k coincides with logical equivalence in the (k+1)variable fragment of firstorder logic with counting, while homomorphismindistinguishability over the class of graphs of treedepth at most q coincides with equivalence in the quantifierrankq fragment. We introduce the graph parameter of eliminationorder and prove that two graphs are equivalent in the kvariable, quantifierrankq fragment of counting firstorder logic if and only if they are homomorphismindistinguishable over the class of graphs of eliminationorder (k,q). 
31/03/2022
15:45  16:30MScVariants of the WeisfeilerLeman Algorithm
Sebastian Issel[master]The expressiveness of different variants of the kdimensional WeisfeilerLeman 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 SheraliAdams relaxation for integer linear programming. 
25/03/2022
10:30  11:15The Expressiveness of Convolutions and Random Walks in Graph Learning//Fabian Bender
In the field of graphlearning, the wellknown WeisfeilerLeman 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 realworld 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 standardmessagepassing architectures as well as higherlevel approaches. 
18/03/2022
10:30  11:15BScQuery 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 firstorder 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 firstorder sentences using a novel Skolemization algorithm, which retains the model count of a firstorder 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 firstorder 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:15BScThe 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:30ATISeparating 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 fixedpoint 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:00ATIBlind 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 wellknown WeisfeilerLehman (color refinement) algorithm. Second, we generalize this idea to a setting where we only observe the outputs to random, lowrank excitations of the graph filter, and present a simple spectral algorithm to extract the relevant equitable partitions. 
27/01/2022
15:00  16:00BScThe Logical Strength of Graph Neural Networks on Knowledge Graphs
Fabian Hamm
Abstract The 1dimensional Weisfeiler–Leman algorithm and graph neural networks (GNNs) have prominently been defined on undirected non edgelabeled vertexlabeled 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 edgelabeled graphs, which are also known as knowledge graphs. 
21/01/2022
10:00  11:00ATIProbabilistic Query Evaluation with Bag Semantics
Christoph Standke
[ati][speaker=https://www.lics.rwthaachen.de/cms/LICS/DerLehrstuhl/Team/WissenschaftlicheMitarbeiterinnenundM/~fvvzk/ChristophStandke/]
Typically, probabilistic databases (PDBs) are probability distributions over the subsets of a finite set of facts. The problem of evaluating a query on such setPDBs, known as probabilistic query evaluation, is wellunderstood for unions of conjunctive queries (UCQs): it is either in polynomial time, or #Phard (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 setversion. This talk will give an introduction to probabilistic query evaluation. We start by reviewing the case of setPDBs and then present current results on querying bagPDBs. This is joint work with Martin Grohe and Peter Lindner. 
17/12/2021
10:00  11:00ATIConstructing 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:00ATIGraph 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 graphstructured 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 stateoftheart GNN architectures across a multitude of benchmark datasets for graph learning. 
03/12/2021
10:00  11:00ATIUntangling 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. Realworld 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:00ATIUntangling 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. Realworld 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:00ATIHomomorphism 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 linearalgebraic and representationtheoretic 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:15ATIThe Effects of Randomness on the Stability of Node Embeddings
Hinrikus Wolf
We systematically evaluate the (in)stability of stateoftheart 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:00Graph 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 wellknown 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:00ATIWeisfeilerLeman 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 kdimensional WeisfeilerLeman algorithm is a more powerful generalization of color refinement that colors ktuples instead of single vertices. We show how indistinguishability by the $k$dimensional WeisfeilerLeman algorithm generalizes from graphs to graphons. 
29/10/2021
10:00  11:00ATISpectral 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 pnorm of pi(A_G)A_H but focus on the spectral norm / matrix 2norm 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:00MScMasterKolloquium 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 Covid19 pandemic when attending the talk in person. You may only participate if you are vaccinated against, tested negative for or recovered from Covid19. 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 noninduced subgraphs. 
12/10/2021
11:15  12:00BScThe 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 fptintractability of first order logic of bounded quantifier rank equiva lence. 
12/10/2021
12:00  12:45BScLower Bounds for Learning Logical Concepts
Constantin Rettig
We study the complexity of learning concepts definable in firstorder or monadic secondorder 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 qCLIQUE 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 firstorder modelchecking 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:00BScGraph Neural Networks for MAXSAT
Mert Basaran[bachelor]
We present RUNSAT, a novelrecurrent message passing neural network. RUNSAT learns to approximate MAXSATin an unsupervised manner. The architecture can be applied to arbitrary CNFformulas. We experimentally evaluate our approach on the SAT and MAXSATproblems and compare the performance to conventional solvers, heuristics andother neural architectures.

23/09/2021
14:00  15:00Learning 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 firstorder 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 1dimensional WeisfeilerLeman 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:30MScNondeterministic Deep Weisfeiler Leman
Louis Härtel
https://rwth.zoom.us/j/5419503919?pwd=enlnbm1mclNBNkVQZTgvVXR4RTRHZz09 
06/09/2021
14:00  15:00BScBachelorKolloquium Matthäus Micun
Counting and Sampling based on Nondeterministic Logspace Transducers Abstract: Transducers are Turing machines that, instead of deciding problems, compute witnesses. Additionally, nondeterministic Transducers compute relations of witnesses. In this paper, we discuss nondeterministic 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 preprocessing polynomial time Las Vegas uniform generator (PPLVUG). Additionally, we connect these properties to nondeterministic finite automata, and prove that the #NFA problem admits an FPRAS. 
02/09/2021
15:00  16:00Parameterized 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 2connected 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 2connected 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 wellstudied 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:00Parameterized 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 2connected 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 2connected 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 wellstudied 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:30Facility Location and Clustering on Planar and Almost Planar Graphs
Sebastian Schaub
Masterkolloquium
ZoomMeeting beitreten
https://rwth.zoom.us/j/99375584947?pwd=UVNSaTBNRm1qL2ZneDExWVVZUUxKZz09
MeetingID: 993 7558 4947
Kenncode: 600407
Abstract: In this thesis we will reflect the current state of research for the uniform facility location problem and kClustering 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 polynomialtime 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, rdivisions 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 polynomialtime approximation scheme. The second result is an efficient polynomialtime randomised approximation scheme, where we use an algorithm for the kMedian problem as a subroutine to derive a solution. For the third result we have another polynomialtime approximation scheme with a local search algorithm for the kClustering problems kMedian and kMeans. And the fourth result is a fully polynomialtime randomised approximation scheme for the kMedian problem, where the algorithm is based on constructing coresets. 
29/07/2021
11:00  12:00Simulation Relations for Symbolic Automata, Robert Funk, Masterkolloquium 
29/07/2021
11:00  12:00Simulation Relations for Symbolic Automata, Robert Funk, Masterkolloquium 
21/07/2021
10:00  11:00Learning and Minimization of omegaAutomata in the Presence of Don’t CareWords, Max Stachon
Masterkollquiumhttps://rwth.zoom.us/j/93883134873?pwd=Y1lKYXpEZHBlaHlmUWtHSG9VQ1M5Zz09