Krishnaram Kenthapadi's Publications

Last revised May, 2024. Please see arXiv and Google Scholar for my recent publications and LinkedIn for my recent talks.

Krishnaram's research interests are in the areas of Trustworthy Generative AI, Trustworthy Health AI, AI Observability, AI Safety, Fairness/Explainability/Privacy/Robustness in AI/ML Systems, Algorithms for Large Datasets and Graphs, Data Mining, Web Search, Information Retrieval, Search and Recommendation Systems, Social Network Analysis, and Computational Education.

Krishnaram Kenthapadi, Mehrnoosh Sameki, Ankur Taly, Grounding and Evaluation for Large Language Models: Practical Challenges and Lessons Learned, Tutorial at ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2024).

With the ongoing rapid adoption of Artificial Intelligence (AI) based systems in high-stakes domains such as financial services, healthcare and life sciences, hiring and human resources, education, societal infrastructure, and national security, ensuring the trustworthiness, safety, and observability of these systems has become a crucial necessity. Hence, it is essential to ensure that the AI systems are evaluated and monitored for not only accuracy and quality related metrics, but also for robustness against adversarial attacks, robustness under distribution shift, bias and discrimination against underrepresented groups, security and privacy protection, interpretability, and other responsible AI related dimensions. Our focus is on large language models (LLMs) and other generative AI models and applications, for which there are additional challenges such as hallucinations (and other ungrounded or low-quality outputs), harmful content (such as sexual, racist, and hateful responses), jailbreaks on safety and alignment mechanisms, prompt injection attacks, misinformation and disinformation, fake, misleading, and manipulative content, and copyright infringement.
In this tutorial, we first highlight key harms associated with generative AI systems with a focus on ungrounded answers (hallucinations), jailbreaks and prompt injection attacks, harmful content, and copyright infringement. Then, we discuss how to effectively address potential risks and challenges, following the framework of identification, measurement, mitigation (with four mitigation layers at model, safety system, application, and positioning), and operationalization. We present real-world LLM use cases, practical challenges, best practices, lessons learned from deploying solution approaches in industry, and key open problems. Our goal is to stimulate further research on grounding and evaluation of LLMs, and enable researchers and practitioners to build more robust and trustworthy LLM applications.
Krishnaram Kenthapadi, Himabindu Lakkaraju, Nazneen Rajani, Trustworthy Generative AI, Tutorials at International Conference on Machine Learning (ICML 2023), ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2023 [proposal]), and ACM Conference on Fairness, Accountability, and Transparency (FAccT 2023) [slides] [Video Recording].

Generative AI models and applications are being rapidly developed and deployed across a wide spectrum of industries and applications ranging from writing and email assistants to graphic design and art generation to educational assistants to coding to drug discovery. However, there are several ethical and social considerations associated with generative AI models and applications. These concerns include lack of interpretability, bias and discrimination, privacy, lack of model robustness, fake and misleading content, copyright implications, plagiarism, and environmental impact associated with training and inference of generative AI models.
In this tutorial, we first motivate the need for adopting responsible AI principles when developing and deploying large language models (LLMs) and other generative AI models, as part of a broader AI model governance and responsible AI framework, from societal, legal, user, and model developer perspectives, and provide a roadmap for thinking about responsible AI for generative AI in practice. We provide a brief technical overview of text and image generation models, and highlight the key responsible AI desiderata associated with these models. We then describe the technical considerations and challenges associated with realizing the above desiderata in practice. We focus on real-world generative AI use cases spanning domains such as media generation, writing assistants, copywriting, code generation, and conversational assistants, present practical solution approaches / guidelines for applying responsible AI techniques effectively, discuss lessons learned from deploying responsible AI approaches for generative AI applications in practice, and highlight the key open research problems. We hope that our tutorial will inform both researchers and practitioners, stimulate further research on responsible AI in the context of generative AI, and pave the way for building more reliable and trustworthy generative AI applications in the future.
Gyandev Gupta, Bashir Rastegarpanah, Amalendu Iyer, Joshua Rubin, Krishnaram Kenthapadi, Measuring Distributional Shifts in Text: The Advantage of Language Model-Based Embeddings, Preprint, 2023 [arxiv]

An essential part of monitoring machine learning models in production is measuring input and output data drift. In this paper, we present a system for measuring distributional shifts in natural language data and highlight and investigate the potential advantage of using large language models (LLMs) for this problem. Recent advancements in LLMs and their successful adoption in different domains indicate their effectiveness in capturing semantic relationships for solving various natural language processing problems. The power of LLMs comes largely from the encodings (embeddings) generated in the hidden layers of the corresponding neural network. First we propose a clustering-based algorithm for measuring distributional shifts in text data by exploiting such embeddings. Then we study the effectiveness of our approach when applied to text embeddings generated by both LLMs and classical embedding algorithms. Our experiments show that general-purpose LLM-based embeddings provide a high sensitivity to data drift compared to other embedding methods. We propose drift sensitivity as an important evaluation metric to consider when comparing language models. Finally, we present insights and lessons learned from deploying our framework as part of the Fiddler ML Monitoring platform over a period of 18 months.
Vijay Keswani, Elisa Celis, Krishnaram Kenthapadi, Matthew Lease, Designing Closed-Loop Models for Task Allocation, International Conference on Hybrid Human Artificial Intelligence (HHAI), 2023 [arxiv] [code] [slides]

Automatically assigning tasks to people is challenging because human performance can vary across tasks for many reasons. This challenge is further compounded in real-life settings in which no oracle exists to assess the quality of human decisions and task assignments made. Instead, we find ourselves in a "closed" decision-making loop in which the same fallible human decisions we rely on in practice must also be used to guide task allocation. How can imperfect and potentially biased human decisions train an accurate allocation model? Our key insight is to exploit weak prior information on human-task similarity to bootstrap model training. We show that the use of such a weak prior can improve task allocation accuracy, even when human decision-makers are fallible and biased. We present both theoretical analysis and empirical evaluation over synthetic data and a social media toxicity detection task. Results demonstrate the efficacy of our approach.
Michael Lohaus, Matthaeus Kleindessner, Krishnaram Kenthapadi, Francesco Locatello, Chris Russell, Are Two Heads the Same as One? Identifying Disparate Treatment in Fair Neural Networks , Advances in Neural Information Processing Systems (NeurIPS), 2022 [arxiv] [slides and video]

We show that deep networks trained to satisfy demographic parity often do so through a form of race or gender awareness, and that the more we force a network to be fair, the more accurately we can recover race or gender from the internal state of the network. Based on this observation, we investigate an alternative fairness approach: we add a second classification head to the network to explicitly predict the protected attribute (such as race or gender) alongside the original task. After training the two-headed network, we enforce demographic parity by merging the two heads, creating a network with the same architecture as the original network. We establish a close relationship between existing approaches and our approach by showing (1) that the decisions of a fair classifier are well-approximated by our approach, and (2) that an unfair and optimally accurate classifier can be recovered from a fair classifier and our second head predicting the protected attribute. We use our explicit formulation to argue that the existing fairness approaches, just as ours, demonstrate disparate treatment and that they are likely to be unlawful in a wide range of scenarios under US law.
Sanjiv Das, Michele Donini, Muhammad Bilal Zafar, John He, Krishnaram Kenthapadi, FinLex: An Effective Use of Word Embeddings for Financial Lexicon Generation, The Journal of Finance and Data Science, 2022. The Outstanding Paper in FinTech Award [Amazon Science]

We present a simple and effective methodology for the generation of lexicons (word lists) that may be used in natural language scoring applications. In particular, in the finance industry, word lists have become ubiquitous for sentiment scoring. These have been derived from dictionaries such as the Harvard Inquirer and require manual curation. Here, we present an automated approach to the curation of lexicons, which makes automatic preparation of any word list immediate. We show that our automated word lists deliver comparable performance to traditional lexicons on machine learning classification tasks. This new approach will enable finance academics and practitioners to create and deploy new word lists in addition to the few traditional ones in a facile manner.
David Munechika, Zijie J Wang, Jack Reidy, Josh Rubin, Krishna Gade, Krishnaram Kenthapadi, Duen Horng Chau, Visual Auditor: Interactive Visualization for Detection and Summarization of Model Biases, IEEE Visualization and Visual Analytics (VIS) Conference, 2022 [arxiv] [code] [live demo] [demo video]

As machine learning (ML) systems become increasingly widespread, it is necessary to audit these systems for biases prior to their de-ployment. Recent research has developed algorithms for effectively identifying intersectional bias in the form of interpretable, underper-forming subsets (or slices) of the data. However, these solutions and their insights are limited without a tool for visually understanding and interacting with the results of these algorithms. We propose Visual Auditor, an interactive visualization tool for auditing and summarizing model biases. Visual Auditor assists model validation by providing an interpretable overview of intersectional bias (bias that is present when examining populations defined by multiple features), details about relationships between problematic data slices, and a comparison between underperforming and overper-forming data slices in a model. Our open-source tool runs directly in both computational notebooks and web browsers, making model auditing accessible and easily integrated into current ML development workflows. An observational user study in collaboration with domain experts at Fiddler AI highlights that our tool can help ML practitioners identify and understand model biases.
Krishnaram Kenthapadi, Himabindu Lakkaraju, Pradeep Natarajan, Mehrnoosh Sameki, Model Monitoring in Practice, Tutorials at ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2022 [proposal]), ACM Conference on Fairness, Accountability, and Transparency (FAccT 2022), and The Web Conference (WWW 2023) [slides] [Video Recording].

Artificial Intelligence (AI) is increasingly playing an integral role in determining our day-to-day experiences. Increasingly, the applications of AI are no longer limited to search and recommendation systems, such as web search and movie and product recommendations, but AI is also being used in decisions and processes that are critical for individuals, businesses, and society. With AI based solutions in high-stakes domains such as hiring, lending, criminal justice, healthcare, and education, the resulting personal and professional implications of AI are far-reaching. Consequently, it becomes critical to ensure that these models are making accurate predictions, are robust to shifts in the data, are not relying on spurious features, and are not unduly discriminating against minority groups. To this end, several approaches spanning various areas such as explainability, fairness, and robustness have been proposed in recent literature, and many papers and tutorials on these topics have been presented in recent computer science conferences. However, there is relatively less attention on the need for monitoring machine learning (ML) models once they are deployed and the associated research challenges.
In this tutorial, we first motivate the need for ML model monitoring[14], as part of a broader AI model governance[9] and responsible AI framework, from societal, legal, customer/end-user, and model developer perspectives, and provide a roadmap for thinking about model monitoring in practice. We then present findings and insights on model monitoring desiderata based on interviews with various ML practitioners spanning domains such as financial services, healthcare, hiring, online retail, computational advertising, and conversational assistants[15]. We then describe the technical considerations and challenges associated with realizing the above desiderata in practice. We provide an overview of techniques/tools for model monitoring (e.g., see [1, 1, 2, 5, 6, 8, 10-13, 18-21]. Then, we focus on the real-world application of model monitoring methods and tools [3, 4, 7, 11, 13, 16, 17], present practical challenges/guidelines for using such techniques effectively, and lessons learned from deploying model monitoring tools for several web-scale AI/ML applications. We present case studies across different companies, spanning application domains such as financial services, healthcare, hiring, conversational assistants, online retail, computational advertising, search and recommendation systems, and fraud detection. We hope that our tutorial will inform both researchers and practitioners, stimulate further research on model monitoring, and pave the way for building more reliable ML models and monitoring tools in the future.
Yigitcan Kaya, Muhammad Bilal Zafar, Sergul Aydore, Nathalie Rauschmayr, Krishnaram Kenthapadi, Generating Distributional Adversarial Examples to Evade Statistical Detectors, International Conference on Machine Learning (ICML), 2022 [slides] [slides and video] [blog]

Deep neural networks (DNNs) are known to be highly vulnerable to adversarial examples (AEs) that include malicious perturbations. Assumptions about the statistical differences between natural and adversarial inputs are commonplace in many detection techniques. As a best practice, AE detectors are evaluated against ’adaptive’ attackers who actively perturb their inputs to avoid detection. Due to the difficulties in designing adaptive attacks, however, recent work suggests that most detectors have incomplete evaluation. We aim to fill this gap by designing a generic adaptive attack against detectors: the ’statistical indistinguishability attack’ (SIA). SIA optimizes a novel objective to craft adversarial examples (AEs) that follow the same distribution as the natural inputs with respect to DNN representations. Our objective targets all DNN layers simultaneously as we show that AEs being indistinguishable at one layer might fail to be so at other layers. SIA is formulated around evading distributional detectors that inspect a set of AEs as a whole and is also effective against four individual AE detectors, two dataset shift detectors, and an out-of-distribution sample detector, curated from published works. This suggests that SIA can be a reliable tool for evaluating the security of a range of detectors.
Ana Lucic, Sheeraz Ahmad, Amanda Furtado Brinhosa, Vera Liao, Himani Agrawal, Umang Bhatt, Krishnaram Kenthapadi, Alice Xiang, Maarten de Rijke, Nicholas Drabowski, Towards the Use of Saliency Maps for Explaining Low-Quality Electrocardiograms to End Users, ICML Workshop on Interpretable ML in Healthcare, 2022 [arxiv]

When using medical images for diagnosis, either by clinicians or artificial intelligence (AI) systems, it is important that the images are of high quality. When an image is of low quality, the medical exam that produced the image often needs to be redone. In telemedicine, a common problem is that the quality issue is only flagged once the patient has left the clinic, meaning they must return in order to have the exam redone. This can be especially difficult for people living in remote regions, who make up a substantial portion of the patients at Portal Telemedicina, a digital healthcare organization based in Brazil. In this paper, we report on ongoing work regarding (i) the development of an AI system for flagging and explaining low-quality medical images in real-time, (ii) an interview study to understand the explanation needs of stakeholders using the AI system at OurCompany, and, (iii) a longitudinal user study design to examine the effect of including explanations on the workflow of the technicians in our clinics. To the best of our knowledge, this would be the first longitudinal study on evaluating the effects of XAI methods on end-users -- stakeholders that use AI systems but do not have AI-specific expertise. We welcome feedback and suggestions on our experimental setup.
David Nigenda, Zohar Karnin, Muhammad Bilal Zafar, Raghu Ramesha, Alan Tan, Michele Donini, Krishnaram Kenthapadi, Amazon SageMaker Model Monitor: A System for Real-Time Insights into Deployed Machine Learning Models, ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2022 [arxiv]

With the increasing adoption of machine learning (ML) models and systems in high-stakes settings across different industries, guaranteeing a model's performance after deployment has become crucial. Monitoring models in production is a critical aspect of ensuring their continued performance and reliability. We present Amazon SageMaker Model Monitor, a fully managed service that continuously monitors the quality of machine learning models hosted on Amazon SageMaker. Our system automatically detects data, concept, bias, and feature attribution drift in models in real-time and provides alerts so that model owners can take corrective actions and thereby maintain high quality models. We describe the key requirements obtained from customers, system design and architecture, and methodology for detecting different types of drift. Further, we provide quantitative evaluations followed by use cases, insights, and lessons learned from more than two years of production deployment.
Nathalie Rauschmayr, Sami Kama, Muhyun Kim, Miyoung Choi, Krishnaram Kenthapadi, Profiling Deep Learning Workloads at Scale using Amazon SageMaker, ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2022 [Amazon Science]

With the rise of deep learning (DL), machine learning (ML) has become compute and data intensive, typically requiring multi-node multi-GPU clusters. As state-of-the-art models grow in size in the order of trillions of parameters, their computational complexity and cost also increase rapidly. Since 2012, the cost of deep learning doubled roughly every quarter, and this trend is likely to continue. ML practitioners have to cope with common challenges of efficient resource utilization when training such large models. In this paper, we propose a new profiling tool that cross-correlates relevant system utilization metrics and framework operations. The tool supports profiling DL models at scale, identifies performance bottlenecks, and provides insights with recommendations. We deployed the profiling functionality as an add-on to Amazon SageMaker Debugger, a fully-managed service that leverages an on-the-fly analysis system (called rules) to automatically identify complex issues in DL training jobs. By presenting deployment results and customer case studies, we show that it enables users to identify and fix issues caused by inefficient hardware resource usage, thereby reducing training time and cost.
Murtuza N Shergadwala, Himabindu Lakkaraju, Krishnaram Kenthapadi, A Human-Centric Perspective on Model Monitoring, AAAI Conference on Human Computation and Crowdsourcing (HCOMP), 2022 [arxiv]. Short versions appeared in ICML 2022 Workshop on Human-Machine Collaboration and Teaming and NeurIPS 2022 Workshop on Challenges in Deploying and Monitoring Machine Learning Systems [slides and video]

Predictive models are increasingly used to make various consequential decisions in high-stakes domains such as healthcare, finance, and policy. It becomes critical to ensure that these models make accurate predictions, are robust to shifts in the data, do not rely on spurious features, and do not unduly discriminate against minority groups. To this end, several approaches spanning various areas such as explainability, fairness, and robustness have been proposed in recent literature. Such approaches need to be human-centered as they cater to the understanding of the models to their users. However, there is little to no research on understanding the needs and challenges in monitoring deployed machine learning (ML) models from a human-centric perspective. To address this gap, we conducted semi-structured interviews with 13 practitioners who are experienced with deploying ML models and engaging with customers spanning domains such as financial services, healthcare, hiring, online retail, computational advertising, and conversational assistants. We identified various human-centric challenges and requirements for model monitoring in real-world applications. Specifically, we found that relevant stakeholders would want model monitoring systems to provide clear, unambiguous, and easy-to-understand insights that are readily actionable. Furthermore, our study also revealed that stakeholders desire customization of model monitoring systems to cater to domain-specific use cases.
Kate Donahue, Alexandra Chouldechova, Krishnaram Kenthapadi, Human-Algorithm Collaboration: Achieving Complementarity and Avoiding Unfairness, ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2022 [arxiv] [Research highlight in the Montreal AI Ethics Newsletter]. Short version appeared in NeurIPS 2021 Workshop on Human Centered AI [slides and video].

Much of machine learning research focuses on predictive accuracy: given a task, create a machine learning model (or algorithm) that maximizes accuracy. In many settings, however, the final prediction or decision of a system is under the control of a human, who uses an algorithm’s output along with their own personal expertise in order to produce a combined prediction. One ultimate goal of such collaborative systems is complementarity: that is, to produce lower loss (equivalently, greater payoff or utility) than either the human or algorithm alone. However, experimental results have shown that even in carefully-designed systems, complementary performance can be elusive. Our work provides three key contributions. First, we provide a theoretical framework for modeling simple human-algorithm systems and demonstrate that multiple prior analyses can be expressed within it. Next, we use this model to prove conditions where complementarity is impossible, and give constructive examples of where complementarity is achievable. Finally, we discuss the implications of our findings, especially with respect to the fairness of a classifier. In sum, these results deepen our understanding of key factors influencing the combined performance of human-algorithm systems, giving insight into how algorithmic tools can best be designed for collaborative environments.
Emily Diana, Wesley Gill, Michael J. Kearns, Krishnaram Kenthapadi, Aaron Roth, Saeed Sharifi-Malvajerdi, Multiaccurate Proxies for Downstream Fairness, ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2022 [arxiv]

We study the problem of training a model that must obey demographic fairness conditions when the sensitive features are not available at training time — in other words, how can we train a model to be fair by race when we don’t have data about race? We adopt a fairness pipeline perspective, in which an “upstream” learner that does have access to the sensitive features will learn a proxy model for these features from the other attributes. The goal of the proxy is to allow a general “downstream” learner — with minimal assumptions on their prediction task — to be able to use the proxy to train a model that is fair with respect to the true sensitive features. We show that obeying multiaccuracy constraints with respect to the downstream model class suffices for this purpose, provide sample- and oracle efficient-algorithms and generalization bounds for learning such proxies, and conduct an experimental evaluation. In general, multiaccuracy is much easier to satisfy than classification accuracy, and can be satisfied even when the sensitive features are hard to predict.
Matthaus Kleindessner, Samira Samadi, Muhammad Bilal Zafar, Krishnaram Kenthapadi, Chris Russell, Pairwise Fairness for Ordinal Regression, International Conference on Artificial Intelligence and Statistics (AISTATS), 2022 [arxiv] [code] [slides and video]

We initiate the study of fairness for ordinal regression. We adapt two fairness notions previously considered in fair ranking and propose a strategy for training a predictor that is approximately fair according to either notion. Our predictor has the form of a threshold model, composed of a scoring function and a set of thresholds, and our strategy is based on a reduction to fair binary classification for learning the scoring function and local search for choosing the thresholds. We provide generalization guarantees on the error and fairness violation of our predictor, and we illustrate the effectiveness of our approach in extensive experiments.
Deborah Sulem, Michele Donini, Muhammad Bilal Zafar, Francois-Xavier Aubet, Jan Gasthaus, Tim Januschowski, Sanjiv Das, Krishnaram Kenthapadi, Cedric Archambeau, Diverse Counterfactual Explanations for Anomaly Detection in Time Series, Preprint, 2022 [arxiv]

Data-driven methods that detect anomalies in times series data are ubiquitous in practice, but they are in general unable to provide helpful explanations for the predictions they make. In this work we propose a model-agnostic algorithm that generates counterfactual ensemble explanations for time series anomaly detection models. Our method generates a set of diverse counterfactual examples, i.e, multiple perturbed versions of the original time series that are not considered anomalous by the detection model. Since the magnitude of the perturbations is limited, these counterfactuals represent an ensemble of inputs similar to the original time series that the model would deem normal. Our algorithm is applicable to any differentiable anomaly detection model. We investigate the value of our method on univariate and multivariate real-world datasets and two deep-learning-based anomaly detection models, under several explainability criteria previously proposed in other data domains such as Validity, Plausibility, Closeness and Diversity. We show that our algorithm can produce ensembles of counterfactual examples that satisfy these criteria and thanks to a novel type of visualisation, can convey a richer interpretation of a model's internal mechanism than existing methods. Moreover, we design a sparse variant of our method to improve the interpretability of counterfactual explanations for high-dimensional time series anomalies. In this setting, our explanation is localised on only a few dimensions and can therefore be communicated more efficiently to the model's user.
Fan Wu, Linyi Li, Chejian Xu, Huan Zhang, Bhavya Kailkhura, Krishnaram Kenthapadi, Ding Zhao, Bo Li, COPA: Certifying Robust Policies for Offline Reinforcement Learning against Poisoning Attacks, International Conference on Learning Representations (ICLR), 2022 [arxiv] [Leaderboard] [code] [slides and video]

As reinforcement learning (RL) has achieved near human-level performance in a variety of tasks, its robustness has raised great attention. While a vast body of research has explored test-time (evasion) attacks in RL and corresponding defenses, its robustness against training-time (poisoning) attacks remains largely unanswered. In this work, we focus on certifying the robustness of offline RL in the presence of poisoning attacks, where a subset of training trajectories could be arbitrarily manipulated. We propose the first certification framework, COPA, to certify the number of poisoning trajectories that can be tolerated regarding different certification criteria. Given the complex structure of RL, we propose two certification criteria: per-state action stability and cumulative reward bound. To further improve the certification, we propose new partition and aggregation protocols to train robust policies. We further prove that some of the proposed certification methods are theoretically tight and some are NP-Complete problems. We leverage COPA to certify three RL environments trained with different algorithms and conclude: (1) The proposed robust aggregation protocols such as temporal aggregation can significantly improve the certifications; (2) Our certification for both per-state action stability and cumulative reward bound are efficient and tight; (3) The certification for different training algorithms and environments are different, implying their intrinsic robustness properties. All experimental results are available at https://copa-leaderboard.github.io.
Jing Liu, Chulin Xie, Krishnaram Kenthapadi, Sanmi Koyejo, Bo Li, RVFR: Robust Vertical Federated Learning via Feature Subspace Recovery, NeurIPS Workshop on New Frontiers in Federated Learning: Privacy, Fairness, Robustness, Personalization and Data Ownership, 2021

Vertical Federated Learning (VFL) is a distributed learning paradigm that allows multiple agents to jointly train a global model when each agent holds a different subset of features for the same sample(s). VFL is known to be vulnerable to backdoor attacks during training, and also vulnerable to test-time attacks. However, unlike the standard horizontal federated learning, improving the robustness of VFL remains challenging. To this end, we propose RVFR, a novel robust VFL training and inference framework. The key to our approach is to ensure that with a low-rank feature subspace, a small number of attacked samples, and other mild assumptions, RVFR recovers the underlying uncorrupted features with guarantees, thus sanitizes the model against a vast range of backdoor attacks. Further, RVFR also defends against inference-time adversarial feature attack. Our empirical studies further corroborate the robustness of the proposed framework.
Dylan Slack, Nathalie Rauschmayr, Krishnaram Kenthapadi, Defuse: Training More Robust Models through Creation and Correction of Novel Model Errors, NeurIPS Workshop on eXplainable AI approaches for debugging and diagnosis, 2021 [arxiv] [code] [slides and video] [Amazon Science article]

We typically compute aggregate statistics on held-out test data to assess the generalization of machine learning models. However, test data is only so comprehensive, and in practice, important cases are often missed. Thus, the performance of deployed machine learning models can be variable and untrustworthy. Motivated by these concerns, we develop methods to generate and correct novel model errors beyond those available in the data. We propose Defuse: a technique that trains a generative model on a classifier's training dataset and then uses the latent space to generate new samples which are no longer correctly predicted by the classifier. For instance, given a classifier trained on the MNIST dataset that correctly predicts a test image, Defuse then uses this image to generate new similar images by sampling from the latent space. Defuse then identifies the images that differ from the label of the original test input. Defuse enables efficient labeling of these new images, allowing users to re-train a more robust model, thus improving overall model performance. We evaluate the performance of Defuse on classifiers trained on real world datasets and find it reveals novel sources of model errors.
Michaela Hardt, Xiaoguang Chen, Xiaoyi Cheng, Michele Donini, Jason Gelman, Satish Gollaprolu, John He, Pedro Larroy, Xinyu Liu, Nick McCarthy, Ashish Rathi, Scott Rees, Ankit Siva, ErhYuan Tsai, Keerthan Vasist, Pinar Yilmaz, Bilal Zafar, Sanjiv Das, Kevin Haas, Tyler Hill, Krishnaram Kenthapadi, Amazon SageMaker Clarify: Machine Learning Bias Detection and Explainability in the Cloud, ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2021 [Product page: Amazon SageMaker Clarify] [Open Source Implementation] [slides] [Amazon AI Fairness and Explainability Whitepaper] [Amazon Blog Posts: Amazon SageMaker Clarify announcement; Amazon Science Article] [Press Coverage: TechCrunch; VentureBeat; Yahoo Finance; TechTarget; GeekWire; ZDNet; Business Wire; A Cloud Guru: SageMaker Clarify is the most important announcement of re:Invent 2020]

Understanding the predictions made by machine learning (ML) models and their potential biases remains a challenging and labor-intensive task that depends on the application, the dataset, and the specific model. We present Amazon SageMaker Clarify, an explainability feature for Amazon SageMaker that launched in December 2020, providing insights into data and ML models by identifying biases and explaining predictions. It is deeply integrated into Amazon SageMaker, a fully managed service that enables data scientists and developers to build, train, and deploy ML models at any scale. Clarify supports bias detection and feature importance computation across the ML lifecycle, during data preparation, model evaluation, and post-deployment monitoring. We outline the desiderata derived from customer input, the modular architecture, and the methodology for bias and explanation computations. Further, we describe the technical challenges encountered and the tradeoffs we had to make. For illustration, we discuss two customer use cases. We present our deployment results including qualitative customer feedback and a quantitative evaluation. Finally, we summarize lessons learned, and discuss best practices for the successful adoption of fairness and explanation tools in practice.
Valerio Perrone, Huibin Shen, Aida Zolic, Iaroslav Shcherbatyi, Amr Ahmed, Tanya Bansal, Michele Donini, Fela Winkelmolen, Rodolphe Jenatton, Jean Baptiste Faddoul, Barbara Pogorzelska, Miroslav Miladinovic, Krishnaram Kenthapadi, Matthias Seeger, Cedric Archambeau, Amazon SageMaker Automatic Model Tuning: Scalable Black-box Optimization, ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2021 [arxiv]

Tuning complex machine learning systems is challenging. Machine learning models typically expose a set of hyperparameters, be it regularization, architecture, or optimization parameters, whose careful tuning is critical to achieve good performance. To democratize access to such systems, it is essential to automate this tuning process. This paper presents Amazon SageMaker Automatic Model Tuning (AMT), a fully managed system for black-box optimization at scale. AMT finds the best version of a machine learning model by repeatedly training it with different hyperparameter configurations. It leverages either random search or Bayesian optimization to choose the hyperparameter values resulting in the best-performing model, as measured by the metric chosen by the user. AMT can be used with built-in algorithms, custom algorithms, and Amazon SageMaker pre-built containers for machine learning frameworks. We discuss the core functionality, system architecture and our design principles. We also describe some more advanced features provided by AMT, such as automated early stopping and warm-starting, demonstrating their benefits in experiments.
Sergul Aydore, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, Ankit Siva, Differentially Private Query Release Through Adaptive Projection, International Conference on Machine Learning (ICML), 2021 (Long Presentation) [arxiv] [code] [slides and video]. Short version in ICLR 2021 Workshop on Synthetic Data Generation: Quality, Privacy, Bias.

We propose, implement, and evaluate a new algorithm for releasing answers to very large numbers of statistical queries like k-way marginals, subject to differential privacy. Our algorithm makes adaptive use of a continuous relaxation of the Projection Mechanism, which answers queries on the private dataset using simple perturbation, and then attempts to find the synthetic dataset that most closely matches the noisy answers. We use a continuous relaxation of the synthetic dataset domain which makes the projection loss differentiable, and allows us to use efficient ML optimization techniques and tooling. Rather than answering all queries up front, we make judicious use of our privacy budget by iteratively and adaptively finding queries for which our (relaxed) synthetic data has high error, and then repeating the projection. We perform extensive experimental evaluations across a range of parameters and datasets, and find that our method outperforms existing algorithms in many cases, especially when the privacy budget is small or the query class is large.
Muhammad Bilal Zafar, Philipp Schmidt, Michele Donini, Cedric Archambeau, Felix Biessmann, Sanjiv Ranjan Das, Krishnaram Kenthapadi, More Than Words: Towards Better Quality Interpretations of Text Classifiers, Preprint, 2021 [arxiv]

The large size and complex decision mechanisms of state-of-the-art text classifiers make it difficult for humans to understand their predictions, leading to a potential lack of trust by the users. These issues have led to the adoption of methods like SHAP and Integrated Gradients to explain classification decisions by assigning importance scores to input tokens. However, prior work, using different randomization tests, has shown that interpretations generated by these methods may not be robust. For instance, models making the same predictions on the test set may still lead to different feature importance rankings. In order to address the lack of robustness of token-based interpretability, we explore explanations at higher semantic levels like sentences. We use computational metrics and human subject studies to compare the quality of sentence-based interpretations against token-based ones. Our experiments show that higher-level feature attributions offer several advantages: 1) they are more robust as measured by the randomization tests, 2) they lead to lower variability when using approximation-based methods like SHAP, and 3) they are more intelligible to humans in situations where the linguistic coherence resides at a higher granularity level. Based on these findings, we show that token-based interpretability, while being a convenient first choice given the input interfaces of the ML models, is not the most effective one in all situations.
Muhammad Bilal Zafar, Michele Donini, Dylan Slack, Cedric Archambeau, Sanjiv Ranjan Das, Krishnaram Kenthapadi, On the Lack of Robust Interpretability of Neural Text Classifiers, Findings at the Joint Conference of the Annual Meeting of the Association for Computational Linguistics and the International Joint Conference on Natural Language Processing (ACL-IJCNLP Findings), 2021 [arxiv]

With the ever-increasing complexity of neural language models, practitioners have turned to methods for understanding the predictions of these models. One of the most well-adopted approaches for model interpretability is feature-based interpretability, i.e., ranking the features in terms of their impact on model predictions. Several prior studies have focused on assessing the fidelity of feature-based interpretability methods, i.e., measuring the impact of dropping the top-ranked features on the model output. However, relatively little work has been conducted on quantifying the robustness of interpretations. In this work, we assess the robustness of interpretations of neural text classifiers, specifically, those based on pretrained Transformer encoders, using two randomization tests. The first compares the interpretations of two models that are identical except for their initializations. The second measures whether the interpretations differ between a model with trained parameters and a model with random parameters. Both tests show surprising deviations from expected behavior, raising questions about the extent of insights that practitioners may draw from interpretations.
Sergul Aydore, Haipeng Chen, Edward Choi, Jamie Hayes, Mario Fritz, Rachel Cummings, Krishnaram Kenthapadi, Organizers of the ICLR 2021 Workshop on Synthetic Data Generation: Quality, Privacy, Bias [Workshop Webpage] [Amazon Science Article].

Despite the substantial benefits from using synthetic data, the process of synthetic data generation is still an ongoing technical challenge. Although the two scenarios of limited data and privacy concerns share similar technical challenges such as quality and fairness, they are often studied separately. This workshop aims at the intersection of these challenges of synthetic data generation, and hopes to shine a light on the solutions that address these challenges. The 1st Synthetic Data Generation workshop will be a virtual workshop at ICLR 2021 (held on May 8, 2021). Our goal is to advance the general discussion of the topic by highlighting contributions proposing innovative approaches integrating quality, privacy and bias aspects of synthetic data generation.
Sanjiv Das, Michele Donini, Jason Gelman, Kevin Haas, Mila Hardt, Jared Katzman, Krishnaram Kenthapadi, Pedro Larroy, Pinar Yilmaz, Bilal Zafar, Fairness Measures for Machine Learning in Finance, The Journal of Financial Data Science, 2021 [PDF]

We present a machine learning pipeline for fairness-aware machine learning (FAML) in finance that encompasses metrics for fairness (and accuracy). Whereas accuracy metrics are well understood and the principal ones used frequently, there is no consensus as to which of several available measures for fairness should be used in a generic manner in the financial services industry. We explore these measures and discuss which ones to focus on, at various stages in the ML pipeline, pre-training and post-training, and we also examine simple bias mitigation approaches. Using a standard dataset we show that the sequencing in our FAML pipeline offers a cogent approach to arriving at a fair and accurate ML model. We discuss the intersection of bias metrics with legal considerations in the US, and the entanglement of explainability and fairness is exemplified in the case study. We discuss possible approaches for training ML models while satisfying constraints imposed from various fairness metrics, and the role of causality in assessing fairness.
Vijay Keswani, Matthew Lease, Krishnaram Kenthapadi, Designing Closed Human-in-the-loop Deferral Pipelines , Symposium on Biases in Human Computation and Crowdsourcing (BHCC), 2021 [arxiv]

In hybrid human-machine deferral frameworks, a classifier can defer uncertain cases to human decision-makers (who are often themselves fallible). Prior work on simultaneous training of such classifier and deferral models has typically assumed access to an oracle during training to obtain true class labels for training samples, but in practice there often is no such oracle. In contrast, we consider a "closed" decision-making pipeline in which the same fallible human decision-makers used in deferral also provide training labels. How can imperfect and biased human expert labels be used to train a fair and accurate deferral framework? Our key insight is that by exploiting weak prior information, we can match experts to input examples to ensure fairness and accuracy of the resulting deferral framework, even when imperfect and biased experts are used in place of ground truth labels. The efficacy of our approach is shown both by theoretical analysis and by evaluation on two tasks.
Vijay Keswani, Matthew Lease, Krishnaram Kenthapadi, Towards Unbiased and Accurate Deferral to Multiple Experts, AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society (AIES), 2021 (Oral Presentation) [arxiv] [code] [poster] [video]

Machine learning models are often implemented in cohort with humans in the pipeline, with the model having an option to defer to a domain expert in cases where it has low confidence in its inference. Our goal is to design mechanisms for ensuring accuracy and fairness in such prediction systems that combine machine learning model inferences and domain expert predictions. Prior work on "deferral systems" in classification settings has focused on the setting of a pipeline with a single expert and aimed to accommodate the inaccuracies and biases of this expert to simultaneously learn an inference model and a deferral system. Our work extends this framework to settings where multiple experts are available, with each expert having their own domain of expertise and biases. We propose a framework that simultaneously learns a classifier and a deferral system, with the deferral system choosing to defer to one or more human experts in cases of input where the classifier has low confidence. We test our framework on a synthetic dataset and a content moderation dataset with biased synthetic experts, and show that it significantly improves the accuracy and fairness of the final predictions, compared to the baselines. We also collect crowdsourced labels for the content moderation task to construct a real-world dataset for the evaluation of hybrid machine-human frameworks and show that our proposed learning framework outperforms baselines on this real-world dataset as well.
Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, Aaron Roth, Minimax Group Fairness: Algorithms and Experiments, AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society (AIES), 2021 (Oral Presentation) [arxiv] [code] [poster] [video]

We consider a recently introduced framework in which fairness is measured by worst-case outcomes across groups, rather than by the more standard differences between group outcomes. In this framework we provide provably convergent oracle-efficient learning algorithms (or equivalently, reductions to non-fair learning) for minimax group fairness. Here the goal is that of minimizing the maximum loss across all groups, rather than equalizing group losses. Our algorithms apply to both regression and classification settings and support both overall error and false positive or false negative rates as the fairness measure of interest. They also support relaxations of the fairness constraints, thus permitting study of the tradeoff between overall accuracy and minimax fairness. We compare the experimental behavior and performance of our algorithms across a variety of fairness-sensitive data sets and show empirical cases in which minimax fairness is strictly and strongly preferable to equal outcome notions.
Valerio Perrone, Michele Donini, Muhammad Bilal Zafar, Robin Schmucker, Krishnaram Kenthapadi, Cedric Archambeau, Fair Bayesian Optimization, AAAI/ACM Conference on Artificial Intelligence, Ethics, and Society (AIES), 2021 [arxiv] [slides/video] [poster] [Integration with AutoGluon: Fair Bayesian Optimization tutorial] [Amazon Science Article]. Earlier version received the Best Paper Award at the ICML 2020 Workshop on AutoML [Amazon Science Article].

Given the increasing importance of machine learning (ML) in our lives, several algorithmic fairness techniques have been proposed to mitigate biases in the outcomes of the ML models. However, most of these techniques are specialized to cater to a single family of ML models and a specific definition of fairness, limiting their adaptibility in practice. We introduce a general constrained Bayesian optimization (BO) framework to optimize the performance of any ML model while enforcing one or multiple fairness constraints. BO is a model-agnostic optimization method that has been successfully applied to automatically tune the hyperparameters of ML models. We apply BO with fairness constraints to a range of popular models, including random forests, gradient boosting, and neural networks, showing that we can obtain accurate and fair solutions by acting solely on the hyperparameters. We also show empirically that our approach is competitive with specialized techniques that enforce model-specific fairness constraints, and outperforms preprocessing methods that learn fair representations of the input data. Moreover, our method can be used in synergy with such specialized fairness techniques to tune their hyperparameters. Finally, we study the relationship between fairness and the hyperparameters selected by BO. We observe a correlation between regularization and unbiased models, explaining why acting on the hyperparameters leads to ML models that generalize well and are fair.
Nathalie Rauschmayr, Vikas Kumar, Rahul Huilgol, Andrea Olgiati, Satadal Bhattacharjee, Nihal Harish, Vandana Kannan, Amol Lele, Anirudh Acharya, Jared Nielsen, Lakshmi Ramakrishnan, Ishaaq Chandy, Ishan Bhatt, Zhihan Li, Kohen Chia, Neelesh Dodda, Jiacheng Gu, Miyoung Choi, Balajee Nagarajan, Jeffrey Geevarghes, Denis Davydenko, Sifei Li, Lu Huang, Edward Kim, Tyler Hill, Krishnaram Kenthapadi, Amazon SageMaker Debugger: A System for Real-time Insights into Machine Learning Model Training, The Conference on Machine Learning and Systems (MLSys), 2021 [MLSys 2021 Proceedings] [slides and video] [Amazon Science Article]

Manual debugging is a common productivity drain in the machine learning (ML) lifecycle. Identifying underperforming training jobs requires constant developer attention and deep domain expertise. As state-of-the-art models grow in size and complexity, debugging becomes increasingly difficult. Just as unit tests boost traditional software development, an automated ML debugging library can save time and money. We present Amazon SageMaker Debugger, a machine learning feature that automatically identifies and stops underperforming training jobs. Debugger is a new feature of Amazon SageMaker that automatically captures relevant data during training and evaluation and presents it for online and offline inspection. Debugger helps users define a set of conditions, in the form of built-in or custom rules, that are applied to this data, thereby enabling users to catch training issues as well as monitor and debug ML model training in real-time. These rules save time and money by alerting the developer and terminating a problematic training job early.
Zeinab S. Jalali, Krishnaram Kenthapadi and Sucheta Soundarajan, On Measuring the Diversity of Organizational Networks, International Conference on Complex Networks (CompleNet), 2021 [arxiv] [code]

The interaction patterns of employees in social and professional networks play an important role in the success of employees and organizations as a whole. However, in many fields there is a severe under-representation of minority groups; moreover, minority individuals may be segregated from the rest of the network or isolated from one another. While the problem of increasing the representation of minority groups in various fields has been well-studied, diversification in terms of numbers alone may not be sufficient: social relationships should also be considered. In this work, we consider the problem of assigning a set of employment candidates to positions in a social network so that diversity and overall fitness are maximized, and propose Fair Employee Assignment (FairEA), a novel algorithm for finding such a matching. The output from FairEA can be used as a benchmark by organizations wishing to evaluate their hiring and assignment practices. On real and synthetic networks, we demonstrate that FairEA does well at finding high-fitness, high-diversity matchings.
Krishnaram Kenthapadi, Invited panelist in the Roundtable on Trustworthy AI ("Principles of Trustworthy AI: Comparing Western and Non-Western conceptions of fairness and AI ethics") organized by the Indo-US Science & Technology Forum as part of the U.S.- India Artificial Intelligence (USIAI) Initiative, July 2021.

A principled approach to Trustworthy AI needs to revisit, and think beyond, standard outcome-based notions (e.g., demographic parity, equal opportunity) that are suited to fair classification and aligned with certain civil rights and labor laws in the US. Ethical behavior and trustworthiness are inherently human qualities whose definitions vary based on the underlying context. What is justice, in theory and practice, also varies based on the law of the land. Following the western notion of business, applications of trustworthy AI are often seen as exchange of goods and services with utilities for various stakeholders, supported by certain beliefs about labor, ownership, property, rights. This track will focus on understanding the above in different non-Western contexts, important challenges therein, and fundamental trade-offs between multiple desired properties in trustworthy AI.
Krishnaram Kenthapadi, Responsible AI in Industry: Practical Challenges and Lessons Learned, Invited talks at (1) Responsible Use of Data seminar series, The Academic Fringe Festival, Delft University of Technology [Talk Details], July 2021, (2) Flipkart Data Science Conference, June 2021, (3) Syracuse University, May 2021, (4) The University of Waterloo ML+Logic Colloquium [Video Recording], April 2021, (5) The University of British Columbia, Vancouver, March 2021 [slides]

How do we develop machine learning models and systems taking fairness, accuracy, explainability, and transparency into account? How do we protect the privacy of users when building large-scale AI based systems? Model fairness and explainability and protection of user privacy are considered prerequisites for building trust and adoption of AI systems in high stakes domains such as hiring, lending, and healthcare. We will first motivate the need for adopting a "fairness, explainability, and privacy by design" approach when developing AI/ML models and systems for different consumer and enterprise applications from the societal, regulatory, customer, end-user, and model developer perspectives. We will then focus on the application of responsible AI techniques in practice through industry case studies. We will discuss the sociotechnical dimensions and practical challenges, and conclude with the key takeaways and open challenges.
Krishnaram Kenthapadi, Nashlie Sephus, Responsible AI in Industry: Practical Challenges and Lessons Learned, Invited talk at the CVPR 2021 Workshop on Responsible Computer Vision [video] [slides].

How do we develop machine learning models and systems taking fairness, accuracy, explainability, and transparency into account? How do we protect the privacy of users when building large-scale AI based systems? Model fairness and explainability and protection of user privacy are considered prerequisites for building trust and adoption of AI systems in high stakes domains such as hiring, lending, and healthcare. We will first motivate the need for adopting a "fairness, explainability, and privacy by design" approach when developing AI/ML models and systems for different consumer and enterprise applications from the societal, regulatory, customer, end-user, and model developer perspectives. We will then focus on the application of responsible AI techniques in practice through industry case studies. We will discuss the sociotechnical dimensions and practical challenges, and conclude with the key takeaways and open challenges.
Krishnaram Kenthapadi, Ben Packer, Mehrnoosh Sameki, Nashlie Sephus, Responsible AI in Industry: Practical Challenges and Lessons Learned, Tutorials at ACM Conference on Fairness, Accountability, and Transparency (FAccT 2021 [Video Recording]), AAAI Conference on Artificial Intelligence (AAAI 2021 [Video Recording]), The Web Conference (WWW 2021) [slides], and International Conference on Machine Learning (ICML 2021 [slides] [Video Recording]).

Artificial Intelligence (AI) is increasingly playing an integral role in determining our day-to-day experiences. Increasingly, the applications of AI are no longer limited to search and recommendation systems, such as web search and movie and product recommendations, but AI is also being used in decisions and processes that are critical for individuals, businesses, and society. With web-based AI based solutions in areas such as hiring, lending, criminal justice, healthcare, and education, the resulting personal and professional implications of AI are far-reaching. With many factors playing a role in development and deployment of AI systems, they can exhibit different, and sometimes harmful, behaviors. For example, the training data often comes from society and real world, and thus it may reflect the society's biases and discrimination toward minorities and disadvantaged groups. For instance, minorities are known to face higher arrest rates for similar behaviors as the majority population, so building an AI system without compensating for this is likely to only exacerbate this prejudice. These concerns highlight the need for regulations, best practices, and practical tools to help data scientists and ML developers build AI systems that are secure, privacy-preserving, transparent, explainable, fair, and accountable --- to avoid unintended consequences and compliance challenges that can be harmful to individuals, businesses, and society.

In this tutorial, we will present an overview of responsible AI, highlighting model explainability, fairness, and privacy in AI, key regulations/laws, and techniques/tools for providing understanding around web-based AI/ML systems. Then, we will focus on the application of explainability, fairness assessment/unfairness mitigation, and privacy techniques in industry, wherein we present practical challenges/guidelines for using such techniques effectively and lessons learned from deploying models for several web-scale machine learning and data mining applications. We will present case studies across different companies, spanning application domains such as search and recommendation systems, hiring, sales, lending, and fraud detection. We will emphasize that topics related to responsible AI are socio-technical, that is, they are topics at the intersection of society and technology. The underlying challenges cannot be addressed by technologists alone; we need to work together with all key stakeholders --- such as customers of a technology, those impacted by a technology, and people with background in ethics and related disciplines --- and take their inputs into account while designing these systems. Finally, based on our experiences in industry, we will identify open problems and research directions for the data mining/machine learning community.
Krishnaram Kenthapadi, Privacy in AI/ML Systems: Practical Challenges and Lessons Learned, Invited talk at the EMNLP 2020 Workshop on Privacy in Natural Language Processing (PrivateNLP) [video] [slides].

How do we protect the privacy of users when building large-scale AI based systems? How do we develop machine learning models and systems taking fairness, accuracy, explainability, and transparency into account? Model fairness and explainability and protection of user privacy are considered prerequisites for building trust and adoption of AI systems in high stakes domains. We will first motivate the need for adopting a “fairness, explainability, and privacy by design” approach when developing AI/ML models and systems for different consumer and enterprise applications from the societal, regulatory, customer, end-user, and model developer perspectives. We will then focus on the application of privacy-preserving AI techniques in practice through industry case studies. We will discuss the sociotechnical dimensions and practical challenges, and conclude with the key takeaways and open challenges.
Krishnaram Kenthapadi, Fairness and Privacy in AI/ML Systems, Invited talk at LinkedIn - Microsoft Research - Indian Institute of Science Workshop on Fairness, Accountability, Transparency, and Ethics in Machine Learning 2020 [slides]

How do we protect privacy of users when building large-scale AI based systems? How do we develop machine learned models and systems taking fairness, accountability, and transparency into account? With the ongoing explosive growth of AI/ML models and systems, these are some of the ethical, legal, and technical challenges encountered by researchers and practitioners alike. In this talk, we will first motivate the need for adopting a "fairness and privacy by design" approach when developing AI/ML models and systems for different consumer and enterprise applications. We will then focus on the application of fairness-aware machine learning and privacy-preserving data mining techniques in practice, by presenting case studies spanning different LinkedIn applications (such as fairness-aware talent search ranking, privacy-preserving analytics, and LinkedIn Salary privacy & security design), and conclude with the key takeaways and open challenges.
Vidya Ravipati, Erika Pelaez Coyotl, Ujjwal Ratan, Krishnaram Kenthapadi, Fairness, Explainability, and Privacy in AI/ML Systems, NeurIPS 2020 Expo Talk [slides and video].

How do we develop machine learning models and systems taking fairness, accuracy, explainability, and transparency into account? How do we protect the privacy of users when building large-scale AI based systems? Model fairness and explainability and protection of user privacy are considered prerequisites for building trust and adoption of AI systems in high stakes domains such as lending and healthcare requiring reliability, safety, and fairness. We will first motivate the need for adopting a “fairness, explainability, and privacy by design” approach when developing AI/ML models and systems for different consumer and enterprise applications from the societal, regulatory, customer, end-user, and model developer perspectives. We will then focus on the application of fairness-aware ML, explainable AI, and privacy-preserving AI techniques in practice through industry case studies. We will discuss the sociotechnical dimensions and practical challenges, and conclude with the key takeaways and open challenges.
Krishnaram Kenthapadi, Fairness and Privacy in AI/ML Systems, Invited talk at @Scale 2019 [Video Recording] and Pinterest Distinguished Lecture, October 2019 [slides]

How do we protect privacy of users when building large-scale AI based systems? How do we develop machine learned models and systems taking fairness, accountability, and transparency into account? With the ongoing explosive growth of AI/ML models and systems, these are some of the ethical, legal, and technical challenges encountered by researchers and practitioners alike. In this talk, we will first motivate the need for adopting a "fairness and privacy by design" approach when developing AI/ML models and systems for different consumer and enterprise applications. We will then focus on the application of fairness-aware machine learning and privacy-preserving data mining techniques in practice, by presenting case studies spanning different LinkedIn applications (such as fairness-aware talent search ranking, privacy-preserving analytics, and LinkedIn Salary privacy & security design), and conclude with the key takeaways and open challenges.
Sriram Vasudevan, Krishnaram Kenthapadi, LiFT: A Scalable Framework for Measuring Fairness in ML Applications, ACM International Conference on Information and Knowledge Management (CIKM), 2020 [arxiv] [Open Source Toolkit: The LinkedIn Fairness Toolkit (LiFT)] [LinkedIn Engineering Blog Posts: LiFT announcement; Using LiFT in large-scale AI systems] [Press Coverage: Wall Street Journal; VentureBeat; Toolbox; Software Development (SD) Times; MarkTechPost]

Many internet applications are powered by machine learned models, which are usually trained on labeled datasets obtained through either implicit / explicit user feedback signals or human judgments. Since societal biases may be present in the generation of such datasets, it is possible for the trained models to be biased, thereby resulting in potential discrimination and harms for disadvantaged groups. Motivated by the need for understanding and addressing algorithmic bias in web-scale ML systems and the limitations of existing fairness toolkits, we present the LinkedIn Fairness Toolkit (LiFT), a framework for scalable computation of fairness metrics as part of large ML systems. We highlight the key requirements in deployed settings, and present the design of our fairness measurement system. We discuss the challenges encountered in incorporating fairness tools in practice and the lessons learned during deployment at LinkedIn. Finally, we provide open problems based on practical experience.
Cyrus DiCiccio, Sriram Vasudevan, Kinjal Basu, Krishnaram Kenthapadi, Deepak Agarwal, Evaluating Fairness Using Permutation Tests, ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2020 [arxiv] [code] [slides]

Machine learning models are central to people's lives and impact society in ways as fundamental as determining how people access information. The gravity of these models imparts a responsibility to model developers to ensure that they are treating users in a fair and equitable manner. Before deploying a model into production, it is crucial to examine the extent to which its predictions demonstrate biases. This paper deals with the detection of bias exhibited by a machine learning model through statistical hypothesis testing. We propose a permutation testing methodology that performs a hypothesis test that a model is fair across two groups with respect to any given metric. There are increasingly many notions of fairness that can speak to different aspects of model fairness. Our aim is to provide a flexible framework that empowers practitioners to identify significant biases in any metric they wish to study. We provide a formal testing mechanism as well as extensive experiments to show how this method works in practice.
G Roshan Lal, Sahin Cem Geyik, Krishnaram Kenthapadi, Fairness-Aware Online Personalization, FAccTRec Workshop on Responsible Recommendation at ACM Recommender Systems Conference (RecSys), 2020 [arxiv] [code]

Decision making in crucial applications such as lending, hiring, and college admissions has witnessed increasing use of algorithmic models and techniques as a result of a confluence of factors such as ubiquitous connectivity, ability to collect, aggregate, and process large amounts of fine-grained data using cloud computing, and ease of access to applying sophisticated machine learning models. Quite often, such applications are powered by search and recommendation systems, which in turn make use of personalized ranking algorithms. At the same time, there is increasing awareness about the ethical and legal challenges posed by the use of such data-driven systems. Researchers and practitioners from different disciplines have recently highlighted the potential for such systems to discriminate against certain population groups, due to biases in the datasets utilized for learning their underlying recommendation models. We present a study of fairness in online personalization settings involving the ranking of individuals. Starting from a fair warm-start machine-learned model, we first demonstrate that online personalization can cause the model to learn to act in an unfair manner if the user is biased in his/her responses. For this purpose, we construct a stylized model for generating training data with potentially biased features as well as potentially biased labels and quantify the extent of bias that is learned by the model when the user responds in a biased manner as in many real-world scenarios. We then formulate the problem of learning personalized models under fairness constraints and present a regularization based approach for mitigating biases in machine learning. We demonstrate the efficacy of our approach through extensive simulations with different parameter settings.
Kathy Baxter, Yoav Schlesinger, Sarah Aerni, Lewis Baker, Julie Dawson, Krishnaram Kenthapadi, Isabel Kloumann, Hanna Wallach, Bridging the gap from AI ethics research to practice, ACM Conference on Fairness, Accountability, and Transparency (FAccT) CRAFT Session, 2020

The study of fairness in machine learning applications has seen significant academic inquiry, research and publication in recent years. Concurrently, technology companies have begun to instantiate nascent program in AI ethics and product ethics more broadly. As a result of these efforts, AI ethics practitioners have piloted new processes to evaluate and ensure fairness in their machine learning applications. In this session, six industry practitioners, hailing from LinkedIn, Yoti, Microsoft, Pymetrics, Facebook, and Salesforce share insights from the work they have undertaken in the area of fairness, what has worked and what has not, lessons learned and best practices instituted as a result. Building on those insights, we discuss insights and brainstorm modalities through which to build upon the practitioners' work. Opportunities for further research or collaboration are identified, with the goal of developing a shared understanding of experiences and needs of AI ethics practitioners. Ultimately, the aim is to develop a playbook for more ethical and fair AI product development and deployment.
Krishnaram Kenthapadi, Stuart Ambler, Ahsan Chudhary, Mark Dietz, Sahin Cem Geyik, Krishnaram Kenthapadi, Ian Koeppe, Varun Mithal, Guillaume Saint-Jacques, Amir Sepehri, Thanh Tran, Sriram Vasudevan, Fairness, Privacy, and Transparency by Design in AI/ML Systems, LinkedIn Engineering Blog Post, July 2019
Sahin Cem Geyik, Stuart Ambler, Krishnaram Kenthapadi, Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search, ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2019 [arxiv]

We present a framework for quantifying and mitigating algorithmic bias in mechanisms designed for ranking individuals, typically used as part of web-scale search and recommendation systems. We first propose complementary measures to quantify bias with respect to protected attributes such as gender and age. We then present algorithms for computing fairness-aware re-ranking of results towards mitigating algorithmic bias. For a given search or recommendation task, our algorithms seek to achieve a desired distribution of top ranked results with respect to one or more protected attributes. We show that such a framework can be utilized to achieve fairness criteria such as equality of opportunity and demographic parity depending on the choice of the desired distribution. We evaluate the proposed algorithms via extensive simulations over different parameter choices, and study the effect of fairness-aware ranking on both bias and utility measures. We finally present the online A/B testing results from applying our framework towards representative ranking in LinkedIn Talent Search, and discuss the lessons learned in practice. Our approach resulted in tremendous improvement in the fairness metrics (nearly three fold increase in the number of search queries with representative results) without affecting the business metrics, which paved the way for deployment to 100% of LinkedIn Recruiter users worldwide. Ours is the first large-scale deployed framework for ensuring fairness in the hiring domain, with the potential positive impact for more than 630M LinkedIn members.
Krishna Gade, Sahin Cem Geyik, Krishnaram Kenthapadi, Varun Mithal, Ankur Taly, Explainable AI in Industry, Tutorials at ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2019 [slides] [proposal]), ACM Conference on Fairness, Accountability, and Transparency (FAccT 2020 [slides] [proposal] [Video Recording] ), AAAI Conference on Artificial Intelligence (Broader day-long tutorial from the following contributors: Freddy Lecue, Krishna Gade, Sahin Cem Geyik, Krishnaram Kenthapadi, Varun Mithal, Ankur Taly, Riccardo Guidotti, Pasquale Minervini; AAAI 2020 [slides]), The Web Conference (WWW 2020 [slides] [proposal]) [Video Recording] [Amazon Science Article]

Artificial Intelligence is increasingly playing an integral role in determining our day-to-day experiences. Moreover, with proliferation of AI based solutions in areas such as hiring, lending, criminal justice, healthcare, and education, the resulting personal and professional implications of AI are far-reaching. The dominant role played by AI models in these domains has led to a growing concern regarding potential bias in these models, and a demand for model transparency and interpretability. In addition, model explainability is a prerequisite for building trust and adoption of AI systems in high stakes domains requiring reliability and safety such as healthcare and automated transportation, and critical industrial applications with significant economic implications such as predictive maintenance, exploration of natural resources, and climate change modeling.

As a consequence, AI researchers and practitioners have focused their attention on explainable AI to help them better trust and understand models at scale. The challenges for the research community include (i) defining model explainability, (ii) formulating explainability tasks for understanding model behavior and developing solutions for these tasks, and finally (iii) designing measures for evaluating the performance of models in explainability tasks.

In this tutorial, we will present an overview of model interpretability and explainability in AI, key regulations / laws, and techniques / tools for providing explainability as part of AI/ML systems. Then, we will focus on the application of explainability techniques in industry, wherein we present practical challenges / guidelines for effectively using explainability techniques and lessons learned from deploying explainable models for several web-scale machine learning and data mining applications. We will present case studies across different companies, spanning application domains such as hiring, sales, lending, and fraud detection. Finally, based on our experiences in industry, we will identify open problems and research directions for the data mining / machine learning community.
Sarah Bird, Ben Hutchinson, Krishnaram Kenthapadi, Emre Kiciman, Margaret Mitchell, Fairness-Aware Machine Learning: Practical Challenges and Lessons Learned, Tutorials at ACM International Conference on Web Search and Data Mining (WSDM 2019 [slides] [proposal]), The Web Conference (WWW 2019 [slides] [proposal]), and ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2019 [slides] [proposal])

Researchers and practitioners from different disciplines have highlighted the ethical and legal challenges posed by the use of machine learned models and data-driven systems, and the potential for such systems to discriminate against certain population groups, due to biases in algorithmic decision-making systems. This tutorial aims to present an overview of algorithmic bias / discrimination issues observed over the last few years and the lessons learned, key regulations and laws, and evolution of techniques for achieving fairness in machine learning systems. The tutorial will then focus on the application of fairness-aware machine learning techniques in practice, by presenting case studies from different technology companies. Based on our experiences in industry, we will identify open problems and research challenges for the data mining / machine learning community.
Krishnaram Kenthapadi, Ilya Mironov, Abhradeep Guha Thakurta, Privacy-preserving Data Mining in Industry, Tutorials at ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD 2018 [slides]), ACM International Conference on Web Search and Data Mining (WSDM 2019 [slides] [proposal]), and The Web Conference (WWW 2019 [slides] [proposal])

Preserving privacy of users is a key requirement of web-scale data mining applications and systems such as web search, recommender systems, crowdsourced platforms, and analytics applications, and has witnessed a renewed focus in light of recent data breaches and new regulations such as GDPR. In this tutorial, we will first present an overview of privacy breaches over the last two decades and the lessons learned, key regulations and laws, and evolution of privacy techniques leading to differential privacy definition / techniques. Then, we will focus on the application of privacy-preserving data mining techniques in practice, by presenting case studies such as Apple's differential privacy deployment for iOS / macOS, Google's RAPPOR, LinkedIn Salary, and Microsoft's differential privacy deployment for collecting Windows telemetry. We will conclude with open problems and challenges for the data mining / machine learning community, based on our experiences in industry.
Alexey Romanov, Maria De-Arteaga, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexandra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, Anna Rumshisky, Adam Kalai, What's in a name? Reducing bias in bios without access to protected attributes, Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), 2019. Best Thematic Paper Award. [arxiv] [ACL] [Alexey's talk video] [blog]

There is a growing body of work that proposes methods for mitigating bias in machine learning systems. These methods typically rely on access to protected attributes such as race, gender, or age. However, this raises two significant challenges: (1) protected attributes may not be available or it may not be legal to use them, and (2) it is often desirable to simultaneously consider multiple protected attributes, as well as their intersections. In the context of mitigating bias in occupation classification, we propose a method for discouraging correlation between the predicted probability of an individual's true occupation and a word embedding of their name. This method leverages the societal biases that are encoded in word embeddings, eliminating the need for access to protected attributes. Crucially, it only requires access to individuals' names at training time and not at deployment time. We evaluate two variations of our proposed method using a large-scale dataset of online biographies. We find that both variations simultaneously reduce race and gender biases, with almost no reduction in the classifier's overall true positive rate.
Maria De-Arteaga, Alexey Romanov, Hanna Wallach, Jennifer Chayes, Christian Borgs, Alexandra Chouldechova, Sahin Geyik, Krishnaram Kenthapadi, Adam Kalai, Bias in Bios: A Case Study of Semantic Representation Bias in a High-Stakes Setting, ACM Conference on Fairness, Accountability, and Transparency (FAccT), 2019 [arxiv] [code] [Maria's talk video] [Maria's talk slides] [blog]

We present a large-scale study of gender bias in occupation classification, a task where the use of machine learning may lead to negative outcomes on peoples' lives. We analyze the potential allocation harms that can result from semantic representation bias. To do so, we study the impact on occupation classification of including explicit gender indicators -- such as first names and pronouns -- in different semantic representations of online biographies. Additionally, we quantify the bias that remains when these indicators are "scrubbed," and describe proxy behavior that occurs in the absence of explicit gender indicators. As we demonstrate, differences in true positive rates between genders are correlated with existing gender imbalances in occupations, which may compound these imbalances.
Krishnaram Kenthapadi, Fairness, Transparency, and Privacy in AI @ LinkedIn, Invited talk at QConSF 2018 [slides] [video][Related: Fairness, Privacy, and Transparency by Design in AI/ML Systems, LinkedIn Engineering Blog Post, July 2019]

How do we protect privacy of users in large-scale systems? How do we ensure fairness and transparency when developing machine learned models? With the ongoing explosive growth of AI/ML models and systems, these are some of the ethical and legal challenges encountered by researchers and practitioners alike. In this talk, we will first present an overview of privacy breaches as well as algorithmic bias / discrimination issues observed in the Internet industry over the last few years and the lessons learned, key regulations and laws, and evolution of techniques for achieving privacy and fairness in data-driven systems. We will motivate the need for adopting a "privacy and fairness by design" approach when developing data-driven AI/ML models and systems for different consumer and enterprise applications. We will also focus on the application of privacy-preserving data mining and fairness-aware machine learning techniques in practice, by presenting case studies spanning different LinkedIn applications, and conclude with the key takeaways and open challenges.
Sahin Geyik, Krishnaram Kenthapadi, Building Representative Talent Search at LinkedIn, LinkedIn Engineering Blog Post, October 2018 [Press Coverage: MIT Technology Review (June 2021); Business Insider; GeekWire; Tech Crunch; Fast Company; CNBC]
Krishnaram Kenthapadi, Thanh T. L. Tran, PriPeARL: A Framework for Privacy-Preserving Analytics and Reporting at LinkedIn, ACM International Conference on Information and Knowledge Management (CIKM), 2018 [arxiv] [slides] [LinkedIn Engineering Blog Post]

Preserving privacy of users is a key requirement of web-scale analytics and reporting applications, and has witnessed a renewed focus in light of recent data breaches and new regulations such as GDPR. We focus on the problem of computing robust, reliable analytics in a privacy-preserving manner, while satisfying product requirements. We present PriPeARL, a framework for privacy-preserving analytics and reporting, inspired by differential privacy. We describe the overall design and architecture, and the key modeling components, focusing on the unique challenges associated with privacy, coverage, utility, and consistency. We perform an experimental study in the context of ads analytics and reporting at LinkedIn, thereby demonstrating the tradeoffs between privacy and utility needs, and the applicability of privacy-preserving mechanisms to real-world data. We also highlight the lessons learned from the production deployment of our system at LinkedIn.
Rohan Ramanath, Hakan Inan, Gungor Polatkan, Bo Hu, Qi Guo, Cagri Ozcaglar, Xianren Wu, Krishnaram Kenthapadi, Sahin Cem Geyik, Towards Deep and Representation Learning for Talent Search at LinkedIn, ACM International Conference on Information and Knowledge Management (CIKM), 2018 [arxiv]

Talent search and recommendation systems at LinkedIn strive to match the potential candidates to the hiring needs of a recruiter or a hiring manager expressed in terms of a search query or a job posting. Recent work in this domain has mainly focused on linear models, which do not take complex relationships between features into account, as well as ensemble tree models, which introduce non-linearity but are still insufficient for exploring all the potential feature interactions, and strictly separate feature generation from modeling. In this paper, we present the results of our application of deep and representation learning models on LinkedIn Recruiter. Our key contributions include: (i) Learning semantic representations of sparse entities within the talent search domain, such as recruiter ids, candidate ids, and skill entity ids, for which we utilize neural network models that take advantage of LinkedIn Economic Graph, and (ii) Deep models for learning recruiter engagement and candidate response in talent search applications. We also explore learning to rank approaches applied to deep models, and show the benefits for the talent search use case. Finally, we present offline and online evaluation results for LinkedIn talent search and recommendation systems, and discuss potential challenges along the path to a fully deep model architecture. The challenges and approaches discussed generalize to any multi-faceted search engine.
Krishnaram Kenthapadi, Privacy-preserving Analytics and Data Mining at LinkedIn: Practical Challenges & Lessons Learned, Invited talks at the "Privacy in Graphs (PiG)" workshop, co-organized by Lise Getoor at UC Santa Cruz, November 2018 and the "Differential Privacy Deployed" workshop, co-organized by Cynthia Dwork at Harvard, September 2018

Preserving privacy of users is a key requirement of web-scale data mining, machine learning, and analytics applications, and has witnessed a renewed focus in light of recent data breaches and new regulations such as GDPR. In this talk, we will focus on the application of privacy-preserving data mining techniques in practice, by presenting two case studies at LinkedIn: differential privacy for LinkedIn analytics applications (https://arxiv.org/pdf/1809.07754), and LinkedIn Salary privacy design (https://arxiv.org/pdf/1705.06976), and reflect on the privacy challenges associated with applications enabled by the LinkedIn Economic Graph. The first part presents a framework to compute robust, privacy-preserving analytics, while the second part focuses on the privacy challenges/design for a large crowdsourced system (LinkedIn Salary). We will highlight the practical challenges/requirements, techniques, and lessons learned from deployment.
Stuart Ambler, Sahin Geyik, Krishnaram Kenthapadi, Fairness Aware Talent Search Ranking at LinkedIn, Microsoft's AI/ML conference (MLADS Spring 2018). Distinguished Contribution Award. [Video of LinkedIn CEO, Jeff Weiner referring to our work & this award.]

Recently, policymakers, regulators, and advocates have raised awareness about the ethical, policy, and legal challenges posed by machine learning and data driven systems. In particular, they have expressed concerns about the potentially discriminatory impact of such systems, for example, due to inadvertent encoding of bias into automated decisions. In the context of LinkedIn Talent Search, our goal is to understand whether there is bias in our machine learning models, and then devise techniques to ensure fairness/representation in the ranked results. This work presents the first large-scale framework for ensuring fairness/representation in the hiring domain, with the potential positive impact for more than 500M LinkedIn members.

We propose complementary measures to quantify bias with respect to attributes such as gender and age, and perform a study of these measures in the context of LinkedIn Talent Search application. We then describe our approach for computing a fairness-aware reranking of results. We present the results from extensive evaluation of the effect of fairness-aware ranking on both bias and utility measures over a large LinkedIn dataset on talent search. Finally, we discuss fairness notions for broad classes of web applications, alternate approaches, and extensions.
Xi Chen, Yiqun Liu, Liang Zhang, Krishnaram Kenthapadi, How LinkedIn Economic Graph Bonds Information and Product: Applications in LinkedIn Salary, ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), 2018 [arxiv] [LinkedIn Engineering Blog Post]

The LinkedIn Salary product was launched in late 2016 with the goal of providing insights on compensation distribution to job seekers, so that they can make more informed decisions when discovering and assessing career opportunities. The compensation insights are provided based on data collected from LinkedIn members and aggregated in a privacy-preserving manner. Given the simultaneous desire for computing robust, reliable insights and for having insights to satisfy as many job seekers as possible, a key challenge is to reliably infer the insights at the company level when there is limited or no data at all. We propose a two-step framework that utilizes a novel, semantic representation of companies (Company2vec) and a Bayesian statistical model to address this problem. Our approach makes use of the rich information present in the LinkedIn Economic Graph, and in particular, uses the intuition that two companies are likely to be similar if employees are very likely to transition from one company to the other and vice versa. We compute embeddings for companies by analyzing the LinkedIn members' company transition data using machine learning algorithms, then compute pairwise similarities between companies based on these embeddings, and finally incorporate company similarities in the form of peer company groups as part of the proposed Bayesian statistical model to predict insights at the company level. We perform extensive validation using several different evaluation techniques, and show that we can significantly increase the coverage of insights while, in fact, even improving the quality of the obtained insights. For example, we were able to compute salary insights for 35 times as many title-region-company combinations in the U.S. as compared to previous work, corresponding to 4.9 times as many monthly active users. Finally, we highlight the lessons learned from deployment of our system.
Sahin Cem Geyik, Qi Guo, Bo Hu, Cagri Ozcaglar, Ketan Thakkar, Xianren Wu, Krishnaram Kenthapadi, Talent Search and Recommendation Systems at LinkedIn: Practical Challenges and Lessons Learned, International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR), 2018 [arxiv] [slides] [LinkedIn Engineering Blog Post]

LinkedIn Talent Solutions business contributes to around 65% of LinkedIn's annual revenue, and provides tools for job providers to reach out to potential candidates and for job seekers to find suitable career opportunities. LinkedIn's job ecosystem has been designed as a platform to connect job providers and job seekers, and to serve as a marketplace for efficient matching between potential candidates and job openings. A key mechanism to help achieve these goals is the LinkedIn Recruiter product, which enables recruiters to search for relevant candidates and obtain candidate recommendations for their job postings. In this work, we highlight a set of unique information retrieval, system, and modeling challenges associated with talent search and recommendation systems.
Krishnaram Kenthapadi, Stuart Ambler, Liang Zhang, Deepak Agarwal, Bringing Salary Transparency to the World: Computing Robust Compensation Insights via LinkedIn Salary, ACM on Conference on Information and Knowledge Management (CIKM), 2017. Best Case Studies Paper Award. [arxiv] [slides] [LinkedIn Engineering Blog Post]

The recently launched LinkedIn Salary product has been designed with the goal of providing compensation insights to the world's professionals and thereby helping them optimize their earning potential. We describe the overall design and architecture of the statistical modeling system underlying this product. We focus on the unique data mining challenges while designing and implementing the system, and describe the modeling components such as Bayesian hierarchical smoothing that help to compute and present robust compensation insights to users. We report on extensive evaluation with nearly one year of de-identified compensation data collected from over one million LinkedIn users, thereby demonstrating the efficacy of the statistical models. We also highlight the lessons learned through the deployment of our system at LinkedIn.
Krishnaram Kenthapadi, Ahsan Chudhary, Stuart Ambler, LinkedIn Salary: A System for Secure Collection and Presentation of Structured Compensation Insights to Job Seekers, IEEE Symposium on Privacy-Aware Computing (PAC), 2017 [arxiv] [slides] [LinkedIn Engineering Blog Post]

Online professional social networks such as LinkedIn have enhanced the ability of job seekers to discover and assess career opportunities, and the ability of job providers to discover and assess potential candidates. For most job seekers, salary (or broadly compensation) is a crucial consideration in choosing a new job. At the same time, job seekers face challenges in learning the compensation associated with different jobs, given the sensitive nature of compensation data and the dearth of reliable sources containing compensation data. Towards the goal of helping the world's professionals optimize their earning potential through salary transparency, we present LinkedIn Salary, a system for collecting compensation information from LinkedIn members and providing compensation insights to job seekers. We present the overall design and architecture, and describe the key components needed for the secure collection, de-identification, and processing of compensation data, focusing on the unique challenges associated with privacy and security. We perform an experimental study with more than one year of compensation submission history data collected from over 1.5 million LinkedIn members, thereby demonstrating the tradeoffs between privacy and modeling needs. We also highlight the lessons learned from the production deployment of this system at LinkedIn.
Krishnaram Kenthapadi, Benjamin Le, Ganesh Venkataraman, Personalized Job Recommendation System at LinkedIn: Practical Challenges and Lessons Learned, ACM Conference on Recommender Systems (RecSys), 2017 [PDF] [slides]

Online professional social networks such as LinkedIn play a key role in helping job seekers find right career opportunities and job providers reach out to potential candidates. LinkedIn's job ecosystem has been designed to serve as a marketplace for efficient matching between potential candidates and job postings, and to provide tools to connect job seekers and job providers. LinkedIn's job recommendations product is a crucial mechanism to help achieve these goals, wherein personalized sets of recommended job postings are presented for members based on the structured, context data present in their profiles. We present how we formulated and addressed the unique information retrieval, system, and modeling challenges associated with personalized job recommendation, the overall system design and architecture, the challenges encountered in practice, and the lessons learned from the production deployment at LinkedIn.
Dhruv Arya, Ganesh Venkataraman, Aman Grover, Krishnaram Kenthapadi, Candidate Selection for Large Scale Personalized Search and Recommender Systems, Tutorial at International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), 2017 [PDF] [slides] [Github code assignments]

Modern day social media search and recommender systems require complex query formulation that incorporates both user context and their explicit search queries. Users expect these systems to be fast and provide relevant results to their query and context. With millions of documents to choose from, these systems utilize a multi-pass scoring function to narrow the results and provide the most relevant ones to users. Candidate selection is required to sift through all the documents in the index and select a relevant few to be ranked by subsequent scoring functions. It becomes crucial to narrow down the document set while maintaining relevant ones in resulting set. In this tutorial we survey various candidate selection techniques and deep dive into case studies on a large scale social media platform. In the later half we provide hands-on tutorial where we explore building these candidate selection models on a real world dataset and see how to balance the tradeoff between relevance and latency.
Fedor Borisyuk, Liang Zhang, Krishnaram Kenthapadi, LiJAR: A System for Job Application Redistribution towards Efficient Career Marketplace, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2017 [PDF]

Online professional social networks such as LinkedIn serve as a marketplace, wherein job seekers can find right career opportunities and job providers can reach out to potential candidates. LinkedIn's job recommendations product is a key vehicle for efficient matching between potential candidates and job postings. However, we have observed in practice that a subset of job postings receive too many applications (due to several reasons such as the popularity of the company, nature of the job, etc.), while some other job postings receive too few applications. Both cases can result in job poster dissatisfaction and may lead to discontinuation of the associated job posting contracts. At the same time, if too many job seekers compete for the same job posting, each job seeker's chance of getting this job will be reduced. In the long term, this reduces the chance of users finding jobs that they really like on the site. Therefore, it becomes beneficial for the job recommendation system to consider values provided to both job seekers as well as job posters in the marketplace.

In this paper, we propose the job application redistribution problem, with the goal of ensuring that job postings do not receive too many or too few applications, while still providing job recommendations to users with the same level of relevance. We present a dynamic forecasting model to estimate the expected number of applications at the job expiration date, and algorithms to either promote or penalize jobs based on the output of the forecasting model. We also describe the system design and architecture for LiJAR, LinkedIn's Job Applications Forecasting and Redistribution system, which we have implemented and deployed in production. We perform extensive evaluation of LiJAR through both offline and online A/B testing experiments. Our production deployment of this system as part of LinkedIn's job recommendation engine has resulted in significant increase in the engagement of users for underserved jobs (6.5%) without affecting the user engagement in terms of the total number of job applications, thereby addressing the needs of job seekers as well as job providers simultaneously.
Jian Wang, Krishnaram Kenthapadi, Kaushik Rangadurai, David Hardtke, Dionysius: A Framework for Modeling Hierarchical User Interactions in Recommender Systems, LinkedIn Technical Report, 2017

We address the following problem: How do we incorporate user item interaction signals as part of the relevance model in a large-scale personalized recommendation system such that, (1) the ability to interpret the model and explain recommendations is retained, and (2) the existing infrastructure designed for the (user profile) content-based model can be leveraged? We propose Dionysius, a hierarchical graphical model based framework and system for incorporating user interactions into recommender systems, with minimal change to the underlying infrastructure. We learn a hidden fields vector for each user by considering the hierarchy of interaction signals, and replace the user profile-based vector with this learned vector, thereby not expanding the feature space at all. Thus, our framework allows the use of existing recommendation infrastructure that supports content based features. We implemented and deployed this system as part of the recommendation platform at LinkedIn for more than one year. We validated the efficacy of our approach through extensive offline experiments with different model choices, as well as online A/B testing experiments. Our deployment of this system as part of the job recommendation engine resulted in significant improvement in the quality of retrieved results, thereby generating improved user experience and positive impact for millions of users.
Fedor Borisyuk, Krishnaram Kenthapadi, David Stein, Bo Zhao, CaSMoS: A Framework for Learning Candidate Selection Models over Structured Queries and Documents, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016 [PDF]

User experience at social media and web platforms such as LinkedIn is heavily dependent on the performance and scalability of its products. Applications such as personalized search and recommendations require real-time scoring of millions of structured candidate documents associated with each query, with strict latency constraints. In such applications, the query incorporates the context of the user (in addition to search keywords if present), and hence can become very large, comprising of thousands of Boolean clauses over hundreds of document attributes. Consequently, candidate selection techniques need to be applied since it is infeasible to retrieve and score all matching documents from the underlying inverted index. We propose CaSMoS, a machine learned candidate selection framework that makes use of Weighted AND (WAND) query. Our framework is designed to prune irrelevant documents and retrieve documents that are likely to be part of the top-k results for the query. We apply a constrained feature selection algorithm to learn positive weights for feature combinations that are used as part of the weighted candidate selection query. We have implemented and deployed this system to be executed in real time using LinkedIn's Galene search platform. We perform extensive evaluation with different training data approaches and parameter settings, and investigate the scalability of the proposed candidate selection model. Our deployment of this system as part of LinkedIn's job recommendation engine has resulted in significant reduction in latency (up to 25%) without sacrificing the quality of the retrieved results, thereby paving the way for more sophisticated scoring models.

Document Understanding and Augmentation with Multimedia Content / Computational Education:

Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Similarity Search using Concept Graphs, ACM International Conference on Information and Knowledge Management (CIKM), 2014 [PDF]

The rapid proliferation of hand-held devices has led to the development of rich, interactive and immersive applications, such as e-readers for electronic books. These applications motivate retrieval systems that can implicitly satisfy any information need of the reader by exploiting the context of the user's interactions. Such retrieval systems differ from traditional search engines in that the queries constructed using the context are typically complex objects (including the document and its structure).

In this paper, we develop an efficient retrieval system, only assuming an oracle access to a traditional search engine that admits 'succinct' keyword queries for retrieving objects of a desired media type. As part of query generation, we first map the complex query object to a concept graph and then use the concepts along with their relationships in the graph to compute a small set of keyword queries to the search engine. Next, as part of the result generation, we aggregate the results of these queries to identify relevant web content of the desired type, thereby eliminating the need for explicitly computing similarity between the query object and all web content. We present a theoretical analysis of our approach and carry out a detailed empirical evaluation to show the practicality of the approach for the task of augmenting electronic documents with high quality videos from the web.
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Study Navigator: An Algorithmically Generated Aid for Learning from Electronic Textbooks, Journal of Educational Data Mining, vol. 6 (1), International Educational Data Mining Society, 2014.

We present study navigator, an algorithmically-generated aid for enhancing the experience of studying from electronic textbooks. The study navigator for a section of the book consists of helpful concept references for understanding this section. Each concept reference is a pair consisting of a concept phrase explained elsewhere and the link to the section in which it has been explained. We propose a novel reader model for textbooks and an algorithm for generating the study navigator based on this model. We also present an extension of the study navigator specialized to accommodate the information processing preference of the student. Specifically, this specialization allows a student to control the balance between references to sections that help refresh material already studied vs. sections that provide more advanced information. We also present two user studies that demonstrate the efficacy of the proposed system across textbooks on different subjects from different grades.
Marios Kokkodis, Anitha Kannan, and Krishnaram Kenthapadi, Assigning Educational Videos at Appropriate Locations in Textbooks, International Conference on Educational Data Mining (EDM), 2014 [Extended version]

The emergence of tablet devices, cloud computing, and abundant online multimedia content presents new opportunities to transform traditional paper-based textbooks into tablet-based electronic textbooks. Towards this goal, techniques have been proposed to automatically augment textbook sections with relevant web content such as online educational videos. However, a highly relevant video can be created at a granularity that may not mimic the organization of the textbook. We focus on the video assignment problem: Given a candidate set of relevant educational videos for augmenting an electronic textbook, how do we assign the videos at appropriate locations in the textbook? We propose a rigorous formulation of the video assignment problem and present an algorithm for assigning each video to the optimum subset of logical units. Our experimental evaluation using a diverse collection of educational videos relevant to multiple chapters in a textbook demonstrates the efficacy of the proposed techniques for inferring the granularity at which a relevant video should be assigned.
Rakesh Agrawal, Maria Christoforaki, Sreenivas Gollapudi, Anitha Kannan, Krishnaram Kenthapadi, and Adith Swaminathan, Mining Videos from the Web for Electronic Textbooks, International Conference on Formal Concept Analysis (ICFCA), 2014 [Extended version]

We propose a system for mining videos from the web for supplementing the content of electronic textbooks in order to enhance their utility. Textbooks are generally organized into sections such that each section explains very few concepts and every concept is primarily explained in one section. Building upon these principles from the education literature and drawing upon the theory of Formal Concept Analysis, we define the focus of a section in terms of a few indicia, which themselves are combinations of concept phrases uniquely present in the section. We identify videos relevant for a section by ensuring that at least one of the indicia for the section is present in the video and measuring the extent to which the video contains the concept phrases occurring in different indicia for the section. Our user study employing two corpora of textbooks on different subjects from two countries demonstrate that our system is able to find useful videos, relevant to individual sections.
Rakesh Agrawal, M. Hanif Jhaveri, and Krishnaram Kenthapadi, Evaluating Educational Interventions at Scale, ACM Conference on Learning at Scale (L@S), 2014 [PDF]

Education and learning are currently undergoing transformative changes due to the emergence of tablet devices, cloud computing, and abundant online content. These trends present opportunities to transform traditional paper-based textbooks into tablet-based electronic textbooks, and to further enrich the educational experience by augmenting them with relevant supplementary materials. A natural question is whether this educational intervention, namely, enriching textbooks with relevant web articles, images and videos, is effective. It turns out that designing an experiment at scale for this purpose is nontrivial. We report on progress in designing and carrying out such an experiment.
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Studying from Electronic Textbooks, ACM International Conference on Information and Knowledge Management (CIKM), 2013 [PDF]

We present study navigator, an algorithmically-generated aid for enhancing the experience of studying from electronic textbooks. The study navigator for a section of the book consists of helpful concept references for understanding this section. Each concept reference is a pair consisting of a concept phrase explained elsewhere and the link to the section in which it has been explained. We propose a novel reader model for textbooks and an algorithm for generating the study navigator based on this model. We also present the results of an extensive user study that demonstrates the efficacy of the proposed system across textbooks on different subjects from different grades.
Rakesh Agrawal, Sunandan Chakraborty, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Empowering Authors to Diagnose Comprehension Burden in Textbooks, ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2012 [PDF]

Good textbooks are organized in a systematically progressive fashion so that students acquire new knowledge and learn new concepts based on known items of information. We provide a diagnostic tool for quantitatively assessing the comprehension burden that a textbook imposes on the reader due to non-sequential presentation of concepts. We present a formal definition of comprehension burden and propose an algorithmic approach for computing it. We apply the tool to a corpus of high school textbooks from India and empirically examine its effectiveness in helping authors identify sections of textbooks that can benefit from reorganizing the material presented.
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Electronic Textbooks and Data Mining (invited paper), International Conference on Web-Age Information Management (WAIM), LNCS 7418, 2012

Education is known to be the key determinant of economic growth and prosperity [8,12]. While the issues in devising a high-quality educational system are multi-faceted and complex, textbooks are acknowledged to be the educational input most consistently associated with gains in student learning [11]. They are the primary conduits for delivering content knowledge to the students and the teachers base their lesson plans primarily on the material given in textbooks [7]. With the emergence of abundant online content, cloud computing, and electronic reading devices, textbooks are poised for transformative changes. Notwithstanding understandable misgivings (e.g. Gutenberg Elegies [6]), textbooks cannot escape what Walter Ong calls 'the technologizing of the word' [9]. The electronic format comes naturally to the current generation of 'digital natives' [10]. Inspired by the emergence of this new medium for "printing" and "distributing" textbooks, we present our early explorations into developing a data mining based approach for enhancing the quality of electronic textbooks. Speci�cally, we �rst describe a diagnostic tool for authors and educators to algorithmically identify de�ciencies in textbooks. We then discuss techniques for algorithmically augmenting different sections of a book with links to selective content mined from the Web. Our tool for diagnosing de�ciencies consists of two components. Abstracting from the education literature, we identify the following properties of good textbooks: (1) Focus : Each section explains few concepts, (2) Unity: For every concept, there is a unique section that best explains the concept, and (3) Sequentiality: Concepts are discussed in a sequential fashion so that a concept is explained prior to occurrences of this concept or any related concept. Further, the tie for precedence in presentation between two mutually related concepts is broken in favor of the more signi�cant of the two. The �rst component provides an assessment of the extent to which these properties are followed in a textbook and quanti�es the comprehension load that a textbook imposes on the reader due to non-sequential presentation of concepts [1,2]. The second component identi�es sections that are not written well and can bene�t from further exposition. We propose a probabilistic decision model for this purpose, which is based on the syntactic complexity of writing and the notion of the dispersion of key concepts mentioned in the section [4]. For augmenting a section of a textbook, we �rst identify the set of key concept phrases contained in a section. Using these phrases, we �nd web articles that represent the central concepts presented in the section and endow the section with links to them [5]. We also describe techniques for �nding images that are most relevant toa section of the textbook, while respecting the constraint that the same image is not repeated indifferent sections of the same chapter. We pose this problem of matching images to sections in a textbook chapter as an optimization problem and present an ef�cient algorithm for solving it [3].
Rakesh Agrawal, Sunandan Chakraborty, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Quality of Textbooks: An Empirical Study, ACM Symposium on Computing for Development (ACM DEV), 2012 [PDF]

Textbooks are the educational input most consistently associated with gains in student learning. Particularly in developing countries, textbooks are the primary conduits for delivering content knowledge to the students and the teachers base their lesson plans on the material given in textbooks. Abstracting from the education literature, we propose that well-written textbooks exhibit the following properties:

FOCUS. Each section explains very few concepts.

UNITY. For each concept, there is a unique section that best explains the concept.

SEQUENTIALITY. Concepts are discussed in a sequential fashion: a concept is explained prior to occurrences of this concept or any related concept. Further, the tie for precedence in presentation between two mutually related concepts is broken in favor of the more significant of the two.
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Data Mining for Improving Textbooks (invited paper), ACM SIGKDD Explorations Newsletter, December 2011 [PDF]

We present our early explorations into developing a data mining based approach for enhancing the quality of textbooks. We describe a diagnostic tool to algorithmically identify deficient sections in textbooks. We also discuss techniques for algorithmically augmenting textbook sections with links to selective content mined from the Web. Our evaluation, employing widely-used textbooks from India, indicates that developing technological approaches to help improve textbooks holds promise.
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Enriching Textbooks with Images, ACM International Conference on Information and Knowledge Management (CIKM), 2011 [PDF]

Textbooks have a direct bearing on the quality of education imparted to the students. Therefore, it is of paramount importance that the educational content of textbooks should provide rich learning experience to the students. Recent studies on understanding learning behavior suggest that the incorporation of digital visual material can greatly enhance learning. However, textbooks used in many developing regions are largely text-oriented and lack good visual material. We propose techniques for finding images from the web that are most relevant for augmenting a section of the textbook, while respecting the constraint that the same image is not repeated in different sections of the same chapter. We devise a rigorous formulation of the image assignment problem and present a polynomial time algorithm for solving the problem optimally. We also present two image mining algorithms that utilize orthogonal signals and hence obtain different sets of relevant images. Finally, we provide an ensembling algorithm for combining the assignments. To empirically evaluate our techniques, we use a corpus of high school textbooks in use in India. Our user study utilizing the Amazon Mechanical Turk platform indicates that the proposed techniques are able to obtain images that can help increase the understanding of the textbook material.
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Enriching Education through Data Mining (invited paper), International Conference on Pattern Recognition and Machine Intelligence (PReMI), LNCS 6744, 2011

Education is acknowledged to be the primary vehicle for improving the economic well-being of people [1,6]. Textbooks have a direct bearing on the quality of education imparted to the students as they are the primary conduits for delivering content knowledge [9]. They are also indispensable for fostering teacher learning and constitute a key component of the ongoing professional development of the teachers [5,8]. Many textbooks, particularly from emerging countries, lack clear and adequate coverage of important concepts [7]. In this talk, we present our early explorations into developing a data mining based approach for enhancing the quality of textbooks. We discuss techniques for algorithmically augmenting different sections of a book with links to selective content mined from the Web. For �nding authoritative articles, we �rst identify the set of key concept phrases contained in a section. Using these phrases, we �nd web (Wikipedia) articles that represent the central concepts presented in the section and augment the section with links to them [4]. We also describe a framework for �nding images that are most relevant to a section of the textbook, while respecting global relevancy to the entire chapter to which the section belongs. We pose this problem of matching images to sections in a textbook chapter as an optimization problem and present an e�ƒcient algorithm for solving it [2].
Rakesh Agrawal, Sreenivas Gollapudi, Anitha Kannan, and Krishnaram Kenthapadi, Identifying Enrichment Candidates in Textbooks, International World Wide Web Conference (WWW), 2011 [PDF]

Many textbooks written in emerging countries lack clear and adequate coverage of important concepts. We propose a technological solution for algorithmically identifying those sections of a book that are not well written and could benefit from better exposition. We provide a decision model based on the syntactic complexity of writing and the dispersion of key concepts. The model parameters are learned using a tune set which is algorithmically generated using a versioned authoritative web resource as a proxy. We evaluate the proposed methodology over a corpus of Indian textbooks which demonstrates its effectiveness in identifying enrichment candidates.
Rakesh Agrawal, Sreenivas Gollapudi, Krishnaram Kenthapadi, Nitish Srivastava, and Raja Velu, Enriching Textbooks Through Data Mining, ACM Symposium on Computing for Development (ACM DEV), 2010 [PDF]

Textbooks play an important role in any educational system. Unfortunately, many textbooks produced in developing countries are not written well and they often lack adequate coverage of important concepts. We propose a technological solution to address this problem based on enriching textbooks with authoritative web content. We augment textbooks at the section level for key concepts discussed in the section. We use ideas from data mining for identifying the concepts that need augmentation as well as to determine the links to the authoritative content that should be used for augmentation. Our evaluation, employing textbooks from India, shows that we are able to enrich textbooks on different subjects and across different grades with high quality augmentations using automated techniques.
Rakesh Agrawal, Sreenivas Gollapudi, and Krishnaram Kenthapadi, Computing for the Underserved (invited paper), CCC Workshop on Computer Science and Global Development, Computing Community Consortium, August 2009

We make the case for focusing on economically disadvantaged and for developing technological solutions to address their needs. We then discuss compelling computing applications for the underserved: (a) viewing mobile phone as the first computing device (b) democratizing access to education.

Algorithmic Identification and Ranking of Twitter Groups:

James Cook, Abhimanyu Das, Krishnaram Kenthapadi, and Nina Mishra, Ranking Twitter Discussion Groups, ACM Conference on Online Social Networks (COSN), 2014 [PDF]

A discussion group is a repeated, synchronized conversation organized around a specific topic. Groups are extremely valuable to the attendees, creating a sense of community among like-minded users. While groups may involve many users, there are many outside the group that would benefit from participation. However, finding the right group is not easy given their quantity and given topic overlap. We study the following problem: given a search query, find a good ranking of discussion groups. We describe a random walk model for how users select groups: starting with a group relevant to the query, a hypothetical user repeatedly selects an authoritative user in the group and then moves to a group according to what the authoritative user prefers. The stationary distribution of this walk yields a group ranking. We analyze this random walk model, demonstrating that it enjoys many natural properties of a desirable ranking algorithm. We study groups on Twitter where conversations can be organized via pre-designated hashtags. These groups are an emerging phenomenon and there are at least tens of thousands in existence today according to our calculations. Via an extensive collection of experiments on one year of tweets, we show that our model effectively ranks groups, outperforming several baseline solutions.
James Cook, Krishnaram Kenthapadi, and Nina Mishra, Group Chats on Twitter, International World Wide Web Conference (WWW), 2013 [PDF]

We report on a new kind of group conversation on Twitter that we call a group chat. These chats are periodic, synchronized group conversations focused on specific topics and they exist at a massive scale. The groups and the members of these groups are not explicitly known. Rather, members agree on a hashtag and a meeting time (e.g., 3pm Pacific Time every Wednesday) to discuss a subject of interest. Topics of these chats are numerous and varied. Some are serious: for example, there are support groups for post-partum depression and borderline personality disorder. Others are about a passionate interest: topics include skiing, photography, movies, wine and foodie communities. We develop a definition of a group that is inspired by how sociologists define groups and present an algorithm for discovering groups. We prove that our algorithms find all groups under certain assumptions. While these groups are of course known to the people who participate in the discussions, what we do not believe is known is the number and variety of groups. We provide some insight into the nature of these groups based on two years of tweets.

Web Search and Related Topics:

Marc Najork, Dennis Fetterly, Alan Halverson, Krishnaram Kenthapadi, and Sreenivas Gollapudi, Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs, ACM International Conference on Web Search and Data Mining (WSDM), 2012 [PDF]

Many phenomena and artifacts such as road networks, social networks and the web can be modeled as large graphs and analyzed using graph algorithms. However, given the size of the underlying graphs, efficient implementation of basic operations such as connected component analysis, approximate shortest paths, and link-based ranking (e.g. PageRank) becomes challenging.

This paper presents an empirical study of computations on such large graphs in three well-studied platform models, viz., a relational model, a data-parallel model, and a special-purpose in-memory model. We choose a prototypical member of each platform model and analyze the computational efficiencies and requirements for five basic graph operations used in the analysis of real-world graphs viz., PageRank, SALSA, Strongly Connected Components (SCC), Weakly Connected Components (WCC), and Approximate Shortest Paths (ASP). Further, we characterize each platform in terms of these computations using model-specific implementations of these algorithms on a large web graph. Our experiments show that there is no single platform that performs best across different classes of operations on large graphs. While relational databases are powerful and flexible tools that support a wide variety of computations, there are computations that benefit from using special-purpose storage systems and others that can exploit data-parallel platforms.
Shuai Ding, Sreenivas Gollapudi, Samuel Ieong, Krishnaram Kenthapadi, and Alexandros Ntoulas, Indexing Strategies for Graceful Degradation of Search Quality, International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), 2011 [PDF]

Large web search engines process billions of queries each day over tens of billions of documents with often very stringent requirements for a user�€™s search experience, in particular, low latency and highly relevant search results. Index generation and serving are key to satisfying both these requirements. For example, the load to search engines can vary drastically when popular events happen around the world. In the case when the load is exceeding what the search engine can serve, queries will get dropped. This results in an ungraceful degradation in search quality. Another example that could increase the query load and affect the user�€™s search experience are ambiguous queries which often result in the execution of multiple query alterations in the back end.

In this paper, we look into the problem of designing robust indexing strategies, i.e. strategies that allow for a graceful degradation of search quality in both the above scenarios. We study the problems of index generation and serving using the notions of document allocation, server selection, and document replication. We explore the space of efficient algorithms for these problems and empirically corroborate with existing theory that it is hard to optimally solve the allocation and selection problems without any replication. We propose a greedy replication algorithm and study its performance under different choices of allocation and selection. Further, we show that under random selection and allocation, our algorithm is optimal.
Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alex Ntoulas, Releasing Search Queries and Clicks Privately, International World Wide Web Conference (WWW), 2009 [PDF] (Best Paper Award Finalist; Media coverage: New Scientist [PDF], ACM TechNews, TechFlash, and other sources)

The question of how to publish an anonymized search log was brought to the forefront by a well-intentioned, but privacy-unaware AOL search log release. Since then a series of ad-hoc techniques have been proposed in the literature, though none are known to be provably private. In this paper, we take a major step towards a solution: we show how queries, clicks and their associated perturbed counts can be published in a manner that rigorously preserves privacy. Our algorithm is decidedly simple to state, but non-trivial to analyze. On the opposite side of privacy is the question of whether the data we can safely publish is of any use. Our findings offer a glimmer of hope: we demonstrate that a non-negligible fraction of queries and clicks can indeed be safely published via a collection of experiments on a real search log. In addition, we select an application, keyword generation, and show that the keyword suggestions generated from the perturbed data resemble those generated from the original data.
Rakesh Agrawal, Alan Halverson, Krishnaram Kenthapadi, Nina Mishra, and Panayiotis Tsaparas, Generating Labels from Clicks, ACM International Conference on Web Search and Data Mining (WSDM), 2009 [PDF]

The ranking function used by search engines to order results is learned from labeled training data. Each training point is a (query, URL) pair that is labeled by a human judge who assigns a score of Perfect, Excellent, etc., depending on how well the URL matches the query. In this paper, we study whether clicks can be used to automatically generate good labels. Intuitively, documents that are clicked (resp., skipped) in aggregate can indicate relevance (resp., lack of relevance). We give a novel way of transforming clicks into weighted, directed graphs inspired by eye-tracking studies and then devise an objective function for finding cuts in these graphs that induce a good labeling. In its full generality, the problem is NP-hard, but we show that, in the case of two labels, an optimum labeling can be found in linear time. For the more general case, we propose heuristic solutions. Experiments on real click logs show that clickbased labels align with the opinion of a panel of judges, especially as the consensus of the panel grows stronger.

Large Graph/Data Algorithms:

Marc Najork, Dennis Fetterly, Alan Halverson, Krishnaram Kenthapadi, and Sreenivas Gollapudi, Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs, ACM International Conference on Web Search and Data Mining (WSDM), 2012 [PDF]

Many phenomena and artifacts such as road networks, social networks and the web can be modeled as large graphs and analyzed using graph algorithms. However, given the size of the underlying graphs, efficient implementation of basic operations such as connected component analysis, approximate shortest paths, and link-based ranking (e.g. PageRank) becomes challenging.

This paper presents an empirical study of computations on such large graphs in three well-studied platform models, viz., a relational model, a data-parallel model, and a special-purpose in-memory model. We choose a prototypical member of each platform model and analyze the computational efficiencies and requirements for five basic graph operations used in the analysis of real-world graphs viz., PageRank, SALSA, Strongly Connected Components (SCC), Weakly Connected Components (WCC), and Approximate Shortest Paths (ASP). Further, we characterize each platform in terms of these computations using model-specific implementations of these algorithms on a large web graph. Our experiments show that there is no single platform that performs best across different classes of operations on large graphs. While relational databases are powerful and flexible tools that support a wide variety of computations, there are computations that benefit from using special-purpose storage systems and others that can exploit data-parallel platforms.
Krishnaram Kenthapadi and Rina Panigrahy, Balanced Allocation on Graphs, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006 [arxiv] (Student Best Paper Award)

It is well known that if $n$ balls are inserted into $n$ bins, with high probability, the bin with maximum load contains $(1+ o(1)) \log n / \log\log n$ balls. Azar, Broder, Karlin, and Upfal [ABKU99] showed that instead of choosing one bin, if $d \ge 2$ bins are chosen at random and the ball inserted into the least loaded of the $d$ bins, the maximum load reduces drastically to $\log\log n /\log d + O(1)$. In this paper, we study the two choice balls and bins process when balls are not allowed to choose any two random bins, but only bins that are connected by an edge in an underlying graph. We show that for $n$ balls and $n$ bins, if the graph is almost regular with degree $n^\epsilon$, where $\epsilon$ is not too small, the previous bounds on the maximum load continue to hold. Precisely, the maximum load is $\log \log n + O(1/\epsilon) + O(1)$. So even if the graph has degree $n^{\Omega(1/\log\log n)}$, the maximum load is $O(\log\log n)$. For general $\Delta$-regular graphs, we show that the maximum load is $\log\log n + O(\frac{\log n}{\log (\Delta/\log^4 n)}) + O(1)$ and also provide an almost matching lower bound of $\log \log n + \frac{\log n}{\log (\Delta \log n)}$. Further this does not hold for non-regular graphs even if the minimum degree is high.

V{\"o}cking [Voc99] showed that the maximum bin size with $d$ choice load balancing can be further improved to $O(\log\log n /d)$ by breaking ties to the left. This requires $d$ random bin choices. We show that such bounds can be achieved by making only two random accesses and querying $d/2$ contiguous bins in each access. By grouping a sequence of $n$ bins into $2n/d$ groups, each of $d/2$ consecutive bins, if each ball chooses two groups at random and inserts the new ball into the least-loaded bin in the lesser loaded group, then the maximum load is $O(\log\log n/d)$ with high probability. Furthermore, it also turns out that this partitioning into groups of size $d/2$ is also essential in achieving this bound, that is, instead of choosing two random groups, if we simply choose two random sets of $d/2$ consecutive bins, then the maximum load jumps to $\Omega(\log\log n /\log d)$.
Krishnaram Kenthapadi and Gurmeet Singh Manku, Decentralized Algorithms using both Local and Random Probes for P2P Load Balancing, ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2005 [PDF]

We study randomized algorithms for placing a sequence of n nodes on a circle with unit perimeter. Nodes divide the circle into disjoint arcs. We desire that a newly-arrived node (which is oblivious of its index in the sequence) choose its position on the circle by learning the positions of as few existing nodes as possible. At the same time, we desire that that the variation in arc-lengths be small. To this end, we propose a new algorithm that works as follows: The kth node chooses r random points on the circle, inspects the sizes of v arcs in the vicinity of each random point, and places itself at the mid-point of the largest arc encountered. We show that for any combination of r and v satisfying $rv \ge c \log k$, where c is a small constant, the ratio of the largest to the smallest arc-length is at most eight w.h.p., for an arbitrarily long sequence of n nodes. This strategy of node placement underlies a novel decentralized load-balancing algorithm that we propose for Distributed Hash Tables (DHTs) in peer-to-peer environments.

Underlying the analysis of our algorithm is Structured Coupon Collection over n/b disjoint cliques with b nodes per clique, for any $n, b \ge 1$. Nodes are initially uncovered. At each step, we choose d nodes independently and uniformly at random. If all the nodes in the corresponding cliques are covered, we do nothing. Otherwise, from among the chosen cliques with at least one uncovered node, we select one at random and cover an uncovered node within that clique. We show that as long as $bd \ge c \log n$, O(n) steps are sufficient to cover all nodes w.h.p. and each of the first $\Omega(n)$ steps succeeds in covering a node w.h.p. These results are then utilized to analyze a stochastic process for growing binary trees that are highly balanced - the leaves of the tree belong to at most four different levels with high probability.

Privacy:

Krishnaram Kenthapadi, Nina Mishra, and Kobbi Nissim, Denials Leak Information: Simulatable Auditing, Journal of Computer and System Sciences, vol. 79 (8), pp. 1322-1340, Elsevier, December 2013

Imagine a data set consisting of private information about individuals. The online query auditing problem is: given a sequence of queries that have already been posed about the data, their corresponding answers and given a new query, deny the answer if privacy can be breached or give the true answer otherwise. We investigate the fundamental problem that query denials leak information. This problem was largely overlooked in previous work on auditing. Because of this oversight, some of the previously suggested auditors can be used by an attacker to compromise the privacy of a large fraction of the individuals in the data. To overcome this problem, we introduce a new model called simulatable auditing where query denials provably do not leak information. We present a simulatable auditing algorithm for max queries under the classical definition of privacy where a breach occurs if a sensitive value is fully compromised. Because of the known limitations of the classical definition of compromise, we describe a probabilistic notion of (partial) compromise, closely related to the notion of semantic security. We demonstrate that sum queries can be audited in a simulatable fashion under probabilistic compromise, making some distributional assumptions.
Krishnaram Kenthapadi, Aleksandra Korolova, Ilya Mironov, and Nina Mishra, Privacy via the Johnson-Lindenstrauss Transform, Journal of Privacy and Confidentiality, vol. 5 (1), July 2013

Suppose that party A collects private information about its users, where each user�€™s data is represented as a bit vector. Suppose that party B has a proprietary data mining algorithm that requires estimating the distance between users, such as clustering or nearest neighbors. We ask if it is possible for party A to publish some information about each user so that B can estimate the distance between users without being able to infer any private bit of a user. Our method involves projecting each user�€™s representation into a random, lower-dimensional space via a sparse Johnson-Lindenstrauss transform and then adding Gaussian noise to each entry of the lower-dimensional representation. We show that the method preserves differential privacy�€”where the more privacy is desired, the larger the variance of the Gaussian noise. Further, we show how to approximate the true distances between users via only the lower-dimensional, perturbed data. Finally, we consider other perturbation methods such as randomized response and draw comparisons to sketch-based methods. While the goal of releasing user-specific data to third parties is more broad than preserving distances, this work shows that distance computations with privacy is an achievable goal.
Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, and An Zhu, Achieving anonymity via clustering, ACM Transactions on Algorithms (TALG), vol. 6, no. 3, pp. 49:1-49:19, ACM, July 2010 [PDF]

Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of deidentifying records is to remove identifying fields such as social security number, name, etc. However, recent research has shown that a large fraction of the U.S. population can be identified using nonkey attributes (called quasi-identifiers) such as date of birth, gender, and zip code. The k-anonymity model protects privacy via requiring that nonkey attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k�ˆ’1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a prespecified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an ε fraction of points to remain unclustered, that is, deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.
Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alex Ntoulas, Releasing Search Queries and Clicks Privately, International World Wide Web Conference (WWW), 2009 [PDF] (Best Paper Award Finalist; Media coverage: New Scientist [PDF], ACM TechNews, TechFlash, and other sources)

The question of how to publish an anonymized search log was brought to the forefront by a well-intentioned, but privacy-unaware AOL search log release. Since then a series of ad-hoc techniques have been proposed in the literature, though none are known to be provably private. In this paper, we take a major step towards a solution: we show how queries, clicks and their associated perturbed counts can be published in a manner that rigorously preserves privacy. Our algorithm is decidedly simple to state, but non-trivial to analyze. On the opposite side of privacy is the question of whether the data we can safely publish is of any use. Our findings offer a glimmer of hope: we demonstrate that a non-negligible fraction of queries and clicks can indeed be safely published via a collection of experiments on a real search log. In addition, we select an application, keyword generation, and show that the keyword suggestions generated from the perturbed data resemble those generated from the original data.
Shubha Nabar, Krishnaram Kenthapadi, Nina Mishra, and Rajeev Motwani, A Survey of Query Auditing Techniques for Data Privacy, Chapter in Privacy-Preserving Data Mining: Models and Algorithms, Kluwer Academic Publishers, 2008

This chapter is a survey of query auditing techniques for detecting and preventing disclosures in a database containing private data. Informally, auditing is the process of examining past actions to check whether they were in conformance with official policies. In the context of database systems with specific data disclosure policies, auditing is the process of examining queries that were answered in the past to determine whether answers to these queries could have been used by an individual to ascertain confidential nformation forbidden by the disclosure policies. Techniques used for detecting disclosures could potentially also be used or extended to prevent disclosures, and so in addition to the retroactive auditing mentioned above, researchers have also studied an online variant of the auditing problem wherein the task of an online auditor is to deny queries that could potentially cause a breach of privacy.
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor, Our Data, Ourselves: Privacy Via Distributed Noise Generation, International Conference on the Theory and Applications of Cryptographic Techniques, Advances in Cryptology (EUROCRYPT), 2006

In this work we provide efficient distributed protocols for generating shares of random noise, secure against malicious participants. The purpose of the noise generation is to create a distributed implementation of the privacy-preserving statistical databases described in recent papers [14,4,13]. In these databases, privacy is obtained by perturbing the true answer to a database query by the addition of a small amount of Gaussian or exponentially distributed random noise. The computational power of even a simple form of these databases, when the query is just of the form $\sum_i f(d_i)$, that is, the sum over all rows i in the database of a function f applied to the data in row i, has been demonstrated in [4]. A distributed implementation eliminates the need for a trusted database administrator.

The results for noise generation are of independent interest. The generation of Gaussian noise introduces a technique for distributing shares of many unbiased coins with fewer executions of verifiable secret sharing than would be needed using previous approaches (reduced by a factor of n). The generation of exponentially distributed noise uses two shallow circuits: one for generating many arbitrarily but identically biased coins at an amortized cost of two unbiased random bits apiece, independent of the bias, and the other to combine bits of appropriate biases to obtain an exponential distribution.
Shubha U. Nabar, Bhaskara Marthi, Krishnaram Kenthapadi, Nina Mishra, and Rajeev Motwani, Towards Robustness in Query Auditing, International Conference on Very Large Data Bases (VLDB), 2006

We consider the online query auditing problem for a database containing private information about individuals: given a sequence of queries posed by an attacker, when should queries be denied to prevent privacy breaches. Historically, all research in auditing has focused on static datasets and known algorithms do not work in the presence of updates. We consider a new auditing problem where records can be inserted, deleted or modified and obtain algorithms for auditing sum queries, max queries and bags of max and min queries in this scenario under the classical notion of compromise. In [KMN05], a new probabilistic definition of compromise was proposed due to the limitations of classical compromise. Since this is a recent development, not much is known about auditing different kinds of queries under this definition. We obtain new algorithms for auditing max queries and bags of max and min queries under probabilistic compromise. We conclude with a study of a certain aspect of the utility delivered by an auditing scheme and obtain initial results for the utility of sum auditing under classical compromise.
Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Samir Khuller, Rina Panigrahy, Dilys Thomas, and An Zhu, Achieving Anonymity via Clustering, ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), 2006 [PDF]

Publishing data for analysis from a table containing personal records, while maintaining individual privacy, is a problem of increasing importance today. The traditional approach of de-identifying records is to remove identifying fields such as social security number, name etc. However, recent research has shown that a large fraction of the US population can be identified using non-key attributes (called quasi-identifiers) such as date of birth, gender, and zip code. The k-anonymity model protects privacy via requiring that non-key attributes that leak information are suppressed or generalized so that, for every record in the modified table, there are at least k�ˆ’1 other records having exactly the same values for quasi-identifiers. We propose a new method for anonymizing data records, where quasi-identifiers of data records are first clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a pre-specified number of data records. This technique is more general since we have a much larger choice for cluster centers than k-Anonymity. In many cases, it lets us release a lot more information without compromising privacy. We also provide constant factor approximation algorithms to come up with such a clustering. This is the first set of algorithms for the anonymization problem where the performance is independent of the anonymity parameter k. We further observe that a few outlier points can significantly increase the cost of anonymization. Hence, we extend our algorithms to allow an $\epsilon$ fraction of points to remain unclustered, i.e., deleted from the anonymized publication. Thus, by not releasing a small fraction of the database records, we can ensure that the data published for analysis has less distortion and hence is more useful. Our approximation algorithms for new clustering objectives are of independent interest and could be applicable in other clustering scenarios as well.
Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-Molina, Krishnaram Kenthapadi, Rajeev Motwani, Utkarsh Srivastava, Dilys Thomas, and Ying Xu, Two Can Keep a Secret: A Distributed Architecture for Secure Database Services, Conference on Innovative Data Systems Research (CIDR), 2005

Recent trends towards database outsourcing, as well as concerns and laws governing data privacy, have led to great interest in enabling secure database services. Previous approaches to enabling such a service have been based on data encryption, causing a large overhead in query processing. We propose a new, distributed architecture that allows an organization to outsource its data management to two untrusted servers while preserving data privacy. We show how the presence of two servers enables efficient partitioning of data so that the contents at any one server are guaranteed not to breach data privacy. We show how to optimize and execute queries in this architecture, and discuss new challenges that emerge in designing the database schema.
Krishnaram Kenthapadi, Nina Mishra, and Kobbi Nissim, Simulatable Auditing, ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), 2005 [PDF]

Given a data set consisting of private information about individuals, we consider the online query auditing problem: given a sequence of queries that have already been posed about the data, their corresponding answers -- where each answer is either the true answer or "denied" (in the event that revealing the answer compromises privacy) -- and given a new query, deny the answer if privacy may be breached or give the true answer otherwise. A related problem is the offline auditing problem where one is given a sequence of queries and all of their true answers and the goal is to determine if a privacy breach has already occurred.

We uncover the fundamental issue that solutions to the offline auditing problem cannot be directly used to solve the online auditing problem since query denials may leak information. Consequently, we introduce a new model called simulatable auditing where query denials provably do not leak information. We demonstrate that max queries may be audited in this simulatable paradigm under the classical definition of privacy where a breach occurs if a sensitive value is fully compromised. We also introduce a probabilistic notion of (partial) compromise. Our privacy definition requires that the a-priori probability that a sensitive value lies within some small interval is not that different from the posterior probability (given the query answers). We demonstrate that sum queries can be audited in a simulatable fashion under this privacy definition.
Gagan Aggarwal, Tomas Feder, Krishnaram Kenthapadi, Rajeev Motwani, Rina Panigrahy, Dilys Thomas, and An Zhu, Approximation Algorithms for k-Anonymity, Journal of Privacy Technology, 2005. Preliminary version: Anonymizing Tables, International Conference on Database Theory (ICDT), 2005.

We consider the problem of releasing a table containing personal records, while ensuring individual privacy and maintaining data integrity to the extent possible. One of the techniques proposed in the literature is k-anonymization. A release is considered k-anonymous if the information corresponding to any individual in the release cannot be distinguished from that of at least k�ˆ’1 other individuals whose information also appears in the release. In order to achieve k-anonymization, some of the entries of the table are either suppressed or generalized (e.g. an Age value of 23 could be changed to the Age range 20-25). The goal is to lose as little information as possible while ensuring that the release is k-anonymous. This optimization problem is referred to as the k-Anonymity problem. We show that the k-Anonymity problem is NP-hard even when the attribute values are ternary and we are allowed only to suppress entries. On the positive side, we provide an O(k)-approximation algorithm for the problem. We also give improved positive results for the interesting cases with specific values of k �€” in particular, we give a 1.5-approximation algorithm for the special case of 2-Anonymity, and a 2-approximation algorithm for 3-Anonymity.
Gagan Aggarwal, Mayank Bawa, Prasanna Ganesan, Hector Garcia-Molina, Krishnaram Kenthapadi, Nina Mishra, Rajeev Motwani, Utkarsh Srivastava, Dilys Thomas, Jennifer Widom, and Ying Xu, Vision Paper: Enabling Privacy for the Paranoids, International Conference on Very Large Data Bases (VLDB), 2004

P3P is a set of standards that allow corporations to declare their privacy policies. Hippocratic Databases have been proposed to implement such policies within a corporation's datastore. From an end-user individual's point of view, both of these rest on an uncomfortable philosophy of trusting corporations to protect his/her privacy. Recent history chronicles several episodes when such trust has been willingly or accidentally violated by corporations facing bankruptcy courts, civil subpoenas or lucrative mergers. We contend that data management solutions for information privacy must restore controls in the individual's hands. We suggest that enabling such control will require a radical re-think on modeling, release, and management of personal data.

PhD Thesis:

Krishnaram Kenthapadi, Models and Algorithms for Data Privacy, Stanford University, September 2006

Over the last twenty years, there has been a tremendous growth in the amount of private data collected about individuals. With the rapid growth in database, networking, and computing technologies, such data can be integrated and analyzed digitally. On the one hand, this has led to the development of data mining tools that aim to infer useful trends from this data. But, on the other hand, easy access to personal data poses a threat to individual privacy. In this thesis, we provide models and algorithms for protecting the privacy of individuals in such large data sets while still allowing users to mine useful trends and statistics.

We focus on the problem of statistical disclosure control - revealing aggregate statistics about a population while preserving the privacy of individuals. A statistical database can be viewed as a table containing personal records, where the rows correspond to individuals and the columns correspond to different attributes. For example, a medical database may contain attributes such as name, social security number, address, age, gender, ethnicity, and medical history for each patient. We would like the medical researchers to have some form of access to this database so as to learn trends such as correlation between age and heart disease, while maintaining individual privacy. There are broadly two frameworks for protecting privacy in statistical databases. In the interactive framework, the user (researcher) queries the database through a privacy mechanism, which may deny the query or alter the answer to the query in order to ensure privacy. In the non-interactive framework, the original database is first sanitized so as to preserve privacy and then the modified version is released. We study methods under both these frameworks as each method is useful in different contexts.

The first part of the thesis focuses on the interactive framework and provides models and algorithms for two methods used in this framework. We first consider the online query auditing problem: given a sequence of queries that have already been posed about the data, their corresponding answers and given a new query, deny the answer if privacy can be breached or give the true answer otherwise. We uncover the fundamental problem that query denials leak information. As this problem was overlooked in previous work, some of the previously suggested auditors can be used by an attacker to compromise the privacy of a large fraction of the individuals in the data. To overcome this problem, we introduce a new model called simulatable auditing where query denials provably do not leak information. We also describe a probabilistic notion of (partial) compromise, in order to overcome the known limitations of the existing privacy definition. We then present simulatable auditing algorithms under both these definitions. The second problem we consider is output perturbation, in which the database administrator computes exact answer to the query and then outputs a perturbed answer (by adding random noise) as the response to the query. Inspired by the desire to enable individuals to retain control over their information, we provide a fault-tolerant distributed implementation of output perturbation schemes, thereby eliminating the need for a trusted database administrator.

The second part of the thesis focuses on the non-interactive framework and considers two anonymization methods for publishing data for analysis from a table containing personal records. We present approximation algorithms for anonymizing databases using the k-Anonymity model. Then we propose a new method for anonymizing data records, where the data records are clustered and then cluster centers are published. To ensure privacy of the data records, we impose the constraint that each cluster must contain no fewer than a pre-specified number of data records. We provide approximation algorithms to come up with such a clustering.

Krishnaram Kenthapadi

Krishnaram Kenthapadi's Publications

Selected Projects

Publications, Articles, Talks, and Tutorials Since 2016

Document Understanding and Augmentation with Multimedia Content / Computational Education

Algorithmic Identification and Ranking of Twitter Groups

Web Search and Related Topics

Large Graph/Data Algorithms

Privacy

PhD Thesis