We present MOSS, a multi-objective optimization framework for constructing stable sets of decision rules. MOSS incorporates three important criteria for interpretability: sparsity, accuracy, and stability, into a single multi-objective optimization framework. Importantly, MOSS allows a practitioner to rapidly evaluate the trade-off between accuracy and stability in sparse rule sets in order to select an appropriate model. We develop a specialized cutting plane algorithm in our framework to rapidly compute the Pareto frontier between these two objectives, and our algorithm scales to problem instances beyond the capabilities of commercial optimization solvers. Our experiments show that MOSS outperforms state-of-the-art rule ensembles in terms of both predictive performance and stability.
论文检索
输入标题、作者或关键词，从 844 篇学术成果中精准定位
In the field of auction design, leveraging deep learning to solve optimal auctions from sampled data has become a promising direction. However, real-world contexts often involve uncertain data, which would severely affect the auction performance, but it is lacking consideration in existing works. To address this challenge, we incorporate these uncertainties into auction design metrics, and frame this challenge as a robust data-driven auction design problem. To solve this problem, we first propose the GAT method, where we introduce the process of problem relaxation and transformation to address the non-differentiable variable presented in the original problem, and further propose an adversarial training algorithm to solve the mini-max problem after transformation. Moreover, to obtain moderately robust auctions, we propose two methods to select the robust coefficient, which provides guidance and insights for selecting robust auctions based on generalization and performance metrics. Finally, with the insights from the GAT method, we further propose the SAT method, where we employ a strict and unified IC constraint that extends from the GAT method, which provides strong IC guarantees and stable revenue in uncertain environments. Experiments on both constructed and real-world datasets show that our robust methods effectively improve the performance of auctions in terms of revenue and IC guarantees.
Graph Prompt Learning (GPL) has been introduced as a promising approach that uses prompts to adapt pre-trained GNN models to specific downstream tasks without requiring fine-tuning of the entire model. Despite the advantages of GPL, little attention has been given to its vulnerability to backdoor attacks, where an adversary can manipulate the model's behavior by embedding hidden triggers. Existing graph backdoor attacks rely on modifying model parameters during training, but this approach is impractical in GPL as GNN encoder parameters are frozen after pre-training. Moreover, downstream users may fine-tune their own task models on clean datasets, further complicating the attack. In this paper, we propose TGPA, a backdoor attack framework designed specifically for GPL. TGPA injects backdoors into graph prompts without modifying pre-trained GNN encoders and ensures high attack success rates and clean accuracy. To address the challenge of model fine-tuning by users, we introduce a finetuning-resistant poisoning approach that maintains the effectiveness of the backdoor even after downstream model adjustments. Extensive experiments on multiple datasets under various settings demonstrate the effectiveness of TGPA in compromising GPL models with fixed GNN encoders.
Mining cohesive subgraphs in bipartite graphs is of great importance to various real-world applications such as recommendation in e-commercial systems and fraud detections in social networks. In this paper, we study the problem of Bitruss Decomposition of a given bipartite graph G. The goal is to compute, for each edge e, the largest value of k such that e is still contained in a k-bitruss. Here, a k-bitruss is a maximal subgraph of G such that every edge of it is contained in at least k butterflies (i.e(2,2)-cliques) in the subgraph. All the previous state-of-the-art solutions are based on the well-known Peeling Process framework and have to ''touch'' every butterfly in the graph G for at least once, causing a O(⧖G) cost, where ⧖G is the number of butterflies in G. In the worst case, ⧖G can be as large as O(m2), where m is the number of edges in G. We propose the first algorithm called BiT-DT, whose running time is bounded by O(m^1.5 log m), significantly improving the state-of-the-art bound by roughly a factor of O(√m). The crucial idea of our algorithm is an efficient approach to identify the edges to be peeled next in the Peeling Process without maintaining a precise butterfly support for each edge. To further enhance the practical performance of our BiT-DT algorithm, we propose a heuristic to peel the edges in batch. Extensive experimental results on ten real-world datasets show that our proposed algorithm outperforms the state-of-the-art baselines by up to an order of magnitude in terms of running time.
Feature Reconstruction for Anomaly Detection on Directed Multigraphs: A Preprocessing Framework for GNNs
PDF ↗Graph Neural Networks (GNNs) have achieved significant success in anomaly detection across various domains. However, existing GNN approaches face notable challenges when applied to directed multigraphs where edge attributes serve as the sole source of information. This limitation complicates the learning of meaningful node representations and the accurate detection of anomalies, particularly in transaction networks. Moreover, existing methods typically suffer from dimensionality explosion and suboptimal use of structural and semantic information, leading to reduced detection performance. To address these challenges, we propose Feature Reconstruction for Anomaly Detection on Directed Multigraphs (FRAD-DM), a novel preprocessing framework tailored to enhance graph representations in node feature-absent scenarios. FRAD-DM employs advanced edge feature derivation techniques, temporal and structural subgraph analysis for node representation generation, and a reinforcement learning-based adaptive feature selection mechanism. This comprehensive framework optimizes feature spaces by balancing informativeness, task relevance, and computational efficiency, ensuring robust and scalable anomaly detection. Extensive experiments on real-world datasets under barely supervised settings demonstrate the effectiveness of FRAD-DM. By integrating it into various GNN architectures for node-level and edge-level anomaly detection tasks, negative-class F1-scores improve by 5.44% to 20.98%. These results highlight its capability to address the challenges of directed multigraphs in practical applications.
Distribution shifts between training and testing datasets can significantly affect the effectiveness of machine learning models, as the typical assumption of data homogeneity often does not hold in practical applications. To address this challenge, previous literature explores invariant representation learning methods, including but not limited to domain adversarial learning, feature alignment, and invariant risk minimization. In this paper, we introduce a novel method for generating distribution-free prediction regions, which effectively quantify the uncertainty of predictions in different environments. Our methodology incorporates a weighted conformity score, tailored to the environment of each test sample, to construct adaptive conformal intervals. The proposed method is computationally efficient and can be implemented by subsampling. We demonstrate how these intervals maintain a consistent conditional coverage under some conditions. The numerical experiments, including simulations and real data analysis, show that our method is applicable and robust in dealing with distribution shifts.
Imputation via Domain Adaptation: Rethinking Variable Subset Forecasting from Knowledge Transfer
PDF ↗Multivariate time series forecasting in practical deployment faces a critical challenge termed Variable Subset Forecasting (VSF), where certain variables accessible during training are entirely missing during inference. This creates a stark discrepancy between the training (source domain with full variables) and inference (target domain with partial variables) environments, disrupting cross-variable dependencies and fragmenting global temporal patterns. Existing imputation methods, limited to transferring local knowledge (e.g., temporal neighbors or pairwise correlations), fail to capture essential global dynamics, leading to severe performance degradation under distribution shifts. To address these challenges, we redefine VSF as a cross-domain knowledge transfer problem and propose VIDA, a framework that systematically transfers Variable Invariant knowledge from complete to partial observations through Domain Adaptation. Key to our approach is (1) Global time-frequency joint representation learning, which encodes temporal dynamics via dilated convolutions and captures low-frequency spectral consistency using Fourier neural operators, and (2) Sinkhorn-regularized distribution alignment to bridge non-overlapping feature supports across domains via optimal transport. Unlike imputation-first methods, VIDA enforces task-driven consistency by jointly optimizing predictions on reconstructed and original data, ensuring the transferred knowledge directly enhances forecasting robustness. Extensive experiments across four real-world datasets show that VIDA outperforms state-of-the-art imputation methods by 25% on average with partially observed variables. This work establishes a new paradigm for variable-missing scenarios by unifying imputation and forecasting through principled knowledge transfer.
Hexagon-Net: Heterogeneous Cross-View Aligned Graph Attention Networks for Implied Volatility Surface Prediction
PDF ↗Implied Volatility Surface (IVS) prediction is critical for options hedging, portfolio management, and risk control. These applications encounter significant challenges, including imbalanced data distributions and inherent uncertainties in forecasting. Recent advances relying on deep learning have led to significant progress in addressing these issues. However, several key problems have not yet been solved: (i) Moneyness and maturities of traded options change over time. Therefore, proper spatio-temporal alignment is an essential prerequisite for the downstream forecasting exercise. (ii) Different regions of the IVS are unevenly informed because of liquidity constraints and therefore should not be modeled uniformly. (iii) The complex interconnections among data points in the IVS from various perspectives-such as the well-known 'smirk' patterns across dimensions-are neither explicitly addressed nor effectively captured by existing models. To address these issues, we propose a novel end-to-end heterogeneous cross(x)-view aligned graph attention network (Hexagon-Net), which aligns historical IVS data, learns distinctive IVS patterns, propagates predictive information, and forecasts future IVS movements simultaneously. Extensive experiments on stock index options datasets demonstrate that Hexagon-Net significantly and consistently outperforms the previous approaches in IVS modeling and deep learning. Additionally, we present further experiments-such as ablation studies, sensitivity analyses, and alternative configurations-to explore the reasons behind its superior performance.
Federated learning (FL) involves multiple heterogeneous clients collaboratively training a global model via iterative local updates and model fusion. The generalization of FL's global model has a large gap compared with centralized training, which is its bottleneck for broader applications. In this paper, we study and improve FL's generalization through a fundamental ''connectivity'' perspective, which means how the local models are connected in the parameter region and fused into a generalized global model. The term ''connectivity'' is derived from linear mode connectivity (LMC), studying the interpolated loss landscape of two different solutions (e.g., modes) of neural networks. Bridging the gap between LMC and FL, in this paper, we leverage fixed anchor models to empirically and theoretically study the transitivity property of connectivity from two models (LMC) to a group of models (model fusion in FL). Based on the findings, we propose FedGuCci(+), improving group connectivity for better generalization. It is shown that our methods can boost the generalization of FL under client heterogeneity across various tasks (4 CV datasets and 6 NLP datasets) and model architectures (e.g., ViTs and PLMs). The code is available here: https://github.com/ZexiLee/fedgucci.
Open-world continual learning (OWCL) adapts to sequential tasks with open samples, learning knowledge incrementally while preventing forgetting. However, existing OWCL still requires a large amount of labeled data for training, which is often impractical in real-world applications. Given that new categories/entities typically come with limited annotations and are in small quantities, a more realistic situation is OWCL with scarce labeled data, i.e., few-shot training samples. Hence, this paper investigates the problem of open-world few-shot continual learning (OFCL), challenging in (i) learning unbounded tasks without forgetting previous knowledge and avoiding overfitting(ii) constructing compact decision boundaries for open detection with limited labeled data, and (iii) transferring knowledge about knowns and unknowns and even update the unknowns to knowns once the labels of open samples are learned. In response, we propose a novel OFCL framework that integrates three key components: (1) an instance-wise token augmentation (ITA) that represents and enriches sample representations with additional knowledge(2) a margin-based open boundary (MOB) that supports open detection with new tasks emerge over time, and (3) an adaptive knowledge space (AKS) that endows unknowns with knowledge for the updating from unknowns to knowns. Finally, extensive experiments show that the proposed OFCL framework outperforms all baselines remarkably with practical importance and reproducibility. The source code is released at https://github.com/liyj1201/OFCL.
Recently, Graph Foundation Models (GFMs) have emerged as a significant research topic in graph machine learning. Compared with traditional graph neural networks, GFMs demonstrate impressive zero-shot generalization across different domains and tasks through large-scale pre-training on extensive and diverse graph data. Despite the initial success of pre-training, existing GFMs face challenges such as extreme time consumption and the presence of redundancy and noise in pre-training data. To alleviate these issues, we present the first exploration of data-centric GFM, which aims to optimize pre-training data (i.e., a set of subgraphs) to establish a more efficient GFM while maintaining robust performance across various downstream tasks. We propose DCGFM, a plug-and-play approach for Data-Centric GFM that incorporates the idea of data pruning to remove redundant and less informative subgraphs from the pre-training data, thereby improving both efficiency and effectiveness. Specifically, DCGFM consists of two components: (1) a model-agnostic hard pruning module that filters out subgraphs with lower informativity scores by considering both the semantics and structures of subgraphs; and (2) a model-aware soft pruning module that dynamically prunes subgraphs with lower loss values in each pre-training epoch with a gradient rescaling strategy. Extensive experiments on representative GFM backbones demonstrate DCGFM's efficiency and effectiveness. Remarkably, DCGFM achieves even better performance using only 30% of the pre-training data. Codes and data are available at https://github.com/Yuhan1i/DCGFM.
Interference in online controlled experiments poses significant challenges, as treatment effects may propagate through user interactions. This phenomenon systematically biases conventional treatment effect estimators and substantially complicates the interpretation of experimental results. Detecting the presence of interference is crucial for ensuring the reliability of conclusions, ultimately enhancing decision-making processes. We formalize a framework for detecting the existence of interference with dyadic data, which is ubiquitous in social network platforms. Dyadic data, typically generated from user interactions, have not been fully utilized in online controlled experiments. We first introduce the dyadic-robust inference techniques, then illustrate how the dyadic outcomes link to the user-level metrics and how interference manifests. We then propose a comprehensive approach to detect interference effects based on dyadic-robust t-statistics, and we also provide a subsampling approach to reduce the computational complexity of the proposed methods. We also provide several approaches to leverage pre-experiment data, such as selecting the optimal treatment probability, designing stratified randomization in the pre-experiment stage, or reducing the variance with both user-level and dyad-level control variates at the post-experiment stage. Our approach is computationally efficient and easily integrated with existing pipelines. We provide theoretical guarantees for our inference procedure across various asymptotic regimes. Finally, we conduct several empirical evaluations under various dyadic data-generating processes to assess the performance and robustness of the proposed procedures. Finally, we introduce an interference detection pipeline and demonstrate it with an experiment from Weixin.
Distributed deep learning has been widely deployed in data centers to provide various services such as image classification and speech recognition. To reduce the training time, Top-k compression has become one of the most popular solutions used to shrink the data volume of gradients. Nevertheless, we observe that existing Top-k compression solutions are inefficient when used for large-scale distributed training due to gradient build-up, missing of Top-k gradients, and high compression overhead at the end hosts. To address these problems, we propose SwitchTop-k, which improves the accuracy of selecting Top-k values while ensuring a high compression rate and zero compression overhead. Specifically, SwitchTop-k offloads the Top-k compression from the end hosts to the programmable switches, thus alleviating the gradient build-up and compression overhead. Meanwhile, we propose a sketch-based solution to achieve high accuracy in selecting global Top-k gradients. We also co-design switch logic and end host logic to improve communication efficiency of uncompressed traffic. Finally, we implement SwitchTop-k on Intel Tofino switches and integrate it with Pytorch. The test results show that SwitchTop-k reduces iteration time by up to 91% compared with existing compression algorithms.
Traditional knowledge graph (KG) embedding methods aim to represent entities and relations in a low-dimensional space, primarily focusing on static graphs. However, real-world KGs are dynamically evolving with the constant addition of entities, relations and facts. To address such dynamic nature of KGs, several continual knowledge graph embedding (CKGE) methods have been developed to efficiently update KG embeddings to accommodate new facts while maintaining learned knowledge. As KGs grow at different rates and scales in real-world scenarios, existing CKGE methods often fail to consider the varying scales of updates and lack systematic evaluation throughout the entire update process. In this paper, we propose SAGE, a scale-aware gradual evolution framework for CKGE. Specifically, SAGE firstly determine the embedding dimensions based on the update scales and expand the embedding space accordingly. The Dynamic Distillation mechanism is further employed to balance the preservation of learned knowledge and the incorporation of new facts. We conduct extensive experiments on seven benchmarks, and the results show that SAGE consistently outperforms existing baselines, with a notable improvement of 1.38% in MRR, 1.25% in H@1 and 1.6% in H@10. Furthermore, experiments comparing with fixed dimensions methods show that SAGE achieves optimal performance on every snapshot, demonstrating the importance of adaptive embedding dimensions in CKGE.
Understanding molecular structure and related knowledge is crucial for scientific research. Recent studies integrate molecular graphs with their textual descriptions to enhance molecular representation learning. However, they focus on the whole molecular graph and neglect frequently occurring subgraphs, known as motifs, which are essential for determining molecular properties. Without such fine-grained knowledge, these models struggle to generalize to unseen molecules and tasks that require motif-level insights. To bridge this gap, we propose FineMolTex, a novel Fine-grained Molecular graph-Text pre-training framework to jointly learn coarse-grained molecule-level knowledge and fine-grained motif-level knowledge. Specifically, FineMolTex consists of two pre-training tasks: a contrastive alignment task for coarse-grained matching and a masked multi-modal modeling task for fine-grained matching. In particular, the latter predicts the labels of masked motifs and words, which are selected based on their importance. By leveraging insights from both modalities, FineMolTex is able to understand the fine-grained matching between motifs and words. Finally, we conduct extensive experiments across three downstream tasks, achieving up to 230% improvement in the text-based molecule editing task. Additionally, our case studies reveal that FineMolTex successfully captures fine-grained knowledge, potentially offering valuable insights for drug discovery and catalyst design.
Recently, Graph Neural Networks (GNNs) have become the dominant approach for Knowledge Graph-aware Recommender Systems (KGRSs) due to their proven effectiveness. Building upon GNN-based KGRSs, Self-Supervised Learning (SSL) has been incorporated to address the sparity issue, leading to longer training time. However, through extensive experiments, we reveal that: (1)compared to other KGRSs, the existing GNN-based KGRSs fail to keep their superior performance under sparse interactions even with SSL. (2) More complex models tend to perform worse in sparse interaction scenarios and complex mechanisms, like attention mechanism, can be detrimental as they often increase learning difficulty. Inspired by these findings, we propose LightKG, a simple yet powerful GNN-based KGRS to address sparsity issues. LightKG includes a simplified GNN layer that encodes directed relations as scalar pairs rather than dense embeddings and employs a linear aggregation framework, greatly reducing the complexity of GNNs. Additionally, LightKG incorporates an efficient contrastive layer to implement SSL. It directly minimizes the node similarity in original graph, avoiding the time-consuming subgraph generation and comparison required in previous SSL methods. Experiments on four benchmark datasets show that LightKG outperforms 12 competitive KGRSs in both sparse and dense scenarios while significantly reducing training time. Specifically, it surpasses the best baselines by an average of 5.8% in recommendation accuracy and saves 84.3% of training time compared to KGRSs with SSL. Our code is available at https://github.com/1371149/LightKG.
Graph Anomaly Detection (GAD) in heterogeneous networks presents unique challenges due to node and edge heterogeneity. Existing Graph Neural Network (GNN) methods primarily focus on homogeneous GAD and thus fail to address three key issues: (C1) Capturing abnormal signal and rich semantics across diverse meta-paths; (C2) Retaining high-frequency content in HIN dimension alignment; and (C3) Learning effectively from difficult anomaly samples with class imbalance. To overcome these, we propose ChiGAD, a spectral GNN framework based on a novel Chi-Square filter, inspired by the wavelet effectiveness in diverse domains. Specifically, ChiGAD consists of: (1) Multi-Graph Chi-Square Filter, which captures anomalous information via applying dedicated Chi-Square filters to each meta-path graph; (2) Interactive Meta-Graph Convolution, which aligns features while preserving high-frequency information and incorporates heterogeneous messages by a unified Chi-Square Filter; and (3) Contribution-Informed Cross-Entropy Loss, which prioritizes difficult anomalies to address class imbalance. Extensive experiments on public and industrial datasets show that ChiGAD outperforms state-of-the-art models on multiple metrics. Additionally, its homogeneous variant, ChiGNN, excels on seven GAD datasets, validating the effectiveness of Chi-Square filters. Our code is available at https://github.com/HsipingLi/ChiGAD.
Warning: This paper contains examples of toxic text. Knowledge editing has emerged as an efficient technique for updating the knowledge of large language models (LLMs), attracting increasing attention in recent years. However, there is a lack of effective measures to prevent the malicious misuse of this technique, which could lead to harmful edits in LLMs. These malicious modifications could cause LLMs to generate toxic content, misleading users into inappropriate actions. In front of this risk, we introduce a new task, Knowledge Editing Type Identification (KETI), aimed at identifying different types of edits in LLMs, thereby providing timely alerts to users when encountering illicit edits. As part of this task, we propose KETIBench, which includes five types of harmful edits covering the most popular toxic types, as well as one benign factual edit. We develop five classical classification models and three BERT-based models as baseline identifiers for both open-source and closed-source LLMs. Our experimental results, across 92 trials involving four models and three knowledge editing methods, demonstrate that all eight baseline identifiers achieve decent identification performance, highlighting the feasibility of identifying malicious edits in LLMs. Additional analyses reveal that the performance of the identifiers is independent of the reliability of the knowledge editing methods and exhibits cross-domain generalization, enabling the identification of edits from unknown sources. All data and code are available in https://github.com/xpq-tech/KETI.
Adapting Pretrained Language Models for Citation Classification via Self-Supervised Contrastive Learning
PDF ↗Citation classification, which identifies the intention behind academic citations, is pivotal for scholarly analysis. Previous works suggest fine-tuning pretrained language models (PLMs) on citation classification datasets, reaping the reward of the linguistic knowledge they gained during pretraining. However, directly fine-tuning for citation classification is challenging due to labeled data scarcity, contextual noise, and spurious keyphrase correlations. In this paper, we present a novel framework, Citss, that adapts the PLMs to overcome these challenges. Citss introduces self-supervised contrastive learning to alleviate data scarcity, and is equipped with two specialized strategies to obtain the contrastive pairs: sentence-level cropping, which enhances focus on target citations within long contexts, and keyphrase perturbation, which mitigates reliance on specific keyphrases. Compared with previous works that are only designed for encoder-based PLMs, Citss is carefully developed to be compatible with both encoder-based PLMs and decoder-based LLMs, to embrace the benefits of enlarged pretraining. Experiments with three benchmark datasets with both encoder-based PLMs and decoder-based LLMs demonstrate our superiority compared to the previous state of the art. Our code is available at: github.com/LITONG99/Citss
Fine-grained traffic management and prediction are fundamental to key applications such as autonomous driving, lane change guidance, and traffic signal control. However, obtaining lane-level traffic data has become a critical bottleneck for data-driven models due to limitations in the types and number of sensors and issues with the accuracy of tracking algorithms. To address this, we propose the Fine-grained Road Traffic Inference (FRTI) task, which aims to generate more detailed lane-level traffic information using limited road data, providing a more energy-efficient and cost-effective solution for precise traffic management. This task is abstracted as the first scene of the spatio-temporal graph node generation problem. We designed a two-stage framework-RoadDiff-to solve the FRTI task. This framework leverages the Road-Lane Correlation Autoencoder-Decoder and the Lane Diffusion Module to fully utilize the limited spatio-temporal dependencies and distribution relationships of road data to accurately infer fine-grained lane traffic states. Based on existing research, we designed several baseline models with the potential to solve the FRTI task and conducted extensive experiments on six datasets representing different road conditions to validate the effectiveness of the RoadDiff model in addressing the FRTI task. The relevant datasets and code are available at https://github.com/ShuhaoLii/RoadDiff.