Friedrich, Tobias; Göbel, Andres; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus Analysis of the survival time of the SIRS process via expansionElectronic Journal of Probability 2024: 1–29
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~\(\lambda\), and each recovered vertex becomes susceptible at a rate~\(\varrho\), 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~\(\lambda\). 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 \(\lambda \geq 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 Erdos-Renyi-graphs and 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.
Ben Jedidia, Firas; Doerr, Benjamin; Krejca, Martin S. Estimation-of-Distribution Algorithms for Multi-Valued Decision VariablesTheoretical Computer Science 2024: 114622:1–114622:16
The majority of research on estimation-of-distribution algorithms (EDAs) concentrates on pseudo-Boolean optimization and permutation problems, leaving the domain of EDAs for problems in which the decision variables can take more than two values, but which are not permutation problems, mostly unexplored. To render this domain more accessible, we propose a natural way to extend the known univariate EDAs to this setting. Different from a naive reduction to the binary case, our approach avoids additional constraints. Since understanding genetic drift is crucial for an optimal parameter choice, we extend the known quantitative analysis of genetic drift to EDAs for multi-valued, categorical variables. Roughly speaking, when the variables take \(r\) different values, the time for genetic drift to become significant is \(r\) times shorter than in the binary case. Consequently, the update strength of the probabilistic model has to be chosen \(r\) times lower now. To investigate how desired model updates take place in this framework, we undertake a mathematical runtime analysis on the \(r\)-valued LeadingOnes problem. We prove that with the right parameters, the multi-valued UMDA solves this problem efficiently in \(O(r\ln(r)^2 n^2 \ln(n))\) function evaluations. This bound is nearly tight as our lower bound \(\Omega(r\ln(r) n^2 \ln(n))\) shows. Overall, our work shows that our good understanding of binary EDAs naturally extends to the multi-valued setting, and it gives advice on how to set the main parameters of multi-values EDAs.
Doerr, Benjamin; Krejca, Martin S.; Weeks, Noé Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem SolutionsParallel Problem Solving from Nature (PPSN) 2024
The decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function \(f\), but instead optimizes \(N + 1\) single-objective subproblems of \(f\) in a co-evolutionary manner. It maintains an archive of all non-dominated solutions found and outputs it as approximation to the Pareto front. Once the MOEA/D found all optima of the subproblems (the \(g\)-optima), it may still miss Pareto optima of \(f\). The algorithm is then tasked to find the remaining Pareto optima directly by mutating the \(g\)-optima. In this work, we analyze for the first time how the MOEA/D with only standard mutation operators computes the whole Pareto front of the OneMinMax benchmark when the \(g\)-optima are a strict subset of the Pareto front. For standard bit mutation, we prove an expected runtime of \(O(n N log n + n^n/(2N) N \log n)\) function evaluations. Especially for the second, more interesting phase when the algorithm start with all \(g\)-optima, we prove an \(\Omega(n^(1/2)(n/N + 1) \sqrt{N} 2^{-n/N})\) expected runtime. This runtime is super-polynomial if \(N = o(n)\), since this leaves large gaps between the \(g\)-optima, which require costly mutations to cover. For power-law mutation with exponent \(beta in (1, 2)\), we prove an expected runtime of \(O\left(n N \log n + n^\beta} \log n\right)\) function evaluations. The \(O\left(n^{\beta} \log n\right)\) term stems from the second phase of starting with all \(g\)-optima, and it is independent of the number of subproblems \(N\). This leads to a huge speedup compared to the lower bound for standard bit mutation. In general, our overall bound for power-law suggests that the MOEA/D performs best for \(N = O(n^\beta - 1})\), resulting in an \(O(n^\beta \log n)\) bound. In contrast to standard bit mutation, smaller values of \(N\) are better for power-law mutation, as it is capable of easily creating missing solutions.
Doerr, Benjamin; Echarghaoui, Aymen; Jamal, Mohammed; Krejca, Martin S. Runtime Analysis of the (µ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse PopulationsAnnual AAAI Conference on Artificial Intelligence (AAAI) 2024: 20683–20691
Most evolutionary algorithms used in practice heavily employ crossover. In contrast, the rigorous understanding of how crossover is beneficial is largely lagging behind. In this work, we make a considerable step forward by analyzing the population dynamics of the \((\mu+1)\) genetic algorithm when optimizing the Jump benchmark. We observe (and prove via mathematical means) that once the population contains two different individuals on the local optimum, the diversity in the population increases in expectation. From this drift towards more diverse states, we show that a diversity suitable for crossover to be effective is reached quickly and, more importantly, then persists for a time that is at least exponential in the population size \(\mu\). This drastically improves over the previously best known guarantee, which is only quadratic in \(\mu\). Our new understanding of the population dynamics easily gives stronger performance guarantees. In particular, we derive that population sizes logarithmic in the problem size \(n\) already suffice to gain an \(\Omega(n)\)-factor runtime improvement from crossover (previous works achieved comparable bounds only with \(\mu=\Theta(n)\) or via a non-standard mutation rate).
Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network ModelsAnnual AAAI Conference on Artificial Intelligence 2024
Information diffusion models on networks are at the forefront of AI research. The dynamics of such models typically follow stochastic models from epidemiology, used to model not only infections but various phenomena, including the behavior of computer viruses and viral marketing campaigns. A core question in this setting is how to efficiently detect the most influential vertices in the host graph such that the infection survives the longest. In processes that incorporate re-infection of the vertices, such as the SIS process, theoretical studies identify parameter thresholds where the survival time of the process rapidly transitions from logarithmic to super-polynomial. These results contradict the intuition that the starting configuration is relevant, since the process will always either die out fast or survive almost indefinitely. A shortcoming of these results is that models incorporating short-term immunity (or creative advertisement fatigue) have not been subjected to such a theoretical analysis so far. We reduce this gap in the literature by studying the SIRS process, a more realistic model, which besides re-infection additionally incorporates short-term immunity. On complex network models, we identify parameter regimes for which the process survives exponentially long, and we get a tight threshold for random graphs. Underlying these results is our main technical contribution, showing a threshold behavior for the survival time of the SIRS process on graphs with large expander subgraphs, such as social network models.
Krejca, Martin S.; Witt, Carsten A Flexible Evolutionary Algorithm With Dynamic Mutation Rate ArchiveGenetic and Evolutionary Computation Conference (GECCO) 2024
We propose a new, flexible approach for dynamically maintaining successful mutation rates in evolutionary algorithms using \(k\)-bit flip mutations. The algorithm adds successful mutation rates to an archive of promising rates that are favored in subsequent steps. Rates expire when their number of unsuccessful trials has exceeded a threshold, while rates currently not present in the archive can enter it in two ways: (i) via user-defined minimum selection probabilities for rates combined with a successful step or (ii) via a stagnation detection mechanism increasing the value for a promising rate after the current bit-flip neighborhood has been explored with high probability. For the minimum selection probabilities, we suggest different options, including heavy-tailed distributions. We conduct rigorous runtime analysis of the flexible evolutionary algorithm on the OneMax and Jump functions, on general unimodal functions, on minimum spanning and on a class of hurdle-like functions with varying hurdle width that benefit particularly from the archive of promising mutation rates. In all cases, the runtime bounds are close to or even outperform the best known results for both stagnation detection and heavy-tailed mutations.
Friedrich, Tobias; Göbel, Andreas; Klodt, Nicolas; Krejca, Martin S.; Pappik, Marcus From Market Saturation to Social Reinforcement: Understanding the Impact of Non-Linearity in Information Diffusion ModelsThe 23rd International Conference on Autonomous Agents and Multi-Agent Systems 2024
Diffusion of information in networks is at the core of many problems in AI. Common examples include the spread of ideas and rumors as well as marketing campaigns. Typically, information diffuses at a non-linear rate, for example, if markets become saturated or if users of social networks reinforce each other's opinions. Despite these characteristics, this area has seen little research, compared to the vast amount of results for linear models, which exhibit less complex dynamics. Especially, when considering the possibility of re-infection, no fully rigorous guarantees exist so far. We address this shortcoming by studying a very general non-linear diffusion model that captures saturation as well as reinforcement. More precisely, we consider a variant of the SIS model in which vertices get infected at a rate that scales polynomially in the number of their infected neighbors, weighted by an infection coefficient \(\lambda\). We give the first fully rigorous results for thresholds of \(\lambda\) at which the expected survival time becomes super-polynomial. For cliques we show that when the infection rate scales sub-linearly, the threshold only shifts by a poly-logarithmic factor, compared to the standard SIS model. In contrast, super-linear scaling changes the process considerably and shifts the threshold by a polynomial term. For stars, sub-linear and super-linear scaling behave similar and both shift the threshold by a polynomial factor. Our bounds are almost tight, as they are only apart by at most a poly-logarithmic factor from the lower thresholds, at which the expected survival time is logarithmic.
Doerr, Benjamin; Krejca, Martin S.; Vu, Nguyen Superior Genetic Algorithms for the Target Set Selection Problem Based on Power-Law Parameter Choices and Simple Greedy Heuristics 2024
The target set selection problem (TSS) asks for a set of vertices such that an influence spreading process started in these vertices reaches the whole graph. The current state of the art for this NP-hard problem are three recently proposed randomized search heuristics, namely a biased random-key genetic algorithm (BRKGA) obtained from extensive parameter tuning, a max-min ant system (MMAS), and a MMAS using Q-learning with a graph convolutional network. We show that the BRKGA with two simple modifications and without the costly parameter tuning obtains significantly better results. Our first modification is to simply choose all parameters of the BRKGA in each iteration randomly from a power-law distribution. The resulting parameterless BRKGA is already competitive with the tuned BRKGA, as our experiments on the previously used benchmarks show. We then add a natural greedy heuristic, namely to repeatedly discard small-degree vertices that are not necessary for reaching the whole graph. The resulting algorithm consistently outperforms all of the state-of-the-art algorithms. Besides providing a superior algorithm for the TSS problem, this work shows that randomized parameter choices and elementary greedy heuristics can give better results than complex algorithms and costly parameter tuning.
Bläsius, Thomas; Cohen, Sarel; Fischbeck, Philipp; Friedrich, Tobias; Krejca, Martin S. Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic ApproximationCoRR 2024
ArXiv preprint
Random graph models are widely used to understand network properties and graph algorithms. Key to such analyses are the different parameters of each model, which affect various network features, such as its size, clustering, or degree distribution. The exact effect of the parameters on these features is not well understood, mainly because we lack tools to thoroughly investigate this relation. Moreover, the parameters cannot be considered in isolation, as changing one affects multiple features. Existing approaches for finding the best model parameters of desired features, such as a grid search or estimating the parameter-feature relations, are not well suited, as they are inaccurate or computationally expensive. We introduce an efficient iterative fitting method, named ParFit, that finds parameters using only a few network samples, based on the Robbins-Monro algorithm. We test ParFit on three well-known graph models, namely Erdős-Rényi, Chung-Lu, and geometric inhomogeneous random graphs, as well as on real-world networks, including web networks. We find that ParFit performs well in terms of quality and running time across most parameter configurations.