Talks (Archive)

Showing 1 - 50 of 253 Results

  • Date
     
    Title
  • 27/01/2023
    10:30 - 11:30
    ATI
    Graph Similarity Based on Matrix Norms
    Timo Gervens
    Quantifying 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 Evaluation
    Julia Feith
    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 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 Evaluation
    Julia Feith
    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 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 Need
    Eran Rosenbluth
    Graph 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 Counts
    Tim Seppelt
    Counting
    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 Metric
    Jan 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
    Learning algorithms for ω-automata
    Leon Bohn
    [ati][speaker=href="https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~ldsbd/Leon-Bohn-alt/">https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~ldsbd/Leon-Bohn-alt/]The
    RPNI algorithm (Oncina, Garcia 1992) constructs deterministic finite
    automata (DFA) from finite sets of negative and positive example words.
    In this talk, we propose an extension of this algorithm to infinite
    words, which can learn all deterministic ω
    -automata
    with an informative right congruence in the limit with polynomial time
    and data.
    Further, we introduce a second learner that is complete for
    the full class of deterministic Büchi automata (DBA). This learner
    constructs multiple DFAs using
    a polynomial-time active learning
    algorithm on finite words as black box using an oracle that we implement
    based on the given sample of ω-words, and combines these DFAs into a
    single DBA.
  • 04/11/2022
    10:30 - 11:30
    ATI
    Learning algorithms for ω-automata
    Leon Bohn
    [ati][speaker=href="https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~ldsbd/Leon-Bohn-alt/">https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~ldsbd/Leon-Bohn-alt/]The
    RPNI algorithm (Oncina, Garcia 1992) constructs deterministic finite
    automata (DFA) from finite sets of negative and positive example words.
    In this talk, we propose an extension of this algorithm to infinite
    words, which can learn all deterministic ω
    -automata
    with an informative right congruence in the limit with polynomial time
    and data.
    Further, we introduce a second learner that is complete for
    the full class of deterministic Büchi automata (DBA). This learner
    constructs multiple DFAs using
    a polynomial-time active learning
    algorithm on finite words as black box using an oracle that we implement
    based on the given sample of ω-words, and combines these DFAs into a
    single DBA.
  • 21/10/2022
    10:30 - 11:30
    ATI
    Analysis of multi-stage flow shop processing systems
    Robin Westermann
    We 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 Satisfaction
    Jan 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 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
    Width of Graph Decompositions
    Eva 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 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
    Out-of-the-ordinary ATI talk
    Eva Fluck
  • 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 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
    [ati][speaker=https://www.lics.rwth-aachen.de/cms/LICS/Der-Lehrstuhl/Team/Wissenschaftliche-Mitarbeiterinnen-und-M/~fvvzk/Christoph-Standke/]
    Typically, probabilistic databases (PDBs) are probability distributions over the subsets of a finite set of facts. The problem of evaluating a query on such set-PDBs, known as probabilistic query evaluation, is well-understood for unions of conjunctive queries (UCQs): it is either in polynomial time, or #P-hard (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 set-version.   This talk will give an introduction to probabilistic query evaluation. We start by reviewing the case of set-PDBs and then present current results on querying bag-PDBs. 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 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.