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.

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

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.

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.

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.

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.

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.

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.

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.