We rethink the basic operations, i.e., inner product and matrix multiplication used in neural networks. A quantum-inspired alternative is proposed, utilizing the power of high-dimensional Hilbert space by devising a high-order form of tensor product. We re-parameterize the original (low-order) vectors/matrices into an expressive high-order form, without incurring extra model parameters, and the extra computational overhead is negligible (e.g., about 2%). As an in-place transparent atomic operation, we show its use in the key components in Transformers: token embeddings, attentions (query, key, value) and the MLP. Due to its inherent compatibility to vanilla multiplicative operations, we propose C2Q-SFT, i.e., classic-to-quantum (C2Q) protocol for supervised fine-tuning (SFT): it continues to train a given model by transparently replacing the standard operations with ours. As shown by our experiments, it shows advantages for both training from scratch and fine-tuning on downstream tasks across scales of LLMs. C2Q-SFT consistently outperforms standard SFT, with relative improvements on MMLU (+0.56%) and GSM8k (+0.61%). It sheds light on the innovation of operations in networks, orthogonal to the efforts on new architecture, position encoding, and training algorithms, etc. See project page at: https://github.com/Thinklab-SJTU/LLM/QI-LLM.

The Quadratic Assignment Problem (QAP) has attracted lasting attention for its wide applications and computational challenges. Despite the rich literature in machine learning for QAP, most works often address the problem in the setting of image matching, whereby deep networks could play a vital role in extracting useful features for the subsequent matching. While its power on pure numerical QAP instances is limited in node embedding, often with a vanilla graph neural network. This paper tries to tap the potential of deep nets for QAP, specifically by modifying the input instance, which is orthogonal to previous efforts. Specifically, we develop a bi-level unsupervised framework, where the inner optimization involves trying to solve the modified instance with entropic regularization that can be solved iteratively using the Sinkhorn algorithm without affecting backpropagation by truncating gradients during training. The outer minimization deals with the quadratic objective function of the original QAP. In particular, seeing the intractable scale of the most general form, i.e., Lawler's QAP and the practical utility of the more efficient Koopmans-Beckmann QAP (KBQAP) form for solving other graph and combinatorial problems like TSP and graph edit distance, we embody our network on the KBQAP, and show its strong performance on various benchmarks in our experiments.

Video moment retrieval locates a specified moment by a sentence query. Recent approaches have made remarkable advancements with large-scale video-sentence annotations. These annotations require extensive human labor and expertise, leading to the need for unsupervised fashion. Generating pseudo-supervision from videos is an effective strategy. With the power of the large-scale pre-trained model, we introduce knowledge into constructing pseudo-supervision. The main technical challenge is improving pseudo-supervision diversity and alleviating noise brought by external knowledge. To address these problems, we propose two Knowledge-Based Pseudo-Supervision Construction (KPSC) strategies: KPSC-P and KPSC-F. They all follow two steps: generating diverse samples and alleviating knowledge chaos. The main difference is that the former first learns a representation space with prompt tuning, while the latter directly utilizes data information. KPSC-P has two modules: (1) Proposal Prompt (PP): Generate temporal proposals; (2) Verb Prompt (VP): Generate pseudo-queries with noun-verb patterns. KPSC-F also has two modules: (1) Captioner: Generating candidate queries; (2) Filter: Alleviating knowledge chaos. Thus, our KPSC involves two attempts to extract knowledge from pre-trained models. Extensive experiments show that our attempts outperform the existing unsupervised methods on two public datasets (Charades-STA and ActivityNet-Captions) and perform on par with several methods using stronger supervision.

Deep visual graph matching (GM) is a challenging combinatorial task that involves finding a permutation matrix that indicates the correspondence between keypoints from a pair of images. Like many learning systems, empirical studies have shown that visual GM is susceptible to adversarial attacks, with reliability issues in downstream applications. To the best of our knowledge, certifying robustness for deep visual GM remains an open challenge with two main difficulties: how to handle the paired inputs together with the heavily non-linear permutation output space (especially at large scale), and how to balance the trade-off between certified robustness and matching performance.

Mixup has shown considerable success in mitigating the challenges posed by limited labeled data in image classification. By synthesizing samples through the interpolation of features and labels, Mixup effectively addresses the issue of data scarcity. However, it has rarely been explored in graph learning tasks due to the irregularity and connectivity of graph data. Specifically, in node classification tasks, Mixup presents a challenge in creating connections for synthetic data. In this paper, we propose Geometric Mixup (GeoMix), a simple and interpretable Mixup approach leveraging in-place graph editing. It effectively utilizes geometry information to interpolate features and labels with those from the nearby neighborhood, generating synthetic nodes and establishing connections for them. We conduct theoretical analysis to elucidate the rationale behind employing geometry information for node Mixup, emphasizing the significance of locality enhancement-a critical aspect of our method's design. Extensive experiments demonstrate that our lightweight Geometric Mixup achieves state-of-the-art results on a wide variety of standard datasets with limited labeled data. Furthermore, it significantly improves the generalization capability of underlying GNNs across various challenging out-of-distribution generalization tasks. Our code is available at https://github.com/WtaoZhao/geomix.

Out-of-distribution (OOD) generalization has gained increasing attentions for learning on graphs, as graph neural networks (GNNs) often exhibit performance degradation with distribution shifts. The challenge is that distribution shifts on graphs involve intricate interconnections between nodes, and the environment labels are often absent in data. In this paper, we adopt a bottom-up data-generative perspective and reveal a key observation through causal analysis: the crux of GNNs' failure in OOD generalization lies in the latent confounding bias from the environment. The latter misguides the model to leverage environment-sensitive correlations between ego-graph features and target nodes' labels, resulting in undesirable generalization on new unseen nodes. Built upon this analysis, we introduce a conceptually simple yet principled approach for training robust GNNs under node-level distribution shifts, without prior knowledge of environment labels. Our method resorts to a new learning objective derived from causal inference that coordinates an environment estimator and a mixture-of-expert GNN predictor. The new approach can counteract the confounding bias in training data and facilitate learning generalizable predictive relations. Extensive experiment demonstrates that our model can effectively enhance generalization with various types of distribution shifts and yield up to 27.4% accuracy improvement over state-of-the-arts on graph OOD generalization benchmarks.

Cross-Domain Sequential Recommendation (CDSR) methods aim to tackle the data sparsity and cold-start problems present in Single-Domain Sequential Recommendation (SDSR). Existing CDSR works design their elaborate structures relying on overlapping users to propagate the cross-domain information. However, current CDSR methods make closed-world assumptions, assuming fully overlapping users across multiple domains and that the data distribution remains unchanged from the training environment to the test environment. As a result, these methods typically result in lower performance on online real-world platforms due to the data distribution shifts. To address these challenges under open-world assumptions, we design an Adaptive Multi-Interest Debiasing framework for cross-domain sequential recommendation (AMID), which consists of a multi-interest information module (MIM) and a doubly robust estimator (DRE). Our framework is adaptive for open-world environments and can improve the model of most off-the-shelf single-domain sequential backbone models for CDSR. Our MIM establishes interest groups that consider both overlapping and non-overlapping users, allowing us to effectively explore user intent and explicit interest. To alleviate biases across multiple domains, we developed the DRE for the CDSR methods. We also provide a theoretical analysis that demonstrates the superiority of our proposed estimator in terms of bias and tail bound, compared to the IPS estimator used in previous work. To promote related research in the community under open-world assumptions, we collected an industry financial CDSR dataset from Alipay, called "MYbank-CDR". Extensive offline experiments on four industry CDSR scenarios including the Amazon and MYbank-CDR datasets demonstrate the remarkable performance of our proposed approach. Additionally, we conducted a standard A/B test on Alipay, a large-scale financial platform with over one billion users, to validate the effectiveness of our model under open-world assumptions. Code and dataset are available at https://github.com/WujiangXu/AMID.

We focus on the problem of event sequence clustering with different temporal patterns from the view of Reinforcement Learning (RL), whereby the observed sequences are assumed to be generated from a mixture of latent policies. We propose an Expectation-Maximization (EM) based algorithm to cluster the sequences with different temporal patterns into the underlying policies while simultaneously learning each of the policy model, in E-step estimating the cluster labels for each sequence, in M-step learning the respective policy. For each policy learning, we resort to Inverse Reinforcement Learning (IRL) by decomposing the observed sequence into states (hidden embedding of event history) and actions (time interval to next event) in order to learn a reward function. Experiments on synthetic and real-world datasets show the efficacy of our method against the state-of-the-arts.

Learning to plan and schedule receives increasing attention due to its efficiency in problem-solving and potential to outperform heuristics. In particular, actor-critic-based reinforcement learning (RL) has been widely adopted for uncertain environments. Yet one standing challenge for applying RL to real-world industrial decision-making problems is the high variance during training. Existing efforts design novel value functions to alleviate the issue but still suffer. In this paper, we address this issue from the perspective of adjusting the actor-critic paradigm. We start by making an observation ignored in many industrial problems---the environmental dynamics for an agent consist of two parts physically independent of each other: the exogenous task demand over time and the hard constraint for action. And we theoretically show that decoupling these two effects in the actor-critic technique would reduce variance. Accordingly, we propose to decouple and model them separately in the state transition of the Markov decision process (MDP). In the demand-encoding process, the temporal task demand, e.g., the passengers for elevator scheduling is encoded followed by a critic for scoring. While in the constraint-encoding process, an actor-critic module is adopted for action embedding, and the two critics are then used for a revised advantaged function calculation. Experimental results show that our method can adaptively handle different dynamic planning and scheduling tasks and outperform recent learning-based models and traditional heuristic algorithms.

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.

Industrial SAT formula generation is a critical yet challenging task. Existing SAT generation approaches can hardly simultaneously capture the global structural properties and maintain plausible computational hardness. We first present an in-depth analysis for the limitation of previous learning methods in reproducing the computational hardness of original instances, which may stem from the inherent homogeneity in their adopted split-merge procedure. On top of the observations that industrial formulae exhibit clear community structure and oversplit substructures lead to the difficulty in semantic formation of logical structures, we propose HardSATGEN, which introduces a fine-grained control mechanism to the neural split-merge paradigm for SAT formula generation to better recover the structural and computational properties of the industrial benchmarks. Experiments including evaluations on private and practical corporate testbed show the superiority of HardSATGEN being the only method to successfully augments formulae maintaining similar computational hardness and capturing the global structural properties simultaneously. Compared to the best previous methods, the average performance gains achieve 38.5% in structural statistics, 88.4% in computational metrics, and over 140.7% in the effectiveness of guiding solver tuning by our generated instances. Source code is available at https://github.com/Thinklab-SJTU/HardSATGEN.

Many real-world machine learning problems involve structured prediction beyond categorical labels. However, most existing robustness certification works are devoted to the classification case. It remains open for robustness certification for more general outputs. In this paper, we propose a novel framework of robustness certification for structured prediction problems, where the output space is modeled as a semimetric space with a distance function that satisfies non-negativity and symmetry but not necessarily the triangle inequality. We further develop our tailored certification methods for binary, numerical, and hybrid inputs in structured prediction. Experiment results show that our method achieves tighter robustness guarantees than the SOTA structured certification baseline for numerical inputs (for which it only supports) with ℓ2 norm perturbation when outputs are measured by intersection over union (IoU) similarity, total variation distance, and perceptual distance. Moreover, we achieve good robustness certification for binary inputs with ℓ0 norm perturbation and hybrid inputs with corresponding perturbation when outputs are measured by Manhattan distance.

Learning of network embedding with vector-based node representation has attracted wide attention over the decade. It differs from the general setting of graph node embedding whereby the node attributes are also considered and yet may incur privacy issues. In this paper, we depart from the classic CPU/GPU architecture to consider the well-established network alignment problem based on network embedding, and develop a quantum machine learning approach with a low qubit cost for its near-future applicability on Noisy Intermediate-Scale Quantum (NISQ) devices. Specifically, our model adopts the discrete-time quantum walk (QW) and conducts the QW on the tailored merged network to extract structure information from the two aligning networks without the need for quantum state preparation which otherwise requires high quantum gate cost. Then the quantum states from QW are fed to a quantum embedding ansatz (i.e., parameterized circuit) to learn the latent representation of each node. The key part of our approach is to connect these two quantum modules to achieve a pure quantum paradigm without involving classical modules. To our best knowledge, there has not been any classic-quantum hybrid approach to network embedding, let alone a pure quantum paradigm being free from the bottleneck of communication between classic devices and quantum devices, which is still an open problem. Experimental results on two real-world datasets show the effectiveness of our quantum embedding approach in comparison with classical embedding approaches. Our model is readily and efficiently implemented in Python with a full-amplitude simulation of the QW and the quantum circuit. Therefore, our model can be readily deployed on an existing NISQ device with all the circuits provided, and only 13 qubits are needed in the experiments, which is rarely attained in existing quantum graph learning works.

Graph structure learning is a well-established problem that aims at optimizing graph structures adaptive to specific graph datasets to help message passing neural networks (i.e., GNNs) to yield effective and robust node embeddings. However, the common limitation of existing models lies in the underlying closed-world assumption: the testing graph is the same as the training graph. This premise requires independently training the structure learning model from scratch for each graph dataset, which leads to prohibitive computation costs and potential risks for serious over-fitting. To mitigate these issues, this paper explores a new direction that moves forward to learn a universal structure learning model that can generalize across graph datasets in an open world. We first introduce the mathematical definition of this novel problem setting, and describe the model formulation from a probabilistic data-generative aspect. Then we devise a general framework that coordinates a single graph-shared structure learner and multiple graph-specific GNNs to capture the generalizable patterns of optimal message-passing topology across datasets. The well-trained structure learner can directly produce adaptive structures for unseen target graphs without any fine-tuning. Across diverse datasets and various challenging cross-graph generalization protocols, our experiments show that even without training on target graphs, the proposed model i) significantly outperforms expressive GNNs trained on input (non-optimized) topology, and ii) surprisingly performs on par with state-of-the-art models that independently optimizes adaptive structures for specific target graphs, with notably orders-of-magnitude acceleration for training on the target graph.

Combinatorial drug recommendation involves recommending a personalized combination of medication (drugs) to a patient over his/her longitudinal history, which essentially aims at solving a combinatorial optimization problem that pursues high accuracy under the safety constraint. Among existing learning-based approaches, the association between drug substructures (i.e., a sub-graph of the molecule that contributes to certain chemical effect) and the target disease is largely overlooked, though the function of drugs in fact exhibits strong relevance with particular substructures. To address this issue, we propose a molecular substructure-aware encoding method entitled MoleRec that entails a hierarchical architecture aimed at modeling inter-substructure interactions and individual substructures’ impact on patient’s health condition, in order to identify those substructures that really contribute to healing patients. Specifically, MoleRec learns to attentively pooling over substructure representations which will be element-wisely re-scaled by the model’s inferred relevancy with a patient’s health condition to obtain a prior-knowledge-informed drug representation. We further design a weight annealing strategy for drug-drug-interaction (DDI) objective to adaptively control the balance between accuracy and safety criteria throughout training. Experiments on the MIMIC-III dataset demonstrate that our approach achieves new state-of-the-art performance w.r.t. four accuracy and safety metrics. Our source code is publicly available at https://github.com/yangnianzu0515/MoleRec.

Anomalies are ubiquitous in real-world time-series data which call for effective and timely detection, especially in an unsupervised setting for labeling cost saving. In this paper, we develop an unsupervised density reconstruction model for multi-dimensional time-series anomaly detection. In particular, it directly handles an important realistic setting that the detection is achieved towards raw time-series contaminated with noise for training, in contrast to most existing anomaly detection works that assume the training data is in general clean i.e. not contaminated with anomaly. It extends recent advancements in deep generative models and state space models to achieve robust anomaly detection. Our approach comprises of a novel state space based generative model, a filtering based inference model, together with a carefully-designated emission model based on robust statistics theory. Extensive experimental results are conducted to show that our approach can adapt to complex patterns even given severely contaminated training data. We also develop visualization techniques to help better understand the behavior of the anomaly detection models. Empirical results show that our method outperforms state-of-the-arts on both synthetic and real-world datasets.

Time-series and event sequences are widely collected data types in real-world applications. Modeling and forecasting of such temporal data play an important role in an informed decision-making process. A major limitation of previous methods is that they either focus on time-series or events, rather than the combination of the two worlds. In fact, the two types of data often provide complementary information, emphasizing the necessity of jointly modeling the both. In this paper, we propose the RNN-ODE collaborative model for joint modeling and forecasting of heterogeneous time-series and event sequence data, which combines several useful techniques from both Bayesian and deep learning for its interpretability. Specifically, we devise a tailored encoder to combine the advances in deep temporal point processes models and variational recurrent neural networks. To predict the probability of event occurrence over an arbitrary continuous-time horizon, we base our model on the mathematical foundation of Neural Ordinary Differential Equations (NODE). Extensive experimental results on simulations and real data sets show that compared with existing methods, our integrated approach can achieve more competitive forecasting performance of both time-series and event sequences.

Skip-gram models are popular in large-scale network embedding for their cost-effectiveness. The objectives of many skip-gram based methods relate to the word2vec model which closely relates to Noise Contrastive Estimation (NCE). Among existing embedding methods, the differences mostly lie in how the node neighborhood is modeled e.g. by different ways of random walk, which leads to different learning strategies. Orthogonal to these efforts, we take a unified view that the NCE based methods commonly involve two basic NCE components in the learning objective. This perspective allows a natural generalization of the objectives by taking different forms of scoring function in the NCE components. We theoretically analyze how the vanilla NCE-based objectives suffer from the slow convergence speed and challenge in first-/second-order proximity preservation. We also prove the fundamental difficulty for NCE methods to capture non-linearity of complex networks. To mitigate such issues, we devise a general distance-based term added to the used NCE term, inspired by its physical meaning. The distance functions include Wasserstein-k distance and Laplacian/Gaussian kernel functions, with relatively little additional time overhead. The effectiveness of our approach is verified both by prototype examples as well as real-world datasets, for the task of node classification and network reconstruction.

Graph Neural Networks (GNNs) are one of the prominent methods to solve semi-supervised learning on graphs. However, most of the existing GNN models often need sufficient observed data to allow for effective learning and generalization. In real-world scenarios where complete input graph structure and sufficient node labels might not be achieved easily, GNN models would encounter with severe performance degradation. To address this problem, we propose WSGNN, short for weakly-supervised graph neural network. WSGNN is a flexible probabilistic generative framework which harnesses variational inference approach to solve graph semi-supervised learning in a label-structure joint estimation manner. It collaboratively learns task-related new graph structure and node representations through a two-branch network, and targets a composite variational objective derived from underlying data generation distribution concerning the inter-dependence between scarce observed data and massive missing data. Especially, under weakly-supervised low-data regime where labeled nodes and observed edges are both very limited, extensive experimental results on node classification and link prediction over common benchmarks demonstrate the state-of-the-art performance of WSGNN over strong competitors. Concretely, when only 1 label per class and 1% edges are observed on Cora, WSGNN maintains a decent 52.00% classification accuracy, exceeding GCN by 75.6%.

The adversarial attack reveals the vulnerability of deep models by incurring test domain shift, while delusive attack relieves the privacy concern about personal data by injecting malicious noise into the training domain to make data unexploitable. However, beyond their successful applications, the two attacks can be easily defended by adversarial training (AT). While AT is not the panacea, it suffers from poor generalization for robustness. For the limitations of attack and defense, we argue that to fit data well, DNNs can learn the spurious relations between inputs and outputs, which are consequently utilized by the attack and defense and degrade their effectiveness, and DNNs can not easily capture the causal relations like humans to make robust decisions under attacks. In this paper, to better understand and improve attack and defense, we first take a bottom-up perspective to describe the correlations between latent factors and observed data, then analyze the effect of domain shift on DNNs induced by attack and finally develop our causal graph, namely Domain-attack Invariant Causal Model (DICM). Based on DICM, we propose a coherent causal invariant principle, which guides our algorithm design to infer the human-like causal relations. We call our algorithm Domain-attack Invariant Causal Learning (DICE) and the experimental results on two attacks and one defense task verify its effectiveness.

Graph representation learning has been extensively studied, and recent models can well incorporate both node features and graph structures. Despite these progress, the inherent scalability challenge for classical computers of processing graph data and solving the downstream tasks (many are NP-hard) is still a bottleneck for existing classical graph learning models. On the other hand, quantum computing is known a promising direction for its theoretically verified scalability as well as the increasing evidence for the access to physical quantum machine in near-term. Different from many existing classical-quantum hybrid machine learning models on graphs, in this paper we take a more aggressive initiative for developing a native quantum paradigm for (attributed) graph representation learning, which to our best knowledge, has not been fulfilled in literature yet. Specifically, our model adopts the well-established theory and technique in quantum computing e.g. quantum random walk, and adapt it to the attributed graph. Then the node attribute quantum state sequence is fed into a quantum recurrent network to obtain the final node embedding. Experimental results on three public datasets show the effectiveness of our quantum model which also outperforms a classical learning approach GraphRNA notably in terms of efficiency even on a classical computer. Though it is still restricted to the classical loss-based learning paradigm with gradient descent for model parameter training, while our computing scheme is compatible with quantum computing without involving classical computers. This is in fact largely in contrast to many hybrid quantum graph learning models which often involve many steps and modules having to be performed on classical computers.

Negative pairs, especially hard negatives as combined with common negatives (easy to discriminate), are essential in contrastive learning, which plays a role of avoiding degenerate solutions in the sense of constant representation across different instances. Inspired by recent hard negative mining methods via pairwise mixup operation in vision, we propose M-Mix, which dynamically generates a sequence of hard negatives. Compared with previous methods, M-Mix mainly has three features: 1) adaptively choose samples to mix; 2) simultaneously mix multiple samples; 3) automatically assign different mixing weights to the selected samples. We evaluate our method on two image datasets (CIFAR-10, CIFAR-100), five node classification datasets (PPI, DBLP, Pubmed, etc), five graph classification datasets (IMDB, PTC_MR, etc), and two downstream combinatorial tasks (graph edit distance and node clustering). Results show that it achieves state-of-the-art performance under self-supervised settings. Code is available at: https://github.com/Sherrylone/m-mix.

Capturing the dynamics in user preference is crucial to better predict user future behaviors because user preferences often drift over time. Many existing recommendation algorithms – including both shallow and deep ones – often model such dynamics independently, i.e., user static and dynamic preferences are not modeled under the same latent space, which makes it difficult to fuse them for recommendation. This paper considers the problem of embedding a user's sequential behavior into the latent space of user preferences, namelytranslating sequence to preference. To this end, we formulate the sequential recommendation task as a dictionary learning problem, which learns: 1) a shareddictionary matrix, each row of which represents a partial signal of user dynamic preferences shared across users; and 2) aposterior distribution estimatorusing a deep autoregressive model integrated with Gated Recurrent Unit (GRU), which can select related rows of the dictionary to represent a user's dynamic preferences conditioned on his/her past behaviors. Qualitative studies on the Netflix dataset demonstrate that the proposed method can capture the user preference drifts over time and quantitative studies on multiple real-world datasets demonstrate that the proposed method can achieve higher accuracy compared with state-of-the-art factorization and neural sequential recommendation methods.

Link prediction and network alignment are two fundamental and interleaved tasks in network analysis. In this paper, we propose a novel cross-network embedding model under the Skip-gram framework, which alternately performs link prediction and network alignment by joint optimization. Vertex sequences, obtained via a biased random walk based on empirical mixture distributions, are used to train a Skip-gram based node embedding model. On one hand, based on the similarity in embedding space, network alignment can be effectively performed either with the initial ground truth alignments as seeds or from scratch. On the other hand, the proposed link prediction model involves training a supervised classifier by sampling a set of positive and negative edges. We also modify and incorporate the Collective Link Fusion (CLF) method under a Skip-gram framework and show that the new method can achieve better results in both tasks. Extensive experimental results show the state-of-the-art performance of our methods.

Temporal point process (TPP) is an expressive tool for modeling the temporal pattern of event sequences. However, discovering temporal patterns for event sequences clustering is rarely studied in TPP modeling. To solve this problem, we take a reinforcement learning view whereby the observed sequences are assumed to be generated from a mixture of latent policies. The purpose is to cluster the sequences with different temporal patterns into the underlying policies while learning each of the policy model. The flexibility of our model lies in: i) all the components are networks including the policy network for modeling the temporal point process; ii) to handle varying-length event sequences, we resort to inverse reinforcement learning by decomposing the observed sequence into states (RNN hidden embedding of history) and actions (time interval to next event) in order to learn a reward function, it helps to achieve better performance or increasing efficiency compared to existing methods using rewards over the entire sequence such as log-likelihood or Wasserstein distance. We adopt an Expectation-Maximization algorithm, in E-step estimating the cluster labels for each sequence, in M-step aiming to learn the respective policy. Extensive experiments on synthetic and real-world datasets show the efficacy of our method against the state-of-the-arts.

Multi-order proximity is useful for effective network embedding. In contrast to many previous works that only consider order-level weights, this paper proposes to explore a more expressive node-level weighting mechanism to encode the diverse local structure, with a scalable and theoretically justified sampling strategy for its learning. Specifically, we start with a formal definition of multi-order proximity matrix which leads to our new multi-order objective based on Laplacian Eigenmaps and Skip-Gram. Then we instantiate the node-specific multi-order weights in the objective with the help of neighborhood size estimation, which indicates node-specific multi-order information. For objective learning, it is implicitly fulfilled with our proposed branching tree-like random walk strategy termed by BTWalk, which differs from the dominant chain-like walk in existing sampling techniques. BTWalk is designed by a synergetic combination of BFS (breadth-first search) and DFS (depth-first search), which is modulated according to the weights of the considered proximity orders. We theoretically analyze its cost-efficiency, and further propose the so-called Vec4Cross framework that incorporates joint node embedding and network alignment for two partially overlapped networks based on the seed matchings, whereby BTWalk is also adopted for embedding. Promising experimental results are obtained on real-world datasets across popular tasks.

Sequential Recommendation aims to recommend items that a target user will interact with in the near future based on the historically interacted items. While modeling temporal dynamics is crucial for sequential recommendation, most of the existing studies concentrate solely on the user side while overlooking the sequential patterns existing in the counterpart, i.e., the item side. Although a few studies investigate the dynamics involved in the dual sides, the complex user-item interactions are not fully exploited from a global perspective to derive dynamic user and item representations. In this paper, we devise a novel Dynamic Representation Learning model for Sequential Recommendation (DRL-SRe). To better model the user-item interactions for characterizing the dynamics from both sides, the proposed model builds a global user-item interaction graph for each time slice and exploit time-sliced graph neural networks to learn user and item representations. Moreover, to enable the model to capture fine-grained temporal information, we propose an auxiliary temporal prediction task over consecutive time slices based on temporal point process. Comprehensive experiments on three public real-world datasets demonstrate DRL-SRe outperforms the state-of-the-art sequential recommendation models with a large margin.

In spite of the success of existing meta reinforcement learning methods, they still have difficulty in learning a meta policy effectively for RL problems with sparse reward. In this respect, we develop a novel meta reinforcement learning framework called Hyper-Meta RL(HMRL), for sparse reward RL problems. It is consisted with three modules including the cross-environment meta state embedding module which constructs a common meta state space to adapt to different environments; the meta state based environment-specific meta reward shaping which effectively extends the original sparse reward trajectory by cross-environmental knowledge complementarity and as a consequence the meta policy achieves better generalization and efficiency with the shaped meta reward. Experiments with sparse-reward environments show the superiority of HMRL on both transferability and policy learning efficiency.

Despite its success in learning network node representations, network embedding is still relatively new for multiplex networks (MNs) with multiple types of edges. In such networks, the inter-layer anchor links are usually missing, which represent the alignment relations between nodes on different layers and are a crucial prerequisite for many cross-network applications like network alignment. For mining such anchor links between layers for MNs, multiplex network embedding (MNE) has become one of the most promising techniques. In this paper, we consider two problems for MNs: 1) edges can be missing to different extent, and data augmentation may mitigate this issue; 2) the known alignment anchor links between layers can be misleading since the behaviors of nodes on different layers are not always consistent, so the most informative ones should be emphasized compared with those misleading ones. However, most existing works neglect the two problems and simply 1) adopt one structural view for all the layers (e.g. random walk with the same window size) and 2) equally extract information from all the anchor links. We propose an end-to-end contrastive framework called cM2NE for MNE, utilizing multiple structural views for each layer and learning with several plug-in components for different scenarios. Through end-to-end optimization on three levels, the intra-view, inter-view, and inter-layer level, our framework achieves to select the fitted views for different layers and maximize the inter-layer mutual information by emphasizing those most informative anchor links. Extensive experimental results on real-world datasets for node classification and multi-network alignment show that our approach consistently outperforms peer methods.

Selecting elements for graphic design is essential for ensuring a correct understanding of clients' requirements as well as improving the efficiency of designers before a fine-designed process. Some semi-automatic design tools proposed layout templates where designers always select elements according to the rectangular boxes that specify how elements are placed. In practice, layout and element selection are complementary. Compared to the layout which can be readily obtained from pre-designed templates, it is generally time-consuming to mindfully pick out suitable elements, which calls for an automation of elements selection. To address this, we formulate element selection as a sequential decision-making process and develop a deep element selection network (DESN). Given a layout file with annotated elements, new graphical elements are selected to form graphic designs based on aesthetics and consistency criteria. To train our DESN, we propose an end-to-end, reinforcement learning based framework, where we design a novel reward function that jointly accounts for visual aesthetics and consistency. Based on this, visually readable and aesthetic drafts can be efficiently generated. We further contribute a layout-poster dataset with exhaustively labeled attributes of poster key elements. Qualitative and quantitative results indicate the efficacy of our approach.

Ensemble matrix approximation (MA) methods have achieved promising performance in collaborative filtering, many of which perform matrix approximation on multiple submatrices of user-item ratings in parallel and then combine the predictions from the sub-models for higher efficiency. However, data partitioning could lead to suboptimal accuracy due to the lack of capturing structural information related to most or all users/items. This paper proposes a new ensemble learning framework, in which the local models and global models are synergetically updated from each other. This makes it possible to capture both local associations in user-item subgroups and global structures over all users and items. Experiments on three real-world datasets demonstrate that the proposed method outperforms six state-of-the-art methods in recommendation accuracy with decent scalability.

Real-world entities' behaviors, associated with their side information, are often recorded over time as asynchronous event sequences. Such event sequences are the basis of many practical applications, neural spiking train study, earth quack prediction, crime analysis, infectious disease diffusion forecasting, condition-based preventative maintenance, information retrieval and behavior-based network analysis and services, etc. Temporal point process (TPP) is a principled mathematical tool for the modeling and learning of asynchronous event sequences, which captures the instantaneous happening rate of the events and the temporal dependency between historical and current events. TPP provides us with an interpretable model to describe the generative mechanism of event sequences, which is beneficial for event prediction and causality analysis. Recently, it has been shown that TPP has potentials to many machine learning and data science applications and can be combined with other cutting-edge machine learning techniques like deep learning, reinforcement learning, adversarial learning, and so on.

Understanding a mobile user's behavior, e.g., to infer if she is exercising in a gym or dining in a restaurant, is the key to a variety of applications. However, in many real-world scenarios, precisely determining user visitation is extremely challenging due to the uncertainty present in mobile location updates, where errors can be hundreds of meters or even more. We consider the location uncertainty circle determined by the reported location coordinates as the center and the associated location error as the radius. Such a location uncertainty circle is likely to cover multiple location categories, especially in densely populated areas. Worse still, in many cases, mobile users are anonymous, and we have no access to their personal information or other labeled data, which compels us to develop an unsupervised learning approach to solve this problem. Using a user-time-location category tensor, we capture the user behavior and propose a novel tensor factorization framework to accurately infer the location categories visited by mobile users. This framework leverages several key observations including the negative-unlabeled nature of the data and the intrinsic correlations between users. Also, the proposed algorithm can predict where users are even in the absence of location information. To efficiently solve the proposed framework, we propose a parameter-free and scalable optimization algorithm by effectively exploring the sparse and low-rank structure of the tensor. Our empirical studies show that the proposed algorithm is both effective and scalable: it can solve problems with millions of users and billions of location updates, and also provide superior prediction accuracies on real-world location update and check-in datasets.

At large and popular conferences, it is not uncommon for attendees to feel overwhelmed and lost while trying to navigate through many parallel sessions. In this paper, we present a conference session recommender system. In contrast to the conventional query-search model where a system passively engages with users, Session Expert actively interacts with users via natural, human-like conversations and provides personalized recommendations. The underlying session recommender engine is designed to handle the cold start problem, and is lightweight to enable real-time session recommendations and rationale-aware response generation. Specifically, the recommender system alleviates the cold start problem by transferring knowledge from another similar conference in an offline setting. This step is achieved by first exploiting a positive-unlabeled (PU) learning model to reveal the underlying user interest from the historical enrollment data, and then modeling a bilinear relationship which captures how user and session features influence users’ interests. Given the learned bilinear model, recommendation scores and rationale can be generated online as it only involves a few matrix-vector multiplications which can be computed efficiently.

This paper presents a factorial marked temporal point process model and presents efficient learning methods. In conventional (multi-dimensional) marked temporal point process models, an event is often encoded by a single discrete variable (marker). We describe the factorial marked point processes whereby time-stamped event is factored into multiple markers. Accordingly the size of the infectivity matrix modeling the effect between pairwise markers is in exponential order regarding the number of discrete markers. We propose a decoupled learning method with two learning procedures: i) directly solving the model based on two techniques: Alternating Direction Method of Multipliers and Fast Iterative Shrinkage-Thresholding Algorithm; ii) involving a reformulation that transforms the original problem into a Logistic Regression model for more efficient learning. Moreover, a sparse group regularizer is added to identify the key profile features and event labels. Empirical results on real world datasets demonstrate the efficiency of our decoupled and reformulated method.

Extreme multi-label learning (XML) or classification has been a practical and important problem since the boom of big data. The main challenge lies in the exponential label space which involves 2L possible label sets especially when the label dimension L is huge, e.g., in millions for Wikipedia labels. This paper is motivated to better explore the label space by originally establishing an explicit label graph. In the meanwhile, deep learning has been widely studied and used in various classification problems including multi-label classification, however it has not been properly introduced to XML, where the label space can be as large as in millions. In this paper, we propose a practical deep embedding method for extreme multi-label classification, which harvests the ideas of non-linear embedding and graph priors-based label space modeling simultaneously. Extensive experiments on public datasets for XML show that our method performs competitive against state-of-the-art result.

Key frames are playing a very important role for many video applications, such as on-line movie preview and video information retrieval. Although a number of key frame selection methods have been proposed in the past, existing technologies mainly focus on how to precisely summarize the video content, but seldom take the user preferences into consideration. However, in real scenarios, people may cast diverse interests on the contents even for the same video, and thus they may be attracted by quite different key frames, which makes the selection of key frames an inherently personalized process. In this paper, we propose and investigate the problem of personalized key frame recommendation to bridge the above gap. To do so, we make use of video images and user time-synchronized comments to design a novel key frame recommender that can simultaneously model visual and textual features in a unified framework. By user personalization based on her/his previously reviewed frames and posted comments, we are able to encode different user interests in a unified multi-modal space, and can thus select key frames in a personalized manner, which, to the best of our knowledge, is the first time in the research field of video content analysis. Experimental results show that our method performs better than its competitors on various measures.

Graph matching, which refers to a class of computational problems of finding an optimal correspondence between the vertices of graphs to minimize (maximize) their node and edge disagreements (affinities), is a fundamental problem in computer science and relates to many areas such as combinatorics, pattern recognition, multimedia and computer vision. Compared with the exact graph (sub)isomorphism often considered in a theoretical setting, inexact weighted graph matching receives more attentions due to its flexibility and practical utility. A short review of the recent research activity concerning (inexact) weighted graph matching is presented, detailing the methodologies, formulations, and algorithms. It highlights the methods under several key bullets, e.g. how many graphs are involved, how the affinity is modeled, how the problem order is explored, and how the matching procedure is conducted etc. Moreover, the research activity at the forefront of graph matching applications especially in computer vision, multimedia and machine learning is reported. The aim is to provide a systematic and compact framework regarding the recent development and the current state-of-the-arts in graph matching.

Detecting anomalous events from spatial data has important applications in real world. The spatial scan statistic methods are popular in this area. With maximizing the spatial statistical discrepancy by comparing observed data with a given baseline data distribution, significant spatial overdensity and underdensity can be detected. In reality, the spatial discrepancy is often irregularly shaped and has a structure of multiple spatial scales. However, a large-scale discrepancy pattern may not be significant when conducting fine granularity analysis. Meanwhile, local irregular boundaries of a maximized discrepancy cannot be well approximated with a coarse granularity analysis. Existing methods mostly work either on a fixed granularity, or with a regularly shaped scanning window. Thus, they have difficulties in characterizing such flexible spatial discrepancies. To solve the problem, in this paper we propose a novel discrepancy maximization algorithm, RefineScan. A grid hierarchy encoding multi-scale information is employed, making the algorithm capable of maximizing spatial discrepancies with multi-scale structures and irregular shapes. Experiments on a wide range of datasets demonstrate the advantages of RefineScan over the state-of-the-art algorithms: It always finds the largest discrepancy scores and remarkably better characterizes multi-scale discrepancy boundaries. Theoretical and empirical analyses also show that RefineScan has a moderate computational complexity and a good scalability.