Pair-Matching: Link Prediction with Adaptive Queries

Christophe Giraud (1, 2) , Yann Issartel (3, 4, 1) , Luc Lehericy (1, 5) , Matthieu Lerasle (6, 7, 8, 9, 1)

1 LMO - Laboratoire de Mathématiques d'Orsay
2 CELESTE - Statistique mathématique et apprentissage
3 LTCI - Laboratoire Traitement et Communication de l'Information
4 Télécom Paris
5 LJAD - Laboratoire Jean Alexandre Dieudonné
6 ENSAE - Ecole Nationale de la Statistique et de l'Analyse Economique
7 FAIRPLAY - IA coopérative : équité, vie privée, incitations
8 CREST - Centre de Recherche en Économie et Statistique
9 ENSAE Paris - École Nationale de la Statistique et de l'Administration Économique

The pair-matching problem appears in many applications where one wants to discover good matches between pairs of entities or individuals. Formally, the set of individuals is represented by the nodes of a graph where the edges, unobserved at first, represent the good matches. The algorithm queries pairs of nodes and observes the presence/absence of edges. Its goal is to discover as many edges as possible with a fixed budget of queries. Pair-matching is a particular instance of multi-armed bandit problem in which the arms are pairs of individuals and the rewards are edges linking these pairs. This bandit problem is non-standard though, as each arm can only be played once. Given this last constraint, sub-linear regret can be expected only if the graph presents some underlying structure. This paper shows that sub-linear regret is achievable in the case where the graph is generated according to a Stochastic Block Model (SBM) with two communities. Optimal regret bounds are computed for this pair-matching problem. They exhibit a phase transition related to the Kesten-Stigum threshold for community detection in SBM. The pair-matching problem is considered in the case where each node is constrained to be sampled less than a given amount of times. We show how optimal regret rates depend on this constraint. The paper is concluded by a conjecture regarding the optimal regret when the number of communities is larger than 2. Contrary to the two communities case, we argue that a statistical-computational gap would appear in this problem.

Mots clés: sequential matching; Adaptive link prediction; stochastic block model

Domaines: Statistiques [math.ST]

Christophe Giraud, Yann Issartel, Luc Lehericy, Matthieu Lerasle. Pair-Matching: Link Prediction with Adaptive Queries. Mathematical Statistics and Learning, 2024. ⟨hal-04578273⟩