
Date
Title

12/11/2020
11:00  11:30
Connectivity and Routing using Graph
Neural Networks
Frorian Frantzen
Graph Neural Networks form a deep learning architecture for machine learning tasks on graphs. Recently, they have been used to obtain heuristics for hard combinatorial problems such as TSP, SAT, or constraint satisfaction problems. The purpose of this thesis is to investigate how such approaches perform on computationally much easier shortest path problems. We will present lower bounds regarding the depth and width of a message passing neural network, which must be fulfilled for such a model to learn the shortest path problem. Then we will evaluate an existing neural network  originally designed for the traveling salesperson problem  for its applicability to the shortest path problem. While this network will fail with insignificant accuracies, these tests will allow us to derive unique challenges of the shortest path problem and which weaknesses in the architecture we need to fix to achieve better results. Based on these results, we will built our own neural network architecture and train it both supervised and unsupervised. We will evaluate this network in terms accuracy, scalability to larger graphs and how well the network generalizes the shortest path problem.

30/10/2020
10:00  11:00
ATI
Flag Algebras in Graph TheoryTim SeppeltFlag algebras as introduced by Razborov represent a powerful tool in extremal combinatorics. This talk will provide a gentle introduction to the framework highlighting applications graph theory. Moreover, limitations of flag algebraic techniques are discussed following the work of Hatami and Norine.

30/10/2020
10:00  11:00
ATI
Flag Algebras in Graph TheoryTim SeppeltFlag algebras as introduced by Razborov represent a powerful tool in extremal combinatorics. This talk will provide a gentle introduction to the framework highlighting applications graph theory. Moreover, limitations of flag algebraic techniques are discussed following the work of Hatami and Norine.

27/10/2020
14:00  14:30
BSc
The FineGrained Complexity of Longest Common Subsequence
Benjamin Stutte
[bachelor]We will examine approaches to finegrained analyses of the Longest Common Subsequence (LCS) problem with special attention to recent results that have proven lower bounds for solving LCS under the Strong Exponential Time Hypothesis. We will first showcase two results, one by Abboud et al. (FOCS’15) and the other by Bringmann et al. (FOCS’15), where subquadratic lower bounds have been proven for the general LCS problem. Later, we turn to Bringmann et al.’s (SODA’18) which examined the optimal running time of multivariate LCS which proved lower bounds that coincide with the running times of the fastest known algorithms.

27/10/2020
14:45  15:15
BSc
Stable and Efficient Algorithms for Logarithmically Counting Homomorphisms from Selected Graph ClassesAnton Florey
Graph homomorphisms are mappings between two graphs H and G that preserve all edge relationsof the lefthand side graph. The graph homomorphism counting problem #Hom(H, G) asks for
the number of homomorphisms from one graph H ∈ H to another graph G ∈ G. It is polynomial
time solvable for certain lefthand graph classes H. As part of his recent master thesis, Maximilian
Merz already provided implementations of various homomorphism counting algorithms. Unfor
tunately, they quickly get impracticable for large problem instances, as homomorphism numbers
grow extremely fast. This work revisits most of these algorithms with the novel idea of counting
the logarithm of these numbers. One main contribution is the implementation and evaluation of
these adapted algorithms. For most of the newly implemented functions, a significant improve
ment in efficiency over the exact counting implementations can be measured. Further experiments
also show that errors of this logarithmic approximation stay sufficiently close to the unavoidable
accuracy loss induced by finite machine precision.
https://rwth.zoom.us/j/95988725888?pwd=NUlaM05VdU5Kdkp0NXVTZHplWlFSQT09

27/10/2020
14:00  14:30
BSc
The FineGrained Complexity of Longest Common Subsequence
Benjamin Stutte
[bachelor]We will examine approaches to finegrained analyses of the Longest Common Subsequence (LCS) problem with special attention to recent results that have proven lower bounds for solving LCS under the Strong Exponential Time Hypothesis. We will first showcase two results, one by Abboud et al. (FOCS’15) and the other by Bringmann et al. (FOCS’15), where subquadratic lower bounds have been proven for the general LCS problem. Later, we turn to Bringmann et al.’s (SODA’18) which examined the optimal running time of multivariate LCS which proved lower bounds that coincide with the running times of the fastest known algorithms.

27/10/2020
14:45  15:15
BSc
Stable and Efficient Algorithms for Logarithmically Counting Homomorphisms from Selected Graph ClassesAnton Florey
Graph homomorphisms are mappings between two graphs H and G that preserve all edge relationsof the lefthand side graph. The graph homomorphism counting problem #Hom(H, G) asks for
the number of homomorphisms from one graph H ∈ H to another graph G ∈ G. It is polynomial
time solvable for certain lefthand graph classes H. As part of his recent master thesis, Maximilian
Merz already provided implementations of various homomorphism counting algorithms. Unfor
tunately, they quickly get impracticable for large problem instances, as homomorphism numbers
grow extremely fast. This work revisits most of these algorithms with the novel idea of counting
the logarithm of these numbers. One main contribution is the implementation and evaluation of
these adapted algorithms. For most of the newly implemented functions, a significant improve
ment in efficiency over the exact counting implementations can be measured. Further experiments
also show that errors of this logarithmic approximation stay sufficiently close to the unavoidable
accuracy loss induced by finite machine precision.
https://rwth.zoom.us/j/95988725888?pwd=NUlaM05VdU5Kdkp0NXVTZHplWlFSQT09

23/10/2020
10:30  11:00
MSc
Detecting Substructures with Graph Neural Networks
Michael Scholkemper
[master]We present theoretical results relating the computational expressiveness of graph neural networks (GNNs) to the color refinement algorithm for graph isomorphism (Morris et al., X et al.). These yield that given the wrong initialisation, graph neural networks are not able to detect triangles on regular graphs. We introduce a refinement algorithm for graph isomorphism that outperforms color refinement on regular graphs and propose a GNNarchitecture motivated by this new algorithm. We experimentally investigate the effect of different initialisations on the detection of triangles and extend this to kcycles and kcliques.

16/10/2020
10:00  11:00
ATI
Learning Concepts Described by Weight Aggregation LogicSteffen van BergeremWe consider weighted structures, which extend ordinary relational structures by assigning weights, i.e. elements from a particular group or ring, to tuples present in the structure. We introduce an extension of firstorder logic that allows to aggregate weights of tuples, compare such aggregates, and use them to build more complex formulas. We provide locality properties of fragments of this logic including FefermanVaught decompositions and a Gaifman normal form for a fragment called FOW1, as well as a localisation theorem for a larger fragment called FOWA1. This fragment can express concepts from various machine learning scenarios. Using the locality properties, we show that concepts definable in FOWA1 over a weighted background structure of at most polylogarithmic degree are agnostically PAClearnable in polylogarithmic time after pseudolinear time preprocessing. This is joint work with Nicole Schweikardt.

13/10/2020
10:00  10:30
BSc
A comparison of translation from LTL to Büchi automata
Anna Maiworm

01/10/2020
10:00  10:45
Bachelor Vortrag JanChristoph Kassing
Vortrag zur Bachelorarbeit: The Recursive Algorithm for Parity Games

01/10/2020
10:00  10:45
Bachelor Vortrag JanChristoph Kassing
Vortrag zur Bachelorarbeit: The Recursive Algorithm for Parity Games

29/09/2020
10:00  10:45
BachelorVortrag Johannes Lehmann
Vortrag zur Bachelorarbeit "Exact Minimization of omegaAutomata"

29/09/2020
10:00  10:45
BachelorVortrag Johannes Lehmann
Vortrag zur Bachelorarbeit "Exact Minimization of omegaAutomata"

25/09/2020
10:30  11:00
MSc
MasterVortrag: Graph Autoencoder for Chemical Compounds
Stefanie Winkler
https://rwth.zoom.us/j/91919735145?pwd=OWFJMDZ5aTErUjhLWEN0T1AwY0lIdz09 A challenging task in fuel design is to find suitable molecules that optimise desired properties like cetane and octane numbers. Our goal is to automate the generation of molecular graphs whose corresponding molecules serve as components for fuels with a high autoignition quality. We use three different neural network models built on variational autoencoders and a generative adversarial network: JTVAE by Jin et al., MHGVAE by Kajino and MolGAN by De Cao and Kipf [1–3]. Using a subset of QM9 for training, we adapt the models to optimise different combinations of the cetane and octane numbers of new molecules through Bayesian optimisation. Our results show that all models are able to produce valid molecules with high cetane and octane numbers. MHGVAE is able to generate most of the highest scoring molecules in the different experiments. Moreover, it creates a lot more unique molecules than the other two models, many of which are easy to synthesise.

25/09/2020
11:15  12:00
BSc
Lower Bounds for the WeisfeilerLeman Dimension of Graphs of Bounded Tree Width
Lea Schirp
The WeisfeilerLeman (WL) algorithm is an iterative approach used to classify graphs and other relational structures. For every natural number k, there is a kdimensional version, which colors ktuples of vertices, running in polynomial time but there are also nonisomorphic graphs, which the kdim version cannot distinguish. This makes it useful to know the WLdimension of a graph, which is the least natural number k such that the kdim WL distinguishes the graph from all other nonisomorphic graphs. It is known that bounds on the WL dimension of a graph can be determined if its tree width is known. In this talk, we present tools for computing the tree width of a graph with a focus on Tamaki's implementation. We finally discuss the results of an experimental evaluation of the tree width of these graphs with the goal of finding out if the currently best known bounds on the WL dimension of graphs parametrized by their tree width are tight.

25/09/2020
12:30  13:00
BSc
Counting Homomorphisms via Model Counting and Knowledge Compilation
Patrick Bögel
The homomorphism counting problem #HOM asks how many homomorphisms there are from a graph H to a graph G. The model counting problem #SAT asks how many satisfying assignments a propositional formula has. Both problems are #Pcomplete, but #HOM becomes tractable if the lefthand side graphs are restricted to a class of bounded treewidth. In this talk we consider reductions from #HOM to #SAT with special attention to whether the tractable subproblems of #HOM are mapped to tractable subproblems of #SAT. Specifically we find reductions that map homomorphism counting instances where the lefthand side graph is a tree, to formulas which adhere to structural restrictions under which #SAT becomes tractable. We also utilize the approach of knowledge compilation to create formulas in a representation that allows for the model count to be calculated in linear time of its size. We evaluate the reductions practically with multiple stateoftheart model counters and find the reduction to be inferior to the direct approach.

18/09/2020
10:00  11:00
ATI
TupleIndependent Representations of Probabilistic Databases
Christoph Standke
https://rwth.zoom.us/j/96525649453?pwd=bHRma0lmV2xuRTNhWUdQbi9ockdNZz09

03/08/2020
12:00  12:30
BSc
Bachelor Kolloquium Meder

28/07/2020
16:00  17:00
Vortrag Wolfgang Gatterbauer

28/07/2020
16:00  17:00
Vortrag Wolfgang Gatterbauer

26/06/2020
10:00  11:00
ATI
ATI Seminar Jan Böker
Jan Böker

19/06/2020
10:00  10:45
ATI
ATI Seminar Vortrag Steffen van Bergerem
Steffen van Bergerem

05/06/2020
10:00  11:00
ATI

29/05/2020
10:00  10:30
ATI
Graph isomorphism in quasipolynomial time parameterized by treewidth
Daniel Wiebking

22/05/2020
10:00  11:00
ATI
The Iteration Number of Colour RefinementSandra KieferThe Colour Refinement procedure and its generalisation to higher dimensions, the WeisfeilerLeman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes G1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n ≥ 10, there are graphs on n vertices on which Colour Refinement requires at least n2 iterations to reach stabilisation. This is joint work with Brendan McKay.

27/02/2020
10:00  10:30
MSc
Unsupervised machine learning for constraint satisfaction problems
Jan Tönshoff

27/02/2020
10:00  10:30
MSc
Unsupervised machine learning for constraint satisfaction problems
Jan Tönshoff

17/01/2020
10:00  11:00
ATI
Generative Datalog with Continuous DistributionsPeter LindnerProbabilistic Databases (PDBs) are a formal model of uncertainty in relational databases, as might occur in a variety of practical application scenarios such as noisy or unreliable input data, data integration or data cleaning. Quite recently, Bárány et al. (TODS 2017) proposed a language called "Probabilistic Programming Datalog (PPDL)" which uses classic Datalog rules that are extended by random sampling. In a nutshell, PPDL is a declarative probabilistic programming language with very close ties to database applications and can be seen as a tool to specify PDBs. In this talk, we focus on the generative part of the language, "Generative Datalog". While the original language of Bárány et al. only supported discrete probability distributions, we allow using probability density functions and inputs that are already PDBs themselves. We present the formal semantics of the language and discuss various properties and consequences, most notably, the support of PDB inputs and robustness with respect to the order of rule applications. This is joint work with M. Grohe, B. L. Kaminski, J.P. Katoen.

15/01/2020
10:00  10:30
MSc
Algorithms for counting homomorphisms from small treewidth graphs
Maximilian Merz

10/01/2020
10:00  11:00
ATI
Isomorphism Testing: From Strings to HypergraphsDaniel NeuenWe consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices $V$ and a permutation group $Gamma$ over domain $V$, and asking whether there is a permutation $gamma in Gamma$ that proves the two hypergraphs to be isomorphic. We show that for input groups, all of whose composition factors are isomorphic to a subgroup of the symmetric group on $d$ points, this problem can be solved in time $(n+m)^{O((log d)^{c})}$ for some absolute constant $c$ where $n$ denotes the number of vertices and $m$ the number of hyperedges. The previous best algorithm for this problem due to Schweitzer and Wiebking (STOC 2019) runs in time $n^{O(d)}m^{O(1)}$.
As an application of this result, we obtain, for example, an algorithm testing isomorphism of graphs excluding $K_{3,h}$ ($h geq 3$) as a minor in time $n^{O((log h)^{c})}$. In particular, this gives an isomorphism test for graphs of Euler genus at most $g$ running in time $n^{O((log g)^{c})}$.

13/12/2019
10:00  11:00
ATI
RUNCSP: Recurrent unsupervised network for CSPsMartin RitzertConstraint satisfaction problems form an important and wide class of combinatorial search and optimization problems with many applications in AI and other areas. We introduce a recurrent neural network architecture RUNCSP (Recurrent Unsupervised Neural Network for Constraint Satisfaction Problems) to train message passing networks solving binary constraint satisfaction problems (CSPs) or their optimization versions (MaxCSP). The architecture is universal in the sense that it works for all binary CSPs: depending on the constraint language, we can automatically design a loss function, which is then used to train generic neural nets. In this paper, we experimentally evaluate our approach for the 3colorability problem (3Col) and its optimization version (Max3Col) and for the maximum 2satisfiability problem (Max2Sat). We also extend the framework to work for related optimization problems such as the maximum independent set problem (MaxIS). Training is unsupervised, we train the network on arbitrary (unlabeled) instances of the problems. Moreover, we experimentally show that it suffices to train on relatively small instances; the resulting message passing network will perform well on much larger instances (at least 10times larger).

29/11/2019
10:00  11:00
ATI
Fractional Sets, Fractional Decompositions, and Fractional TanglesEva Fluck

29/11/2019
10:00  11:00
ATI
Fractional Sets, Fractional Decompositions, and Fractional TanglesEva Fluck

22/11/2019
10:00  11:00
ATI
Ambiguity in Probabilistic Büchi AutomataAnton PirogovProbabilistic Büchi automata are a natural generalization of PFA to infinite words, but have been studied indepth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that goes beyond the regular languages. In this talk I will present new classes of restricted PBA which are still regular, strongly relying on notions concerning ambiguity in classical ωautomata.

20/11/2019
13:15  13:45
MSc
Algorithms for Maximum Matching Width
Yassin Bahloul

20/11/2019
15:00  15:30
BSc
The FineGrained Complexity of FirstOrder Properties
Louis Härtel
Based on the results by Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova and Ryan Williams, we break down the finegrained complexity of firstorder properties by analyzing their reduction from any modelchecking problem on a (k + 1)quantifier firstorder formula to the sparse version of kOrthogonal Vectors, and summarize their algorithmic improvements and consequences for common finegrained conjectures.

15/11/2019
10:00  11:00
ATI

25/10/2019
10:00  11:00
ATI
Tree automata with global constraints for infinite treesPatrick LandwehrWe study an extension of tree automata on infinite trees with global equality and disequality constraints. These constraints can enforce that all subtrees for which in the accepting run a state q is reached (at the root of that subtree) are identical, or that these trees differ from the subtrees at which a state q' is reached. We consider the closure properties of this model, its decision problems and its connection to logic.

24/10/2019
10:00  10:30
BSc
Regular Sensing for Nested Word Automta
Alina Ibach

17/10/2019
10:00  10:30
BSc
Comparing learning algorithms for regular expressions from positive examples
Konrad Ostrowski

17/10/2019
10:45  11:15
BSc
A comparison of algorithms for automata learning on sparse data
Caspar Zecha

16/09/2019
11:00  11:30
The Complexity of FirstOrder Model Checking on Graphs of Bounded Tree Depth
Jonathan du Mesnil de Rochemont
In this talk, we discuss algorithmic metatheorems for graphs of bounded treedepth. TreeDepth is a graph invariant also known as vertex ranking number and minimum elimination tree height, which captures, intuitively speaking, how much a graph resembles a star graph. We present a result due to Chen and Flum stating that the modelchecking problem for FO parameterized by the length of the formula is in paraAC0 if the inputs are limited to any class of graphs of bounded treedepth. paraAC0 can be viewed as the complexity class of parameterized problems that are decidable by polynomialsize constantdepth circuit families with arbitrary fanin after a precomputation on the parameter. An important ingredient in the proof is the following characterization: We show that the modelchecking problem for FO on any class of structures is in paraAC0 if and only if FO has an effective generalized quantifier elimination on that class. We then show that FO has such an effective generalized quantifier elimination on classes of graphs of bounded treedepth to conclude the proof.

16/09/2019
11:45  12:15
Data structures for approximate membership queries
Razvan Manea

09/09/2019
14:00  15:00
Representations of Correlated Probabilistic Databases
Nils Freyer
As an extension of Codd's relational data model, probabilistic databases were discussed in the literature when the relational data model became popular in the 1980's. The studies of probabilistic databases were motivated by errors in the data collection process and designed as a generalisation of the relational data model that is able to integrate probabilistic data into relational data. Today, the amount of data and information is growing strictly, which causes a lot of research in information extraction and efforts in representing the extracted information. One can imagine that representing correlated probabilistic data is not trivial. We will present the most common representation systems for probabilistic data and examine their properties. Afterwards, we will construct translations between the representation systems to draw conclusions on their relationships.

14/06/2019
10:00  10:30
ATI
A unifying method for the design of algorithms canonizing combinatorial objectsDaniel WiebkingWe devise a unified framework for the design of canonization algorithms.
Using hereditarily finite sets, we define a general notion of combinatorial objects
that includes graphs, hypergraphs, relational structures, codes, permutation
groups, tree decompositions, and so on.
Our approach allows for a systematic transfer of the techniques that have been
developed for isomorphism testing to canonization. We use it to design a canonization algorithm for general combinatorial objects. This result gives new fastest canonization algorithms with an asymptotic running time matching the best known isomorphism algorithm for the following types of objects: hypergraphs, hypergraphs of bounded color class size, permutation groups (up to permutational isomorphism)
and codes that are explicitly given (up to code equivalence).

31/05/2019
10:00  11:00
ATI
The Power of the WeisfeilerLeman Algorithm to Decompose GraphsDaniel NeuenThe WeisfeilerLeman procedure is a widelyused approach for graph
isomorphism testing, which iteratively computes an isomorphisminvariant
coloring of vertex tuples. Meanwhile, a fundamental tool in structural
graph theory, which is often exploited in approaches to tackle the graph
isomorphism problem, is the decomposition into bi and triconnected
components.
We prove that the 2dimensional WeisfeilerLeman algorithm implicitly
computes the decomposition of a graph into its triconnected components.
This means that the decomposition into triconnected components is "for
free" with respect to the dimension of the algorithm needed to
distinguish two graphs (assuming dimension at least 2).
This result implies that the kdimensional algorithm distinguishes
kseparators, i.e., ktuples of vertices that separate the graph, from
other vertex ktuples. As a byproduct, we also obtain insights about the
connectivity of constituent graphs of association schemes.
In an application of the results, we show the new upper bound of k on
the WeisfeilerLeman dimension of graphs of treewidth at most k. Using a
construction by Cai, Fürer, and Immerman, we also provide a new lower
bound that is asymptotically tight up to a factor of 2.
This is joint work with Sandra Kiefer.

31/05/2019
10:00  11:00
ATI
The Power of the WeisfeilerLeman Algorithm to Decompose GraphsDaniel NeuenThe WeisfeilerLeman procedure is a widelyused approach for graph
isomorphism testing, which iteratively computes an isomorphisminvariant
coloring of vertex tuples. Meanwhile, a fundamental tool in structural
graph theory, which is often exploited in approaches to tackle the graph
isomorphism problem, is the decomposition into bi and triconnected
components.
We prove that the 2dimensional WeisfeilerLeman algorithm implicitly
computes the decomposition of a graph into its triconnected components.
This means that the decomposition into triconnected components is "for
free" with respect to the dimension of the algorithm needed to
distinguish two graphs (assuming dimension at least 2).
This result implies that the kdimensional algorithm distinguishes
kseparators, i.e., ktuples of vertices that separate the graph, from
other vertex ktuples. As a byproduct, we also obtain insights about the
connectivity of constituent graphs of association schemes.
In an application of the results, we show the new upper bound of k on
the WeisfeilerLeman dimension of graphs of treewidth at most k. Using a
construction by Cai, Fürer, and Immerman, we also provide a new lower
bound that is asymptotically tight up to a factor of 2.
This is joint work with Sandra Kiefer.

24/05/2019
10:00  11:00
The Complexity of Homomorphism IndistinguishabilityJan BökerWe study the complexity of HomInd(F): for a class F of graphs, HomInd(F) denotes the problem of deciding whether two given graphs G and H are homomorphism indistinguishable over F, i.e., whether for every graph F' in F, the number of homomorphisms from F' to G equals the corresponding number from F' to H. We show that there is a polynomialtime decidable class F of graphs of bounded treewidth for which HomInd(F) is undecidable. Our second hardness result concerns the class K of complete graphs: We show that HomInd(K) is coNPhard. In fact, we show that it is complete for the class C=P and, hence, apparently much harder than coNP. We conclude our studies of HomInd(F) with a tractability result: HomInd(P) can be solved in polynomial time for the class P of directed paths. Finally, we briefly study some variants of HomInd(F). This is joint work with Yijia Chen, Martin Grohe, and Gaurav Rattan.

23/05/2019
13:00  14:00
The WeisfeilerLeman Dimension of Graphs of Bounded Treedepth
Luca Oeljeklaus
In this talk we discuss the dimension of the WeisfeilerLeman (WL) algorithm, which is a combinatorial algorithm used as a subroutine for graph isomorphism testing, in terms of treedepth, a graph invariant also referred to as minimum elimination tree height or vertex ranking number. More precisely, we prove upper and lower bounds on the WLdimension of graphs of bounded treedepth by using two results from Cai, Fürer, and Immerman. In our proof to show that every graph of treedepth at most k is identified by the (k1)dimensional WLalgorithm, we use the fact that the (k1)dimensional WLalgorithm identifying a graph is equivalent to Spoiler having a winning strategy for the C_kpebble game between a graph of treedepth at most k and any other nonisomorphic graph. From there we develop an inductive winning strategy for Spoiler over the treedepth of the graph. In our proof to show that there exists a family of pairs of graphs of treedepth k for arbitrarily large k such that the (k/25)dimensional WLalgorithm does not distinguish them, we apply the CFIgraph construction to a family of graphs with large separators and then prove an upper bound on the treedepth of the resulting pairs of graphs.