Trip recommendation aims to generate a sequence of points of interest (POIs) under a user's query input. Existing data-driven methods mainly fall into two categories: supervised approaches and self-supervised approaches. The former cannot fully capture the transition patterns among POIs, while the latter fail to comprehensively model user's query intents. Fortunately, privileged knowledge distillation (PKD) provides us an unique opportunity to align user's query intents with its corresponding trip in historical data. However, such knowledge alignment is implicit, which may not directly reflect the query intents. To this end, in this paper, we propose EKD-Trip, an explicit intent-enhanced knowledge distillation framework. EKD-Trip first trains a trajectory encoder (teacher model) and a trip generator jointly in a self-supervised manner. Then, a query encoder (student model) is trained via multi-task learning to extract implicit knowledge by PKD from teacher and explicit knowledge from an auxiliary task, respectively. At inference time, we use the query encoder and the trip generator to recommend trips. Extensive experiments on four real-world datasets demonstrate that EKD-Trip outperforms all baselines over three metrics, with a particularly notable improvement of 13.70% in pairs-F1.

Continuous crowdsensing in Mobile CrowdSensing (MCS) involves ongoing monitoring to gather real-time data over extended periods. A key challenge is determining appropriate intervals between consecutive data samplings to capture temporal variations, especially in unknown dynamic environments. Traditional Age-of-Information (AoI) driven methods maintain data freshness but can be costly and result in data redundancy. To address this, we integrate the AoI metric with information entropy difference to create a novel indicator, Composite Data Value (CDV), balancing data freshness and redundancy. Based on it, we investigate the online adaptive sampling problem for continuous crowdsensing in unknown dynamic environments. This problem is challenging due to the vast space of sensing strategies, difficulty in estimating rewards with unknown distributions and varying rates of change, and the degradation of optimal strategies as the environment evolves. Using a multi-armed bandit framework, we propose AdaScs, an online adaptive sampling optimization approach to maximize long-term CDV performance. First, AdaScs develops compact sensing strategies through limited trials. Then, it adaptively performs online sampling based on evolving reward estimations, identifying optimal strategies, detecting environmental drifts, updating strategies, and adjusting cycle lengths. Our results show that AdaScs outperforms all baselines, with accuracy increasing by 22.6% and reaction time at last improving by 54.6%.

The rapid spread of diverse information on online social platforms has prompted both academia and industry to realize the importance of predicting content popularity, which could benefit a wide range of applications, such as recommendation systems and strategic decision-making. Recent works mainly focused on extracting spatiotemporal patterns inherent in the information diffusion process within a given observation period so as to predict its popularity over a future period of time. However, these works often overlook the future popularity trend, as future popularity could either increase exponentially or stagnate, introducing uncertainties to the prediction performance. Additionally, how to transfer the preceding-term dynamics learned from the observed diffusion process into future-term trends remains an unexplored challenge. Against this background, we propose CasFT, which leverages observed information Cascades and dynamic cues extracted via neural ODEs as conditions to guide the generation of Future popularity-increasing Trends through a diffusion model. These generated trends are then combined with the spatiotemporal patterns in the observed information cascade to make the final popularity prediction. Extensive experiments conducted on three real-world datasets demonstrate that CasFT significantly improves the prediction accuracy compared to state-of-the-art approaches.

With the ubiquity of hyper-relational facts in modern Knowledge Graphs (KGs), existing link prediction techniques mostly focus on learning the sophisticated relationships among multiple entities and relations contained in a fact, while ignoring the multimodal information, which often provides additional clues to boost link prediction performance.Nevertheless, traditional multimodal fusion approaches, which are mainly designed for triple facts under either entity-centric or relation-guided fusion schemes, fail to integrate the multimodal information with the rich context of the hyperrelational fact consisting of multiple entities and relations.Against this background, we propose HyperFM, a Hyper-relational Factcentric Multimodal Fusion technique.It effectively captures the intricate interactions between different data modalities while accommodating the hyper-relational structure of the KG in a fact-centric manner via a customized Hypergraph Transformer.We evaluate Hy-perFM against a sizeable collection of baselines in link prediction tasks on two real-world KG datasets.The results show that HyperFM consistently achieves the best performance, yielding an average improvement of 6.0-6.8% over the best-performing baselines on the two datasets.Moreover, a series of ablation studies systematically validate our fact-centric fusion scheme.

Synthetic human trajectory data becoming increasingly prominent in various applications, including urban planning, traffic control, and crowd monitoring. Recent neural generative models for human trajectory data mostly follow an unconditional generative paradigm that relies on a pure data-driven imitative learning scheme, without considering the rich context of human mobility (e.g., social events or weather conditions) which may significantly impact the underlying human mobility patterns. Against this background, we propose Marionette, a Manipulatable generative model for human trajectory data with fine-grained conditions. Specifically, Marionette integrates both global and partial mobility-related contexts and extracts both sequence-level and event-level conditions. Afterward, it designs fine-grained and cascading conditioning mechanisms for modeling the temporal and spatial dynamics based on diffusion-alike Temporal Point Processes (TPPs) and discrete diffusion models, respectively, offering fine-grained controllable generative modeling of human trajectory data with both global and partial mobility-related contexts. We conduct a thorough evaluation on two real-world human trajectory datasets against a sizeable collection of baselines. Results show that our Marionette consistently outperforms the best baselines by 13.96-54.13% on statistical and distributional similarity metrics and by 9.36-40.63% in task-based data utility evaluation. Ablation studies verify our key design choices. Case studies also demonstrate the manipulability of Marionette in generating data in previously unseen scenarios.

Human trajectory data, which plays a crucial role in various applications such as crowd management and epidemic prevention, is challenging to obtain due to practical constraints and privacy concerns. In this context, synthetic human trajectory data is generated to simulate as close as possible to real-world human trajectories, often under summary statistics and distributional similarities. However, these similarities oversimplify complex human mobility patterns (a.k.a. ''Datasaurus''), resulting in intrinsic biases in both generative model design and benchmarks of the generated trajectories. Against this background, we propose MIRAGE, a huMan-Imitative tRAjectory GenErative model designed as a neural Temporal Point Process integrating an Exploration and Preferential Return model. It imitates the human decision-making process in trajectory generation, rather than fitting any specific statistical distributions as traditional methods do, thus avoiding the Datasaurus issue. We also propose a comprehensive task-based evaluation protocol beyond Datasaurus to systematically benchmark trajectory generative models on four typical downstream tasks, integrating multiple techniques and evaluation metrics for each task, to assess the ultimate utility of the generated trajectories. We conduct a thorough evaluation of MIRAGE on three real-world user trajectory datasets against a sizeable collection of baselines. Results show that compared to the best baselines, MIRAGE-generated trajectory data not only achieves the best statistical and distributional similarities with 59.0-67.7% improvement, but also yields the best performance in the task-based evaluation with 10.9-33.4% improvement. A series of ablation studies also validate the key design choices of MIRAGE.

Spatial Crowdsourcing (SC), which outsources location-dependent tasks to workers for physical completion, is gaining popularity. Recently, more complex tasks have emerged that require a group of workers collaborating in a coalition. Several pioneering studies have examined this issue using the server assigned tasks mode from an overall perspective, such as maximizing the total benefits of all workers. Unfortunately, maximizing the overall benefit does not necessarily align with maximizing individual benefits. In practice, crowd workers are often self-interested and autonomous, making decisions based on their personal perspectives. In this article, under the worker selected tasks mode, we investigate an important problem: Selfish Workers Coalition Formation (SWCF) problem in SC. Here, selfish workers autonomously form coalitions to accomplish tasks to maximize their individual benefits. Achieving a stable coalition formation for SWCF problem requires balancing cooperation and competition. First, we transform the SWCF problem into a hedonic coalition formation game using a devised exploited skills-based reward distribution model. Subsequently, we propose a distributed algorithm HCFTA and prove its Nash stability and performance bounds. Additionally, to enhance coalition formation efficiency, we propose a Markov blanket coloring parallel optimization algorithm MCPHCF . Extensive experiments demonstrate the superiority of the proposed methods on both synthetic and real-world datasets.

Information popularity prediction is important yet challenging in various domains, including viral marketing and news recommendations. The key to accurately predicting information popularity lies in subtly modeling the underlying temporal information diffusion process behind observed events of an information cascade, such as the retweets of a tweet. To this end, most existing methods either adopt recurrent networks to capture the temporal dynamics from the first to the last observed event or develop a statistical model based on self-exciting point processes to make predictions. However, information diffusion is intrinsically a complex continuous-time process with irregularly observed discrete events, which is oversimplified using recurrent networks as they fail to capture the irregular time intervals between events, or using self-exciting point processes as they lack flexibility to capture the complex diffusion process. Against this background, we propose ConCat, modeling theContinuous-time dynamics ofCascades for information popularity prediction. On the one hand, it leverages neural Ordinary Differential Equations (ODEs) to model irregular events of a cascade in continuous time based on the cascade graph and sequential event information. On the other hand, it considers cascade events as neural temporal point processes (TPPs) parameterized by a conditional intensity function which can also benefit the popularity prediction task. We conduct extensive experiments to evaluate ConCat on three real-world datasets. Results show that ConCat achieves superior performance compared to state-of-the-art baselines, yielding 2.3%-33.2% improvement over the best-performing baselines across the three datasets.

In the realm of human mobility, the decision-making process for selecting the next-visit location is intricately influenced by a trade-off between spatial and temporal constraints, which are reflective of individual needs and preferences. This trade-off, however, varies across individuals, making the modeling of these spatial-temporal dynamics a formidable challenge. To address the problem, in this work, we introduce the "Spatial-temporal Induced Hierarchical Reinforcement Learning" (STI-HRL) framework, for capturing the interplay between spatial and temporal factors in human mobility decision-making. Specifically, STI-HRL employs a two-tiered decision-making process: the low-level focuses on disentangling spatial and temporal preferences using dedicated agents, while the high-level integrates these considerations to finalize the decision. To complement the hierarchical decision setting, we construct a hypergraph to organize historical data, encapsulating the multi-aspect semantics of human mobility. We propose a cross-channel hypergraph embedding module to learn the representations as the states to facilitate the decision-making cycle. Our extensive experiments on two real-world datasets validate the superiority of STI-HRL over state-of-the-art methods in predicting users' next visits across various performance metrics.

During the past few years, with the advent of large-scale pre-trained language models (PLMs), there has been a significant advancement in cross-domain text classification with limited labeled samples. However, most existing approaches still face the problem of excessive computation overhead. While some non-pretrained language models can reduce the computation overhead, the performance could sharply drop off. To resolve few-shot learning problems on resource-limited devices with satisfactory performance, we propose a prototype rectification framework, ProtoRectifier, based on pre-trained model distillation and episodic meta-learning strategy. Specifically, a representation refactor based on DistilBERT is developed to mine text semantics. Meanwhile, a novel prototype rectification approach (i.e., Mean Shift Rectification) is put forward by making full use of the pseudo labeled query samples, so that the prototype of each category can be updated during the meta-training phase without introducing additional time overhead. Experiments on multiple real-world datasets demonstrate that ProtoRectifier outperforms the state-of-the-art baselines, not only achieving high cross-domain classification accuracy but also reducing the computation overhead significantly.

Dynamically deploying mobile base stations is cru-cial for meeting public network demands and optimizing utilization. Traditional dynamic deployment strategies focus on maxi-mizing coverage of Points of Interest (POls), often overlooking the dynamic network demands of these locations. To address this problem, we propose a reinforcement learning-based dynamic deployment method. More specifically, we first design a spatio- temporal modeling-based actor network to comprehensively cap-ture network demand dynamics and make decisions for the next locations. Second, we design an attention-based critic network to efficiently process information and more accurately estimate collaborative decision-making. Third, we formulate a heuristic reward function to align the objectives of maximizing cumulative service utilization and minimizing energy consumption. Finally, we develop a digital twin simulator to validate the proposed method. Experiments using real-world data demonstrate the effectiveness of our approach.

Modern Knowledge Graphs (KGs) are inevitably noisy due to the nature of their construction process. Existing robust learning techniques for noisy KGs mostly focus on triple facts, where the fact-wise confidence is straightforward to evaluate. However, hyper-relational facts, where an arbitrary number of key-value pairs are associated with a base triplet, have become increasingly popular in modern KGs, but significantly complicate the confidence assessment of the fact. Against this background, we study the problem of robust link prediction over noisy hyper-relational KGs, and propose NYLON, a \underlineN oise-resistant h\underlineY per-re\underlineL ati\underlineON al link prediction technique via active crowd learning. Specifically, beyond the traditional fact-wise confidence, we first introduce element-wise confidence measuring the fine-grained confidence of each entity or relation of a hyper-relational fact. We connect the element- and fact-wise confidences via a "least confidence'' principle to allow efficient crowd labeling. NYLON is then designed to systematically integrate three key components, where a hyper-relational link predictor uses the fact-wise confidence for robust prediction, a cross-grained confidence evaluator predicts both element- and fact-wise confidences, and an effort-efficient active labeler selects informative facts for crowd annotators to label using an efficient labeling mechanism guided by the element-wise confidence under the "least confidence'' principle and further followed by data augmentation. We evaluate NYLON on three real-world KG datasets against a sizeable collection of baselines. Results show that NYLON achieves superior and robust performance in both link prediction and error detection tasks on noisy KGs, and outperforms best baselines by 2.42-10.93% and 3.46-10.65% in the two tasks, respectively.

Knowledge Graph (KG) embeddings have become a powerful paradigm to resolve link prediction tasks for KG completion. The widely adopted triple-based representation, where each triplet$(h,r,t)$links two entities$h$and$t$through a relation$r$, oversimplifies the complex nature of the data stored in a KG, in particular for hyper-relational facts, where each fact contains not only a base triplet$(h,r,t)$, but also the associated key-value pairs$(k,v)$. Even though a few recent techniques tried to learn from such data by transforming a hyper-relational fact into an n-ary representation (i.e., a set of key-value pairs only without triplets), they result in suboptimal models as they are unaware of the triplet structure, which serves as the fundamental data structure in modern KGs and preserves the essential information for link prediction. Moreover, as the KG schema information has been shown to be useful for resolving link prediction tasks, it is thus essential to incorporate the corresponding hyper-relational schema in KG embeddings. Against this background, we propose sHINGE, a schema-aware hyper-relational KG embedding model, which learns from hyper-relational facts directly (without the transformation to the n-ary representation) and their corresponding hyper-relational schema in a KG. Our extensive evaluation shows the superiority of sHINGE on various link prediction tasks over KGs. In particular, compared to a sizeable collection of 21 baselines, sHINGE consistently outperforms the best-performing triple-based KG embedding method, hyper-relational KG embedding method, and schema-aware KG embedding method by 19.1%, 1.8%, and 12.9%, respectively.

Modern Knowledge Graphs (KG) often suffer from an incompleteness issue (i.e., missing facts). By representing a fact as a triplet$(h,r,t)$linking two entities$h$and$t$via a relation$r$, existing KG completion approaches mostly consider a link prediction task to solve this problem, i.e., given two elements of a triplet predicting the missing one, such as$(h,r,?)$. However, this task implicitly has a strong yet impractical assumption on the two given elements in a triplet, which have to be correlated, resulting otherwise in meaningless predictions, such as (Marie Curie,headquarters location, ?). Against this background, this paper studies an instance completion task suggesting$r$-$t$pairs for a given$h$, i.e.,$(h,?,?)$. Inspired by the human psychological principle “fast-and-slow thinking”, we propose a two-step schema-aware approach RETA++ to efficiently solve our instance completion problem. It consists of two components: afastRETA-Filter efficiently filtering candidate$r$-$t$pairs schematically matching the given$h$, and adeliberateRETA-Grader leveraging a KG embedding model scoring each candidate$r$-$t$pair considering the plausibility of both the input triplet and its corresponding schema. RETA++ systematically integrates them by training RETA-Grader on the reduced solution space output by RETA-Filter via a customized negative sampling process, so as to fully benefit from the efficiency of RETA-Filter in solution space reduction and the deliberation of RETA-Grader in scoring candidate triplets. We evaluate our approach against a sizable collection of state-of-the-art techniques on three real-world KG datasets. Results show that RETA-Filter can efficiently reduce the solution space for the instance completion task, outperforming best baseline techniques by 10.61%–84.75% on the reduced solution space size, while also being 1.7×–29.6x faster than these techniques. Moreover, RETA-Grader trained on the reduced solution space also significantly outperforms the best state-of-the-art techniques on the instance completion task by 31.90%–105.02%.

Mobile Crowdsensing (MCS) is a sensing paradigm that enables large-scale smart city applications, such as environmental sensing and traffic monitoring. However, traditional MCS often suffers from performance degradation due to the limited spatiotemporal coverage of collected data. In this context, Sparse MCS has been proposed, which utilizes data inference algorithms to recover full data from sparse data collected by users. However, existing Sparse MCS approaches often overlook spatiotemporal fractures, where no data is observed either for a sensing subarea across all sensing time slots (temporal fracture), or for a sensing time slot in all sensing subarea (spatial fracture). Such spatiotemporal fractures pose great challenges to the data inference algorithms, as it is difficult to capture the complex spatiotemporal correlations of the sensing data from very limited observations. To address this issue, we propose a Graph-and Attention-based Matrix Completion (GAMC) method for the spatiotemporal fracture data inference problem in Sparse MCS. Specifically, we first pre-fill the general missing values using the classical Matrix Factorization (MF) technique. Then, we propose a neural network architecture based on Graph Attention Networks (GAT) and Transformer to capture complex spatiotemporal dependencies in the sensing data. Finally, we recover the complete data with a projection layer. We conduct extensive experiments on three real-world urban sensing datasets. The experimental results show the effectiveness of the proposed method.

Understanding the vulnerability of label aggregation against data poisoning attacks is key to ensuring data quality in crowdsourced label collection. State-of-the-art attack mechanisms generally assume full knowledge of the aggregation models while failing to consider the flexibility of malicious workers in selecting which instances to label. Such a setup limits the applicability of the attack mechanisms and impedes further improvement of their success rate. This paper introduces a black-box data poisoning attack framework that finds the optimal strategies for instance selection and labeling to attack unknown label aggregation models in crowdsourcing. We formulate the attack problem on top of a generic formalization of label aggregation models and then introduce a substitution approach that attacks a substitute aggregation model in replacement of the unknown model. Through extensive validation on multiple real-world datasets, we demonstrate the effectiveness of both instance selection and model substitution in improving the success rate of attacks.

Knowledge graph (KG) schema, which prescribes a high-level structure and semantics of a KG, is significantly helpful for KG completion and reasoning problems. Despite its usefulness, open-domain KGs do not practically have a unified and fixed schema. Existing approaches usually extract schema information using entity types from a KG where each entity e can be associated with a set of types {Te, by either heuristically taking one type for each entity or exhaustively combining the types of all entities in a fact (to get entity-typed tuples, (h_type, r, t_type) for example). However, these two approaches either overlook the role of multiple types of a single entity across different facts or introduce non-negligible noise as not all the type combinations actually support the fact, thus failing to capture the sophisticated schema information. Against this background, we study the problem of modeling hyper-relational schema, which is formulated as mixed hyper-relational tuples ({Th}, r, {Tt}, k, {Tv1},...) with two-fold hyper-relations: each type set T may contain multiple types and each schema tuple may contain multiple key-type set pairs (k, Tv). To address this problem, we propose HELIOS, a hyper-relational schema model designed to subtly learn from such hyper-relational schema tuples by capturing not only the correlation between multiple types of a single entity, but also the correlation between types of different entities and relations in a schema tuple. We evaluate HELIOS on three real-world KG datasets in different schema prediction tasks. Results show that HELIOS consistently outperforms state-of-the-art hyper-relational link prediction techniques by 20.0-29.7%, and is also much more robust than baselines in predicting types and relations across different positions in a hyper-relational schema tuple.

As a fundamental problem in human mobility modeling, location prediction forecasts a user’s next location based on historical user mobility trajectories. Recurrent neural networks (RNNs) have been widely used to capture sequential patterns of user visited locations for solving location prediction problems. Due to the sparse nature of real-world user mobility trajectories, existing techniques strive to improve RNNs by incorporating spatiotemporal contexts into the recurrent hidden state passing process of RNNs using context-parameterized transition matrices or gates. However, such a scheme mismatches universal spatiotemporal mobility laws and thus cannot fully benefit from rich spatiotemporal contexts encoded in user mobility trajectories. Against this background, we propose Flashback++, a general RNN architecture designed for modeling sparse user mobility trajectories. It not only leverages rich spatiotemporal contexts to search past hidden states with high predictive power but also learns to optimally combine them via a hidden state re-weighting mechanism, which significantly improves the robustness of the models against different settings and datasets. Our extensive evaluation compares Flashback++ against a sizable collection of state-of-the-art techniques on two real-world location-based social networks datasets and one on-campus mobility dataset. Results show that Flashback++ not only consistently and significantly outperforms all baseline techniques by 20.56% to 44.36% but also achieves better robustness of location prediction performance against different model settings (different RNN architectures and numbers of hidden states to flash back), different levels of trajectory sparsity, and different train-testing splitting ratios than baselines, yielding an improvement of 31.05% to 94.60%.

Noisy labels represent one of the key issues in supervised machine learning. Existing work for label noise reduction mainly takes a probabilistic approach that infers true labels from data distributions in low-level feature spaces. Such an approach is not only limited by its capability to learn high-quality data representations, but also by the low predictive power of data distributions in inferring true classes. To address those problems, we introduce Nessy, a neuro-symbolic system that integrates deep probabilistic modeling and symbolic knowledge for label noise reduction. Our deep probabilistic model infers the true classes of data instances with noisy labels by exploiting data distributions in an underlying latent feature representation space. For data instances where inference is not reliable enough, Nessy extracts symbolic rules and ranks them according to several utility metrics. Top-ranking rules are injected into the deep probabilistic model via expectation regularization, i.e., via a posterior regularization term constraining the class distribution in the objective function. In a real deployment over multiple relation extraction tasks, we demonstrate that Nessy is able to significantly improve the state of the art, by 7% accuracy and 10.7% AUC on average.

Graph embeddings have been widely used for many graph analysis tasks. Mainstream factorization-based and graph-sampling-based embedding learning schemes both involve many hyperparameters and design choices. However, existing techniques often adopt some heuristics for these hyperparameters and design choices with little investigation into their impact, making it unclear what is the exact performance gains of these techniques on graph analysis tasks. Against this background, this paper presents a systematic study on the impact of an extensive list of hyperparameters for both factorization-based and graph-sampling-based graph embedding techniques for homogeneous graphs. We design generalized factorization-based and graph-sampling-based techniques involving these hyperparameters, and conduct a comprehensive set of experiments with over 3,000 embedding models trained and evaluated per dataset. We reveal that much of the performance gains are indeed due to optimal hyperparameter settings/design choices rather than the sophistication of embedding models; appropriate hyperparameter settings for typical embedding techniques can outperform a sizeable collection of 18 state-of-the-art graph embedding techniques by 0.30-35.41% across different tasks. Moreover, we find that there is no one-size-fits-all hyperparameter setting across tasks, but we can indeed provide a list of task-specific practical recommendations for these hyperparameter settings/design choices, which we believe can serve as important guidelines for future research on embedding based graph analyses.

Graph embeddings have become a key paradigm to learn node representations and facilitate downstream graph analysis tasks. Many real-world scenarios such as online social networks and communication networks involve streaming graphs, where edges connecting nodes are continuously received in a streaming manner, making the underlying graph structures evolve over time. Such a streaming graph raises great challenges for graph embedding techniques not only in capturing the structural dynamics of the graph, but also in efficiently accommodating high-speed edge streams. Against this background, we propose SGSketch, a highly-efficient streaming graph embedding technique via incremental neighborhood sketching. SGSketch cannot only generate high-quality node embeddings from a streaming graph by gradually forgetting outdated streaming edges, but also efficiently update the generated node embeddings via an incremental embedding updating mechanism. Our extensive evaluation compares SGSketch against a sizable collection of state-of-the-art techniques using both synthetic and real-world streaming graphs. The results show that SGSketch achieves superior performance on different graph analysis tasks, showing 31.9% and 21.9% improvement on average over the best-performing static and dynamic graph embedding baselines, respectively. Moreover, SGSketch is significantly more efficient in both embedding learning and incremental embedding updating processes, showing 54x-1813x and 118x-1955x speedup over the baseline techniques, respectively.

Mobile Crowdsensing (MCS), which assigns outsourced sensing tasks to volunteer workers, has become an appealing paradigm to collaboratively collect data from surrounding environments. However, during actual task implementation, various unpredictable disruptions are usually inevitable, which might cause a task execution failure and thus impair the benefit of MCS systems. Practically, via reactively shifting the pre-determined assignment scheme in real time, it is usually impossible to develop reassignment schemes without a sacrifice of the system performance. Against this background, we turn to an alternative solution, i.e., proactively creating a robust task assignment scheme offline. In this work, we provide the first attempt to investigate an important and realisticRoBustTaskAssignment (RBTA) problem in MCS systems, and try to strengthen the assignment scheme's robustness while minimizing the workers’ traveling detour cost simultaneously. By leveraging the workers’ spatiotemporal mobility, we propose an assignment-graph-based approach. First, an assignment graph is constructed to locally model the assignment relationship between the released MCS tasks and available workers. And then, under the framework of evolutionary multi-tasking, we devise a population-based optimization algorithm, namelyEMTRA, to effectively achieve adequate Pareto-optimal schemes. Comprehensive experiments on two real-world datasets clearly validate the effectiveness and applicability of our proposed approach.

With the increasing prominence of smart mobile devices, an innovative distributed computing paradigm, namely Mobile Crowdsourcing (MCS), has emerged. By directly recruiting skilled workers, MCS exploits the power of the crowd to complete location-dependent tasks. Currently, based on online social networks, a new and complementary worker recruitment mode, i.e., socially aware MCS, has been proposed to effectively enlarge worker pool and enhance task execution quality, by harnessing underlying social relationships. In this paper, we propose and develop a novel worker recruitment game in socially aware MCS, i.e.,Acceptance-awareWorkerRecruitment (AWR). To accommodate MCS task invitation diffusion over social networks, we design a Random Diffusion model, where workers randomly propagate task invitations to social neighbors, and receivers independently make a decision whether to accept or not. Based on the diffusion model, we formulate the AWR game as a combinatorial optimization problem, which strives to search a subset of seed workers to maximize overall task acceptance under a pre-given incentive budget. We prove its NP hardness, and devise a meta-heuristic-based evolutionary approach namedMA-RAWRto balance exploration and exploitation during the search process. Comprehensive experiments using two real-world data sets clearly validate the effectiveness and efficiency of our proposed approach.

Until recently, a novel spatial crowdsourcing paradigm, namely Three-Dimensional (3D) spatial crowdsourcing, has emerged, in which the task requestors and the workers need travel to their designated third-party workplaces, e.g., shared offices, to deliver certain services, such as DiDi station ride-sharing service, Quyundong sport training service in the Online-To-Offline (O2O) applications. In 3D spatial crowdsourcing applications, a core issue is to develop an efficient global tasklist plan, based on the tripartite matching among the three parties, i.e., task requestors, workers and workplaces, which is different from the conventional spatial crowdsourcing. In this context, one key challenge is how to suitably schedule the available workers with the consideration of the interests of all the parties, under the constraint of worker resource. To answer the questions, in this paper, we propose and study a new problem, namely Social-Welfare-driven Task Scheduling (SWTS) problem, which strives to schedule the workers' continuous routines, i.e., successively implementing tasks for different requestors at different workplaces, to promote the social welfare for all the involved parties. We prove our studied problem is NP-hard, and devise two heuristic optimization algorithms to solve it. Finally, we conduct extensive experiments which verify the efficiency and effectiveness of the proposed algorithms on both real and synthetic data sets.

In this article, we propose and study a novel data-driven framework for Targeted Outdoor Advertising Recommendation (TOAR) with a special consideration of user profiles and advertisement topics. Given an advertisement query and a set of outdoor billboards with different spatial locations and rental prices, our goal is to find a subset of billboards, such that the total targeted influence is maximum under a limited budget constraint. To achieve this goal, we are facing two challenges: (1) it is difficult to estimate targeted advertising influence in physical world; (2) due to NP hardness, many common search techniques fail to provide a satisfied solution with an acceptable time, especially for large-scale problem settings. Taking into account the exposure strength, advertisement matching degree, and advertising repetition effect, we first build a targeted influence model that can characterize that the advertising influence spreads along with users mobility. Subsequently, based on a divide-and-conquer strategy, we develop two effective approaches, i.e., a master–slave-based sequential optimization method, TOAR-MSS, and a cooperative co-evolution-based optimization method, TOAR-CC, to solve our studied problem. Extensive experiments on two real-world datasets clearly validate the effectiveness and efficiency of our proposed approaches.

Recommender algorithms combining knowledge graph and graph convolutional network are becoming more and more popular recently. Specifically, attributes describing the items to be recommended are often used as additional information. These attributes along with items are highly interconnected, intrinsically forming a Knowledge Graph (KG). These algorithms use KGs as an auxiliary data source to alleviate the negative impact of data sparsity. However, these graph convolutional network based algorithms do not distinguish the importance of different neighbors of entities in the KG, and according to Pareto’s principle, the important neighbors only account for a small proportion. These traditional algorithms can not fully mine the useful information in the KG. To fully release the power of KGs for building recommender systems, we propose in this article KRAN, a Knowledge Refining Attention Network, which can subtly capture the characteristics of the KG and thus boost recommendation performance. We first introduce a traditional attention mechanism into the KG processing, making the knowledge extraction more targeted, and then propose a refining mechanism to improve the traditional attention mechanism to extract the knowledge in the KG more effectively. More precisely, KRAN is designed to use our proposed knowledge-refining attention mechanism to aggregate and obtain the representations of the entities (both attributes and items) in the KG. Our knowledge-refining attention mechanism first measures the relevance between an entity and it’s neighbors in the KG by attention coefficients, and then further refines the attention coefficients using a “richer-get-richer” principle, in order to focus on highly relevant neighbors while eliminating less relevant neighbors for noise reduction. In addition, for the item cold start problem, we propose KRAN-CD, a variant of KRAN, which further incorporates pre-trained KG embeddings to handle cold start items. Experiments show that KRAN and KRAN-CD consistently outperform state-of-the-art baselines across different settings.

Location-Based Social Networks (LBSNs) have been widely used as a primary data source for studying the impact of mobility and social relationships on each other. Traditional approaches manually define features to characterize users’ mobility homophily and social proximity, and show that mobility and social features can help friendship and location prediction tasks, respectively. However, these hand-crafted features not only require tedious human efforts, but also are difficult to generalize. Against this background, we propose in this paper LBSN2Vec++, a heterogeneous hypergraph embedding approach designed specifically for LBSN data for automatic feature learning. Specifically, LBSN data intrinsically forms a heterogeneous hypergraph including both user-user homogeneous edges (friendships) and user-time-POI-semantic heterogeneous hyperedges (check-ins). Based on this hypergraph, we first propose a random-walk-with-stay scheme to jointly sample user check-ins and social relationships, and then learn node embeddings from the sampled (hyper)edges by not only preserving the$n$-wise node proximity captured by the hyperedges, but also considering embedding space transformation between node domains to fully grasp the complex structural characteristics of the LBSN heterogeneous hypergraph. Using real-world LBSN datasets collected in six cities all over the world, our extensive evaluation shows that LBSN2Vec++ significantly and consistently outperforms both state-of-the-art graph embedding techniques by up to 68 percent and the best-performing hand-crafted features in the literature by up to 70.14 percent on friendship and location prediction tasks.

With the proliferation of increasingly powerful mobile devices and wireless networks, mobile crowdsourcing has emerged as a novel service paradigm. It enables crowd workers to take over outsourced location-dependent tasks, and has attracted much attention from both research communities and industries. In this paper, we consider a mobile crowdsourcing scenario, where a mobile crowdsourcing task is too complex (e.g., post-earthquake recovery, citywide package delivery) but can be divided into a number of easier subtasks, which have interdependency between them. Under this scenario, we investigate an important problem, namelytask graph scheduling in mobile crowdsourcing(TGS-MC), which seeks to optimize a compact scheduling, such that the task completion time (i.e., makespan) and overall idle time are simultaneously minimized with the consideration of worker reliability. We analyze the complexity and NP-complete of the TGS-MC problem, and propose two heuristic approaches, including BFS-based dynamic priority schedulingBFSPriDalgorithm, and an evolutionary multitasking-basedEMTTSchalgorithm, to solve our problem from local and global optimization perspective, respectively. We conduct extensive evaluation using two real-world data sets, and demonstrate superiority of our proposed approaches.

Knowledge Graph (KG) completion has been widely studied to tackle the incompleteness issue (i.e., missing facts) in modern KGs. A fact in a KG is represented as a triplet (h, r, t) linking two entities h and t via a relation r. Existing work mostly consider link prediction to solve this problem, i.e., given two elements of a triplet predicting the missing one, such as (h, r, ?). This task has, however, a strong assumption on the two given elements in a triplet, which have to be correlated, resulting otherwise in meaningless predictions, such as (Marie Curie, headquarters location, ?). In addition, the KG completion problem has also been formulated as a relation prediction task, i.e., when predicting relations r for a given entity h. Without predicting t, this task is however a step away from the ultimate goal of KG completion. Against this background, this paper studies an instance completion task suggesting r-t pairs for a given h, i.e., (h, ?, ?). We propose an end-to-end solution called RETA (as it suggests the Relation and Tail for a given head entity) consisting of two components: a RETA-Filter and RETA-Grader. More precisely, our RETA-Filter first generates candidate r-t pairs for a given h by extracting and leveraging the schema of a KG; our RETA-Grader then evaluates and ranks the candidate r-t pairs considering the plausibility of both the candidate triplet and its corresponding schema using a newly-designed KG embedding model. We evaluate our methods against a sizable collection of state-of-the-art techniques on three real-world KG datasets. Results show that our RETA-Filter generates of high-quality candidate r-t pairs, outperforming the best baseline techniques while reducing by 10.61%-84.75% the candidate size under the same candidate quality guarantees. Moreover, our RETA-Grader also significantly outperforms state-of-the-art link prediction techniques on the instance completion task by 16.25%-65.92% across different datasets.

With the rapid development of smart devices and high-quality wireless technologies, mobile crowdsourcing (MCS) has been drawing increasing attention with its great potential in collaboratively completing complicated tasks on a large scale. A key issue toward successful MCS is participant recruitment, where a MCS platform directly recruits suitable crowd participants to execute outsourced tasks by physically traveling to specified locations. Recently, a novel recruitment strategy, namely Word-of-Mouth(WoM)-based MCS, has emerged to effectively improve recruitment effectiveness, by fully exploring users' mobility traces and social relationships on geo-social networks. Against this background, we study in this paper a novel problem, namely Expected Task Execution Quality Maximization (ETEQM) for MCS in geo-social networks, which strives to search a subset of seed users to maximize the expected task execution quality of all recruited participants, under a given incentive budget. To characterize the MCS task propagation process over geo-social networks, we first adopt a propagation tree structure to model the autonomous recruitment between the referrers and the referrals. Based on the model, we then formalize the task execution quality and devise a novel incentive mechanism by harnessing the business strategy of multi-level marketing. We formulate our ETEQM problem as a combinatorial optimization problem, and analyze its NP hardness and high-dimensional characteristics. Based on a cooperative co-evolution framework, we proposed a divide-and-conquer problem-solving approach named ETEQM-CC. We conduct extensive simulation experiments and a case study, verifying the effectiveness of our proposed approach.

As an emerging social dynamic system, geo-social network can be used to facilitate viral marketing through the wide spread of targeted advertising. However, unlike traditional influence spread problem, the heterogeneous spatial distribution has to incorporated into geo-social network environment. Moreover, from the perspective of business managers, it is indispensable to balance the tradeoff between the objective of influence spread maximization and objective of promotion cost minimization. Therefore, these two goals need to be seamlessly combined and optimized jointly. In this paper, considering the requirements of real-world applications, we develop a multiobjective optimization-based influence spread framework for geo-social networks, revealing the full view of Pareto-optimal solutions for decision makers. Based on the reverse influence sampling (RIS) model, we propose a similarity matching-based RIS sampling method to accommodate diverse users, and then transform our original problem into a weighted coverage problem. Subsequently, to solve this problem, we propose a greedy-based incrementally approximation approach and heuristic-based particle swarm optimization approach. Extensive experiments on two real-world geo-social networks clearly validate the effectiveness and efficiency of our proposed approaches.

In mobile crowdsourcing, organizers usually need participants' precise locations for optimal task allocation, e.g., minimizing selected workers' travel distance to task locations. However, the exposure of users' locations raises privacy concerns. In this paper, we propose a location privacy-preserving task allocation framework with geo-obfuscation to protect users' locations during task assignments. More specifically, we make participants obfuscate their reported locations under the guarantee of two rigorous privacy-preserving schemes, differential and distortion privacy, without the need to involve any third-party trusted entity. In order to achieve optimal task allocation with the differential-and-distortion geo-obfuscation, we formulate a mixed-integer non-linear programming problem to minimize the expected travel distance of the selected workers under the constraints of differential and distortion privacy. Moreover, a worker may be willing to accept multiple tasks, and a task organizer may be concerned with multiple utility objectives such as task acceptance ratio in addition to travel distance. Against this background, we also extend our solution to the multi-task allocation and multi-objective optimization cases. Evaluation results on both simulation and real-world user mobility traces verify the effectiveness of our framework. Particularly, our framework outperforms Laplace obfuscation, a state-of-the-art geo-obfuscation mechanism, by achieving up to 47 percent shorter average travel distance on real-world data under the same level of privacy protection.

The surging traffic volumes and dynamic user mobility patterns pose great challenges for cellular network operators to reduce operational costs and ensure service quality. Cloud-radio access network (C-RAN) aims to address these issues by handling traffic and mobility in a centralized manner, separating baseband units (BBUs) from base stations (RRHs) and sharing BBUs in a pool. The key problem in C-RAN optimization is to dynamically allocate BBUs and map them to RRHs under cost and quality constraints, since real-world traffic and mobility are difficult to predict, and there are enormous numbers of candidate RRH-BBU mapping schemes. In this work, we propose a data-driven framework for C-RAN optimization. First, we propose a deep-learning-based Multivariate long short term memory (MuLSTM) model to capture the spatiotemporal patterns of traffic and mobility for accurate prediction. Second, we formulate RRH-BBU mapping with cost and quality objectives as a set partitioning problem, and propose a resource-constrained label-propagation (RCLP) algorithm to solve it. We show that the greedy RCLP algorithm is monotone suboptimal with worst-case approximation guarantee to optimal. Evaluations with real-world datasets from Ivory Coast and Senegal show that our framework achieves a BBU utilization above 85.2 percent, with over 82.3 percent of mobility events handled with high quality, outperforming the traditional and the state-of-the-art baselines.

Location prediction is a key problem in human mobility modeling, which predicts a user's next location based on historical user mobility traces. As a sequential prediction problem by nature, it has been recently studied using Recurrent Neural Networks (RNNs). Due to the sparsity of user mobility traces, existing techniques strive to improve RNNs by considering spatiotemporal contexts. The most adopted scheme is to incorporate spatiotemporal factors into the recurrent hidden state passing process of RNNs using context-parameterized transition matrices or gates. However, such a scheme oversimplifies the temporal periodicity and spatial regularity of user mobility, and thus cannot fully benefit from rich historical spatiotemporal contexts encoded in user mobility traces. Against this background, we propose Flashback, a general RNN architecture designed for modeling sparse user mobility traces by doing flashbacks on hidden states in RNNs. Specifically, Flashback explicitly uses spatiotemporal contexts to search past hidden states with high predictive power (i.e., historical hidden states sharing similar contexts as the current one) for location prediction, which can then directly benefit from rich spatiotemporal contexts. Our extensive evaluation compares Flashback against a sizable collection of state-of-the-art techniques on two real-world LBSN datasets. Results show that Flashback consistently and significantly outperforms state-of-the-art RNNs involving spatiotemporal factors by 15.9% to 27.6% in the next location prediction task.

Knowledge Graph (KG) embeddings are a powerful tool for predicting missing links in KGs. Existing techniques typically represent a KG as a set of triplets, where each triplet (h, r, t) links two entities h and t through a relation r, and learn entity/relation embeddings from such triplets while preserving such a structure. However, this triplet representation oversimplifies the complex nature of the data stored in the KG, in particular for hyper-relational facts, where each fact contains not only a base triplet (h, r, t), but also the associated key-value pairs (k, v). Even though a few recent techniques tried to learn from such data by transforming a hyper-relational fact into an n-ary representation (i.e., a set of key-value pairs only without triplets), they result in suboptimal models as they are unaware of the triplet structure, which serves as the fundamental data structure in modern KGs and preserves the essential information for link prediction. To address this issue, we propose HINGE, a hyper-relational KG embedding model, which directly learns from hyper-relational facts in a KG. HINGE captures not only the primary structural information of the KG encoded in the triplets, but also the correlation between each triplet and its associated key-value pairs. Our extensive evaluation shows the superiority of HINGE on various link prediction tasks over KGs. In particular, HINGE consistently outperforms not only the KG embedding methods learning from triplets only (by 0.81-41.45% depending on the link prediction tasks and settings), but also the methods learning from hyper-relational facts using the n-ary representation (by 13.2-84.1%).

Sparse Mobile Crowdsensing (MCS) has become a compelling approach to acquire and infer urban-scale sensing data. However, participants risk their location privacy when reporting data with their actual sensing positions. To address this issue, we propose a novel location obfuscation mechanism combining E-differential-privacy and δ-distortion-privacy in Sparse MCS. More specifically, differential privacy bounds adversaries' relative information gain regardless of their prior knowledge, while distortion privacy ensures that the expected inference error is larger than a threshold under an assumption of adversaries' prior knowledge. To reduce the data quality loss incurred by location obfuscation, we design a differential-and-distortion privacy-preserving framework with three components. First, we learn a data adjustment function to fit the original sensing data to the obfuscated location. Second, we apply a linear program to select an optimal location obfuscation function. The linear program aims to minimize the uncertainty in data adjustment under the constraints of E-differential-privacy, δ-distortion-privacy, and evenly-distributed obfuscation. We also design an approximated method to reduce the required computation resources. Third, we propose an uncertainty-aware inference algorithm to improve the inference accuracy for the obfuscated data. Evaluations with real environment and traffic datasets show that our optimal method reduces the data quality loss by up to 42% compared to the state-of-the-art methods with the same level of privacy protection; the approximated method incurs <; 3% additional quality loss than the optimal method, but only needs <; 1% of the computation time.

Different from online promotion, the outdoor billboard advertising industry suffers from a lack of audience-targeted delivery and quantitative dissemination evaluation, which undermine its impact in practice and hinder it from fast development. To bridge this gap, in this paper, we leverage crowdsensing vehicle trajectory data to empower audience-targeted billboard advertising. More specifically, by integrating the information of mobility transition, traffic conditions (traffic volume and average speed), and advertisement semantic topics, we propose a quantitative model to quantify advertisement influence spread, with a special consideration on influence overlapping among mobile users. Based on it, an influence maximization-targeted billboard advertising problem is formulated to find k advertising units over spatiotemporal dimensions, with the goal of maximizing the total expected advertisement influence spread. To tackle the efficiency issue for solving large combinatorial optimization problem, we employ a divide-and-conquer mechanism, and propose a utility evaluation-based optimal searching approach. Extensive experiments on real-world taxicab trajectories clearly validate the effectiveness and efficiency of our proposed approach.

Graph embedding has become a key component of many data mining and analysis systems. Current graph embedding approaches either sample a large number of node pairs from a graph to learn node embeddings via stochastic optimization or factorize a high-order node proximity/adjacency matrix via computationally intensive matrix factorization techniques. These approaches typically require significant resources for the learning process and rely on multiple parameters, which limits their applicability in practice. Moreover, most of the existing graph embedding techniques operate effectively in one specific metric space only (e.g., the one produced with cosine similarity), do not preserve higher-order structural features of the input graph and cannot automatically determine a meaningful number of dimensions for the embedding space. Typically, the produced embeddings are not easily interpretable, which complicates further analyses and limits their applicability. To address these issues, we propose DAOR, a highly efficient and parameter-free graph embedding technique producing metric space-robust, compact and interpretable embeddings without any manual tuning. Compared to a dozen state-of-the-art graph embedding algorithms, DAOR yields competitive results on both node classification (which benefits form high-order proximity) and link prediction (which relies on low-order proximity mostly). Unlike existing techniques, however, DAOR does not require any parameter tuning and improves the embeddings generation speed by several orders of magnitude. Our approach has hence the ambition to greatly simplify and speed up data analysis tasks involving graph representation learning.

Jointly learning embeddings from text and a Knowledge Graph benefits both word and entity/relation embeddings by taking advantage of both large-scale unstructured content (text) and high-quality structured data (the Knowledge Graph). Current techniques leverage anchors to associate entities in the Knowledge Graph to corresponding words in the text corpus; these anchors are then used to generate additional learning samples during the embedding learning process. However, we show in this paper that such techniques yield suboptimal results, as they fail to control the amount of shared information between the two data sources during the joint learning process. Moreover, the additional learning samples often incur significant computational overhead. Aiming at releasing the power of such joint embeddings, we propose JOINER, a new joint text and Knowledge Graph embedding method using regularization. JOINER not only preserves co-occurrence between words in a text corpus and relations between entities in a Knowledge Graph, it also provides the flexibility to control the amount of information shared between the two data sources via regularization. Our method does not generate additional learning samples, which makes it computationally efficient. Our extensive empirical evaluation on real datasets shows the superiority of JOINER across different evaluation tasks, including analogical reasoning, link prediction, and relation extraction. Compared to state-of-the-art techniques generating additional learning samples from a set of anchors, our method yields better results (with up to 4.3% absolute improvement) and significantly less computational overhead (76% less learning time overhead).

Embeddings have become a key paradigm to learn graph representations and facilitate downstream graph analysis tasks. Existing graph embedding techniques either sample a large number of node pairs from a graph to learn node embeddings via stochastic optimization, or factorize a high-order proximity/adjacency matrix of the graph via expensive matrix factorization. However, these techniques usually require significant computational resources for the learning process, which hinders their applications on large-scale graphs. Moreover, the cosine similarity preserved by these techniques shows suboptimal efficiency in downstream graph analysis tasks, compared to Hamming similarity, for example. To address these issues, we propose NodeSketch, a highly-efficient graph embedding technique preserving high-order node proximity via recursive sketching. Specifically, built on top of an efficient data-independent hashing/sketching technique, NodeSketch generates node embeddings in Hamming space. For an input graph, it starts by sketching the self-loop-augmented adjacency matrix of the graph to output low-order node embeddings, and then recursively generates k-order node embeddings based on the self-loop-augmented adjacency matrix and (k-1)-order node embeddings. Our extensive evaluation compares NodeSketch against a sizable collection of state-of-the-art techniques using five real-world graphs on two graph analysis tasks. The results show that NodeSketch achieves state-of-the-art performance compared to these techniques, while showing significant speedup of 9x-372x in the embedding learning process and 1.19x-1.68x speedup when performing downstream graph analysis tasks.

Location Based Social Networks (LBSNs) have been widely used as a primary data source to study the impact of mobility and social relationships on each other. Traditional approaches manually define features to characterize users' mobility homophily and social proximity, and show that mobility and social features can help friendship and location prediction tasks, respectively. However, these hand-crafted features not only require tedious human efforts, but also are difficult to generalize. In this paper, by revisiting user mobility and social relationships based on a large-scale LBSN dataset collected over a long-term period, we propose LBSN2Vec, a hypergraph embedding approach designed specifically for LBSN data for automatic feature learning. Specifically, LBSN data intrinsically forms a hypergraph including both user-user edges (friendships) and user-time-POI-semantic hyperedges (check-ins). Based on this hypergraph, we first propose a random-walk-with-stay scheme to jointly sample user check-ins and social relationships, and then learn node embeddings from the sampled (hyper)edges by preserving n-wise node proximity (n = 2 or 4). Our evaluation results show that LBSN2Vec both consistently and significantly outperforms the state-of-the-art graph embedding methods on both friendship and location prediction tasks, with an average improvement of 32.95% and 25.32%, respectively. Moreover, using LBSN2Vec, we discover the asymmetric impact of mobility and social relationships on predicting each other, which can serve as guidelines for future research on friendship and location prediction in LBSNs.

This paper presents Scalpel-CD, a first-of-its-kind system that leverages both human and machine intelligence to debug noisy labels from the training data of machine learning systems. Our system identifies potentially wrong labels using a deep probabilistic model, which is able to infer the latent class of a high-dimensional data instance by exploiting data distributions in the underlying latent feature space. To minimize crowd efforts, it employs a data sampler which selects data instances that would benefit the most from being inspected by the crowd. The manually verified labels are then propagated to similar data instances in the original training data by exploiting the underlying data structure, thus scaling out the contribution from the crowd. Scalpel-CD is designed with a set of algorithmic solutions to automatically search for the optimal configurations for different types of training data, in terms of the underlying data structure, noise ratio, and noise types (random vs. structural). In a real deployment on multiple machine learning tasks, we demonstrate that Scalpel-CD is able to improve label quality by 12.9% with only 2.8% instances inspected by the crowd.

Histogram-based similarity has been widely adopted in many machine learning tasks. However, measuring histogram similarity is a challenging task for streaming histograms, where the elements of a histogram are observed one after the other in an online manner. The ever-growing cardinality of histogram elements over the data streams makes any similarity computation inefficient in that case. To tackle this problem, we propose in this paper D2HistoSketch, a similarity-preserving sketching method for streaming histograms to efficiently approximate their Discriminative and Dynamic similarity. D2HistoSketch can fast and memory-efficiently maintain a set of compact and fixed-size sketches of streaming histograms to approximate the similarity between histograms. To provide high-quality similarity approximations, D2HistoSketch considers both discriminative and gradual forgetting weights for similarity measurement, and seamlessly incorporates them in the sketches. Based on both synthetic and real-world datasets, our empirical evaluation shows that our method is able to efficiently and effectively approximate the similarity between streaming histograms while outperforming state-of-the-art sketching methods. Compared to full streaming histograms with both discriminative and gradual forgetting weights in particular, D2HistoSketch is able to dramatically reduce the classification time (with a 7500x speedup) at the expense of a small loss in accuracy only (about 3.25 percent).

Personalized recommendation is crucial to help users find pertinent information. It often relies on a large collection of user data, in particular users' online activity (e.g., tagging/rating/checking-in) on social media, to mine user preference. However, releasing such user activity data makes users vulnerable to inference attacks, as private data (e.g., gender) can often be inferred from the users' activity data. In this paper, we proposed PrivRank, a customizable and continuous privacy-preserving social media data publishing framework protecting users against inference attacks while enabling personalized ranking-based recommendations. Its key idea is to continuously obfuscate user activity data such that the privacy leakage of user-specified private data is minimized under a given data distortion budget, which bounds the ranking loss incurred from the data obfuscation process in order to preserve the utility of the data for enabling recommendations. An empirical evaluation on both synthetic and real-world datasets shows that our framework can efficiently provide effective and continuous protection of user-specified private data, while still preserving the utility of the obfuscated data for personalized ranking-based recommendation. Compared to state-of-the-art approaches, PrivRank achieves both a better privacy protection and a higher utility in all the ranking-based recommendation use cases we tested.

With the remarkable proliferation of smart mobile devices, mobile crowdsensing has emerged as a compelling paradigm to collect and share sensor data from surrounding environment. In many application scenarios, due to unavailable wireless network or expensive data transfer cost, it is desirable to offload crowdsensing data traffic on opportunistic device-to-device (D2D) networks. However, coupling between mobile crowdsensing and D2D networks, it raises new technical challenges caused by intermittent routing and indeterminate settings. Considering the operations of data sensing, relaying, aggregating, and uploading simultaneously, in this article, we study collaborative mobile crowdsensing in opportunistic D2D networks. Toward the concerns of sensing data quality, network performance and incentive budget, Minimum-Delay-Maximum-Coverage (MDMC) problem and Minimum-Overhead-Maximum-Coverage (MOMC) problem are formalized to optimally search a complete set of crowdsensing task execution schemes over user, temporal, and spatial three dimensions. By exploiting mobility traces of users, we propose an unified graph-based problem representation framework and transform MDMC and MOMC problems to a connection routing searching problem on weighted directed graphs. Greedy-based recursive optimization approaches are proposed to address the two problems with a divide-and-conquer mode. Empirical evaluation on both real-world and synthetic datasets validates the effectiveness and efficiency of our proposed approaches.

For real-world mobile applications such as location-based advertising and spatial crowdsourcing, a key to success is targeting mobile users that can maximally cover certain locations in a future period. To find an optimal group of users, existing methods often require information about users' mobility history, which may cause privacy breaches. In this paper, we propose a method to maximize mobile crowd's future location coverage under a guaranteed location privacy protection scheme. In our approach, users only need to upload one of their frequently visited locations, and more importantly, the uploaded location is obfuscated using a geographic differential privacy policy. We propose both analytic and practical solutions to this problem. Experiments on real user mobility datasets show that our method significantly outperforms the state-of-the-art geographic differential privacy methods by achieving a higher coverage under the same level of privacy protection.

The graph embedding paradigm projects nodes of a graph into a vector space, which can facilitate various downstream graph analysis tasks such as node classification and clustering. To efficiently learn node embeddings from a graph, graph embedding techniques usually preserve the proximity between node pairs sampled from the graph using random walks. In the context of a heterogeneous graph, which contains nodes from different domains, classical random walks are biased towards highly visible domains where nodes are associated with a dominant number of paths. To overcome this bias, existing heterogeneous graph embedding techniques typically rely on meta-paths (i.e., fixed sequences of node types) to guide random walks. However, using these meta-paths either requires prior knowledge from domain experts for optimal meta-path selection, or requires extended computations to combine all meta-paths shorter than a predefined length. In this paper, we propose an alternative solution that does not involve any meta-path. Specifically, we propose JUST, a heterogeneous graph embedding technique using random walks with JUmp and STay strategies to overcome the aforementioned bias in an more efficient manner. JUST can not only gracefully balance between homogeneous and heterogeneous edges, it can also balance the node distribution over different domains (i.e., node types). By conducting a thorough empirical evaluation of our method on three heterogeneous graph datasets, we show the superiority of our proposed technique. In particular, compared to a state-of-the-art heterogeneous graph embedding technique Hin2vec, which tries to optimally combine all meta-paths shorter than a predefined length, our technique yields better results in most experiments, with a dramatically reduced embedding learning time (about 3x speedup).

Data quality and budget are two primary concerns in urban-scale mobile crowdsensing. Traditional research on mobile crowdsensing mainly takes sensing coverage ratio as the data quality metric rather than the overall sensed data error in the target-sensing area. In this article, we propose to leverage spatiotemporal correlations among the sensed data in the target-sensing area to significantly reduce the number of sensing task assignments. In particular, we exploit both intradata correlations within the same type of sensed data and interdata correlations among different types of sensed data in the sensing task. We propose a novel crowdsensing task allocation framework called SPACE-TA (SPArse Cost-Effective Task Allocation) , combining compressive sensing, statistical analysis, active learning, and transfer learning, to dynamically select a small set of subareas for sensing in each timeslot (cycle), while inferring the data of unsensed subareas under a probabilistic data quality guarantee. Evaluations on real-life temperature, humidity, air quality, and traffic monitoring datasets verify the effectiveness of SPACE-TA. In the temperature-monitoring task leveraging intradata correlations, SPACE-TA requires data from only 15.5% of the subareas while keeping the inference error below 0.25°C in 95% of the cycles, reducing the number of sensed subareas by 18.0% to 26.5% compared to baselines. When multiple tasks run simultaneously, for example, for temperature and humidity monitoring, SPACE-TA can further reduce ∼10% of the sensed subareas by exploiting interdata correlations.

Histogram-based similarity has been widely adopted in many machine learning tasks. However, measuring histogram similarity is a challenging task for streaming data, where the elements of a histogram are observed in a streaming manner. First, the ever-growing cardinality of histogram elements makes any similarity computation inefficient. Second, the concept-drift issue in the data streams also impairs the accurate assessment of the similarity. In this paper, we propose to overcome the above challenges with HistoSketch, a fast similarity-preserving sketching method for streaming histograms with concept drift. Specifically, HistoSketch is designed to incrementally maintain a set of compact and fixed-size sketches of streaming histograms to approximate similarity between the histograms, with the special consideration of gradually forgetting the outdated histogram elements. We evaluate HistoSketch on multiple classification tasks using both synthetic and real-world datasets. The results show that our method is able to efficiently approximate similarity for streaming histograms and quickly adapt to concept drift. Compared to full streaming histograms gradually forgetting the outdated histogram elements, HistoSketch is able to dramatically reduce the classification time (with a 7500x speedup) with only a modest loss in accuracy (about 3.5%).

In traditional mobile crowdsensing applications, organizers need participants' precise locations for optimal task allocation, e.g., minimizing selected workers' travel distance to task locations. However, the exposure of their locations raises privacy concerns. Especially for those who are not eventually selected for any task, their location privacy is sacrificed in vain. Hence, in this paper, we propose a location privacy-preserving task allocation framework with geo-obfuscation to protect users' locations during task assignments. Specifically, we make participants obfuscate their reported locations under the guarantee of differential privacy, which can provide privacy protection regardless of adversaries' prior knowledge and without the involvement of any third-part entity. In order to achieve optimal task allocation with such differential geo-obfuscation, we formulate a mixed-integer non-linear programming problem to minimize the expected travel distance of the selected workers under the constraint of differential privacy. Evaluation results on both simulation and real-world user mobility traces show the effectiveness of our proposed framework. Particularly, our framework outperforms Laplace obfuscation, a state-of-the-art differential geo-obfuscation mechanism, by achieving 45% less average travel distance on the real-world data.

Understanding the irregular crowd movement and social activities caused by urban events such as city festivals and concerts can benefit event management and city planning. Although various urban data can be exploited to detect such irregularities, the crowd mobility data (e.g., bike trip records) are usually in a mixed state with several basic patterns (e.g., eating, working, and recreation), making it difficult to separate concurrent events happening in the same region. The social activity data (e.g., social network check-ins) are usually oversparse, hindering the fine-grained characterization of urban events. In this paper, we propose a tensor cofactorization-based data fusion framework for fine-grained urban event detection and characterization leveraging crowd mobility data and social activity data. First, we adopt a nonnegative tensor cofactorization approach to decompose the crowd mobility tensor into several basic patterns, with the help of the auxiliary social activity tensor. We then use a multivariate-outlier-detection-based method to identify irregularities from the decomposed basic patterns and aggregate them to detect and characterize the associated urban events. We evaluate the performance of our framework using real-world bike trip data and check-in data from New York City and Washington, DC, respectively. Results show that by fusing the two types of urban data, our method achieves fine-grained urban event detection and characterization in both cities and consistently outperforms the baselines.

Bike sharing is booming globally as a green transportation mode, but the occurrence of over-demand stations that have no bikes or docks available greatly affects user experiences. Directly predicting individual over-demand stations to carry out preventive measures is difficult, since the bike usage pattern of a station is highly dynamic and context dependent. In addition, the fact that bike usage pattern is affected not only by common contextual factors (e.g., time and weather) but also by opportunistic contextual factors (e.g., social and traffic events) poses a great challenge. To address these issues, we propose a dynamic cluster-based framework for over-demand prediction. Depending on the context, we construct a weighted correlation network to model the relationship among bike stations, and dynamically group neighboring stations with similar bike usage patterns into clusters. We then adopt Monte Carlo simulation to predict the over-demand probability of each cluster. Evaluation results using real-world data from New York City and Washington, D.C. show that our framework accurately predicts over-demand clusters and outperforms the baseline methods significantly.

With the widespread adoption of smartphones, we have observed an increasing popularity of Location-Based Services (LBSs) in the past decade. To improve user experience, LBSs often provide personalized recommendations to users by mining their activity (i.e., check-in) data from location-based social networks. However, releasing user check-in data makes users vulnerable to inference attacks, as private data (e.g., gender) can often be inferred from the users' check-in data. In this paper, we propose PrivCheck, a customizable and continuous privacy-preserving check-in data publishing framework providing users with continuous privacy protection against inference attacks. The key idea of PrivCheck is to obfuscate user check-in data such that the privacy leakage of user-specified private data is minimized under a given data distortion budget, which ensures the utility of the obfuscated data to empower personalized LBSs. Since users often give LBS providers access to both their historical check-in data and future check-in streams, we develop two data obfuscation methods for historical and online check-in publishing, respectively. An empirical evaluation on two real-world datasets shows that our framework can efficiently provide effective and continuous protection of user-specified private data, while still preserving the utility of the obfuscated data for personalized LBSs.

Sparse Mobile Crowdsensing (MCS) has become a compelling approach to acquire and make inference on urban-scale sensing data. However, participants risk their location privacy when reporting data with their actual sensing positions. To address this issue, we adopt e-differential-privacy in Sparse MCS to provide a theoretical guarantee for participants' location privacy regardless of an adversary's prior knowledge. Furthermore, to reduce the data quality loss caused by differential location obfuscation, we propose a privacypreserving framework with three components. First, we learn a data adjustment function to fit the original sensing data to the obfuscated location. Second, we apply a linear program to select an optimal location obfuscation function, which aims to minimize the uncertainty in data adjustment. We also propose a fast approximated variant. Third, we propose an uncertaintyaware inference algorithm to improve the inference accuracy of obfuscated data. Evaluations with real environment and traffic datasets show that our optimal method reduces the data quality loss by up to 42% compared to existing differential privacy methods.

Culture has been recognized as a driving impetus for human development. It co-evolves with both human belief and behavior. When studying culture, Cultural Mapping is a crucial tool to visualize different aspects of culture (e.g., religions and languages) from the perspectives of indigenous and local people. Existing cultural mapping approaches usually rely on large-scale survey data with respect to human beliefs, such as moral values. However, such a data collection method not only incurs a significant cost of both human resources and time, but also fails to capture human behavior, which massively reflects cultural information. In addition, it is practically difficult to collect large-scale human behavior data. Fortunately, with the recent boom in Location-Based Social Networks (LBSNs), a considerable number of users report their activities in LBSNs in a participatory manner, which provides us with an unprecedented opportunity to study large-scale user behavioral data. In this article, we propose a participatory cultural mapping approach based on collective behavior in LBSNs. First, we collect the participatory sensed user behavioral data from LBSNs. Second, since only local users are eligible for cultural mapping, we propose a progressive “home” location identification method to filter out ineligible users. Third, by extracting three key cultural features from daily activity, mobility, and linguistic perspectives, respectively, we propose a cultural clustering method to discover cultural clusters. Finally, we visualize the cultural clusters on the world map. Based on a real-world LBSN dataset, we experimentally validate our approach by conducting both qualitative and quantitative analysis on the generated cultural maps. The results show that our approach can subtly capture cultural features and generate representative cultural maps that correspond well with traditional cultural maps based on survey data.

Bike sharing systems have been deployed in many cities to promote green transportation and a healthy lifestyle. One of the key factors for maximizing the utility of such systems is placing bike stations at locations that can best meet users' trip demand. Traditionally, urban planners rely on dedicated surveys to understand the local bike trip demand, which is costly in time and labor, especially when they need to compare many possible places. In this paper, we formulate the bike station placement issue as a bike trip demand prediction problem. We propose a semi-supervised feature selection method to extract customized features from the highly variant, heterogeneous urban open data to predict bike trip demand. Evaluation using real-world open data from Washington, D.C. and Hangzhou shows that our method can be applied to different cities to effectively recommend places with higher potential bike trip demand for placing future bike stations.

Data quality and budget are two primary concerns in urban-scale mobile crowdsensing applications. In this paper, we leverage the spatial and temporal correlation among the data sensed in different sub-areas to significantly reduce the required number of sensing tasks allocated (corresponding to budget), yet ensuring the data quality. Specifically, we propose a novel framework called CCS-TA, combining the state-of-the-art compressive sensing, Bayesian inference, and active learning techniques, to dynamically select a minimum number of sub-areas for sensing task allocation in each sensing cycle, while deducing the missing data of unallocated sub-areas under a probabilistic data accuracy guarantee. Evaluations on real-life temperature and air quality monitoring datasets show the effectiveness of CCS-TA. In the case of temperature monitoring, CCS-TA allocates 18.0-26.5% fewer tasks than baseline approaches, allocating tasks to only 15.5% of the sub-areas on average while keeping overall sensing error below 0.25°C in 95% of the cycles.

With the recent surge of location based social networks (LBSNs), activity data of millions of users has become attainable. This data contains not only spatial and temporal stamps of user activity, but also its semantic information. LBSNs can help to understand mobile users' spatial temporal activity preference (STAP), which can enable a wide range of ubiquitous applications, such as personalized context-aware location recommendation and group-oriented advertisement. However, modeling such user-specific STAP needs to tackle high-dimensional data, i.e., user-location-time-activity quadruples, which is complicated and usually suffers from a data sparsity problem. In order to address this problem, we propose a STAP model. It first models the spatial and temporal activity preference separately, and then uses a principle way to combine them for preference inference. In order to characterize the impact of spatial features on user activity preference, we propose the notion of personal functional region and related parameters to model and infer user spatial activity preference. In order to model the user temporal activity preference with sparse user activity data in LBSNs, we propose to exploit the temporal activity similarity among different users and apply nonnegative tensor factorization to collaboratively infer temporal activity preference. Finally, we put forward a context-aware fusion framework to combine the spatial and temporal activity preference models for preference inference. We evaluate our proposed approach on three real-world datasets collected from New York and Tokyo, and show that our STAP model consistently outperforms the baseline approaches in various settings.

Offline event marketing invites people to participate in a sponsored gathering, thus allowing marketers to have face-to-face, direct, and close contact with their current and potential customers. This paper presents a framework that supports marketers in improving marketing effectiveness by carefully selecting invitees to such sponsored offline events by leveraging location-based social networks. In particular, we first transform the participant selection task into a combinatorial optimization problem. Second, we propose a marketing effect quantitative model that considers the distance and overlapping social influence. Third, we introduce algorithms to determine a participant team that can maximize the marketing effect while fulfilling the scale and item coverage constraints. We finally evaluate the effectiveness of the framework and validate the proposed marketing effect of the quantitative model with real-world data.

Human memory often fails. People are frequently beset with questions like “Who is that person? I think I met him in Tokyo last year.” Existing memory aid tools cannot well support the recall of names effectively. This paper explores the memory recall enhancement issue from the perspective of memory cue extraction and associative search, and proposes a generic methodology to extract memory cues from heterogeneous, multimodal, physical/virtual data sources. Specifically, we use the contact name recall in the academic community as the target application to showcase our proposed methodology. We further develop an intelligent social contact manager that supports 1) autocollection of rich contact data from a combination of pervasive sensors and Web data sources, and 2) associative search of contacts when human memory fails. The system is validated by testing the performance of contact data collection techniques. An empirical user study on contact memory recall is also conducted, through which several findings about contact memorizing and recall are presented. Classic cognitive psychology theories are used to interpret these findings.

With the recent popularity of social network services, a significant volume of heterogeneous social media data is generated by users, in the form of texts, photos, videos and collections of points of interest, etc. Such social media data provides users with rich resources for exploring content, such as looking for an interesting video or a favorite point of interest. However, the rapid growth of social media causes difficulties for users to efficiently retrieve their desired media items. Fortunately, users' digital footprints on social networks such as comments massively reflect individual's fine-grained preference on media items, that is, preference on different aspects of the media content, which can then be used for personalized social media search. In this article, we propose SESAME, a fine-grained preference-aware social media search framework leveraging user digital footprints on social networks. First, we collect users' direct feedback on media content from their social networks. Second, we extract users' sentiment about the media content and the associated keywords from their comments to characterize their fine-grained preference. Third, we propose a parallel multituple based ranking tensor factorization algorithm to perform the personalized media item ranking by incorporating two unique features, viz., integrating an enhanced bootstrap sampling method by considering user activeness and adopting stochastic gradient descent parallelization techniques. We experimentally evaluate the SESAME framework using two datasets collected from Foursquare and YouTube, respectively. The results show that SESAME can subtly capture user preference on social media items and consistently outperform baseline approaches by achieving better personalized ranking quality.

With the recent surge of location-based social networks (LBSNs), such as Foursquare and Facebook Places, huge digital footprints of people's locations, profiles, and online social connections become accessible to service providers. Unlike social networks (e.g., Flickr, Facebook) that have explicit groups for users to subscribe to or join, LBSNs usually have no explicit community structure. In order to capitalize on the large number of potential users, quality community detection and profiling approaches are needed. In the meantime, the diversity of people's interests and behaviors when using LBSNs suggests that their community structures overlap. In this paper, based on the user check-in traces at venues and user/venue attributes, we come out with a novel multimode multi-attribute edge-centric coclustering framework to discover the overlapping and hierarchical communities of LBSNs users. By employing both intermode and intramode features, the proposed framework is not only able to group like-minded users from different social perspectives but also discover communities with explicit profiles indicating the interests of community members. The efficacy of our approach is validated by intensive empirical evaluations using the collected Foursquare dataset.

The crowdsourced digital footprints from Location Based Social Networks (LBSNs) contain not only rich information about locations, but also individual's feeling about locations and associated entities. This new data source provides us with an unprecedented opportunity to massively and cheaply collect location related information, and to subtly characterize individual's fine-grained preference about those places and associated entities. In this paper, we propose SEALs - a fine-grained preference-aware location search framework leveraging the crowdsourced traces in LBSNs. We first collect user check-ins and tips from Foursquare and use them as direct user feedback on locations. Second, we extract users' sentiment about locations and associated entities from tips to characterize their fine-grained location preference. Third, we incorporate such fine-grained user preference into personalized location ranking using tensor factorization techniques. Experimental results show that SEALs can achieve better location ranking comparing to the state-of-the-art solutions.

Crowd sourcing is a new paradigm of service provision. Current commercial crowd sourcing platforms rarely consider the interaction between task takers, which is extremely required in the disaster management scenario. In this paper, we designed a framework for community based crowd sourcing, i.e., task takers are from an existing community or will easily form a new community. A size-specified community creation method using multiple social contexts is also proposed.

The ability to leverage the power of a network of social contacts is important to get things done. However, as the number of contacts increases, people often find it difficult to maintain their contact network by using merely memory, and are frequently encompassed with questions like "who is that person, I met him in Tokyo last year". Existing contact tools make up for the shortage of unreliable human memory by storing contact information in the digital format, but laying much burden on users on manually inputting contact data. This paper, however, presents a social contact management system called SCM, which supports the auto-collection of rich contact data by exploring the aggregated power of pervasive sensing and Web intelligence techniques. Regarding that people often need to leverage several associated things (e.g., meeting location) to fetch other information about a contact (e.g., his name), we also develop an associative contact retrieval method. The effectiveness and runtime performance of our system is validated through a set of experiments.