Accurate multivariate time series forecasting (MTSF) is critical for intelligent web services in Web of Things. When confronted with unseen multivariate time series (MTS), the industry typically invests significant time and resources in training multiple models to identify the optimal model for deployment. This paper proposes a novel, efficient, and scalable MTSF model selection method that directly selects suitable MTSF methods based on data characteristics without extensive model training. Model selection is a core component of AutoML, which has made significant progress in recent years. However, existing methods incur high operational costs and cannot be directly applied to MTSF tasks. Moreover, there is a lack of a comprehensive and cohesive public time series library for MTSF model selection. To address these challenges, we compile the first large heterogeneous labeled MTSF model selection dataset, called the ModelPile, which covers 41 mainstream datasets across 11 domains. We then propose AutoMTSF, a large model-enabled model selection method that transforms the MTSF model selection problem into a time series classification problem and utilizes the ModelPile to unlock large-scale multi-dataset training. AutoMTSF first uses the pre-trained large model to encode raw MTS. Given the coarse-grained limitations of large model encoding, Recursive Temporal Pattern Feature (RTPF) is proposed to capture both fine-grained and global temporal feature evolution, thereby effectively mapping data characteristics to the MTSF method space. Experiments comparing AutoMTSF with 2 baselines, 17 MTSF methods, and 4 large time series models show that AutoMTSF outperforms state-of-the-art methods while maintaining comparable execution time. This work represents a critical step in validating the accuracy and efficiency of large model-enabled classification for MTSF.

Subgraph Anomaly Detection (SAD) is crucial for identifying groups that deviate from the regular pattern within graphs, which benefits different domains such as financial fraud and network security. However, current studies rely on traditional node detection methods and fixed sampling strategies of subgraph structures, which makes it difficult to learn the pattern collaboration behavior of subgraphs. To address this limitation, this paper proposes a novel unsupervised framework named PC-SAD. The PC-SAD framework first employs an improved Graph AutoEncoder to identify core anomaly nodes by capturing multi-scale neighborhood information. Starting from these core anomaly nodes, we sample candidate subgraphs with path, tree, and cyclic structures, and enhance them according to the characteristics of the subgraph structures. Subsequently, candidate subgraphs are fed into the proposed Pattern Collaboration-based Graph Contrastive Learning method to generate collaborative pattern embeddings, thereby distinguishing anomaly subgraphs. The experimental results show that PC-SAD outperforms the state-of-the-art baseline methods on four benchmark datasets, which proves that PC-SAD is an effective solution to detect anomaly subgraphs.

Network quantization, one of the most widely studied model compression methods, effectively quantizes a floating-point model to obtain a fixed-point one with negligible accuracy loss. Although great success was achieved in reducing the model size, it may exacerbate the unfairness in model accuracy across different groups of datasets. This paper considers two widely used algorithms: Post-Training Quantization (PTQ) and Quantization-Aware Training (QAT), with an attempt to understand how they cause this critical issue. Theoretical analysis with empirical verifications reveals two responsible factors, as well as how they influence a metric of fairness in depth. A comparison between PTQ and QAT is then made, explaining an observation that QAT behaves even worse than PTQ in fairness, although it often preserves a higher accuracy at lower bit-widths in quantization. Finally, the paper finds out that several simple data augmentation methods can be adopted to alleviate the disparate impacts of quantization, based on a further observation that class imbalance produces distinct values of the aforementioned factors among different attribute classes. We experiment on either imbalanced (UTK-Face and FER2013) or balanced (CIFAR-10 and MNIST) datasets using ResNet and VGG models for empirical evaluation.

We explore the potential of \emph{AI-enhanced combinatorial optimization theory}, taking online bipartite matching (OBM) as a case study. In the theoretical study of OBM, the \emph{hardness} corresponds to a performance \emph{upper bound} of a specific online algorithm or any possible online algorithms. Typically, these upper bounds derive from challenging instances meticulously designed by theoretical computer scientists. Zhang et al. (ICML 2024) recently provide an example demonstrating how reinforcement learning techniques enhance the hardness result of a specific OBM model. Their attempt is inspiring but preliminary. It is unclear whether their methods can be applied to other OBM problems with similar breakthroughs. This paper takes a further step by introducing DiMa, a unified and novel framework that aims at understanding the hardness of OBM problems based on denoising diffusion probabilistic models (DDPMs). DiMa models the process of generating hard instances as denoising steps, and optimizes them by a novel reinforcement learning algorithm, named \emph{shortcut policy gradient} (SPG). We first examine DiMa on the classic OBM problem by reproducing its known hardest input instance in literature. Further, we apply DiMa to two well-known variants of OBM, for which the exact hardness remains an open problem, and we successfully improve their theoretical state-of-the-art upper bounds.

Graph Neural Networks (GNNs) are inherently vulnerable to link stealing attacks, as their structural aggregation mechanisms may inadvertently leak training graph data. Existing link stealing methods primarily rely on posterior similarity for inference but suffer from critical limitations: inherent semantic bias (e.g., misclassifying semantically similar but unconnected nodes) and insufficient structural information, which constrain attack performance. To address these issues, we propose TLSA (Transfer Learning-based Link Stealing Attack), a novel framework that captures generalized structural knowledge from multi-domain heterogeneous graphs based on cross-domain knowledge transfer, and merges it with posterior similarity to enhance attack performance. The cross-domain knowledge transfer is enabled by integrating partially leaked target subgraphs with shadow graphs. Specifically, TLSA designs a triple-level alignment mechanism, including node feature reconstruction, which unifies heterogeneous posterior dimensions across domains; trainable hub nodes with gradient-driven topological optimization, forming bidirectional learning loops that bridge target and shadow domains; and domain adversarial training, which minimizes graph distribution distance and ensures deep semantic consistency across domains. Since its extracted structure-aware features are fused with node-pair semantic similarity, TLSA generates enhanced attack features for accurate edge existence prediction, significantly improving link stealing performance. Extensive experiments on diverse graph datasets validate the effectiveness of TLSA.

Ensuring privacy in e-health recommendation systems is a critical yet challenging task, particularly when high-quality recommendations require access to sensitive patient data. Existing approaches often rely on computationally expensive cryptographic techniques or restrict matching to binary outcomes, limiting both efficiency and recommendation accuracy. In this paper, we propose APER, a novel privacy-preserving recommendation scheme that achieves both accuracy and efficiency through the design of two core cryptographic protocols. Specifically, we construct a secure and efficient similarity computation protocol and a privacy-preserving truth discovery protocol by leveraging distributed multi-point function and replicated secret sharing techniques. These protocols enable fine-grained doctor-patient matching without exposing private health or feedback data. Security analysis proves that APER achieves rigorous privacy guarantees under semi-honest adversaries. Experimental results show that APER reduces computational overhead by up to 10× compared to recent methods, while delivering accurate and scalable recommendations.

Memory-based Temporal Graph Neural Networks (M-TGNNs) demonstrate superior performance in dynamic graph learning tasks. Their success attributes to a memory module, which captures historical information for each node and implicitly creates a memory dependency constraint among chronologically ordered minibatches. This unique characteristic of M-TGNN introduces new challenges for parallel training that have not been encountered before. Existing parallelism strategies for M-TGNN either sacrifice memory accuracy (minibatch parallelism and epoch parallelism) or compromise space efficiency (memory parallelism) to optimize runtime. This paper proposes a pipeline parallel approach for multi-GPU M-TGNN training that effectively addresses both inter-minibatch memory dependencies and intra-minibatch task dependencies, based on a runtime analysis DAG for M-TGNNs. We further optimize pipeline efficiency by incorporating improved scheduling, finer-grained operation reorganization, and targeted communication optimizations tailored to the specific training properties of M-TGNN. These enhancements significantly reduce GPU waiting and idle time caused by memory dependencies and frequent communication and result in zero pipeline bubbles for common training configurations. Extensive evaluations demonstrate that PipeTGL achieves a speedup of 1.27x to 4.74x over other baselines while also improving the accuracy of M-TGNN training across multiple GPUs.

Vision transformers (ViTs) have demonstrated great success in various fundamental CV tasks, mainly benefiting from their self-attention-based transformer architectures, and the paradigm of pre-training followed by fine-tuning. However, such advantages may lead to significant data privacy risks, such as membership inference attacks (MIAs), which remain unclear. This paper presents the first comprehensive study on MIAs and corresponding defenses against ViTs. Our first contribution is a rollout-attention-based MIA method (RAMIA), based on an experimental observation that the attention, more precisely the rollout attention, behaves disproportionately for members and non-members. We evaluate RAMIA on the standard ViT architecture proposed by Google (ICLR 2021), achieving high accuracy, precision, and recall performance. Further, inspired by another experimental observation on a strong connection between positional embeddings (PEs) and attentions, we propose a novel framework for training ViTs, named Mosaic MixUp Training (MMUT), as a defense against RAMIA. Intuitively, MMUT mixes up private images and public ones at a patch level, and mosaics the corresponding PEs with a global learnable mosaic embedding. Our empirical results show MMUT achieves a much better accuracy-privacy trade-off than some common defense mechanisms. Extensive experiments are conducted to rigorously evaluate both RAMIA and MMUT.

For a specific online optimization problem, for example, online bipartite matching (OBM), research efforts could be made in two directions before it is finally closed, i.e., the optimal competitive online algorithm is found. One is to continuously design algorithms with better performance. To this end, reinforcement learning (RL) has demonstrated great success in literature. However, little is known on the other direction: whether RL helps explore how hard an online problem is. In this paper, we study a generalized model of OBM, named online matching with stochastic rewards (OMSR, FOCS 2012), for which the optimal competitive ratio is still unknown. We adopt an adversarial RL approach that trains two RL agents adversarially and iteratively: the algorithm agent learns for algorithms with larger competitive ratios, while the adversarial agent learns to produce a family of hard instances. Through such a framework, agents converge at the end with a robust algorithm, which empirically outperforms the state of the art (STOC 2020). Much more significantly, it allows to track how the hard instances are generated. We succeed in distilling two structural properties from the learned graph patterns, which remarkably reduce the action space, and further enable theoretical improvement on the best-known hardness result of OMSR, from $0.621$ (FOCS 2012) to $0.597$. To the best of our knowledge, this gives the first evidence that RL can help enhance the theoretical understanding of an online problem.

Feature-only partition of large graph data in distributed Graph Neural Network (GNN) training offers advantages over commonly adopted graph structure partition, such as minimal graph preprocessing cost and elimination of cross-worker subgraph sampling burdens. Nonetheless, performance bottleneck of GNN training with feature-only partitions still largely lies in the substantial communication overhead due to cross-worker feature fetching. To reduce the communication overhead and expedite distributed training, we first investigate and answer two key questions on convergence behaviors of GNN model in feature-partition based distribute GNN training: 1) As no worker holds a complete copy of each feature, can gradient exchange among workers compensate for the information loss due to incomplete local features? 2) If the answer to the first question is negative, is feature fetching in every training iteration of the GNN model necessary to ensure model convergence? Based on our theoretical findings on these questions, we derive an optimal communication plan that decides the frequency for feature fetching during the training process, taking into account bandwidth levels among workers and striking a balance between model loss and training time. Extensive evaluation demonstrates consistent results with our theoretical analysis, and the effectiveness of our proposed design.

Abstract. Mehta and Panigrahi ( FOCS 2012, IEEE, Piscataway, NJ, 2012, pp. 728–737) introduce the problem of online matching with stochastic rewards, where edges are associated with success probabilities and a match succeeds with the probability of the corresponding edge. It is one of the few online matching problems that have defied the randomized online primal dual framework by Devanur, Jain, and Kleinberg ( SODA 2013, SIAM, Philadelphia, 2013, pp. 101–107) thus far. This paper unlocks the power of randomized online primal dual in online matching with stochastic rewards by employing the configuration linear program rather than the standard matching linear program used in previous works. Our main result is a 0.572 competitive algorithm for the case of vanishing and unequal probabilities, improving the best previous bound of 0.534 by Mehta, Waggoner, and Zadimoghaddam ( SODA 2015, SIAM, Philadelphia, 2015, pp. 1388–1404) and, in fact, is even better than the best previous bound of 0.567 by Mehta and Panigrahi ( FOCS 2012, IEEE, Piscataway, NJ, 2012, pp. 728–737) for the more restricted case of vanishing and equal probabilities. For vanishing and equal probabilities, we get a better competitive ratio of 0.576. Our results further generalize to the vertex-weighted case due to the intrinsic robustness of the randomized online primal dual analysis.

Software-defined Network (SDN), presented to be a novel architecture of network because of its separation of data plane and control plane, brings centralization and extensibility to network management as well as new attacks that exploit the flexibility of SDN. OpenFlow, which is the protocol that is applied by the majority of SDN, leads to the widely used definition of the communication between the controller and the switch resulting in similar implementations regardless of different vendors. In this paper, we focus on the mechanisms of packet processing and topology discovery and their fundamental weaknesses caused by general implementations or device limitations. Despite the common vulnerabilities, the universal standard mechanisms of basic function in SDN also enlighten us to present an automated attack discovery method based on the formal verification with a generic model of SDN system. We describe the abstraction of the SDN components, their key functions, and communications along with the malicious operations that could be executed by malicious hosts and malicious switches and translate them into a formal model of the SDN system. The formal verification carried on with the assertion representing the security properties derived from the common vulnerabilities of the SDN system reports the potential attack paths each of which shows an attack process. Our evaluation shows that our method can discover feasible attack paths efficiently and effectively, with 23 attacks being identified, among which 2 are new. We further demonstrate the practicality of the 2 new attacks.

Abstract. Three decades ago, Karp, Vazirani, and Vazirani [ Proceedings of the 22 nd Annual ACM Symposium on Theory of Computing, 1990, pp. 352–358] defined the online matching problem and gave an optimal [Formula: see text]-competitive algorithm. Fifteen years later, Mehta et al. [ J. ACM, 54 (2007), pp. 22:1–22:19] introduced the first generalization called AdWords driven by online advertising and obtained the optimal [Formula: see text] competitive ratio in the special case of small bids. It has been open ever since whether there is an algorithm for general bids better than the 0.5-competitive greedy algorithm. This paper presents a 0.5016-competitive algorithm for AdWords, answering this open question on the positive end. The algorithm builds on several ingredients, including a combination of the online primal dual framework and the configuration linear program of matching problems recently explored by Huang and Zhang [ Proceedings of the 52 nd ACM Symposium on Theory of Computing, 2020], a novel formulation of AdWords which we call the panorama view, and a generalization of the online correlated selection by Fahrbach et al. [ Proceedings of the 61 st Annual IEEE Symposium on Foundations of Computer Science, 2020], which we call the panoramic online correlated selection.

Mehta and Panigrahi (FOCS 2012) introduce the problem of online matching with stochastic rewards, where edges are associated with success probabilities and a match succeeds with the probability of the corresponding edge. It is one of the few online matching problems that have defied the randomized online primal dual framework by Devanur, Jain, and Kleinberg (SODA 2013) thus far. This paper unlocks the power of randomized online primal dual in online matching with stochastic rewards by employing the configuration linear program rather than the standard matching linear program used in previous works. Our main result is a 0.572 competitive algorithm for the case of vanishing and unequal probabilities, improving the best previous bound of 0.534 by Mehta, Waggoner, and Zadimoghaddam (SODA 2015) and, in fact, is even better than the best previous bound of 0.567 by Mehta and Panigrahi (FOCS 2012) for the more restricted case of vanishing and equal probabilities. For vanishing and equal probabilities, we get a better competitive ratio of 0.576. Our results further generalize to the vertex-weighted case due to the intrinsic robustness of the randomized online primal dual analysis.