OpenRaiser/Intern-Atlas huggingface dataset:
A Causal Look at Statistical Definitions of Discrimination
Authors: Elias Chaibub Neto
Venue: KDD
Year: 2020

Predictive parity and error rate balance are both widely accepted and adopted criteria for assessing fairness of classifiers. The realization that these equally reasonable criteria can lead to contradictory results has, nonetheless, generated a lot of debate/controversy, and has motivated the development of mathematical results establishing the impossibility of concomitantly satisfying predictive parity and error rate balance. Here, we investigate these fairness criteria from a causality perspective. By taking into consideration the data generation process giving rise to the observed data, as well as, the data generation process giving rise to the predictions, and assuming faithfulness, we prove that when the base rates differ across the protected groups and there is no perfect separation, then a standard classifier cannot achieve exact predictive parity. (Where, by standard classifier we mean a classifier trained in the usual way, without adopting pre-processing, in-processing, or post-processing fairness techniques.) This result holds in general, irrespective of the data generation process giving rise to the observed data. Furthermore, we show that the amount of disparate mistreatment for the positive predictive value metric is proportional to the difference between the base rates. For the error rate balance, as well as, the closely related equalized odds and equality of opportunity criteria, we show that there are, nonetheless, data generation processes that can still satisfy these criteria when the base rates differ by protected group, and we characterize the conditions under which these criteria hold. We illustrate our results using synthetic data, and with the re-analysis of the COMPAS data.
A Dual Heterogeneous Graph Attention Network to Improve Long-Tail Performance for Shop Search in E-Commerce
Authors: Xichuan Niu, Bofang Li, Chenliang Li 0005, Rong Xiao 0005, Haochuan Sun, Hongbo Deng, Zhenzhong Chen
Venue: KDD
Year: 2020

Shop search has become an increasingly important service provided by Taobao, the China's largest e-commerce platform. By using shop search, a user can easily identify the desired shop that provides a full-scale of relevant items matching his information need. With the tremendous growth of users and shops, shop search faces several unique challenging problems: 1) many shop names do not fully express what they sell, i.e., the semantic gap between user query and shop name; 2) due to the lack of user interactions, it is difficult to deliver a good search result for the long-tail queries and retrieve long-tail shops that are highly relevant to a query.
Edge-consensus Learning: Deep Learning on P2P Networks with Nonhomogeneous Data
Authors: Kenta Niwa, Noboru Harada, Guoqiang Zhang 0003, W. Bastiaan Kleijn
Venue: KDD
Year: 2020

An effective Deep Neural Network (DNN) optimization algorithm that can use decentralized data sets over a peer-to-peer (P2P) network is proposed. In applications such as medical data analysis, the aggregation of data in one location may not be possible due to privacy issues. Hence, we formulate an algorithm to reach a global DNN model that does not require transmission of data among nodes. An existing solution for this issue is gossip stochastic gradient descend (SGD), which updates by averaging node models over a P2P network. However, in practical situations where the data are statistically heterogeneous across the nodes and/or where communication is asynchronous, gossip SGD often gets trapped in local minimum since the model gradients are noticeably different. To overcome this issue, we solve a linearly constrained DNN cost minimization problem, which results in variable update rules that restrict differences among all node models. Our approach can be based on the Primal-Dual Method of Multipliers (PDMM) or the Alternating Direction Method of Multiplier (ADMM), but the cost function is linearized to be suitable for deep learning. It facilitates asynchronous communication. The results of our numerical experiments using CIFAR-10 indicate that the proposed algorithms converge to a global recognition model even though statistically heterogeneous data sets are placed on the nodes.
Scaling Choice Models of Relational Social Data
Authors: Jan Overgoor, George Pakapol Supaniratisai, Johan Ugander
Venue: KDD
Year: 2020

Many prediction problems on social networks, from recommendations to anomaly detection, can be approached by modeling network data as a sequence of relational events and then leveraging the resulting model for prediction. Conditional logit models of discrete choice are a natural approach to modeling relational events as "choices" in a framework that envelops and extends many long-studied models of network formation. The conditional logit model is simplistic, but it is particularly attractive because it allows for efficient consistent likelihood maximization via negative sampling, something that isn't true for mixed logit and many other richer models. The value of negative sampling is particularly pronounced because choice sets in relational data are often enormous. Given the importance of negative sampling, in this work we introduce a model simplification technique for mixed logit models that we call "de-mixing", whereby standard mixture models of network formation---particularly models that mix local and global link formation---are reformulated to operate their modes over disjoint choice sets. This reformulation reduces mixed logit models to conditional logit models, opening the door to negative sampling while also circumventing other standard challenges with maximizing mixture model likelihoods. To further improve scalability, we also study importance sampling for more efficiently selecting negative samples, finding that it can greatly speed up inference in both standard and de-mixed models. Together, these steps make it possible to much more realistically model network formation in very large graphs. We illustrate the relative gains of our improvements on synthetic datasets with known ground truth as well as a large-scale dataset of public transactions on the Venmo platform.
xGAIL: Explainable Generative Adversarial Imitation Learning for Explainable Human Decision Analysis
Authors: Menghai Pan, Weixiao Huang, Yanhua Li, Xun Zhou 0001, Jun Luo 0007
Venue: KDD
Year: 2020

To make daily decisions, human agents devise their own "strategies" governing their mobility dynamics (e.g., taxi drivers have preferred working regions and times, and urban commuters have preferred routes and transit modes). Recent research such as generative adversarial imitation learning (GAIL) demonstrates successes in learning human decision-making strategies from their behavior data using deep neural networks (DNNs), which can accurately mimic how humans behave in various scenarios, e.g., playing video games, etc. However, such DNN-based models are "black box" models in nature, making it hard to explain what knowledge the models have learned from human, and how the models make such decisions, which was not addressed in the literature of imitation learning. This paper addresses this research gap by proposing xGAIL, the first explainable generative adversarial imitation learning framework. The proposed xGAIL framework consists of two novel components, including Spatial Activation Maximization (SpatialAM) and Spatial Randomized Input Sampling Explanation (SpatialRISE), to extract both global and local knowledge from a well-trained GAIL model that explains how a human agent makes decisions. Especially, we take taxi drivers' passenger-seeking strategy as an example to validate the effectiveness of the proposed xGAIL framework. Our analysis on a large-scale real-world taxi trajectory data shows promising results from two aspects: i) global explainable knowledge of what nearby traffic condition impels a taxi driver to choose a particular direction to find the next passenger, and ii) local explainable knowledge of what key (sometimes hidden) factors a taxi driver considers when making a particular decision.
Time-Aware User Embeddings as a Service
Authors: Martin Pavlovski, Jelena Gligorijevic, Ivan Stojkovic, Shubham Agrawal, Shabhareesh Komirishetty, Djordje Gligorijevic, Narayan Bhamidipati, Zoran Obradovic
Venue: KDD
Year: 2020

Digital media companies typically collect rich data in the form of sequences of online user activities. Such data is used in various applications, involving tasks ranging from click or conversion prediction to recommendation or user segmentation. Nonetheless, each application depends upon specialized feature engineering that requires a lot of effort and typically disregards the time-varying nature of the online user behavior. Learning time-preserving vector representations of users (user embeddings), irrespective of a specific task, would save redundant effort and potentially lead to higher embedding quality. To that end, we address the limitations of the current state-of-the-art self-supervised methods for task-independent (unsupervised) sequence embedding, and propose a novel Time-Aware Sequential Autoencoder (TASA) that accounts for the temporal aspects of sequences of activities. The generated embeddings are intended to be readily accessible for many problem formulations and seamlessly applicable to desired tasks, thus sidestepping the burden of task-driven feature engineering. The proposed TASA shows improvements over alternative self-supervised models in terms of sequence reconstruction. Moreover, the embeddings generated by TASA yield increases in predictive performance on both proprietary and public data. It also achieves comparable results to supervised approaches that are trained on individual tasks separately and require substantially more computational effort. TASA has been incorporated within a pipeline designed to provide time-aware user embeddings as a service, and the use of its embeddings exhibited lifts in conversion prediction AUC on four audiences.
Data Pricing - From Economics to Data Science
Authors: Jian Pei 0001
Venue: KDD
Year: 2020

Data are invaluable. How can we assess the value of data objectively and quantitatively? Pricing data, or information goods in general, has been studied and practiced in dispersed areas and principles, such as economics, data management, data mining, electronic commerce, and marketing. In this tutorial, we present a unified and comprehensive overview of this important direction. We examine various motivations behind data pricing, understand the economics of data pricing, review the development and evolution of pricing models, and compare the proposals of marketplaces of data. We cover both digital products, such as ebooks and MP3 music, and data products, such as data sets, data queries and machine learning models. We also connect data pricing with the highly related areas, such as cloud service pricing, privacy pricing, and decentralized privacy preserving infrastructure like blockchains.
Discovering Approximate Functional Dependencies using Smoothed Mutual Information
Authors: Frédéric Pennerath, Panagiotis Mandros, Jilles Vreeken
Venue: KDD
Year: 2020

We consider the task of discovering the top-K reliable approximate functional dependencies X -> Y from high dimensional data. While naively maximizing mutual information involving high dimensional entropies over empirical data is subject to false discoveries, correcting the empirical estimator against data sparsity can lead to efficient exact algorithms for robust dependency discovery. Previous approaches focused on correcting by subtracting expected values of different null hypothesis models. In this paper, we consider a different correction strategy and counter data sparsity using uniform priors and smoothing techniques, that leads to an efficient and robust estimating process. In addition, we derive an admissible and tight bounding function for the smoothed estimator that allows us to efficiently solve via branch-and-bound the hard search problem for the top-K dependencies. Our experiments show that our approach is much faster than previous proposals, and leads to the discovery of sparse and informative functional dependencies.
How Can Computer Science Education Address Inequities
Authors: Manuel A. Pérez-Quiñones
Venue: KDD
Year: 2020

The 2019 global pandemic and the social protests in support of Black Lives Matter has made it clear that society has yet to eradicate systemic racism. Can computing education help? Academics, particularly in STEM fields, are often shielded from these conversations as we think they belong in a social science classroom. The effect of the pandemic and the protests has made it abundantly clear that we can no longer be apathetic about systemic issues that impact equity in society. Based on personal experience and on years of participation in Broadening Participation in Computing (BPC) efforts, the author suggests actions that CS departments can do to fight inequity. These can be classified into several broad categories: (a) provide more support and opportunities to students from underrepresented groups, (b) encourage faculty to become active participants in addressing inequity, (c) update the computing curriculum to be more inclusive and culturally responsive, and (d) evolve the departmental infrastructure to manage diversity, equity and inclusion.
Data Compression as a Comprehensive Framework for Graph Drawing and Representation Learning
Authors: Claudia Plant, Sonja Biedermann, Christian Böhm 0001
Venue: KDD
Year: 2020

Embedding a graph into feature space is a promising approach to understand its structure. Embedding into 2D or 3D space enables visualization; representation in higher-dimensional vector space (typically >100D) enables the application of data mining techniques. For the success of knowledge discovery it is essential that the distances between the embedded vertices truly reflect the structure of the graph. Our fundamental idea is to compress the adjacency matrix by predicting the existence of an edge from the Euclidean distance between the corresponding vertices in the embedding, and to use the achieved compression as a quality measure for the embedding. We call this quality measure Predictive Entropy (PE). PE uses a sigmoid function to define the probability which is monotonically decreasing with the Euclidean distance. We use this sigmoid probability to compress the adjacency matrix of the graph by an entropy coding. While PE could be used to assess the result of any graph drawing or representation learning method we particularly use it as objective function in our new method GEMPE (Graph Embedding by Minimizing the Predictive Entropy). We demonstrate in our experiments that GEMPE clearly outperforms comparison methods with respect to quality of the visual result, clustering and node-labeling accuracy on the discovered coordinates.
Voronoi Graph Traversal in High Dimensions with Applications to Topological Data Analysis and Piecewise Linear Interpolation
Authors: Vladislav Polianskii, Florian T. Pokorny
Venue: KDD
Year: 2020

Voronoi diagrams and their dual, the Delaunay complex, are two fundamental geometric concepts that lie at the foundation of many machine learning algorithms and play a role in particular in classical piecewise linear interpolation and regression methods. More recently, they are also crucial for the construction of a common class of simplicial complexes such as Alpha and Delaunay-\vC ech complexes in topological data analysis. We propose a randomized approximation approach that mitigates the prohibitive cost of exact computation of Voronoi diagrams in high dimensions for machine learning applications. In experiments with data in up to 50 dimensions, we show that this allows us to significantly extend the use of Voronoi-based simplicial complexes in Topological Data Analysis (TDA) to higher dimensions. We confirm prior TDA results on image patches that previously had to rely on sub-sampled data with increased resolution and demonstrate the scalability of our approach by performing a TDA analysis on synthetic data as well as on filters of a ResNet neural network architecture. Secondly, we propose an application of our approach to piecewise linear interpolation of high dimensional data that avoids explicit complete computation of an associated Delaunay triangulation.
Lumos: A Library for Diagnosing Metric Regressions in Web-Scale Applications
Authors: Jamie Pool, Ebrahim Beyrami, Vishak Gopal, Ashkan Aazami, Jayant Gupchup, Jeff Rowland, Binlong Li, Pritesh Kanani, Ross Cutler, Johannes Gehrke
Venue: KDD
Year: 2020

Web-scale applications can ship code on a daily to weekly cadence. These applications rely on online metrics to monitor the health of new releases. Regressions in metric values need to be detected and diagnosed as early as possible to reduce the disruption to users and product owners. Regressions in metrics can surface due to a variety of reasons: genuine product regressions, changes in user population and bias due to telemetry loss (or processing) are among the common causes. Diagnosing the cause of these metric regressions is costly for engineering teams as they need to invest time in finding the root cause of the issue as soon as possible. We presentLumos, a Python library built using the principles of A/B testing to systematically diagnose metric regressions to automate such analysis.Lumos has been deployed across the component teams in Microsoft's Real-Time Communication (RTC) applications Skype and Microsoft Teams. It has enabled engineering teams to detect 100s of real changes in metrics and reject 1000s of false alarms detected by anomaly detectors. The application ofLumos has resulted in freeing up as much as $95%$ of the time allocated to metric-based investigations. In this work, we open sourceLumos and present our results from applying it to two different components within the RTC group over millions of sessions. This general library can be coupled with any production system to manage the volume of alerting efficiently.
Broadening Participation in Technology Policy
Authors: Brianna B. Posadas
Venue: KDD
Year: 2020

Those who work in politics and policy are often unprepared to address the issues that current technology developments have created. A glaring example is the congressional hearings with Facebook where Congress Members asked embarrassingly fundamental questions and were not able to get to the heart of the issue. Many congress people do not have technology advisor on staff to assist in addressing technical issues. Not only does Congress not have technology experts on staff, but the few who are involved are not from underrepresented minority communities. This makes it even more difficult to adequately address issues that more directly impact communities of color including predictive policing, voter suppression, and facial recognition.
Innovating with Language AI
Authors: Ashwin Ram 0001
Venue: KDD
Year: 2020

Understanding human language in real world scenarios involves not just natural language processing but also speech, vision, knowledge graphs, user modeling, and other AI techniques. Doing this at Google scale involves planetary-scale cloud computing as well as tiny-scale edge computing. I'll share a behind-the-scenes look at how Google uses Language AI to power its billion-user products, and discuss some of the newer approaches we are developing to make sense of human language. I'll end with our vision to democratize AI and how you can use Google AI in your own work.
Accelerating and Expanding End-to-End Data Science Workflows with DL/ML Interoperability Using RAPIDS
Authors: Bartley Richardson, Bradley Rees, Tom Drabas, Even Oldridge, David A. Bader, Rachel Allen
Venue: KDD
Year: 2020

The lines between data science (DS), machine learning (ML), deep learning (DL), and data mining continue to be blurred and removed. This is great as it ushers in vast amounts of capabilities, but it brings increased complexity and a vast number of tools/techniques. It's not uncommon for DL engineers to use one set of tools for data extraction/cleaning and then pivot to another library for training their models. After training and inference, it's common to then move data yet again by another set of tools for post-processing. The RAPIDS suite of open source libraries not only provides a method to execute and accelerate these tasks using GPUs with familiar APIs, but it also provides interoperability with the broader open source community and DL tools while removing unnecessary serializations that slow down workflows. GPUs provide massive parallelization that DL has leveraged for some time, and RAPIDS provides the missing pieces that extend this computing power to more traditional yet important DS and ML tasks (e.g., ETL, modeling). Complete pipelines can be built that encompass everything, including ETL, feature engineering, ML/DL modeling, inference, and visualization, all while removing typical serialization costs and affording seamless interoperability between libraries. All experiments using RAPIDS can effortlessly be scheduled, logged and reviewed using existing public cloud options. Join our engineers and data scientists as they walk through a collection of DS and ML/DL engineering problems that show how RAPIDS running on Azure ML can be used for end-to-end, entirely GPU pipelines. This tutorial includes specifics on how to use RAPIDS for feature engineering, interoperability with common ML/DL packages, and creating GPU native visualizations using cuxfilter. The use cases presented here give attendees a hands-on approach to using RAPIDS components as part of a larger workflow, seamlessly integrating with other libraries (e.g., TensorFlow) and visualization packages.
Deep Graph Learning: Foundations, Advances and Applications
Authors: Yu Rong 0001, Tingyang Xu, Junzhou Huang, Wenbing Huang 0001, Hong Cheng 0001, Yao Ma 0001, Yiqi Wang 0001, Tyler Derr, Lingfei Wu 0001, Tengfei Ma 0001
Venue: KDD
Year: 2020

Many real data come in the form of non-grid objects, i.e. graphs, from social networks to molecules. Adaptation of deep learning from grid-alike data (e.g. images) to graphs has recently received unprecedented attention from both machine learning and data mining communities, leading to a new cross-domain field---Deep Graph Learning (DGL). Instead of painstaking feature engineering, DGL aims to learn informative representations of graphs in an end-to-end manner. It has exhibited remarkable success in various tasks, such as node/graph classification, link prediction, etc.
Off-policy Bandits with Deficient Support
Authors: Noveen Sachdeva, Yi Su, Thorsten Joachims
Venue: KDD
Year: 2020

Learning effective contextual-bandit policies from past actions of a deployed system is highly desirable in many settings (e.g. voice assistants, recommendation, search), since it enables the reuse of large amounts of log data. State-of-the-art methods for such off-policy learning, however, are based on inverse propensity score (IPS) weighting. A key theoretical requirement of IPS weighting is that the policy that logged the data has "full support", which typically translates into requiring non-zero probability for any action in any context. Unfortunately, many real-world systems produce support deficient data, especially when the action space is large, and we show how existing methods can fail catastrophically. To overcome this gap between theory and applications, we identify three approaches that provide various guarantees for IPS-based learning despite the inherent limitations of support-deficient data: restricting the action space, reward extrapolation, and restricting the policy space. We systematically analyze the statistical and computational properties of these three approaches, and we empirically evaluate their effectiveness. In addition to providing the first systematic analysis of support-deficiency in contextual-bandit learning, we conclude with recommendations that provide practical guidance.