Building a general model capable of analyzing human trajectories across different geographic regions and different tasks becomes an emergent yet important problem for various applications. However, existing works suffer from the generalization problem, i.e., they are either restricted to train for specific regions or only suitable for a few tasks. Given the recent advances of multimodal large language models (MLLMs), we raise the question: can MLLMs reform current trajectory data mining and solve the problem? Nevertheless, due to the modality gap of trajectory, how to generate task-independent multimodal trajectory representations and how to adapt flexibly to different tasks remain the foundational challenges. In this paper, we propose Traj-MLLM, which is the first general framework using MLLMs for trajectory data mining. By integrating multiview contexts, Traj-MLLM transforms raw trajectories into interleaved image-text sequences while preserving key spatial-temporal characteristics, and directly utilizes the reasoning ability of MLLMs for trajectory analysis. Additionally, a prompt optimization method is proposed to finalize data-invariant prompts for task adaptation. Extensive experiments on four publicly available datasets show that Traj-MLLM outperforms state-of-the-art baselines by 48.05%, 15.52%, 51.52%, 1.83% on travel time estimation, mobility prediction, anomaly detection and transportation mode identification, respectively. Traj-MLLM achieves these superior performances without requiring any training data or fine-tuning the MLLM backbones.

The video game industry has emerged as a significant economic force, driving extensive research on optimizing the gaming environment and improving gaming experiences. Among these endeavors, player behavior representation learning has become a critical way to model valuable player properties and is beneficial for a wide range of downstream tasks. However, some common factors, such as login rewards and daily tasks, can trigger similar behaviors among different players, which are informative and noisy for learning high-quality player behavior representations. Existing methods ignore the low signal-to-noise ratio in player behavior data and waste too much modeling capacity on less informative behaviors, resulting in their learned representations being noisy. In this paper, we propose a novel model for Denoised Player Behavior representation Learning, namely DPBL, which consists of two key modules. The first module extracts various player behavior patterns and isolates them from less informative noise. The second module utilizes the extracted patterns to refine the embedding of each behavior and eliminates noise. To optimize DPBL, two contrastive learning strategies are proposed to identify the noise that should be eliminated and to learn distinguishable representations, respectively. With the above design, DPBL is capable of mitigating the impact of noise in the data and learning high-quality representations that effectively capture player characteristics. We conducted extensive experiments on two real-world datasets, and DPBL outperforms all baselines on various downstream tasks with an improvement of 1.4% ∼ 18.1%. The results also show that DPBL achieves an improvement of 5.6% ∼ 23.0% in the denoising experiments, which proves that DPBL is more robust to noisy behaviors. Code is available at https://github.com/LwbXc/DPBL.

Flight trajectory data plays a vital role in the traffic management community, especially for downstream tasks such as trajectory prediction, flight recognition, and anomaly detection. Existing works often utilize handcrafted features and design models for different tasks individually, which heavily rely on domain expertise and are hard to extend. We argue that different flight analysis tasks share the same useful features of the trajectory. Jointly learning a unified representation for flight trajectories could be beneficial for improving the performance of various tasks. However, flight trajectory representation learning (TRL) faces two primary challenges, \ie unbalanced behavior density and 3D spatial continuity, which disable recent general TRL methods. In this paper, we propose Flight2Vec, a flight-specific representation learning method to address these challenges. Specifically, a behavior-adaptive patching mechanism is used to inspire the learned representation to pay more attention to behavior-dense segments. Moreover, we introduce a motion trend learning technique that guides the model to memorize not only the precise locations, but also the motion trend to generate better representations. Extensive experimental results demonstrate that Flight2Vec significantly improves performance in downstream tasks such as flight trajectory prediction, flight recognition, and anomaly detection.

Adversarial purification has emerged as a critical defense mechanism against various adversarial attacks on deep neural networks, however, such category of diffusion-based purification in the pixel space confronts two challenges while applying into today’s large vision transformers: i) the distributional divergence between adversarial and clean examples in high-dimensional image manifold; and ii) the prohibitive computational cost while processing high-resolution images. To address the predicament, we in this paper focus on the transformer-based visual encoders commonly employed in large Vision-Language Models (VLMs), and propose a novel Latent Diffusion-based Purification (LDP) mechanism through leveraging the latent space to pave the gap between adversarial distribution and clean distribution. Resorting to projecting adversarial input into a low-dimensional latent representation, our proposed LDP not only suppresses the off-manifold perturbations to achieve accelerated denoising, but also preserves critical semantic features by aligning input with the priori high-quality visual representations. Multi-facet experiments over both proactive robustness enhancement and post-attack purification demonstrate that our LDP has a superior performance in terms of effectiveness and efficiency.

Trajectory clustering is an essential task in spatial data mining. To address this problem, many previous studies either extended traditional clustering algorithms with spatial features of trajectories or employed deep learning models for representation learning. However, one common drawback of existing solutions is that the final number of clusters needs to be specified as part of the input. In this paper, we proposed Tra-jDPM, an end-to-end framework for non-parametric trajectory clustering. We come up with two novel loss functions to pretrain a trajectory encoder so as to generate discriminative trajectory representation. Moreover, we employed the neural Dirichlet process mixture model to perform non-parametric clustering based on trajectory embeddings. In this process, the trajectory encoder can also be jointly optimized to improve the performance by a contrastive learning based strategy. We conduct an extensive set of evaluations on several public datasets. Experimental results show that our proposed framework can outperform state-of-the-art methods by a significant margin.

Trajectory anomaly detection, aiming to estimate the anomaly risk of trajectories given the Source-Destination (SD) pairs, has become a critical problem for many real-world applications. Existing solutions directly train a generative model for observed trajectories and calculate the conditional generative probability$P(T \vert C)$as the anomaly risk, where$T$and$C$represent the trajectory and SD pair respectively. However, we argue that the observed trajectories are confounded by road network preference which is a common cause of both SD distribution and trajectories. Existing methods ignore this issue limiting their generalization ability on out-of-distribution trajectories. In this paper, we define the debiased trajectory anomaly detection problem and propose a causal implicit generative model, namely CausalTAD, to solve it. CausalTAD adopts do-calculus to eliminate the confounding bias of road network preference and estimates$P(T\vert do(C))$as the anomaly criterion. Extensive experiments show that CausalTadcan not only achieve superior performance on trained trajectories but also generally improve the performance of out-of-distribution data, with improvements of 2.1% ~ 5.7% and 10.6% ~ 32.7% respectively.

Detecting anomaly edges for dynamic graphs aims to identify edges significantly deviating from the normal pattern and can be applied in various domains, such as cybersecurity, financial transactions and AIOps. With the evolving of time, the types of anomaly edges are emerging and the labeled anomaly samples are few for each type. Current methods are either designed to detect randomly inserted edges or require sufficient labeled data for model training, which harms their applicability for real-world applications. In this paper, we study this problem by cooperating with the rich knowledge encoded in large language models(LLMs) and propose a method, namely AnomalyLLM. To align the dynamic graph with LLMs, AnomalyLLM pretrains a dynamic-aware encoder to generate the representations of edges and reprograms the edges using the prototypes of word embeddings. Along with the encoder, we design an in-context learning framework that integrates the information of a few labeled samples to achieve few-shot anomaly detection. Experiments on four datasets reveal that AnomalyLlmcan not only significantly improve the performance of few-shot anomaly detection, but also achieve superior results on new anomalies without any update of model parameters.

In online advertising, marketing mix modeling (MMM) is employed to predict the gross merchandise volume (GMV) of brand shops and help decision-makers to adjust the budget allocation of various advertising channels. Traditional MMM methods leveraging regression techniques can fail in handling the complexity of marketing. Although some efforts try to encode the causal structures for better prediction, they have the strict restriction that causal structures are prior-known and unchangeable. In this paper, we define a new causal MMM problem that automatically discovers the interpretable causal structures from data and yields better GMV predictions. To achieve causal MMM, two essential challenges should be addressed: (1) Causal Heterogeneity. The causal structures of different kinds of shops vary a lot. (2) Marketing Response Patterns. Various marketing response patterns i.e., carryover effect and shape effect, have been validated in practice. We argue that causal MMM needs dynamically discover specific causal structures for different shops and the predictions should comply with the prior known marketing response patterns. Thus, we propose CausalMMM that integrates Granger causality in a variational inference framework to measure the causal relationships between different channels and predict the GMV with the regularization of both temporal and saturation marketing response patterns. Extensive experiments show that CausalMMM can not only achieve superior performance of causal structure learning on synthetic datasets with improvements of 5.7%\sim 7.1%, but also enhance the GMV prediction results on a representative E-commerce platform.

Trajectory outlier detection has a profound impact on many real-world applications. Most existing methods, whether supervised or unsupervised, require adequate historical data as a prerequisite. However, due to the uneven distribution of the trajectories in space, the detection in some regions(e.g. rural areas) may suffer from data scarcity. Furthermore, because the occurrence of outliers is a small probability event, there are frequently no outlier trajectories in such limited data which makes it even worse. To handle such issues, we in this paper study a new problem, i.e. few-shot trajectory outlier detection with only normal trajectories. And we propose a novel model, named MetaTAD, which consists of a Multi-scale Encoder and an Ab-detection Meta Learner. The Multi-scale Encoder aims to learn the diverse features of trajectories for outlier detection, while the Ab-detection Meta Learner guides the model to detect with few labeled normal trajectories. Extensive experiments on two real taxi trajectory datasets show that MetaTAD achieves state-of-the-art performance compared with the baselines.

Temporal data representing chronological observations of complex systems can be ubiquitously collected in smart industry, medicine, finance and etc. In the last decade, many tasks have been studied for mining temporal data and offered significant value for various applications. Among these tasks, causal discovery aims to understand the underlying generation mechanism of temporal data and has attracted much research attention. According to whether the data is calibrated, existing causal discovery approaches can be divided into two subtasks, i.e., multivariate time-series causal discovery, and event sequence causal discovery. Previous tutorials or surveys have primarily focused on causal discovery from time-series data and disregarded the second ones. In this tutorial, we elucidate the correlation between the two subtasks and provide a comprehensive review of the existing solutions. Moreover, we offer some potential applications and summarize new perspectives for discovering causal relations from temporal data. We hope the audiences can obtain a systematic overview of this topic and inspire some new ideas for their own research.

Nowadays safety has become one of the most critical factors for ride-hailing service. Ride-hailing platforms have conducted meticulous background checks for drivers to minimize the risk of abnormal trips, e.g. violence and sexual assault. However, current methods are labor-consuming and highly rely on the personal information of drivers, which may harm the fairness of the order dispatching system. In this paper, we utilize the trip trajectories as inputs and propose a dual variational auto-encoder(VAE) framework, namely TripSafe, to estimate the probability of abnormal safety incidents. Specifically, TripSafe models the moving behavior and route information, as two independent components and employs VAEs to pre-train generative models for normal trips. Then, a fusion network is adopted to fine-tune the whole model with a few labeled samples. In practice, TripSafe monitors the data update and calculate the anomaly score of partial-observed trips in real-time. Experiments on real ridehailing data show that TripSafe is superior to the state-of-the-art baselines with about 14.2%~28.9% improvements on F1 score.

Trajectory similarity computation as the fundamental problem for various downstream analytic tasks, such as trajectory classification and clustering, has been extensively studied in recent years. However, how to infer an accurate and robust similarity over two trajectories is difficult due to the some trajectory characteristics in practice, e.g. non-uniform sampling rate, nonmalignant fluctuation, and noise points, etc. To circumvent such challenges, we in this paper introduce the adversarial training idea into the trajectory representation learning for the first time to enhance the robustness and accuracy. Specifically, our proposed method AdvTraj2Vec has two novelties: i) it perturbs the weight parameters of embedding layers to learn a robust model to infer an accurate pairwise similarity over each two trajectories; and ii) it employs the GAN momentum to harness the perturbation extent to which an appropriate trajectory representation can be learned for the similarity computation. Extensive experiments using two real-world trajectory datasets Porto and Beijing validate our proposed AdvTraj2Vec on the robustness and accuracy aspects. The multi-facet results show that our AdvTraj2Vec significantly outperforms the stat-of-the-art methods in terms of different distortions, such as trajectory-point addition, deletion, disturbance, and outlier injection.

To circumvent the grave problem of present adversarial training methods, i.e. distortion of classification surface, we in this paper propose a generated Triplet-based adversarial training method-GTAT, in which a Generator generates a semi-hard Triplet by design, rather than directly invoking the existing clean examples and adversarial examples. Through this kind of generated semi-hard Triplet constraint, GTAT can reshape the classification boundaries appropriately across various classes, arising from two-facet synergies: i) pull the intra-class examples together with tight distances; and ii) push away the inter-class examples with broad distances. This synergy will simplify and broaden the classification surfaces across different classes. Extensive experiments on the popular MNIST and CIFAR-10 datasets show that our proposed GTAT significantly outperforms other state-of-the-art adversarial training methods. We believe GTAT opens a door for the adversarial training from a new horizon of rationally generating semi-hard Triplet-satisfied adversarial training (retraining) examples, instead of straightly performing retraining on the generated adversarial examples and existing clean examples, or on the generated adversarial examples only.

With the emerging of smartphones, mobile games have attracted billions of players and occupied most of the share for game companies. On the other hand, mobile game cheating, aiming to gain improper advantages by using programs that simulate the players' inputs, severely damages the game's fairness and harms the user experience. Therefore, detecting mobile game cheating is of great importance for mobile game companies. Many PC game-oriented cheating detection methods have been proposed in the past decades, however, they can not be directly adopted in mobile games due to the concern of privacy, power, and memory limitations of mobile devices. Even worse, in practice, the cheating programs are quickly updated, leading to the label scarcity for novel cheating patterns. To handle such issues, we in this paper introduce a mobile game cheating detection framework, namely FCDGame, to detect the cheats under the few-shot learning framework. FCDGame only consumes the screen sensor data, recording users' touch trajectories, which is less sensitive and more general for almost all mobile games. Moreover, a Hierarchical Trajectory Encoder and a Cross-pattern Meta Learner are designed in FCDGame to capture the intrinsic characters of mobile games and solve the label scarcity problem, respectively. Extensive experiments on two real online games show that FCDGame achieves almost 10% improvements in detection accuracy with only few fine-tuned samples.

Multi-touch attribution (MTA), aiming to estimate the contribution of each advertisement touchpoint in conversion journeys, is essential for budget allocation and automatically advertising. Existing methods first train a model to predict the conversion probability of the advertisement journeys with historical data and calculate the attribution of each touchpoint by using the results counterfactual predictions. An assumption of these works is the conversion prediction model is unbiased. It can give accurate predictions on any randomly assigned journey, including both the factual and counterfactual ones. Nevertheless, this assumption does not always hold as the user preferences act as the common cause for both ad generation and user conversion, involving the confounding bias and leading to an out-of-distribution (OOD) problem in the counterfactual prediction. In this paper, we define the causal MTA task and propose CausalMTA to solve this problem. It systemically eliminates the confounding bias from both static and dynamic perspectives and learn an unbiased conversion prediction model using historical data. We also provide a theoretical analysis to prove the effectiveness of CausalMTA with sufficient ad journeys. Extensive experiments on both synthetic and real data in Alibaba advertising platform show that CausalMTA can not only achieve better prediction performance than the state-of-the-art method but also generate meaningful attribution credits across different advertising channels.

Computing trajectory similarities is a critical and fundamental task for various spatial-temporal applications, such as clustering, prediction, and anomaly detection. Traditional similarity metrics, i.e. DTW and Hausdorff, suffer from quadratic computation complexity, leading to their inability on large-scale data. To solve this problem, many trajectory representation learning techniques are proposed to approximate the metric space while reducing the complexity of similarity computation. Nevertheless, these works are designed based on RNN backend, resulting in a serious performance decline on long trajectories. In this paper, we propose a novel graph-based method, namely TrajGAT, to explicitly model the hierarchical spatial structure and improve the performance of long trajectory similarity computation. TrajGAT consists of two main modules, i.e. , graph construction and trajectory encoding. For graph construction, TrajGAT first employs PR quadtree to build the hierarchical structure of the whole spatial area, and then constructs a graph for each trajectory based on the original records and the leaf nodes of the quadtree. For trajectory encoding, we replace the self-attention in Transformer with graph attention and design an encoder to represent the generated graph trajectory. With these two modules, TrajGAT can capture the long-term dependencies of trajectories while reducing the GPU memory usage of Transformer. Our experiments on two real-life datasets show that TrajGAT not only improves the performance on long trajectories but also outperforms the state-of-the-art methods on mixture trajectories significantly.

This paper studies the task of detecting bots for online mobile games. Considering the fact of lacking labeled cheating samples and restricted available data in the real detection systems, we aim to study the finger operations captured by screen sensors to infer the potential bots in an unsupervised way. In detail, we introduce a Transformer-style detection model, namely FingFormer. It studies the finger operations in the format of graph structure in order to capture the spatial and temporal relatedness between the two hands’ operations. To optimize the model in an unsupervised way, we introduce two contrastive learning strategies to refine both finger moving patterns and players’ operation habits. We conduct extensive experiments under different experimental environments, including the synthetic dataset, the offline dataset, as well as the large-scale online data flow from three mobile games. The multi-facet experiments illustrate the proposed model is both effective and general to detect the bots for different mobile games.

Time series similarity computation is a fundamental primitive that underpins many time series data analysis tasks. However, many existing time series similarity measures have a high computation cost. While there has been much research effort for reducing the computational cost, such effort is usually specific to one similarity measure. We proposeNeuTS(Neural metric learning forTimeSeries) to accelerate time series similarity computation in a generic fashion.NeuTScomputes the similarity of a given time series pair in linear time and generic to handle any existing similarity measures.NeuTSsamples a number of seed time series from the given database, and then uses their pair-wise similarities as guidance to approximate the similarity function with a neural metric learning framework.NeuTSfeatures two novel modules to achieve accurate approximation of the similarity function: (1) a local attention memory module that augments existing recurrent neural networks for time series encoding; and (2) a distance-weighted ranking loss that effectively transcribes information from the seed-based guidance. With these two modules,NeuTScan yield high accuracies and fast convergence rates even if the training data is small. Our experiments with five real-life datasets and four similarity measures (Fréchet, Hausdorff, ERP and DTW) show thatNeuTSoutperforms baselines consistently and significantly. Specifically, it achieves over 80 percent accuracies in most settings, while obtaining 50x-1000x speedup over bruteforce methods and 3x-350x speedup over approximate algorithms for top-k similarity search.

In this paper, we propose a new task namely trajectory cross-modal retrieval which achieves the cross-modal search between coordinate trajectories and images containing trajectories. Nevertheless, trajectory cross-modal retrieval is rather challenging in learning the representations of each modality and reduce the cross-domain discrepancy caused by the inconsistent data distribution at the same time. we proposes a cross-modal retrieval model TrajCross based on multi-level representation for trajectory cross-modal retrieval. Specifically, TrajCross extracts the location features and the shape information respectively for the represention of multi-modal data. we adopt a contrastive learning method to achieve semantic preservation among similar multi-modal data. Extensive experiments show that TrajCross significantly outperforms state-of-the-art cross-modal retrieval methods.

User identity linkage (UIL) task aims to infer the identical users between different social networks/platforms. Existing models leverage the labeled inter-linkages or high-quality user attributes to make predictions. Nevertheless, it is often difficult or even impossible to obtain such information in real-world applications. To this end, we in this paper focus on studying an Anonymized User Identity Linkage (AUIL) problem wherein neither labeled anchor users nor attributes are available. To handle such a practical and challenging task, we propose a novel and concise unsupervised embedding method, VCNE, by utilizing the network structural information. Concretely, considering the inherent properties of structural diversity in the AUIL problem, we introduce a variational cross-network embedding learning framework to jointly study the Gaussian embeddings instead of the existing deterministic embedding from the angle of vector space. The multi-facet experiments on both real-world and synthetic datasets demonstrate that VCNE not only outperforms all baselines to a large extent but also be more robust to the different-level diversities and sparsities of the networks.

Social media has became a critical manner for people to acquire information in daily life. Despite the great convenience, fake news can be widely spread through social networks, causing various adverse effects on people's lives. Detecting these fake news or misinformations has proved to be a critical task and draws attentions from both governments and individuals. Recently, many methods have been proposed to solve this problem, but most of them rely on the body content of the news, ignoring the social context information such as the comments. We argue that the comments of a specific news contain common judgements of the whole society and could be extremely useful for detecting fake news. In this paper, we propose a new method TRANSFAKE which jointly models the body content and comments of news systemically, and detects fake news with multi-task learning framework. TRANSFAKE model is a Transformer-based model. It takes different modalities as input and employs multiple tasks, i.e. rumor score prediction and event classification, as intermediate tasks for extracting useful hidden relationships across various modalities. These intermediate tasks promote each other and encourage TRANSFAKE making the right decision. Extensive experiments on two standard real-life datasets demonstrate that TRANSFAKE outperforms state-of-the-art methods. It improves the detection accuracy by margins as large as ~12.6% and F1 scores as large as ~15%.

Recently, a new methodology using generative adversarial network (GAN) has been proposed to produce adversarial examples, which breaks the limitations of the previous methods dependent on different norm-levels. It can efficiently generate perturbations for any instance once the generator is trained, arising from the learning to approximate the distribution of real instances. However, there are still two shortcomings for this category of GAN-based method: i) the predicted label in attacking stage totally depend on a fixed or randomly-chosen label in training stage, which cannot tackle the elasticity problem on how to elastically produce adversarial example with any arbitrarily-assigned label in targeted attack scene when the generator has finished training; and ii) it only considering the produced adversarial example is as close as the real instances, which cannot guarantee the generated adversarial example is visually indistinguishable from its corresponding original instance perceptually. The aboved two disadvantages make this kind of method lack of flexibility and covertness. To circumvent these two predicaments, we in this paper propose a simple and easy-to-use adversarial example generating framework AdvCGAN through training a conditional generative adversarial network under the co-consideration on the similarities in data distributions and the image labels between the adversarial examples and the original instances to be imperceptible to humans. Concretely, our proposed AdvCGAN trains the conditional GAN with both image data and label (normal and attack) information, by which the generator can utilizing the guidance of label information to appropriately produce the adversarial example with any specific label in attacking stage. Extensive experiments using the commonly used MNIST and CIFAR-10 datasets show that our proposed AdvCGAN significantly outperforms other methods in terms of multi-facet evaluation. The results exhibit that our AdvCGAN can elastically produce more realistic adversarial examples with any arbitrarily-assigned attack label and achieve higher attack accuracy, especially in targeted attack.

Recommending citywide POIs where users would visit in the next future benefits many location-based businesses and individuals. To train a decent recommendation model, adequate historical data is usually a prerequisite. However, historical check-ins are usually distributed unevenly, which leads to many cities suffering from data scarcity. To make matters worse, transferring knowledge from data sufficient cities is challenging due to the varying distribution of POIs and city structures. Most of existing next POI recommendation methods assume that the training data is adequate and can not solve these problems. In this paper, we propose a novel meta-learning enhanced neural ordinary differential equation (ODE) method, namely METAODE, which models city-invariant information and city-specified information separately to achieve accurate citywide next POI recommendation. For transferring knowledge from data sufficient cities, METAODE learns city-invariant information including the representation of POIs categories and user groups to extract user preference. Basing on that, METAODE employs a GRU-ODE-Bayes model for city-specified information modeling. It can not only capture the sequential relationships within the historical check-ins but also model the irregular-sampled timestamp in the continuous timeline. Moreover, METAODE leverages meta-learning mechanism to optimize the parameters on various data sufficient cities and train a well-generalized initialization, which can be effectively adapted to data insufficient cities to enhance recommendation performance. Extensive experiments on real-world datasets demonstrate the effectiveness of METAODE. Comparing with the state-of-the-art baselines, METAODE achieves 6.21% and 14.77% improvements on HR and NDCG, respectively.

Heterogeneous information networks (HINs) have been successfully applied into several fields to accomplish complex data analytics, such as bibliography, bioinformatics, NLP, etc. In the meantime, network embedding at present has emerged as a convenient tool to mine and learn from networked data. As a result, it is of interest to develop HIN embedding methods. Despite recent breakthroughs in HIN embedding methods, little research attention has been paid to exploit the relation semantics in HINs and further integrate it to improve the embedding quality. Considering the sophisticated correlations in HINs, we in this paper propose a novel HIN embedding method LRHNE to yield latent-relation enhanced embeddings for nodes. Our work mainly involves three contributions: i) we verify that the latent relation can promote the embedding quality indeed through a real-world dataset, then a novel graph inception network is proposed to extract the latent relational features under the guidance of partial prior knowledge; ii) taking into account the existing structure information and inferred latent relation knowledge, we propose a cross-aligned variational graph autoencoder to extract and further fuse both the structure and latent relational features into the embeddings; and iii) we perform extensive experiments to validate our proposed LRHNE, and experimental results show that our LRHNE can significantly outperform state-of-the-art methods. The multi-facet inspections also exhibit our method is robust and hyper-parameter insensitive, therefore, our method can serve as a radical tool to tackle the relation-sophisticated HINs.

Collective classification, as an important technique to study networked data, aims to exploit the label autocorrelation for a group of inter-connected entities with complex dependencies. As the emergence of various heterogeneous information networks (HINs), collective classification at present is confronting several severe challenges stemming from the heterogeneity of HINs, such as complex relational hierarchy, potential incompatible semantics and node-context relational semantics. To address the challenges, in this paper, we propose a novel heterogeneous graph convolutional network-based deep learning model, called HGCN, to collectively categorize the entities in HINs. Our work involves three primary contributions: i) HGCN not only learns the latent relations from the relation-sophisticated HINs via multi-layer heterogeneous convolutions, but also captures the semantic incompatibility among relations with properly-learned edge-level filter parameters; ii) to preserve the fine-grained relational semantics of different-type nodes, we propose a heterogeneous graph convolution to directly tackle the original HINs without any in advance transforming the network from heterogeneity to homogeneity; iii) we perform extensive experiments using four real-world datasets to validate our proposed HGCN, the multi-facet results show that our proposed HGCN can significantly improve the performance of collective classification compared with the state-of-the-art baseline methods.

Trajectory similarity computation is a fundamental problem for various applications in trajectory data analysis. However, the high computation cost of existing trajectory similarity measures has become the key bottleneck for trajectory analysis at scale. While there have been many research efforts for reducing the complexity, they are specific to one similarity measure and often yield limited speedups. We propose NeuTraj to accelerate trajectory similarity computation. NeuTraj is generic to accommodate any existing trajectory measure and fast to compute the similarity of a given trajectory pair in linear time. Furthermore, NeuTraj is elastic to collaborate with all spatial-based trajectory indexing methods to reduce the search space. NeuTraj samples a number of seed trajectories from the given database, and then uses their pair-wise similarities as guidance to approximate the similarity function with a neural metric learning framework. NeuTraj features two novel modules to achieve accurate approximation of the similarity function: (1) a spatial attention memory module that augments existing recurrent neural networks for trajectory encoding; and (2) a distance-weighted ranking loss that effectively transcribes information from the seed-based guidance. With these two modules, NeuTraj can yield high accuracies and fast convergence rates even if the training data is small. Our experiments on two real-life datasets show that NeuTraj achieves over 80% accuracy on Fre chet, Hausdorff, ERP and DTW measures, which outperforms state-of-the-art baselines consistently and significantly. It obtains 50x-1000x speedup over bruteforce methods and 3x-500x speedup over existing approximate algorithms, while yielding more accurate approximations of the similarity functions.

Network embedding aims at learning the latent representations of nodes while preserving the complex structure of the underlying graph. Real-world networks are usually related with each other via common nodes, the so-called multiplex network. To make the data mining work on the multiplex network more actionable, it become urgent and essential to transform it into low-dimension vector space. Recently, several works have been proposed to leverage the complementary information for embedding. However, they suffer from sacrificing distinct properties of the counterparts in different layers, as they preserve much noise information into embedding vectors. In this paper, we propose a Noise-Aware Network Embedding approach for Multiplex Network, namely NANE. Unlike previous works, NANE considers the roles of an identical node in different layers, and adopts a more robust and flexible strategy to rationally integrate the cross-layer information while keeping the unique characteristic of each layer. We perform extensive evaluations on several real-world datasets. The experimental results demonstrate that our NANE can achieve better performance on link prediction task and significantly outperform previous methods especially in noisy multiplex network scenarios.

Recently, data mining through analyzing the complex structure and diverse relationships on multi-network has attracted much attention in both academia and industry. One crucial prerequisite for this kind of multi-network mining is to map the nodes across different networks, i.e., so-called network alignment. In this paper, we propose a cross-network embedding method CrossMNA for multi-network alignment problem through investigating structural information only. Unlike previous methods focusing on pair-wise learning and holding the topology consistent assumption, our proposed CrossMNA considers the multi-network scenarios which involve at least two types of networks with diverse network structures. CrossMNA leverages the cross-network information to refine two types of node embedding vectors, i.e., inter-vector for network alignment and intra-vector for other downstream network analysis tasks. Finally, we verify the effectiveness and efficiency of our proposed method using several real-world datasets. The extensive experiments show that our CrossMNA can significantly outperform the existing baseline methods on multi-network alignment task, and also achieve better performance for link prediction task with less memory usage.

In Software-Defined Networking (SDN), Ternary Content Addressable Memory (TCAM) enables fast lookup with flexible wildcard rule patterns for flow tables, however, the scarcity and expensiveness of TCAM dramatically limit the number of rules that switches can support. Rule caching for TCAM breaks the flow table size constraint by appropriate combinations of hardware and software processing. Nevertheless, previous literatures, from the viewpoint of maximizing cache hit ratio, ignore the TCAM update operations incurred by cache replacement, which is severely time-consuming. In this paper, we solve the TCAM cache replacement problem from a standpoint of reducing update cost. Upon comprehensively analyze and measure on cache hit ratio and update cost while sticking to the rule dependency constraints, we propose an effective cache replacement algorithm that can dynamically and adaptively adjust TCAM rules on a switch. Our experimental results show that our proposed algorithm can effectively eliminate over 60% update operations with less than 5% cache hit loss.

Abstract Trajectory clustering, which aims at discovering groups of similar trajectories, has long been considered as a corner stone task for revealing movement patterns as well as facilitating higher level applications such as location prediction and activity recognition. Although a plethora of trajectory clustering techniques have been proposed, they often rely on spatio‐temporal similarity measures that are not space and time invariant. As a result, they cannot detect trajectory clusters where the within‐cluster similarity occurs in different regions and time periods. In this paper, we revisit the trajectory clustering problem by learning quality low‐dimensional representations of the trajectories. We first use a sliding window to extract a set of moving behaviour features that capture space‐ and time‐invariant characteristics of the trajectories. With the feature extraction module, we transform each trajectory into a feature sequence to describe object movements and further employ a sequence‐to‐sequence auto‐encoder to learn fixed‐length deep representations. The learnt representations robustly encode the movement characteristics of the objects and thus lead to space‐ and time‐invariant clusters. We evaluate the proposed method on both synthetic and real data and observe significant performance improvements over existing methods.

Predicting the next location a user tends to visit is an important task for applications like location-based advertising, traffic planning, and tour recommendation. We consider the next location prediction problem for semantic trajectory data, wherein each GPS record is attached with a text message that describes the user's activity. In semantic trajectories, the confluence of spatiotemporal transitions and textual messages indicates user intents at a fine granularity and has great potential in improving location prediction accuracies. Nevertheless, existing methods designed for GPS trajectories fall short in capturing latent user intents for such semantics-enriched trajectory data. We propose a method named semantics-enriched recurrent model (SERM). SERM jointly learns the embeddings of multiple factors (user, location, time, keyword) and the transition parameters of a recurrent neural network in a unified framework. Therefore, it effectively captures semantics-aware spatiotemporal transition regularities to improve location prediction accuracies. Our experiments on two real-life semantic trajectory datasets show that SERM achieves significant improvements over state-of-the-art methods.

Trajectory clustering, which aims at discovering groups of similar trajectories, has long been considered as a corner stone task for revealing movement patterns as well as facilitating higher-level applications like location prediction. While a plethora of trajectory clustering techniques have been proposed, they often rely on spatiotemporal similarity measures that are not space- and time-invariant. As a result, they cannot detect trajectory clusters where the within-cluster similarity occurs in different regions and time periods. In this paper, we revisit the trajectory clustering problem by learning quality low-dimensional representations of the trajectories. We first use a sliding window to extract a set of moving behavior features that capture space- and time-invariant characteristics of the trajectories. With the feature extraction module, we transform each trajectory into a feature sequence to describe object movements, and further employ a sequence to sequence autoencoder to learn fixed-length deep representations. The learnt representations robustly encode the movement characteristics of the objects and thus lead to space- and time-invariant clusters. We evaluate the proposed method on both synthetic and real data, and observe significant performance improvements over existing methods.

Match field overlaps are common in most of today's networks because of wildcards and Longest Prefix Match (LPM). These overlaps exacerbate the loop-free update problem in Software-Defined Networks (SDNs). Because with overlaps, forwarding loops exist not only between old and new routes of a single policy but also among routes of different policies. However, previous work can only eliminate forwarding loops introduced by a single policy. In this paper, we focus on eliminating forwarding loops introduced by match field overlaps of multiple policies. Moreover, we prove that it is NP-hard to give a (ks+ 1)-round schedule, where ksis the maximum round number of the single policy schedules. We then propose an N-ary tree based heuristic algorithm that efficiently produces a schedule with approximate minimum rounds. Experimental results show that our approach could reduce more than 90% unnecessary rounds and achieve absolute loop-freedom especially when updating policies with overlaps.

With the development of internet, there are billions of short texts generated each day. However, the accuracy of large scale short text classification is poor due to the data sparseness. Traditional methods used to use external dataset to enrich the representation of document and solve the data sparsity problem. But external dataset which matches the specific short texts is hard to find. In this paper, we propose a framework to solve the data sparsity problem without using external dataset. Our framework deal with large scale short text by making the most of semantic similarity of words which learned from the training short texts. First, we learn word distributed representation and measure the word semantic similarity from the training short texts. Then, we propose a method which enrich the document representation by using the word semantic similarity information. At last, we build classifiers based on the enriched representation. We evaluate our framework on both the benchmark dataset(Standford Sentiment Treebank) and the large scale Chinese news title dataset which collected by ourselves. For the benchmark dataset, using our framework can improve 3% classification accuracy. The result we tested on the large scale Chinese news title dataset shows that our framework achieve better result with the increase of the training set size.

Video streaming uploading service over Vehicular Networks is very useful as it can support many applications. Due to the vehicle's high mobility and roadside access point (AP)'s sparse deployment, how to provide a high-quality video service with a low-price charge still remains an open question. To address this issue, a novel video uploading scheme based on vehicle moving prediction is proposed, in which the vehicle-to-infrastructure (V2I) and vehicle-to-vehicle communications (V2V) are cooperated to forward video streaming continuously from the moving vehicles to a fixed network. We make use of vehicle mobility prediction to find the stable relay nodes and reduce the link failure frequency, while an adaptive selection algorithm is used for roadside APs and gateway-vehicles to reduce the charge for video uploading. Experimental results show that the proposed scheme can achieve good performance while keeping a low application charge.

In virtualized data centers, live virtual machine (VM) migration can increase energy efficiency by consolidating VMs on fewer servers. This problem is usually considered as Bin Packing Problem with the server capacity constraints, such as CPU, memory and network bandwidth. In order to minimize the communication traffic in data center network, existing works proposed correlation-aware VM consolidation algorithms. VMs with high inter traffic will be consolidated as close as possible (e.g. Within a physical server). However, the traffic load of virtual switches causes a certain number of CPU cycles of physical servers to move traffic through virtual switches. This increases the risk that VMs running on servers are not allocated enough resource, and consequently reduces VMs' performance. In this work, we conduct experiments to estimate the server CPU overhead caused by virtual switching, and based on the experiment results, we propose virtual-switching-aware VM consolidation algorithm to solve this problem. Experiments on representative data center workloads show that the overhead can occupy 10% to 30% of server's CPU resources. Besides, our algorithm has a sharp decrease of the server capacity violation probability compared with the state-of-the-art baseline.

Today's data centers are facing extreme challenges in providing low latency and high throughput simultaneously for their applications. However, the fair sharing congestion control algorithms, together with the hash-based load balancing mechanisms, seriously impede the satisfaction of such requirements. In this paper, we use threshold-based signaling and marking schemes to seamlessly integrate load balancing with congestion control protocols. Through adaptive per-packet load balancing, we evenly split network traffic across multiple paths. Meanwhile, we adaptively react to ECN in the case of congestion, and prioritize flows according to their latency requirements. Using realistic data center workloads, we show that, compared to the state-of-the-art load balancing and TCP, our approach improves the application throughput and mean flow completion time by 30–50% and 40–80%, respectively.

Despite significant efforts to qualitatively describe the flattening trends of the Internet topology, there is few large-scale quantitative measurement study of such trends from the perspective of inter-domain routing. In this paper, we analyze the evolutionary trends of the Internet hierarchy and the interconnection policies, using fifteen years of historical datasets from RouteViews and RIPE. We find that the Internet is becoming flatter mainly due to bypassing the Tier-1 ISPs on AS-paths and the notable increase of peer-to-peer links. We also examine the global routing infrastructure, and find that IXPs are increasing rapidly in number and expand to broad areas around the world, which greatly facilitates the expansion of major content providers and content delivery networks to most regions in the world. Finally we discuss the impact and implication of this trend. Our measurement results strongly confirm the flattening trends of the Internet, and will help advance our understanding of the Internet AS-level ecosystem and the design of future Internet architecture.

Recently, there has been renewed interest in latency as a primary metric for mainstream data center applications. In this paper, we propose a coordinated mechanism for congestion control and multi-path transmission to reduce flow completion time in data centers. The approach leverages ECN to adaptively react to congestion, prioritizes flows according to their timeliness requirements, and evenly distributes network traffic across multiple paths. Through a real implementation and simulations, we show that our approach can effectively reduce flow completion time under different workflow patterns. Compared to existing solutions based on TCP and flow hashing, our approach achieves an improvement of 30% in application throughput and a reduction of up to 90% in 99th percentile flow completion time for latency-sensitive flows, and a reduction of 50%-80% in average completion time for long background flows.

In recent years, virtualization technologies are applied to data centers for resource sharing. Virtual Machine Monitor (VMM) can consolidate virtual machines (VMs) running on multiple physical servers onto a single one via live VM migration, consequently improving energy efficiency of data centers. VM consolidation is usually modeled as a bin packing problem aiming at minimizing the number of servers being used. However, resource consumption overhead of consolidating VMs is seldom considered in existing approaches. In this paper, the overhead is defined as the resource consumption difference between the server and all the VMs running on it. We theoretically and experimentally prove that under the realistic constrains, this overhead exists and remains steady with the increasing of consolidating VMs. We also propose Margin Reserved Consolidation (MRC) algorithm to supplement existing works. Besides, we conduct experiments to validate the overhead. Experiments based on a representative benchmark show that 11.7% of the server's CPU resource is occupied by the overhead averagely.

People's growing dependency on the Internet makes them want to access the network anytime and anywhere, even while driving cars. Although 3G or 4G networks can be used to achieve this goal, roadside APs have the advantages of low cost and high bandwidth. At present, however, APs cannot cover all the areas, which cause intermittent connectivity. In this paper, we propose the DSRelay, a scheme of cooperative downloading. Unlike some studies that multiple cars download files from the Internet and different cars deliver different blocks of files like a P2P network, our work concentrates on the request of downloading respectively. Making use of the characters of the limited communication range of WIFI network, DSRelay schedules the Dark Areas (DA) out of AP coverage areas. If a mobile client leaves an AP coverage area without finishing its downloading, using the proposed scheme, APs calculate meeting time and communication duration between client car and other registered cars, and choose a series of cars to carry data client needed so that the data can be transmitted to it at different slot in DA. Also, we analyze the influence of change of car speed and a corresponding solution is presented. This scheme utilizes DAs for extending the downloading areas of the client as much as possible. Simulation results indicate the benefits of the proposed scheme in terms of increasing throughput and reducing delay.

BGP dictates routing between autonomous systems with rich policy mechanisms in today's Internet. Operators translate high-level policy objectives into low-level router configurations without a comprehensive understanding of the actual effects on the network behavior, leaving the routing management an error-prone and time-consuming procedure. A fundamental question is: how to verify the intended routing principles against the actual routing effects of an ISP? In this paper, we develop a Routing Policy Inference Model (RPIM) as the first step towards addressing this fundamental issue. RPIM extracts various policy patterns from the BGP routing tables and translates them into high-level policy objectives of the ISP using a grouping and matching technique. Our work bridges the gap between the high-level policy objectives and the actual routing effects, which provides network operators with a novel approach to verify their policy design principles, thus facilitating the routing management. We evaluate our approach by extensive simulations using the Internet AS-level topology from CAIDA and the real routing data from the Abilene network. Simulation results show that RPIM achieves over 78.94% average inference accuracy in our suggested optimal threshold range. We also verify RPIM on several operating ISPs by the registered policies in an Internet Routing Registry (IRR). A representative case study on AS3292 demonstrates that RPIM effectively infers high-level policy objectives from routing data.

Trust mechanism is a crucial part of the P2P applications, which limits their rapid development. Unfortunately, current mechanisms were unable to detect the malicious peers accurately under the disturbing of various malicious reports. This paper proposes a new trust model, named Similarity Transitivity chain based Trust Model (STTM), to evaluate peers' global trust more precisely. Firstly, we employ PeerStrategy to produce feedbacks. Then we offer a novel similarity transitivity chain, which is formed by the peers who have common neighbors, to calculate report trustworthiness. By considering the peer's feedbacks as a vector, we calculate the personal similarity of each pair that has common neighbors. After that, we transit such personal similarities through the chain and get the report trustworthiness vector when all the peers come to a static view. Finally, we make use of maximum likelihood estimation equation to compute global trust. The simulation results show that our trust model is able to estimate peers' global trust accurately in most scenarios, especially in the scenario of two collusion groups. Also, it sharply decreases the mean error of trust estimation and performs better than other trust models.

Despite the recent and remarkable popularity of P2P IPTV systems, the study of their characteristics on largescale broadcasting is rare. In this paper, we have undertaken a measurement study on one of the most popular P2P IPTV systems, PPStream, during the 29th Olympics broadcasting. We deployed our dedicated measurement tool, PPS-Sniffer, under different network environments, and collected extensive data during a large number of events. We evaluate the playback delay, and the peering strategies towards local cluster. We also investigate the data scheduling, and its impact on the playback quality and the control overhead. To the best of our knowledge, results obtained in our study are unique and new as compared with existing work. Specifically, our study demonstrates that: (1) The playback delay is notable in Olympic channels, even for close peers. (2) Peering strategies of PPStream target mainly on the ISP level, and should exploit peers of local clusters to reduce the playback lag among close peers. (3) We unveil an overhead-quality tradeoff that sheds light on the design of future systems that can achieve a good balance. Our study aids the understanding of significant performance and design issues of PPStream, and is also useful for optimizing, modeling and the future design of P2P IPTV systems.

P2P streaming technique is spreading widely and the study of its characteristics on large-scale broadcasting is meaningful and important. In this paper, we have undertaken a measurement on one of the most popular P2P IPTV systems, PPStream, during the 29thBeijing Olympics. We collected extensive data traces under different network environments. New and unique observations are presented in our study as compared with existing measurements. Specifically, our results show that 1.) The playback delay is more remarkable in Olympics channels; 2.) Parent overlap is extremely small even for peers very nearby; 3.) The change of buffering fluctuates periodically in both Olympic and ordinary channels; 4.) Smaller scheduling unit is employed in Olympic channels with potential inefficiency. Measurement results obtained in our study bring to light significant performance and design issues of P2P live streaming systems during large-scale broadcasting, and are valuable in better understanding, optimizing and modeling of such systems.

Energy efficiency is an important issue in wireless sensor networks. One available power saving strategy is having only a portion of nodes work, but this would always compromise data quality as a result. In this paper, we propose an adaptive nodes scheduling approach (ADNS) to conserve energy while maintaining the overall data quality. ADNS selects a subset of nodes to be active and puts the others into sleep mode to save energy. An efficient active node selection (ANS) algorithm is presented. Using the spatial correlation among sensor readings as the prediction model, the values of sleep nodes are predicted by data collected from active nodes to ensure the data quality. In order to maintain the data quality throughout network operation, the prediction errors are validated timely and prediction models are adaptively reconstructed if necessary. We evaluate ADNS on a real-world sensor network data set and validate its effectiveness.

Border gateway protocol (BGP) is the de facto inter-domain routing protocol nowadays, and its behavior greatly impacts the end-to-end Internet performance. Various work has been done on revealing the cause and location of BGP routing instability, and they are helpful for operators to recover their networks from routing disasters. However, current approaches have the "magic numbers" problem in choosing the parameters, which prevents the accuracy in finding the correct location from rising above a certain level. In this paper, we present a statistical approach based on pattern matching to accurately identify familiar BGP routing instabilities and pinpoint their locations. Simulation results show that our approach can achieve over 80% locating precision if the ongoing instability is not well isolated, and increases the average locating precision from 60% to 75% for a BGP session availability event.

Packet delay is one of the most important Internet performance metrics. Many studies indicate that long-range dependence (LRD) exits in Internet packet delay, but the scaling behavior of packet delay is very complicated. This paper analyzes the Internet round-trip time (RTT) behavior based on small-interval (10 ms) measurements and finds that RTT series consist of two completely different components: spiky component and normal component. A bottleneck model is proposed to explain the phenomenon. By using detrended fluctuation analysis (DFA) method, it is found that the original RTT series don't exhibit simplex scaling behavior, and although the spiky component accounts for a little proportion of the original RTT series, it has a great impact on the scaling behavior. After removing the spiky component, RTT series show LRD, with Hurst exponent ranging from 0.55 to 0.8. And we discuss the implications of our findings on delay-boundary prediction algorithms of TCP

Owing to the asymmetry of Internet paths, more and more studies have turned to the measurement for one-way metrics. However, since the clocks at end systems often behave diversely, the synchronization between the end hosts is what we care about all along. In this paper, we firstly propose a general model for clock skew estimation in one-way measurements, which turns the problem of clock skew estimation to the solution of n-dimension equation group, and give the equation group what it needs based on different presumptions. We then present a Piece-wise Reliable Clock Skew Estimation Algorithm (PRCSEA), which introduces the reliability test of estimation results and eliminates the extra presumptions needed by other algorithms, such as only one clock adjustment in the measurements. PRCSEA solves the skew estimation problem in a heuristic way, and it can handle many special cases affecting the estimation of clock skew, such as routing change, clock hiccup and network congestion. PRCSEA is the only algorithm that can handle non-constant clock skew to the best of our knowledge. The time complexity of PRCSEA is O(n*logn), which is the same as that of Paxson's algorithm.

This paper characterizes the end-to-end routing measurement infrastructure WTracer and discusses the crucial technologies. Although WTracer is a traceroute server based Internet measurement infrastructure, it can be used in many areas, such as measurement and analysis of end-to-end routing behavior of the Internet, the estimation of the global Internet host distances, the measurement of hop count in the Internet, the discovery of Internet topology at both router level and AS level so on.

The distribution characteristic of RTT (round-trip time) is an important part of Internet end-to-end behavior characteristics. People have made lots of studies of it, but many conclusions only adapt to the cases of small packet loss rate. We study the RTT characteristics on nearly 40 end-to-end paths in CSTNET and CERNET in China, and draw the following conclusions: (1) the distribution characteristics of RTT and loss rate are dependable; (2) when loss rate is small, RTT distribution is usually unimodal, but with the increase of loss rate, RTT distribution is no longer unimodal and it becomes more and more decentralized; (3) with the increase of loss rate, the occurring times of inherent RTT tend to decrease.