OpenRaiser/Intern-Atlas huggingface dataset:
Preemptive Detection of Fake Accounts on Social Networks via Multi-Class Preferential Attachment Classifiers
Authors: Adam Breuer, Nazanin Khosravani Tehrani, Michael Tingley, Bradford Cottel
Venue: KDD
Year: 2023

In this paper, we describe a new algorithm called Preferential Attac hment k-class Classifier (PreAttacK) for detecting fake accounts in a social network. Recently, several algorithms have obtained high accuracy on this problem. However, they have done so by relying on information about fake accounts' friendships or the content they share with others-the very things we seek to prevent.
Privacy Matters: Vertical Federated Linear Contextual Bandits for Privacy Protected Recommendation
Authors: Zeyu Cao, Zhipeng Liang, Bingzhe Wu, Shu Zhang 0013, Hangyu Li 0002, Ouyang Wen, Yu Rong 0001, Peilin Zhao
Venue: KDD
Year: 2023

Recent awareness of privacy protection and compliance requirement resulted in a controversial view of recommendation system due to personal data usage. Therefore, privacy-protected recommendation emerges as a novel research direction. In this paper, we first formulate this problem as a vertical federated learning problem, i.e., features are vertically distributed over different departments. We study a contextual bandit learning problem for recommendation in the vertical federated setting. To this end, we carefully design a customized encryption scheme named orthogonal matrix-based mask mechanism (O3M). O3M mechanism, a tailored component for contextual bandits by carefully exploiting their shared structure, can ensure privacy protection while avoiding expensive conventional cryptographic techniques. We further apply the mechanism to two commonly-used bandit algorithms, LinUCB and LinTS, and instantiate two practical protocols for online recommendation. The proposed protocols can perfectly recover the service quality of centralized bandit algorithms while achieving a satisfactory runtime efficiency, which is theoretically proved and analysed in this paper. By conducting extensive experiments on both synthetic and real-world datasets, we show the superiority of the proposed method in terms of privacy protection and recommendation performance.
When to Pre-Train Graph Neural Networks? From Data Generation Perspective!
Authors: Yuxuan Cao, Jiarong Xu, Carl Yang 0001, Jiaan Wang, Yunchao Zhang, Chunping Wang 0001, Lei Chen 0082, Yang Yang 0009
Venue: KDD
Year: 2023

In recent years, graph pre-training has gained significant attention, focusing on acquiring transferable knowledge from unlabeled graph data to improve downstream performance. Despite these recent endeavors, the problem of negative transfer remains a major concern when utilizing graph pre-trained models to downstream tasks. Previous studies made great efforts on the issue of <i>what to pre-train</i> and <i>how to pre-train</i> by designing a variety of graph pre-training and fine-tuning strategies. However, there are cases where even the most advanced "pre-train and fine-tune" paradigms fail to yield distinct benefits. This paper introduces a generic framework W2PGNN to answer the crucial question of <i>when to pre-train</i> (<i>i.e</i>., in what situations could we take advantage of graph pre-training) before performing effortful pre-training or fine-tuning. We start from a new perspective to explore the complex generative mechanisms from the pre-training data to downstream data. In particular, W2PGNN first fits the pre-training data into graphon bases, each element of graphon basis (<i>i.e</i>., a graphon) identifies a fundamental transferable pattern shared by a collection of pre-training graphs. All convex combinations of graphon bases give rise to a generator space, from which graphs generated form the solution space for those downstream data that can benefit from pre-training. In this manner, the feasibility of pre-training can be quantified as the generation probability of the downstream data from any generator in the generator space. W2PGNN offers three broad applications: providing the application scope of graph pre-trained models, quantifying the feasibility of pre-training, and assistance in selecting pre-training data to enhance downstream performance. We provide a theoretically sound solution for the first application and extensive empirical justifications for the latter two applications.
SURE: Robust, Explainable, and Fair Classification without Sensitive Attributes
Authors: Deepayan Chakrabarti
Venue: KDD
Year: 2023

A classifier that is accurate on average may still underperform for "sensitive" subsets of people. Such subsets could be based on race, gender, age, etc. The goal of a fair classifier is to perform well for all sensitive subsets. But often, the sensitive subsets are not known a priori. So we may want the classifier to perform well on all subsets that are likely to be sensitive. We propose an iterative algorithm called SURE for this problem. In each iteration, SURE identifies high-risk zones in feature space where the risk of unfair classification is statistically significant. By changing the loss function's weights for points from these zones, SURE builds a fair classifier. The emphasis on statistical significance makes SURE robust to noise. The high-risk zones are intuitive and interpretable. Every step of our method is explainable in terms of significance tests. Finally, SURE is fast and parameter-free. Experiments on both simulated and real-world datasets show that SURE is competitive with the state-of-the-art.
Taming the Domain Shift in Multi-source Learning for Energy Disaggregation
Authors: Xiaomin Chang, Wei Li 0058, Yunchuan Shi, Albert Y. Zomaya
Venue: KDD
Year: 2023

Non-intrusive load monitoring (NILM) is a cost-effective energy disaggregation means to estimate the energy consumption of individual appliances from a central load reading. Learning-based methods are the new trends in NILM implementations but require large labeled data to work properly at end-user premises. We first formulate an unsupervised multi-source domain adaptation problem to address this challenge by leveraging rich public datasets for building the NILM model. Then, we prove a new generalization bound for the target domain under multi-source settings. A hybrid loss-driven multi-source domain adversarial network (HLD-MDAN) is developed by approximating and optimizing the bound to tackle the domain shift between source and target domains. We conduct extensive experiments on three real-world residential energy datasets to evaluate the effectiveness of HLD-MDAN, showing that it is superior to other methods in single-source and multi-source learning scenarios.
Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time
Authors: Yixin Chen 0007, Alan Kuhnle
Venue: KDD
Year: 2023

In this work, we study the problem of finding the maximum value of a non-negative submodular function subject to a limit on the number of items selected, a ubiquitous problem that appears in many applications, such as data summarization and nonlinear regression. We provide the first deterministic, linear-time approximation algorithms for this problem that do not assume the objective is monotone. We present three deterministic, linear-time algorithms: a single-pass streaming algorithm with a ratio of 23.313 + ε, which is the first linear-time streaming algorithm; a simpler deterministic linear-time algorithm with a ratio of 11.657; and a (4 + O(ε))-approximation algorithm. Finally, we present a deterministic algorithm that obtains ratio of e + ε in O_ε (n log(n)) time, close to the best known expected ratio of e - 0.121 in polynomial time.
Graph-Based Model-Agnostic Data Subsampling for Recommendation Systems
Authors: Xiaohui Chen, Jiankai Sun, Taiqing Wang, Ruocheng Guo, Li-Ping Liu 0001, Aonan Zhang
Venue: KDD
Year: 2023

Data subsampling is widely used to speed up the training of large-scale recommendation systems. Most subsampling methods are model-based and often require a pre-trained pilot model to measure data importance via e.g. sample hardness. However, when the pilot model is misspecified, model-based subsampling methods deteriorate. Since model misspecification is persistent in real recommendation systems, we instead propose model-agnostic data subsampling methods by only exploring input data structure represented by graphs. Specifically, we study the topology of the user-item graph to estimate the importance of each user-item interaction (an edge in the user-item graph) via graph conductance, followed by a propagation step on the network to smooth out the estimated importance value. Since our proposed method is model-agnostic, we can marry the merits of both model-agnostic and model-based subsampling methods. Empirically, we show that combing the two consistently improves over any single method on the used datasets. Experimental results on KuaiRec and MIND datasets demonstrate that our proposed methods achieve superior results compared to baseline approaches.
Open-Set Semi-Supervised Text Classification with Latent Outlier Softening
Authors: Junfan Chen 0001, Richong Zhang, Junchi Chen, Chunming Hu, Yongyi Mao
Venue: KDD
Year: 2023

Semi-supervised text classification (STC) has been extensively researched and reduces human annotation. However, existing research assuming that unlabeled data only contains in-distribution texts is unrealistic. This paper extends STC to a more practical Open-set Semi-supervised Text Classification (OSTC) setting, which assumes that the unlabeled data contains out-of-distribution (OOD) texts. The main challenge in OSTC is the false positive inference problem caused by inadvertently including OOD texts during training. To address the problem, we first develop baseline models using outlier detectors for hard OOD-data filtering in a pipeline procedure. Furthermore, we propose a Latent Outlier Softening (LOS) framework that integrates semi-supervised training and outlier detection within probabilistic latent variable modeling. LOS softens the OOD impacts by the Expectation-Maximization (EM) algorithm and weighted entropy maximization. Experiments on 3 created datasets show that LOS significantly outperforms baselines.
Foundations and Applications in Large-scale AI Models: Pre-training, Fine-tuning, and Prompt-based Learning
Authors: Derek Zhiyuan Cheng, Dhaval Patel 0002, Linsey Pang, Sameep Mehta, Kexin Xie, Ed H. Chi, Wei Liu 0007, Nitesh V. Chawla, James Bailey 0001
Venue: KDD
Year: 2023

Deep learning techniques have advanced rapidly in recent years, leading to significant progress in pre-trained and fine-tuned large-scale AI models. For example, in the natural language processing domain, the traditional "pre-train, fine-tune" paradigm is shifting towards the "pre-train, prompt, and predict" paradigm, which has achieved great success on many tasks across different application domains such as ChatGPT/BARD for Conversational AI and P5 for a unified recommendation system. Moreover, there has been a growing interest in models that combine vision and language modalities (vision-language models) which are applied to tasks like Visual Captioning/Generation. Considering the recent technological revolution, it is essential to emphasize these paradigm shifts and highlight the paradigms with the potential to solve different tasks. We thus provide a platform for academic and industrial researchers to showcase their latest work, share research ideas, discuss various challenges, and identify areas where further research is needed in pre-training, fine-tuning, and prompt-learning methods for large-scale AI models. We foster the development of a strong research community focused on solving challenges related to large-scale AI models, providing superior and impactful strategies that can change people's lives in the future.
Evolve Path Tracer: Early Detection of Malicious Addresses in Cryptocurrency
Authors: Ling Cheng 0002, Feida Zhu 0001, Yong Wang 0021, Ruicheng Liang, Huiwen Liu
Venue: KDD
Year: 2023

With the boom of cryptocurrency and its concomitant financial risk concerns, detecting fraudulent behaviors and associated malicious addresses has been drawing significant research effort. Most existing studies, however, rely on the full history features or full-fledged address transaction networks, both of which are unavailable in the problem of early malicious address detection and therefore failing them for the task. To detect fraudulent behaviors of malicious addresses in the early stage, we present Evolve Path Tracer, which consists of Evolve Path Encoder LSTM, Evolve Path Graph GCN, and Hierarchical Survival Predictor. Specifically, in addition to the general address features, we propose Asset Transfer Paths and corresponding path graphs to characterize early transaction patterns. Furthermore, since transaction patterns change rapidly in the early stage, we propose Evolve Path Encoder LSTM and Evolve Path Graph GCN to encode asset transfer path and path graph under an evolving structure setting. Hierarchical Survival Predictor then predicts addresses' labels with high scalability and efficiency. We investigate the effectiveness and generalizability of Evolve Path Tracer on three real-world malicious address datasets. Our experimental results demonstrate that Evolve Path Tracer outperforms the state-of-the-art methods. Extensive scalability experiments demonstrate the model's adaptivity under a dynamic prediction setting.
Reducing Exposure to Harmful Content via Graph Rewiring
Authors: Corinna Coupette, Stefan Neumann 0003, Aristides Gionis
Venue: KDD
Year: 2023

Most media content consumed today is provided by digital platforms that aggregate input from diverse sources, where access to information is mediated by recommendation algorithms. One principal challenge in this context is dealing with content that is considered harmful. Striking a balance between competing stakeholder interests, rather than block harmful content altogether, one approach is to minimize the exposure to such content that is induced specifically by algorithmic recommendations. Hence, modeling media items and recommendations as a directed graph, we study the problem of reducing the exposure to harmful content via edge rewiring. We formalize this problem using absorbing random walks, and prove that it is NP-hard and NP-hard to approximate to within an additive error, while under realistic assumptions, the greedy method yields a (1-1/e)-approximation. Thus, we introduce Gamine, a fast greedy algorithm that can reduce the exposure to harmful content with or without quality constraints on recommendations. By performing just 100 rewirings on YouTube graphs with several hundred thousand edges, Gamine reduces the initial exposure by 50%, while ensuring that its recommendations are at most 5% less relevant than the original recommendations. Through extensive experiments on synthetic data and real-world data from video recommendation and news feed applications, we confirm the effectiveness, robustness, and efficiency of Gamine in practice.
3rd Workshop on Online and Adaptive Recommender Systems (OARS)
Authors: Xiquan Cui, Vachik S. Dave, Yi Su 0008, Khalifeh Al Jadda, Srijan Kumar, Julian J. McAuley, Tao Ye 0001, Stephen D. Guo, Chip Huyen
Venue: KDD
Year: 2023

Recommender systems (RecSys) play important roles in helping users navigate, discover, and consume large and highly dynamic information. Today, many RecSys solutions deployed in the real world rely on categorical user-profiles and/or pre-calculated recommendation actions that stay static during a user session. However, recent trends suggest that RecSys need to model user intent in real time and constantly adapt to meet user needs at the moment or change user behavior in situ. There are three primary drivers for this emerging need of online adaptation. First, in order to meet the increasing demand for a better personalized experience, the personalization dimensions and space will grow larger and larger. It would not be feasible to pre-compute recommended actions for all personalization scenarios beyond a certain scale. Second, in many settings the system does not have user prior history to leverage. Estimating user intent in real time is the only feasible way to personalize. As various consumer privacy laws tighten, it is foreseeable that many businesses will reduce their reliance on static user profiles. Therefore, it makes the modeling of user intent in real time an important research topic. Third, a user's intent often changes within a session and between sessions, and user behavior could shift significantly during dramatic events. A RecSys should adapt in real time to meet user needs and be robust against distribution shifts. The online and adaptive recommender systems (OARS) workshop offers a focused discussion of the study and application of OARS, and will bring together an interdisciplinary community of researchers and practitioners from both industry and academia. KDD, as the premier data science conference, is an ideal venue to gather leaders in the field to further research into OARS and promote its adoption. This workshop is complementary to several sessions of the main conference (e.g., recommendation, reinforcement learning, etc.) and brings them together using a practical and focused application.
Below the Surface: Summarizing Event Sequences with Generalized Sequential Patterns
Authors: Joscha Cüppers, Jilles Vreeken
Venue: KDD
Year: 2023

We study the problem of succinctly summarizing a database of event sequences in terms of generalized sequential patterns. That is, we are interested in patterns that are not exclusively defined over observed surface-level events, as is usual, but rather may additionally include generalized events that can match a set of events. To avoid spurious and redundant results we define the problem in terms of the Minimum Description Length principle, by which we are after that set of patterns and generalizations that together best compress the data without loss. The resulting optimization problem does not lend itself for exact search, which is why we propose the heuristic Flock algorithm to efficiently find high-quality models in practice. Extensive experiments on synthetic and real-world data show that Flock results in compact and easily interpretable models that accurately recover the ground truth, including rare instances of generalized patterns. Additionally Flock recovers how generalized events within patterns depend on each other, and overall provides clearer insight into the data-generating process than using state of the art algorithms that only consider surface-level patterns.
Conditional Neural ODE Processes for Individual Disease Progression Forecasting: A Case Study on COVID-19
Authors: Ting Dang, Jing Han 0010, Tong Xia, Erika Bondareva, Chloë Siegele-Brown, Jagmohan Chauhan, Andreas Grammenos, Dimitris Spathis, Pietro Cicuta, Cecilia Mascolo
Venue: KDD
Year: 2023

Time series forecasting, as one of the fundamental machine learning areas, has attracted tremendous attentions over recent years. The solutions have evolved from statistical machine learning (ML) methods to deep learning techniques. One emerging sub-field of time series forecasting is individual disease progression forecasting, e.g., predicting individuals' disease development over a few days (e.g., deteriorating trends, recovery speed) based on few past observations. Despite the promises in the existing ML techniques, a variety of unique challenges emerge for disease progression forecasting, such as irregularly-sampled time series, data sparsity, and individual heterogeneity in disease progression. To tackle these challenges, we propose novel Conditional Neural Ordinary Differential Equations Processes (CNDPs), and validate it in a COVID-19 disease progression forecasting task using audio data. CNDPs allow for irregularly-sampled time series modelling, enable accurate forecasting with sparse past observations, and achieve individual-level progression forecasting. CNDPs show strong performance with an Unweighted Average Recall (UAR) of 78.1%, outperforming a variety of commonly used Recurrent Neural Networks based models. With the proposed label-enhancing mechanism (i.e., including the initial health status as input) and the customised individual-level loss, CNDPs further boost the performance reaching a UAR of 93.6%. Additional analysis also reveals the model's capability in tracking individual-specific recovery trend, implying the potential usage of the model for remote disease progression monitoring. In general, CNDPs pave new pathways for time series forecasting, and provide considerable advantages for disease progression monitoring.
Generalized Matrix Local Low Rank Representation by Random Projection and Submatrix Propagation
Authors: Pengtao Dang, Haiqi Zhu, Tingbo Guo, Changlin Wan, Tong Zhao 0002, Paul Salama, Yijie Wang, Sha Cao, Chi Zhang 0021
Venue: KDD
Year: 2023

Matrix low rank approximation is an effective method to reduce or eliminate the statistical redundancy of its components. Compared with the traditional global low rank methods such as singular value decomposition (SVD), local low rank approximation methods are more advantageous to uncover interpretable data structures when clear duality exists between the rows and columns of the matrix. Local low rank approximation is equivalent to low rank submatrix detection. Unfortunately, existing local low rank approximation methods can detect only submatrices of specific mean structure, which may miss a substantial amount of true and interesting patterns. In this work, we develop a novel matrix computational framework called RPSP (Random Probing based submatrix Propagation) that provides an effective solution for the general matrix local low rank representation problem. RPSP detects local low rank patterns that grow from small submatrices of low rank property, which are determined by a random projection approach. RPSP is supported by theories of random projection. Experiments on synthetic data demonstrate that RPSP outperforms all state-of-the-art methods, with the capacity to robustly and correctly identify the low rank matrices when the pattern has a similar mean as the background, background noise is heteroscedastic and multiple patterns present in the data. On real-world datasets, RPSP also demonstrates its effectiveness in identifying interpretable local low rank matrices.
Modelling Delayed Redemption with Importance Sampling and Pre-Redemption Engagement
Authors: Samik Datta, Anshuman Mourya, Anirban Majumder, Vineet Chaoji
Venue: KDD
Year: 2023

Rewards-based programs are popular within e-commerce online stores, with the goal of providing serendipitous incentives to delight customers. These rewards (or incentives) could be in the form of cashback, free-shipping or discount coupons on purchases within specific categories. The success of such programs relies on their ability to identify relevant rewards for customers, from a wide variety of incentives available on the online store. Estimating the likelihood of a customer redeeming an incentive is challenging due to 1) data sparsity: relatively rare occurrence of coupon redemptions as compared to issuances, and 2) delayed feedback: customers taking time to redeem, resulting in inaccurate model refresh, compounded by data drift due to new customers and coupons.