The goal of community search in heterogeneous information networks (HINs) is to identify a set of closely related target nodes that includes a query target node. In practice, a size constraint is often imposed due to limited resources, which has been overlooked by most existing HIN community search works. In this paper, we introduce the size-bounded community search problem to HIN data. Specifically, we propose a refined (k, P)-truss model to measure community cohesiveness, aiming to identify the most cohesive community of size s that contains the query node. We prove that this problem is NP-hard. To solve this problem, we develop a novel B\&B framework that efficiently generates target node sets of size s. We then tailor novel bounding, branching, total ordering, and candidate reduction optimisations, which enable the framework to efficiently lead to an optimum result. We also design a heuristic algorithm leveraging structural properties of HINs to efficiently obtain a high-quality initial solution, which serves as a global lower bound to further enhance the above optimisations. Building upon these, we propose two exact algorithms that enumerate combinations of edges and nodes, respectively. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of the proposed methods.

Maximal cliques are useful in many applications, e.g., community detection, bioinformatics, anomaly detection and graph visualization. Enumerating maximal cliques from a graph is a computationally challenging problem, as the output size can be exponentially large with respect to the vertex number. Such a large number of cliques typically overlap heavily, which brings information redundancy when being applied to aforementioned domains. This paper studies how to use a small set of maximal cliques, i.e., a summary, to summarize all the maximal cliques in a graph. The state-of-the-art suffers from inefficiency in updating the summary with progressively generated cliques, especially when the summary grows large. In this work, we identify the challenge of summary updating to be how to efficiently estimate the overlap between cliques in the summary and each newly found maximal clique. By exploiting the vertex order information, we propose the notion of clique comparator, and devise four types of operators to quickly identify clique overlap in less costly manners. We conduct extensive experiments on six real-world datasets to verify the effectiveness of our approach, which reduces unnecessary clique intersection calculations by at least seven orders of magnitude and achieves a speedup of 2.5 ~3.1 times compared to the state-of-the-art.

Community Search in heterogeneous information networks HINs has received great attention recently, which aims to group community members extensively connected via derived relationships based on a meta-path since there exists no real relationship between members. However, in many applications, it is desired that the derived relationships are more focused on certain query requirements and that the community members are seriously engaged. What is more, to ensure sufficient flexibility, i.e., query requirements could be closely related or relatively loose, we may need multiple communities to collectively cover all query requirements. To the best of our knowledge, there is no existing work providing such flexibility. In this paper, we propose a novel model called society. It first ensures that each derived relationship is related to query requirements, and each community member should be involved at least k in such derived relationships, i.e., the community members exhibit high homogeneous cohesiveness. To the best of our knowledge, there is no existing work providing such flexibility. Then, to ensure the serious engagement of each member, we propose a novel constraint set called heterogeneous constraints, which ensures each member seriously interacts with heterogeneous vertices consisting of the derived relationship. At last, the society model allows for finding a set of communities that collectively cover all requirements. The main challenge of searching society is to efficiently and dynamically maintain the derived relationships since the deletion of a heterogeneous vertex against a heterogeneous constraint can induce dramatic changes over the derived relationships. We propose a novel unified peeling algorithm so that we can control deletions of vertices against homogeneous and heterogeneous cohesiveness and, therefore, provide opportunities for dynamically maintaining the derived relationships. An effective dynamic data structure is then proposed to avoid re-computations of the derived relationships. After that, batch update techniques are studied, which ensure that the time complexity of updating a batch is equivalent to a single update. Extensive experimental studies are conducted on real datasets to justify the effectiveness of our proposed model and the efficiency of the proposed techniques.

The number of bicliques in a bipartite graph may grow exponentially as its vertices increase. A biclique summary is a subset of all maximal bicliques and can somehow represent all maximal bicliques. In practical application scenarios, a summary helps users obtain more representative results. Due to its compact size, it enables users to efficiently locate and select the information they need. For instance, in the biomedical field, when researchers explore relationships between genes and proteins, they are often faced with an excessive number of combinations. Using a summary of these gene-protein relationships not only provides more representative insights but also significantly reduces the time needed for analysis. To find such representative maximal bicliques faster, we propose a method to determine whether to terminate the current search by computing lower bounds. We begin by introducing a baseline method, MBS, followed by two algorithms that incorporate bound pruning: MBSL, a neighborhood-based search algorithm, and MBSc, an$(\alpha,\beta)$- core-based search algorithm. We also provide three strategies for optimizing the algorithms. They are the Upper Bound Deflation Pruning method, the Intersection Deflation Heuristic method, and the Lazy Lower Bound Evaluation method. Based on the above optimization strategies, we present the advanced algorithms MBSA and MBScA. In experiments, we demonstrate the efficiency and result quality of the proposed algorithms. After incorporating three optimization strategies, MBSA and MBScA show improvements in computation time compared to the baseline MBS and are able to generate smaller summaries.

Multi-modal Knowledge Graph Completion (MKGC) aims at leveraging multi-modal information to infer missing objective facts in incomplete multi-modal knowledge graphs, thereby significantly enhancing their expressive capabilities. The segmentation of semantic data, including image segmentation and word-level descriptions, often contain implicit relationships between entities that are frequently overlooked by existing methodologies, thus limiting the effectiveness of reasoning tasks. Therefore, we propose a novel completion inference method based on fine-grained semantic segmentation, which enhances reasoning capability by utilizing implicit relationships between entities. Primarily, we introduce the concept of Semantic Related Entity (SRE) and a novel SRE selection algorithm, which captures the semantic neighboring relationships of entities based on segmentation semantic similarity to fully exploit the semantic association information. Subsequently, we propose a Multi-modal Related Entity Fusion Transformer (M-REFT) model to effectively utilize SREs from semantic modalities and neighbors from structural modality for completion inference. The M-REFT employs a hierarchical Transformer architecture to encode the fusion modality representation between each entity and its SREs, and then decode the triplet representation with the neighbor information to identify missing entities in incomplete triplets. We conducted extensive comparative experiments with several state-of-the-art models on three datasets, demonstrating the significant performance advantages of M-REFT. A series of ablation experiments and case studies further validate the rationality and necessity of the SRE concept and the SRE selection algorithm.

Graph neural networks play a pivotal role in various location-based applications, showcasing their compelling ability to capture collaborative signals across user check-in sequences. Recent advancements in next POI recommendation have further leveraged spatio-temporal graphs to uncover the transitional and geographical regularities. However, these methods are usually vulnerable due to the presence of data biases in real-life scenarios, which may mislead the model to disproportionately favoring certain POIs. To this end, this paper proposes a new graph debiasing paradigm for POI recommendation, which disentangles causal and bias knowledge within spatio-temporal graphs, allowing for not only the mitigation of bias issues, but also the utilization of causal information from spatial and temporal perspectives. Specifically, to facilitate graph debiasing at its topological level, an adaptive edge mask generator is first designed to explicitly decompose an entangled graph into causal and bias subgraphs. We encourage the stable relationships between the causal subgraph and the prediction, while the bias subgraph targets at the skewed bias distribution. We further enhance the independence between such two parts by employing a causal-bias disagreement regularization to encourage their distribution in separate semantic spaces. In addition, an inter-view contrastive learning module is also applied to maintain the relation discriminability of transitional and geographical representations. Extensive experiments on three real-world datasets demonstrate the superiority of our proposed model on recommendation performance, as well as its robustness against data bias.

Trajectory metric learning, which supports the trajectory similarity search, is one of the most fundamental tasks in spatial-temporal data analysis. However, existing trajectory metric learning methods rely on massive labels of pairwise trajectory distance, and thus cannot be applied to few-shot scenarios frequently occurring in real-world applications. Though performance drops caused by insufficient labels can be alleviated by knowledge distillation, we demonstrate that they cannot be directly applied to few-shot trajectory metric learning due to the domain shift problem. To this end, this paper proposes invariant and relaxed learning enhanced knowledge distillation method TMLKD for few-shot trajectory metric learning, such that domain-invariant representation and rank knowledge can be distilled. Specifically, in the representation learning phase, it first employs an adversarial sub-network to distinguish domain-specific and domain-invariant information, so as to distill transferable representation knowledge from teacher models. To mitigate the few-shot problem in student model training, we further enrich sparse labels of the target domain by utilizing the rank knowledge revealed in teachers' predictions. Particularly, TMLKD employs a list-wise learning-to-rank approach to learn the relaxed trajectory ranking orders instead of focusing on all the samples inefficiently. Finally, to guide accurate distillation, we adaptively assign reliability of teacher prediction by utilizing the ground-truth labels, to avoid misleading the student model with low-quality teacher predictions. Extensive experiments on three real-world datasets demonstrate the superiority of our model.

Group recommendation aims to recommend desired items for a group of users. Existing methods mainly adopt deterministic networks to represent groups as fixed-point vectors, assuming their preferences be highly close to these vectors in interest space. However, each group tends to have various interests, which cannot be fully captured by fixed-point vectors and thus calls for probabilistic modeling of interests as density instead. Although this can be supported by Variational AutoEncoder (VAE), interaction data in group recommendation are highly sparse and insufficient for VAE model training, resulting in high risks of posterior collapse and deficiency in personalization. To this end, this paper proposes a contrastive variational learning model boosted by variational model augmentation and an easyto-hard paradigm. Specifically, VAE with tailored attention is first employed to represent group preferences as variational vectors for probabilistic preference modeling. Additionally, we conduct data-agnostic augmentation via learnable variational dropout, which removes redundant or irrelevant neurons in VAE to generate meaningful augmented views adequately for contrastive learning in spite of data sparsity. Difficulty-aware negative sampling is further applied to generate high-quality negative samples adapting to varying requirements of task difficulty according to the training process. Finally, we utilize density-based variational alignment to guide the optimization process of contrastive learning. Experiments on four real-world datasets are conducted to demonstrate the significant performance improvements of our model compared with SOTA methods for group recommendation.

Graph data has been widely applied due to its powerful expressive capabilities. The release of raw graph data without preprocessing may lead to privacy information leakage. Thus, generating privacy-protected graphs is necessary for data analysis. Current privacy protection methods in graphs focus on securing attributes like degree distribution, triangle counts, and node information, but they often overlook the need to protect user group relationships. Additionally, some privacy-preserving graph publishing methods introduce significant noise due to the chosen graph generation techniques and the points at which noise is added. This paper aims to propose an effective graph synthesis algorithm by using differential privacy named DPCAG (Differentially Private Community Affiliation Graph Generation Model) for protecting user group relationships. Firstly, it is observed that there are numerous small probabilities in the adjacency matrix D generated by the affiliation matrix F, directly utilizing it to construct graph G would result in the generation of a substantial number of redundant edges. Therefore, we introduce a generating threshold theta to filter out unnecessary edges. Secondly, to achieve a better balance between data availability and the level of privacy protection, two budget allocation schemes are designed based on the introduction of k-truss to describe the tightness of group relationships. Lastly, we demonstrate the proposed model satisfies differential privacy mathematically and the effectiveness of DPCAG is validated using four real graph datasets.

Enumerating all the bipartite cohesive subgraphs in a bipartite graph has been studied extensively. However, for some applications, one is interested in finding bipartite cohesive subgraphs containing a specific vertex. In this paper, we study a new query-dependent bipartite cohesive subgraph search problem based on k-wing model. To address the problem, we propose two efficient and wing number conserving indexing schemes, EquiWing-Graph and a more compact index, EquiWing-Tree, which is achieved by using our proposed k-butterfly loose approach and discovered hierarchy properties. Moreover, we discover novel properties that help us localize the scope of the maintenance in our proposed indices at a lower cost for evolving bipartite graphs. Extensive experimental results evidence the efficiency and effectiveness of our proposed approaches.

Group recommendation aims to recommend desired items for a group of users. Due to the sparsity of group-item interactions, existing methods mainly model group preferences by aggregating member-level preference. However, they not only ignore possible user interest drift in specific groups, but also adopt deterministic models to represent group preferences using fixed-points, which are weak in characterizing uncertain group preferences. To this end, following the paradigm of variational learning, this paper proposes a multi-view attentive variational preference aggregation network called GroupAV for group rec-ommendation, so as to conduct user/group preference modeling and aggregation in a density-based manner. Specifically, we first adopt Variational AutoEncoder (VAE) to capture member-level preferences by variational vectors as density. To address user interest drift in groups, a variational preference adapter module is designed to learn group-contextualized preferences via rational transformation in variational space. Next, attentive variational aggregation networks are carefully designed for group-level preference aggregation in two different views (i.e., group-interactions and member-consensus views). Besides, we apply contrastive learning and gating fusion to optimize the multi-view learning process for the final group preference modeling of Mixture-of-Gaussian distribution. Finally, we conduct experiments on real-world datasets and demonstrate GroupAV's significant performance improvements compared to state-of-the-art group recommendation methods.

Probabilistic knowledge graphs (PKGs) improve traditional knowledge graphs by characterizing the inherent uncertainty of knowledge. In PKGs, each triple$(e_{1}, r,e_{2})$, representing that entity$e_{1}$has a relationship$r$with entity$e_{2}$, is associated with a probability$\phi$indicating its likelihood of being true. PKGs have gained popularity in various domains, such as ProBase [22] and NELL [13].

Community search over large dynamic graph has become an important research problem in modern complex networks, such as the online social network, collaboration network and biological networks. Network data in the time-varied environment has motivated several recent studies to identify the evolution of the communities. However, these studies mostly match communities of different snapshot or utilize the aggregation of the disjoint structural information and ignores the cohesion continuity. To fill this research gap, in this work, we propose a novel$(\theta ,k)$-core reliable community (CRC) and define the reliable community search problem which jointly considers member engagement, connection strength and cohesion continuity of the community in the dynamic network. We propose an online search algorithm based on eligible edge filtering and we further construct the Weighted Core Forest-Index (WCF-index) and develop efficient index-based querying algorithm with strong pruning properties. We also propose top-$l$reliable community search problem that couples query based distance to reduce the free rider effect in local community search and support flexible multiple query vertices. Extensive experiments are conducted to show the efficiency and effectiveness of the proposed algorithms.

Recent work has explored federated clustering and developed an efficient k-means based method. However, it is well known that k-means clustering underperforms in high-dimensional space due to the so-called "curse of dimensionality". In addition, high-dimensional data (e.g., generated from healthcare, medical, and biological sectors) are pervasive in the big data era, which poses critical challenges to federated clustering in terms of, but not limited to, clustering effectiveness and communication efficiency. To fill this significant gap in federated clustering, we propose a one-shot federated subspace clustering scheme Fed-SC that can achieve remarkable clustering effectiveness on high-dimensional data while keeping communication cost low using only one round of communication for each local device. We further establish theoretical guarantees on the clustering effectiveness of one-shot Fed-SC and exploit the benefits of statistical heterogeneity across distributed data. Extensive experiments on synthetic and real-world datasets demonstrate significant effectiveness gains of Fed-SC compared with both subspace clustering and one-shot federated clustering methods.

Temporal Knowledge Graphs (TKGs), which record the evolution of relationships among entities over time, have been increasingly used in a myriad of applications. Despite their growing importance, the challenge of aligning entities in these evolving structures has yet to be satisfactorily addressed. Most existing techniques struggle to keep pace with the continual stream of new entities and relations, which is a defining characteristic of TKGs. In response to this challenge, we propose a novel teacher-student approach for incremental entity alignment in evolving TKGs. Our solution leverages a Graph Attention Network (GAT) as the teacher model and a sampling Graph Convolutional Network (GCN) as a lightweight, adaptable student model. This approach efficiently navigates the evolving complexities inherent in TKGs, leading to remarkable improvements in the efficiency and effectiveness of entity alignment. The experimental results substantiate the superior performance of our approach in achieving effective entity alignment promptly, outstripping existing state-of-the-art models. As such, our study contributes a crucial step towards efficiently handling evolving entity alignment tasks in TKGs.

Social media platforms provide rich data sources in several domains. In mental health, individuals experiencing an Eating Disorder (ED) are often hesitant to seek help through conventional healthcare services. However, many people seek help with diet and body image issues on social media. To better distinguish at-risk users who may need help for an ED from those who are simply commenting on ED in social environments, highly sophisticated approaches are required. Assessment of ED risks in such a situation can be done in various ways, and each has its own strengths and weaknesses. Hence, there is a need for and potential benefit of a more complex multimodal approach. To this end, we collect historical tweets, user biographies, and online behaviours of relevant users from Twitter, and generate a reasonably large labelled benchmark dataset. Thereafter, we develop an advanced multimodal deep learning model called EDNet using these data to identify the different types of users with ED engagement (e.g., potential ED sufferers, healthcare professionals, or communicators) and distinguish them from those not experiencing EDs on Twitter. EDNet consists of five deep neural network layers. With the help of its embedding, representation and behaviour modeling layers, it effectively learns the multimodalities of social media. In our experiments, EDNet consistently outperforms all the baseline techniques by significant margins. It achieves an accuracy of up to 94.32% and F1 score of up to 93.91% F1 score. To the best of our knowledge, this is the first such study to propose a multimodal approach for user-level classification according to their engagement with ED content on social media.

Cohesive multipartite subgraphs (CMS) in heterogeneous information networks (HINs) uncover closely connected vertex groups of multiple types, enhancing real applications like community search and anomaly detection. However, existing works for HINs pay less attention to searching CMS. In this paper, we leverage well-established concepts of meta-path and densest subgraph to propose a novel CMS model called the densest P -partite subgraph. Given a multipartite subgraph of an HIN induced by i =| P | types of vertices defined in a query meta-path P (i.e., a P -partite subgraph), we devise a novel density function which is the number of the instances of P over the geometric mean of the sizes of i different types of vertex sets in the subgraph. A P -partite subgraph with the highest density serves as the optimum result. To find the densest P -partite subgraph in an HIN with n vertices, we first design an exact algorithm with a runtime cost equivalent to solving Θ(|M|) instances of the min-cut problem where |M|= O (( n/i ) i ). Then, we attempt a more efficient approximation algorithm that achieves a ratio of 1/ i but still incurs the cost of solving Θ(|M|) instances of our proposed peeling problem. Both approaches struggle with scalability due to Θ(|M|). To overcome this bottleneck, we improve the exact algorithm with novel pruning rules that non-trivially reduce the number of min-cut problem instances to solve to O (|M|). Empirically, 70-90% instances are pruned, making the improved exact algorithm significantly faster than the approximation algorithm. Extensive experiments on real datasets demonstrate the effectiveness of the proposed model and the efficiency of our algorithms.

There are extensive studies focusing on the application scenario that all the bipartite cohesive subgraphs need to be discovered in a bipartite graph. However, we observe that, for some applications, one is interested in finding bipartite cohesive subgraphs containing a specific vertex. In this paper, we study a new query-dependent bipartite cohesive subgraph search problem based on$k$-wing model, named as personalized$k$-wing search problem. We study the$k$-wing equivalence relationship to summarize the edges of a bipartite graph$G$into groups. Therefore, all the edges of$G$are segregated into different groups, i.e.$k$-wing equivalence class, forming an efficient and wing number conserving index calledEquiWing-Graph. Further, we propose a more compact index,EquiWing-Tree, which is achieved by using our proposed$k$-butterfly looseapproach and discovered hierarchy properties. These indices are used to expedite the personalized$k$-wing search with a non-repetitive access to$G$, which leads to linear algorithms for searching the personalized$k$-wing. Moreover, we conduct a thorough study on the maintenance of the proposed indices for evolving bipartite graphs. We discover novel properties that help us localize the scope of the maintenance at a low cost. By exploiting the discoveries, we propose novel algorithms for maintaining the two indices, which substantially reduces the cost of maintenance. We perform extensive experimental studies in real-world graphs to validate the efficiency and effectiveness ofEquiWing-GraphandEquiWing-Treecompared to the baseline.

Fastest route recommendation (FRR) is crucial for intelligent transportation systems. The existing methods treat it as a pathfinding problem on dynamic graphs, and extend A* algorithm with neuralized travel time estimators as cost functions. However, they fail to provide effective heuristic cost due to the neglect of its admissibility and the utilization of noise path information, resulting in sub-optimal results and inefficiency. Besides, path sequentiality is also ignored, affecting algorithm accuracy as well. In this paper, we propose a variational inference based fastest route recommendation method, which follows the framework of A* algorithm and provides effective costs for routing. Specifically, we first adopt a sequential estimator to accurately estimate the travel time of a specific path. More importantly, we design a variational inference based estimator, which models the distribution of travel time between two nodes and provides an effective heuristic cost with high probability of being admissible. We further take advantage of adversarial learning to enrich the fastest path information. To the best of our knowledge, we are the first to use variational estimator to consider the admissibility of heuristics in FRR. Extensive experiments are conducted on two real-world datasets. The results verify the performance advantage of our proposed method.

Enumeration of all maximal bicliques in bipartite graphs is a well-studied fundamental problem. However, a wide range of applications need less overlapping bicliques with specific size constraints instead of all the maximal bicliques. In this paper, we study a new biclique problem, called the top-k t-biclique coverage problem. A t-biclique is a biclique with a size constraint$t$for one vertex set and the problem aims to find$k$t-bicliques maximising the coverage on the other vertex set. The top-k t-biclique coverage problem has novel applications such as finding top-k courses while maximising student engagement. We prove that this problem is NP-hard. A straightforward way to address the problem first needs to enumerate and store all t-bicliques and then greedily select$k$promising t-bicliques, leading an approximate guarantee on the coverage. However, it takes exponential space, which is impractical. We then apply a fast approximation scheme to solve this problem, which shaves the exponential space consumption by progressively updating top-k results during the t-biclique enumeration. Observing that the fast approximation algorithm takes too much time on updating the results due to the coverage is computed from scratch for each update, an online index is devised to address the drawback. Due the hardness of the problem, even the fast approximation algorithm cannot scale to large dataset. To devise a scalable solution, we then propose a heuristic algorithm running in polynomial time. Thanks for four carefully designed heuristic rules, the heuristic algorithm can find large coverage top-k t-bicliques extremely fast for large datasets. Apart from that, the heuristic result with large coverage can effectively prune unpromising enumerations in the fast greedy algorithm, which improves the efficiency of the fast approximation algorithm without compromising the approximation ratio. Extensive experiments are conducted on real datasets to justify the effectiveness and efficiency of the proposed algorithms.

Maximal clique, the most cohesive structure in a graph, has a broad range of applications, e.g., community detection, bioinformatics, anomaly detection, and graph visualization. However, the sheer number of maximal cliques brings the challenge to fully examine them all. In addition, the omnipresent overlaps between cliques imply that it may not be necessary to process every maximal clique, since many vertices are shared in multiple cliques. A real example is that, in commercial advertising, a small group of individuals who participate in different communities can help spread an advertisement across all the communities. Inspired by this observation, we study the problem of finding a τ-cover, which is a subset of vertices in a graph. This subset overlaps with each maximal clique by no less than τ, where τ is a threshold reflecting the user's requirement. We prove the NP-hardness and the non-submodularity of finding a minimum τ-cover. As a result, to find a small τ-cover as best effort, we propose three methods: MCCb, MCC, and EMCC. MCCb is a baseline that adds vertices into the cover while doing clique enumeration until the coverage requirement is satisfied. MCC decides whether to add a vertex with more caution by evaluating the increment of coverage lower bound with O(1) time complexity. EMCC is a randomized algorithm built on an elegant adaptive sampling, which further achieves cover conciseness by relaxing the coverage requirement in a statistical manner. Extensive experiments show that MCC (1.3 ∽ 2.5 × faster) produces a cover whose size is 1/2 of MCCb, and EMCC (2 ∽ 5 × faster) averagely produces a cover whose size is one order of magnitude smaller vs. MCCb.

Maximal bicliques are effective to reveal meaningful information hidden in bipartite graphs. Maximal biclique enumeration (MBE) is challenging since the number of the maximal bicliques grows exponentially w.r.t. the number of vertices in a bipartite graph in the worst case. However, a large bipartite graph is usually very sparse, which is against the worst case and may lead to fast MBE algorithms. The uncharted opportunity is taking advantage of the sparsity to substantially improve the MBE efficiency for large sparse bipartite graphs. We observe that for a large sparse bipartite graph, a vertex u may converge to a few vertices in the same vertex set as u via its neighbours, which reveals that the enumeration scope for a vertex could be very small. Based on this observation, we propose novel concepts: unilateral coreness for individual vertices, unilateral order for each vertex set and unilateral convergence (ζ) for a large sparse bipartite graph, ζ could be a few thousand for a large sparse bipartite graph with hundreds of million edges. Using the unilateral order, every vertex with τ unilateral coreness only needs to check at most 2 τ combinations so that all maximal bicliques can be enumerated and τ is bounded by ζ, which leads to a novel MBE algorithm running in O * (2 ζ ). We then propose a batch-pivots technique to eliminate all enumerations resulting in non-maximal bicliques, which guarantees that every maximal biclique is reported in O (ζ e )-delay, where e is the number of edges. We devise novel data structures that allow storing subgraphs at omissible space for further speeding up MBE. Extensive experiments are conducted on synthetic and real large datasets to justify that our proposed algorithm is faster and more scalable than the existing algorithms.

Searching for local communities is an important research problem that supports advanced data analysis in various complex networks, such as social networks, collaboration networks, cellular networks, etc. The evolution of such networks over time has motivated several recent studies to identify local communities in dynamic networks. However, these studies only utilize the aggregation of disjoint structural information to measure the quality and ignore the reliability of the communities in a continuous time interval. To fill this research gap, we propose a novel (θ, k )- core reliable community (CRC) model in the weighted dynamic networks, and define the problem of most reliable community search that couples the desirable properties of connection strength, cohesive structure continuity, and the maximal member engagement. To solve this problem, we first develop a novel edge filtering based online CRC search algorithm that can effectively filter out the trivial edge information from the networks while searching for a reliable community. Further, we propose an index structure, Weighted Core Forest-Index (WCF-index), and devise an index-based dynamic programming CRC search algorithm, that can prune a large number of insignificant intermediate results and support efficient query processing. Finally, we conduct extensive experiments systematically to demonstrate the efficiency and effectiveness of our proposed algorithms on eight real datasets under various experimental settings.

Density Peak Clustering (DPC), a popular density-based clustering approach, has received considerable attention from the research community primarily due to its simplicity and fewer-parameter requirement. However, the resultant clusters obtained using DPC are influenced by the sensitive parameter$d_c$, which depends on data distribution and requirements of different users. Besides, the original DPC algorithm requires visiting a large number of objects, making it slow. To this end, this paper investigates index-based solutions for DPC. Specifically, we propose two list-based index methods viz. (i) a simple List Index, and (ii) an advanced Cumulative Histogram Index. Efficient query algorithms are proposed for these indices which significantly avoids irrelevant comparisons at the cost of space. For memory-constrained systems, we further introduce an approximate solution to the above indices which allows substantial reduction in the space cost, provided that slight inaccuracies are admissible. Furthermore, owing to considerably lower memory requirements of existing tree-based index structures, we also present effective pruning techniques and efficient query algorithms to support DPC using the popular Quadtree Index and R-tree Index. Finally, we practically evaluate all the above indices and present the findings and results, obtained from a set of extensive experiments on six synthetic and real datasets. The experimental insights obtained can help to guide in selecting a befitting index.

Session-based recommendation is to predict an anonymous user's next action based on the user's historical actions in the current session. However, the cold-start problem of limited number of actions at the beginning of an anonymous session makes it difficult to model the user's behavior, i.e., hard to capture the user's various and dynamic preferences within the session. This severely affects the accuracy of session-based recommendation. Although some existing meta-learning based approaches have alleviated the cold-start problem by borrowing preferences from other users, they are still weak in modeling the behavior of the current user. To tackle the challenge, we propose a novel cluster-based meta-learning model for session-based recommendation. Specially, we adopt a soft-clustering method and design a parameter gate to better transfer shared knowledge across similar sessions and preserve the characteristics of the session itself. Besides, we apply two self-attention blocks to capture the transition patterns of sessions in both item and feature aspects. Finally, comprehensive experiments are conducted on two real-world datasets and demonstrate the superior performance of CBML over existing approaches.

The number of maximal cliques could be exponentially large with respect to the number of vertices. A clique summary is a subset of all the maximal cliques and can somehow represent all the maximal cliques. Finding such a summary is deemed important in information distribution, influence estimation, cost-effective marketing, etc. The existing approach that finds a maximal clique summary suffers from long running time due to the excessive number of costly bound calculations that are used to estimate the size of to-be-found cliques during the enumeration process. Furthermore, we found that, sometimes, the bound calculation is not necessary at all. As a result, in order to provide the best study of the problem, we propose four strategies in two directions to speed up the process of finding a maximal clique summary by (1) restricting the bound calculation operation to a particular subset of all search branches and (2) making the best use of the bounds that have been previously calculated. Extensive experiments are conducted on eight real-world datasets to validate our strategies. Results demonstrate that the proposed method can reduce the number of bound calculations by 3 ~ 5 orders of magnitude, and each run of our algorithm can be up to 2.x times faster than the state-of-the-art algorithm while still keeping the summary concise. Our method can potentially benefit other large-output enumeration based problems, such as frequent itemset mining, when a summary of results is needed.

Clusters reflect a potential relationship among different entities of data. This data can be sourced from a wide range of domains like market research, spatial data analysis, etc. Many clustering algorithms have been developed in the last few decades in response to the proliferating demands across industries and organizations, which help them make operational and strategic decisions. Among them, density-based clustering algorithms are popular, which find subsets of objects in "dense regions" separated by not-so-dense regions, where each subset represents a cluster. In this paper, our focal point will be Density Peak Clustering (DPC) [1] , a popular approach towards obtaining density-based clusters.

Given a bipartite graph, the maximum balanced biclique (MBB) problem, discovering a mutually connected while disjoint sets of equal size with the maximum cardinality, plays a significant role for mining the bipartite graph and has numerous applications. Despite the NP-hardness of the MBB problem, in this paper, we show that an exact MBB can be discovered extremely fast in bipartite graphs for real applications. We propose two exact algorithms dedicated for small dense and large sparse bipartite graphs respectively. For dense bipartite graphs, an O*(1.3803n) algorithm is proposed. This algorithm in fact can find an MBB very fast for small dense bipartite graphs that are common for applications such as VLSI design. This is because, using our proposed novel techniques, the search can fast converge to sufficiently dense bipartite graphs which we prove to be polynomial-time solvable. For large sparse bipartite graphs typical for applications such as biological data analysis, an O*(1.3803 δ) algorithm is proposed, where δ is only a few hundred for large sparse bipartite graphs with millions of vertices. The indispensible optimization that leads to this time complexity is: we transform a large sparse bipartite graph into a limited number of dense subgraphs such that each of the dense subgraphs has up to δ vertices and then apply our proposed algorithm for dense bipartite graphs on each of the subgraphs. To further speed up this algorithm, tighter upper bounds, faster heuristics and more effective reductions are proposed, allowing an MBB to be discovered within a few seconds for bipartite graphs with millions of vertices. Extensive experiments are conducted on synthetic and real large bipartite graphs to demonstrate the efficiency and effectiveness of our proposed algorithms and techniques.

Travel time estimation has been recognized as an important research topic that can find broad applications. Existing approaches aim to explore mobility patterns via trajectory embedding for travel time estimation. Though state-of-the-art methods utilize estimated traffic condition (by explicit features such as average traffic speed) for auxiliary supervision of travel time estimation, they fail to model their mutual influence and result in inaccuracy accordingly. To this end, in this article, we propose an improved traffic-aware model, called TAML, which adopts a multi-task learning network to integrate a travel time estimator and a traffic estimator in a shared space and improves the accuracy of estimation by enhanced representation of traffic condition, such that more meaningful implicit features are fully captured. In TAML, multi-task learning is further applied for travel time estimation in multi-granularities (including road segment, sub-path, and entire path). The multiple loss functions are combined by considering the homoscedastic uncertainty of each task. Extensive experiments on two real trajectory datasets demonstrate the effectiveness of our proposed methods.

Destination prediction is known as an important problem for many location based services (LBSs). Existing solutions generally apply probabilistic models or neural network models to predict destinations over a subtrajectory, and adopt the standard attention mechanism to improve the prediction accuracy. However, the standard attention mechanism uses fixed feature representations, and has a limited ability to represent distinct features of locations. Besides, existing methods rarely take the impact of spatial and temporal characteristics of the trajectory into account. Their accuracies in fine-granularity prediction are always not satisfactory due to the data sparsity problem. Thus, in this paper, a carefully designed deep learning model called LATL model is presented. It not only adopts an adaptive attention network to model the distinct features of locations, but also implements time gates and distance gates into the Long Short-Term Memory (LSTM) network to capture the spatial-temporal relation between consecutive locations. Furthermore, to better understand the mobility patterns in different spatial granularities, and explore the fusion of multi-granularity learning capability, a hierarchical model that utilizes tailored combination of different neural networks under multiple spatial granularities is further proposed. Extensive empirical studies verify that the newly proposed models perform effectively and settle the problem nicely.

Geo-social group search aims to find a group of people proximate to a location while socially related. One of the driven applications for geo-social group search is organizing an impromptu activity. This is because the social cohesiveness of a found geo-social group ensures a good communication atmosphere for the activity and the spatial closeness of the geo-social group reduces the preparation time for the activity. Most existing works treat geo-social group search as a problem that finds a group satisfying a single social constraint while optimizing the spatial proximity. However, since different impromptu activities have diverse demands on attendees, e.g. an activity could require (or prefer) the attendees to have skills (or favorites) related to the activity, the existing works cannot find this kind of geo-social groups effectively. In this paper, we propose a novel geo-social group model, equipped with elegant keyword constraints, to fill this gap. We propose a novel search framework which first significantly narrows down the search space with theoretical guarantees and then efficiently finds the optimum result. To evaluate the effectiveness, we conduct experiments on real datasets, demonstrating the superiority of our proposed model. We conduct extensive experiments on large semi-synthetic datasets for justifying the efficiency of the proposed search algorithms.

Recording and querying time-stamped trajectories incurs high cost of data storage and computing. In this paper, we explore characteristics of the trajectories in road networks, which have motivated the idea of coding trajectories by associating timestamps with relative spatial path and locations. Such a representation contains large number of duplicate information to achieve a lower entropy compared with the existing representations, thereby drastically cutting the storage cost. We propose techniques to compress spatial path and locations separately, which can support fast positioning and achieve better compression ratio. For locations, we propose two novel encoding schemes such that the binary code can preserve distance information, which is very helpful for LBS applications. In addition, an unresolved question in this area is whether it is possible to perform search directly on the compressed trajectories, and if the answer is yes, then how. Here we show that directly querying compressed trajectories based on our encoding scheme is possible and can be done efficiently.We design a set of primitive operations for this purpose, and propose index structures to reduce query response time. We demonstrate the advantage of our method and compare it against existing ones through a thorough experimental study on real trajectories in road network.

Community search on attributed networks has recently attracted great deal of research interest. However, most of existing works require query users to specify some community structure parameters. This may not be always practical as sometimes a user does not have the knowledge and experience to decide the suitable parameters. In this paper, we propose a novel parameter-free contextual community model for attributed community search. The proposed model only requires a query context, i.e., a set of keywords describing the desired matching community context, while the community returned is both structure and attribute cohesive w.r.t. the provided query context. We theoretically show that both our exact and approximate contextual community search algorithms can be executed in worst case polynomial time. The exact algorithm is based on an elegant parametric maximum flow technique and the approximation algorithm that significantly improves the search efficiency is analyzed to have an approximation factor of 1/3. In the experiment, we use six real networks with ground-truth communities to evaluate the effectiveness of our contextual community model. Experimental results demonstrate that the proposed model can find near ground-truth communities. We also test both our exact and approximate algorithms using eight large real networks to demonstrate the high efficiency of the proposed algorithms.

Maximal clique enumeration (MCE) is a fundamental problem in graph theory and is used in many applications, such as social network analysis, bioinformatics, intelligent agent systems, cyber security. Most existing MCE algorithms focus on improving the efficiency rather than reducing the size of the output, which could consist of a large number of maximal cliques. In this paper, we study how to report a summary of less overlapping maximal cliques. The problem was studied before, however, after examining the pioneer approach, we consider it still not satisfactory. To advance the research along this line, this paper attempts to make two contributions: (a) We propose a more effective sampling strategy, which produces a much smaller summary but still ensures that the summary can somehow witness all the maximal cliques and the expectation of each maximal clique witnessed by the summary is above a predefined threshold. (b) To verify experimentally, we tested ten real benchmark datasets that have a variety of graph characteristics. The results show that our new sampling strategy consistently outperforms the state-of-the-art method by producing smaller summaries and running faster on all the datasets.

A phrase is a natural, meaningful, and essential semantic unit. In topic modeling, visualizing phrases for individual topics is an effective way to explore and understand unstructured text corpora. However, from phrase quality and topical cohesion perspectives, the outcomes of existing approaches remain to be improved. Usually, the process of topical phrase mining is twofold: phrase mining and topic modeling. For phrase mining, existing approaches often suffer from order sensitive and inappropriate segmentation problems, which make them often extract inferior quality phrases. For topic modeling, traditional topic models do not fully consider the constraints induced by phrases, which may weaken the cohesion. Moreover, existing approaches often suffer from losing domain terminologies since they neglect the impact of domain-level topical distribution. In this paper, we propose an efficient method for high quality and cohesive topical phrase mining. A high quality phrase should satisfy frequency, phraseness, completeness, and appropriateness criteria. In our framework, we integrate quality guaranteed phrase mining method, a novel topic model incorporating the constraint of phrases, and a novel document clustering method into an iterative framework to improve both phrase quality and topical cohesion. We also describe efficient algorithmic designs to execute these methods efficiently. The empirical verification demonstrates that our method outperforms the state-of-the-art methods from the aspects of both interpretability and efficiency.

Destination prediction is known as an important problem for many location based services (LBSs). Existing solutions generally apply probabilistic models to predict destinations over a sub-trajectory, but their accuracies in fine-granularity prediction are always not satisfactory due to the data sparsity problem. This paper presents a carefully designed deep learning model called TALL model for destination prediction. It not only takes advantage of the bidirectional Long Short-Term Memory (LSTM) network for sequence modeling, but also gives more attention to meaningful locations that have strong correlations w.r.t. destination by adopting attention mechanism. Furthermore, a hierarchical model that explores the fusion of multi-granularity learning capability is further proposed to improve the accuracy of prediction. Extensive experiments on Beijing and Chengdu real datasets finally demonstrate that our proposed models outperform existing methods without considering external features.

The problem of influence maximization has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the social users, although location is an important factor in targeted marketing. In this paper, we investigate the problem of influence spanning maximization in location-aware social networks. Our target is to identify the maximum spanning geographical regions in a query region, which is very different from the existing methods that focus on the quantity of the activated users in the query region. Since the problem is NP-hard, we develop one greedy algorithm with a 1-1/e approximation ratio and further improve its efficiency by developing an upper bound based approach. Then, we propose the OIR index by combining ordered influential node lists and an R*-tree and design the index based solution. The efficiency and effectiveness of our proposed solutions and index have been verified using three real datasets.

Discovering expert drivers is highly important for a broad range of location based services, but this issue is largely untouched in previous trajectory mining and search studies. In this paper, we study the problem of trajectory data driven expert driver discovery. It aims to find out top-k expert drivers about a region of interest, based on the understanding of their historical trajectories. To this end, we first investigate the construction of reference system, which collectively describes exemplar routes among important junctions, so that the driving behaviors embedded in each trajectory can be evaluated. To discover expert drivers accurately, a novel tf-idf concept based measure is proposed afterwards, such that the rationality of their trajectories are not only precisely evaluated by the match to reference system, but also properly aggregated for modelling expert drivers. Extensive experimental evaluation using real trajectory datasets demonstrates the effectiveness and efficiency of our proposed solutions.

String similarity join, as an essential operation in applications including data integration and data cleaning, has attracted significant attention in the research community. Previous studies focus on global similarity join. In this paper, we study local similarity join with edit distance constraints, which finds string pairs from two string collections that have similar substrings. We study two kinds of local similarity join problems: checking local similar pairs and locating local similar pairs. We first consider the case where if two strings are locally similar to each other, they must share a common gram of a certain length. We show how to do efficient local similarity verification based on a matching gram pair. We propose two pruning techniques and an incremental method to further improve the efficiency of finding matching gram pairs. Then we devise a method to locate the longest similar substring pair for two local similar strings. We conducted a comprehensive experimental study to evaluate the efficiency of these techniques.

The problem of k-truss search has been well defined and investigated to find the highly correlated user groups in social networks. But there is no previous study to consider the constraint of users' spatial information in k-truss search, denoted as co-located community search in this paper. The co-located community can serve many real applications. To search the maximum co-located communities efficiently, we first develop an efficient exact algorithm with several pruning techniques. After that, we further develop an approximation algorithm with adjustable accuracy guarantees and explore more effective pruning rules, which can reduce the computational cost significantly. To accelerate the real-time efficiency, we also devise a novel quadtree based index to support the efficient retrieval of users in a region and optimise the search regions with regards to the given query region. Finally, we verify the performance of our proposed algorithms and index using five real datasets.

The urban road networks undergo frequent traffic congestions during the peak hours and around the city center. Capturing the spatiotemporal evolution of the congestion scenario in real-time in an urban-scale can aid in developing smart traffic management systems, and guiding commuters in making informed decision about route choice. The congestion scenario is often represented by a set of distinguishable network partitions that have a homogeneous level of congestion inside them but are heterogeneous to others. Due to the dynamic nature of traffic, these partitions evolve with time in terms of their structure and location. In this paper, we propose a comprehensive framework to capture the evolution by incrementally updating the partitions in an efficient manner using a two-layer approach. The physical layer maintains a set of small-sized road network building blocks in a fine granularity, and performs low-level computations to incrementally update them, whereas the logical layer performs high-level computations in order to serve as an interface to query the physical layer about the congested partitions in a coarse granularity. We also propose an in-memory index calledBinthat compactly stores the historical sets of building blocks in the main memory with no information loss, and facilitates their efficient retrieval. Our experimental results show that the proposed method is much efficient than the existing re-partitioning methods without significant sacrifice in accuracy. The proposedBinconsumes a minimum space with least redundancy at different time stamps.

Real social networks contain many communities, where members within each community are densely connected with each other, while they are sparsely connected with the members outside of the community. Since each member can join multiple communities simultaneously, communities in social networks are usually overlapping with each other. How to efficiently and effectively identify overlapping communities in a large social network becomes a fundamental problem in the big data era. Most existing studies on community finding focused on non-overlapping communities based on several well-known community fitness metrics. However, recent investigations have shown that these fitness metrics may suffer free rider and separation effects where the overlapping region of two communities always belongs to the denser one, rather to both of them. In this paper, we study the overlapping community detection problem in social networks that not only takes the quality of the found overlapping communities but also incorporate both free rider and separation effects on the found communities into consideration. Specifically, in this paper, we first propose a novel community fitness metric - triangle based fitness metric, for overlapping community detection that can minimize the free rider and separation effects on found overlapping communities, and show that the problem is NP-hard. We then propose an efficient yet scalable algorithm for the problem that can deliver a feasible solution. We finally validate the effectiveness of the proposed fitness metric and evaluate the performance of the proposed algorithm, through conducting extensive experiments on real-world datasets with over 100 million vertices and edges. Experimental results demonstrate that the proposed algorithm is very promising.

Recording and querying time-stamped trajectories incurs high cost of data storage and computing. In this paper, we explore several characteristics of the trajectories in road networks, which have motivated the idea of coding trajectories by associating timestamps with relative spatial path and locations. Such a representation contains a large number of duplicate information to achieve a lower entropy compared with the existing representations, thereby drastically cutting the storage cost. We propose several techniques to compress spatial path and locations separately, which can support fast positioning and achieve better compression ratio. For locations, we propose two novel encoding schemes such that the binary code can preserve distance information, which is very helpful for LBS applications. In addition, an unresolved question in this area is whether it is possible to perform a search directly on the compressed trajectories, and if the answer is yes, then how. Here, we show that directly querying compressed trajectories based on our encoding scheme is possible and can be done efficiently. We design a set of primitive operations for this purpose, and propose index structures to reduce query response time. We demonstrate the advantage of our method and compare it against existing ones through a thorough experimental study on real trajectories in road network.

Finding communities in networks has become very important because various social and physical complex systems are represented as networks. Because of their ability to address large networks, local community detection methods that start from a seed node have become the focus of many research endeavours in recent times. In this paper, a derivative-based local community detection method, inspired by active contours, is proposed for finding a community surrounding an initial seed. The method is based on the concepts of curvature and gradient of the current communitys boundary. Curvature and gradient comprise the velocity function used to determine whether the boundary should move to include a candidate node in its vicinity. Unlike Euclidean space, networks have non-uniform space with fluctuations of dimensionality, given by the fluctuation in degrees of nodes, which complicates the calculation of derivatives used to define the curvature and gradient of boundary nodes. In this research, with some intuitive imagination, a framework for approximating derivatives in network space is proposed. Benchmarking this community detection method against three contemporary methods shows that it is capable of building communities with equal or better conductance.

Conventional spatial keyword queries confront the difficulty of returning desired objects that are synonyms but morphologically different to query keywords. To overcome this flaw, this paper investigates the interactive spatial keyword querying with semantics. It aims to enhance the conventional queries by not only making sense of the query keywords, but also refining the understanding of query semantics through interactions. On top of the probabilistic topic model, a novel interactive strategy is proposed to precisely infer the latent query semantics by learning from user feedbacks. In each interaction, the returned objects are carefully selected to ensure effective inference of user intended query semantics. Query processing is carried out on a small candidate object set at each round of interaction, and the whole querying process terminates when the latent query semantics learned from user feedback becomes explicit enough. The experimental results on real check-in dataset demonstrates that the quality of results has been significantly improved through limited number of interactions.

Social networks have become a vital mechanism to disseminate information to friends and colleagues. But the dynamic nature of information and user connectivity within these networks raised many new and challenging research problems. One of them is the query-related topic search in social networks. In this work, we investigate the important problem of the personalized influential topic search. There are two challenging questions that need to be answered: how to extract the social summarization of the social network so as to measure the topics' influence at the similar granularity scale? and how to apply the social summarization to the problem of personalized influential topic search. Based on the evaluation using real-world datasets, our proposed algorithms are proved to efficient and effective.

Understanding the influence of a product is crucially important for making informed business decisions. This paper introduces a new type of skyline queries, called uncertain reverse skyline, for measuring the influence of a probabilistic product in uncertain data settings. More specifically, given a dataset of probabilistic products P and a set of customers C, an uncertain reverse skyline of a probabilistic product q retrieves all customers c ∈ C which include q as one of their preferred products. We present efficient pruning ideas and techniques for processing the uncertain reverse skyline query of a probabilistic product using R-Tree data index. We also present an efficient parallel approach to compute the uncertain reverse skyline and influence score of a probabilistic product. Our approach significantly outperforms the baseline approach derived from the existing literature. The efficiency of our approach is demonstrated by conducting experiments with both real and synthetic datasets.

Nowadays, users of social networks like tweets and weibo have generated massive geo-tagged records, and these records reveal their activities in the physical world together with spatio-temporal dynamics. Existing trajectory data management studies mainly focus on analyzing the spatio-temporal properties of trajectories, while leaving the understanding of their activities largely untouched. In this paper, we incorporate the semantic analysis of the activity information embedded in trajectories into query modelling and processing, with the aim of providing end users more accurate and meaningful trip recommendations. To this end, we propose a novel trajectory query that not only considers the spatio-temporal closeness but also, more importantly, leverages probabilistic topic modelling to capture the semantic relevance of the activities between data and query. To support efficient query processing, we design a novel hybrid index structure, namely ST-tree, to organize the trajectory points hierarchically, which enables us to prune the search space in spatial and topic dimensions simultaneously. The experimental results on real datasets demonstrate the efficiency and scalability of the proposed index structure and search algorithms.

Influence maximization is a recent but well-studied problem which helps identify a small set of users that are most likely to “influence” the maximum number of users in a social network. The problem has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the users, but location is an important factor in targeted marketing. In this paper, we propose and investigate the problem of influence maximization in location-aware social networks, or, more generally,Geo-social Influence Spanning Maximization. Given a query$q$composed of a region$R$, a regional acceptance rate$\rho$, and an integer$k$as a seed selection budget, our aim is to find the maximum geographic spanning regions (MGSR). We refer to this as the MGSR problem. Our approach differs from previous work as we focus more on identifying the maximum spanning geographical regions within a region$R$, rather than just the number of activated users in the given network like the traditional influence maximization problem[14]. Our research approach can be effectively used for online marketing campaigns that depend on the physical location of social users. To address the MGSR problem, we first prove NP-Hardness. Next, we present a greedy algorithm with a$1-1/e$approximation ratio to solve the problem, and further improve the efficiency by developing an upper bounded pruning approach. Then, we propose the OIR*-Tree index, which is a hybrid index combining ordered influential node lists with an R*-tree. We show that our index based approach is significantly more efficient than the greedy algorithm and the upper bounded pruning algorithm, especially when$k$is large. Finally, we evaluate the performance for all of the proposed approaches using three real datasets.

String similarity join, as an essential operation in applications including data integration and data cleaning, has attracted significant attention in the research community. Previous studies focus on global similarity join. In this paper, we study local similarity join with edit distance constraints, which finds string pairs from two string collections that have similar substrings. We study two kinds of local similarity join problems: checking local similar pairs and locating local similar pairs. We first consider the case where if two strings are locally similar to each other, they must share a common gram of a certain length. We show how to do efficient local similarity verification based on a matching gram pair. We propose two pruning techniques and an incremental method to further improve the efficiency of finding matching gram pairs. Then, we devise a method to locate the longest similar substring pair for two local similar strings. We conducted a comprehensive experimental study to evaluate the efficiency of these techniques.

Recent studies show that individuals in a social network can be divided into different groups of densely connected communities, and these individuals who bridge different communities, referred to as structural hole spanners, have great potential to acquire resources/information from communities and thus benefit from the access. Structural hole spanners are crucial in many real applications such as community detections, diffusion controls, viral marketing, etc. In spite of their importance, little attention has been paid to them. Particularly, how to accurately characterize the structural hole spanners and how to devise efficient yet scalable algorithms to find them in a large social network are fundamental issues. In this paper, we study the top-k structural hole spanner problem. We first provide a novel model to measure the quality of structural hole spanners through exploiting the structural hole spanner properties. Due to its NP-hardness, we then devise two efficient yet scalable algorithms, by developing innovative filtering techniques that can filter out unlikely solutions as quickly as possible, while the proposed techniques are built up on fast estimations of the upper and lower bounds on the cost of an optimal solution and make use of articulation points in real social networks. We finally conduct extensive experiments to validate the effectiveness of the proposed model, and to evaluate the performance of the proposed algorithms using real world datasets. The experimental results demonstrate that the proposed model can capture the characteristics of structural hole spanners accurately, and the structural hole spanners found by the proposed algorithms are much better than those by existing algorithms in all considered social networks, while the running times of the proposed algorithms are very fast.

Skyline queries play an important role in multi-criteria decision making applications of many areas. Given a dataset of objects, a skyline query retrieves data objects that are not dominated by any other data object in the dataset. Unlike standard skyline queries where the different aspects of data objects are compared directly, dynamic and reverse skyline queries adhere to the around-by semantics, which is realized by comparing the relative distances of the data objects w.r.t. a given query. Though, there are a number of works on parallelizing the standard skyline queries, only a few works are devoted to the parallel computation of dynamic and reverse skyline queries. This paper presents an efficient quad-tree based data indexing scheme, called Q+Tree, for parallelizing the computations of the dynamic and reverse skyline queries. We compare the performance of Q+Tree with an existing quad-tree based indexing scheme. We also present several optimization heuristics to improve the performance of both of the indexing schemes further. Experimentation with both real and synthetic datasets verifies the efficiency of the proposed indexing scheme and optimization heuristics.

The congestion scenario on a road network is often represented by a set of differently congested partitions having homogeneous level of congestion inside. Due to the changing traffic, these partitions evolve with time. In this paper, we propose a two-layer method to incrementally update the differently congested partitions from those at the previous time point in an efficient manner, and thus track their evolution. The physical layer performs low-level computations to incrementally update a set of small-sized road network building blocks, and the logical layer provides an interface to query the physical layer about the congested partitions. At each time point, the unstable road segments are identified and moved to their most suitable building blocks. Our experimental results on different datasets show that the proposed method is much efficient than the existing re-partitioning methods without significant sacrifice in accuracy.

Recently, answering keyword queries on graph data has drawn a great deal of attention from database communities. However, most graph keyword search solutions proposed so far primarily focus on a single query setting. We observe that for a popular keyword query system, the number of keyword queries received could be substantially large even in a short time interval, and the chance that these queries share common keywords is quite high. Therefore, answering keyword queries in batches would significantly enhance the performance of the system. Motivated by this, this paper studies efficient batch processing for multiple keyword queries on graph data. Realized that finding both the optimal query plan for multiple queries and the optimal query plan for a single keyword query on graph data are computationally hard, we first propose two heuristic approaches which target maximizing keyword overlap and give preferences for processing keywords with short sizes. Then we devise a cardinality based cost estimation model that takes both graph data statistics and search semantics into account. Based on the model, we design an A* based algorithm to find the global optimal execution plan for multiple queries. We evaluate the proposed model and algorithms on two real datasets and the experimental results demonstrate their efficacy.

Graph data management and matching similar graphs are very important for many applications including bioinformatics, computer vision, VLSI design, bug localization, road networks, social and communication networking. Many graph indexing and similarity matching techniques have already been proposed for managing and querying graph data. In similar graph matching, a user is returned with the database graphs whose distances with the query graph are below a threshold. In such query settings, a user may not receive certain database graphs that are very similar to the query graph if the initial query graph is inappropriate/imperfect for the expected answer set. To exemplify this, consider a drug designer who is looking for chemical compounds that could be the target of her hypothetical drug before realizing it. In response to her query, the traditional search system may return the structures from the database that are most similar to the query graph. However, she may get surprised if some of the expected targets are missing in the answer set. She may then seek assistance from the system by asking “Is there other query graph that can match my expected answer set?”. The system may then modify her initial query graph to include the missing answers in the new answer set. Here, we study this kind of problem of answering why-not questions in similar graph matching for graph databases.

Social networks are a vital mechanism to disseminate information to friends and colleagues. In this work, we investigate an important problem—thepersonalized influential topic search, or PIT-Search in a social network: Given a keyword query$q$issued by a user$u$in a social network, a PIT-Search is to find the top-$k$$q$-related topics that are most influential for the query user$u$. The influence of a topic to a query user depends on the social connection between the query user and the social users containing the topic in the social network. To measure the topics’ influence at the similar granularity scale, we need to extract the social summarization of the social network regarding topics. To make effective topic-aware social summarization, we propose two random-walk based approaches: random clustering and an L-length random walk. Based on the proposed approaches, we can find a small set of representative users with assigned influential scores to simulate the influence of the large number of topic users in the social network with regards to the topic. The selected representative users are denoted as the social summarization of topic-aware influence spread over the social network. And then, we verify the usefulness of the social summarization by applying it to the problem of personalized influential topic search. Finally, we evaluate the performance of our algorithms using real-world datasets, and show the approach is efficient and effective in practice.

With the rapidly growing population in urban areas, these days the urban road networks are expanding at a faster rate. The frequent movement of people on them leads to traffic congestions. These congestions originate from some crowded road segments, and diffuse towards other parts of the urban road networks creating further congestions. This behavior of road networks motivates the need to understand the influence of individual road segments on others in terms of congestion. In this work, we propose RoadRank, an algorithm to compute the influence scores of each road segment in an urban road network, and rank them based on their overall influence. It is an incremental algorithm that keeps on updating the influence scores with time, by feeding with the latest traffic data at each time point. The method starts with constructing a directed graph called influence graph, which is then used to iteratively compute the influence scores using probabilistic diffusion theory. We show promising preliminary experimental results on real SCATS traffic data of Melbourne.

Recent studies have shown that in social networks, users who bridge different communities, known as structural hole spanners, have great potentials to acquire available resources from these communities and gain access to multiple sources of information flow. Structural hole spanners are crucial in many applications such as community detections, diffusion controls, and viral marketing. In spite of their importance, not much attention has been paid to them. Particularly, how to characterize the structural hole spanner properties and how to devise efficient yet scalable algorithms to find them are fundamental issues. In this paper, we formulate the problem as the top-k structural hole spanner problem. Specifically, we first provide a generic model to measure the quality of structural hole spanners, by exploring their properties, and show that the problem is NP-hard. We then devise efficient and scalable algorithms, by exploiting the bounded inverse closeness centralities of vertices and making use of articulation points of the network. We finally evaluate the performance of the proposed algorithms through extensive experiments on real and synthetic datasets, and validate the effectiveness of the proposed model. Our experimental results demonstrate that the proposed model can capture the characteristics of structural hole spanners accurately, and the proposed algorithms are very promising.

Answeringwhy-notquestions in databases is promised to have wide application prospect in many areas and thereby, has attracted recent attention in the database research community. This paper addresses the problem of answering these so-calledwhy-notquestions in similar graph matching for graph databases. Given a set of answer graphs of an initial query graph$q$and a set of missing (why-not) graphs, we aim to modify$q$into a new query graph$q^*$such that the missing graphs are included in the new answer set of$q^*$. We present an approximate solution to address the above as the optimal solution is NP-hard to compute. In our approach, we first compute the bounded search space and the distance to be minimized for$q^*$. Then, we present a two-phase algorithm to find the new query$q^*$. In the first phase, we generate a set of candidate edges to be added/deleted into/from the initial query$q$within the bounded search space and in the second phase, we select a subset of candidate edges generated in the first phase to minimize the distance for$q^*$. We also demonstrate the effectiveness and efficiency of our approach by conducting extensive experiments on two real datasets.

While keyword query empowers ordinary users to search vast amount of data, the ambiguity of keyword query makes it difficult to effectively answer keyword queries, especially for short and vague keyword queries. To address this challenging problem, in this paper we propose an approach that automatically diversifies XML keyword search based on its different contexts in the XML data. Given a short and vague keyword query and XML data to be searched, we first derive keyword search candidates of the query by a simple feature selection model. And then, we design an effective XML keyword search diversification model to measure the quality of each candidate. After that, two efficient algorithms are proposed to incrementally compute top-k qualified query candidates as the diversified search intentions. Two selection criteria are targeted: the k selected query candidates are most relevant to the given query while they have to cover maximal number of distinct results. At last, a comprehensive evaluation on real and synthetic data sets demonstrates the effectiveness of our proposed diversification model and the efficiency of our algorithms.

The rapid global migration of people towards urban areas is multiplying the traffic volume on urban road networks. As a result these networks are rapidly growing in size, in which different sub-networks exhibit distinctive traffic flow patterns. In this paper, we propose a scalable framework for traffic congestion-based spatial partitioning of large urban road networks. It aims to identify different sub-networks or partitions that exhibit homogeneous traffic congestion patterns internally, but heterogenous to others externally. To this end, we develop a two-stage procedure within our framework that first transforms the large road graph into a well-structured and condensed supergraph via clustering and link aggregation based on traffic density and adjacency connectivity, respectively. We then devise a spectral theory based novel graph cut (referred as 훼-Cut) to partition the supergraph and compare its performance with that of an ex-isting method for partitioning urban networks. Our results show that the proposed method outperforms the normalized cut based existing method in all the performance evaluation metrics for small road networks and provides good results for much larger networks where other methods may face serious problems of time and space complexities.

Recent years have witnessed an unprecedented proliferation of social media, e.g., millions of blog posts, micro-blog posts, and social networks on the Internet. This kind of social media data can be modeled in a large graph where nodes represent the entities and edges represent relationships between entities of the social media. Discovering keyword-based correlated networks of these large graphs is an important primitive in data analysis, from which users can pay more attention about their concerned information in the large graph. In this paper, we propose and define the problem of keyword-based correlated network computation over a massive graph. To do this, we first present a novel tree data structure that only maintains the shortest path of any two graph nodes, by which the massive graph can be equivalently transformed into a tree data structure for addressing our proposed problem. After that, we design efficient algorithms to build the transformed tree data structure from a graph offline and compute the γ-bounded keyword matched subgraphs based on the pre-built tree data structure on the fly. To further improve the efficiency, we propose weighted shingle-based approximation approaches to measure the correlation among a large number of γ-bounded keyword matched subgraphs. At last, we develop a merge-sort based approach to efficiently generate the correlated networks. Our extensive experiments demonstrate the efficiency of our algorithms on reducing time and space cost. The experimental results also justify the effectiveness of our method in discovering correlated networks from three real datasets.

The probabilistic threshold query is one of the most common queries in uncertain databases, where a result satisfying the query must be also with probability meeting the threshold requirement. In this paper, we investigate probabilistic threshold keyword queries (PrTKQ)over XML data, which is not studied before. We first introduce the notion of quasi-SLCA and use it to represent results for a PrTKQ with the consideration of possible world semantics. Then we design a probabilistic inverted (PI)index that can be used to quickly return the qualified answers and filter out the unqualified ones based on our proposed lower/upper bounds. After that, we propose two efficient and comparable algorithms: Baseline Algorithm and PI index-based Algorithm. To accelerate the performance of algorithms, we also utilize probability density function. An empirical study using real and synthetic data sets has verified the effectiveness and the efficiency of our approaches.

This paper aims at answering the so called why-not questions in reverse skyline queries. A reverse skyline query retrieves all data points whose dynamic skylines contain the query point. We outline the benefit and the semantics of answering why-not questions in reverse skyline queries. In connection with this, we show how to modify the why-not point and the query point to include the why-not point in the reverse skyline of the query point. We then show, how a query point can be positioned safely anywhere within a region (i.e., called safe region) without losing any of the existing reverse skyline points. We also show how to answer why-not questions considering the safe region of the query point. Our approach efficiently combines both query point and data point modification techniques to produce meaningful answers. Experimental results also demonstrate that our approach can produce high quality explanations for why-not questions in reverse skyline queries.

Efficiently computing k-edge connected components in a large graph, G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimization algorithms. Consider existing techniques for computing k-edge connected components are quite time consuming and are unlikely to be scalable for large scale graphs, in this paper we firstly propose a novel graph decomposition paradigm to iteratively decompose a graph G for computing its k-edge connected components such that the number of drilling-down iterations h is bounded by the "depth" of the k-edge connected components nested together to form G, where h usually is a small integer in practice. Secondly, we devise a novel, efficient threshold-based graph decomposition algorithm, with time complexity O(l × |E|), to decompose a graph G at each iteration, where l usually is a small integer with l « |V|. As a result, our algorithm for computing k-edge connected components significantly improves the time complexity of an existing state-of-the-art technique from O(|V|2|E| + |V|3 log |V|) to O(h × l × |E|). Finally, we conduct extensive performance studies on large real and synthetic graphs. The performance studies demonstrate that our techniques significantly outperform the state-of-the-art solution by several orders of magnitude.

In this paper, we study how to find maximal k-edge-connected subgraphs from a large graph. k-edge-connected subgraphs can be used to capture closely related vertices, and finding such vertex clusters is interesting in many applications, e. g., social network analysis, bioinformatics, web link research. Compared with other explicit structures for modeling vertex clusters, such as quasi-clique, k-core, which only set the requirement on vertex degrees, k-edge-connected subgraph further requires high connectivity within a subgraph (a stronger requirement), and hence defines a more closely related vertex cluster.

Functional and inclusion dependency discovery is important to knowledge discovery, database semantics analysis, database design, and data quality assessment. Motivated by the importance of dependency discovery, this paper reviews the methods for functional dependency, conditional functional dependency, approximate functional dependency, and inclusion dependency discovery in relational databases and a method for discovering XML functional dependencies.

A fundamental problem related to RDF query processing is selectivity estimation, which is crucial to query optimization for determining a join order of RDF triple patterns. In this paper we focus research on selectivity estimation for SPARQL graph patterns. The previous work takes the join uniformity assumption when estimating the joined triple patterns. This assumption would lead to highly inaccurate estimations in the cases where properties in SPARQL graph patterns are correlated. We take into account the dependencies among properties in SPARQL graph patterns and propose a more accurate estimation model. Since star and chain query patterns are common in SPARQL graph patterns, we first focus on these two basic patterns and propose to use Bayesian network and chain histogram respectively for estimating the selectivity of them. Then, for estimating the selectivity of an arbitrary SPARQL graph pattern, we design algorithms for maximally using the precomputed statistics of the star paths and chain paths. The experiments show that our method outperforms existing approaches in accuracy.

Despite the proliferation of work on XML keyword query, it remains open to support keyword query over probabilistic XML data. Compared with traditional keyword search, it is far more expensive to answer a keyword query over probabilistic XML data due to the consideration of possible world semantics. In this paper, we firstly define the new problem of studying top-k keyword search over probabilistic XML data, which is to retrieve k SLCA results with the k highest probabilities of existence. And then we propose two efficient algorithms. The first algorithm PrStack can find k SLCA results with the k highest probabilities by scanning the relevant keyword nodes only once. To further improve the efficiency, we propose a second algorithm EagerTopK based on a set of pruning properties which can quickly prune unsatisfied SLCA candidates. Finally, we implement the two algorithms and compare their performance with analysis of extensive experimental results.

An important facility to aid keyword search on XML data is suggesting alternative queries when user queries contain typographical errors. Query suggestion thus can improve users' search experience by avoiding returning empty result or results of poor qualities. In this paper, we study the problem of effectively and efficiently providing quality query suggestions for keyword queries on an XML document. We illustrate certain biases in previous work and propose a principled and general framework, XClean, based on the state-of-the-art language model. Compared with previous methods, XClean can accommodate different error models and XML keyword query semantics without losing rigor. Algorithms have been developed that compute the top-k suggestions efficiently. We performed an extensive experiment study using two large-scale real datasets. The experiment results demonstrate the effectiveness and efficiency of the proposed methods.

Although keyword query enables inexperienced users to easily search XML database with no specific knowledge of complex structured query languages or XML data schemas, the ambiguity of keyword query may result in generating a great number of results that may be classified into different types. For users, each result type implies a possible search intention. To improve the performance of keyword query, it is desirable to efficiently work out the most relevant result type from the data to be retrieved.

Keyword search is integrated in many applications on account of the convenience to convey users' query intention. Recently, answering keyword queries on XML data has drawn the attention of web and database communities, because the success of this research will relieve users from learning complex XML query languages, such as XPath/XQuery, and/or knowing the underlying schema of the queried XML data. As a result, information in XML data can be discovered much easier.

This paper focuses on selectivity estimation for SPARQL graph patterns, which is crucial to RDF query optimization. The previous work takes the join uniformity assumption, which would lead to high inaccurate estimation in the cases where properties in SPARQL graph patterns are correlated. We take into account the dependencies among properties in SPARQL graph patterns and propose a more accurate estimation model. We first focus on two common SPARQL graph patterns (star and chain patterns) and propose to use Bayesian network and chain histogram for estimating the selectivityof them. Then, for an arbitrary composite SPARQL graph pattern, we maximally combines the results of the star and chain patterns we have precomputed. The experiments show that our method outperforms existing approaches in accuracy.

Tree patterns represent important fragments of XPath. In this paper, we show that some classes of tree patterns exhibit such a property that, given a finite number of tree patterns P1, ..., Pn, there exists another pattern P (tree pattern or DAG-pattern) such that P1, ..., Pn, are all contained in P, and for any tree pattern Q belonging to a given class C, P1, ..., Pn, are contained in Q implies P is contained in Q.

In this article, we address the problem of how to extend the definition of functional dependencies (FDs) in incomplete relations to XML documents (called XFDs) using the well-known strong satisfaction approach.We propose a syntactic definition of strong XFD satisfaction in an XML document and then justify it by showing that, similar to the case in relational databases, for the case of simple paths, keys in XML are a special case of XFDs. We also propose a normal form for XML documents based on our definition of XFDs and provide a formal justification for it by proving that it is a necessary and sufficient condition for the elimination of redundancy in an XML document.

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

Spatial data, ranging from various land information data to different types of environmental data, are typically collected and used by different custodians. The full benefits of using spatial data can be achieved by combining the data from different sources covering a common region. Due to organizational, political and technical reasons, it is unrealistic to physically integrate the vast amount of spatial data managed by different systems in different organizations. A practical approach is to provide interoperability to support multi-site data queries. In this paper, we study the performance aspect of complex spatial query processing. We propose a framework for processing queries with multiple spatial and aspatial predicates using data from multiple sites. Using a new concept called generalized filter, a query is processed in three steps. First, an aspatial filter that incorporates some conditions derived from spatial predicates is used to find a set of candidates, which is a superset of the final query results. Then, the candidates are manipulated and a refinement step is executed following an optimized candidate sequence. Finally, a post-processing step is used to handle spatial expressions in query results. The focus of this paper is to generate enhanced filters in order to minimize the need of transferring and processing complex spatial data.

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