Collaborative likelihood-ratio estimation over graphs

Alejandro de la Concha, Nicolas Vayatis, Argyris KalogeratosarXiv 2022 · arXiv

TL;DR

This paper introduces GRULSIF, the first graph-based framework for collaborative likelihood-ratio estimation (LRE). By leveraging the structural similarities between nodes in a graph, the method allows multiple agents to share information and estimate their local density ratios more accurately than they could individually, especially when local data is scarce.

What Problem Does This Paper Address?

Likelihood-ratio estimation (LRE)—calculating the ratio $r(x) = q(x)/p(x)$ between two probability density functions—is a fundamental tool in machine learning, powering everything from transfer learning and outlier detection to change-point analysis. Traditionally, LRE is treated as a "solo" task: you have one pair of distributions and you estimate one ratio.

However, modern data often comes from networks, such as a grid of weather sensors or a collection of hospitals. In these cases, each node has its own local distributions ($p_v$ and $q_v$), but these distributions are likely similar to those of neighboring nodes. Standard LRE methods either ignore this structure (solving each node independently) or pool all data together (washing out local differences). The authors address this gap by asking: How can local data sources collaborate to solve their respective tasks with higher precision by using the graph as a guide?

Methods

The authors propose Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF). Its key components include:

  • Relative Likelihood-Ratio: Instead of the standard ratio, they use the $\alpha$-relative ratio, which is bounded and numerically more stable.
  • Graph Regularization: They incorporate a Laplacian penalty term into the objective function. This enforces "smoothness" across the graph, essentially assuming that if two nodes are connected, their likelihood-ratio functions should be similar.
  • Vector-Valued RKHS (VV-RKHS): To handle multiple functions simultaneously, they use Vector-Valued Reproducing Kernel Hilbert Spaces. This allows the model to capture both the local data features and the global graph geometry in a single functional space.
  • Scalability via Nyström & CBCGD: To make the method practical for large graphs and datasets, they use Nyström dimensionality reduction to create a global "dictionary" of representative data points. They also implement a Cyclic Block Coordinate Gradient Descent (CBCGD) algorithm, which allows for distributed, asynchronous updates at each node.
Likelihood-ratio estimation over a graph G. Figure 1 visualizes how local data observations (left) are used to estimate node-specific likelihood-ratio functions (right) that are smoothed according to the graph structure.

Datasets

Because the true likelihood ratio is unknown in real-world data, the authors evaluated GRULSIF using four sophisticated synthetic scenarios:

  • Stochastic Block Model (SBM) Scenarios: Graphs with 4 clusters where nodes within a cluster share similar distribution changes.
  • Barabási-Albert (BA) Scenarios: Scale-free graphs where changes in distributions are localized to specific "ego-networks" (a node and its multi-hop neighbors).
  • Distributions: They used a variety of 1D, 2D, and 3D distributions, including Normal distributions, Uniform distributions, and Gaussian Mixtures, to simulate different types of statistical shifts.

Key Insights and Ideas

  • The Power of Collaboration: The core "aha" moment is that the graph structure acts as a powerful prior. When a node has very few samples, it can "borrow" statistical strength from its neighbors to produce a much cleaner estimate.
  • Global vs. Local Trade-off: The method successfully balances local heterogeneity (keeping node-specific estimates) with global consistency (smoothing via the graph).
  • The "POOL" Baseline: An interesting finding was that even without the graph edges, a variant they call POOL—which uses a global Nyström dictionary and joint hyperparameter selection—outperforms standard independent LRE methods. This suggests that joint dictionary learning is a significant benefit in itself.
  • Theoretical Justification: The authors derived convergence rates showing that the benefit of collaboration is most pronounced when the tasks are complex (high "effective dimension") and the available local data is minimal.

Key Results

  • Superior Accuracy: In all synthetic scenarios, GRULSIF consistently achieved lower Mean Squared Error (MSE) compared to state-of-the-art independent methods like RULSIF, ULSIF, and KLIEP.
  • Data Efficiency: The performance gain was most dramatic at small sample sizes (e.g., $n=50$ observations per node). As sample sizes increased, independent methods eventually caught up, but GRULSIF remained the most robust.
  • Bias Reduction: GRULSIF was particularly effective at reducing bias in nodes where no change occurred ($p_v = q_v$), where independent methods often "hallucinated" differences due to noise.

Limitations and Future Work

  • Fixed Graph Assumption: The current framework assumes the graph structure is known and fixed. In many real-world applications, the "similarity graph" between tasks might be unknown and need to be learned alongside the ratios.
  • Hyperparameter Sensitivity: While the authors provide a cross-validation strategy, the performance depends on correctly tuning the regularization parameters ($\lambda, \gamma$) and the relative ratio parameter ($\alpha$).
  • Future Applications: The authors aim to extend this work to specific downstream tasks like collaborative transfer learning and collaborative change-point detection, where the estimated ratios serve as the primary input.

Summary updated

Abstract

Assuming we have iid observations from two unknown probability density functions (pdfs), $p$ and $q$, the likelihood-ratio estimation (LRE) is an elegant approach to compare the two pdfs only by relying on the available data. In this paper, we introduce the first -to the best of our knowledge-graph-based extension of this problem, which reads as follows: Suppose each node $v$ of a fixed graph has access to observations coming from two unknown node-specific pdfs, $p_v$ and $q_v$, and the goal is to estimate for each node the likelihood-ratio between both pdfs by also taking into account the information provided by the graph structure. The node-level estimation tasks are supposed to exhibit similarities conveyed by the graph, which suggests that the nodes could collaborate to solve them more efficiently. We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF). We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks. These theoretical results explicit the situations where collaborative estimation effectively leads to an improvement in performance compared to solving each problem independently. Finally, in a series of experiments, we illustrate how GRULSIF infers the likelihood-ratios at the nodes of the graph more accurately compared to state-of-the art LRE methods, which would operate independently at each node, and we also verify that the behavior of GRULSIF is aligned with our previous theoretical analysis.
BibTeX
@misc{concha2022collaborative,
  author = {Alejandro de la Concha and Nicolas Vayatis and Argyris Kalogeratos},
  title = {{Collaborative likelihood-ratio estimation over graphs}},
  year = {2022},
  eprint = {2205.14461},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2205.14461},
}
Figure