Eindhoven SPOR Seminar

To be added.

Consider a situation where a number of objects acting to maximize their own satisfaction are to be matched. Each object ranks the other objects and a matching is then said to be stable if there is no pair of objects that would prefer to be matched to each other rather than their current partners. We consider stable matching of the vertices in the complete graph based on i.i.d. exponential edge costs. Our results concern the total cost of the matching, the typical cost and rank of an edge in the matching, and the sensitivity of the matching and the matching cost to small perturbations of the underlying edge costs.

Submodular cover is a common generalisation of set cover, integer cover, and the minimum weight spanning tree problem. In the submodular cover problem, we are given a submodular, nonnegative, and monotone non-decreasing function f defined on all subsets of a finite ground set E, and the task is to find a subset S satisfying f(S)=f(E) of minimum cost for some given cost function on E.
It is known that a naive greedy heuristic, which starts with the empty set, and iteratively adds elements of optimal ratio between cost and marginal coverage has a performance ratio of of 1+ ln k, where k is the maximum f-value of a singleton (Wolsey 1982). This performance guarantee is nearly best possible, even in the special case of set cover (Feige 1996).
We propose and discuss a modification of the greedy algorithm where redundant elements are deleted in each iteration. We show that this modified greedy algorithm is guaranteed to terminate with an optimal solution to the submodular cover problem in case of submodular systems satisfying certain properties which are easily seen to be fulfilled by e.g. laminar set cover and weighted matroid rank functions.
(Joint work with Niklas Rieken and José Verschae.)

An (“ordinary”) proper vertex-colouring of a graph is an assignment of colours to the vertices of the graph such that adjacent vertices get different colours. Another way to look at this is to observe that this means that vertices that receive the same colour must form a set with no edges between them, i.e. an independent set of vertices. Hence a vertex-colouring is a covering of all vertices by independent sets. If we allow fractional weights of independent sets, but such that every vertex still needs to be included in independent sets of total weigh at least one, we get a so-called fractional colouring of the graph.

In this talk we consider the following problem: given a fractional colouring of a graph, what does this tell us about ordinary colourings of that graph?

This is joint work with Xinyi Xu.

In this paper, we propose a model-agnostic post-hoc explanation procedure devoted to computing feature attribution. The proposed method, termed Sparseness-Optimized Feature Importance (SOFI), entails solving an optimization problem related to the sparseness of feature importance explanations. The intuition behind this property is that the model’s performance is severely affected after marginalizing the most important features while remaining largely unaffected after marginalizing the least important ones. Existing post-hoc feature attribution methods do not optimize this property directly but rather implement proxies to obtain this behavior. Numerical simulations using both structured (tabular) and unstructured (image) classification datasets show the superiority of our proposal compared with state-of-the-art feature attribution explanation methods. The implementation of the method is available on https://github.com/igraugar/sofi

Model checking algorithms determine whether a given mathematical structure satisfies a given property, expressed as a logic formula. Model checking is an important tool in software verification: when applied to mathematical models of software, model checking guarantees that software is bug-free. Model checking is an active field of research, and new algorithms are typically tested on randomly generated models. This raises the question which random models make appropriate test cases, and which random models show ‘degenerate’ behaviour.

In this joint work with Yanni Dong and Mariëlle Stoelinga, we answer this question for Erdős-Rényi type Kripke structures, a prominent graph-like model for software, and LTL and CTL, two prominent logics to express software properties. We give new, self-contained proofs for the established result that these structures follow 0-1 laws: the probability that a random model satisfies a given logic formula goes to either 0 or 1 as its size goes to infinity. We furthermore develop algorithms that determine whether this outcome is asymptotically 0 or 1. Together, these results show that Erdős-Rényi models are unsuitable for testing model checkers, as we can build fast model checkers that are almost always correct, without even taking the model into account.

In many networks nodes have features from geometric spaces. However, in the case of clustering geometric graphs—the task of identifying groups of tightly connected nodes in a graph—can be rather difficult. The widely used method of spectral clustering is mostly inefficient for these graphs. It is based on the eigenvector of the adjacency matrix associated with the second eigenvalue. For geometric graphs such a vector provides information about the geometric structure but does not allow to recover the cluster structure.

We present an effective generalization of this method, which we call higher-order spectral clustering. It resembles in concept the classical spectral clustering method but uses for partitioning the eigenvector associated with a higher-order eigenvalue. As it will be shown, this algorithm gives the almost exact recovery of clusters for a wide class of geometric graphs sampled from Soft Geometric Block Model. A small adjustment of the algorithm provides the exact recovery. We also show that our method is effective in numerical experiments for real world networks.

This is a joint work with Andrei Bobu (Criteo) and Maximilien Dreveton (EPFL).

Link to the paper: https://link.springer.com/content/pdf/10.1007/s00041-021-09825-2.pdf

I will talk about two separate projects where random walks are building a random tree, yielding preferential attachment behaviour from completely local mechanisms.

First, the Tree Builder Random Walk is a randomly growing tree, built by a walker as she is walking around the tree. At each time n, she adds a leaf to her current vertex with probability $n^{-\gamma}$, $\gamma \in (2/3, 1]$, then moves to a uniform random neighbor on the possibly modified tree. We show that the tree process at its growth times, after a random finite number of steps, can be coupled to be identical to the Barabási-Albert preferential attachment tree model. This coupling implies that many properties known for the BA-model, such as diameter and degree distribution, can be directly transferred to our model. Joint work with János Engländer, Giulio Iacobelli, and Rodrigo Ribeiro, https://arxiv.org/abs/2311.18734.

Second, we introduce a network-of-networks model for physical networks: we randomly grow subgraphs of an ambient graph (say, a box of $\Z^d$) until they hit each other, building a tree from how these spatially extended nodes touch each other. We compute non-rigorously the degree distribution exponent of this tree in large generality, and offer a novel way, the Physical Laplacian, to measure the effects of physicality on the network structure. We also provide a rigorous analysis when the nodes are loop-erased random walks in dimension $d=2$ or $d\ge 5$, using a connection with the Uniform Spanning Tree. Joint work with Ádám Timár, Sigurdur Örn Stefánsson, Ivan Bonamassa, and Márton Pósfai, https://arxiv.org/abs/2306.01583, to appear in Nature Communications.

The interplay between the properties of graphs and the eigenvalues of their adjacency matrices is well-studied. Important graph invariants, such as diameter and chromatic number, can be understood using these eigenvalue techniques. In this talk, we bring these classical techniques in algebraic graph theory to the study of quantum walks.

A system of interacting quantum qubits can be modelled by a quantum process on an underlying graph and is, in some sense, a quantum analogue of random walk. This gives rise to a rich connection between graph theory, linear algebra and quantum computing. In this talk, I will give an overview of applications of algebraic graph theory in quantum walks, as well as various recent results.

In a recent paper with V. Schmeits, we show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to a model of discrete-time quantum walk proposed by H. Zhan [J. Algebraic Combin. 53(4):1187-1213, 2020], whose transition matrix is given by two reflections, using the face and vertex incidence relations of a graph embedded in an orientable surface. For the vertex-face walk and more general 2-reflection quantum walks, we prove theorems about perfect state transfer and periodicity and give infinite families of examples where these occur.

Gaussian graphical lasso is a powerful tool for modelling sparse dependence structure for non-extreme data. For extreme data, Gaussian graphical model is not suitable. Instead, Huesler-Reiss graphical model was recently proposed as an alternative. The adaptation of graphical lasso in this scenario is not straightforward due to the different structure in parameter matrix. We propose a graphical lasso for Huesler-Reiss graphical model through a reparametrization. The estimator is solved via a penalized likelihood and enjoys convenient properties of the traditional graphical lasso: concentration equalities, fast computation and the ability to scale up to large dimensions.

It is a notorious open question whether integer programs (IPs) of the form max {p^T x : Mx <= h, x in Z^n}, where all square submatrices of M have their determinants bounded by a constant Delta in absolute value, can be solved in polynomial time.

We consider the case in which we further require that by removing a constant number of rows and columns from M, one obtains a submatrix A that is totally unimodular (TU). In virtue of Seymour’s decomposition of TU matrices, there are two base cases to consider, namely the case where A is a network matrix and that where A is the transpose of a network matrix. We show that the IP can be solved in strongly polynomial time in the second base case, that is, when A is the transpose of a network matrix. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory.

First, we derive a strong proximity result for the case where M becomes TU after removing k rows only, where k is a constant. In particular, we show that given an optimal solution of the linear programming relaxation, an optimal solution to the IP can be obtained by finding a constant number of augmentations by circuit vectors.

Second, we focus on the case where A is the transpose of a network matrix. We reformulate the IP as a maximum constrained potential problem on a graph G. In this context, circuit vectors have a natural combinatorial interpretation: they correspond to “doubly connected sets”. As part of the input, every vertex has an associated vector of k integer weights. These define a natural set of *roots*, namely, the vertices whose weight vector is nonzero. We observe that if G is 2-connected, then it has no rooted K_{2,t}-minor for t = \Omega(k \Delta). We leverage this to obtain a tree-decomposition of G into highly structured graphs for which we can solve the problem locally. This allows us to solve the global problem via dynamic programming.

This is joint work with Manuel Aprile, Gwenaël Joret, Stefan Kober, Michał Seweryn, Stefan Weltge and Yelena Yuditsky.

We will discuss some of our recent work advancing two data mining subfields that can be seen as cousins of each other.

Clustering strives to partition a dataset into coherent groups. This becomes challenging when the natural shape of the clusters in the data space is nonconvex, and when there is a considerable amount of noise in the data. We introduce SpectACl (Spectral Averagely-dense Clustering), a new clustering method introducing a small but important change of the popular Spectral Clustering method, that is motivated by filling a gap in the theory of kernel-based clustering methods. SpectACl finds clusters having a large average density, where the appropriate density for each cluster is automatically determined through the spectrum of the weighted adjacency matrix. This opens up a comparison to the density-based DBSCAN clustering method, eliminating the parameter sensitivity issues from which DBSCAN suffers. As in the Spectral Clustering pipeline, the final step of SpectACl is an embedding postprocessing step using k-means. However, unlike Spectral Clustering, we demonstrate the fundamental soundness of applying k-means to the embedding step in SpectACL: from SpectACl’s objective function we derive an upper bound by means of the eigenvector decomposition; we derive that the optimization of our upper bound is equal to k-means on the eigenvectors.

Exceptional Model Mining (EMM) strives to find subgroups in a dataset that behave somehow exceptionally. We partition the columns of the dataset into two sets. The one set is used for defining candidate subgroups (by making conjunctions of conditions on single attributes); a challenge lies in efficiently traversing the search space of candidate subgroups. The other set is used for evaluating exceptionality of subgroup behavior: we define a kind of interaction between these target columns, and deem subgroups to be exceptional if parameters of this interaction have exceptional values. We will illustrate this concept with three types of interaction: standard linear regression and its implications for the price of rice in China, nonlinear mixed models and their application on potato growth, and preferences (where the target columns become a ranking of discrete objects) and their application on sushi and elections. The last kind of interaction turns EMM into Exceptional Preferences Mining. It can be made more intelligent by incorporating clustering-like behavior into the function that determines exceptionality.

We consider the classical continuous-time interacting particle system for 2-opinion dynamics known as the voter process on a random d-regular graph.It is well known that this particle system is dual to a system of coalescing random walkers and that in this geometrical setting, as the graph size increases, the time to reach consensus grows quadratically with the number of nodes n.

We study the time-evolution of the density of the discordant edges (i.e. edges with different opinions at their end vertices) until the consensus is reached. This observable can be thought as the dynamic “perimeter” associated to the density of opinions of one type in the given network (the latter to be seen as the “volume”). While the volume of one opinion evolves as a martingale until the consensus time, the density of discordant edges (i.e. the perimeter) undergoes a very different metastable evolution which we make precise.

If time permits we will discuss extensions to the directed configuration models.

Antiblocking duality is a key piece in the theory of polyhedral combinatorics. This concept can be applied to convex corners which are not polyhedra, and can be interpreted in a general setting of norm or gauge duality. In this talk I will carefully explain what all of this means, and I will show an application to derive an alternative formulation for the celebrated Lovász theta number of a graph. I will also comment on other recent applications, and possible avenues for further investigation.

In this talk we will introduce a rate balance principle for general (not necessarily Markovian) stochastic processes. The usefulness of this principle will be demonstrated by deriving well-known as well as new results for queues with state-dependent arrival and services processes.

In two-stage robust optimization (2RO) we tackle optimization problems with an inherent two-stage structure involving uncertainty in the problem parameters. This type of problems has a wide range of applications especially in the field of operations research. However, when the decision variables are integer, these problems are computationally extremely challenging and there is still a lack of efficient approximation algorithms.

In the first part of this talk we consider the so called k-adaptability approach, where a set of k second-stage solutions is calculated already in the first-stage which leads to approximate solutions of the problem. While this approach attained increasing popularity, nothing is known about its approximation guarantees for 2RO. We derive the first known approximation guarantees depending on the number of solutions k, which lead to several interesting insights on the complexity of the problem.

In the second part we consider a deep learning approach to solve 2RO, where a neural network is trained on small-dimensional instances to predict the second-stage optimal values. This neural network is then incorporated into a column-and-constraint generation algorithm (a classical exact method to solve 2RO), leading to significant improvements in computation time and often even solution quality.

The interest in this talk is on quantifying dependence between a finite number of random vectors. We focus on copula-based dependence quantification between multiple groups of random variables of possibly different sizes. This is done via a family of Phi-divergences (which includes for example mutual information). A theoretical framework is provided, and the divergence measures are illustrated by means of examples. Special attention goes to elliptical copulas, with Gaussian and Student’s t copulas as exemplary cases. Parametric and semi-parametric estimation procedures for the divergence measures are briefly discussed. These divergence measures are then used for measuring the similarity between variable clusters in an agglomerative hierarchical procedure. An example involving cluster analysis of continuous random variables is presented.

This talk is based on joint work with Steven De Keyser.

There is a current trend on reevaluating artificial intelligence (AI), its advancements and their implications to society. Uncertainty treatment plays a major role in this discussion. This talk will hopefully convince you that we can make AI more reliable and trustworthy by a sound treatment of uncertainty. Uncertainty is often modelled by probabilities, while it has been argued that some broadening of probability theory is required for a more convincing treatment, as one may not always be able to provide a reliable probability for every situation. Credal models generalize probability theory to allow for partial probability specifications and are arguably a good direction to follow when information is scarce, vague, and/or conflicting. We will present and discuss credal approaches from simple examples to sophisticated credal machine learning models and even their reach into both adversarial and causal inferences. The talk argues that we must continue to push AI forward by investing in Cautious AI.

Investigating a cluster of deaths on a hospital ward is a difficult task for medical investigators, police, and courts. Patients do die in hospitals (the three most common causes of deaths in a hospital are, in order: cancer, heart disease, medical errors). Often such cases come to the attention of police investigators for two reasons: gossip about a particular nurse is circulating just as a couple of unexpected and disturbing events occur. Hospital investigators see a pattern and call in the police.

I will discuss two such cases with which I have been intensively involved. The first one is the case of the Dutch nurse Lucia de Berk. Arrested in 2001, convicted by a succession of courts up to the supreme court by 2005, after which a long fight started to get her a re-trial. She was completely exonerated in 2010. The second case is that of the English nurse Lucy Letby. Arrested in 2018, 2019 and 2020 for murders taking place in 2015 and 2016. Her trial started in 2022 and concluded with a “full life” sentence a couple of months ago.

There are many similarities between the two cases, but also a couple of disturbing differences. One difference being that Lucy Letby’s lawyers seem to have made no attempt whatsoever to defend her. Another difference is that statistics was used against Lucia de Berk but not, apparently, against Lucy Letby. But appearances are not always what they seem.

Report published by Royal Statistical Society on statistical issues in these cases
https://rss.org.uk/news-publication/news-publications/2022/section-group-reports/rss-publishes-report-on-dealing-with-uncertainty-i/

News feature in “Science” about myself and my work
https://www.science.org/content/article/unlucky-numbers-fighting-murder-convictions-rest-shoddy-stats

Recursive distributional equations (RDE) appear in various areas of probability such as the probabilistic analysis of algorithms, probabilistic number theory, stochastic geometry or, more recently, in distributional reinforcement learning (DRL). In this talk more applied aspects of RDE are discussed in the context of their applications. Some of the new results discussed on DRL are joint work with Julian Gerstenberg and Denis Spiegel

Via a new probabilistic result, we provide (1+o(1))-asymptotics for the number of integer sequences n-1>= d_1 >= … >= d_n >= 0 that form the degree sequence of an n-vertex graph (improving both the upper and lower bound by a multiplicative n^{1/4}-factor). In particular, we determine the asymptotic probability that the integral of a (lazy) simple symmetric random walk bridge remains non-negative. This talk will explain how this problem arose, what the connection is with the problem about random walks (including what all the words in this abstract mean) and then provide a short sketch of the proof. This is based on joint work with Paul Balister, Serte Donderwinkel, Tom Johnston and Alex Scott.

Over the past 20 years, the Santa Claus problem has been the source of many beautiful algorithmic ideas and to date remains an active and fruitful research area. The problem takes its metaphorical name from the narrative of Santa Claus distributing his gifts to children in a way that the least happy child is as happy as possible. I will give an overview over the landscape of techniques used to approach the problem, previous results as well as open questions. Then I will focus on recent joint work with Bamas [STOC’23], where we make progress towards sublogarithmic approximations.

We consider a finite horizon online resource allocation/matching problem where the goal of the decision maker is to combine resources (from a finite set of resource types) into feasible configurations. Each configuration is specified by the number of resources consumed of each type and a reward. The resources are further subdivided into three types – offline, online-queueable (which arrive online and can be stored in a buffer), and online-nonqueueable (which arrive online and must be matched on arrival or lost). We prove the efficacy of a simple greedy algorithm when the corresponding static planning linear program (SPP) exhibits a non-degeneracy condition called the general position gap (GPG). In particular we prove that, (i) our greedy algorithm gets bounded any-time regret when no configuration contains both an online-queueable and an online-nonqueueable resource, and (ii) O(log t) expected any-time regret otherwise (we also prove a matching lower bound). By considering the three types of resources, our matching framework encompasses several well-studied problems such as dynamic multi-sided matching, network revenue management, online stochastic packing, and multiclass queueing systems.

It has been well-known since Aldous’ seminal work in the 90s that a critical Galton-Watson tree conditioned to survive until generation n converges, as n goes to infinity, to a continuous random tree (CRT). This is the equivalent, in the world of random trees, of the fact that a random walk with finite-variance i.i.d. increments converges to the Brownian motion. In this is joint work with Guillaume Conchon-Kerjan and Daniel Kious, we prove that a Galton-Watson tree “in random environment” (GWRE) also converges to the CRT. GWREs are GW trees in which the offspring distribution of an individual depends on its generation, and the sequence of offspring distributions (indexed by the generation) is sampled in an i.i.d. way. I will review known results on GWREs before stating our main result and giving ideas of the proof.

During this seminar, two postdocs within our cluster will introduce themselves and their research.

We discuss recent developments in the use of interacting particles for solving high-dimensional optimization problems, and provide insights into analytical guarantees for convergence in the particle mean-field limit.

Symbolic Data Analysis gives a new way of thinking in Data Science by extending the standard variables to take into consideration new kinds of data, called “symbolic”, as they cannot be reduced to numbers without losing much information. Interval data are a prime example of symbolic data. There have been a series of proposed adaptations of the Principal Component Analysis method for interval-valued symbolic data, all of which have the downside of having intermediate steps that deal with conventional data. In this talk, we use algebraic structures on the intervals, to define symbolic principal components as linear combinations of the intervals that maximise the symbolic variance. This framework provides the mathematical tools needed to use the symbolic principal components to transform the original data in a way that is mathematically coherent with the remainder of the framework and defines the principal components as solutions to maximisation problems, like what is done in conventional Principal Component Analysis. As in the conventional case, our formulation of interval-based principal component analysis can be seen as a dimensionality reduction method, since we explicitly project the original symbolic observations on the reduced space spanned by the first principal components. We conclude by exploring real-world data from the telecommunications sector, in an attempt to detect Internet redirection attacks in real time. Joint work with Rodrigo Serrão Girão and Lina Oliveira

Multivariate extreme value distributions are a common choice for modelling multivariate extremes. In high dimensions, however, the construction of flexible and parsimonious models is challenging. We propose to combine bivariate extreme value distributions into a Markov random field with respect to a tree. Although in general not an extreme value distribution itself, this Markov tree is attracted by a multivariate extreme value distribution. The latter serves as a tree-based approximation to an unknown extreme value distribution with the given bivariate distributions as margins. Given data, we learn an appropriate tree structure by Prim’s algorithm with estimated pairwise upper tail dependence coefficients or Kendall’s tau values as edge weights. The distributions of pairs of connected variables can be fitted in various ways. The resulting tree-structured extreme value distribution allows for inference on rare event probabilities, as illustrated on river discharge data from the upper Danube basin. Based on joint work with Shuang Hu and Zuoxiang Peng.

During this seminar, three postdocs within our cluster will introduce themselves and their research.