
Date
Title

27/01/2023
10:30  11:30
ATI
Graph Similarity Based on Matrix NormsTimo GervensQuantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graphbased data. We study the computational complexity of a family of similarity measures based on quantifying the mismatch between the two graphs, that is, the "symmetric difference" of the graphs under an optimal alignment of the vertices. An important example is similarity based on graph edit distance. While edit distance calculates the "global" mismatch, that is, the number of edges in the symmetric difference, our main focus is on "local" measures calculating the maximum mismatch per vertex. Mathematically, our similarity measures are best expressed in terms of the adjacency matrices: the mismatch between graphs is expressed as the difference of their adjacency matrices (under an optimal alignment), and we measure it by applying some matrix norm. Roughly speaking, global measures like graph edit distance correspond to entrywise matrix norms like the Frobenius norm and local measures correspond to operator norms like the spectral norm. We prove a number of strong NPhardness and inapproximability results even for very restricted graph classes such as boundeddegree trees.

16/12/2022
11:30  12:15
BSc
Shapley Value Explanations for Graph Invariants
Jens Breitung
[bachelor] The Shapley value is an attribution function originating in cooperative game
theory that concerns itself with distributing wealth “fairly” among the players
of a cooperative game. Shapley values have been studied in many different
fields, but so far there exists no framework for graphs.
We introduce the Shapley value for graphs where the cooperative games are
defined by integer graph invariants. Since graphs provide a lot of natural struc
ture we study how this structure can be exploited to improve the computation
of Shapley values and how their computational complexity relates to that of the
graph invariants themselves.
While counting problems are at least as hard as their decision variant, we give
evidence that in terms of Shapley value considerations, this relation does not
necessarily hold.

02/12/2022
10:30  11:30
ATI
Approximate Probabilistic Query EvaluationJulia FeithProbabilistic 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 evaluating 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 results from related fields to show that these approximation paradigms give rise to a strict hierarchy under common complexitytheoretic assumptions.
This is work in progress joint with Peter Lindner, Christoph Standke and Martin Grohe

02/12/2022
10:30  11:30
ATI
Approximate Probabilistic Query EvaluationJulia FeithProbabilistic 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 evaluating 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 results from related fields to show that these approximation paradigms give rise to a strict hierarchy under common complexitytheoretic assumptions.
This is work in progress joint with Peter Lindner, Christoph Standke and Martin Grohe

25/11/2022
10:30  11:30
ATI
Some Might Say Sum Is All You NeedEran RosenbluthGraph Neural Networks (GNNs) are a class of algorithms for processing graphs, used in learning tasks on graphs. A GNN is defined as a series of computations on a vertex’s state, interleaved with message passes between the vertex and its neighbors. The computations and message passes procedures are identical for each vertex in any graph – defined once and applied everywhere, making GNNs isomorphisminvariant and inherently scalable algorithms. Each computation (in the series of computations) starts with an aggregation of the vertex’s neighbors’ current state. Specific GNN architectures may differ in various properties, one of which is the aggregation functions they use. A key characteristic of a learning framework is the expressivity of its underlying class of algorithms. There have been several works concerning the effect of the specific aggregation function a GNN architecture uses and that architecture’s expressivity. Although not proving it, some of these works strengthened a belief that Sum aggregation is generally superior (expressivitywise) to other popular aggregations  Mean and Max. We set out to examine that idea. WORK IN PROGRESS . Joint work with Martin Grohe and Jan Toenshoff

18/11/2022
10:30  11:30
ATI
Reconstructing Graphs from Homomorphism CountsTim SeppeltCounting
homomorphism F_i → G from a family of graphs F_1, dots, F_n
has emerged as a promising strategy for extracting properties of a graph
G from a theoretical point of view as well as in applications. In
practice, such homomorphism counts yield a vector embedding of graphs,
which paves the way to using standard machine learning techniques on
graph data. In this talk, the converse question of reconstructing a
graph G from such homomorphism counts is addressed. This problem arises
when attempting to interpret predictions made by machine learning
machineries on vectorembedded graphs. We study the complexity of
reconstruction from homomorphism counts, giving both positive and
negative results.
This is work in progress joint with Jan Böker and Christoph Standke.

14/11/2022
10:00  10:30
BSc
Graph Clustering with GNNs
Soysal Dogukan
[bachelor]Graph Neural Networks with messagepassing networks
perform outstandingly on graph analysis tasks by leveraging higherorder
structural information. The research trend in recent years has given
birth to various GNN architectures. In this thesis, we present and
empirically evaluate a recently proposed GNNbased unsupervised
attributed clustering approach Deep Modularity Networks with carefully
designed experiments. We experiment with different models with several
realworld datasets and evaluate them based on the groundtruth label
correlation and graph clustering quality. The robustness of each model
is further tested with synthetic graphs with different signaltonoise
scenarios. We then analyze the outstanding performance of DMoN across
different metrics compared to four baselines.

14/11/2022
16:00  17:00
Querying Incomplete Numerical Data: Between Certain and Possible Answers
Liat Peterfreund
Queries with aggregation and arithmetic operations, as well as incomplete data, are common in realworld databases, but we lack a good understanding of how they should interact. On the one hand, systems based on SQL provide adhoc rules for numerical nulls, on the other, theoretical research largely concentrates on the standard notions of certain and possible answers which In the presence of numerical attributes and aggregates are often meaningless. In this work, we define a principled compositional framework for databases with numerical nulls and answering queries with arithmetic and aggregations over them. We assume that missing values are given by probability distributions associated with marked nulls, which yields a model of probabilistic bag databases. We concentrate on queries that resemble standard SQL with arithmetic and aggregation and show that they are measurable, and that their outputs have a finite representation. Moreover, since the classical forms of answers provide little information in the numerical setting, we look at the probability that numerical values in output tuples belong to specific intervals. Even though their exact computation is intractable, we show efficient approximation algorithms to compute such probabilities.
The talk is based on joint work with Marco Console and Leonid Libkin, and will be presented in PODS 2023.

11/11/2022
10:30  11:30
ATI
Graph Homomorphisms and Sampling and the Prokhorov MetricJan Böker[ati][speaker=href=
href="https://www.lics.rwthaachen.de/cms/LICS/DerLehrstuhl/Team/WissenschaftlicheMitarbeiterinnenundM/~rrqo/JanBoeker/">"https://www.lics.rwthaachen.de/cms/LICS/DerLehrstuhl/Team/WissenschaftlicheMitarbeiterinnenundM/~rrqo/JanBoeker/"> class="moztxtlinkfreetext"
href="https://www.lics.rwthaachen.de/cms/LICS/DerLehrstuhl/Team/WissenschaftlicheMitarbeiterinnenundM/~rrqo/JanBoeker/">https://www.lics.rwthaachen.de/cms/LICS/DerLehrstuhl/Team/WissenschaftlicheMitarbeiterinnenundM/~rrqo/JanBoeker/]The
tree distance, a variant of the wellknown cut distance from the theory
of graph limits, is a pseudometric on graphs that can be characterized
in
terms of tree homomorphism densities (B. 2021). However, existing
results
are nonquantitative in nature and do not give an understanding
of
why two graphs are similar in the tree distance if their tree
homomorphism
densities are close. We show how tree homomorphism
densities are
closely related to taking samples of the colors the
colorrefinement
algorithm assigns to the vertices of a graph. To
measure the
similarity of such colors in a graph, we use the Prokhorov metric to
define
a pseudometric on graphs that is similar to one proposed by Chen et al.
(2022). Our pseudometric is computable in polynomial time and
induces
the same topology as both the tree distance and tree
homomorphism
densities and, hence, can arguably be seen as the
right way to
turn the colorrefinement algorithm into a distance
measure on
graphs.

11/11/2022
12:00  12:30
BSc
Answering Queries from Substructure Counts
Julius Tischbein
[bachelor]

04/11/2022
10:30  11:30
ATI

04/11/2022
10:30  11:30
ATI

21/10/2022
10:30  11:30
ATI
Analysis of multistage flow shop processing systemsRobin WestermannWe introduce and investigate a simple flow shop model with equivalent jobs passing through a given sequence of stations. The model is characterized by the existence of constraints on the maximum number of jobs on specified sets of stations. Some elementary observations serve to illustrate its dynamics. Our main result is the NPhardness of three central problems: reachability, absence of deadlocks, and determining the optimal throughput for a variant of the model.

14/10/2022
10:30  11:30
ATI
Graph Neural Networks as Fast Global Search Heuristics for Constraint SatisfactionJan Tönshoff[ati][speaker=https://www.lics.rwthaachen.de/cms/LICS/DerLehrstuhl/Team/WissenschaftlicheMitarbeiterinnenundM/~hhxya/JanToenshoff/]We
propose a universal Graph Neural Network architecture which can be
trained as an end2end search heuristic for any Constraint Satisfaction
Problem (CSP). Our architecture can be trained unsupervised with policy
gradient descent to generate problem specific heuristics for any CSP in
a purely data driven manner. The approach is based on a novel graph
representation for CSPs that is both generic and compact and enables us
to process every possible CSP instance with one GNN, regardless of
constraint arity, relations or domain size. Unlike previous RLbased
methods, we operate on a global search action space and allow our GNN to
modify any number of variables in every step of the stochastic search.
This enables our method to properly leverage the inherent parallelism of
GNNs. We perform a thorough empirical evaluation where we learn
heuristics for well known and important CSPs from random data, including
graph coloring, MaxCut, 3SAT and MAXkSAT. Our approach outperforms
prior approaches for neural combinatorial optimization by a substantial
margin. It can compete with, and even improve upon, conventional search
heuristics on test instances that are several orders of magnitude larger
and structurally more complex than those seen during training.

10/10/2022
15:00  15:30
BSc
Motif Counting with Color Coding
Jan Reinhard
[bachelor]A motif is a pattern that occurs more often inside a
graph than it should. Discovering and counting motifs has application
in bioinformatics is computationally hard. We explore the theoretical
background of the underlying problem of subgraph isomorphy. Then we
discuss the color coding method by Alon et al. and adapt it to count
trees and more general graphs of bounded treewidths. These algorithms
are analysed, implemented and and evaluated. We find that color coding
is a useful method to approximately count subgraphs, especially for
graphs of size k ≥ 9.

28/09/2022
11:00  11:30
BSc
Algorithms for Computing Treedepth
Amelie Dittmann
[bachelor] Treedepth is a graph invariant that plays an important role in the structure
theory of sparse graphs. As treedepth is NPhard, there is no polynomialtime
algorithm unless P=NP. Thus there are parameterized algorithms as well as
approximation algorithms. We discuss the current commonstateoftheart
exact algorithm for solving treedepth. This is a functional parameterized
algorithm that runs linearly in the number of vertices and exponential in the
treedepth of the graph.
The Parametrized Algorithms and Computational Experiments (PACE)
challenge 2020 was a competition for implementations of treedepth solvers.
While the challenge evaluated the number of solved instances, we investigate the
functionality of the algorithms in more detail. The key results of the submitted
algorithms are special preprocessing and pruning techniques. For the analysis
we focus on the best solvers submitted to the PACE challenge 2020 and examine
their performance on selected graphs. Finally, we work out the best ways of
preprocessing and pruning used by the algorithms.

28/09/2022
11:00  11:30
BSc
Algorithms for Computing Treedepth
Amelie Dittmann
[bachelor] Treedepth is a graph invariant that plays an important role in the structure
theory of sparse graphs. As treedepth is NPhard, there is no polynomialtime
algorithm unless P=NP. Thus there are parameterized algorithms as well as
approximation algorithms. We discuss the current commonstateoftheart
exact algorithm for solving treedepth. This is a functional parameterized
algorithm that runs linearly in the number of vertices and exponential in the
treedepth of the graph.
The Parametrized Algorithms and Computational Experiments (PACE)
challenge 2020 was a competition for implementations of treedepth solvers.
While the challenge evaluated the number of solved instances, we investigate the
functionality of the algorithms in more detail. The key results of the submitted
algorithms are special preprocessing and pruning techniques. For the analysis
we focus on the best solvers submitted to the PACE challenge 2020 and examine
their performance on selected graphs. Finally, we work out the best ways of
preprocessing and pruning used by the algorithms.

01/09/2022
15:00  16:00
BSc
Arithmetic 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:00
BSc
Arithmetic 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:00
Ensemble 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:45
MSc
Pliability 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:45
MSc
The 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:30
ATI
On the Parameterised Complexity of Learning FirstOrder LogicSteffen van BergeremWe 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:30
ATI
On the Parameterised Complexity of Learning FirstOrder LogicSteffen van BergeremWe 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:30
ATI
Width of Graph DecompositionsEva 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:45
MSc
Hierarchical 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: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 #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:30
ATI
The solidarity cover problemEran RosenbluthVarious 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:30
ATI
Solving AC Power Flow with Graph Neural Networks under Realistic ConstraintsHinrikus WolfWe 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:30
ATI

14/04/2022
13:00  13:45
BSc
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 GNNbased CSP and SAT solvers for the factorisation problem.

01/04/2022
10:30  11:15
MSc
The 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:15
MSc
The 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:30
BSc
Characterising 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:30
MSc
Variants 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:30
BSc
Characterising 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:30
MSc
Variants 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:15
The 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: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 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: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 TimeMoritz LichterIn 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: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 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:00
BSc
The 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:00
ATI
Probabilistic Query Evaluation with Bag SemanticsChristoph 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:00
ATI
Constructing deterministic ωautomata from examples by an extension of the RPNI algorithmLeón BohnThe 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 WalksJan TönshoffGraphs 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:00
ATI
Untangling Gaussian MixturesEva FluckTangles 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:00
ATI
Untangling Gaussian MixturesEva FluckTangles 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:00
ATI
Homomorphism Tensors and Linear EquationsTim SeppeltLová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.