Exposing Query Identification for Search Transparency

Ruohan Li, Jianxiang Li, Bhaskar Mitra, Fernando Diaz, Asia J. Biega

TL;DR

This paper introduces "Exposing Query Identification" (EQI), a novel approach to search transparency that aims to identify which specific search queries lead to a particular document appearing in search results. By framing EQI as a retrieval task and developing a new evaluation metric (RELQ), the authors provide a computational method to understand and audit search bias, privacy, and optimization.

What Problem Does This Paper Address?

Search engines act as gatekeepers, controlling which content appears in front of users. While content creators care about if their content is seen, they often lack insight into which specific searches cause their content to surface. This "exposing query" problem is crucial for understanding and addressing issues like search bias (e.g., retrievability bias), user privacy (e.g., preventing sensitive content from being exposed by unintended queries), and even search engine optimization (SEO). Existing methods for identifying these queries are often computationally expensive or rely on outdated search logs. This paper tackles the challenge of efficiently and accurately identifying these exposing queries in a dynamic search environment.

Methods

The core innovation lies in reframing the problem: instead of searching for documents with queries, they search for queries that expose a given document. They explore this for two main types of search systems:

  • Embedding-based search systems (dual-encoders): They adapt metric learning techniques. The idea is to learn a new embedding space where a "nearest neighbor" search for a document will approximate finding queries that expose it in the original system. This involves training new encoders that transform the original query and document embeddings.
  • Traditional search systems (BM25): They adapt the BM25 model by reversing the roles of queries and documents. This involves indexing the query log and treating documents as queries to find matching exposing queries.

A key contribution is the Ranked Exposure List Quality (RELQ) metric. This metric is designed to evaluate the quality of a ranked list of exposing queries. It's unique because it jointly considers the behavior of two users: the user of the search system (who might be patient or impatient in browsing results) and the user of the EQI system (who wants to understand exposure).

Datasets

The primary dataset used for training and evaluation is MS MARCO passage retrieval benchmark. This dataset is well-known in the information retrieval community and contains a large number of passages and query-passage relevance judgments. The authors use this to simulate real-world search scenarios.

Key Insights and Ideas

  • Reversing the retrieval task is feasible: The paper demonstrates that treating "exposing query identification" as a retrieval problem, where you search for queries instead of documents, is a viable and effective approach.
  • Metric learning is key for neural systems: For modern embedding-based search systems, learning a new metric space that aligns with exposure is significantly better than simply using the original retrieval embeddings.
  • A dual-user metric is necessary: The RELQ metric highlights that evaluating exposing queries requires considering both how users interact with search results and how users interact with the EQI system itself.
  • Approximate EQI is computationally efficient: The proposed methods offer a way to identify exposing queries without the prohibitive cost of brute-force methods, making transparency more accessible.
  • Short queries are disproportionately exposed: The study found that shorter queries tend to be more likely to expose documents, which has implications for privacy analysis and regulatory compliance (like the right to be forgotten).

Key Results

  • Significant improvements with metric learning: For embedding-based systems (ANCE), their proposed metric learning approaches (ANCE-append and ANCE-residual) significantly outperformed a baseline ANCE-reverse approach, achieving RELQ scores up to 0.984 compared to 0.887. The ANCE-residual model showed the best performance.
  • BM25 performance: For traditional BM25 systems, a tuned BM25-reverse approach performed slightly better than a basic BM25-reverse, achieving RELQ scores up to 0.845.
  • Brute-force baseline: The brute-force method, by definition, achieved perfect scores (1.000) across all metrics, serving as an upper bound.
  • Training data efficiency: The models achieved good performance even with relatively small training datasets (e.g., 50K queries and 200K passages), suggesting that EQI can be trained efficiently.
  • Query collection expansion: Performance degrades slightly as the query collection expands without retraining, indicating the need for periodic model updates in dynamic environments.

Limitations and Future Work

  • Model retraining: The paper acknowledges that as query collections grow, models may need retraining to maintain optimal performance. Future work could explore adaptive retraining strategies.
  • Query characteristics: The observation that shorter queries are disproportionately exposed raises questions about downstream applications. Further analysis is needed to understand the implications of this bias.
  • Domain-specific studies: The authors suggest the need for domain-specific quantitative and qualitative user studies to further validate and refine EQI approaches.
  • Black-box systems and external signals: Exploring EQI for black-box search systems or incorporating external click signals for ranking are identified as promising future research directions.
  • Generative models for query collections: Developing generative models that create more realistic and downstream-task-grounded query collections is another avenue for future work.

Summary updated

Abstract

Search systems control the exposure of ranked content to searchers. In many cases, creators value not only the exposure of their content but, moreover, an understanding of the specific searches where the content is surfaced. The problem of identifying which queries expose a given piece of content in the ranking results is an important and relatively under-explored search transparency challenge. Exposing queries are useful for quantifying various issues of search bias, privacy, data protection, security, and search engine optimization. Exact identification of exposing queries in a given system is computationally expensive, especially in dynamic contexts such as web search. We explore the feasibility of approximate exposing query identification (EQI) as a retrieval task by reversing the role of queries and documents in two classes of search systems: dense dual-encoder models and traditional BM25 models. We then propose how this approach can be improved through metric learning over the retrieval embedding space. We further derive an evaluation metric to measure the quality of a ranking of exposing queries, as well as conducting an empirical analysis focusing on various practical aspects of approximate EQI. Overall, our work contributes a novel conception of transparency in search systems and computational means of achieving it.
BibTeX
@inproceedings{li2021exposing,
  author = {Ruohan Li and Jianxiang Li and Bhaskar Mitra and Fernando Diaz and Asia J. Biega},
  title = {{Exposing Query Identification for Search Transparency}},
  booktitle = {The Web Conference},
  year = {2021},
  doi = {10.1145/3485447.3512262},
}
Figure