The Knowledge Graph logical reasoning task faces a dual challenge of insufficient semantic coverage from type information and missing structural information from relations. Although type annotations provide semantic priors for entities, their coarse-grained features cannot comprehensively characterize entity attributes; conversely, relational structure can enhance semantic representation, but the incompleteness of edges in real-world graphs limits modeling when relying on a single information source. To address these issues, we propose MRCLQR (Multi-information Relation Constraint-based Logical Query Reasoning), a framework with three core innovations: (1) an Information Semantic Alignment module based on contrastive learning, which achieves cross-modal semantic collaboration via entity-type-structure pairing; (2) a Constraint-aware Relation Encoding method that decomposes relation semantics into domain aggregation features, relation ontology semantics, and range constraint features; and (3) Neural-Symbolic Operators guided by domain constraints, which narrow the reasoning space through a constraint-aware attention mechanism. Experiments on FB15k, FB15k-237, and NELL-995 demonstrate that MRCLQR achieves average MRR scores of 35.8%, 16.2%, and 19.6%, respectively improving over the strongest baselines by 0.5%, 0.2%, and 0.2% --- and exhibits an 8.0% average gain on complex queries involving negation. Ablation studies validate the effectiveness of multi-source collaboration and the curriculum learning strategy. This work offers a novel paradigm for heterogeneous knowledge fusion and logical query reasoning.

Temporal entity alignment (TEA), which identifies equivalent entities across temporal knowledge graphs (TKGs), plays a vital role in integrating multiple TKGs.Simply adapting traditional EA models to TKGs cannot achieve satisfactory results, driving the need for dedicated studies in TEA. However, existing TEA models often fail to effectively capture the importance of temporal features and the richness of temporal context during embedding learning. Moreover, the challenge of temporal heterogeneity, which is prevalent in real-world TKGs, has not been adequately studied. In this work, we propose a HTEA framework to address these limitations. Specifically, we introduce a frequency-based temporal embedding module that incorporates the importance of temporal features for each entity, along with a temporal attention mechanism that prioritizes more informative context based on temporal richness. We further design an iterative module to detect temporal heterogeneity and refine the related facts accordingly. In this way, entity embeddings can be improved progressively, yielding more accurate and consistent alignment outcomes.Extensive experiments showcase the efficacy of our HTEA model, especially under the existence of temporal heterogeneity in real-world TKGs.

Complex Query Answering (CQA) on knowledge graphs is a fundamental yet challenging task, which can be formalized as answering a subset of first-order logic queries containing logical conjunction, disjunction, negation, and existential quantifiers. Recent research reveals that Link Predictors (LPs) trained on 1-hop queries can generalize to various types of complex queries. However, existing methods neglect crucial characteristics of LPs' outputs, including the effects of highly relevant entities and uncertainty. What's worse, as they model logical operations by fuzzy set operations, these methods suffer from problems like inflexibility, sensitivity to noise, and inconsistency with priority in human cognition, which limits their performance, especially on queries with negation. To address these challenges, we propose an efficient fuzzy system for CQA that requires no extra training overheads and is plug-and-play with existing LP-based methods. Firstly, we expand the output of LPs by two complementary membership functions of weak and strong relevance, which help to distinguish the target entities from highly relevant and irrelevant entities. Subsequently, we model logical operations through fuzzy rule bases and infer the final predictions via defuzzification, providing a flexible and tractable scheme for modeling logical operations. Finally, the effectiveness of the proposed fuzzy system is validated by its outstanding performance on benchmark datasets when compared to state-of-theart methods. The source code of our proposed method is available at https://anonymous.4open.science/r/FuzzSys-CQA-E285.

The popularity of location-aware devices has boosted urban systems with massive volumes of anonymous trajectory data, presenting both challenges and opportunities for enhancing smart city initiatives through Trajectory-User Linking (TUL). Typically, TUL aims to match anonymous trajectories with specific users by exploring spatiotemporal patterns and insightful mobility behaviors. However, current TUL models face significant limitations due to their reliance on singular data sources and insufficient consideration of real-world scenarios. Furthermore, these models often lack evaluation in fair and comprehensive environments, hindering accurate assessment of their performance and applicability. This paper systematically investigates prevalent challenges encountered by existing TUL models, conducts a comprehensive review of state-of-the-art models, and proposes a structured framework that encompasses three core components: point-level representation learning, trajectory-level representation learning, and user linking. Through meticulously designed experiments, we examine the effectiveness and efficiency of leading TUL models in handling the complexities of real-world data, such as data imbalance, sparsity, new users, and scalability. This in-depth analysis uncovers limitations in existing methodologies and offers guidance for future advancements, contributing to the development of robust TUL solutions for urban mobility analysis and smart city technologies.

The Constrained Shortest Path (CSP) problem seeks to identify the shortest path between two vertices in a road network while adhering to a specific constraint on another criterion. Solving the CSP problem frequently entails navigating the two-criteria skyline path problem, which incurs a substantial computational expense in large road networks. The primary challenge lies in handling a vast quantity of partial skyline paths, which often hinders index-based solutions from accurately determining the skyline paths. This paper introduces a-FHL, a practical approximation method designed to circumvent the costly skyline path search and hasten computation on skyline path indexing. a-FHL uses tree decomposition to hierarchically assign approximation ratios, thereby facilitating effective pruning within the labelling index. Moreover, we devise various strategies to allocate approximation ratios and an efficient approximation concatenation method to respond to the approximate CSP queries via the a-FHL index. Our method culminates in swift index construction and efficient query response. Comprehensive exper-iments conducted on real-world road networks substantiate the superiority of our approach over contemporary solutions

We devise a neural network-based temporal-textual framework that generates subgraphs with highly correlated authors from short-text contents. Our approach computes the relevance score (edge weight) between authors by considering a portmanteau of contents and concepts. It then employs a stack-wise graph-cutting algorithm to extract communities of related authors. Experimental results show that our multi-aspect vector space model can gain higher performance than other knowledge-centered competitors in linking short-text authors.

We devise a neural network-based temporal-textual framework that generates subgraphs with highly correlated authors from short-text contents. Our approach computes the relevance score (edge weight) between authors by considering a portmanteau of contents and concepts. It then employs a stack-wise graph-cutting algorithm to extract communities of related authors. Experimental results show that our multi-aspect vector space model can gain higher performance than other knowledge-centered competitors in linking short-text authors.

Addressing the challenge of matching queries with the right experts amid temporal-textual inconsistencies, we present a novel approach that combines an attention-based text embedding model with a continuous-time module. This method effectively maps queries to relevant experts by analyzing concept-oriented vectors and user behavior, demonstrating significant effectiveness on StackOverflow and Yahoo datasets.

The uniqueness of trajectory data for user re-identification has received unprecedented attention as the increasing popularity of location-based services boosts the excessive collection of daily trajectories with sufficient spatiotemporal coverage. Consequently, leveraging or releasing personally-sensitive trajectories without proper protection severely threatens individual privacy despite simply removing IDs. Trajectory privacy protection is never a trivial task due to the trade-off between privacy protection, utility preservation, and computational efficiency. Furthermore,recovery attack, one of the most threatening attacks specific to trajectory data, has not been well studied in the current literature. To tackle these challenges, we propose a frequency-based randomization model with a rigorous differential privacy guarantee for privacy-preserving trajectory data publishing. In particular, two randomized mechanisms are introduced for perturbing the local/global frequency distributions of a limited number of significantly essential locations in trajectories by injecting special Laplace noises. To reflect the perturbed distributions on the trajectory level without losing privacy guarantee or data utility, we formulate the trajectory modification tasks as kNN search problems and design two hierarchical indices with powerful pruning strategies and a novel search algorithm to support efficient modification. Extensive experiments on a real-world dataset verify the effectiveness of our approaches in resisting individual re-identification and recovery attacks simultaneously while still preserving desirable data utility. The efficient performance on large-scale data demonstrates the feasibility and scalability in practice.

Document-level Relation Extraction (RE) is a promising task aiming at identifying relations of multiple entity pairs in a document. Compared with the sentence-level counterpart, it has raised two significant challenges: a) In most cases, a relational fact can be adequately expressed via a small subset of sentences from the document, namely evidence. But the traditional method cannot model such strong semantic correlations between evidence sentences that collaborate to describe a specific relation; b) The data of this task is extremely long-tail in terms of too many NA instances and imbalanced relational types. Such data can mislead the tail prediction bias to the head categories in the RE model. In this paper, we present a novelEvidence reasoning andCurriculum learning method forDocRE(DRE-EC) to address these challenges. Particularly, we first formulate evidence extraction as a sequential decision problem through a crafted reinforcement learning mechanism with an efficient path searching strategy to reduce the action space. Providing the evidence for each entity pair as a customized-filtered document in advance helps infer the relations better. To address the long-tail issue, we further develop a hybrid curriculum learning method at the NA-level (NC) and relation-level (RC) with our customized difficulty measure score. In NC, the NA samples are scheduled in an easy-to-hard scheme and gradually added, resulting in the data distribution from ideal and balanced to real and unbalanced. In RC, the scheme is switched into hard-to-easy to enhance the hard and tail samples. In addition, we propose a new Equalization adaptive Focal Loss(EFLoss) that can adjust to the changing data distribution and focus more on the tail categories. We conduct various experiments on two document-level RE benchmarks and achieve a remarkable improvement over previous competitive baselines. Furthermore, we provide detailed analyses of the advantages and effectiveness of our method.

Map-matching plays an essential role in many location-based applications. It seeks to translate a sequence of timestamped location measurements, which may originate from GPS, Bluetooth, or cellular sources, into the actual routes that moving objects follow on the underlying digital road network. Some existing work focus on map-matching methods based on Hidden Markov Models. While powerful, these methods are computationally demanding and require highly accurate location information. In contrast, neural network-based methods offer the ability to handle more complex data sources, but face challenges when applied to large-scale road networks. In this research, we delve into the task of map-matching using wireless traffic sensor data, specifically Bluetooth, in the context of expansive road networks. We introduce a Turn-Based Map-Matching (TBMM) model, built upon a Sequence-to-Sequence framework. This model accepts a sequence of Bluetooth readings as input and generates a sequence of successive turns with a predicted start road segment. As the sequence of turns is generated, the corresponding route is concurrently reconstructed, adhering to the topological structure of the underlying road network. Furthermore, we employ a two-step training approach to optimize our model. We begin by pre-training the model by minimizing cross-entropy loss. Subsequently, we deploy reinforcement learning to fine-tune the model, thereby further enhancing its performance. Our experimental study shows the promising performance of our TBMM model compared with two state-of-the-art solutions, achieving approximately 98% in precision, recall, and F1-score, demonstrating the potential of our approach in the domain of map-matching.

Entity Alignment (EA), which aims to detect entity mappings (i.e. equivalent entity pairs) in different Knowledge Graphs (KGs), is critical for KG fusion. Neural EA methods dominate current EA research but still suffer from their reliance on labelled mappings. To solve this problem, a few works have explored boosting the training of EA models with self-training, which adds confidently predicted mappings into the training data iteratively. Though the effectiveness of self-training can be glimpsed in some specific settings, we still have very limited knowledge about it. One reason is the existing works concentrate on devising EA models and only treat self-training as an auxiliary tool. To fill this knowledge gap, we change the perspective to self-training to shed light on it. In addition, the existing self-training strategies have limited impact because they introduce either much False Positive noise or a low quantity of True Positive pseudo mappings. To improve self-training for EA, we propose exploiting the dependencies between entities, a particularity of EA, to suppress the noise without hurting the recall of True Positive mappings. Through extensive experiments, we show that the introduction of dependency makes the self-training strategy for EA reach a new level. The value of self-training in alleviating the reliance on annotation is actually much higher than what has been realised. Furthermore, we suggest future study on smart data annotation to break the ceiling of EA performance.

Entity alignment (EA) aims to identify equivalent entities between knowledge graphs (KGs), which is a key technique to improve the coverage of existing KGs. Current EA models largely ignore the importance of time information contained in KGs and treat relational facts or attribute values of entities as time-invariant. However, real-world entities could evolve over time, making the knowledge of the aligned entities very different in multiple KGs. This may cause incorrect matching between KGs if such entity dynamics is ignored. In this paper, we propose a time-aware entity alignment (TEA) model that discovers the entity evolving behaviour by exploring the time contexts in KGs and aggregates various contextual information to make the alignment decision. In particular, we address two main challenges in the TEA model: 1) How to identify highly-correlated temporal facts; 2) How to capture entity dynamics and incorporate it to learn a more informative entity representation for the alignment task. Experiments on real-world datasets1 verify the superiority of our TEA model over state-of-the-art entity aligners.

Entity resolution (ER) approaches typically consist of a blocker and a matcher. They share the same goal and cooperate in different roles: the blocker first quickly removes obvious non-matches, and the matcher subsequently determines whether the remaining pairs refer to the same real-world entity. Despite the state-of-the-art performance achieved by deep learning methods in ER, these techniques often rely on a large amount of labeled data for training, which can be challenging or costly to obtain. Thus, there is a need to develop effective ER systems under low-resource settings. In this work, we propose an end-to-end iterative Co-learning framework for ER, aimed at jointly training the blocker and the matcher by leveraging their cooperative relationship. In particular, we let the blocker and the matcher share their learned knowledge with each other via iteratively updated pseudo labels, which broaden the supervision signals. To mitigate the impact of noise in pseudo labels, we develop optimization techniques from three aspects: label generation, label selection and model training. Through extensive experiments on benchmark datasets, we demonstrate that our proposed framework outperforms baselines by an average of 9.13--51.55%. Furthermore, our analysis confirms that our framework achieves mutual benefits between the blocker and the matcher.

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.

Distant supervision is an efficient way to generate large-scale training data for relation extraction without human efforts. However, the accompanying challenges have been plaguing the advance of the extractor: (1) the automatically annotated labels for training data contain much noisy data; (2) the annotations, based on bag-level (cluster of sentences) instead of sentence-level (single sentence), are too coarse to train an accurate extractor; (3) hetergeneous sentences are hard for a denoising model to capture the underlying commonness among valid relational expressions. To address these issues, we bulid a novel sentence representation and craft reinforcement learning to select the expressive sentence for each relation mentioned in a bag. More specifically, we introduce entity-free sentence pattern incorporated with attentive type information. Furthermore, multiple interactions between entity-specific and entity-free representation are proposed to generate complementary sentence features (for challenge 3). Then we design a fine-grained reward function, and model the sentence selection process as an auction where different relations for a bag need to compete together to achieve the possession of a specific sentence based on its expressiveness(for challenge 1 and 2). The experimental results on two public datasets demonstrate the superiority of our model for distantly supervised relation extraction.

Finding the most suitable individual to answer a question using brief content has important usages, including the community of question answering systems and online recommender frameworks. However, one must tackle challenges: Disregarding the indispensable noise in short text contents, authors usually answer the input query with mismatched words that can negatively influence the textual relevance. Moreover, many vocabularies imply various alterations. Finally, not every expert is eager to answer an input query given the time constraint, named the reluctance dilemma. To overcome the challenges, we devise a novel embedding approach that constructs context-aware vectors. We then extract the knowledge domains out of the online contextual content. While we track user textual-temporal behavioral patterns via an infinite continuous-time module, we recommend a set of experts pertinent to the given query and willingly provide the response during the expected time. Experimental results on two real-world datasets ofStackOverflowandYahooshow that our online time-sensitive value-wise transformer can achieve higher effectiveness and efficiency versus other trending rivals in online expert recommendation systems. In addition, we empirically experience that Fourier transformers can automatically infer multi-aspect base signals and overpass manual discrete-time models in obtaining time-specific user profiles.

Entity Alignment (EA) aims to match equivalent entities that refer to the same real-world objects and is a key step for Knowledge Graph (KG) fusion. Most neural EA models cannot be applied to large-scale real-life KGs due to their excessive consumption of GPU memory and time. One promising solution is to divide a large EA task into several subtasks such that each subtask only needs to match two small subgraphs of the original KGs. However, it is challenging to divide the EA task without losing effectiveness. Existing methods display low coverage of potential mappings, insufficient evidence in context graphs, and largely differing subtask sizes.

Entity alignment is a crucial task in knowledge graph fusion. However, most entity alignment approaches have the scalability problem. Recent methods address this issue by dividing large KGs into small blocks for embedding and alignment learning in each. However, such a partitioning and learning process results in an excessive loss of structure and alignment. Therefore, in this work, we propose a scalable GNN-based entity alignment approach to reduce the structure and alignment loss from three perspectives. First, we propose a centrality-based subgraph generation algorithm to recall some landmark entities serving as the bridges between different subgraphs. Second, we introduce self-supervised entity reconstruction to recover entity representations from incomplete neighborhood subgraphs, and design cross-subgraph negative sampling to incorporate entities from other subgraphs in alignment learning. Third, during the inference process, we merge the embeddings of subgraphs to make a single space for alignment search. Experimental results on the benchmark OpenEA dataset and the proposed large DBpedia1M dataset verify the effectiveness of our approach.

Document-level Relation Extraction (RE) is a promising task aiming at identifying relations of multiple entity pairs in a document. However, in most cases, a relational fact can be expressed enough via a small subset of sentences from the document, namely evidence sentence. Moreover, there often exist strong semantic correlations between evidence sentences that collaborate together to describe a specific relation. To address these challenges, we propose a novel evidence-aware model for document-level RE. Particularly, we formulate evidence sentence selection as a sequential decision problem through a crafted reinforcement learning mechanism. Considering the explosive search space of our agent, an efficient path searching strategy is executed on the converted document graph to heuristically obtain hopeful sentences and feed them to reinforcement learning. Finally, each entity pair owns a customized-filtered document for further inferring the relation between them. We conduct various experiments on two document-level RE benchmarks and achieve a remarkable improvement over previous competitive baselines, verifying the effectiveness of our method.

With the popularity of GPS-enabled devices, a huge amount of trajectory data has been continuously collected and a variety of location-based services have been developed that greatly benefit our daily life. However, the released trajectories also bring severe concern on personal privacy, and several recent studies have demonstrated the existence of personally-identifying information in spatial trajectories. Trajectory anonymization is nontrivial due to the trade-off between privacy protection and utility preservation. Furthermore, recovery attack has not been well studied in the current literature. To tackle these issues, we propose a frequency-based randomization model with a rigorous differential privacy guarantee for trajectory data publishing. In particular, we introduce two randomized mechanisms to perturb the local/global frequency distributions of significantly important locations in trajectories by injecting Laplace noise. We design a hierarchical indexing along with a novel search algorithm to support efficient trajectory modification, ensuring the modified trajectories satisfy the perturbed distributions without compromising privacy guarantee or data utility. Extensive experiments on a real-world trajectory dataset verify the effectiveness of our approaches in resisting individual re-identification and recovery attacks, and meanwhile preserving desirable data utility as well as the feasibility in practice.

Entity alignment is a crucial step in integrating knowledge graphs (KGs) from multiple sources. Previous attempts at entity alignment have explored different KG structures, such as neighborhood-based and path-based contexts, to learn entity embeddings, but they are limited in capturing the multi-context features. Moreover, most approaches directly utilize the embedding similarity to determine entity alignment without considering the global interaction among entities and relations. In this work, we propose an Informed Multi-context Entity Alignment (IMEA) model to address these issues. In particular, we introduce Transformer to flexibly capture the relation, path, and neighborhood contexts, and design holistic reasoning to estimate alignment probabilities based on both embedding similarity and the relation/entity functionality. The alignment evidence obtained from holistic reasoning is further injected back into the Transformer via the proposed soft label editing to inform embedding learning. Experimental results on several benchmark datasets demonstrate the superiority of our IMEA model compared with existing state-of-the-art entity alignment methods.

Multi-Constraint Shortest Path ( MCSP ) generalizes the classic shortest path from single to multiple criteria such that more personalized needs can be satisfied. However, MCSP query is essentially a high-dimensional skyline problem and thus time-consuming to answer. Although the current Forest Hop Labeling (FHL) index can answer MCSP efficiently, it takes a long time to construct and lacks the flexibility to handle arbitrary criteria combinations. In this paper, we propose a skyline-cube-based FHL index that can handle the flexible MCSP efficiently. Firstly, we analyze the relation between low and high-dimensional skyline paths theoretically and use a cube to organize them hierarchically. After that, we propose methods to derive the high-dimensional path from the lower ones, which can adapt to the flexible scenario naturally and reduce the expensive high dimensional path concatenation. Then we introduce efficient methods for both single and multi-hop cube concatenations and propose pruning methods to further alleviate the computation. Finally, we improve the FHL structure with lower height for faster construction and query. Experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art.

Route planning is ubiquitous and has a profound impact on our daily life. However, the existing path algorithms tend to produce similar paths between similar OD (Origin-Destination) pairs because they optimize query results without considering their influence on the whole network, which further introduces congestions. Therefore, we investigate the problem of diversifying the top-k paths between an OD pair such that their similarities are under a threshold while their total length is minimal. However, the current solutions all depend on the expensive graph traversal which is too slow to apply in practice. Therefore, we first propose an edge deviation and concatenation-based method to avoid the expensive graph search in path enumeration. After that, we dive into the path relations and propose a path similarity computation method with constant complexity, and propose a pruning technique to improve efficiency. Finally, we provide the completeness and efficiency-oriented solutions to further accelerate the query answering. Evaluations on the real-life road networks demonstrate the effectiveness and efficiency of our algorithm over the state-of-the-art.

Map inference algorithm aims to construct a digital map from other data sources automatically. Due to the labour intensity of traditional map creation and the frequent road change nowadays, map inference is deemed to be a promising solution to automatic map construction and update. However, existing map inference from GPS trajectories suffers from low GPS data quality, which makes the quality of the constructed map unsatisfactory. In this paper, we study the existing map inference algorithms using GPS trajectories. Different from previous surveys, we (1) include the most recent solutions and propose a new categorisation of method; (2) study how different types of GPS errors affect the quality of inference results; (3) evaluate the existing map inference quality measures regarding their ability to identify map quality issues. To achieve these goals, we conduct a comprehensive experimental study on several representative algorithms using both real-world datasets and synthetic datasets, which are generated from our proposed synthetic trajectory generator and artificial map generator. Overall, our study provides insightful observations regarding (1) which inference method performs better in each working scenario, (2) the general data quality requirements for map inference, (3) the direction of future works for quantitative map quality measures.

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.

Linking authors of short-text contents has important usages in many applications, including Named Entity Recognition (NER) and human community detection. However, certain challenges lie ahead. First, the input short-text contents are noisy, ambiguous, and do not follow the grammatical rules. Second, traditional text mining methods fail to effectively extract concepts through words and phrases. Third, the textual contents are temporally skewed, which can affect the semantic understanding by multiple time facets. Finally, using knowledge-bases can make the results biased to the content of the external database and deviate the meaning from the input short text corpus. To overcome these challenges, we devise a neural network-based temporal-textual framework that generates the subgraphs with highly correlated authors from short-text contents. Our approach, on the one hand, computes the relevance score (edge weight) between the authors through considering a portmanteau of contents and concepts, and on the other hand, employs a stack-wise graph cutting algorithm to extract the communities of the related authors. Experimental results show that compared to other knowledge-centered competitors, our multi-aspect vector space model can achieve a higher performance in linking short-text authors. In addition, given the author linking task, the more comprehensive the dataset is, the higher the significance of the extracted concepts will be.

Shortest path query in road network is pervasive in various location-based services nowadays. As the business expands, the scalability issue becomes severer and more servers are deployed to cope with it. Moreover, as the traffic condition keeps changing over time, the existing index-based approaches can hardly adapt to the real-life dynamic environment. Therefore, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this work, we assume the traffic condition is stable over a short period and treat the issued queries within that period as a stream of query sets. Specifically, we first propose three query set decomposition methods to cluster one query set into multiple query subsets:Zigzagthat considers the1-Nshared computation;Co-Clusteringthat considers the source and target's spatial locality; andSearch-Space-Awarethat further incorporates search space estimation. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering:R2Rthat finds a set of approximate shortest paths from one region to another with bounded error; andLocal Cachethat improves the existingGlobal Cachewith higher cache hit ratio. Finally, we design three efficient stream processing methods for intra-batch shared computation. The experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.

Abstract The appetite for effective use of information assets has been steadily rising in both public and private sector organisations. However, whether the information is used for social good or commercial gain, there is a growing recognition of the complex socio-technical challenges associated with balancing the diverse demands of regulatory compliance and data privacy, social expectations and ethical use, business process agility and value creation, and scarcity of data science talent. In this vision paper, we present a series of case studies that highlight these interconnected challenges, across a range of application areas. We use the insights from the case studies to introduce Information Resilience, as a scaffold within which the competing requirements of responsible and agile approaches to information use can be positioned. The aim of this paper is to develop and present a manifesto for Information Resilience that can serve as a reference for future research and development in relevant areas of responsible data management.

The development of existing extractive summarization models for long-form document summarization is hindered by two factors: 1) the computation of the summarization model will dramatically increase due to the sheer size of the input long document; 2) the discourse structural information in the long-form document has not been fully exploited. To address the two deficiencies, we propose HEROES, a novel extractive summarization model for summarizing long-form documents with rich discourse structural information. In particular, the HEROES model consists of two modules: 1) a content ranking module that ranks and selects salient sections and sentences to compose a short digest that empowers complex summarization models and serves as its input; 2) an extractive summarization module based on a heterogeneous graph with nodes from different discourse levels and elaborately designed edge connections to reflect the discourse hierarchy of the document and restrain the semantic drifts across section boundaries. Experimental results on benchmark datasets show that HEROES can achieve significantly better performance compared with various strong baselines.

The Constrained Shortest Path (CSP) problem aims to find the shortest path between two nodes in a road network subject to a given constraint on another attribute. It is typically processed as a skyline path problem on the two attributes, resulting in very high computational cost which can be prohibitive for large road networks. The main bottleneck is to deal with a large amount of partial skyline paths, which further makes the existing index-based methods incapable to obtain the complete exact skyline paths. In this paper, we propose a novel skyline path concatenation approach to avoid the expensive skyline path search, which is then used to efficiently construct a 2-hop labeling index for the CSP queries. Specifically, a rectangle-based technique is designed to prune the concatenation space from multiple hops, and a constraint pruning method is used to further speed up the CSP query processing. To further scale up to larger networks, we propose a novel forest hop labeling that constructs labels from different partitions in parallel. Our approach is the first method that can achieve both accuracy and efficiency for CSP query answering. Extensive experiments on real-life road networks demonstrate that our method outperforms the state-of-the-art CSP solutions by several orders of magnitude.

Shortest path computation is a fundamental operation in small-world networks and index-based methods, especially 2-hop labeling, are commonly applied which have achieved high query efficiency. However, small-world networks keep evolving in real life, making it indispensable to study the maintenance of shortest path index. In this work, we adopt the state-of-the-art Parallel Shortest-distance Labeling (PSL) as the underlying 2-hop labeling construction method, and design algorithms to support efficient update of the index given edge weight change (increase and decrease) in the network. Specifically, we focus on weighted PSL (WPSL) and propose the update propagation mechanism for both synchronous propagation and asynchronous propagation. We then identify the curse of pruning power generated for the propagation under edge weight increase, and solve this problem with a balance between index size and effectiveness. Finally, we extend the proposed asynchronous propagation method to Pruned Landmark Labeling (PLL) for faster index maintenance and query processing with smaller index size. Our experimental results on real-life and synthetic networks demonstrate the superiority of our algorithms on index maintenance.

Shortest path finding is the building block of various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, the traffic condition keeps changing in real life, making the pre-computed index unable to answer the query correctly. In this work, we adopt the state-of-the-art tree decomposition-based hub labeling as the underlying index, and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce the minimum weight property and minimum distance property to guarantee the index correctness without graph traversal. Moreover, we propose the star-centric paradigm for tracing index change and design various pruning techniques to further accelerate the index maintenance. Finally, we extend our algorithms to batch mode for shared computation, extend to structural maintenance for full types of update, and generalize to all kinds of TDHL. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.

Route reconstruction targets at recovering the actual routes of objects moving on an underlying road network from their times-tamped position measurements. This fundamental pre-processing step to many location-based applications has been extensively studied for GPS data, which are object-centric and relatively densely sampled data. In this paper, we investigate the problem of route reconstruction using data collected from road-side Bluetooth scanners. In many cities, Bluetooth scanners are installed in road networks for monitoring the movement of Bluetooth-enabled devices. To address new challenges caused by such reader-centric Bluetooth data including spatial and temporal distortion, a new route reconstruction framework is proposed to transform Bluetooth readings through a family of distortion suppression strategies such that the transformed data can work well with the Hidden Markov model (HMM) map-matching approach. Extensive experiments are conducted to evaluate different transformation strategies with real-world datasets. The experimental results show that when the algorithm uses the baseline or the proposed transformation strategies, the map matching F1 score can be increased by up to 10% depending on the severity of distortion.

Shortest path query is a fundamental operation in various location-based services (LBS) and most of them process queries on the server-side. As the business expands, scalability becomes a severe issue. Instead of simply deploying more servers to cope with the quickly increasing query number, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this paper, we aim to improve the performance of batch shortest path algorithms by revisiting the problem of query clustering. Specifically, we first propose three query decomposition methods to cluster queries: Zigzag that considers the 1-N shared computation; Search-Space Estimation that further incorporates search space estimation; and Co-Clustering that considers the source and target's spatial locality. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering: Local Cache that improves the existing Global Cache with higher cache hit ratio, and R2R that finds a set of approximate shortest paths from one region to another with bounded error. Experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.

We are pleased to present a special issue of Data Science and Engineering (DSE), which contains a collection of five papers from the WISE 2019 conference, and two regular submission papers.The International Conference on Web Information Systems Engineering (WISE) has established itself as a community aiming at high-quality research and offering the ground for advancing efforts in topics related to Web information systems.WISE 2019 focuses on research, development, and applications in relation to Web information systems, including a wide range of topics, such as blockchain, deep learning, machine learning, recommender systems, data mining, Web-based applications, graph learning, knowledge graphs, graph mining, text mining, and crowdsourcing.WISE 2019 was held in Hong Kong, China, during January 19-21, 2020.WISE 2019 attracted a total of 211 research paper submissions.The conference program committee selected 50 full research papers (with an acceptance rate of 23.7%), five demonstration papers, and three tutorial papers to be presented at the conference and published in the proceedings [1,2].The conference program also included keynote presentations by

Distant supervision is an efficient way to generate large-scale training data for relation extraction without human efforts. However, a coin has two sides. The automatically annotated labels for training data are problematic, which can be summarized as multi-instance multi-label problem and coarse-grained (bag-level) supervised signal. To address these problems, we propose two reasonable assumptions and craft reinforcement learning to capture the expressive sentence for each relation mentioned in a bag. More specifically, we extend the original expressed-at-least-once assumption to multi-label level, and introduce a novel express-at-most-one assumption. Besides, we design a fine-grained reward function, and model the sentence selection process as an auction where different relations for a bag need to compete together to achieve the possession of a specific sentence based on its expressiveness. In this way, our model can be dynamically self-adapted, and eventually implements the accurate one-to-one mapping from a relation label to its chosen expressive sentence, which serves as training instances for the extractor. The experimental results on a public dataset demonstrate that our model constantly and substantially outperforms current state-of-the-art methods for relation extraction.

The prevalent adoption of GPS-enabled devices has witnessed an explosion of various location-based services which produce a huge amount of trajectories monitoring an individual's movement. This triggers an interesting question: is movement history sufficiently representative and distinctive to identify an individual? In this work, we study the problem of moving object linking based on their historical traces. However, it is non-trivial to extract effective patterns from moving history and meanwhile conduct object linking efficiently. To this end, we propose four representation strategies (sequential, temporal, spatial, and spatiotemporal) and two quantitative criteria (commonality and unicity) to construct the personalised signature from the historical trace. Moreover, we formalise the problem of moving object linking as a k-nearest neighbour (k-NN) search on the collection of signatures, and aim to improve efficiency considering the high dimensionality of signatures and the large cardinality of the candidate object set. A simple but effective dimension reduction strategy is introduced in this work, which empirically outperforms existing algorithms including PCA and LSH. We propose a novel indexing structure, Weighted R-tree (WR-tree), and two pruning methods to further speed up k-NN search by combining weight and spatial information contained in the signature. Our extensive experimental results on a real world dataset verify the superiority of our proposals, in terms of both accuracy and efficiency, over state-of-the-art approaches.

Finding the shortest path from one place to another is an essential operation for various location-based services (LBS), and most of the computations run on the server side. However, as the business grows, the service providers are facing an increasing swarm of path requests submitted during a short time period. The most straightforward solution is deploying more servers, while the operation cost increases at the same time. Therefore, in this work, we aim to improve the efficiency algorithmically by answering a large set of shortest path queries in a batch and reusing sharable computations. Specifically, we first propose the petal A*-1N algorithm to process 1-N shortest path queries by batch without repeated computation. Then we introduce several decomposition methods to cluster the start/target set and answer the whole query set with zigzag scheduling methods to further reduce the total running time. Extensive evaluations on both synthetic and real-world data verify the superiority of our algorithm compared with state-of-the-art methods.

Accurate user representation learning has been proven fundamental for many social media applications, including community detection, recommendation, etc. A major challenge lies in that, the available data in a single social network are usually very limited and sparse. In real life, many people are members of several social networks in the same time. Constrained by the features and design of each, any single social platform offers only a partial view of a user from a particular perspective. In this paper, we propose MV-URL, a multi-view user representation learning model to enhance user modeling by integrating the knowledge from various networks. Different from the traditional network embedding frameworks where either the whole framework is single-network based or each network involved is a homogeneous network, we focus on multiple social networks and each network in our task is a heterogeneous network. It's very challenging to effectively fuse knowledge in this setting as the fusion depends upon not only the varying relatedness of information sources, but also the target application tasks. MV-URL focuses on two tasks: user account linkage (i.e., to predict the missing true user account linkage across social media) and user attribute prediction. Extensive evaluations have been conducted on two real-world collections of linked social networks, and the experimental results show the superiority of MV-URL compared with existing state-of-art embedding methods. It can be learned online, and is trivially parallelizable. These qualities make it suitable for real world applications.

The recent art in relation extraction is distant supervision which generates training data by heuristically aligning a knowledge base with free texts and thus avoids human labelling. However, the concerned relation mentions often use the bag-of-words representation, which ignores inner correlations between features located in different dimensions and makes relation extraction less effective. To capture the complex characteristics of relation expression and tighten the correlated features, we attempt to discover and utilise informative correlations between features by the following four phases: 1) formulating semantic similarities between lexical features using the embedding method; 2) constructing generative relation for lexical features with different sizes of side windows; 3) computing correlation scores between syntactic features through a kernel-based method; and 4) conducting a distillation process for the obtained correlated feature pairs and integrating informative pairs with existing relation extraction models. The extensive experiments demonstrate that our method can effectively discover correlation information and improve the performance of state-of-the-art relation extraction methods.

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

Cross-device and cross-domain user linkage have been attracting a lot of attention recently. An important branch of the study is to achieve user linkage with spatio-temporal data generated by the ubiquitous GPS-enabled devices. The main task in this problem is twofold, i.e., how to extract the representative features of a user; how to measure the similarities between users with the extracted features. To tackle the problem, we propose a novel model STUL (Spatio-Temporal User Linkage) that consists of the following two components. 1) Extract users - spatial features with a density based clustering method, and extract the users - temporal features with the Gaussian Mixture Model. To link user pairs more precisely, we assign different weights to the extracted features, by lightening the common features and highlighting the discriminative features. 2) Propose novel approaches to measure the similarities between users based on the extracted features, and return the pair-wise users with similarity scores higher than a predefined threshold. We have conducted extensive experiments on three real-world datasets, and the results demonstrate the superiority of our proposed STUL over the state-of-the-art methods.

On time-dependent graphs, fastest path query is an important problem and has been well studied. It focuses on minimizing the total travel time (waiting time + on-road time) but does not allow waiting on any intermediate vertex if the FIFO property is applied. However, in practice, waiting on a vertex can reduce the time spent on the road (for example, resuming traveling after a traffic jam). In this paper, we study how to find a path with the minimal on-road time on time-dependent graphs by allowing waiting on some predefined parking vertices. The existing works are based on the following fact: the arrival time of a vertex v is determined by the arrival time of its in-neighbor u , which does not hold in our scenario since we also consider the waiting time on u if u allows waiting. Thus, determining the waiting time on each parking vertex to achieve the minimal on-road time becomes a big challenge, which further breaks FIFO property. To cope with this challenging problem, we propose two efficient algorithms using minimum on-road travel cost function to answer the query. The evaluations on multiple real-world time-dependent graphs show that the proposed algorithms are more accurate and efficient than the extensions of existing algorithms. In addition, the results further indicate, if the parking facilities are enabled in the route scheduling algorithms, the on-road time will reduce significantly compared to the fastest path algorithms.

Understanding short texts is crucial to many applications, but challenges abound. First, short texts do not always observe the syntax of a written language. As a result, traditional natural language processing tools, ranging from part-of-speech tagging to dependency parsing, cannot be easily applied. Second, short texts usually do not contain sufficient statistical signals to support many state-of-the-art approaches for text mining such as topic modeling. Third, short texts are more ambiguous and noisy, and are generated in an enormous volume, which further increases the difficulty to handle them. We argue that semantic knowledge is required in order to better understand short texts. In this work, we build a prototype system for short text understanding which exploits semantic knowledge provided by a well-known knowledgebase and automatically harvested from a web corpus. Our knowledge-intensive approaches disrupt traditional methods for tasks such as text segmentation, part-of-speech tagging, and concept labeling, in the sense that we focus on semantics in all these tasks. We conduct a comprehensive performance evaluation on real-life data. The results show that semantic knowledge is indispensable for short text understanding, and our knowledge-intensive approaches are both effective and efficient in discovering semantics of short texts.

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. For example, a personalized route query is issued by providing some clues that describe the spatial context between PoIs along the route, where the result can be far from the optimal one. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

Understanding short texts is crucial to many applications, but challenges abound. First, short texts do not always observe the syntax of a written language. As a result, traditional natural language processing methods cannot be easily applied. Second, short texts usually do not contain sufficient statistical signals to support many state-of-the-art approaches for text processing such as topic modeling. Third, short texts are usually more ambiguous. We argue that knowledge is needed in order to better understand short texts. In this work, we use lexical-semantic knowledge provided by a well-known semantic network for short text understanding. Our knowledge-intensive approach disrupts traditional methods for tasks such as text segmentation, part-of-speech tagging, and concept labeling, in the sense that we focus on semantics in all these tasks. We conduct a comprehensive performance evaluation on real-life data. The results show that knowledge is indispensable for short text understanding, and our knowledge-intensive approaches are effective in harvesting semantics of short texts.

Nowadays microblogging sites, such as Twitter and Chinese Sina Weibo, have established themselves as an invaluable information source, which provides a huge collection of manually-generated tweets with broad range of topics from daily life to breaking news. Entity linking is indispensable for understanding and maintaining such information, which in turn facilitates many real-world applications such as tweet clustering and classification, personalized microblog search, and so forth. However, tweets are short, informal and error-prone, rendering traditional approaches for entity linking in documents largely inapplicable. Recent work addresses this problem by utilising information from other tweets and linking entities in a batch manner. Nevertheless, the high computational complexity makes this approach infeasible for real-time applications given the high arrival rate of tweets. In this paper, we propose an efficient solution to link entities in tweets by analyzing their social and temporal context. Our proposed framework takes into consideration three features, namely entity popularity, entity recency, and user interest information embedded in social interactions to assist the entity linking task. Effective indexing structures along with incremental algorithms have also been developed to reduce the computation and maintenance costs of our approach. Experimental results based on real tweet datasets verify the effectiveness and efficiency of our proposals.

A search task represents an atomic information need of a user in web search. Tasks consist of queries and their reformulations, and identifying tasks is important for search engines since they provide valuable information for determining user satisfaction with search results, predicting user search intent, and suggesting queries to the user. Traditional approaches to identifying tasks exploit either temporal or lexical features of queries. However, many query refinements are topical, which means that a query and its refinements may not be similar on the lexical level. Furthermore, multiple tasks in the same search session may interleave, which means we cannot simply order the searches by their timestamps and divide the session into multiple tasks. Thus, in order to identify tasks correctly, we need to be able to compare two queries at the semantic level. In this paper, we use a knowledgebase known as Probase to infer the conceptual meanings of queries, and automatically identify the topical query refinements in the tasks. Experimental results on real search log data demonstrate that Probase can indeed help estimate the topical affinity between queries, and thus enable us to merge queries that are topically related but dissimilar at the lexical level.