Ranking systems based on pairwise comparisons are fundamental in decision-making applications, yet fairness concerns remain largely unaddressed, particularly in active ranking frameworks. We propose a novel fairness-aware active ranking approach that adaptively queries pairwise preferences to construct rankings that are both probably approximately correct (PAC) and fair. We propose a flexible cascaded norm-based objective that balances error distribution within and across socially salient groups, providing a unified framework to mitigate systemic disparities. Adopting our objective function allows us to explore fundamental fairness concepts like equal or proportionate errors within a unified framework. We develop both group-blind and group-aware algorithms and derive their sample complexity bounds. Empirical evaluations on real-world datasets, including COMPAS and German Credit, demonstrate the efficiency of our approach, reducing sample complexity while achieving fairer rankings. Our findings offer theoretical insights and practical methods to enhance fairness in active ranking systems, improving their reliability in hiring, recommendations, and other applications.

We study the problem of approximately counting cliques and near-cliques in a graph, where the access to the graph is only available through crawling its vertices. This model has been introduced recently to capture real-life scenarios in which the entire graph is too massive to be stored as a whole or be scanned entirely. Sampling vertices independently is non-trivial in this model, thus algorithms which rely on sampling often use a random walk. The goal is to provide an accurate estimate by seeing only a small portion of the graph. This model is known as the random walk model or the neighborhood query model. We introduce DeMEtRIS : Dense Motif Estimation through Random Incident Sampling. This method provides a scalable algorithm for clique and near-clique counting in the random walk model. We prove the correctness of our algorithm through rigorous mathematical analysis and extensive experiments. Both our theoretical results and our experiments show that DeMEtRIS obtains a high precision estimation by only crawling a sub-linear portion on vertices. Therefore, we demonstrate a significant improvement over previous known results.

We study the problem of resilient clustering in the metric setting where one is interested in designing algorithms that return high quality solutions that preserve the clustering structure under perturbations of the input points. Our first contribution is to introduce a formal notion of algorithmic resiliency for clustering problems that, roughly speaking, requires an algorithm to have similar outputs on close inputs. Then, we notice that classic algorithms have weak resiliency guarantees and develop new algorithms for fundamental clustering problems such as k-center, k-median, and k-means. Finally, we complement our results with an experimental analysis showing the effectiveness of our techniques on real-world instances.

Online navigation platforms are well optimized to solve the standard objective of minimizing travel time and typically require precomputation-based architectures (such as Contraction Hierarchies and Customizable Route Planning) to do so in a fast manner. The reason for this dependence is the size of the graph that represents the road network, which is large. The need to go beyond minimizing the travel time and introduce various types of customizations has led to approaches that rely on alternative route computation or, more generally, small subgraph extraction. On a small subgraph, one can run computationally expensive algorithms at query time and compute optimal solutions for multiple routing problems. In this framework, it is critical for the subgraph to (a) be small and (b) include (near) optimal routes for a collection of customizations. This is precisely the setting that we study in this work. We design algorithms that extract a subgraph connecting designated terminals with the objective of minimizing the subgraph's size and the constraint of including near-optimal routes for a set of predefined cost functions. We provide theoretical guarantees for our algorithms and evaluate them empirically using real-world road networks.

We study the problem of approximately counting cliques and near cliques in a graph, where the access to the graph is only available through crawling its vertices; thus typically seeing only a small portion of it. This model, known as the random walk model or the neighborhood query model has been introduced recently and captures real-life scenarios in which the entire graph is too massive to be stored as a whole or be scanned entirely and sampling vertices independently is non-trivial in it.

Social networks have become an inseparable part of human life and processing them in an efficient manner is a top priority in the study of networks. These networks are highly dynamic and they are growing incessantly. Inspired by the concept of triadic closure, we propose a probabilistic mechanism to model the evolution of these dynamic graphs. Although triadic closure is ubiquitous in social networks and its presence helps forming communities, probabilistic models encapsulating it have not been studied adequately.We theoretically analyze our model and show how to bound the growth rate of some characteristics of the graph, such as degree of vertices. Leveraging our theoretical results, we develop a scheduling subroutine to process modifications o f t he graph in batches. Our scheduling subroutine is then used to speed up the state-of-the-art algorithms with negligible loss in their approximation guarantees. We demonstrate the applicability of our method by applying it to the densest subgraph discovery problem.

In this paper we consider clustering problems in which each point is endowed with a color. The goal is to cluster the points to minimize the classical clustering cost but with the additional constraint that no color is over-represented in any cluster. This problem is motivated by practical clustering settings, e.g., in clustering news articles where the color of an article is its source, it is preferable that no single news source dominates any cluster. For the most general version of this problem, we obtain an algorithm that has provable guarantees of performance; our algorithm is based on finding a fractional solution using a linear program and rounding the solution subsequently. For the special case of the problem where no color has an absolute majority in any cluster, we obtain a simpler combinatorial algorithm also with provable guarantees. Experiments on real-world data shows that our algorithms are effective in finding good clustering without over-representation.