Temporal graph neural networks (T-GNNs) have emerged as leading approaches for representation learning over dynamic graphs. However, existing solutions typically suffer from exponential time complexity with model depth and excessive GPU memory usage due to acceleration techniques, and cannot handle large dynamic graphs. Furthermore, the core component of T-G NNs, temporal message passing, still predominantly derives from static GNNs. This neglects the distinct characteristics of two types of features, timestamps and edge features, and results in sub-optimal embedding quality. Consequently, existing T-GNNs fail to scale to large dynamic graphs and generalize well in unseen or complex scenarios, limiting their applicability. To bridge the gap, this paper first proposes a simple yet effective temporal message passing paradigm for T-GNNs, called the divided temporal message passing (DT-MP) paradigm, which enables effective feature learning for each feature type. We theoretically demonstrate that the DT-MP paradigm can reduce GPU memory usage compared to existing T-GNNs. Building on this foundation, we propose TimeSGN, a scalable and effective temporal graph neural network, which can handle billion-scale dynamic graphs. Specifically, we design a linear state updater to effectively capture node dynamic evolution and instantiate the DT-MP paradigm using two 1-layer self-attention mechanisms for temporal message passing to generate temporal embeddings. As a result, TimeSGN fundamentally avoids exponential time complexity and significantly reduces GPU memory usage. Extensive experiments demonstrate that TimeSGN achieves an average 10.56% improvement in accuracy, up to 42.48% reduction in training GPU memory, and up to 5 x speedup in per-epoch training time compared to the state-of-the-art baselines, while being one order of magnitude faster than vanilla T-GNNs.

Trajectory data has become ubiquitous nowadays, which can benefit various real-world applications such as traffic management and location-based services. However, trajectories may disclose highly sensitive information of an individual including mobility patterns, personal profiles and gazetteers, social relationships, etc, making it indispensable to consider privacy protection when releasing trajectory data. Ensuring privacy on trajectories demands more than hiding single locations, since trajectories are intrinsically sparse and high-dimensional, and require to protect multi-scale correlations. To this end, extensive research has been conducted to design effective techniques for privacy-preserving trajectory data publishing. Furthermore, protecting privacy requires carefully balance two metrics: privacy and utility. In other words, it needs to protect as much privacy as possible and meanwhile guarantee the usefulness of the released trajectories for data analysis. In this survey, we provide a comprehensive study and a systematic summarization of existing protection models, privacy and utility metrics for trajectories developed in the literature. We also conduct extensive experiments on two real-life public trajectory datasets to evaluate the performance of several representative privacy protection models, demonstrate the trade-off between privacy and utility, and guide the choice of the right privacy model for trajectory publishing given certain privacy and utility desiderata.

Node importance estimation is a fundamental task in graph data analysis. Extensive studies have focused on this task, and various downstream applications have benefited from it, such as recommendation, resource allocation optimization, and missing value completion. However, existing works either focus on the homogeneous network or only study importance-based ranking. We are the first to consider the node importance values as heterogeneous values in heterogeneous information networks (HINs). A typical HIN is built of several distinguished node types where each type has its own measure of importance value (e.g., in the DBLP network, the importance values of authors and papers can be reflected by their h-index and citation numbers, respectively). This characteristic makes the above problem more challenging than computing the node importance in conventional homogeneous networks. In this paper, we formally introduce the problem of node importance value estimation in HINs; that is, given the importance values of a subset of nodes in an HIN, we aim to estimate the importance values of the remaining nodes. To solve this problem, we propose an effective graph neural network (GNN) model, called HIN Importance Value Estimation Network (HIVEN). HIVEN traces the local information of each node, specifically by utilizing the heterogeneity of the HIN. Furthermore, the meta schema is deployed to alleviate the node type domination issue. Additionally, HIVEN exploits the node similarity within each type to remedy the shortcoming of GNN models in capturing global information. Extensive experiments on real-world HIN datasets demonstrate that HIVEN superiorly outperforms the baseline methods.

Trajectory-based spatiotemporal entity linking is to match the same moving object in different datasets based on their movement traces. It is a fundamental step to support spatiotemporal data integration and analysis. In this paper, we study the problem of spatiotemporal entity linking using effective and concise signatures extracted from their trajectories. This linking problem is formalized as a$k$-nearest neighbor ($k$-NN) query on the signatures. Four representation strategies (sequential, temporal, spatial, and spatiotemporal) and two quantitative criteria (commonality and unicity) are investigated for signature construction. A simple yet effective dimension reduction strategy is developed together with a novel indexing structure called the WR-tree to speed up the search. A number of optimization methods are proposed to improve the accuracy and robustness of the linking. Our extensive experiments on real-world datasets verify the superiority of our approach over the state-of-the-art solutions in terms of both accuracy and efficiency.

A bipartite network is a network with two disjoint vertex sets and its edges only exist between vertices from different sets. It has received much interest since it can be used to model the relationship between two different sets of objects in many applications (e.g., the relationship between users and items in E-commerce). In this paper, we study the problem of efficient bi-triangle counting for a large bipartite network, where a bi-triangle is a cycle with three vertices from one vertex set and three vertices from another vertex set. Counting bi-triangles has found many real applications such as computing the transitivity coefficient and clustering coefficient for bipartite networks. To enable efficient bi-triangle counting, we first develop a baseline algorithm relying on the observation that each bi-triangle can be considered as the join of three wedges. Then, we propose a more sophisticated algorithm which regards a bi-triangle as the join of two super-wedges, where a wedge is a path with two edges while a super-wedge is a path with three edges. We further optimize the algorithm by ranking vertices according to their degrees. We have performed extensive experiments on both real and synthetic bipartite networks, where the largest one contains more than one billion edges, and the results show that the proposed solutions are up to five orders of magnitude faster than the baseline method.

Given a set of sparsely distributed sensors in the Euclidean plane, a mobile robot is required to visit all sensors to download the data and finally return to its base. The effective range of each sensor is specified by a disk, and the robot must at least reach the boundary to start communication. The primary goal of optimization in this scenario is to minimize the traveling distance by the robot. This problem can be regarded as a special case of the traveling salesman problem with neighborhoods (TSPN), which is known to be NP-hard. In this paper, we present a novel TSPN algorithm for this class of TSPN, which can yield significantly improved results compared to the latest approximation algorithm.

We present an empirical evaluation and comparison of two content extraction methods in HTML: absolute XPath expressions and relative XPath expressions. We argue that the relative XPath expressions, although not widely used, should be used in preference to absolute XPath expressions in extracting content from human-created Web documents. Evaluation of robustness covers four thousand queries executed on several hundred webpages. We show that in referencing parts of real world dynamic HTML documents, relative XPath expressions are on average significantly more robust than absolute XPath ones.

Pattern discovery in temporal event sequences is of great importance in many application domains, such as telecommunication network fault analysis. In reality, not every type of event has an accurate timestamp. Some of them, defined as inaccurate events may only have an interval as possible time of occurrence. The existence of inaccurate events may cause uncertainty in event ordering. The traditional support model cannot deal with this uncertainty, which would cause some interesting patterns to be missing. A new concept, precise support, is introduced to evaluate the probability of a pattern contained in a sequence. Based on this new metric, we define the uncertainty model and present an algorithm to discover interesting patterns in the sequence database that has one type of inaccurate event. In our model, the number of types of inaccurate events can be extended to k readily, however, at a cost of increasing computational complexity.

Semantic web services are web services with associated semantic descriptions. These descriptions will make it possible for other programs to select, compose and monitor web services at run-time, thereby contributing to the realization of the Semantic Web vision. Researchers have already been active in making the notion of semantic web service more concrete through usage scenaria and technologies that will support their design and use (e.g., [1]). Software Engineering has grappled with the problem of software design for more than three decades. There is welldocumented evidence that designing software manually is a laborious and error-prone task. Semantic descriptions of software (e.g., requirements and design specifications), developed and used at design-time, can facilitate the process of software construction, but they are not panacea. With semantic web services, we seem to be trying to solve the same software development problem, but now these semantic descriptions are used (for selection, composition, monitoring and other purposes) at run-time, automatically. Can we ever hope to see semantic web service technologies and methodologies that actually work? The discussion will focus on this central theme; it will be structured according to the following questions:

The notion of compensation is widely used as means of backward recovery in long-lived transactions as well as in business processes supported by workflow management systems. In general, it is non-trivial to design compensating tasks for tasks in the context of a workflow. Actually, a task does not have to be compensatable. In this paper, we first look into the requirements that a compensating task has to satisfy. Then we introduce a new mechanism called confirmation. With the help of confirmation, we can modify some non-compensatable tasks so that they become compensatable. This greatly improves backward recovery for workflow applications in the case of failures. To effectively incorporate confirmation and compensation into the workflow management environment, a three-level bottom-up workflow design method is introduced. The implementation issues of this design are also discussed.

Business environments have become exceedingly dynamic and competitive in recent times. This dynamism is manifested in the form of changing process requirements and time constraints. Workflow technology is currently one of the most promising fields of research in business process automation. However, workflow systems to date do not provide the flexibility necessary to support the dynamic nature of business processes. In this paper we primarily discuss the issues and challenges related to managing change and time in workflows representing dynamic business processes. We also present an analysis of workflow modifications and provide feasibility considerations for the automation of this process.

A data warehouse collects and maintains a large amount of data from multiple distributed and autonomous data sources. Often the data in it is stored in the form of materialized views in order to provide fast access to the integrated data. However, maintaining a certain level consistency of warehouse data with the source data is challenging in a distributed multiple source environment. Transactions containing multiple updates at one or more sources further complicate the consistency issue.

The notion of a compensation is widely used in advanced transaction models as means of recovery from a failure. Similar concepts are adopted for providing "transaction-like" behaviour for long business processes supported by workflows technology. Generally, designing a compensating task in the context of a workflow process is a non-trivial job. In fact, not every task is compensatable. This work contributes to the study of the non-compensatability problem. A compensating task C of a task T semantically undoes the effect of T after T has been committed. For example, the compensating task of a deposit is a withdrawal. For a task to be compensatable, it must satisfy two conditions. Forcibility: The compensating task of the task must be forcible. In other words, after the task commits, the execution of its compensating task is guaranteed to succeed by the application semantics. Relaxation of isolation: The isolation requirement of the shared data resources which the task may access must be relaxed. This relaxation is required as the purpose of introducing compensation is to avoid long-duration waiting, otherwise, compensation may become useless. In this work, we carefully investigate the properties of shared resources and tasks which may be performed on these resources. As all its invoked operations must be compensatable as well if a task is compensatable, we only discuss the compensatability of operations defined on shared resources.

The Distributed Systems Technology Centre (DSTC) framework for workflow specification, verification and management captures workflows transaction-like behavior for long lasting processes. FlowBack is an advanced prototype functionally enhancing an existing workflow management system by providing process backward recovery. It is based on extensive theoretical research ([3],[4],[5],[6],[8],[9]), and its architecture and construction assumptions are product independent. FlowBack clearly demonstrates the extent to which generic backward recovery can be automated and system supported. The provision of a solution for handling exceptional business process behavior requiring backward recovery makes workflow solutions more suitable for a large class of applications, therefore opening up new dimensions within the market. For the demonstration purpose, FlowBack operates with IBM FlowMark, one of the leading workflow products.