Andreas Göbel
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Andreas Göbel has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Tobias Friedrich
Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
13 shared publications - Marcus Pappik
Hasso Plattner Institute, University of Potsdam, Potsdam, Germany
8 shared publications - Martin Stefan Krejca
Ecole Polytechnique, Palaiseau, France
8 shared publications - Nicolas Klodt
Hasso Plattner Institute University of Potsdam Potsdam Germany
5 shared publications Tobias Friedrich
Hasso Plattner Institute, University of Potsdam
5 shared publications- Maximilian Katzmann
Karlsruhe Institute of Technology Karlsruhe Germany
4 shared publications
Latest Publications
- Open Access
Temporal Exploration of Random Spanning Tree Models
The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs $(G_i)_{i\in \mathbb{N}}$ on the same vertex set, and asks for a walk of shortest length visiting all vertices, where the $i$-th step uses an edge from $G_i$. If each such $G_i$ is connected, then an exploration of length $n^2$ exists, and this is known to be the best possible up to a constant. More fine-grained lower and upper bounds have been obtained for restricted temporal graph classes, however, for several fundamental classes, a large gap persists between known bounds, and it remains unclear which properties of a temporal graph make it inherently difficult to explore. Motivated by this limited understanding and the central role of the Temporal Graph Exploration problem in temporal graph theory, we study the problem in a randomised setting. We introduce the Random Spanning Tree (RST) model, which consists of a set of $n$-vertex trees together with an arbitrary probability distribution $μ$ over this set. A random temporal graph generated by the RST model is a sequence of independent samples drawn from $μ$. We initiate a systematic study of the Temporal Graph Exploration problem in such random temporal graphs and establish tight general bounds on exploration time. Our first main result proves that any RST model can, with high probability (w.h.p.), be explored in $O(n^{3/2})$ time, and we show that this bound is tight up to a constant factor. This demonstrates a fundamental difference between the adversarial and random settings. Our second main result shows that if all trees of an RST are subgraphs of a fixed graph with $m$ edges then, w.h.p.\ , it can be explored in $O(m)$ time.Open AccessTemporal Exploration of Random Spanning Tree Models
The Temporal Graph Exploration problem (TEXP) takes as input a temporal graph, i.e., a sequence of graphs $(G_i)_{i\in \mathbb{N}}$ on the same vertex set, and asks for a walk of shortest length visiting all vertices, where the $i$-th step uses an edge from $G_i$. If each such $G_i$ is connected, then an exploration of length $n^2$ exists, and this is known to be the best possible up to a constant. More fine-grained lower and upper bounds have been obtained for restricted temporal graph classes, however, for several fundamental classes, a large gap persists between known bounds, and it remains unclear which properties of a temporal graph make it inherently difficult to explore. Motivated by this limited understanding and the central role of the Temporal Graph Exploration problem in temporal graph theory, we study the problem in a randomised setting. We introduce the Random Spanning Tree (RST) model, which consists of a set of $n$-vertex trees together with an arbitrary probability distribution $μ$ over this set. A random temporal graph generated by the RST model is a sequence of independent samples drawn from $μ$. We initiate a systematic study of the Temporal Graph Exploration problem in such random temporal graphs and establish tight general bounds on exploration time. Our first main result proves that any RST model can, with high probability (w.h.p.), be explored in $O(n^{3/2})$ time, and we show that this bound is tight up to a constant factor. This demonstrates a fundamental difference between the adversarial and random settings. Our second main result shows that if all trees of an RST are subgraphs of a fixed graph with $m$ edges then, w.h.p.\ , it can be explored in $O(m)$ time. - Open Access
Gradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion
Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.
Open AccessGradually Declining Immunity Retains the Exponential Duration of Immunity-Free Diffusion
Diffusion processes pervade numerous areas of AI, abstractly modeling the dynamics of exchanging, oftentimes volatile, information in networks. A central question is how long the information remains in the network, known as survival time. For the commonly studied SIS process, the expected survival time is at least super-polynomial in the network size already on star graphs, for a wide range of parameters. In contrast, the expected survival time of the SIRS process, which introduces temporary immunity, is always at most polynomial on stars and only known to be super-polynomial for far denser networks, such as expanders. However, this result relies on featuring full temporary immunity, which is not always present in actual processes. We introduce the cSIRS process, which incorporates gradually declining immunity such that the expected immunity at each point in time is identical to that of the SIRS process. We study the survival time of the cSIRS process rigorously on star graphs and expanders and show that its expected survival time is very similar to that of the SIS process, which features no immunity. This suggests that featuring gradually declining immunity is almost as having none at all.
- 8 November 2024
- Published by Elsevier in Physica A: Statistical Mechanics and its Applications
- Vol. 656
Understanding the impact of non-linearity in the SIS model
- 8 November 2024
- Published by Elsevier in Physica A: Statistical Mechanics and its Applications
- Vol. 656
Understanding the impact of non-linearity in the SIS model
- Open Access
- 11 October 2024
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 34 (1) , 63-89
Sampling repulsive Gibbs point processes using random graphs
We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-studied discrete spin system. Given an instance of such a point process, our reduction generates a random graph drawn from a natural geometric model. We show that the partition function of a hard-core model on graphs generated by the geometric model concentrates around the partition function of the Gibbs point process. Our reduction allows us to use a broad range of algorithms developed for the hard-core model to sample from the Gibbs point process and approximate its partition function. This is, to the extent of our knowledge, the first approach that deals with pair potentials of unbounded range.
- 11 October 2024
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 34 (1) , 63-89
Open AccessSampling repulsive Gibbs point processes using random graphs
We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-studied discrete spin system. Given an instance of such a point process, our reduction generates a random graph drawn from a natural geometric model. We show that the partition function of a hard-core model on graphs generated by the geometric model concentrates around the partition function of the Gibbs point process. Our reduction allows us to use a broad range of algorithms developed for the hard-core model to sample from the Gibbs point process and approximate its partition function. This is, to the extent of our knowledge, the first approach that deals with pair potentials of unbounded range.
- Open Access
- 1 August 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 3, 2036-2044
Real-World Networks Are Low-Dimensional: Theoretical and Practical Assessment
Recent empirical evidence suggests that real-world networks have very low underlying dimensionality. We provide a theoretical explanation for this phenomenon as well as develop a linear-time algorithm for detecting the underlying dimensionality of such networks. Our theoretical analysis considers geometric inhomogeneous random graphs (GIRGs), a geometric random graph model, which captures a variety of properties observed in real-world networks. These properties include a heterogeneous degree distribution and non-vanishing clustering coefficient, which is the probability that two random neighbors of a vertex are adjacent. Our first result shows that the clustering coefficient of GIRGs scales inverse exponentially with respect to the number of dimensions d, when the latter is at most logarithmic in n, the number of vertices. Hence, for a GIRG to behave like many real-world networks and have a non-vanishing clustering coefficient, it must come from a geometric space of o(log n) dimensions. Our analysis on GIRGs allows us to obtain a linear-time algorithm for determining the dimensionality of a network. Our algorithm bridges the gap between theory and practice, as it comes with a rigorous proof of correctness and yields results comparable to prior empirical approaches, as indicated by our experiments on real-world instances. The efficiency of our algorithm makes it applicable to very large data-sets. We conclude that very low dimensionalities (from 1 to 10) are needed to explain properties of real-world networks.
- 1 August 2024
- Published by International Joint Conferences on Artificial Intelligence
- Vol. 3, 2036-2044
Open AccessReal-World Networks Are Low-Dimensional: Theoretical and Practical Assessment
Recent empirical evidence suggests that real-world networks have very low underlying dimensionality. We provide a theoretical explanation for this phenomenon as well as develop a linear-time algorithm for detecting the underlying dimensionality of such networks. Our theoretical analysis considers geometric inhomogeneous random graphs (GIRGs), a geometric random graph model, which captures a variety of properties observed in real-world networks. These properties include a heterogeneous degree distribution and non-vanishing clustering coefficient, which is the probability that two random neighbors of a vertex are adjacent. Our first result shows that the clustering coefficient of GIRGs scales inverse exponentially with respect to the number of dimensions d, when the latter is at most logarithmic in n, the number of vertices. Hence, for a GIRG to behave like many real-world networks and have a non-vanishing clustering coefficient, it must come from a geometric space of o(log n) dimensions. Our analysis on GIRGs allows us to obtain a linear-time algorithm for determining the dimensionality of a network. Our algorithm bridges the gap between theory and practice, as it comes with a rigorous proof of correctness and yields results comparable to prior empirical approaches, as indicated by our experiments on real-world instances. The efficiency of our algorithm makes it applicable to very large data-sets. We conclude that very low dimensionalities (from 1 to 10) are needed to explain properties of real-world networks.
- 25 June 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (2) , 1943-2000
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach nongeometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs.
- 25 June 2024
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 38 (2) , 1943-2000
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach nongeometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs.
- Open Access
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-17
The Weisfeiler-Leman Dimension of Conjunctive Queries
A graph parameter is a function f on graphs with the property that, for any pair of isomorphic graphs G 1 and G 2 , f(G 1 )=f(G 2 ). The Weisfeiler--Leman (WL) dimension of f is the minimum k such that, if G 1 and G 2 are indistinguishable by the k-dimensional WL-algorithm then f(G 1 )=f(G 2 ). The WL-dimension of f is ∞ if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query φ, we quantify the WL-dimension of the function that maps every graph G to the number of answers of φ in G. The works of Dvorak (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries φ, the WL-dimension is equal to the treewidth of the Gaifman graph of φ. In this work, we give a characterisation that applies to all conjunctive queries. Given any conjunctive query φ, we prove that its WL-dimension is equal to the semantic extension width sew(φ), a novel width measure that can be thought of as a combination of the treewidth of φ and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of φ are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query φ cannot be computed by GNNs of order smaller than sew(φ). The majority of the paper is concerned with establishing a lower bound of the WL-dimension of a query. Given any conjunctive query φ with semantic extension width k, we consider a graph F of treewidth k obtained from the Gaifman graph of φ by repeatedly cloning the vertices corresponding to existentially quantified variables. Using a modification due to Furer (ICALP 2001) of the Cai-Fürer-Immerman construction (Combinatorica 1992), we then obtain a pair of graphs χ(F) and ^χ(F) that are indistinguishable by the (k-1)-dimensional WL-algorithm since F has treewidth k. Finally, in the technical heart of the paper, we show that φ has a different number of answers in χ(F) and ^χ(F). Thus, φ can distinguish two graphs that cannot be distinguished by the (k-1)-dimensional WL-algorithm, so the WL-dimension of φ is at least k.
- 10 May 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-17
Open AccessThe Weisfeiler-Leman Dimension of Conjunctive Queries
A graph parameter is a function f on graphs with the property that, for any pair of isomorphic graphs G 1 and G 2 , f(G 1 )=f(G 2 ). The Weisfeiler--Leman (WL) dimension of f is the minimum k such that, if G 1 and G 2 are indistinguishable by the k-dimensional WL-algorithm then f(G 1 )=f(G 2 ). The WL-dimension of f is ∞ if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query φ, we quantify the WL-dimension of the function that maps every graph G to the number of answers of φ in G. The works of Dvorak (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries φ, the WL-dimension is equal to the treewidth of the Gaifman graph of φ. In this work, we give a characterisation that applies to all conjunctive queries. Given any conjunctive query φ, we prove that its WL-dimension is equal to the semantic extension width sew(φ), a novel width measure that can be thought of as a combination of the treewidth of φ and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of φ are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query φ cannot be computed by GNNs of order smaller than sew(φ). The majority of the paper is concerned with establishing a lower bound of the WL-dimension of a query. Given any conjunctive query φ with semantic extension width k, we consider a graph F of treewidth k obtained from the Gaifman graph of φ by repeatedly cloning the vertices corresponding to existentially quantified variables. Using a modification due to Furer (ICALP 2001) of the Cai-Fürer-Immerman construction (Combinatorica 1992), we then obtain a pair of graphs χ(F) and ^χ(F) that are indistinguishable by the (k-1)-dimensional WL-algorithm since F has treewidth k. Finally, in the technical heart of the paper, we show that φ has a different number of answers in χ(F) and ^χ(F). Thus, φ can distinguish two graphs that cannot be distinguished by the (k-1)-dimensional WL-algorithm, so the WL-dimension of φ is at least k.
- Open Access
- 1 January 2024
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 29 (none) , 1-29
Analysis of the survival time of the SIRS process via expansion
We study the SIRS process—a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate λ, and each recovered vertex becomes susceptible at a rate ϱ, which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behavior of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph. Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of λ. This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs G with n vertices, degree close to d, and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in n when λ≥c∕d for a constant c>1. Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if G is a subgraph. Notably, our result implies an almost-tight threshold for Erdős–Rényi graphsand a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.
- 1 January 2024
- Published by Institute of Mathematical Statistics in Electronic Journal of Probability
- Vol. 29 (none) , 1-29
Open AccessAnalysis of the survival time of the SIRS process via expansion
We study the SIRS process—a continuous-time Markov chain modeling the spread of infections on graphs. In this model, vertices are either susceptible, infected, or recovered. Each infected vertex becomes recovered at rate 1 and infects each of its susceptible neighbors independently at rate λ, and each recovered vertex becomes susceptible at a rate ϱ, which we assume to be independent of the graph size. A central quantity of the SIRS process is the time until no vertex is infected, known as the survival time. Surprisingly though, to the best of our knowledge, all known rigorous theoretical results that exist so far immediately carry over from the related SIS model and do not completely explain the behavior of the SIRS process. We address this imbalance by conducting theoretical analyses of the SIRS process via the expansion properties of the underlying graph. Our first result shows that the expected survival time of the SIRS process on stars is at most polynomial in the graph size for any value of λ. This behavior is fundamentally different from the SIS process, where the expected survival time is exponential already for small infection rates. This raises the question of which graph properties result in an exponential survival time. Our main result is an exponential lower bound of the expected survival time of the SIRS process on expander graphs. Specifically, we show that on expander graphs G with n vertices, degree close to d, and sufficiently small spectral expansion, the SIRS process has expected survival time at least exponential in n when λ≥c∕d for a constant c>1. Previous results on the SIS process show that this bound is almost tight. Additionally, our result holds even if G is a subgraph. Notably, our result implies an almost-tight threshold for Erdős–Rényi graphsand a regime of exponential survival time for complex network models. The proof of our main result draws inspiration from Lyapunov functions used in mean-field theory to devise a two-dimensional potential function and from applying a negative-drift theorem to show that the expected survival time is exponential.
- Open Access
Using random graphs to sample repulsive Gibbs point processes with arbitrary-range potentials
We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-studied discrete spin system. Given an instance of such a point process, our reduction generates a random graph drawn from a natural geometric model. We show that the partition function of a hard-core model on graphs generated by the geometric model concentrates around the partition function of the Gibbs point process. Our reduction allows us to use a broad range of algorithms developed for the hard-core model to sample from the Gibbs point process and approximate its partition function. This is, to the extend of our knowledge, the first approach that deals with pair potentials of unbounded range. We compare the resulting algorithms with recently established results and study further properties of the random geometric graphs with respect to the hard-core model.
Open AccessUsing random graphs to sample repulsive Gibbs point processes with arbitrary-range potentials
We study computational aspects of repulsive Gibbs point processes, which are probabilistic models of interacting particles in a finite-volume region of space. We introduce an approach for reducing a Gibbs point process to the hard-core model, a well-studied discrete spin system. Given an instance of such a point process, our reduction generates a random graph drawn from a natural geometric model. We show that the partition function of a hard-core model on graphs generated by the geometric model concentrates around the partition function of the Gibbs point process. Our reduction allows us to use a broad range of algorithms developed for the hard-core model to sample from the Gibbs point process and approximate its partition function. This is, to the extend of our knowledge, the first approach that deals with pair potentials of unbounded range. We compare the resulting algorithms with recently established results and study further properties of the random geometric graphs with respect to the hard-core model.
- Open Access
- 28 June 2023
- Published by Wiley in Random Structures & Algorithms
- Vol. 63 (4) , 885-941
The impact of heterogeneity and geometry on the proof complexity of random satisfiability
- 28 June 2023
- Published by Wiley in Random Structures & Algorithms
- Vol. 63 (4) , 885-941
Open AccessThe impact of heterogeneity and geometry on the proof complexity of random satisfiability