OpenRaiser/Intern-Atlas huggingface dataset:
A Unifying Framework for Fairness-Aware Influence Maximization
Authors: Golnoosh Farnadi, Behrouz Babaki, Michel Gendreau
Venue: Conference WWW 2020
Year: 2020

The problem of selecting a subset of nodes with greatest influence in a graph, commonly known as influence maximization, has been well studied over the past decade. This problem has real world applications which can potentially affect lives of individuals. Algorithmic decision making in such domains raises concerns about their societal implications. One of these concerns, which surprisingly has only received limited attention so far, is algorithmic bias and fairness. We propose a flexible framework that extends and unifies the existing works in fairness-aware influence maximization. This framework is based on an integer programming formulation of the influence maximization problem. The fairness requirements are enforced by adding linear constraints or modifying the objective function. Contrary to the previous work which designs specific algorithms for each variant, we develop a formalism which is general enough for specifying different notions of fairness. A problem defined in this formalism can be then solved using efficient mixed integer programming solvers. The experimental evaluation indicates that our framework not only is general but also is competitive with existing algorithms.
Accurate Online Tensor Factorization for Temporal Tensor Streams with Missing Values
Authors: Dawon Ahn, Seyun Kim, U Kang
Venue: Conference CIKM 2021
Year: 2021

Given a time-evolving tensor stream with missing values, how can we accurately discover latent factors in an online manner to predict missing values? Online tensor factorization is a crucial task with many important applications including the analysis of climate, network traffic, and epidemic disease. However, existing online methods have disregarded temporal locality and thus have limited accuracy. In this paper, we propose STF (Streaming Tensor Factorization), an accurate online tensor factorization method for real-world temporal tensor streams with missing values. We exploit an attention-based temporal regularization to learn inherent temporal patterns of the streams. We also propose an efficient online learning algorithm which allows each row of the temporal factor matrix to be updated from past and future information. Extensive experiments show that the proposed method gives the state-of-the-art accuracy, and quickly processes each tensor slice.
Fast and Memory-Efficient Tucker Decomposition for Answering Diverse Time Range Queries
Authors: Jun-Gi Jang, U Kang
Venue: Conference KDD 2021
Year: 2021

Given a temporal dense tensor and an arbitrary time range, how can we efficiently obtain latent factors in the range? Tucker decomposition is a fundamental tool for analyzing dense tensors to discover hidden factors, and has been exploited in many data mining applications. However, existing decomposition methods do not provide the functionality to analyze a specific range of a temporal tensor. The existing methods are one-off, with the main focus on performing Tucker decomposition once for a whole input tensor. Although a few existing methods with a preprocessing phase can deal with a time range query, they are still time-consuming and suffer from low accuracy. In this paper, we propose Zoom-Tucker, a fast and memory-efficient Tucker decomposition method for finding hidden factors of temporal tensor data in an arbitrary time range. Zoom-Tucker fully exploits block structure to compress a given tensor, supporting an efficient query and capturing local information. Zoom-Tucker answers diverse time range queries quickly and memory-efficiently, by elaborately decoupling the preprocessed results included in the range and carefully determining the order of computations. We demonstrate that Zoom-Tucker is up to 171.9x faster and requires up to 230x less space than existing methods while providing comparable accuracy.
Debiased Balanced Interleaving at Amazon Search
Authors: Nan Bi, Pablo Castells, Daniel Gilbert, Slava Galperin, Patrick Tardif, Sachin Ahuja
Venue: Conference CIKM 2022
Year: 2022

Interleaving is an online evaluation technique that has shown to be orders of magnitude more sensitive than traditional A/B tests. It presents users with a single merged result of the compared rankings and then attributes user actions back to the evaluated rankers. Different interleaving methods in the literature have their advantages and limitations with respect to unbiasedness, sensitivity, preservation of user experience, and implementation and computation complexity. We propose a new interleaving method that utilizes a counterfactual evaluation framework for credit attribution while sticking to the simple ranking merge policy of balanced interleaving, and formally derive an unbiased estimator for comparing rankers with theoretical guarantees. We then confirm the effectiveness of our method with both synthetic and real experiments. We also discuss practical considerations of bringing different interleaving methods from the literature into a large-scale experiment, and show that our method achieves a favorable tradeoff in implementation and computation complexity while preserving statistical power and reliability. We have successfully implemented our method and produced consistent conclusions at the scale of billions of search queries. We report 10 online experiments that apply our method to e-commerce search, and observe a 60x sensitivity gain over A/B tests. We also find high correlations between our proposed estimator and corresponding A/B metrics, which helps interpret interleaving results in the magnitude of A/B measurements.
How to Measure Your App: A Couple of Pitfalls and Remedies in Measuring App Performance in Online Controlled Experiments
Authors: Yuxiang Xie, Meng Xu, Evan Chow, Xiaolin Shi
Venue: Conference WSDM 2021
Year: 2021

Effectively measuring, understanding, and improving mobile app performance is of paramount importance for mobile app developers. Across the mobile Internet landscape, companies run online controlled experiments (A/B tests) with thousands of performance metrics in order to understand how app performance causally impacts user retention and to guard against service or app regressions that degrade user experiences. To capture certain characteristics particular to performance metrics, such as enormous observation volume and high skewness in distribution, an industry-standard practice is to construct a performance metric as a quantile over all performance events in control or treatment buckets in A/B tests. In our experience with thousands of A/B tests provided by Snap, we have discovered some pitfalls in this industry-standard way of calculating performance metrics that can lead to unexplained movements in performance metrics and unexpected misalignment with user engagement metrics. In this paper, we discuss two major pitfalls in this industry-standard practice of measuring performance for mobile apps. One arises from strong heterogeneity in both mobile devices and user engagement, and the other arises from self-selection bias caused by post-treatment user engagement changes. To remedy these two pitfalls, we introduce several scalable methods including user-level performance metric calculation and imputation and matching for missing metric values. We have extensively evaluated these methods on both simulation data and real A/B tests, and have deployed them into Snap's in-house experimentation platform.
Masked-field Pre-training for User Intent Prediction
Authors: Peng Wang, Jiang Xu, Chunyi Liu, Hao Feng, Zang Li, Jieping Ye
Venue: Conference CIKM 2020
Year: 2020

For many applications, predicting the users' intents can help the system provide the solutions or recommendations to the users. It improves the user experience, and brings economic benefits. The main challenge of user intent prediction is that we lack enough labeled data for training, and some intents (labels) are sparse in the training set. This is a general problem for many real-world prediction tasks. To overcome data sparsity, we propose a masked-field pre-training framework. In pre-training, we exploit massive unlabeled data to learn useful feature interaction patterns. We do this by masking partial field features, and learning to predict them from other unmasked features. We then finetune the pre-trained model for the target intent prediction task. This framework can be used to train various deep models. In the intent prediction task, each intent is only relevant to partial features. To tackle this problem, we propose a Field-Independent Transformer network. This network generates separate representation for each field, and aggregates the relevant field representations with attention mechanism for each intent. We test our method on intent prediction datasets in customer service scenarios as well as several public datasets. The results show that the masked-field pre-training framework significantly improves the prediction precision for deep models. And the Field-Independent Transformer network trained with the masked-field pre-training framework outperforms the state-of-the-art methods in the user intent prediction.
Consistent Transformation of Ratio Metrics for Efficient Online Controlled Experiments
Authors: Roman Budylin, Alexey Drutsa, Ilya Katsev, Valeriya Tsoy
Venue: Conference WSDM 2018
Year: 2018

We study ratio overall evaluation criteria (user behavior quality metrics) and, in particular, average values of non-user level metrics, that are widely used in A/B testing as an important part of modern Internet companies» evaluation instruments (e.g., abandonment rate, a user»s absence time after a session).
From Missing Data to Boltzmann Distributions and Time Dynamics: The Statistical Physics of Recommendation
Authors: Ed H. Chi
Venue: Conference WSDM 2020
Year: 2020

The challenge of building a good recommendation system is deeply connected to missing data---unknown features and labels to suggest the most "valuable" items to the user. The mysterious properties of the power law distributions that generally arises out of recommender (and social systems in general) create skewed and long-tailed consumption patterns that are often still puzzling to many of us. Missing data and skewed distributions create not just accuracy and recall problems, but also capacity allocation problems, which are at the roots of recent debate on inclusiveness and responsibility. So how do we move forward in the face of these immense conceptual and practical issues? In our work, we have been asking ourselves ways to deriving insights from first principles and drawing inspiration from fields like statistical physics. Surprised, one might ask---what does the field of physics has to do with missing data in ranking and recommendations? As we all know, in the field of information systems, concepts like information entropy and probability have a rich intellectual history. This history is deeply connected to the greatest discoveries of science in the 19th century---statistical mechanics, thermodynamics, and specific concepts like thermal equilibrium. In this talk, I will take us on a journey connecting Boltzmann distribution and partition functions from statistical mechanics with importance weighting for learning better softmax functions, and then further to reinforcement learning, where we can plan better explorations using off-policy correction with policy gradient approaches. As I shall show, these techniques enable us to reason about missing data features, labels, and time dynamic patterns from our data.
Data-driven metric development for online controlled experiments: Seven lessons learned
Authors: Alex Deng, Xiaolin Shi
Venue: Conference KDD 2016
Year: 2016

Online controlled experiments, also called A/B testing, have been established as the mantra for data-driven decision making in many web-facing companies. In recent years, there are emerging research works focusing on building the platform and scaling it up, best practices and lessons learned to obtain trustworthy results, and experiment design techniques and various issues related to statistical inference and testing. However, despite playing a central role in online controlled experiments, there is little published work on treating metric development itself as a data-driven process. In this paper, we focus on the topic of how to develop meaningful and useful metrics for online services in their online experiments, and show how data-driven techniques and criteria can be applied in metric development process. In particular, we emphasize two fundamental qualities for the goal metrics (or Overall Evaluation Criteria) of any online service: directionality and sensitivity. We share lessons on why these two qualities are critical, how to measure these two qualities of metrics of interest, how to develop metrics with clear directionality and high sensitivity by using approaches based on user behavior models and data-driven calibration, and how to choose the right goal metrics for the entire online services.
Learning Sensitive Combinations of A/B Test Metrics
Authors: Eugene Kharitonov, Alexey Drutsa, Pavel Serdyukov
Venue: Conference WSDM 2017
Year: 2017

Online search evaluation, and A/B testing in particular, is an irreplaceable tool for modern search engines. Typically, online experiments last for several days or weeks and require a considerable portion of the search traffic. This restricts their usefulness and applicability.
A/B Testing Intuition Busters: Common Misunderstandings in Online Controlled Experiments
Authors: Ron Kohavi, Alex Deng, Lukas Vermeer
Venue: Conference KDD 2022
Year: 2022

A/B tests, or online controlled experiments, are heavily used in industry to evaluate implementations of ideas. While the statistics behind controlled experiments are well documented and some basic pitfalls known, we have observed some seemingly intuitive concepts being touted, including by A/B tool vendors and agencies, which are misleading, often badly so. Our goal is to describe these misunderstandings, the "intuition" behind them, and to explain and bust that intuition with solid statistical reasoning. We provide recommendations that experimentation platform designers can implement to make it harder for experimenters to make these intuitive mistakes.
Statistical significance testing in information retrieval: an empirical analysis of type I, type II and type III errors
Authors: Julián Urbano, Harlley Lima, Alan Hanjalic
Venue: Conference SIGIR 2019
Year: 2019

Statistical significance testing is widely accepted as a means to assess how well a difference in effectiveness reflects an actual difference between systems, as opposed to random noise because of the selection of topics. According to recent surveys on SIGIR, CIKM, ECIR and TOIS papers, the t-test is the most popular choice among IR researchers. However, previous work has suggested computer intensive tests like the bootstrap or the permutation test, based mainly on theoretical arguments. On empirical grounds, others have suggested non-parametric alternatives such as the Wilcoxon test. Indeed, the question of which tests we should use has accompanied IR and related fields for decades now. Previous theoretical studies on this matter were limited in that we know that test assumptions are not met in IR experiments, and empirical studies were limited in that we do not have the necessary control over the null hypotheses to compute actual Type I and Type II error rates under realistic conditions. Therefore, not only is it unclear which test to use, but also how much trust we should put in them. In contrast to past studies, in this paper we employ a recent simulation methodology from TREC data to go around these limitations. Our study comprises over 500 million p-values computed for a range of tests, systems, effectiveness measures, topic set sizes and effect sizes, and for both the 2-tail and 1-tail cases. Having such a large supply of IR evaluation data with full knowledge of the null hypotheses, we are finally in a position to evaluate how well statistical significance tests really behave with IR data, and make sound recommendations for practitioners.
Improving the Sensitivity of Online Controlled Experiments: Case Studies at Netflix
Authors: Huizhi Xie, Juliette Aurisset
Venue: Conference KDD 2016
Year: 2016

Controlled experiments are widely regarded as the most scientific way to establish a true causal relationship between product changes and their impact on business metrics. Many technology companies rely on such experiments as their main data-driven decision-making tool. The sensitivity of a controlled experiment refers to its ability to detect differences in business metrics due to product changes. At Netflix, with tens of millions of users, increasing the sensitivity of controlled experiments is critical as failure to detect a small effect, either positive or negative, can have a substantial revenue impact. This paper focuses on methods to increase sensitivity by reducing the sampling variance of business metrics. We define Netflix business metrics and share context around the critical need for improved sensitivity. We review popular variance reduction techniques that are broadly applicable to any type of controlled experiment and metric. We describe an innovative implementation of stratified sampling at Netflix where users are assigned to experiments in real time and discuss some surprising challenges with the implementation. We conduct case studies to compare these variance reduction techniques on a few Netflix datasets. Based on the empirical results, we recommend to use post-assignment variance reduction techniques such as post stratification and CUPED instead of at-assignment variance reduction techniques such as stratified sampling in large-scale controlled experiments.
DeepGroup: Group recommendation with implicit feedback
Authors: Sarina Sajadi Ghaemmaghami, Amirali Salehi-Abari
Venue: Conference CIKM 2021
Year: 2021

We focus on making recommendations for a new group of users whose preferences are unknown, but we are given the decisions of other groups. By formulating this problem as group recommendation from group implicit feedback, we focus on two of its practical instances: group decision prediction and reverse social choice. Given a set of groups and their observed decisions, group decision prediction intends to predict the decision of a new group of users, whereas reverse social choice aims to infer the preferences of those users involved in observed group decisions. These two problems are of interest to not only group recommendation, but also to personal privacy when the users intend to conceal their personal preferences but have participated in group decisions. To tackle these two problems, we propose and study DeepGroup---a deep learning approach for group recommendation with group implicit data. We empirically assess the predictive power of DeepGroup on various real-world datasets and group decision rules. Our extensive experiments not only demonstrate the efficacy of DeepGroup but also shed light on the privacy-leakage concerns of some decision-making processes.
FedPseudo: Privacy- Preserving Pseudo Value-Based Deep Learning Models for Federated Survival Analysis
Authors: Md. Mahmudur Rahman, Sanjay Purushotham
Venue: Conference KDD 2023
Year: 2023

Survival analysis, aka time-to-event analysis, has a wide-ranging impact on patient care. Federated Survival Analysis (FSA) is an emerging Federated Learning (FL) paradigm for performing survival analysis on distributed decentralized data available at multiple medical institutions. FSA enables individual medical institutions, referred to as clients, to improve their survival predictions while ensuring privacy. However, FSA faces challenges due to non-linear and non-IID data distributions among clients, as well as bias caused by censoring. Although recent studies have adapted Cox Proportional Hazards (CoxPH) survival models for FSA, a systematic exploration of these challenges is currently lacking. In this paper, we address these critical challenges by introducing FedPseudo, a pseudo value-based deep learning framework for FSA. FedPseudo uses deep learning models to learn robust representations from non-linear survival data, leverages the power of pseudo values to handle non-uniform censoring, and employs FL algorithms such as FedAvg to learn model parameters. We propose a novel and simple approach for estimating pseudo values for FSA. We provide theoretical proof that the estimated pseudo values, referred to as Federated Pseudo Values, are consistent. Moreover, our empirical results demonstrate that they can be computed faster than traditional methods of deriving pseudo values. To ensure and enhance the privacy of both the estimated pseudo values and the shared model parameters, we systematically investigate the application of differential privacy (DP) on both the federated pseudo values and local model updates. Furthermore, we adapt V -Usable Information metric to quantify the informativeness of a client's data for training a survival model and utilize this metric to show the advantages of participating in FSA. We conducted extensive experiments on synthetic and real-world survival datasets to demonstrate that our FedPseudo framework achieves better performance than other FSA approaches and performs similarly to the best centrally trained deep survival model. Moreover, FedPseudo consistently achieves superior results across different censoring settings.
Practice on Effectively Extracting NLP Features for Click-Through Rate Prediction
Authors: Hao Yang, Ziliang Wang, Weijie Bian, Yifan Zeng
Venue: Conference CIKM 2023
Year: 2023

Click-through rate (CTR) prediction is critical for industrial applications such as recommendation system and online advertising. Practically, there are a series of research proved that Natural Language Processing (NLP) features are helpful to improve CTR task performance. As these works show, there are different ways to extract NLP features. For example, keywords of item title are extracted as open-box feature by term frequency?inverse document frequency (tf-idf) method while item semantic embedding is extracted as black-box feature by shallow models (\emphe.g., word2vec) or deep learning models (e.g., BERT). However, these NLP models are pre-trained on NLP task, which is very different from the CTR task. Then it leads to the limited improvement of Area Under the ROC Curve (AUC) in CTR task. On the other hand, traditional NLP models for CTR task only consider open-box feature or black-box feature separately, which also leads to the discounted effect. Lastly, many NLP models are mainly used to extract semantic features only on item side. These methods take little account of user side information, or only IDs related features (\emphe.g., item's IDs) in user behavior sequence are introduced. In our work, we proposed a new network named BERT Attention method based on both Item and User information (BAIU). The target of BAIU is consistent with the CTR task, which is helpful to extract more effective NLP features. Also, both open-box and black-box features are simultaneously extracted by this network, which makes the model to learn more useful NLP features for CTR task and also makes the model more interpretable. Extensive experiments on both public data and our commercial data validate the effectiveness of our approach. Finally, the online experiment brings 2.2% gain of CTR on recommendation.