01/09/2022
15:00 - 16:00

BSc

Arithmetic with Bounded Depth Threshold Circuits
Elena Küchle
[bachelor]Feed-forward 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 well-studied 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 non-rational 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]Feed-forward 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 well-studied 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 non-rational functions, such as the exponential and the natural logarithm functions, using LT circuits.

24/08/2022
14:00 - 15:00

 

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 NP-complete 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 NP-hard 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 tree-like 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 PTAS-approaches 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 First-Order Logic
Steffen van Bergerem
We analyse the complexity of learning first-order queries in a model-theoretic 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 first-order queries is at least as hard as the corresponding model-checking problem, which implies that on general structures it is hard for the parameterised complexity class AW[*]. Our second main contribution is a fixed-parameter tractable agnostic PAC learning algorithm for first-order 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 First-Order Logic
Steffen van Bergerem
We analyse the complexity of learning first-order queries in a model-theoretic 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 first-order queries is at least as hard as the corresponding model-checking problem, which implies that on general structures it is hard for the parameterised complexity class AW[*]. Our second main contribution is a fixed-parameter tractable agnostic PAC learning algorithm for first-order queries over sparse relational data (more precisely, over nowhere dense background structures).

24/06/2022
10:30 - 11:30

ATI

23/06/2022
11:00 - 11:45

MSc

Hierarchical Message Passing for Constraint Satisfaction Problems
Moritz Rösgen
RUN-CSP is a graph neural network solving optimization problems modelled as constraint satisfaction problems (CSPs) by performing message passing on the graph representation of said problems. It is a generic architecture that can be trained unsupervised on any binary CSPs. We introduce an extension for RUN-CSP that additionally performs message passing on the tree decomposition of the input graph. Our goal is to use a tree decomposition that captures the global structure of the graph and allow messages to be passed through the graph in less steps. To this end we experiment with different algorithms for computing tree decompositions. In these experiments we compare our extension with the original architecture. It shows that we were not able to improve the results of RUN-CSP significantly. Neither on instances that were originally used to evaluate RUN-CSP nor on instances that we generated with a small treewidth.

21/06/2022
11:00 - 11:30

BSc

The Complexity of Counting Small Patterns in Graphs and Relational Structures
Daniel Quirmbach
In der Präsentation wird die Komplexität des Zählens von Mustern auf Graphen und relationalen Strukturen untersucht. Hierzu wird das Konzept der Graphmotivparameter vorgestellt, um eine geschlossene Vorgehensweise für die Komplexitätsabschätzung der Zählprobleme #Hom, #Sub und #IndSub zu erhalten, die entweder die Anzahl an Homomorphismen oder an (induzierten) Teilgraphen eines Musters H zu beziehungsweise auf einem Graphen G zählen sollen. Ausgehend vom Dichotomiecharakters der Komplexität vom Problem #Hom untersuchen wir die Komplexität von Linearkombinationen von Problemen in #Hom. Durch eine Darstellung der Probleme #Sub und #IndSub als Linearkombinationen von Homomorphismenproblemen erhalten wir auch eine Dichotomie für diese Klassen. Wir erweitern die Idee der Graphmotivparameter auf relationale Strukturen und zeigen mithilfe einer Dichotomie des Problems $#Hom$ für relationale Strukturen, dass auch die Probleme #Sub und #IndSub durch ihre Darstellung als Linearkombination von Problemen in #Hom immer entweder in polynomieller Zeit lösbar oder #W[1]-schwer sind. Zudem identifizieren wir anhand der Baumweite ein Dichotomiekriterium, welches uns ermöglicht einzelne Probleminstanzen einer der beiden oben genannter Komplexitätsklassen zuzuordnen.

23/05/2022
11:00 - 11:45

MSc

Approximate Probabilistic Query Evaluation
Oliver Feith
[master]Probabilistic databases model uncertain data as a probability space
over traditional relational databases. Evaluating queries in probabilistic
databases hence requires computing confidences for the answers,
which is #P-hard even for (some) conjunctive queries. Therefore, new
methods are needed to obtain practical solutions.
We survey the computational complexity 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 hardness-of-approximation re-
sults from related fields to show that these approximation paradigms
give rise to a strict hierarchy under common complexity-theoretic
assumptions: While exact evaluation is tractable for only select con-
junctive queries, the class of (unions of) conjunctive queries admits a
multiplicative FPRAS. However, we identify other seemingly simple
queries which resist multiplicatively approximate evaluation entirely.
By contrast, all queries can be evaluated using an additive FPRAS.

20/05/2022
10:30 - 11:30

ATI

The solidarity cover problem
Eran Rosenbluth
Various real-world problems consist of partitioning a set of locations into disjoint subsets such that each subset covers the whole set with a certain radius. Given a finite set S, a metric d, and a radius r, define a subset S' ⊆ S to be an *r-cover* if and only if ∀s ∈ S ∃s' ∈ S' : d(s, s') ≤ r. We examine the problem of determining whether there exist m disjoint r-covers, naming it the Solidarity Cover Problem (SCP). We consider as well the related optimization problems of maximizing the number of r-covers, referred to as the partition size, and minimizing the radius. We analyze the relation between the SCP and a graph problem known as the Domatic Number Problem (DNP), both hard problems in the general case. We show that the SCP is hard already in the Euclidean 2D setting, implying hardness of the DNP already in the unit disc graph setting. As far as we know, the latter is a result yet to be shown. We use the tight approximation bound of (1 + o(1))ln(n) for the DNP’s general case, shown by U. Feige, M. Halldórsson, G. Kortsarz, and A. Srinivasan (SIAM 15 Journal on computing, 2002), to deduce the same bound for partition-size approximation of the SCP in the Euclidean space setting. We show an upper bound of 3 and lower bounds of 2 and √2 for approximating the minimal radius in different settings of the SCP. Lastly, in the Euclidean 2D setting we provide a bicriteria-approximation of ( 1/16, 2) for the partition size and radius respectively. Joint work with Britta Peis and Laura Vargas Koch.

13/05/2022
10:30 - 11:30

ATI

Solving AC Power Flow with Graph Neural Networks under Realistic Constraints
Hinrikus Wolf
We propose a graph neural network architecture solving the AC power flow problem under realistic constraints. While the energy transition is changing the energy industry to a digitalized and decentralized energy system, the challenges are increasingly shifting to the distribution grid level to integrate new loads and generation technologies. To ensure a save and resilient operation of distribution grids, AC power flow calculations are the means of choice to determine grid operating limits or analyze grid asset utilization in planning procedures. In our approach we demonstrate the development of a framework which makes use of graph neural networks to learn the physical constraints of the power flow. We present our model architecture on which we perform unsupervised training to learn a general solution of the AC power flow formulation that is independent of the specific topologies and supply tasks used for training. Finally, we demonstrate, validate and discuss our results on medium voltage benchmark grids.

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 GNN-based CSP and SAT solvers for the factorisation problem.

01/04/2022
10:30 - 11:15

MSc

The Iteration Number of the Weisfeiler-Leman Algorithm
Athena Riazsadri
The Weisfeiler-Leman (WL) algorithm is a simple combinatorial algorithm with widespread applications, most prominently as a subroutine for competitive graph isomorphism solvers. The number of iterations until it reaches termination is crucial for the parallelized running time of the algorithm. For each integer k, there is a k-dimensional version of the algorithm. While Lichter et al. (LICS 2019) provided an upper bound of O(n*log n) on the iteration number of 2-WL on input graphs of order n, there have been no improvements over the trivial upper bound of O(n^k) on the iteration number of the k-dimensional version of the algorithm for k>2 and input graphs of order n. We will present the proof to the currently best known upper bound of O(n*log n) on the iteration number of 2-WL and provide a parameterized upper bound on the iteration number of k-WL for k>2.

01/04/2022
10:30 - 11:15

MSc

The Iteration Number of the Weisfeiler-Leman Algorithm
Athena Riazsadri
The Weisfeiler-Leman (WL) algorithm is a simple combinatorial algorithm with widespread applications, most prominently as a subroutine for competitive graph isomorphism solvers. The number of iterations until it reaches termination is crucial for the parallelized running time of the algorithm. For each integer k, there is a k-dimensional version of the algorithm. While Lichter et al. (LICS 2019) provided an upper bound of O(n*log n) on the iteration number of 2-WL on input graphs of order n, there have been no improvements over the trivial upper bound of O(n^k) on the iteration number of the k-dimensional version of the algorithm for k>2 and input graphs of order n. We will present the proof to the currently best known upper bound of O(n*log n) on the iteration number of 2-WL and provide a parameterized upper bound on the iteration number of k-WL for k>2.

31/03/2022
15:00 - 15:30

BSc

Characterising Fragments of First-Order Logic by Counting Homomorphisms
Gian Luca Spitzer
Two graphs G, G' are homomorphism-indistinguishable over a class S of graphs if for each F in S, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'. Results by Dvořák (2010) and Grohe (2020) show that homomorphism-indistinguishability over the class of graphs of tree-width at most k coincides with logical equivalence in the (k+1)-variable fragment of first-order logic with counting, while homomorphism-indistinguishability over the class of graphs of tree-depth at most q coincides with equivalence in the quantifier-rank-q fragment. We introduce the graph parameter of elimination-order and prove that two graphs are equivalent in the k-variable, quantifier-rank-q fragment of counting first-order logic if and only if they are homomorphism-indistinguishable over the class of graphs of elimination-order (k,q).

31/03/2022
15:45 - 16:30

MSc

Variants of the Weisfeiler-Leman Algorithm
Sebastian Issel
[master]The expressiveness of different variants of the k-dimensional Weisfeiler-Leman algorithm and related concepts is compared. The relation of the classical coloring, the bijective pebble game and counting logics will be generalized to these variants with similar results.The variants are obtained by relaxing the coloring of tuples to sets or multisets ofvertices. This reduces the needed memory to calculate the coloring. Some upper and lower bounds of their expressiveness, compared to the classical version, are shown. As an additional viewpoint, a linear equation system will be defined which turns out to be solvable precisely if the algorithm cannot differentiate the graphs. This system stems from an adaptation of the Sherali-Adams relaxation for integer linear programming.

31/03/2022
15:00 - 15:30

BSc

Characterising Fragments of First-Order Logic by Counting Homomorphisms
Gian Luca Spitzer
Two graphs G, G' are homomorphism-indistinguishable over a class S of graphs if for each F in S, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'. Results by Dvořák (2010) and Grohe (2020) show that homomorphism-indistinguishability over the class of graphs of tree-width at most k coincides with logical equivalence in the (k+1)-variable fragment of first-order logic with counting, while homomorphism-indistinguishability over the class of graphs of tree-depth at most q coincides with equivalence in the quantifier-rank-q fragment. We introduce the graph parameter of elimination-order and prove that two graphs are equivalent in the k-variable, quantifier-rank-q fragment of counting first-order logic if and only if they are homomorphism-indistinguishable over the class of graphs of elimination-order (k,q).

31/03/2022
15:45 - 16:30

MSc

Variants of the Weisfeiler-Leman Algorithm
Sebastian Issel
[master]The expressiveness of different variants of the k-dimensional Weisfeiler-Leman algorithm and related concepts is compared. The relation of the classical coloring, the bijective pebble game and counting logics will be generalized to these variants with similar results.The variants are obtained by relaxing the coloring of tuples to sets or multisets ofvertices. This reduces the needed memory to calculate the coloring. Some upper and lower bounds of their expressiveness, compared to the classical version, are shown. As an additional viewpoint, a linear equation system will be defined which turns out to be solvable precisely if the algorithm cannot differentiate the graphs. This system stems from an adaptation of the Sherali-Adams relaxation for integer linear programming.

25/03/2022
10:30 - 11:15

 

18/03/2022
10:30 - 11:15

BSc

Query Evaluation in Symmetric Probabilistic Databases
Adrian Voß
[bachelor]
 
In 2011 van den Broeck et al. proposed an algorithm which is able to compute the symmetric weighted model count of a first-order sentence in CNF, which is effectively a probabilistic inference problem. In their subsequent research, van den Broeck et al. showed that their method is guaranteed to solve the problem in polynomial time for sentences with a most 2 logical variables. The algorithm can be applied to arbitrary first-order sentences using a novel Skolemization algorithm, which retains the model count of a first-order sentence. The naturally arising question about sentences with at least 3 variables has been answered negatively by Suciu et al. 2015. In 2014 van den Broeck et al. also claimed that their algorithm is applicable to symmetric probabilistic databases, for which it solves the query evaluation problem in polynomial time. In this thesis we expand on the latter and construct the relation between first-order models and probabilistic databases. We build a cohesive algorithm from the various sources, expand the descriptions from the original papers to detailed proofs and give examples which illustrate the application of the method, such that the algorithm can be used in probabilistic database applications directly.

11/03/2022
10:30 - 11:15

BSc

The Real Complexity of Query Evaluation in Probabilistic Databases
János Arpasi
[bachelor]Abstract:
 
Probabilistic databases constitute probability distributions over relational databases. Of great interest for research have been the tuple independent probabilistic databases, where it was proven that for every UCQ that the evaluation problem is either computable in polynomial time or #P hard, but until now this always assumed all occurring probabilities are rational, so the case for arbitrary real numbers was not sorted out yet. We will therefore give an introduction into computable real numbers and functions, review some complexity theory for continuous data and show that the dichotomy holds true also for real numbers.

11/02/2022
10:30 - 11:30

ATI

Separating Rank Logic from Polynomial Time
Moritz Lichter
In the search for a logic capturing polynomial time the most promising candidates are Choiceless Polynomial Time (CPT) and rank logic. Rank logic extends fixed-point logic with counting by a rank operator over prime fields. In this talk I will discuss a recent construction that is a variant of the so called CFI graphs that defines them over Z_{2^i} rather than Z_2. The isomorphism problem of these CFI graphs over Z_{2^i} cannot be defined in rank logic, even if the base graph is totally ordered. However, CPT can define this isomorphism problem. The argument therefore separates rank logic from CPT and in particular from polynomial time. The key idea to argue that rank logic does not define the isomorphism problem of CFI graphs over Z_{2^i} constructs matrices over CFI graphs. These show that certain sequences of other matrices are simultaneously similar. I will also discuss arising challenges and hint at their solutions providing overall overview of the arguments, in particular of the construction of said matrices.

28/01/2022
10:00 - 11:00

ATI

Blind Extraction of Equitable Partitions From Graph Signals
Michael Scholkemper
Finding equitable partitions is closely related to the extraction of graph symmetries and of interest in a variety of applications such as node role detection, cluster synchronization, consensus dynamics, and network control problems. In this work we study a blind identification problem in which we aim to recover an equitable partition of a network without the knowledge of the network's edges but based solely on the observations of the outputs of an unknown graph filter. Specifically, we consider two settings. First, we consider a scenario in which we can control the input to the graph filter and present a method to extract the partition inspired by the well-known Weisfeiler-Lehman (color refinement) algorithm. Second, we generalize this idea to a setting where we only observe the outputs to random, low-rank excitations of the graph filter, and present a simple spectral algorithm to extract the relevant equitable partitions.

27/01/2022
15:00 - 16:00

BSc

The Logical Strength of Graph Neural Networks on Knowledge Graphs
Fabian Hamm
Abstract The 1-dimensional Weisfeiler–Leman algorithm and graph neural networks (GNNs) have prominently been defined on undirected non edge-labeled vertex-labeled graphs. It has been shown that they hold the same expressiveness when it comes to distinguishing graphs, which can also be defined in terms of the logic C_2, the first order logic with counting quantifiers and two variables. This talk will recapitulate this and other results, as well as extend them to directed edge-labeled graphs, which are also known as knowledge graphs.

21/01/2022
10:00 - 11:00

ATI

Probabilistic Query Evaluation with Bag Semantics
Christoph Standke

17/12/2021
10:00 - 11:00

ATI

Constructing deterministic ω-automata from examples by an extension of the RPNI algorithm
León Bohn
The RPNI algorithm (Oncina, Garcia 1992) constructs deterministic finite automata from finite sets of negative and positive example words. We propose and analyze an extension of this algorithm to deterministic ω-automata with different types of acceptance conditions. In order to obtain this generalization of RPNI, we develop algorithms for the standard acceptance conditions of ω-automata that check for a given set of example words and a deterministic transition system, whether these example words can be accepted in the transition system with a corresponding acceptance condition. Based on these algorithms, we can define the extension of RPNI to infinite words. We prove that it can learn all deterministic ω-automata with an informative right congruence in the limit with polynomial time and data. We also show that the algorithm, while it can learn some automata that do not have an informative right congruence, cannot learn deterministic ω-automata for all regular ω-languages in the limit. Finally, we also prove that active learning with membership and equivalence queries is not easier for automata with an informative right congruence than for general deterministic ω-automata.

10/12/2021
10:00 - 11:00

ATI

Graph Learning with 1D Convolutions on Random Walks
Jan Tönshoff
Graphs are a very general form of data that naturally occurs across a wide range of applications, from cheminformatics to social network analysis. Due to this ubiquity, Machine Learning on graph-structured data is both crucial and challenging. We propose CRaWl (CNNs for Random Walks), a novel neural network architecture for graph learning. It is based on processing sequences of small subgraphs induced by random walks with standard 1D CNNs. Thus, CRaWl is fundamentally different from typical message passing graph neural network architectures. It is inspired by techniques counting small subgraphs, such as the graphlet kernel and motif counting, and combines them with random walk based techniques in a highly efficient and scalable neural architecture. CRaWl is not constraint by the well known limitations of the standard message passing framework, which currently dominates graph learning. In particular, it can detect arbitrary substructures up to a chosen window size. We demonstrate empirically that CRaWl matches or outperforms state-of-the-art GNN architectures across a multitude of benchmark datasets for graph learning.

03/12/2021
10:00 - 11:00

ATI

Untangling Gaussian Mixtures
Eva Fluck
Tangles were originally introduced as a concept to formalize regions of high connectivity in graphs. In recent years, they were also discovered as a link between structural graph theory and data science: when interpreting similarity in data sets as connectivity between points, finding clusters in the data sets essentially amounts to finding tangles in the underlying graphs. This talk further explores the potential of tangles in data sets as a means for a formal study of clusters. Real-world data often follow a normal distribution. Accounting for this, we develop a quantitative theory of tangles in data sets drawn from Gaussian mixtures. To this end, we equip the data with a graph structure that models similarity between the points and allows to interpret the graph tangles as clusters in the data. We provide explicit conditions under which tangles associated with the marginal Gaussian distributions exist asymptotically almost surely. This is joint work with Sandra Kiefer and Christoph Standke.

03/12/2021
10:00 - 11:00

ATI

Untangling Gaussian Mixtures
Eva Fluck
Tangles were originally introduced as a concept to formalize regions of high connectivity in graphs. In recent years, they were also discovered as a link between structural graph theory and data science: when interpreting similarity in data sets as connectivity between points, finding clusters in the data sets essentially amounts to finding tangles in the underlying graphs. This talk further explores the potential of tangles in data sets as a means for a formal study of clusters. Real-world data often follow a normal distribution. Accounting for this, we develop a quantitative theory of tangles in data sets drawn from Gaussian mixtures. To this end, we equip the data with a graph structure that models similarity between the points and allows to interpret the graph tangles as clusters in the data. We provide explicit conditions under which tangles associated with the marginal Gaussian distributions exist asymptotically almost surely. This is joint work with Sandra Kiefer and Christoph Standke.

26/11/2021
10:00 - 11:00

ATI

Homomorphism Tensors and Linear Equations
Tim Seppelt
Lovász (1967) showed that two graphs $G$ and $H$ are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph $F$, the number of homomorphisms from $F$ to $G$ equals the number of homomorphisms from $F$ to $H$. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalence and algebraic equation systems. In this talk, a unified algebraic framework for such results is introduced by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. This is joint work with Martin Grohe and Gaurav Rattan.

19/11/2021
14:15 - 15:15

ATI

The Effects of Randomness on the Stability of Node Embeddings
Hinrikus Wolf
We systematically evaluate the (in-)stability of state-of-the-art node embedding algorithms due to randomness, i.e., the random variation of their outcomes given identical algorithms and networks. We ap- ply five node embeddings algorithms—HOPE, LINE, node2vec, SDNE, and GraphSAGE—to assess their stability under randomness with respect to their performance in downstream tasks such as node classification and link prediction. We observe that while the classification of individual nodes can differ substantially, the overall accuracy is mostly unaffected by the geometric instabilities in the underlying embeddings. In link prediction, we also observe high stability in the overall accuracy and a higher stability in individual predictions than in node classification. While our work highlights that the overall performance of downstream tasks is largely unaffected by randomness in node embeddings, we also show that individual predictions might be dependent solely on randomness in the underlying embeddings. Our work is relevant for researchers and engineers interested in the effectiveness, reliability, and reproducibility of node embedding approaches.

11/11/2021
13:00 - 14:00

 

Graph Embeddings Based on Homomorphism Counts
Pascal Kühner
A graph homomorphism is a mapping from the nodes of one graph F to the nodes of another graph G. The number of homomorphisms from each graph F in a fixed set F to an arbitrary graph G can be used as a graph embedding for G. We can make many statements on graph similarity (e.g. fractional isomorphisms) if F is fixed to certain natural graph classes as trees, cycles or paths. This makes these embeddings an interesting option in a machine learning context. Within this thesis, we explore these embeddings and conduct various experiments on graph classification, node classification and graph regression tasks. These experiments show, that these embeddings can achieve similar performance as well-known graph kernels on many of these machine learning tasks. Yet, practicability of homomorphism count embeddings remains questionable, as they can be hardly computed on bigger graphs and in addition there are problems with embedding additional information as node labels or edge features.

05/11/2021
10:00 - 11:00

ATI

Weisfeiler-Leman Indistinguishability of Graphons
Jan Böker
The color refinement algorithm is mainly known as a heuristic for graph isomorphism. It computes a coloring of the vertices of a graph, and if these colorings of two graphs do not match, they cannot be isomorphic. Indistinguishability by the color refinement algorithm can be characterized in various different ways, e.g., fractional isomorphism or tree homomorphism counts, and has recently been generalized from graphs to graphons, a natural notion for the limit of a sequence of graphs (Grebík and Rocha, 2021). The k-dimensional Weisfeiler-Leman algorithm is a more powerful generalization of color refinement that colors k-tuples instead of single vertices. We show how indistinguishability by the $k$-dimensional Weisfeiler-Leman algorithm generalizes from graphs to graphons.

29/10/2021
10:00 - 11:00

ATI

Spectral Graph Similarity
Timo Gervens
The graph similarity problem is an optimization version of the graph isomorphism problem. Given two graphs G, H with the same number of nodes, the goal is to find a correspondence pi between the nodes of G and H that minimizes some matching error. In this talk, we choose the matching error to be the matrix p-norm of |pi(A_G)-A_H| but focus on the spectral norm / matrix 2-norm which leads to the spectral graph similarity problem. We investigate how this similarity measure behaves and under which restrictions it is efficiently computable or approximable.

14/10/2021
15:00 - 16:00

MSc

Master-Kolloquium Zeno Bitter
Title: Weisfeiler–Leman Invariant Induced Subgraph Counts Speaker: Zeno Bitter Time and Place: Thursday, October 14, 15:00, seminar room of chair computer science 7 and on Zoom Please make sure you observe the current RWTH rules for tackling the Covid-19 pandemic when attending the talk in person. You may only participate if you are vaccinated against, tested negative for or recovered from Covid-19. https://rwth.zoom.us/j/98409488429?pwd=YkkycFR5S0N6TGRWeHBiR3FQVDNHUT09 Meeting ID: 984 0948 8429 Passcode: 396495 Abstract: The $k$-dimensional Weisfeiler–Leman ($k$-WL) algorithm is a strong graph invariant which sees wide use in both theoretical and practical algorithms for the Graph Isomorphism Problem (textbf{GI}), and in machine learning applications as a graph kernel. As $k$-WL falls short deciding textbf{GI} for all $k$, it gives rise to a coarser equivalence relation on the class of all graphs based on indistinguishability. In this work we study invariant functions under these equivalence relations, with a focus on induced subgraph counts and small $kin{1,2}$. For the case of $k=1$ we obtain a complete description of the induced subgraphs whose counts are invariant, while for $k=2$ we obtain results for path, cycle and matching graphs. In both cases we match known results for non-induced subgraphs.

12/10/2021
11:15 - 12:00

BSc

The Complexity of Homomorphism Indistinguishability
Duc Khuat
The foundation of Homomorphism Indistinguishability was laid by Lovász’ Theorem in 1966, stating that a graph is defined up to isomorphism by the number of homomorphism from all graphs to the studied graph and from the studied graphs to all other graphs, respectively. Collecting these numbers in an infinite vector, motivates the notion of homomorphism vectors. Now, as an infinite dimensional vector we define projections onto entries corresponding to a fixed subset of the set of all graphs. We call two graphs homomorphism indistinguishability over this subset if the projection image of the graphs are equal. Strong recent results characterize homomorphism indistinguishability over some natural classes such as the class of planar graphs, class of bounded tree depth and tree width, respectively with well studied notions, combining results of the past forty years with this single framework. In my thesis I provide an overview and a list of references, combining the ideas and the machineries used to establish the recent results but also well known results from the fields of logic, graph theory, combinatorics and quantum and game theory. A proper focus lies on the analysis of complexity of homomorphism indistinguishability. From the characterisations emerging complexity results will be explicated and extended by an algorithm deciding homomorphism in- distinguishability over graphs of bounded tree depth in polynomial time and the fpt-intractability of first order logic of bounded quantifier rank equiva- lence.

12/10/2021
12:00 - 12:45

BSc

Lower Bounds for Learning Logical Concepts
Constantin Rettig
We study the complexity of learning concepts definable in first-order or monadic second-order logic for relational structures. We introduce a uniform notation for the framework, with which we will remove irregularities among related work. The main focus here lies on the lower bound on the running time for logic learning algorithms. We go over results for string structures, showing that for unary and binary FO formulas there is no consistent learning algorithm running in sublinear time in the size of the structure. For tree structures we show the same results and in addition see that the sublinear bound on logic learning holds for quantifier free formulas. It is shown that for structures with small degree the sublinear time bound holds for logic learning algorithms given local access. After that, we present a section over parameter learning, showing that parameter learning is not possible in sublinear time for structures of small degree. In addition, we show that the parameter learning problem on structures with no degree restrictions is as hard as solving the q-CLIQUE problem on graphs. In the last section we show that concept learning (also in the Probably Approximately Correct (PAC) setting) is as hard as the first-order model-checking problem in the parametrised setting. In the conclusion we sum up the presented results and give a outlook on possible future work.

07/10/2021
10:00 - 11:00

BSc

Graph Neural Networks for MAX-SAT
Mert Basaran

[bachelor]

We present RUN-SAT, a novelrecurrent message passing neural network. RUN-SAT learns to approximate MAX-SATin an unsupervised manner. The architecture can be applied to arbitrary CNFformulas. We experimentally evaluate our approach on the SAT and MAX-SATproblems and compare the performance to conventional solvers, heuristics andother neural architectures.

23/09/2021
14:00 - 15:00

 

Learning on graphs with logic and neural networks
Martin Ritzert
https://rwth.zoom.us/j/95250295111?pwd=cjhFMGk0bStZcGNvcmYrYURPWnQ0dz09 In the domain of graphs we show strong connections between logic and machine learning in both theory and practice. In a purely theoretical framework we develop sublinear machine learning algorithms for supervised learning of logical formulas on various graph classes. Further we show that learning first-order logic on arbitrary graphs is intractable unless P=NP. At the intersection of theory and practice, we prove an equivalence between graph neural networks and the 1-dimensional Weisfeiler-Leman algorithm. As a practical application, we approximate combinatorial problems with recurrent graph neural networks. The proposed architecture is unsupervised and can be applied to all maximum constraint satisfaction problems.

09/09/2021
11:00 - 11:30

MSc

Nondeterministic Deep Weisfeiler Leman
Louis Härtel
https://rwth.zoom.us/j/5419503919?pwd=enlnbm1mclNBNkVQZTgvVXR4RTRHZz09

06/09/2021
14:00 - 15:00

BSc

Bachelor-Kolloquium Matthäus Micun
Counting and Sampling based on Nondeterministic Logspace Transducers Abstract: Transducers are Turing machines that, instead of deciding problems, compute witnesses. Additionally, non-deterministic Transducers compute relations of witnesses. In this paper, we discuss non-deterministic logspace transducers (NL transducers), as well as their unambiguous version (UL transducers). More specifically, we prove that for any relation computed by an NL transducer, we can enumerate the witnesses of a given word w with polynomial delay, count the number of all witnesses using a fully polynomial randomized approximation scheme (FPRAS), and uniformly generate a witness using a pre-processing polynomial time Las Vegas uniform generator (PPLVUG). Additionally, we connect these properties to non-deterministic finite automata, and prove that the #NFA problem admits an FPRAS.

02/09/2021
15:00 - 16:00

 

Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs, Daniel Neuen
Abstract: Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. In this talk I discuss a framework for obtaining n^{O(sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an n^{O(sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{O(sqrt{k} polylog(k))}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain such (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set.

02/09/2021
15:00 - 16:00

 

Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs, Daniel Neuen
Abstract: Subexponential parameterized algorithms are known for a wide range of natural problems on planar graphs, but the techniques are usually highly problem specific. In this talk I discuss a framework for obtaining n^{O(sqrt{k})} time algorithms for a family of graph modification problems that includes problems that can be seen as generalized cycle hitting problems. Our starting point is the Node Unique Label Cover problem (that is, given a CSP instance where each constraint is a permutation of values on two variables, the task is to delete k variables to make the instance satisfiable). We introduce a variant of the problem where k vertices have to be deleted such that every 2-connected component of the remaining instance is satisfiable. Then we extend the problem with cardinality constraints that restrict the number of times a certain value can be used (globally or within a 2-connected component of the solution). We show that there is an n^{O(sqrt{k})} time algorithm on planar graphs for any problem that can be formulated this way, which includes a large number of well-studied problems, for example, Odd Cycle Transversal, Subset Feedback Vertex Set, Group Feedback Vertex Set, Subset Group Feedback Vertex Set, Vertex Multiway Cut, and Component Order Connectivity. For those problems that admit appropriate (quasi)polynomial kernels (that increase the parameter only linearly and preserve planarity), our results immediately imply 2^{O(sqrt{k} polylog(k))}n^{O(1)} time parameterized algorithms on planar graphs. In particular, we use or adapt known kernelization results to obtain such (randomized) algorithms for Vertex Multiway Cut, Group Feedback Vertex Set, and Subset Feedback Vertex Set.

11/08/2021
15:00 - 15:30

 

Facility Location and Clustering on Planar and Almost Planar Graphs
Sebastian Schaub
Masterkolloquium


Zoom-Meeting beitreten
https://rwth.zoom.us/j/99375584947?pwd=UVNSaTBNRm1qL2ZneDExWVVZUUxKZz09
Meeting-ID: 993 7558 4947
Kenncode: 600407


Abstract: In this thesis we will reflect the current state of research for the uniform facility location problem and k-Clustering in terms of approximability. We will focus our attention on the special case of the planar graph metric, because for the problems with general metric no polynomial-time approximation scheme exist.
To illustrate this we will depict and explain four recent results which use different techniques for the analysis of the algorithms, including Voronoi Diagrams, r-divisions and coresets. The first result is an algorithm accuracy analysis for the uniform facility location, where we show that a commonly known local search algorithm is a polynomial-time approximation scheme. The second result is an efficient polynomial-time randomised approximation scheme, where we use an algorithm for the k-Median problem as a subroutine to derive a solution. For the third result we have another polynomial-time approximation scheme with a local search algorithm for the k-Clustering problems k-Median and k-Means. And the fourth result is a fully polynomial-time randomised approximation scheme for the k-Median problem, where the algorithm is based on constructing coresets.

29/07/2021
11:00 - 12:00

 

29/07/2021
11:00 - 12:00

 

21/07/2021
10:00 - 11:00

 

Learning and Minimization of omega-Automata in the Presence of Don’t CareWords, Max Stachon
Masterkollquium

https://rwth.zoom.us/j/93883134873?pwd=Y1lKYXpEZHBlaHlmUWtHSG9VQ1M5Zz09