# Collaborative likelihood-ratio estimation over graphs

arXiv: https://arxiv.org/abs/2205.14461 · HTML: https://mlsanity.com/paper/2205.14461/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 41 references that are in the map.
- First posted on arXiv 28 May 2022.

## Builds on (most cited first, 13 of 13)

- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [MMD Aggregated Two-Sample Test](https://mlsanity.com/paper/2110.15073/) (2021)
- [Multitask learning over graphs: An Approach for Distributed, Streaming Machine Learning](https://mlsanity.com/paper/2001.02112/) (2020)
- [Practical and Consistent Estimation of f-Divergences](https://mlsanity.com/paper/1905.11112/) (2019)
- [A Time-Vertex Signal Processing Framework](https://mlsanity.com/paper/1705.02307/) (2017)
- [Learning Kernel Tests Without Data Splitting](https://mlsanity.com/paper/2006.02286/) (2020)
- [Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning](https://mlsanity.com/paper/1602.05916/) (2016)
- [Learning over Multitask Graphs -- Part I: Stability Analysis](https://mlsanity.com/paper/1805.08535/) (2018)
- [Nonparametric Estimation of Renyi Divergence and Friends](https://mlsanity.com/paper/1402.2966/) (2014)
- [Multivariate f-Divergence Estimation With Confidence](https://mlsanity.com/paper/1411.2045/) (2014)
- [Learning over Multitask Graphs -- Part II: Performance Analysis](https://mlsanity.com/paper/1805.08547/) (2018)

## Built on by (most cited first, 1 of 1)

- [Online Centralized Non-parametric Change-point Detection via Graph-based Likelihood-ratio Estimation](https://mlsanity.com/paper/2301.03011/) (2023)

## Abstract (arXiv)

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, pv and qv, 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.