Pair-Matching: Links Prediction with Adaptive Queries

Abstract

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, sublinear regret can be expected only if the graph presents some underlying structure. This paper shows that sublinear 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.

arXiv comment78 pages

References in corpus (17)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Simple, Robust and Optimal Ranking from Pairwise Comparisons
• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants
• Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Undestanding Baseball Team Standings and Streaks
• Information-theoretic thresholds for community detection in sparse networks
• Information-theoretic thresholds for community detection in sparse networks
• Rotting Bandits
• Community Detection via Random and Adaptive Sampling
• Top-$K$ Ranking from Pairwise Comparisons: When Spectral Ranking is Optimal
• Robustness of spectral methods for community detection
• Exploring $k$ out of Top $\rho$ Fraction of Arms in Stochastic Bandits
• A Bayesian nonparametric approach for generalized Bradley-Terry models in random environment