Label distribution learning (LDL) has large practical application potentials due to its superiority in dealing with ambiguous label information. Most existing LDL methods are designed in a closed environment, wherein all the elements, e.g., feature and label space, are fixed. Nevertheless, in reality, data are dynamically acquired in the open environment, wherein the feature space can accumulate over time and the label space can be further enriched and refined accordingly with the accumulated feature space. Conducting LDL for such simultaneous augmentation of feature and label is crucial but rarely studied, particularly when the labeled samples with full observations are limited. In this paper, we propose a novel Incremental Label Distribution Learning (ILDL) method to tackle this brand new LDL problem by continuously transiting discriminative information from the previous model to the current one. Concretely, a prior compensation regularization is designed for such discriminative information transitivity. In this manner, the current model has the capacity to reuse the previous model to guide its own training. Furthermore, we present the theoretical analyses about the generalization bound, which provides guarantees for model inheritance. Comprehensive experimental studies validate the effectiveness of our proposal.
论文检索
输入标题、作者或关键词，从 844 篇学术成果中精准定位
Gradient Boosted Decision Trees (GBDTs) are classical machine learning algorithms widely employed in recommendation systems, database queries, etc. Due to the extensive memory access involved in histogram-based GBDT training methods, high-bandwidth GPUs have been widely adopted to accelerate the training. However, when handling millions of feature data, it requires significant memory to store the training data and histograms, posing challenges for training on limited GPU memories. In this paper, we develop a GPU-based GBDT framework named ScalaGBM, aiming to accelerate high-dimensional data training with less memory usage. We first employ a CSR-like data format and CSR-based histogram construction to reduce the memory occupation of the training data. Then, we reorganize the training workflow with a double buffer structure to reduce the overall memory consumption for the histogram. Finally, we develop multi-dimensional parallel histogram construction and global optimal split point reduction to speed up the training process. Experimental results demonstrate that ScalaGBM handles real-world datasets with over 100 million instances of 50 million features with a single commercial GPU while existing GBDT frameworks all run into out-of-memory errors. Meanwhile, ScalaGBM achieves a maximum speedup of 39× over state-of-the-art GBDT counterparts without sacrificing the training quality. The code is available at https://github.com/Xtra-Computing/thundergbm.
Estimating brain effective connectivity (EC) from functional magnetic resonance imaging (fMRI) data can aid in comprehending the neural mechanisms underlying human behavior and cognition, providing a foundation for disease diagnosis. However, current spatiotemporal attention modules handle temporal and spatial attention separately, extracting temporal and spatial features either sequentially or in parallel. These approach overlooks the inherent spatiotemporal correlations present in real world fMRI data. Additionally, the presence of noise in fMRI data further limits the performance of existing methods. In this paper, we propose a novel brain effective connectivity estimation method based on Fourier spatiotemporal attention (FSTA-EC), which combines Fourier attention and spatiotemporal attention to simultaneously capture inter-series (spatial) dynamics and intra-series (temporal) dependencies from high-noise fMRI data. Specifically, Fourier attention is designed to convert the high-noise fMRI data to frequency domain, and map the denoised fMRI data back to physical domain, and spatiotemporal attention is crafted to simultaneously learn spatiotemporal dynamics. Furthermore, through a series of proofs, we demonstrate that incorporating learnable filters into fast Fourier transform and inverse fast Fourier transform processes is mathematically equivalent to performing cyclic convolution. The experimental results on simulated and real-resting-state fMRI datasets demonstrate that the proposed method exhibits superior performance when compared to state-of-the-art methods. The code is available at https://github.com/XiongWenXww/FSTA.
Spatio-temporal prediction focuses on jointly modeling spatial correlations and temporal evolution and has a wide range of applications. Due to the heterogeneity of spatio-temporal data, accurate prediction relies on effectively integrating topological structures and sequential patterns. Although recurrent graph learning methods excel at capturing dynamic graph patterns, explicitly inferring future snapshots from historical dynamic graphs remains a significant challenge. Recently, prompt-based graph learning has shown the potential to improve future snapshot inference by leveraging node or task-specific prompts. However, these methods fail to fully capture edge information resulting in incomplete and less accurate representations of future snapshot structures. To bridge this gap, we propose ProST, a framework that Prompts future snapshots on dynamic graphs for Spatio-Temporal prediction, which leverages dynamic graph pre-training to generate a premise graph containing historical graph information and then employs prompts on the premise graph to infer explicit future snapshots. Specifically, this framework comprises three steps: Firstly, dynamic graph pre-training is performed using multi-granularity evolution graph convolution to obtain the premise graph with both local and global features of dynamic graphs. Secondly, prompt subgraphs are used to prompt node pairs and edge features within the premise graph. The subgraph prompt aggregation mechanism propagates this information to generate future snapshots. Finally, we freeze the parameters of the pre-trained model and update the subgraph prompt parameters using meta-learning to adapt to downstream spatio-temporal prediction tasks. Extensive experiments on real-world datasets validate that ProST achieves state-of-the-art performance.
Learning low-dimensional semantic representations in diffusion models (DMs) is an open task, since in standard DMs, the dimensions of its intermediate latents are the same as that of the observations and thus are unable to represent low-dimensional semantics. Existing methods address this task either by encoding observations into semantics which makes it difficult to generate samples without observations, or by synthesizing the U-Net's layers of pre-trained DMs into low-dimensional semantics, which is mainly used for downstream tasks rather than using semantics to facilitate the training process. Further, those generated static representations might not be aligned with dynamic timestep-wise intermediate latents. This work introduces a Progressive self-encoded Diffusion model (ProgDiffusion), which simultaneously learns semantic representations and reconstructs observations, does efficient unconditional generation, and produces progressively structured semantic representations. These benefits are gained by a novel self-encoder mechanism which takes the U-Net's upsampling features, intermediate latent and the denoising timestep as conditions to generate time-specific semantic representations, differing from existing work of conditioning on observations only. As a result, the learned intermediate latents are dynamic and mapped to a series of semantic representations that capture their gradual changes. Notably, our proposed encoder operates independently of the observations, making it feasible for unconditional generation as observations are not required. To evaluate ProgDiffusion, we design tasks to visualise the learned progressive semantic representations, in addition to other common tasks, which validate the effectiveness of ProgDiffusion against the state-of-the-art. The code is available at https://github.com/amasawa/ProgDiffusion.
Federated Learning (FL) enables multiple devices to collaboratively train a shared model while preserving data privacy. Most existing research assumes that all participating devices have sufficient resources to support the training process. However, the high memory requirements of model training present a significant challenge to deploying FL on resource-constrained devices in practical scenarios. To this end, this paper presents ProFL, a new framework that effectively addresses the memory constraints in FL. Rather than updating the full model during local training, ProFL partitions the model into blocks based on its original architecture and trains each block in a progressive fashion. It first trains the front blocks and safely freezes them after convergence. Training of the next block is then triggered. This process progressively grows the model to be trained until the training of the full model is completed. In this way, the peak memory footprint is effectively reduced for feasible deployment on heterogeneous devices. In order to preserve the feature representation of each block, the training process is divided into two stages: model shrinking and model growing. During the model shrinking stage, we meticulously design corresponding output modules to assist each block in learning the expected feature representation and obtain the initialization model parameters. Subsequently, the obtained output modules and initialization model parameters are utilized in the corresponding model growing stage, which progressively trains the full model. Additionally, a novel metric from the scalar perspective is proposed to assess the learning status of each block, enabling us to securely freeze it after convergence and initiate the training of the next one. Finally, we theoretically prove the convergence of ProFL and conduct extensive experiments on representative models and datasets to evaluate its effectiveness. The results demonstrate that ProFL effectively reduces the peak memory footprint by up to 57.4% and improves model accuracy by up to 82.4%.
Treatment responders are individuals whose outcomes would change from negative to positive if treated, and learning a classifier to predict responders would help causal decision-making in real applications. Although many treatment effect estimation methods have been proposed to identify treatment responders, there are fundamental differences between treatment effect estimation and treatment responder classification, including: (1) accurate causal effect estimation is not necessary for optimal intervention decisions; (2) methods for accurate causal effect estimation do not directly optimize classification loss; (3) treatment responder classification requires identifying joint potential outcomes, while treatment effect estimation focuses on marginal distributions. To fill this gap, we tackle the treatment responder classification problem without assuming monotonicity. We derive sharp bounds of the probability that an individual is a responder and determine a sharp upper bound on the weighted classification risk to measure the worst classification performance. Based on these findings, we further propose a Classifying Treatment Responder Learning (CTRL) algorithm to accurately identify the treatment responders, and theoretically demonstrate the superiority of jointly learning over two-stage learning. Extensive experiments on semi-synthetic and real-world datasets show that our method better predicts treatment responders and adaptively trades off false-positives and false-negatives with varying weight coefficients.
Network Intrusion Detection (NID) remains a key area of research within the information security community, while also being relevant to Machine Learning (ML) practitioners. The latter generally aim to detect attacks using network features, which have been extracted from raw network data typically using dimensionality reduction methods, such as principal component analysis (PCA). However, PCA is not able to assess the relevance of features for the task at hand. Consequently, the features available are of varying quality, with some being entirely non-informative. From this, two major drawbacks arise. Firstly, trained and deployed models have to process large amounts of unnecessary data, therefore draining potentially costly resources. Secondly, the noise caused by the presence of irrelevant features can, in some cases, impede a model's ability to detect an attack. In order to deal with these challenges, we present Feature Selection for Network Intrusion Detection (FSNID) a novel information-theoretic method that facilitates the exclusion of non-informative features when detecting network intrusions. The proposed method is based on function approximation using a neural network, which enables a version of our approach that incorporates a recurrent layer. Consequently, this version uniquely enables the integration of temporal dependencies. Through an extensive set of experiments, we demonstrate that the proposed method selects a significantly reduced feature set, while maintaining NID performance. Code available at https://github.com/c-s-westphal/FSNID.
Federated Learning (FL), as a mainstream privacy-preserving machine learning paradigm, offers promising solutions for privacy-critical domains such as healthcare and finance. Although extensive efforts have been dedicated from both academia and industry to improve the vanilla FL, little work focuses on the data pricing mechanism. In contrast to the straightforward in-training and post-training pricing techniques, we study a more difficult problem of pre-training pricing without direct information from the learning process. We propose FLMarket that integrates a two-stage pricing mechanism with a security protocol to address the utility-privacy conflict. Through comprehensive experiments, we show that the client selection according to FLMarket can achieve more than 10% higher accuracy in subsequent FL training compared to state-of-the-art methods. In addition, it outperforms the in-training baseline with more than 2% accuracy increase and 3× run-time speedup.
Causal effect estimation (CEE) provides a crucial tool for predicting the unobserved counterfactual outcome for an entity. As CEE relaxes the requirement for "perfect'' counterfactual samples (e.g., patients with identical attributes and only differ in treatments received) that are impractical to obtain and can instead operate on observational data, it is usually used in high-stake domains like medical treatment effect prediction. Nevertheless, in those high-stake domains, gathering a decently sized, fully labelled observational dataset remains challenging due to hurdles associated with costs, ethics, expertise and time needed, etc., of which medical treatment surveys are a typical example. Consequently, if the training dataset is small in scale, low generalization risks can hardly be achieved on any CEE algorithms. Unlike existing CEE methods that assume the constant availability of a dataset with abundant samples, in this paper, we study a more realistic CEE setting where the labelled data samples are scarce at the beginning, while more can be gradually acquired over the course of training -- assuredly under a limited budget considering their expensive nature. Then, the problem naturally comes down to actively selecting the best possible samples to be labelled, e.g., identifying the next subset of patients to conduct the treatment survey. However, acquiring quality data for reducing the CEE risk under limited labelling budgets remains under-explored until now. To fill the gap, we theoretically analyse the generalization risk from an intriguing perspective of progressively shrinking its upper bound, and develop a principled label acquisition pipeline exclusively for CEE tasks. With our analysis, we propose the Model Agnostic Causal Active Learning (MACAL) algorithm for batch-wise label acquisition, which aims to reduce both the CEE model's uncertainty and the post-acquisition distributional imbalance simultaneously at each acquisition step. Extensive experiments are conducted on three datasets, where a clear empirical performance gain from MACAL is observed over state-of-the-art active learning baselines. The implementation repository is open-sourced at: https://github.com/uqhwen2/MACAL.
Distribution shifts between training and testing samples frequently occur in practice and impede model generalization performance. This crucial challenge thereby motivates studies on domain generalization (DG), which aim to predict the label on unseen target domain data by solely using data from source domains. It is intuitive to conceive the class-separated representations learned in contrastive learning (CL) are able to improve DG, while the reality is quite the opposite: users observe directly applying CL deteriorates the performance. We analyze the phenomenon with the insights from CL theory and discover lack of intra-class connectivity in the DG setting causes the deficiency. We thus propose a new paradigm, domain-connecting contrastive learning (DCCL), to enhance the conceptual connectivity across domains and obtain generalizable representations for DG. On the data side, more aggressive data augmentation and cross-domain positive samples are introduced to improve intra-class connectivity. On the model side, to better embed the unseen test domains, we propose model anchoring to exploit the intra-class connectivity in pre-trained representations and complement the anchoring with generative transformation loss. Extensive experiments on five standard DG benchmarks are performed. The results verify that DCCL outperforms state-of-the-art baselines even without domain supervision. The detailed model implementation and the code are provided through https://github.com/weitianxin/DCCL.
Detecting anomalies in temporal data has gained significant attention across various real-world applications, aiming to identify unusual events and mitigate potential hazards. In practice, situations often involve a mix of segment-level labels (detected abnormal events with segments of time points) and unlabeled data (undetected events), while the ideal algorithmic outcome should be point-level predictions. Therefore, the huge label information gap between training data and targets makes the task challenging. In this study, we formulate the above imperfect information as noisy labels and propose NRdetector, a noise-resilient framework that incorporates confidence-based sample selection, robust segment-level learning, and data-centric point-level detection for multivariate time series anomaly detection. Particularly, to bridge the information gap between noisy segment-level labels and missing point-level labels, we develop a novel loss function that can effectively mitigate the label noise and consider the temporal features. It encourages the smoothness of consecutive points and the separability of points from segments with different labels. Extensive experiments on real-world multivariate time series datasets with 11 different evaluation metrics demonstrate that NRdetector consistently achieves robust results across multiple real-world datasets, outperforming various baselines adapted to operate in our setting.
Vertical federated learning (VFL) enables a privacy-preserving collaboration among various parties to train a global model by melding their geo-distributed data features. Communication has been recognized as the primary bottleneck that impairs training efficiency due to frequent cross-party statistics exchange over wide area network. Existing synchronous VFL works often suffer from excessive communication overhead, while asynchronous schemes may introduce significant model staleness, potentially eroding the learning accuracy. In this paper, we propose BS-VFL, an asynchronous VFL with bounded staleness, to pipeline local computation and statistics transmission, substantially reducing the communication overhead while ensuring favorable model performance. Specifically, all data parties will give precedence to local model updates before generating embeddings to curtail model staleness. By analyzing convergence error, we show that BS-VFL can achieve a comparable result to synchronous VFL. Then, we develop a general framework to derive the closed-form wall-clock time of BS-VFL, offering a measure of its runtime efficiency and highlighting a marked communication reduction. Utilizing this convergence and time analysis, we refine learning parameters to minimize the convergence error for optimizing BS-VFL performance without compromising training efficiency. Extensive experiments on real-world datasets validate the superiority of BS-VFL over leading-edge methods, evidencing a reduction in training duration by 48%-90% while preserving model accuracy.
Graph Transformers (GTs) have recently achieved significant success in the graph domain by effectively capturing both long-range dependencies and graph inductive biases. However, these methods face two primary challenges: (1) multi-view chaos, which results from coupling multi-view information (positional, structural, attribute), thereby impeding flexible usage and the interpretability of the propagation process. (2) local-global chaos, which arises from coupling local message passing with global attention, leading to issues of overfitting and over-globalizing. To address these challenges, we propose a high-level decoupled perspective of GTs, breaking them down into three components and two interaction levels: positional attention, structural attention, and attribute attention, alongside local and global interaction. Based on this decoupled perspective, we design a decoupled graph triple attention network named DeGTA, which separately computes multi-view attentions and adaptively integrates multi-view local and global information. This approach offers three key advantages: enhanced interpretability, flexible design, and adaptive integration of local and global information. Through extensive experiments, DeGTA achieves state-of-the-art performance across various datasets and tasks, including node classification and graph classification. Comprehensive ablation studies demonstrate that decoupling is essential for improving performance and enhancing interpretability. Our code is available at: https://github.com/wangxiaotang0906/DeGTA
In the realm of recommender systems, accurately predicting Click-Through Rate (CTR) is a critical task that involves learning user-item interaction features. Many researchers propose novel models to mine interaction signals, but they neglect that redundancy itself causes high computational cost and leads to suboptimal performance. Some tried to remove redundancy by dropping useless features, or shrinking the size of embedding table. However, current feature selection methods are vulnerable to training stochasticity and data dynamics, while embedding size assignment techniques neglect the importance relationships between feature fields. The simple combination of the two optimization ways will also yield poor performance due to the inherent gap in their optimization targets. Hence, there is no effective paradigm that can optimize feature fields from the two aspects in a simultaneous and coordinated way. In this paper, we identify the core issue as the lack of a practical score to measure the contribution of feature fields, and propose a distribution-based field optimization framework that adopts importance distribution to provide a comprehensive view for both methods. We innovatively design a learner for each field to acquire the stable and comprehensive importance situation. Then, based on this, we eliminate noise features, and assign adaptive embedding sizes for different feature fields according to the similarity of importance. With this field optimization, our proposed framework has extremely low pre-training overhead, greatly reduces training and inference time, and even achieves more accurate prediction results with fewer feature fields.
Exploiting users' contextual behaviors in the current session has been proven favorable to the document ranking task. Recently, the context-aware document ranking task has benefited from pre-trained language models (PLMs) due to their superior ability in language modeling. Most PLM-based context-aware document ranking models implicitly learn task-specific knowledge by fine-tuning PLMs on historical search logs. However, since search log data is noisy and contains various user intents and search patterns, such a black-box way may prevent models from fully mastering effective context-aware search knowledge. To solve this problem, we propose LOCK, a PLM-based context-aware document ranking model that explicitly embeds task-specific prior knowledge into PLMs to guide the model optimization. From local to global, we identify three types of task-specific knowledge, including intra-turn signals, inter-turn signals, and global session signals. LOCK formulates such prior knowledge into prior attention biases for impacting the fine-tuning of PLMs. This operation can guide the ranking model by task-specific prior knowledge, thereby improving model convergence and ranking ability. Additionally, we introduce a task-specific pre-training stage that involves masked language modeling and the soft reconstruction of the prior attention matrix, which helps the PLMs adapt to our task. Extensive experiments validate the effectiveness and convergence of our method.
GraphTool-Instruction: Revolutionizing Graph Reasoning in LLMs through Decomposed Subtask Instruction
PDF ↗Large language models (LLMs) have been demonstrated to possess the capabilities to understand fundamental graph properties and address various graph reasoning tasks. Existing methods fine-tune LLMs to understand and execute graph reasoning tasks by specially designed task instructions. However, these Text-Instruction methods generally exhibit poor performance. Inspired by tool learning, researchers propose Tool-Instruction methods to solve various graph problems by special tool calling (e.g., function, API and model), achieving significant improvements in graph reasoning tasks. Nevertheless, current Tool-Instruction approaches focus on the tool information and ignore the graph structure information, which leads to significantly inferior performance on small-scale LLMs (less than 8B). To tackle this issue, we propose GraphTool-Instruction, an innovative Instruction-tuning approach that decomposes the graph reasoning task into three distinct subtasks (i.e., graph extraction, tool name identification and tool parameter extraction), and design specialized instructions for each subtask. Our GraphTool-Instruction can be used as a plug-and-play prompt for different LLMs without fine-tuning. Moreover, building on GraphTool-Instruction, we develop GTools, a dataset that includes twenty graph reasoning tasks, and create a graph reasoning LLM called GraphForge based on Llama3-8B. We conduct extensive experiments on twenty graph reasoning tasks with different graph types (e.g., graph size or graph direction), and we find that GraphTool-Instruction achieves SOTA compared to Text-Instruction and Tool-Instruction methods. Fine-tuned on GTools, GraphForge gets further improvement of over 30% compared to the Tool-Instruction enhanced GPT-3.5-turbo, and it performs comparably to the high-cost GPT-4o. Our codes and data are available at https://github.com/RongzhengWang/GraphTool-Instruction.
Meta-learning is a practical learning paradigm to transfer skills across tasks from a few examples. Nevertheless, the existence of task distribution shifts tends to weaken meta-learners' generalization capability, particularly when the training task distribution is naively hand-crafted or based on simple priors that fail to cover critical scenarios sufficiently. Here, we consider explicitly generative modeling task distributions placed over task identifiers and propose robustifying fast adaptation from adversarial training. Our approach, which can be interpreted as a model of a Stackelberg game, not only uncovers the task structure during problem-solving from an explicit generative model but also theoretically increases the adaptation robustness in worst cases. This work has practical implications, particularly in dealing with task distribution shifts in meta-learning, and contributes to theoretical insights in the field. Our method demonstrates its robustness in the presence of task subpopulation shifts and improved performance over SOTA baselines in extensive experiments. The code is available at the project site https://sites.google.com/view/ar-metalearn.
Recent advances in neural models have shown considerable promise in solving Traveling Salesman Problems (TSPs) without relying on much hand-crafted engineering. However, while non-autoregressive (NAR) approaches benefit from faster inference through parallelism, they typically deliver solutions of inferior quality compared to autoregressive ones. To enhance the solution quality while maintaining fast inference, we propose DEITSP, a diffusion model with efficient iterations tailored for TSP that operates in a NAR manner. Firstly, we introduce a one-step diffusion model that integrates the controlled discrete noise addition process with self-consistency enhancement, enabling optimal solution prediction through simultaneous denoising of multiple solutions. Secondly, we design a dual-modality graph transformer to bolster the extraction and fusion of features from node and edge modalities, while further accelerating the inference with fewer layers. Thirdly, we develop an efficient iterative strategy that alternates between adding and removing noise to improve exploration compared to previous diffusion methods. Additionally, we devise a scheduling framework to progressively refine the solution space by adjusting noise levels, facilitating a smooth search for optimal solutions. Extensive experiments on real-world and large-scale TSP instances demonstrate that DEITSP performs favorably against existing neural approaches in terms of solution quality, inference latency, and generalization ability.
Ride-hailing services offer convenient travel options in urban transportation. To improve passengers' experience and platforms' revenue, plentiful studies use multi-agent reinforcement learning (MARL) for efficient order dispatching, controlling each grid with one agent to balance the supply-demand (drivers-orders) distribution. However, despite the critical role of cooperation among grids for efficient dispatching strategies, existing works neglect it or limit it within neighboring grids. There exist three key challenges in scaling the cooperation to the whole city: (1) cooperative strategies cause complex interactions among grids, making the grids' states coupled and complicating the information extraction from the states for decision-making; (2) cooperation among grids requires both within- and cross-grid dispatching, where the priorities of these two types of actions are difficult to balance; (3) the value of cooperation is not only heterogeneous over different pairs of grids, but also varies temporally, adding difficulty to dynamically determine the intensities of cooperation for each pair of grids and obtain the global cooperation rewards. In this paper, we propose the CoopRide framework to solve the above challenges. We model the interactions among agents with graphs and utilize graph neural network (GNN) for efficient information extraction. We uniformly encode both within- and cross-grid dispatching, enabling flexible choice of both types of actions in the embedding space. We also design to automatically learn the cooperation intensities among grids, thereby obtaining the cooperative rewards to drive the learning of global cooperation actions. We conduct experiments in three real-world datasets with millions of orders, and extensive results demonstrate the superior performance of CoopRide, outperforming the state-of-the-art baselines by up to 12.4%. Our source codes are available at https://github.com/tsinghua-fib-lab/CoopRide.