Statistical and Probabilistic Methods in Algorithmic Data Analysis

Graph neural networks (GNNs) excel in learning from network-like data but often lack interpretability, making their application challenging in domains requiring transparent decision-making. We propose the Graph Kolmogorov–Arnold Network (GKAN), a novel GNN model leveraging spline-based activation functions on edges to enhance both accuracy and interpretability.

Given an underlying graph, we consider distributed dynamics that globally perform detection of planted communities. In the local communication model, we consider the following dynamics: Initially, each node locally chooses a value in $-1,1$, uniformly at random and independently of other nodes. Then, in each consecutive round, every node updates its local value to the average of the values held by its neighbors, at the same time applying an elementary, local clustering rule that only depends on the current and the previous values held by the node.

We prove that the process resulting from this dynamics produces a clustering that exactly or approximately (depending on the graph) reflects the underlying cut in logarithmic time, under various graph models that exhibit a sparse balanced cut, including the stochastic block model. We also prove that a natural extension of this dynamics performs community detection on a regularized version of the stochastic block model with multiple communities.

We further discuss more recent extensions of this work to different models of communication (e.g., population protocols) and more to the case of more communities.

The talk is mainly based on the following papers:

• $\mathrm{■}$

  Becchetti, Luca, et al. Find your place: Simple distributed algorithms for community detection. SIAM Journal on Computing 49.4 (2020): 821–864.

• $\mathrm{■}$

  Becchetti, L., Clementi, A., Manurangsi, P., Natale, E., Pasquale, F., Raghavendra, P., and Trevisan, L. (2018). Average whenever you meet: opportunistic protocols for community detection. In 26th Annual European Symposium on Algorithms: ESA 2018.

• $\mathrm{■}$

  Becchetti, Luca, Emilio Cruciani, Francesco Pasquale, and Sara Rizzo. Step-by-step community detection in volume-regular graphs. Theoretical Computer Science 847 (2020): 49–67.

Matching nodes in a graph $G=(V,E)$ is a well-studied algorithmic problem with many applications. The $b$-matching problem is a generalization that allows to match a node with up to $b$ neighbors.

This allows more flexible connectivity patterns whenever vertices may have multiple associations. The algorithm b-suitor [Khan et al., SISC 2016] is able to compute a (1/2)-approximation of a maximum weight b-matching in $O(|E|)$ time. Since real-world graphs often change over time, fast dynamic methods for b-matching optimization are desirable. In this work, we propose Dyn-b-suitor, a dynamic algorithm for the weighted b-matching problem. As a non-trivial extension to the dynamic Suitor algorithm for 1-matchings [Angriman et al., JEA 2022], our approach computes (1/2)-approximate b-matchings by identifying and updating affected vertices without static recomputation. Our proposed algorithm is fully-dynamic, i.e., it supports both edge insertions and deletions, and we prove that it computes the same solution as its static counterpart. In extensive experiments on real-world benchmark graphs and generated instances, our dynamic algorithm yields significant savings compared to the sequential b-suitor, e.g., for batch updates with 103 edges with an average acceleration factor of 103x. When comparing our sequential dynamic algorithm with the parallel (static) b-suitor on a 128-core machine, our dynamic algorithm is still 59x to 104x faster.

Agent-Based Models (ABMs) are used in several fields to study the evolution of complex systems according to micro-level assumptions. These models encode the causal mechanisms that drive the dynamic processes and have the advantage of being easy to interpret. However, they do not take advantage of the widespread availability of data, so their predictive power is often limited. In addition, there is no principled way to do parameter calibration and model selection. Finally, ABMs typically can not estimate agent-specific (or “micro”) state variables. In this talk, I showcase a line of research aimed at learning the latent parameters and micro-level variables of an ABM from data. The key idea is to cast the ABM into a probabilistic generative model. This transformation follows two general design principles: balance of stochasticity and data availability, and replacement of unobservable discrete choices with differentiable approximations. Given this new form of the model, we can derive a proper likelihood function and proceed to maximize the likelihood of the latent variables thanks to auto-differentiation and gradient-based optimization. I will show: (i) that a maximum likelihood approach for parameter estimation of opinion dynamics models outperforms the typical simulation-based approach, (ii) better forecasting on simulations of an ABM of the housing market, in which agents with different incomes bid higher prices to live in high-income neighborhoods, (iii) a real application to social media data of an opinion dynamics ABM, and (iv) a way to bypass the need to explicitly derive the likelihood, based on variational inference. I will conclude by reflecting on the importance of scientific models in a world of black-box, deep-learning models.

Graphs are a fundamental data structure in machine learning applications lying at the core of countless industrial applications. While traditional graph algorithms have not considered the privacy of the users providing the data, recently private graph analysis has received significant attention. In this talk, I will cover recent research in differentially private (DP) algorithms in graphs. DP is a strong notion of privacy guarantees promising plausible deniability for user data. I will cover our work on designing efficient graph algorithms with a variety of applications, including on solving the seemingly non-graph problem of sanitizing a private dataset of arbitrary items to extract as many items as possible, while respeciting user privacy.

Due to recent common ancestry, species belonging to the same genus are expected to be more similar with respect to their phenotype, and hence exhibit less niche divergence than species belonging to different genera. Consequently, congeneric species are expected to compete intensely for resources, and therefore to be segregated in space. Yet, despite the longstanding history of this hypothesis of congeneric competitive exclusion, empirical evidence in support of it is at best limited. Here, we analyze co-occurrence patterns of species that belong to the same genera in the mammalian fossil record kept in the NOW database, considering separately Europe during the Neogene, and North America during the Oligocene–Neogene. We assess co-occurrence patterns in comparison to baselines where competitive exclusion is obfuscated through randomization. We find that congeneric species occur together notably less than would be expected at random, with large herbivores being more segregated than large carnivorans and small mammals.

Structural bias or segregation of networks refers to situations where two or more disparate groups are present in the network, so that the groups are highly connected internally, but loosely connected to each other. Examples include polarized communities in social networks, antagonistic content in video-sharing or news-feed plat- forms, etc. In many cases it is of interest to increase the connectivity of disparate groups so as to, e.g., minimize social friction, or expose individuals to diverse viewpoints. A commonly-used mechanism for increasing the network connectivity is to add edge shortcuts between pairs of nodes. In many applications of interest, edge shortcuts typically translate to recommendations, e.g., what video to watch, or what news article to read next. The problem of reducing structural bias or segregation via edge shortcuts has recently been studied in the literature, and random walks have been an essential tool for modeling navigation and connectivity in the underlying networks. Existing methods, however, either do not offer approximation guarantees, or engineer the objective so that it satisfies certain desirable properties that simplify the optimization task. We address the problem of adding a given number of shortcut edges in the network so as to directly minimize the average hitting time and the maximum hitting time between two disparate groups. The objectives we study are more natural than objectives considered earlier in the literature (e.g., maximizing hitting-time reduction) and the optimization task is significantly more challenging. Our algorithm for minimizing average hitting time is a greedy bicriteria that relies on supermodularity. In contrast, maximum hitting time is not supermodular. Despite, we develop an approximation algorithm for that objective as well, by leveraging connections with average hitting time and the asymmetric k-center problem.

We consider a cooperative learning scenario where a collection of networked agents with individually owned classifiers dynamically update their predictions, for the same classification task, through communication or observations of each other’s predictions. Clearly if highly influential vertices use erroneous classifiers, there will be a negative effect on the accuracy of all the agents in the network. We ask the following question: how can we optimally fix the prediction of a few classifiers so as maximize the overall accuracy in the entire network. To this end we consider an aggregate and an egalitarian objective function. We show a polynomial time algorithm for optimizing the aggregate objective function, and show that optimizing the egalitarian objective function is NP-hard. Furthermore, we develop approximation algorithms for the egalitarian improvement. The performance of all of our algorithms are guaranteed by mathematical analysis and backed by experiments on synthetic and real data.

A Random Utility Model (RUM) is a classical model of user behavior defined by a utility distribution. A user, presented with a subset of items from $[n]$, will select the item of the subset with highest utility, according to a utility vector drawn from the distribution. In practical settings, the subset is often of small size, as in the “ten blue links” of web search.

In this talk, we will consider a learning setting with complete information on user choices from subsets of size at most k. We show that $k=\mathrm{\Theta }(\sqrt{n})$ is necessary and sufficient to predict the distribution of all user choices within an arbitrarily small constant error. Based on this upper bound, we obtain new algorithms for approximate RUM learning and variations thereof.

In the talks we will discuss algorithms for the dynamic k-median clustering problem. In this problem, the input data points are dynamically changing through insertions and (possibly) deletions, and the goal is to maintain a good clustering with a small number of changes to the cluster centers. In particular, we will discuss algorithms in the insertion only and fully dynamic setting and we will highlight the main ideas behind them.

We study the problem of regret minimization for a single bidder in a sequence of first-price auctions where the bidder discovers the item’s value only if the auction is won. Our main contribution is a complete characterization, up to logarithmic factors, of the minimax regret in terms of the auction’s transparency, which controls the amount of information on competing bids disclosed by the auctioneer at the end of each auction. Our results hold under different assumptions (stochastic, adversarial, and their smoothed variants) on the environment generating the bidder’s valuations and competing bids. These minimax rates reveal how the interplay between transparency and the nature of the environment affects how fast one can learn to bid optimally in first-price auctions.

Communities are most commonly modelled as (quasi-) cliques, assuming that everyone in the community knows everyone else with equal probability. In this talk I argue that this model is too simple. A better model for real-world communities can be obtained by considering the community to have a clique as a core and a tail of members who know increasingly smaller portion of the core. This model generalises many earlier models, including cliques and the core/periphery model (Borgatti & Everett, 1999).

Fitting the model to real-world Q/A-communities shows that the relative sizes of the cores of the communities stays constant (at around 16% of the community size) over time and over fluctuations in the community size.

To find the communities, the model can be expressed as a particular kind of matrix factorization: each community is an outer product of two vectors of nonnegative numbers such that (a permutation of) the values in the vectors form an arithmetic progression and this rank-1 matrix is thresholded to 0/1 matrix. To express the total graph as a union of such thresholded rank-1 matrices, the matrix multiplication must be taken over the max-times (or subtropical) algebra.

Online social networks are ubiquitous parts of modern societies and the discussions that take place in these networks impact people’s opinions on diverse topics, such as politics or vaccination. One of the most popular models to formally describe this opinion formation process is the Friedkin-Johnsen (FJ) model, which allows to define measures, such as the polarization and the disagreement of a network.

Recently, Xu, Bao and Zhang (WebConf’21) showed that all opinions and relevant measures in the FJ model can be approximated in near-linear time. However, their algorithm requires the entire network and the opinions of all nodes as input. Given the sheer size of online social networks and increasing data-access limitations, obtaining the entirety of this data might, however, be unrealistic in practice.

In this paper, we show that node opinions and all relevant measures, like polarization and disagreement, can be efficiently approximated in time that is sublinear in the size of the network. Particularly, our algorithms only require query-access to the network and do not have to preprocess the graph. Furthermore, we use a connection between FJ opinion dynamics and personalized PageRank, and show that in d-regular graphs, we can deterministically approximate each node’s opinion by only looking at a constant-size neighborhood, independently of the network size. We also experimentally validate that our estimation algorithms perform well in practice.

This paper appeared at the WebConf 2024 and is joint work with Yinhao Dong and Pan Peng.

The H-index of a node in a static network is the maximum value h such that at least h of its neighbors have a degree of at least h. Recently, a generalized version, the n-th order H-index, was introduced, allowing to relate degree centrality, H-index, and the k-core of a node. We extend the n-th order H-index to temporal networks and define corresponding temporal centrality measures and temporal core decompositions. Our n-th order temporal H-index respects the reachability in temporal networks leading to node rankings, which reflect the importance of nodes in spreading processes. We derive natural decompositions of temporal networks into subgraphs with strong temporal coherence. We analyze a recursive computation scheme and develop a highly scalable streaming algorithm. Our experimental evaluation demonstrates the efficiency of our algorithms and the conceptional validity of our approach. Specifically, we show that the n-th order temporal H-index is a strong heuristic for identifying super-spreaders in evolving social networks and detects temporally well-connected components.

The problem of continually releasing the value of a counter while ensuring privacy of individual inputs has received a lot of attention recently, in part because of applications in machine learning. This talk gives an overview of recent results on this problem, focusing on efficiency in the streaming setting. Several open problems are presented.

The $k$-center problem requires the selection of $k$ points (centers) out of a given metric pointset $P$ so to minimize the maximum distance any point of $P$ from the closest center. The talk examines a fair variant of the problem, known as fair center, where points are assigned to some category and each category may contribute a limited number of points to the center set. It presents the first sliding-windows streaming algorithm for fair center in general metric spaces. At any time $t$, the algorithm is able to provide a solution for the current window whose quality is almost as good as the one guaranteed by the best, polynomial-time sequential algorithms run on the entire window, and exhibits space and time requirements independent of the window size. Experimental evidence of the practical viability of the algorithm is also given.

Graph null models provide a framework for generating random graph samples that preserve specific structural properties, enabling comparison with observed networks to assess the statistical significance of observed patterns. Many null models in the literature progressively enforce stronger constraints on the graphs in the ensemble, making sampling from these models increasingly challenging. Among the various techniques proposed for this task are Markov Chain Monte Carlo (MCMC) algorithms. These algorithms generate random samples by constructing a Markov chain over the space defined by the graphs in the ensemble and ensuring convergence to the target distribution.

In this talk, I will explore the null models we developed for three distinct types of graphs: bipartite graphs modeling transactional datasets, colored multi-graphs, and directed hypergraphs. Using practical examples such as purchase networks, endorsement networks, and co-sponsorship data, we will see how selecting an appropriate null model can yield different insights into structural patterns. Additionally, I will discuss specialized double-edge swap operations such as restricted swaps and parity swaps, which are designed to ensure uniform and efficient sampling from our graph ensembles.

We present a novel technique to let streaming clustering algorithms adapt to arbitrary drifts in the distribution of the data stream. The goal is to compute, at each step, a clustering that best represents the current distribution of the data. In the streaming setting, this is traditionally attempted through the sliding-window mechanism, where the analysis is performed on the most recent fixed-size segment of the data. The problems with this approach are twofold: (1) setting the correct window size is challenging; and (2) a fixed window size cannot effectively track changes in the distribution happening at variable speed. In this talk, we focus on a family of center-based clustering methods that includes the popular $k$-median and $k$-means problems, and we propose a new methodology that adjusts the window size based on the drift of the data. The challenge is that it is not possible to explicitly estimate the drift, as we may have only a single data point from each distribution. Nonetheless, we prove that our methodology can adjust the window size as effectively as an algorithm that has knowledge of the magnitude of the drift. Furthermore, our solution exhibits the same multiplicative error as the best-known approximation algorithm for the same clustering problem in the no-drift case. We also demonstrate the practical effectiveness of our methodology through experiments on real data.

In classical statistics and distribution testing, it is often assumed that elements can be sampled exactly from some distribution $P$, and that when an element $x$ is sampled, the probability $P(x)$ of sampling $x$ is also known. In this setting, recent work in distribution testing has shown that many algorithms are robust in the sense that they still produce correct output if the elements are drawn from any distribution $Q$ that is sufficiently close to $P$. This phenomenon raises interesting questions: under what conditions is a “noisy” distribution $Q$ sufficient, and what is the algorithmic cost of coping with this noise? In this paper, we investigate these questions for the problem of estimating the sum of a multiset of $N$ real values $x_1,\mathrm{\dots },x_N$. This problem is well-studied in the statistical literature in the case $P=Q$, where the Hansen-Hurwitz estimator [Annals of Mathematical Statistics, 1943] is frequently used. We assume that for some (known) distribution $P$, values are sampled from a distribution $Q$ that is pointwise close to P. That is, there is a parameter such that for all $x_i$,

For every positive integer $k$ we define an estimator ${\zeta }_k$ for $\mu ={\sum }_i{x}_i$ whose bias is proportional to ${\gamma }^k$ (where our ${\zeta }_1$ reduces to the classical Hansen-Hurwitz estimator). As a special case, we show that if $Q$ is pointwise $\gamma$-close to uniform and all $x_i\in \{0,1\}$, for any $\epsilon >0$, we can estimate $\mu$ to within additive error $\epsilon N$ using $m=\mathrm{\Theta }(N^1-1/k/{\epsilon }^2/k)$ samples, where $k=\lceil (\log \epsilon )/(\log \gamma )\rceil$. We then show that this sample complexity is essentially optimal. Interestingly, our upper and lower bounds show that the sample complexity need not vary uniformly with the desired error parameter $\epsilon$: for some values of $\epsilon$, perturbations in its value have no asymptotic effect on the sample complexity, while for other values, any decrease in its value results in an asymptotically larger sample complexity.

We present fully-dynamic algorithms for efficiently maintaining epsilon-feasible decision trees, which are decision trees where the splitting features and values are near-optimal (up to an additive error of epsilon). We present deterministic algorithms with polylog amortized cost as well as polylog cost in the worst case. Our algorithms are near-optimal both in terms of memory requirement and running time (up to polylog factors), while maintaining optimal splits is not possible under the SETH conjecture. We then discuss how to extend our results so as to efficiently maintain random forests in a fully dynamic environment. Our extensive experimental evaluation against the state-of-the-art shows the effectiveness of our approach.

I will present a unified information geometric perspective on various approaches to statistical knowledge discovery in structured spaces. These approaches include pattern (itemset) mining, matrix and tensor decomposition, and mode interaction selection.

We study the problem of identifying one or more high-utility tuples by adaptively receiving user input on a minimum number of pairwise comparisons. We devise a single-pass streaming algorithm, which processes each tuple in the stream at most once, while ensuring that the memory size and the number of requested comparisons are in the worst case logarithmic in $n$, where $n$ is the number of all tuples.

Labeled training data is often scarce, unavailable, or can be very costly to obtain. To circumvent this problem, there is a growing interest in developing methods that can exploit sources of information other than labeled data, such as weak-supervision and zero-shot learning. While these techniques obtained impressive accuracy in practice, both for vision and language domains, they come with no theoretical characterization of their accuracy. In a sequence of recent works, we develop a rigorous mathematical framework for constructing and analyzing algorithms that combine multiple sources of related data to solve a new learning task. Our learning algorithms provably converge to models that have minimum empirical risk with respect to an adversarial choice over feasible labelings for a set of unlabeled data, where the feasibility of a labeling is computed through constraints defined by rigorously estimated statistics of the sources. Notably, these methods do not require the related sources to have the same labeling space as the multiclass classification task. We demonstrate the effectiveness of our approach with experimentations on various image classification tasks.

We present FSR, an efficient algorithm to identify statistically significant patterns with rigorous guarantees on the probability of false discoveries. FSR builds on a novel general framework for mining significant patterns that captures some of the most commonly considered patterns, including itemsets, sequential patterns, and subgroups. FSR uses a small number of resampled datasets, obtained by assigning i.i.d. labels to each transaction, to rigorously bound the supremum deviation of a quality statistic measuring the significance of patterns. FSR builds on novel tight bounds on the supremum deviation that require to mine a small number of resampled datasets, while providing a high effectiveness in discovering significant patterns. This is joint work with Leonardo Pellegrina.

Association Discovery is a powerful but misunderstood tool for data science. When done correctly, it can expose systematic interactions within data. The results are straightforward to interpret and often actionable. However, the standard framework for association discovery, the support/confidence framework is not fit for purpose. It often fails to uncover important interactions and usually hides those it does find with a flood of false and misleading purported associations. This talk explains the value of association discovery, exposes the limitations of the support/confidence framework, and presents self-sufficient itemsets, an alternative framework that avoids those limitations.