Personality prediction from social media posts is a critical task that implies diverse applications in psychology and sociology. The Myers-Briggs Type Indicator (MBTI), a popular personality inventory, has been traditionally predicted by machine learning (ML) and deep learning (DL) techniques. Recently, the success of Large Language Models (LLMs) has revealed their huge potential in understanding and inferring personality traits from social media content. However, directly exploiting LLMs for MBTI prediction faces two key challenges: the hallucination problem inherent in LLMs and the naturally imbalanced distribution of MBTI types in the population. In this paper, we propose PostToPersonality (P2P), a novel LLM- based framework for MBTI prediction from social media posts of individuals. Specifically, P2P leverages Retrieval-Augmented Generation with in-context learning to mitigate hallucination in LLMs. Furthermore, we fine-tune a pre-trained LLM to improve model specification in MBTI understanding with synthetic minority oversampling, which balances the class imbalance by generating synthetic samples. Experiments conducted on a real-world social media dataset demonstrate that P2P achieves state-of-the-art performance compared with 10 ML/DL baselines.

Community search in heterogeneous graphs is fundamental to applications such as expert team formation and scholarly collaboration. Many existing studies leverage meta-paths, which are sequences of node and edge types, to capture semantic relationships in heterogeneous graphs. However, most of them only consider the existence of meta-path instances, overlooking their frequency and thus failing to capture relationship strength. This limitation can result in communities that include nodes with numerous but weak relations. To capture the strength of relationships in heterogeneous graphs, we define the Strong Community (StrCom) model, which evaluates the strength between users based on the number of connecting meta-path instances. Building upon this model, we further propose the Budgeted Strong Community (BSC) problem by incorporating a size constraint. We provide theoretical analyses showing that the BSC problem is NP-hard and not in APX. To address this problem, we design three strategies-Shrink, Expand, and Hybrid-along with several optimization techniques to improve efficiency. Extensive experiments on large real-world datasets (e.g., DBLP, YAGO, DBpedia) demonstrate the effectiveness and efficiency of our approach. Specifically, our method achieves 3.49-107.09× higher PathSim scores for StrCom and two to five orders of magnitude higher scores for BSC compared to state-of-the-art baselines, demonstrating that the identified communities are both semantically coherent and structurally compact.

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

With the increasing availability of trajectory data, it is important to have good indexes to facilitate query processing. In this work, we propose BT-Tree, which is built through a recursive bi-partitioning approach, for the processing of range and KNN queries for past trajectory data. We first propose a cost function based method (CFBM) to build the BT-Tree. Specifically, we design a novel cost function, which incorporates the characteristics of both the data and historical query workload, to decide how to partition a BT-Tree node. Then we propose a reinforcement learning (RL) based method to address CFBM's limitations, such as making locally optimal decisions that may lead to global suboptimality. Experiments on three real datasets with up to 800 million data points show that the CFBM generally outperforms the baselines in terms of query processing time and the RL based method consistently outperforms the baselines and has more significant advantages on larger datasets.

Blockchain technology has become a research hotspot in distributed systems, aiming to sustain a decentralized ledger via consensus. Traditional consensus solutions exhibit slow processing speed and response time, resulting in poor performance. To address this issue, several consensus protocols have been proposed. One such popular protocol is HotStuff, a Byzantine fault-tolerant consensus (BFT) that achieves high throughput at the cost of latency. However, its throughput suffers from a proportional decrease with the increase in latency, posing a significant challenge. In this paper, we propose a new protocol called Dolphin that builds upon HotStuff. It operates in a partially synchronous network with$n$replicas, up to$f$byzantine faults, where$n \ge 3f+1$, and achieves higher throughput in high-latency environments by leveraging non-blocking concurrent block generation. Specifically, we formalize our strategy as a generic Asynchronization Procedure Patch and prove that it does not affect the execution process of the original protocol. Theoretical analysis validates that Dolphin preserves the safety, liveness, and responsiveness properties while enhancing the throughput. The evaluation demonstrates that Dolphin typically achieves more than 10x higher throughput in Wide Area Network (WAN) environments with lower latency compared to HotStuff and its variants, and exhibits similar bandwidth utilization to DAG-based protocols such as Narwhal.

Blockchain technology builds an immutable and append-only ledger in peer-to-peer networks, which attracts attention from various fields. However, traditional chain-based blockchain systems typically have the problem of low throughput, leading to unsatisfactory performance. Among the proposed solutions, introducing a structure of the Directed Acyclic Graph (DAG) into the blockchain reaches a high transaction throughput. Such an approach enables blocks to refer to more than one previous block, thus processing blocks in parallel with better performance. However, existing DAG-based blockchain schemes do not establish a deterministic rule for block reference priority. Adversaries can initiate a splitting attack to select block references to affect DAG topology, making the consensus unstable. In this paper, we propose a more stable consensus protocol named Phantasm, aiming to stabilize the ordering result in the consensus protocol. The referred blocks can be decided after computing a solution to the block puzzle and the difficulty of this solution affects the number of block references. We design two strategies to guide the honest nodes to select references so that they can resist the splitting attacks to stabilize the ordering. Theoretical analysis and simulation experiments show that Phantasm is more stable than the classic DAG-based blockchain consensus protocol Phantom regarding the ordering results.

Learned indexes have been proposed to replace classic index structures like B-Tree with machine learning (ML) models. They require to replace both the indexes and query processing algorithms currently deployed by the databases, and such a radical departure is likely to encounter challenges and obstacles. In contrast, we propose a fundamentally different way of using ML techniques to build a better R-Tree without the need to change the structure or query processing algorithms of traditional R-Tree. Specifically, we develop reinforcement learning (RL) based models to decide how to choose a subtree for insertion and how to split a node when building and updating an R-Tree, instead of relying on hand-crafted heuristic rules currently used by the R-Tree and its variants. Experiments on real and synthetic datasets with up to more than 100 million spatial objects show that our RL based index outperforms the R-Tree and its variants in terms of query processing time.

Geo-textual objects with both geographical location and textual description are gaining in prevalence. Over the past decades, substantial research has been conducted on spatial keyword queries, which integrate location into keyword-based querying of geo-textual content. However, existing proposals mostly focus on efficiency for processing spatial keyword queries, and little effort was made to address the effectiveness perspectives. In this work, using two datasets with ground truth query results, we evaluate the effectiveness of standard spatial keyword queries. Our evaluation results show that the TkQ query that ranks objects by a weighted combination of spatial proximity and text relevance is the most effective. Motivated by the finding, we propose a Deep relevance with Weight learning (DrW) model to further improve the effectiveness of the retrieval ranking. DrW is featured with two novel ideas: First, we propose a neural network architecture to learn the text relevance matching over the local interaction between the query and geo-textual objects. Second, we find that a query-dependent weight to balance text relevance and spatial proximity in ranking can improve effectiveness, and we develop a learning-based method to learn the query-dependent weight. Experimental results reveal that our model outperforms state-of-the-art methods on effectiveness, with improvements up to 32.15%, 32.34%, and 33.00% in terms of NDCG@3, NDCG@5, and MRR.

The activities in many real-world applications, such as e-commerce and online education, are usually modeled as a dynamic bipartite graph that evolves over time. It is a critical task to detect anomalies inductively in a dynamic bipartite graph. Previous approaches either focus on detecting pre-defined types of anomalies or cannot handle nodes that are unseen during the training stage. To address this challenge, we propose an effective method to learn anonymous edge representation (AER) that captures the characteristics of an edge without using identity information. We further propose a model named AER-AD to utilize AER to detect anomalies in dynamic bipartite graphs in an inductive setting. Extensive experiments on both real-life and synthetic datasets are conducted to illustrate that AER-AD outperforms state-of-the-art baselines. In terms of AUC and F1, AER-AD is able to achieve 8.38% and 14.98% higher results than the best inductive representation baselines, and 6.99% and 19.59% than the best anomaly detection baselines.

The wide spread of rumors inflicts damages on social media platforms. Detecting rumors has become an emerging problem concerning the public and government. A crucial problem for rumors detection on social media is the lack of reliably pre-annotated dataset to train classification models. To solve this problem, we propose an unsupervised model that detects rumors by measuring how well the tweets follow the normal patterns. However, the problem is challenging in how to automatically discover the normal patterns of tweets. To tackle the challenge, we first propose a novel tree variational autoencoder model that reconstructs the sentiment labels along the propagation tree of a factual tweet. Then we propose a cross-alignment method to align the multiple modalities, i.e., tree structure and propagation features, and output the final prediction results. We conduct extensive experiments on a real-world dataset collected from Weibo. The experiments show that the proposed method significantly outperforms the state-of-the-art unsupervised methods and adapts better to the concept drift than state-of-the-art supervised methods.

Representing words as embeddings has been proven to be successful in improving the performance in many natural language processing tasks. Different from the traditional methods that learn the embeddings from large text corpora, ensemble methods have been proposed to leverage the merits of pre-trained word embeddings as well as external semantic sources. In this paper, we propose a knowledge-enriched ensemble method to combine information from both knowledge graphs and pre-trained word embeddings. Specifically, we propose an attention network to retrofit the semantic information in the lexical knowledge graph into the pre-trained word embeddings. In addition, we further extend our method to contextual word embeddings and multi-sense embeddings. Extensive experiments demonstrate that the proposed word embeddings outperform the state-of-the-art models in word analogy, word similarity and several downstream tasks. The proposed word sense embeddings outperform the state-of-the-art models in word similarity and word sense induction tasks.

With the proliferation of online social networks, a great deal of online user action data has been generated. Such data has enabled the study of information diffusion prediction, which is a fundamental problem for understanding the propagation of information on social media platforms. In diffusion prediction models, there are two standard components, i.e., a social graph and information diffusion cascades. We observe that both components exhibit latent hierarchical structures. However, most existing models are designed based on euclidean spaces, and hence cannot effectively capture complex patterns, especially hierarchical structures. Therefore, we investigate a novel research problem to learn hyperbolic representations for information diffusion prediction. To reflect the different characteristics of social graphs and diffusion cascades, we encode them into two latent hyperbolic spaces with different trainable curvatures. In addition, to model influence dependencies, we propose a co-attention mechanism to capture the processes of diffusion cascades using positional embeddings. Given a set of activated seed users, we jointly exploit diffusion cascades and social links to predict which users will be influenced. We conduct extensive experiments on four real-world datasets. Empirical results demonstrate that the proposed H-Diffu model significantly outperforms several state-of-the-art diffusion prediction frameworks.

The prevalence of GPS-enabled mobile devices and location-based services yield massive volume of spatial objects where each object contains information including geographical location, name, address, category and other attributes. This paper introduces a novel type of query termedexample-based spatial pattern matching(EPM) query. It takes as input a set of spatial objects, each of which is associated with one or more keywords and a location. These objects serve as an example that depicts the spatial pattern that users want to retrieve. The EPM query returns all sets of objects that match the spatial pattern. The EPM query can be used for applications like urban planning, scene recognition and similar region search. We propose an efficient algorithm and three pruning techniques to answer EPM queries. Furthermore, we provide an approximation guarantee for intermediate results of the algorithm. Our experimental evaluations on four real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithm and techniques.

Finding a set of co-clusters in a bipartite network is a fundamental and important problem. In this paper, we present the Attributed Bipartite Co-clustering (ABC) problem which unifies two main concepts: (i) bipartite modularity optimization, and (ii) attribute cohesiveness. To the best of our knowledge, this is the first work to find co-clusters while considering the attribute cohesiveness. We prove that ABC is NP-hard and is not in APX, unless P=NP. We propose three algorithms: (1) a top-down algorithm; (2) a bottom-up algorithm; (3) a group matching algorithm. Extensive experimental results on real-world attributed bipartite networks demonstrate the efficiency and effectiveness of our algorithms.

Searching for a community based on query nodes in a graph is a fundamental problem and has been extensively investigated. Most of the existing approaches focus on finding a community in a social network, and very few studies consider location-based social networks where users can check in locations. In this paper we propose the GeoSocial Community Search problem (GCS) which aims to find a social community and a cluster of spatial locations that are densely connected in a location-based social network simultaneously. The GCS can be useful for marketing and user/location recommendation. To the best of our knowledge, this is the first work to find a social community and a cluster of spatial locations that are densely connected from location-based social networks. We prove that the problem is NP-hard, and is not in APX, unless P = NP. To solve this problem, we propose three algorithms: core-based basic algorithm, top-down greedy removing algorithm, and an expansion algorithm. Finally, we report extensive experimental studies that offer insights into the efficiency and effectiveness of the proposed solutions.

With the proliferation of mobile devices and location-based services, continuous generation of massive volume of streaming spatial objects (i.e., geo-tagged data) opens up new opportunities to address real-world problems by analyzing them. In this paper, we present a novel continuous bursty region detection (SURGE) problem that aims to continuously detect a burstyregion of a given size in a specified geographical area from a stream of spatial objects. Specifically, a bursty region shows maximum spike in the number of spatial objects in a given time window. The SURGE problem is useful in addressing several real-world challenges such as surge pricing problem in online transportation and disease outbreak detection. To solve the problem, we propose an exact solution and two approximate solutions, and the approximation ratio is 1-α/4 in terms of the burst score, where α is a parameter to control the burst score. We further extend these solutions to support detection of top-k bursty regions. Extensive experiments with real-world data are conducted to demonstrate the efficiency and effectiveness of our solutions.

Representing words as embeddings in a continuous vector space has been proven to be successful in improving the performance in many natural language processing (NLP) tasks. Beyond the traditional methods that learn the embeddings from large text corpora, ensemble methods have been proposed to leverage the merits from pre-trained word embeddings as well as external semantic sources. In this paper, we propose a knowledge-enhanced ensemble method to combine both knowledge graphs and pre-trained word embedding models. Specifically, we interpret relations in knowledge graphs as linear translation from one word to another. We also propose a novel weighting scheme to further distinguish edges in the knowledge graph with same type of relation. Extensive experiments demonstrate that our proposed method is up to 20% times better than state-of-the-art in word analogy task and up to 16% times better than state-of-the-art in word similarity task.

With the proliferation of mobile devices and location-based services, increasingly massive volumes of geo-tagged data are becoming available. This data typically also contains non-location information. We study how to use such information to characterize a region and then how to find a region of the same size and with the most similar characteristics. This functionality enables a user to identify regions that share characteristics with a user-supplied region that the user is familiar with and likes. More specifically, we formalize and study a new problem called the attribute-aware similar region search ( ASRS ) problem. We first define so-called composite aggregators that are able to express aspects of interest in terms of the information associated with a user-supplied region. When applied to a region, an aggregator captures the region's relevant characteristics. Next, given a query region and a composite aggregator, we propose a novel algorithm called DS-Search to find the most similar region of the same size. Unlike any previous work on region search, DS-Search repeatedly discretizes and splits regions until an split region either satisfies a drop condition or it is guaranteed to not contribute to the result. In addition, we extend DS-Search to solve the ASRS problem approximately. Finally, we report on extensive empirical studies that offer insight into the efficiency and effectiveness of the paper's proposals.

With the proliferation of location-based services, the generation of massive geo-tagged data opens up new opportunities to address real-world problems. In this paper, we present a novel continuous bursty region detection (SURGE) problem that aims to continuously detect a bursty region of a given size in a specified geographical area from a stream of spatial objects. The SURGE problem is useful in addressing several real-world challenges such as disease outbreak detection. We propose an exact solution to address the problem, and show the efficiency and effectiveness by conducting experiments on real-world datasets.

With the proliferation of mobile devices, large collections of geospatial data are becoming available, such as geo-tagged photos. Map rendering systems play an important role in presenting such large geospatial datasets to end users. We propose that such systems should support the following desirable features: representativeness, visibility constraint, zooming consistency, and panning consistency. The first two constraints are fundamental challenges to a map exploration system, which aims to efficiently select a small set of representative objects from the current region of user's interest, and any two selected objects should not be too close to each other for users to distinguish in the limited space of a screen. We formalize it as the Spatial Object Selection (SOS) problem, prove that it is an NP-hard problem, and develop a novel approximation algorithm with performance guarantees. % To further support interactive exploration of geospatial data on maps, we propose the Interactive SOS (ISOS) problem, in which we enrich the SOS problem with the zooming consistency and panning consistency constraints. The objective of ISOS is to provide seamless experience for end-users to interactively explore the data by navigating the map. We extend our algorithm for the SOS problem to solve the ISOS problem, and propose a new strategy based on pre-fetching to significantly enhance the efficiency. Finally we have conducted extensive experiments to show the efficiency and scalability of our approach.

This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. We propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

The increasing popularity and growth of mobile devices and location-based services enable us to utilize large-scale geo-tagged data to support novel location-based applications. This paper introduces a novel problem called the best region search (BRS) problem and provides efficient solutions to it. Given a set O of spatial objects, a submodular monotone aggregate score function, and the size a x b of a query rectangle, the BRS problem aims to find a x b rectangular region such that the aggregate score of the spatial objects inside the region is maximized. This problem is fundamental to support several real-world applications such as most influential region search (eg. the best location for a signage to attract most audience) and most diversified region search (eg. region with most diverse facilities). We propose an efficient algorithm called SliceBRS to find the exact answer to the BRS problem. Furthermore, we propose an approximate solution called CoverBRS and prove that the answer found by it is bounded by a constant. Our experimental study with real-world datasets and applications demonstrates the effectiveness and superiority of our proposed algorithms.

With the increasing popularity of mobile devices and location based services, massive amount of geo-textual data (e.g., geo-tagged tweets) is being generated everyday. Compared with traditional spatial data, the textual dimension of geo-textual data greatly enriches the data. Meanwhile, the spatial dimension of geo-textual data also adds a semantically rich new aspect to textual data. The large volume, together with its rich semantics, calls for the need for data exploration. First, it has many applications to retrieve a region for exploration that satisfies user-specified conditions (e.g., the size and shape of the region) while maximizing some other conditions (e.g., the relevance to the query keywords of the objects in the region). Second, it is useful to mine and explore the topics of the geo-textual data within a (specified or retrieved) region and perhaps a timespan. This demonstration proposal presents the main ideas of our system, the RegIon Search and Exploration System (RISE), for efficiently supporting region search and exploration, and our demonstration plan.

Computing shortest paths and distances is one of the fundamental problems on graphs, and it remains a challenging task today. This article investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. To do this, we propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We first show that routing proxies hold good properties for speeding-up shortest path and distance queries. Then, we design a linear-time algorithm to compute routing proxies and their corresponding DRAs. Finally, we experimentally verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

Recently, with the emergence of event-based online social services(e.g. Meetup), there have been increasing online activities to create, distribute, and organize social events. In this paper, we take the first systematic step to discover influential event organizers from online social networks who are essential to the overall success of social events. Informally, such event organizers comprise a small group of people who not only have the relevant skills or expertise that are required for an event (e.g. conference) but they are also able to influence largest number of people to actively contribute to it. We formulate it as the problem of mining influential cover set (ICS) where we wish to find k users in a social network G that together have the required skills or expertise (modeled as attributes of nodes in G) to organize an event such that they can influence the greatest number of individuals to participate in the event. The problem is, however, NP-hard. Hence, we propose three algorithms to find approximate solutions to the problem. The first two algorithms are greedy; they run faster, but have no guarantees. The third algorithm is 2-approximate and guarantees to find a feasible solution if any. Our empirical study over several real-world networks demonstrates the superiority of our proposed solutions.