OpenRaiser/Intern-Atlas huggingface dataset:
An Unsupervised Learning Framework Combined with Heuristics for the Maximum Minimal Cut Problem
Authors: Huaiyuan Liu, Xianzhang Liu, Donghua Yang, Hongzhi Wang 0001, Yingchi Long, Mengtong Ji, Dongjing Miao, Zhiyu Liang
Venue: KDD
Year: 2024

The Maximum Minimal Cut Problem (MMCP), a NP-hard combinatorial optimization (CO) problem, has not received much attention due to the demanding and challenging bi-connectivity constraint. Moreover, as a CO problem, it is also a daunting task for machine learning, especially without labeled instances. To deal with these problems, this work proposes an unsupervised learning framework combined with heuristics for MMCP that can provide valid and high-quality solutions. As far as we know, this is the first work that explores machine learning and heuristics to solve MMCP. The unsupervised solver is inspired by a relaxation-plus-rounding approach, the relaxed solution is parameterized by graph neural networks, and the cost and penalty of MMCP are explicitly written out, which can train the model end-to-end. A crucial observation is that each solution corresponds to at least one spanning tree. Based on this finding, a heuristic solver that implements tree transformations by adding vertices is utilized to repair and improve the solution quality of the unsupervised solver. Alternatively, the graph is simplified while guaranteeing solution consistency, which reduces the running time. We conduct extensive experiments to evaluate our framework and give a specific application. The results demonstrate the superiority of our method against two techniques designed.
Beyond Binary Preference: Leveraging Bayesian Approaches for Joint Optimization of Ranking and Calibration
Authors: Chang Liu 0078, Qiwei Wang, Wenqing Lin, Yue Ding 0001, Hongtao Lu 0001
Venue: KDD
Year: 2024

Predicting click-through rate (CTR) is a critical task in recommendation systems, where the models are optimized with pointwise loss to infer the probability of items being clicked. In industrial practice, applications also require ranking items based on these probabilities. Existing solutions primarily combine the ranking-based loss, i.e., pairwise and listwise loss, with CTR prediction. However, they can hardly calibrate or generalize well in CTR scenarios where the clicks reflect the binary preference. This is because the binary click feedback leads to a large number of ties, which renders high data sparsity. In this paper, we propose an effective data augmentation strategy, named Beyond Binary Preference (BBP) training framework, to address this problem. Our key idea is to break the ties by leveraging Bayesian approaches, where the beta distribution models click behavior as probability distributions in the training data that naturally break ties. Therefore, we can obtain an auxiliary training label that generates more comparable pairs and improves the ranking performance. Besides, BBP formulates ranking and calibration as a multi-task framework to optimize both objectives simultaneously. Through extensive offline experiments and online tests on various datasets, we demonstrate that BBP significantly outperforms state-of-the-art methods in both ranking and calibration capabilities, showcasing its effectiveness in addressing the limitations of existing methods. Our code is available at https://github.com/AlvinIsonomia/BBP.
GRAM: Generative Retrieval Augmented Matching of Data Schemas in the Context of Data Security
Authors: Xuanqing Liu, Runhui Wang, Yang Song, Luyang Kong
Venue: KDD
Year: 2024

Schema matching constitutes a pivotal phase in the data ingestion process for contemporary database systems. Its objective is to discern pairwise similarities between two sets of attributes, each associated with a distinct data table. This challenge emerges at the initial stages of data analytics, such as when incorporating a third-party table into existing databases to inform business insights. Given its significance in the realm of database systems, schema matching has been under investigation since the 2000s. This study revisits this foundational problem within the context of large language models. Adhering to increasingly stringent data security policies, our focus lies on the zero-shot and few-shot scenarios: the model should analyze only a minimal amount of customer data to execute the matching task, contrasting with the conventional approach of scrutinizing the entire data table. We emphasize that the zero-shot or few-shot assumption is imperative to safeguard the identity and privacy of customer data, even at the potential cost of accuracy. The capability to accurately match attributes under such stringent requirements distinguishes our work from previous literature in this domain.
Probabilistic Attention for Sequential Recommendation
Authors: Yuli Liu, Christian Walder, Lexing Xie, Yiqun Liu 0001
Venue: KDD
Year: 2024

Sequential Recommendation (SR) navigates users' dynamic preferences through modeling their historical interactions. The incorporation of the popular Transformer framework, which captures long relationships through pairwise dot products, has notably benefited SR. However, prevailing research in this domain faces three significant challenges: (i) Existing studies directly adopt the primary component of Transformer (i.e., the self-attention mechanism), without a clear explanation or tailored definition for its specific role in SR; (ii) The predominant focus on pairwise computations overlooks the global context or relative prevalence of item pairs within the overall sequence; (iii) Transformer primarily pursues relevance-dominated relationships, neglecting another essential objective in recommendation, i.e., diversity. In response, this work introduces a fresh perspective to elucidate the attention mechanism in SR. Here, attention is defined as dependency interactions among items, quantitatively determined under a global probabilistic model by observing the probabilities of corresponding item subsets. This viewpoint offers a precise and context-specific definition of attention, leading to the design of a distinctive attention mechanism tailored for SR. Specifically, we transmute the well-formulated global, repulsive interactions in Determinantal Point Processes (DPPs) to effectively model dependency interactions. Guided by the repulsive interactions, a theoretically and practically feasible DPP kernel is designed, enabling our attention mechanism to directly consider category/topic distribution for enhancing diversity. Consequently, the <u>P</u>robabilistic <u>Att</u>ention mechanism (PAtt) for sequential recommendation is developed. Experimental results demonstrate the excellent scalability and adaptability of our attention mechanism, which significantly improves recommendation performance in terms of both relevance and diversity.
Asymmetric Beta Loss for Evidence-Based Safe Semi-Supervised Multi-Label Learning
Authors: Hao-Zhe Liu, Ming-Kun Xie, Chen-Chen Zong, Sheng-Jun Huang
Venue: KDD
Year: 2024

The goal of semi-supervised multi-label learning (SSMLL) is to improve model performance by leveraging the information of unlabeled data. Recent studies usually adopt the pseudo-labeling strategy to tackle unlabeled data based on the assumption that labeled and unlabeled data share the same distribution. However, in realistic scenarios, unlabeled examples are often collected through cost-effective methods, inevitably introducing out-of-distribution (OOD) data, leading to a significant decline in model performance. In this paper, we propose a safe semi-supervised multi-label learning framework based on the theory of evidential deep learning (EDL), with the goal of achieving robust and effective unlabeled data exploitation. On one hand, we propose the asymmetric beta loss to not only compensate for the lack of robustness in common MLL losses, but also to solve the inherent positive-negative imbalance problem faced by the EDL losses in MLL. On the other hand, to construct a robust SSMLL framework, we adopt a dual-head structure to generate class probabilities and instance uncertainties. The former are used to generate pseudo-labels, while the latter are utilized to filter OOD examples. To avoid the need for threshold estimation, we develop a dual-measurement weighted loss function to safely perform unlabeled training. Extensive experiments on multiple benchmark datasets verify the effectiveness of the proposed method in both OOD detection and SSMLL tasks.
DAG: Deep Adaptive and Generative K-Free Community Detection on Attributed Graphs
Authors: Chang Liu 0078, Yuwen Yang, Yue Ding 0001, Hongtao Lu 0001, Wenqing Lin, Ziming Wu, Wendong Bi
Venue: KDD
Year: 2024

Community detection on attributed graphs with rich semantic and topological information offers great potential for real-world network analysis, especially user matching in online games. Graph Neural Networks (GNNs) have recently enabled Deep Graph Clustering (DGC) methods to learn cluster assignments from semantic and topological information. However, their success depends on the prior knowledge related to the number of communities K, which is unrealistic due to the high costs and privacy issues of acquisition. In this paper, we investigate the community detection problem without prior K, referred to as K-Free Community Detection problem. To address this problem, we propose a novel Deep Adaptive and Generative model~(DAG) for community detection without specifying the prior K. DAG consists of three key components, i.e., a node representation learning module with masked attribute reconstruction, a community affiliation readout module, and a community number search module with group sparsity. These components enable DAG to convert the process of non-differentiable grid search for the community number, i.e., a discrete hyperparameter in existing DGC methods, into a differentiable learning process. In such a way, DAG can simultaneously perform community detection and community number search end-to-end. To alleviate the cost of acquiring community labels in real-world applications, we design a new metric, EDGE, to evaluate community detection methods even when the labels are not feasible. Extensive offline experiments on five public datasets and a real-world online mobile game dataset demonstrate the superiority of our DAG over the existing state-of-the-art (SOTA) methods. DAG has a relative increase of 7.35% in teams in a Tencent online game compared with the best competitor.
Fast Query of Biharmonic Distance in Networks
Authors: Changan Liu, Ahad N. Zehmakan, Zhongzhi Zhang
Venue: KDD
Year: 2024

Thebiharmonic distance (BD) is a fundamental metric that measures the distance of two nodes in a graph. It has found applications in network coherence, machine learning, and computational graphics, among others. In spite of BD's importance, efficient algorithms for the exact computation or approximation of this metric on large graphs remain notably absent. In this work, we provide several algorithms to estimate BD, building on a novel formulation of this metric. These algorithms enjoy locality property (that is, they only read a small portion of the input graph) and at the same time possess provable performance guarantees. In particular, our main algorithms approximate the BD between any node pair with an arbitrarily small additive error ε in time O(1/ε2 poly(log n/ε)). Furthermore, we perform an extensive empirical study on several benchmark networks, validating the performance and accuracy of our algorithms.
Diffusion-Based Cloud-Edge-Device Collaborative Learning for Next POI Recommendations
Authors: Jing Long, Guanhua Ye, Tong Chen 0005, Yang Wang 0023, Meng Wang 0001, Hongzhi Yin
Venue: KDD
Year: 2024

The rapid expansion of Location-Based Social Networks (LBSNs) has highlighted the importance of effective next Point-of-Interest (POI) recommendations, which leverage historical check-in data to predict users' next POIs to visit. Traditional centralized deep neural networks (DNNs) offer impressive POI recommendation performance but face challenges due to privacy concerns and limited timeliness. In response, on-device POI recommendations have been introduced, utilizing federated learning (FL) and decentralized approaches to ensure privacy and recommendation timeliness. However, these methods often suffer from computational strain on devices and struggle to adapt to new users and regions. This paper introduces a novel collaborative learning framework, Diffusion-Based Cloud-Edge-Device Collaborative Learning for Next POI Recommendations (DCPR), leveraging the diffusion model known for its success across various domains. DCPR operates with a cloud-edge-device architecture to offer region-specific and highly personalized POI recommendations while reducing on-device computational burdens. DCPR minimizes on-device computational demands through a unique blend of global and local learning processes. Our evaluation with two real-world datasets demonstrates DCPR's superior performance in recommendation accuracy, efficiency, and adaptability to new users and regions, marking a significant step forward in on-device POI recommendation technology.
MISP: A Multimodal-based Intelligent Server Failure Prediction Model for Cloud Computing Systems
Authors: Xianting Lu, Yunong Wang, Yu Fu 0008, Qi Sun 0002, Xuhua Ma, Xudong Zheng, Cheng Zhuo
Venue: KDD
Year: 2024

Traditional server failure prediction methods predominantly rely on single-modality data such as system logs or system status curves. This reliance may lead to an incomplete understanding of system health and impending issues, proving inadequate for the complex and dynamic landscape of contemporary cloud computing environments. The potential of multimodal data to provide comprehensive insights is widely acknowledged, yet the lack of a holistic dataset and the challenges inherent in integrating features from both structured and unstructured data have impeded the exploration of multimodal-based server failure prediction. Addressing these challenges, this paper presents an industrial-scale, comprehensive dataset for server failure prediction, comprising nearly 80 types of structured and unstructured data sourced from real-world industrial cloud systems 1. Building on this resource, we introduce MISP, a model that leverages multimodal fusion techniques for server failure prediction. MISP transforms multimodal data into multi-dimensional sequences, extracts and encodes features both within and across the modalities, and ultimately computes the failure probability from the synthesized features. Experiments demonstrate that MISP significantly outperforms existing methods, enhancing prediction accuracy by approximately 25% over previous state-of-the-art approaches.
Integrating System State into Spatio Temporal Graph Neural Network for Microservice Workload Prediction
Authors: Yang Luo 0004, Mohan Gao, Zhemeng Yu, Haoyuan Ge, Xiaofeng Gao 0001, Tengwei Cai, Guihai Chen
Venue: KDD
Year: 2024

Microservice architecture has become a driving force in enhancing the modularity and scalability of web applications, as evidenced by the Alipay platform's operational success. However, a prevalent issue within such infrastructures is the suboptimal utilization of CPU resources due to inflexible resource allocation policies. This inefficiency necessitates the development of dynamic, accurate workload prediction methods to improve resource allocation. In response to this challenge, we present STAMP, a <u>S</u>patio <u>T</u>emporal Gr<u>a</u>ph Network for <u>M</u>icroservice Workload <u>P</u>rediction. STAMP is designed to comprehensively address the multifaceted interdependencies between microservices, the temporal variability of workloads, and the critical role of system state in resource utilization. Through a graph-based representation, STAMP effectively maps the intricate network of microservice interactions. It employs time series analysis to capture the dynamic nature of workload changes and integrates system state insights to enhance prediction accuracy. Our empirical analysis, using three distinct real-world datasets, establishes that STAMP exceeds baselines by achieving an average boost of 5.72% in prediction precision, as measured by RMSE. Upon deployment in Alipay's microservice environment, STAMP achieves a 33.10% reduction in resource consumption, significantly outperforming existing online methods. This research solidifies STAMP as a validated framework, offering meaningful contributions to the field of resource management in microservice architecture-based applications.
PolyFormer: Scalable Node-wise Filters via Polynomial Graph Transformer
Authors: Jiahong Ma, Mingguo He, Zhewei Wei
Venue: KDD
Year: 2024

Spectral Graph Neural Networks have demonstrated superior performance in graph representation learning. However, many current methods focus on employing shared polynomial coefficients for all nodes, i.e., learning node-unified filters, which limits the filters' flexibility for node-level tasks. The recent DSF attempts to overcome this limitation by learning node-wise coefficients based on positional encoding. However, the initialization and updating process of the positional encoding are burdensome, hindering scalability on large-scale graphs. In this work, we propose a scalable node-wise filter, PolyAttn. Leveraging the attention mechanism, PolyAttn can directly learn node-wise filters in an efficient manner, offering powerful representation capabilities. Building on PolyAttn, we introduce the whole model, named PolyFormer. In the lens of Graph Transformer models, PolyFormer, which calculates attention scores within nodes, shows great scalability. Moreover, the model captures spectral information, enhancing expressiveness while maintaining efficiency. With these advantages, PolyFormer offers a desirable balance between scalability and expressiveness for node-level tasks. Extensive experiments demonstrate that our proposed methods excel at learning arbitrary node-wise filters, showing superior performance on both homophilic and heterophilic graphs, and handling graphs containing up to 100 million nodes. The code is available at https://github.com/air029/PolyFormer.
Low Rank Multi-Dictionary Selection at Scale
Authors: Boya Ma, Maxwell McNeil, Abram Magner, Petko Bogdanov
Venue: KDD
Year: 2024

The sparse dictionary coding framework represents signals as a linear combination of a few predefined dictionary atoms. It has been employed for images, time series, graph signals and recently for 2-way (or 2D) spatio-temporal data employing jointly temporal and spatial dictionaries. Large and over-complete dictionaries enable high-quality models, but also pose scalability challenges which are exacerbated in multi-dictionary settings. Hence, an important problem that we address in this paper is: How to scale multi-dictionary coding for large dictionaries and datasets?We propose a multi-dictionary atom selection technique for low-rank sparse coding named LRMDS. To enable scalability to large dictionaries and datasets, it progressively selects groups of row-column atom pairs based on their alignment with the data and performs convex relaxation coding via the corresponding sub-dictionaries. We demonstrate both theoretically and experimentally that when the data has a low-rank encoding with a sparse subset of the atoms, LRMDS is able to select them with strong guarantees under mild assumptions. Furthermore, we demonstrate the scalability and quality of LRMDS in both synthetic and real-world datasets and for a range of coding dictionaries. It achieves 3 times to 10 times speed-up compared to baselines, while obtaining up to two orders of magnitude improvement in representation quality on some of the real world datasets given a fixed target number of atoms.
Handling Varied Objectives by Online Decision Making
Authors: Lanjihong Ma, Zhen-Yu Zhang, Yao-Xiang Ding 0001, Zhi-Hua Zhou
Venue: KDD
Year: 2024

Conventional machine learning typically assume a fixed learning objective throughout the learning process.However, for real-world tasks in open and dynamic environments, objectives can change frequently.For example, in autonomous driving, a car has several default modes, but a user's concern for speed and fuel consumption varies depending on road conditions and personal needs.We formulate this problem as learning with varied objectives (LVO), where the goal is to optimize a dynamic weighted combination of multiple sub-objectives by sequentially selecting actions that incur different losses on these sub-objectives.We propose the VaRons algorithm, which estimates the action-wise performance on each sub-objective and adaptively selects decisions according to the dynamic requirements on different sub-objectives.Further, we extend our approach to cases involving contextual representations and propose the Con-VaRons algorithm, assuming parameterized linear structure that links contextual features to the main objective.Both the VaRons and ConVaRons are provably minimax optimal with respect to the time horizon , with ConVaRons showing better dependency with the number of sub-objectives .Experiments on dynamic classifier and real-world cluster service allocation tasks validate the effectiveness of our methods and support our theoretical findings. CCS Concepts Computing methodologies Online learning settings.
FLAIM: AIM-based Synthetic Data Generation in the Federated Setting
Authors: Samuel Maddock, Graham Cormode, Carsten Maple
Venue: KDD
Year: 2024

Preserving individual privacy while enabling collaborative data sharing is crucial for organizations. Synthetic data generation is one solution, producing artificial data that mirrors the statistical properties of private data. While numerous techniques have been devised under differential privacy, they predominantly assume data is centralized. However, data is often distributed across multiple clients in a federated manner. In this work, we initiate the study of federated synthetic tabular data generation. Building upon a SOTA central method known as AIM, we present DistAIM and FLAIM. We first show that it is straightforward to distribute AIM, extending a recent approach based on secure multi-party computation which necessitates additional overhead, making it less suited to federated scenarios. We then demonstrate that naively federating AIM can lead to substantial degradation in utility under the presence of heterogeneity. To mitigate both issues, we propose an augmented FLAIM approach that maintains a private proxy of heterogeneity. We simulate our methods across a range of benchmark datasets under different degrees of heterogeneity and show we can improve utility while reducing overhead.
Symbolic Regression: A Pathway to Interpretability Towards Automated Scientific Discovery
Authors: Nour Makke, Sanjay Chawla
Venue: KDD
Year: 2024

Symbolic regression is a machine learning technique employed for learning mathematical equations directly from data. Mathematical equations capture both functional and causal relationships in the data. In addition, they are simple, compact, generalizable, and interpretable models, making them the best candidates for i) learning inherently transparent models and ii) boosting scientific discovery. Symbolic regression has received a growing interest since the last decade and is tackled using different approaches in supervised and unsupervised deep learning, thanks to the enormous progress achieved in deep learning in the last twenty years. Symbolic regression remains underestimated in conference coverage as a primary form of interpretable AI and a potential candidate for automating scientific discovery. This tutorial overviews symbolic regression: problem definition, approaches, and key limitations, discusses why physical sciences are beneficial to symbolic regression, and explores possible future directions in this research area.
A Uniformly Bounded Correlation Function for Spatial Point Patterns
Authors: Evgenia Martynova, Johannes Textor
Venue: KDD
Year: 2024

Contains fulltext : 312219.pdf (Publisher’s version ) (Open Access)