-
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 graph-based 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 NP-hardness and inapproximability results even for very restricted graph classes such as bounded-degree 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 #P-hard 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 hardness-of-approximation results from related fields to show that these approximation paradigms give rise to a strict hierarchy under common complexity-theoretic 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 #P-hard 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 hardness-of-approximation results from related fields to show that these approximation paradigms give rise to a strict hierarchy under common complexity-theoretic 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 isomorphism-invariant 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 (expressivity-wise) 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 vector-embedded 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 message-passing networks
perform outstandingly on graph analysis tasks by leveraging higher-order
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 GNN-based unsupervised
attributed clustering approach Deep Modularity Networks with carefully
designed experiments. We experiment with different models with several
real-world datasets and evaluate them based on the ground-truth label
correlation and graph clustering quality. The robustness of each model
is further tested with synthetic graphs with different signal-to-noise
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 real-world databases, but we lack a good understanding of how they should interact. On the one hand, systems based on SQL provide ad-hoc 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.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~rrqo/JanBoeker/">"https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~rrqo/JanBoeker/"> class="moz-txt-link-freetext"
href="https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~rrqo/JanBoeker/">https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~rrqo/JanBoeker/]The
tree distance, a variant of the well-known 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 non-quantitative 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
color-refinement
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 color-refinement 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 multi-stage 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 NP-hardness 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.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~hhxya/Jan-Toenshoff/]We
propose a universal Graph Neural Network architecture which can be
trained as an end-2-end 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 RL-based
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, 3-SAT and MAX-k-SAT. 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 NP-hard, there is no polynomial-time
algorithm unless P=NP. Thus there are parameterized algorithms as well as
approximation algorithms. We discuss the current common-state-of-the-art
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 pre-processing 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
pre-processing 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 NP-hard, there is no polynomial-time
algorithm unless P=NP. Thus there are parameterized algorithms as well as
approximation algorithms. We discuss the current common-state-of-the-art
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 pre-processing 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
pre-processing and pruning used by the algorithms.
-
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
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 graph-based design, GNNs present an alternative platform to build large-scale combinatorial heuristics. A recent example of this is RUN-CSP, which is a highly scalable, heuristic solver for binary Maximum-Constraint Satisfaction Problems (Max-CSPs). This thesis aims to empirically evaluate the performance improvement on Max-CSPs like Max-k-COL using ensemble based learning techniques with RUN-CSP 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 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 LogicSteffen van BergeremWe 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 LogicSteffen van BergeremWe 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
Width of Graph DecompositionsEva Fluck[ati][speaker=https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~ryzs/Eva-Fluck/]
Tree and Path decompositions of graphs are an important and well studied topic
in theoretical computer science and discrete math, since at least the Graph
Minors project of Robertson and Seymour. Recently a generalization to graph
classes beyond paths and trees emerged. In this talk we will look at a possible
width measure for general graph decompositions, since considering the size of
the bag no longer suffices for a rich theory. Furthermore we try to find an
analog to Robertsons and Seymours Excluded Gird Theorem for tree width. That is
we try to find substructures that have to be present in graphs of large width.
We are able to proof a theorem for our width measure on path decompositions and
give a conjecture for all minor closed classes of graphs.
Joint work with Sandra Albrechtsen, Reinhard Diestel, Ann-Kathrin Elm, Raphael
W. Jacobs, Paul Knappe and Paul Wollan.
-
23/06/2022
11:00 - 11:45
MSc
Hierarchical Message Passing for Constraint Satisfaction Problems
Moritz Rösgen
RUN-CSP is a graph neural network solving optimization problems modelled as constraint satisfaction problems (CSPs) by performing message passing on the graph representation of said problems. It is a generic architecture that can be trained unsupervised on any binary CSPs. We introduce an extension for RUN-CSP that additionally performs message passing on the tree decomposition of the input graph. Our goal is to use a tree decomposition that captures the global structure of the graph and allow messages to be passed through the graph in less steps. To this end we experiment with different algorithms for computing tree decompositions. In these experiments we compare our extension with the original architecture. It shows that we were not able to improve the results of RUN-CSP significantly. Neither on instances that were originally used to evaluate RUN-CSP nor on instances that we generated with a small treewidth.
-
21/06/2022
11:00 - 11:30
BSc
The Complexity of Counting Small Patterns in Graphs and Relational Structures
Daniel Quirmbach
In der Präsentation wird die Komplexität des Zählens von Mustern auf Graphen und relationalen Strukturen untersucht. Hierzu wird das Konzept der Graphmotivparameter vorgestellt, um eine geschlossene Vorgehensweise für die Komplexitätsabschätzung der Zählprobleme #Hom, #Sub und #IndSub zu erhalten, die entweder die Anzahl an Homomorphismen oder an (induzierten) Teilgraphen eines Musters H zu beziehungsweise auf einem Graphen G zählen sollen. Ausgehend vom Dichotomiecharakters der Komplexität vom Problem #Hom untersuchen wir die Komplexität von Linearkombinationen von Problemen in #Hom. Durch eine Darstellung der Probleme #Sub und #IndSub als Linearkombinationen von Homomorphismenproblemen erhalten wir auch eine Dichotomie für diese Klassen. Wir erweitern die Idee der Graphmotivparameter auf relationale Strukturen und zeigen mithilfe einer Dichotomie des Problems $#Hom$ für relationale Strukturen, dass auch die Probleme #Sub und #IndSub durch ihre Darstellung als Linearkombination von Problemen in #Hom immer entweder in polynomieller Zeit lösbar oder #W[1]-schwer sind. Zudem identifizieren wir anhand der Baumweite ein Dichotomiekriterium, welches uns ermöglicht einzelne Probleminstanzen einer der beiden oben genannter Komplexitätsklassen zuzuordnen.
-
23/05/2022
11:00 - 11:45
MSc
Approximate Probabilistic Query Evaluation
Oliver Feith
[master]Probabilistic databases model uncertain data as a probability space
over traditional relational databases. Evaluating queries in probabilistic
databases hence requires computing confidences for the answers,
which is #P-hard even for (some) conjunctive queries. Therefore, new
methods are needed to obtain practical solutions.
We survey the computational complexity 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 problemEran RosenbluthVarious 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 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 GNN-based CSP and SAT solvers for the factorisation problem.
-
01/04/2022
10:30 - 11:15
MSc
The Iteration Number of the Weisfeiler-Leman Algorithm
Athena Riazsadri
The Weisfeiler-Leman (WL) algorithm is a simple combinatorial algorithm with widespread applications, most prominently as a subroutine for competitive graph isomorphism solvers. The number of iterations until it reaches termination is crucial for the parallelized running time of the algorithm. For each integer k, there is a k-dimensional version of the algorithm. While Lichter et al. (LICS 2019) provided an upper bound of O(n*log n) on the iteration number of 2-WL on input graphs of order n, there have been no improvements over the trivial upper bound of O(n^k) on the iteration number of the k-dimensional version of the algorithm for k>2 and input graphs of order n. We will present the proof to the currently best known upper bound of O(n*log n) on the iteration number of 2-WL and provide a parameterized upper bound on the iteration number of k-WL for k>2.
-
01/04/2022
10:30 - 11:15
MSc
The Iteration Number of the Weisfeiler-Leman Algorithm
Athena Riazsadri
The Weisfeiler-Leman (WL) algorithm is a simple combinatorial algorithm with widespread applications, most prominently as a subroutine for competitive graph isomorphism solvers. The number of iterations until it reaches termination is crucial for the parallelized running time of the algorithm. For each integer k, there is a k-dimensional version of the algorithm. While Lichter et al. (LICS 2019) provided an upper bound of O(n*log n) on the iteration number of 2-WL on input graphs of order n, there have been no improvements over the trivial upper bound of O(n^k) on the iteration number of the k-dimensional version of the algorithm for k>2 and input graphs of order n. We will present the proof to the currently best known upper bound of O(n*log n) on the iteration number of 2-WL and provide a parameterized upper bound on the iteration number of k-WL for k>2.
-
31/03/2022
15:00 - 15:30
BSc
Characterising Fragments of First-Order Logic by Counting Homomorphisms
Gian Luca Spitzer
Two graphs G, G' are homomorphism-indistinguishable over a class S of graphs if for each F in S, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'. Results by Dvořák (2010) and Grohe (2020) show that homomorphism-indistinguishability over the class of graphs of tree-width at most k coincides with logical equivalence in the (k+1)-variable fragment of first-order logic with counting, while homomorphism-indistinguishability over the class of graphs of tree-depth at most q coincides with equivalence in the quantifier-rank-q fragment. We introduce the graph parameter of elimination-order and prove that two graphs are equivalent in the k-variable, quantifier-rank-q fragment of counting first-order logic if and only if they are homomorphism-indistinguishable over the class of graphs of elimination-order (k,q).
-
31/03/2022
15:45 - 16:30
MSc
Variants of the Weisfeiler-Leman Algorithm
Sebastian Issel
[master]The expressiveness of different variants of the k-dimensional Weisfeiler-Leman algorithm and related concepts is compared. The relation of the classical coloring, the bijective pebble game and counting logics will be generalized to these variants with similar results.The variants are obtained by relaxing the coloring of tuples to sets or multisets ofvertices. This reduces the needed memory to calculate the coloring. Some upper and lower bounds of their expressiveness, compared to the classical version, are shown. As an additional viewpoint, a linear equation system will be defined which turns out to be solvable precisely if the algorithm cannot differentiate the graphs. This system stems from an adaptation of the Sherali-Adams relaxation for integer linear programming.
-
31/03/2022
15:00 - 15:30
BSc
Characterising Fragments of First-Order Logic by Counting Homomorphisms
Gian Luca Spitzer
Two graphs G, G' are homomorphism-indistinguishable over a class S of graphs if for each F in S, the number of homomorphisms from F to G equals the number of homomorphisms from F to G'. Results by Dvořák (2010) and Grohe (2020) show that homomorphism-indistinguishability over the class of graphs of tree-width at most k coincides with logical equivalence in the (k+1)-variable fragment of first-order logic with counting, while homomorphism-indistinguishability over the class of graphs of tree-depth at most q coincides with equivalence in the quantifier-rank-q fragment. We introduce the graph parameter of elimination-order and prove that two graphs are equivalent in the k-variable, quantifier-rank-q fragment of counting first-order logic if and only if they are homomorphism-indistinguishable over the class of graphs of elimination-order (k,q).
-
31/03/2022
15:45 - 16:30
MSc
Variants of the Weisfeiler-Leman Algorithm
Sebastian Issel
[master]The expressiveness of different variants of the k-dimensional Weisfeiler-Leman algorithm and related concepts is compared. The relation of the classical coloring, the bijective pebble game and counting logics will be generalized to these variants with similar results.The variants are obtained by relaxing the coloring of tuples to sets or multisets ofvertices. This reduces the needed memory to calculate the coloring. Some upper and lower bounds of their expressiveness, compared to the classical version, are shown. As an additional viewpoint, a linear equation system will be defined which turns out to be solvable precisely if the algorithm cannot differentiate the graphs. This system stems from an adaptation of the Sherali-Adams relaxation for integer linear programming.
-
25/03/2022
10:30 - 11:15
The Expressiveness of Convolutions and Random Walks in Graph Learning//Fabian Bender
In the field of graphlearning, the well-known Weisfeiler-Leman algorithm imposes a hierarchy that theoreticallybinds the expressive powers of a wide group of modern learning architectures.This establishes impossibility constraints hindering these architectures to useimportant insights into graphs for real-world predictions.
Provably not subject to this hierarchy, the work of [Toenshoff et al., 2021]introduces a new approach called CRAWL, which leverages 1D convolutions andrandom walks to capture the underlying structure of graphs. However, thetheoretical promises raise no guarantee in practical performance. In thisthesis, the abilities of the design to detect cycles and count various smallerstructures called graphlets in graphs are investigated. The expressiveness ofCRAWL and the influence of its hyperparameters is evaluated and compared to standardmessage-passing architectures as well as higherlevel approaches.
-
18/03/2022
10:30 - 11:15
BSc
Query Evaluation in Symmetric Probabilistic Databases
Adrian Voß
[bachelor]
In 2011 van den Broeck et al. proposed an algorithm which is able to compute the symmetric weighted model count of a first-order sentence in CNF, which is effectively a probabilistic inference problem. In their subsequent research, van den Broeck et al. showed that their method is guaranteed to solve the problem in polynomial time for sentences with a most 2 logical variables. The algorithm can be applied to arbitrary first-order sentences using a novel Skolemization algorithm, which retains the model count of a first-order sentence. The naturally arising question about sentences with at least 3 variables has been answered negatively by Suciu et al. 2015. In 2014 van den Broeck et al. also claimed that their algorithm is applicable to symmetric probabilistic databases, for which it solves the query evaluation problem in polynomial time. In this thesis we expand on the latter and construct the relation between first-order models and probabilistic databases. We build a cohesive algorithm from the various sources, expand the descriptions from the original papers to detailed proofs and give examples which illustrate the application of the method, such that the algorithm can be used in probabilistic database applications directly.
-
11/03/2022
10:30 - 11:15
BSc
The Real Complexity of Query Evaluation in Probabilistic Databases
János Arpasi
[bachelor]Abstract:
Probabilistic databases constitute probability distributions over relational databases. Of great interest for research have been the tuple independent probabilistic databases, where it was proven that for every UCQ that the evaluation problem is either computable in polynomial time or #P hard, but until now this always assumed all occurring probabilities are rational, so the case for arbitrary real numbers was not sorted out yet. We will therefore give an introduction into computable real numbers and functions, review some complexity theory for continuous data and show that the dichotomy holds true also for real numbers.
-
11/02/2022
10:30 - 11:30
ATI
Separating Rank Logic from Polynomial 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 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.