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.

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%.

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%.

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.

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.

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.

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.

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.