Max Hahn-Klimroth

Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth et al.

We study the group testing problem where the goal is to identify a set of k infected individuals carrying a rare disease within a population of size n, based on the outcomes of pooled tests which return positive whenever there is at least one infected individual in the tested group. We consider two different simple random procedures for assigning individuals to tests: the constant-column design and Bernoulli design. Our first set of results concerns the fundamental statistical limits. For the constant-column design, we give a new information-theoretic lower bound which implies that the proportion of correctly identifiable infected individuals undergoes a sharp "all-or-nothing" phase transition when the number of tests crosses a particular threshold. For the Bernoulli design, we determine the precise number of tests required to solve the associated detection problem (where the goal is to distinguish between a group testing instance and pure noise), improving both the upper and lower bounds of Truong, Aldridge, and Scarlett (2020). For both group testing models, we also study the power of computationally efficient (polynomial-time) inference procedures. We determine the precise number of tests required for the class of low-degree polynomial algorithms to solve the detection problem. This provides evidence for an inherent computational-statistical gap in both the detection and recovery problems at small sparsity levels. Notably, our evidence is contrary to that of Iliopoulos and Zadik (2021), who predicted the absence of a computational-statistical gap in the Bernoulli design.

Petra Berenbrink, Max Hahn-Klimroth, Dominik Kaaser et al.

We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al.\ [2003]. In this model, a small subset of nodes from a network are the source of a rumor. In discrete time steps, each informed node "infects" each of its uninformed neighbors with probability $p$. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model, see, e.g., Lokhov [NeurIPS'16] or Mastakouri et al. [NeurIPS'20]. In this work we present a maximum likelihood estimator for the rumor's source, given a snapshot of the process in terms of a set of active nodes $X$ after $t$ steps. Our results show that, for cycle-free graphs, the likelihood estimator undergoes a non-trivial phase transition as a function $t$. We provide a rigorous analysis for two prominent classes of acyclic network, namely $d$-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.

Abdou Majeed Alidou, Júlia Baligács, Max Hahn-Klimroth et al.

Polarization and unexpected correlations between opinions on diverse topics (including in politics, culture and consumer choices) are an object of sustained attention. However, numerous theoretical models do not seem to convincingly explain these phenomena. This paper is motivated by a recent line of work, studying models where polarization can be explained in terms of biased assimilation and geometric interplay between opinions on various topics. The agent opinions are represented as unit vectors on a multidimensional sphere and updated according to geometric rules. In contrast to previous work, we focus on the classical opinion exchange setting, where the agents update their opinions in discrete time steps, with a pair of agents interacting randomly at every step. The opinions are updated according to an update rule belonging to a general class. Our findings are twofold. First, polarization appears to be ubiquitous in the class of models we study, requiring only relatively modest assumptions reflecting biased assimilation. Second, there is a qualitative difference between two-dimensional dynamics on the one hand, and three or more dimensions on the other. Accordingly, we prove almost sure polarization for a large class of update rules in two dimensions. Then, we prove polarization in three and more dimensions in more limited cases and try to shed light on central difficulties that are absent in two dimensions.

Yannick Gerstorfer, Lena Krieg, Max Hahn-Klimroth

In many studies, we want to determine the influence of certain features on a dependent variable. More specifically, we are interested in the strength of the influence -- i.e., is the feature relevant? -- and, if so, how the feature influences the dependent variable. Recently, data-driven approaches such as \emph{random forest regression} have found their way into applications (Boulesteix et al., 2012). These models allow to directly derive measures of feature importance, which are a natural indicator of the strength of the influence. For the relevant features, the correlation or rank correlation between the feature and the dependent variable has typically been used to determine the nature of the influence. More recent methods, some of which can also measure interactions between features, are based on a modeling approach. In particular, when machine learning models are used, SHAP scores are a recent and prominent method to determine these trends (Lundberg et al., 2017). In this paper, we introduce a novel notion of feature importance based on the well-studied Gram-Schmidt decorrelation method. Furthermore, we propose two estimators for identifying trends in the data using random forest regression, the so-called absolute and relative transversal rate. We empirically compare the properties of our estimators with those of well-established estimators on a variety of synthetic and real-world datasets.

Max Hahn-Klimroth, Dominik Kaaser, Malin Rau

In the pooled data problem we are given $n$ agents with hidden state bits, either $0$ or $1$. The hidden states are unknown and can be seen as the underlying ground truth $σ$. To uncover that ground truth, we are given a querying method that queries multiple agents at a time. Each query reports the sum of the states of the queried agents. Our goal is to learn the hidden state bits using as few queries as possible. So far, most literature deals with exact reconstruction of all hidden state bits. We study a more relaxed variant in which we allow a small fraction of agents to be classified incorrectly. This becomes particularly relevant in the noisy variant of the pooled data problem where the queries' results are subject to random noise. In this setting, we provide a doubly regular test design that assigns agents to queries. For this design we analyze an approximate reconstruction algorithm that estimates the hidden bits in a greedy fashion. We give a rigorous analysis of the algorithm's performance, its error probability, and its approximation quality. As a main technical novelty, our analysis is uniform in the degree of noise and the sparsity of $σ$. Finally, simulations back up our theoretical findings and provide strong empirical evidence that our algorithm works well for realistic sample sizes.

Max Hahn-Klimroth, Paul W. Dierkes, Matthias W. Kleespies

In several branches of the social sciences and humanities, surveys based on standardized questionnaires are a prominent research tool. While there are a variety of ways to analyze the data, some standard procedures have become established. When those surveys want to analyze differences in the answer patterns of different groups (e.g., countries, gender, age, ...), these procedures can only be carried out in a meaningful way if there is measurement invariance, i.e., the measured construct has psychometric equivalence across groups. As recently raised as an open problem by Sauerwein et al. (2021), new evaluation methods that work in the absence of measurement invariance are needed. This paper promotes an unsupervised learning-based approach to such research data by proposing a procedure that works in three phases: data preparation, clustering of questionnaires, and measuring similarity based on the obtained clustering and the properties of each group. We generate synthetic data in three data sets, which allows us to compare our approach with the PCA approach under measurement invariance and under violated measurement invariance. As a main result, we obtain that the approach provides a natural comparison between groups and a natural description of the response patterns of the groups. Moreover, it can be safely applied to a wide variety of data sets, even in the absence of measurement invariance. Finally, this approach allows us to translate (violations of) measurement invariance into a meaningful measure of similarity.

Max Hahn-Klimroth, João Pedro Meireles, Laurie Bingaman Lackey et al.

The depiction of populations - of humans or animals - as "population pyramids" is a useful tool for the assessment of various characteristics of populations at a glance. Although these visualisations are well-known objects in various communities, formalised and algorithmic approaches to gain information from these data are less present. Here, we present an algorithm-based classification of population data into "pyramids" of different shapes ([normal and inverted] pyramid / plunger / bell, [lower / middle / upper] diamond, column, hourglass) that are linked to specific characteristics of the population. To develop the algorithmic approach, we used data describing global zoo populations of mammals from 1970-2024. This algorithm-based approach delivers plausible classifications, in particular with respect to changes in population size linked to specific series of, and transitions between, different "pyramid" shapes. We believe this approach might become a useful tool for analysing and communicating historical population developments in multiple contexts and is of broad interest. Moreover, it might be useful for animal population management strategies.

AminCoja-Oghlan, Max Hahn-Klimroth, Philipp Loick et al.

The group testing problem asks for efficient pooling schemes and algorithms that allow to screen moderately large numbers of samples for rare infections. The goal is to accurately identify the infected samples while conducting the least possible number of tests. Exploring the use of techniques centred around the Belief Propagation message passing algorithm, we suggest a new test design that significantly increases the accuracy of the results. The new design comes with Belief Propagation as an efficient inference algorithm. Aiming for results on practical rather than asymptotic problem sizes, we conduct an experimental study.