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.

Cross-modal retrieval is a fundamental task in multimedia understanding, aimed at querying samples with similar semantics in one modality (e.g., text) using another modality (e.g., image). Existing methods merely focus on point-to-point comparisons between individual samples, while overlooking the widely present many-to-many structural relationships in real-world scenarios. However, the many-to-many relationships formed by multiple samples sharing similar semantics are crucial for effectively achieving semantic alignment and accurately constructing shared semantic representations. To address this, we propose a novel hypergraph-based cross-modal retrieval approach, which explicitly establishes many-to-many associations between multiple samples using a label-driven hypergraph construction mechanism, combined with differentiated hyperedge weighting. Additionally, to avoid the limitation of information interaction direction imposed by traditional unidirectional cross-attention mechanisms, we design a bidirectional cross-attention structure, with image and text as separate query sources, to achieve symmetric semantic enhancement between modalities. The resulting joint image-text representations are then mapped as hypergraph vertices, further enhancing the model's ability to align cross-modal semantics. Since constructing a global hypergraph on a large-scale sample set would incur high computational cost, we introduce global label co-occurrence frequency to supervise the batch-level hypergraph construction, enhancing the local graph's ability to capture global semantics. Experimental results show that our model outperforms existing state-of-the-art methods on three benchmark cross-modal retrieval datasets.

Cross-modal hashing has gained widespread attention in cross-modal retrieval due to its low storage cost and significant computational efficiency. Existing cross-modal hashing methods primarily focus on learning modality invariance by mapping data from different modalities into a shared space and learn unified hash codes. Nevertheless, due to the inherent heterogeneity between different modalities, the common subspace may still exhibit modality discrepancies. This ultimately makes it challenging to achieve semantic alignment, thereby affecting the accuracy of cross-modal retrieval. To address this issue, we propose an Unsupervised Adversarial Contrastive Hashing (UACH) method for cross-modal retrieval. Specifically, we design a cycle generative adversarial network to learn the transformation relationships between different modality feature domains, effectively promoting semantic alignment across modalities. Additionally, we employ dual contrastive learning to simultaneously measure the representation learning and hashing learning components of each specific modality, and learn unified hash codes for each specific modality, thus mitigating the impact of modality discrepancies. Extensive experiments conducted on three cross-modal benchmark datasets demonstrate that our model outperforms the state-of-the-art baselines.

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.

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.

Multimodal Named Entity Recognition (MNER) aims to achieve more accurate entity recognition by incorporating image information to assist text, which is particularly significant on social media platforms. Current research disproportionately emphasizes enhancing text with images, overlooking that the core of the NER task remains textual. The modal differences between images and text inevitably introduces noise when incorporating image information. Therefore, when textual information is sufficient to independently complete the NER task, the introduction of image information is unnecessary. This paper proposes an Adaptive Logical Decision Framework (ALDF) capable of determining the sufficiency of textual information in NER tasks, deciding whether to introduce image information, avoiding unnecessary noise, and focusing more on information-scarce entities when introducing image information. Specifically, we designed a Logic Reasoning Neural Network (LRNN) that uses an evidence-theory-based method to simulate human decision-making logic and generate decision support degrees for deciding whether image information should participate in the recognition task. When incorporating image information, we utilize the generated decision support degrees to guide the multi-head self-attention mechanism, enhancing the model's focus on information-scarce entities. Additionally, we employ a modality-aware progressive training method that can use decision information in real-time during multimodal training and reduce information redundancy between modalities. Extensive experiments demonstrate that our model achieves state-of-the-art performance on popular public 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.

The k-plex model, which allows each vertex to miss connections with up to$k$neighbors, serves as a relaxation of the clique model. Its adaptability makes it more suitable for analyzing graphs from real-world applications, where noise and imperfect data are common and the stringent clique model is often impractical. The challenge of identifying maximum k-plex (MKP, an NP-hard problem) is gaining attention in fields such as social network analysis, community detection, terrorist network identification, and graph clustering. Recent research efforts have focused on optimizing the time complexity of MKP algorithms. The state-of-the-art has reduced the complexity from a trivial$O^{*}(2^{n})$to$O^{*}(c_{k}^{n})$, with$c_{k} > 1.94$for$k$> 3, where$n$denotes the number of vertices. In this paper, we demonstrate that MKP can be solved in$O^{*}(1.42^{n})$and propose the first two quantum algorithms, qTKP and qMKP, to achieve this complexity. qTKP employs quantum search integrated with graph encoding, degree count, degree comparison, and size determination to find a k-plex of a given size; qMKP uses a binary search to progressively identify the maximum solution. To validate the practical performance and effectiveness of our algorithms, proof-of-principle experiments were conducted using the latest IBM quantum simulator currently available. This work holds potential to be applied to a wide range of clique relaxations, e.g., n-clan and n-club.

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

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.

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.

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.

Health knowledge graph provides an ideal technical means to integrate heterogeneous data resources and enhance knowledge-based services. There are many challenges for the construction of health knowledge graph such as complex concepts and relationships, various medical standards, heterogeneous data structures, poor data quality, highly accurate and interpretable services, etc. In this paper, firstly, we propose Health Knowledge Graph Builder (HKGB), an end-to-end platform which could be used to construct disease-specific and extensible health knowledge graphs from multiple sources. Secondly, we analyze the capabilities and requirements of clinicians, design the tasks to involve the clinicians and implement a clinician-in-the-loop toolset to integrate the clinicians prior knowledge into the construction of health knowledge graphs. Thirdly, we design an extensible mechanism to add new diseases to an existing knowledge graph. Fourthly, we present a quantitative effort estimation algorithm to quantitatively evaluate the effort of clinicians during the construction, and use it to calculate the workloads such as 44.27 person days for knee osteoarthritis domain. Finally, we have developed several knowledge graph based tools to facilitate real applications.

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.

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.

Extracting web content is to obtain the required data embedded in web pages, usually including structured records, such as product information, and text content, such as news. Web pages use a large number of HTML tags to organize and to present various information. Both knowing little about the structures of web pages and mixing kinds of information in web pages are making the extraction process very challenging to guarantee extraction performance and extraction adaptability. This study proposes a unified web content extraction framework that can be applied in various web environments to extract both structured records and text content. First, we construct a characteristic container to hold kinds of characteristics related with extraction objectives, including visual text information, content semantics(instead of HTML tag semantics), web page structures, etc. Second, the above characteristics are integrated into an extraction framework for extraction decisions on different web sites. Especially, we put forward different strategies, path aggregation for extracting text content and HMM model for structured records, to locate the extraction area by exploiting both those extraction characteristics. Comparative experiments on multiple web sites with popular extraction methods, including CETR, CETD and CNBE, show that our proposed extraction method can provide better extraction precision and extraction adaptability.

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.

Determining appropriate statistical distributions for modeling text corpora is important for accurate estimation of numerical characteristics. Based on the validity of the test on a claim that the data conforms to Poisson distribution we propose Poisson decomposition model (PDM), a statistical model for modeling count data of text corpora, which can straightly capture each document's multidimensional numerical characteristics on topics. In PDM, each topic is represented as a parameter vector with multidimensional Poisson distribution, which can be easily normalized to multinomial term probabilities and each document is represented as measurements on topics and thereby reduced to a measurement vector on topics. We use gradient descent methods and sampling algorithm for parameter estimation. We carry out extensive experiments on the topics produced by our models. The results demonstrate our approach can extract more coherent topics and is competitive in document clustering by using the PDM-based features, compared to PLSI and LDA.

Anomaly or outlier detection is a major challenge in big data analytics because anomaly patterns provide valuable insights for decision-making in a wide range of applications. Recently proposed anomaly detection methods based on the tree isolation mechanism are very fast due to their logarithmic time complexity, making them capable of handling big data sets efficiently. However, the underlying similarity or distance measures in these methods have not been well understood. Contrary to the claims that these methods never rely on any distance measure, we find that they have close relationships with certain distance measures. This implies that the current use of this fast isolation mechanism is only limited to these distance measures and fails to generalise to other commonlyused measures. In this paper, we propose a generic framework named LSHiForest for fast tree isolation based ensemble anomaly analysis with the use of a Locality-Sensitive Hashing (LSH) forest. Being generic, the proposed framework can be instantiated with a diverse range of LSH families, and the fast isolation mechanism can be extended to any distance measures, data types and data spaces where an LSH family is defined. In particular, the instances of our framework with kernelised LSH families or learning based hashing schemes can detect complicated anomalies like local or surrounded anomalies. We also formally show that the existing tree isolation based detection methods are special cases of our framework with the corresponding distance measures. Extensive experiments on both synthetic and real-world benchmark data sets show that the framework can achieve both high time efficiency and anomaly detection quality.

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.

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.

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.

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.

Technological advances have enabled the deployment of large-scale sensor networks for environmental monitoring and surveillance purposes. The large volume of data generated by sensors needs to be processed to respond to the users queries. However, efficient processing of queries in sensor networks poses great challenges due to the unique characteristics imposed on sensor networks including slow processing capability, limited storage, and energy-limited batteries, etc. Among various queries, top-k query is one of the fundamental operators in many applications of wireless sensor networks for phenomenon monitoring. In this paper we focus on evaluating top-k queries in an energy-efficient manner such that the network lifetime is maximized. To achieve that, we devise a scalable, filter-based localized evaluation algorithm for top-k query evaluation, which is able to filter out as many unlikely top-k results as possible within the network from transmission. We also conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm on real datasets. The experimental results show that the proposed algorithm outperforms existing algorithms significantly in network lifetime prolongation.

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.