Despite the rich works on machine learning (ML) for combinatorial optimization (CO), a unified, principled framework remains lacking. This study utilizes the Travelling Salesman Problem (TSP) as a major case study, with adaptations demonstrated for other CO problems, dissecting established mainstream learning-based solvers to outline a comprehensive design space. We present ML4TSPBench, which advances a unified modular streamline incorporating existing technologies in both learning and search for transparent ablation, aiming to reassess the role of learning and discern which parts of existing techniques are genuinely beneficial and which are not. This further leads to the investigation of desirable principles of learning designs and the exploration of concepts guiding method designs. We demonstrate the desirability of principles such as joint probability estimation, symmetry solution representation, and online optimization for learning-based designs. Leveraging the findings, we propose enhancements to existing methods to compensate for their missing attributes, thereby advancing performance and enriching the technique library. From a higher viewpoint, we also uncover a performance advantage in non-autoregressive and supervised paradigms compared to their counterparts. The strategic decoupling and organic recompositions yield a factory of new TSP solvers, where we investigate synergies across various method combinations and pinpoint the optimal design choices to create more powerful ML4TSP solvers, thereby facilitating and offering a reference for future research and engineering endeavors.

Technological advances have led to the emergence of an increasing number of applications requiring the analysis of datastreams, that are characterized by an indefinitely long and time-evolving sequence, particularly in the healthcare domain. In such applications, the status of a stream can alternate, possibly many times, between a regular status and an irregular status. Consequently, it is necessary to develop statistical methodologies that constantly detect multiple changepoints in an online manner. While we may employ conventional methods of sequential change detection to trigger signals after the change occurs, no online procedure is available to quantify the uncertainty of the detected changes. In this work, we fill this gap by framing online multiple changepoint detection into an online multiple testing problem and proposing a new framework to test the null hypothesis that there is no change between neighboring signalled points. To obtain valid p-values for online multiple testing, we propose a data-fission-based procedure that is a simple yet effective way of dealing with the post-detection uncertainty quantification. It is shown that popular online false discovery rate control methods with those p-values can achieve finite-sample false discovery rate control. We evaluate the proposed method in simulation studies. The method is applied to health monitoring dataset, alleviating the false alarm issue in online data analysis.

Predictive combinatorial optimization, where the parameters of combinatorial optimization (CO) are unknown at the decision-making time, is the precise modeling of many real-world applications, including energy cost-aware scheduling and budget allocation on advertising. Tackling such a problem usually involves a prediction model and a CO solver. These two modules are integrated into the predictive CO pipeline following two design principles: ''Predict-then-Optimize (PtO)'', which learns predictions by supervised training and subsequently solves CO using predicted coefficients, while the other, named ''Predict-and-Optimize (PnO)'', directly optimizes towards the ultimate decision quality and claims to yield better decisions than traditional PtO approaches. However, there lacks a systematic benchmark of both approaches, including the specific design choices at the module level, as well as an evaluation dataset that covers representative real-world scenarios. To this end, we develop a modular framework to benchmark 11 existing PtO/PnO methods on 8 problems, including a new industrial dataset for combinatorial advertising that will be released. Our study shows that PnO approaches are better than PtO on 7 out of 8 benchmarks, but there is no silver bullet found for the specific design choices of PnO. A comprehensive categorization of current approaches and integration of typical scenarios are provided under a unified benchmark. Therefore, this paper could serve as a comprehensive benchmark for future PnO approach development and also offer fast prototyping for application-focused development. The code is available at \url{https://github.com/Thinklab-SJTU/PredictiveCO-Benchmark}.

Dynamic graphs arise in various real-world applications, and it is often welcomed to model the dynamics in continuous time domain for its flexibility. This paper aims to design an easy-to-use pipeline (EasyDGL which is also due to its implementation by DGL toolkit) composed of three modules with both strong fitting ability and interpretability, namely encoding, training and interpreting: i) a temporal point process (TPP) modulated attention architecture to endow the continuous-time resolution with the coupled spatiotemporal dynamics of the graph with edge-addition events; ii) a principled loss composed of task-agnostic TPP posterior maximization based on observed events, and a task-aware loss with a masking strategy over dynamic graph, where the tasks include dynamic link prediction, dynamic node classification and node traffic forecasting; iii) interpretation of the outputs (e.g., representations and predictions) with scalable perturbation-based quantitative analysis in the graph Fourier domain, which could comprehensively reflect the behavior of the learned model. Empirical results on public benchmarks show our superior performance for time-conditioned predictive tasks, and in particular EasyDGL can effectively quantify the predictive power of frequency content that a model learns from evolving graph data.

The identification of changes in linear models is a fundamental problem encountered in various applications. Traditional methods often encounter difficulties when attempting to identify changepoints in the presence of heavy-tailed distribution. This paper focuses on the study of high-dimensional linear models with multiple structural changes in the presence of heavy-tailed errors, especially for those errors without moment conditions. We first propose a robust method that simultaneously estimates regression coefficient and changepoint by incorporating$\ell _{1}$norm penalized Wilcoxon rank loss minimization for single changepoint estimation. Furthermore, we extend it to multiple changepoints estimation based on a novel two-step moving window mechanism that combines fast coarse grid screening and an efficient refinement. Our method exhibits robustness against heavy-tailed random errors while maintaining high efficiency for normal random errors. Theoretically, we establish non-asymptotic error bounds with a near-oracle rate for the estimates of both the coefficient and the changepoint under weak conditions on the random error distribution. Numerical results provide evidence for the validity and effectiveness of the proposed approach.

Spectral methods for graph neural networks (GNNs) have achieved great success. Despite their success, many works have shown that existing approaches are mainly focused on low-frequency information which may not be pertinent to the task at hand. Recent efforts have been made to design new graph filters for wider frequency profiles, but it remains an open problem how to learn multi-scale disentangled node embeddings in the graph Fourier domain. In this paper, we propose a graph (signal) sampling and filtering framework, entitled Pyramid Graph Neural Network (PyGNN), which follows the Downsampling-Filtering-Upsampling-Decoding scheme. To be specific, we develop an ω-bandlimited downsampling approach to split input graph into subgraphs for the reduction of high-frequency components, then perform spectral graph filters on subgraphs to achieve node embeddings with different frequency bands, and propose a Laplacian smoothing-based upsampling approach to extrapolate the node embedding on subgraphs to the full set of vertices on the original graph. In the end, we add frequency-aware gated units to decode node embeddings of different frequencies for downstream tasks. Results on both homophilic and heterophilic graph datasets show its superiority over state-of-the-art methods.

The NP-hard combinatorial Virtual Network Embedding (VNE) Problem refers to finding the node and edge mapping between a virtual net (request) and the physical net (resource). Learning-based methods are recently devised beyond traditional heuristic solvers. However, the efficiency and scalability hinder its applicability as reinforcement learning (RL) is often adopted in an auto-regressive node-by-node mapping manner to handle complex mapping constraints, for each coming request for mapping. Moreover, existing learning-based works often independently consider each online request, limiting the long-term online service performance. In this paper, we present a synergistic Global-And-Local learning approach for the VNE problem (GAL-VNE). At the global level across requests, RL is employed to capture the cross-request relation for better global resource accommodation to improve overall performance. At the local level within each request, we aim to replace the sequential decision-making procedure which relies much on the network size, with a more efficient one-shot solution generation scheme. The main challenge for such a one-shot model is how to encode the constraints under an end-to-end learning and inference paradigm. Accordingly, within the "rank-then-search" paradigm, we propose to first pretrain a graph neural network (GNN)-based node ranker with imitation supervision from an off-the-shelf solver (moderately expensive yet high quality), which is meanwhile regularized by a neighboring smooth prior. Then RL is used to finetune the GNN ranker whose supervision directly refers to the final (undifferentiable) business objectives concerning revenue and cost, etc. Experiments on benchmarks show that our method outperforms classic and learning-based methods in both efficacy and efficiency.

User interests are usually dynamic in the real world, which poses both theoretical and practical challenges for learning accurate preferences from rich behavior data. Among existing user behavior modeling solutions, attention networks are widely adopted for its effectiveness and relative simplicity. Despite being extensively studied, existing attentions still suffer from two limitations: i) conventional attentions mainly take into account the spatial correlation between user behaviors, regardless the distance between those behaviors in the continuous time space; and ii) these attentions mostly provide a dense and undistinguished distribution over all past behaviors then attentively encode them into the output latent representations. This is however not suitable in practical scenarios where a user’s future actions are relevant to a small subset of her/his historical behaviors. In this paper, we propose a novel attention network, named \textit{self-modulating attention}, that models the complex and non-linearly evolving dynamic user preferences. We empirically demonstrate the effectiveness of our method on top-N sequential recommendation tasks, and the results on three large-scale real-world datasets show that our model can achieve state-of-the-art performance.