Owing to their unprecedented comprehension capabilities, large language models (LLMs) have become indispensable components of modern web search engines. From a technical perspective, this integration represents retrieval-augmented generation (RAG), which enhances LLMs by grounding them in external knowledge base. A prevalent technical approach in this context is graph-based RAG (G-RAG). However, current G-RAG methodologies frequently underutilize graph topology, predominantly focusing on low-order structures or pre-computed static communities. This limitation affects their effectiveness in addressing dynamic and complex queries. Thus, we propose DA-RAG, which leverages attributed community search (ACS) to dynamically extract relevant subgraphs based on the queried question. DA-RAG captures high-order graph structures, allowing for the retrieval of self-complementary knowledge. Furthermore, DA-RAG is equipped with a chunk-layer oriented graph index, which facilitates efficient multi-granularity retrieval while significantly reducing both computational and economic costs. We evaluate DA-RAG on multiple datasets, demonstrating that it outperforms existing RAG methods by up to 40% in head-to-head comparisons across four metrics while reducing index construction time and token overhead by up to 37% and 41%, respectively.

An area of research on communities in signed networks aims to find structures in which each user in the graph is connected to other members in their community by more positive edges than negative edges, indicating a positive experience for the user. However, some of these communities are ‘echo chambers', a rising area of concern in modern discourse regarding social media, which contain almost exclusively positive edges indicating all users trust each other with little or no push-back. Here exists an interesting contradiction, when finding a ‘positive’ community often times the resulting structure may be the negative ‘echo chamber’. In this work we propose a signed graph community substructure named the$(\epsilon,\ \phi)$-Clique which is the best of both worlds, where each user is happy to be in their community (indicated by have a proportion of positive edges$\geq\epsilon$for each node) as well as there existing a level of disagreement in the system (indicated by the community having a proportion of negative edges$\geq \phi$). From this definition, we design algorithms to exactly find the Maximum$(\epsilon,\ \phi)$-Clique containing a query user, utilising heuristics to combat the NP-Hard and NP-Hard to approximate nature of the problem. We perform experiments to examine the improvements in efficiency of our algorithms to the proposed baseline as well as examine example community outputs to show the effectiveness of our structure.

Despite the development of various distributed graph systems, little attention has been paid to the granularity of computation and communication, which can significantly impact overall efficiency. Moreover, users often struggle to write and optimize new parallel algorithms to fit different programming abstractions, which can be a daunting task. To address these challenges, this paper introduces Argan, a parallel graph system that offers efficient adaptive-grained executions and a user-friendly abstraction. Argan utilizes the adaptive-Grained Asynchronous Parallel (GAP) model, which enables runtime adjustments of granularity to enhance performance. Additionally, its programming model allows users to directly derive parallel programs from existing batch sequential algorithms. Our experiments using real-life and synthetic graphs demonstrate that for a variety of graph applications, GAP effectively improves the performance of Argan, which outperforms Grap +, PowerSwitch, and Maiter.

Sparse operators, i.e., operators that take sparse tensors as input, are of great importance in deep learning models. Due to the diverse sparsity patterns in different sparse tensors, it is challenging to optimize sparse operators by seeking an optimal sparse format, i.e., leading to the lowest operator latency. Existing works propose to decompose a sparse tensor into several parts and search for a hybrid of sparse formats to handle diverse sparse patterns. However, they often make a trade-off between search space and search time: their search spaces are limited in some cases, resulting in limited operator running efficiency they can achieve. In this paper, we try to extend the search space in its breadth (by doing flexible sparse tensor transformations) and depth (by enabling multi-level decomposition). We formally define the multi-level sparse format decomposition problem, which is NP-hard, and we propose a framework STile for it. To search efficiently, a greedy algorithm is used, which is guided by a cost model about the latency of computing a sub-task of the original operator after decomposing the sparse tensor. Experiments of two common kinds of sparse operators, SpMM and SDDMM, are conducted on various sparsity patterns, and we achieve 2.1-18.0× speedup against cuSPARSE on SpMMs and 1.5 - 6.9× speedup against DGL on SDDMM. The search time is less than one hour for any tested sparse operator, which can be amortized.

Data quality is critical across many applications. The utility of data is undermined by various errors, making rigorous data cleaning a necessity. Traditional data cleaning systems depend heavily on predefined rules and constraints, which necessitate significant domain knowledge and manual effort. Moreover, while configuration-free approaches and deep learning methods have been explored, they struggle with complex error patterns, lacking interpretability, requiring extensive feature engineering or labeled data. This paper introduces GIDCL ( G raph-enhanced I nterpretable D ata C leaning with L arge language models), a pioneering framework that harnesses the capabilities of Large Language Models (LLMs) alongside Graph Neural Network (GNN) to address the challenges of traditional and machine learning-based data cleaning methods. By converting relational tables into graph structures, GIDCL utilizes GNN to effectively capture and leverage structural correlations among data, enhancing the model's ability to understand and rectify complex dependencies and errors. The framework's creator-critic workflow innovatively employs LLMs to automatically generate interpretable data cleaning rules and tailor feature engineering with minimal labeled data. This process includes the iterative refinement of error detection and correction models through few-shot learning, significantly reducing the need for extensive manual configuration. GIDCL not only improves the precision and efficiency of data cleaning but also enhances its interpretability, making it accessible and practical for non-expert users. Our extensive experiments demonstrate that GIDCL significantly outperforms existing methods, improving F1-scores by 10% on average while requiring only 20 labeled tuples.

Graph neural networks (GNNs) have been gaining a reputation for effective modeling of graph data. Yet, it is challenging to train GNNs efficiently. Many frameworks have been proposed but most of them suffer from high batch preparation cost and data transfer cost for mini-batch training. In addition, existing works have limitations on the device utilization pattern, which results in fewer opportunities for pipeline parallelism. In this paper, we present DAHA, a GNN training framework with data and hardware aware execution planning to accelerate end-to-end GNN training. We first propose a data and hardware aware cost model that is lightweight and gives accurate estimates on per-operation time cost for arbitrary input and hardware settings. Based on the cost model, we further explore the optimal execution plan for the data and hardware with three optimization strategies with pipeline parallelism: (1) group-based in-turn pipelining of batch preparation neural training to explore more optimization opportunities and prevent batch preparation bottlenecks; (2) data and hardware aware rewriting for intra-batch execution planning to improve computation efficiency and create more opportunities for pipeline parallelism; and (3) inter-batch scheduling to further boost the training efficiency. Extensive experiments demonstrate that DAHA can consistently and significantly accelerate end-to-end GNN training and generalize to different message-passing GNN models.

Many real-world binary relations can be modelled as bipartite graphs, which can be inherently temporal and each edge is associated with a timestamp. The ( α, β )-core, a popular structure that requires minimum degrees over two layers of vertices, is useful for understanding the organisation of bipartite networks. However, the temporal property has rarely been considered in cohesive subgraph mining in bipartite graphs. This gap prevents the finding of time-sensitive ( α, β )-cores in real-world applications. In this paper, we aim at finding ( α, β )-cores within any time window over a temporal bipartite graph. To address this problem, we propose a novel DAG (Directed Acyclic Graph)-like hierarchy with qualified time windows to describe the temporal containment property of the ( α, β )-core. Furthermore, we construct the superior-optimized index which significantly optimizes space complexity and guarantees efficient query performance. We also propose a maintenance approach that can efficiently update the index by removing stale information and incorporating newly inserted temporal edges. Extensive experiments are conducted on eight real-world graphs and the results show the effectiveness and efficiency of our indexes.

Signed bipartite graphs represent relationships between two sets of entities, including both positive and negative interactions, allowing for a more comprehensive modeling of real-world networks. In this work, we focus on the detection of cohesive subgraphs in signed bipartite graphs by leveraging the concept of balanced butterflies. A balanced butterfly is a cycle of length 4 that is considered stable if it contains an even number of negative edges. We propose a novel model called the balanced ( k , ϵ)-bitruss, which provides a concise representation of cohesive signed bipartite subgraphs while enabling control over density ( k ) and balance (ϵ). We prove that finding the largest balanced ( k , ϵ)-bitruss is NP-hard and cannot be efficiently approximated to a significant extent. Furthermore, we extend the unsigned butterfly counting framework to efficiently compute both balanced and unbalanced butterflies. Based on this technique, we develop two greedy heuristic algorithms: one that prioritizes followers and another that focuses on balanced support ratios. Experimental results demonstrate that the greedy approach based on balanced support ratios outperforms the follower-based approach in terms of both efficiency and effectiveness.

Community search (CS) aims at personalized subgraph discovery which is the key to understanding the organisation of many real-world networks. CS in undirected networks has attracted significant attention from researchers, including many solutions for various cohesive subgraph structures and for different levels of dynamism with edge insertions and deletions, while they are much less considered for directed graphs. In this paper, we propose incremental solutions of CS based on the D-truss in dynamic directed graphs, where the D-truss is a cohesive subgraph structure defined based on two types of triangles in directed graphs. We first analyze the theoretical boundedness of D-truss given edge insertions and deletions, then we present basic single-update algorithms. To improve the efficiency, we propose an order-based D-Index, associated batch-update algorithms and a fully-dynamic query algorithm. Our extensive experiments on real-world graphs show that our proposed solution achieves a significant speedup compared to the SOTA solution, the scalability over updates is also verified.

Differential privacy (DP) has become the de facto standard of privacy protection. For graphs, there are two widely used definitions of differential privacy, namely, edge differential privacy (edge-DP) and node differential privacy (node-DP), and node-DP is preferred when the minimal unit of interest is a node. To preserve node-DP, one can develop different methods to answer each specific graph query, or develop a graph publishing method to answer all graph queries. However, no existing works worked on such graph publishing methods. In this work, we propose two methods for publishing graphs under node-DP. One is the node-level perturbation algorithm which modifies the input graph by randomly inserting and removing nodes. The other one is the edge-level perturbation algorithm which randomly removing edges and inserting nodes. Both methods can achieve a flexible privacy guarantee by adjusting the running parameters. We conduct extensive experiments on both real-world and synthetic graphs to show the effectiveness and efficiency of proposed algorithms.

Abstract Uncertain butterflies are one of, if not the, most important graphlet structures on uncertain bipartite networks. In this paper, we examine the uncertain butterfly structure (in which the existential probability of the graphlet is greater than or equal to a threshold parameter), as well as the global Uncertain Butterfly Counting Problem (to count the total number of these instances over an entire network). To solve this task, we propose a non-trivial exact baseline ( UBFC ), as well as an improved algorithm ( IUBFC ) which we show to be faster both theoretically and practically. We also design two sampling frameworks ( UBS and PES ) which can sample either a vertex, edge or wedge from the network uniformly and estimate the global count quickly. Furthermore, a notable butterfly-based community structure which has been examined in the past is the k -bitruss. We adapt this community structure onto the uncertain bipartite graph setting and introduce the Uncertain Bitruss Decomposition Problem (which can be used to directly answer any k -bitruss search query for any k ). We then propose an exact algorithm ( UBitD ) to solve our problem with three variations in deriving the initial uncertain support. Using a range of networks with different edge existential probability distributions, we validate the efficiency and effectiveness of our solutions.

Graph Neural Networks (GNNs) have attracted much research interest due to their successful applications on graph-structured data. Despite the effectiveness, due to the data dependency, GNNs are confronted with the neighborhood explosion and over-smoothing problems. Many sampling-based and level-down methods have been proposed to solve the neighborhood explosion problem to boost efficiency. However, they suffer from either poor accuracy or considerable runtime overheads. Moreover, the over-smoothing problem prevents GNNs from exploring more distant neighborhoods effectively. In this paper, we present a Community-and-Contraction-based Graph Neural Network (CC-GNN), which leverages community and contraction to boost the time and space efficiency of GNNs. Specifically, CC-GNN first performs contraction and retrieves the communities as super nodes, and connects them using a tailored similarity function to obtain an informative community contracted graph (CC-Graph). CC-GNN then learns the representations of the super nodes in the CC-Graph, which are used to reconstruct the representations of the original nodes. Finally, CC-GNN explores more distant neighborhoods without additional convolution layers, implicitly alleviating the over-smoothing problem. Since CC-GNN conducts the costly training on a much smaller contracted graph, the efficiency is boosted significantly. Most importantly, we have proved that the information loss of node representations caused by the CC-Graph is bounded. Extensive experimental studies verify the efficiency boost and the effectiveness.

Mining cohesive subgraphs on bipartite graphs is an important task. The k -bitruss is one of many popular cohesive subgraph models, which is the maximal subgraph where each edge is contained in at least k butterflies. The bitruss decomposition problem is to find all k -bitrusses for k ≥ 0. Dealing with large graphs is often beyond the capability of a single machine due to its limited memory and computational power, leading to a need for efficiently processing large graphs in a distributed environment. However, all current solutions are for a single machine and a centralized environment, where processors can access the graph or auxiliary indexes randomly and globally. It is difficult to directly deploy such algorithms on a shared-nothing model. In this paper, we propose distributed algorithms for bitruss decomposition. We first propose SC-HBD as the baseline, which uses H -function to define bitruss numbers and computes them iteratively to a fix point in parallel. We then introduce a subgraph-centric peeling method SC-PBD, which peels edges in batches over different butterfly complete subgraphs. We then introduce local indexes on each fragment, study the butterfly-aware edge partition problem including its hardness, and propose an effective partitioner. Finally we present the bitruss butterfly-complete subgraph concept, and divide and conquer DC-BD method with optimization strategies. Extensive experiments show the proposed methods solve graphs with 30 trillion butterflies in 2.5 hours, while existing parallel methods under shared-memory model fail to scale to such large graphs.

Heterogeneous information networks (HINs) are usually used to model information systems with multi-type objects and relations. In contrast, graphs that have a single type of nodes and edges, are often called homogeneous graphs. Measuring similarities among objects is an important task in data mining applications, such as web search, link prediction, and clustering. Currently, several similarity measures are defined for HINs. Most of these measures are based on meta-paths, which show sequences of node classes and edge types along the paths between two nodes. However, meta-paths, which are often designed by domain experts, are hard to enumerate and choose w.r.t. the quality of similarity scores. This makes using existing similarity measures in real applications difficult. To address this problem, we extend SimRank, a well-known similarity measure on homogeneous graphs, to HINs, by introducing the concept of the decay graph. The newly proposed similarity measure is called HowSim, which has the property of being meta-path free, and capturing the structural and semantic similarity simultaneously. The generality and effectiveness of HowSim, and the efficiency of our proposed algorithms for computing HowSim scores, are demonstrated by extensive experiments.

Recently, deep neural networks (DNNs) have achieved great success in various applications, where low inference latency is important. Existing solutions either manually tune the kernel library or utilize search-based compilation to reduce the operator latency. However, manual tuning requires significant engineering effort, and the huge search space makes the search cost of the search-based compilation unaffordable in some situations. In this work, we propose ETO, a framework for speeding up DNN operator optimization based on reusing the information of performant tensor programs. Specifically, ETO defines conditions for the information reuse between two operators. For operators satisfying the conditions, based on the performant tensor program information of one operator, ETO uses a reuse-based tuner to significantly prune the search space of the other one, and keeps optimization effectiveness at the same time. In this way, for a set of operators, ETO first determines the information reuse relationships among them to reduce the total search time needed, and then tunes the operators either by the backend compiler or by the reuse-based tuner accordingly. ETO further increases the reuse opportunities among the operators by injecting extra operators as bridges between two operators which do not satisfy the reuse conditions. Compared with various existing methods, the experiments show that ETO is effective and efficient in optimizing DNN operators.

When considering uncertain bipartite networks, the number of instances of the popular graphlet structure the butterfly may be used as an important metric to quickly gauge information about the network. This Uncertain Butterfly Count has practical usages in a variety of areas such as biomedical/biological fields, E-Commerce and road networks. In this paper we formally define the uncertain butterfly structure (in which the existential probability of the butterfly is greater than or equal to some user-defined threshold t ) as well as the Uncertain Butterfly Counting Problem (to determine the number of unique instances of this structure on any uncertain bipartite network). We then examine exact solutions by proposing a non-trivial baseline (UBFC) as well as an improved solution (IUBFC) which reduces the time complexity and employs heuristics to further reduce the runtime in practice. In addition to exact solutions, we propose two approximate solutions via sampling, UBS and PES , which can be used to quickly estimate the Uncertain Butterfly Count, a powerful tool when the exact count is unnecessary. Using a range of networks with different edge existential probability distributions, we validate the efficiency and effectiveness of our solutions.

Measuring similarity among data objects is important in data analysis and mining. SimRank is a popular link-based similarity measurement among nodes in a graph. To compute the all-pairs SimRank matrix accurately, iterative methods are usually used. For static graphs, current iterative solutions are not efficient enough, both in time and space, due to the unnecessary cost and storage by the nature of iterative updating. For dynamic graphs, all current incremental solutions for updating the SimRank matrix are based on an approximated SimRank definition, and thus have no accuracy guarantee. In this paper, we propose a novel local push based algorithm for computing and tracking all-pairs SimRank. Furthermore, we develop an iterative parallel two-step framework for local push to take advantage of modern hardwares with multicore CPUs. We show that our algorithms outperform the state-of-the-art methods.

Measuring similarities among different nodes is important in graph analysis tasks, such as link prediction, and recommendation. Among different similarity measures, SimRank is one of the most popular and promising ones, and has received a lot of research attention. While most current studies focus on single-pair, single-source/top-k, and all-pairs SimRank computation, few of them have studied finding similar pairs given a set of node pairs, which has attractive applications in personalized search and recommendation tasks. In this paper, we present Carmo, an efficient algorithm for retrieving the top-k similarities from an arbitrary set of pairs. In addition, we introduce two types of indexes to boost the efficiency of Carmo: one is hub-based, the other is tree-based. We show the effectiveness and efficiency of our proposed methods by extensive experiments.

Learning network embeddings has attracted growing attention in recent years. However, most of the existing methods focus on homogeneous networks, which cannot capture the important type information in heterogeneous networks. To address this problem, in this paper, we propose TransN, a novel multi-view network embedding framework for heterogeneous networks. Compared with the existing methods, TransN is an unsupervised framework which does not require node labels or user-specified meta-paths as inputs. In addition, TransN is capable of handling more general types of heterogeneous networks than the previous works. Specifically, in our framework TransN, we propose a novel algorithm to capture the proximity information inside each single view. Moreover, to transfer the learned information across views, we propose an algorithm to translate the node embeddings between different views based on the dual-learning mechanism, which can both capture the complex relations between node embeddings in different views, and preserve the proximity information inside each view during the translation. We conduct extensive experiments on real-world heterogeneous networks, whose results demonstrate that the node embeddings generated by TransN outperform those of competitors in various network mining tasks.

Heterogeneous information networks (HINs) are usually used to model information systems with multi-type objects and relations. Measuring the similarity among objects is an important task in data mining applications. Currently, several similarity measures are defined for HIN. Most of these measures are based on meta-paths, which show sequences of node classes and edge types along the paths between two nodes. However, meta-paths, which are often designed by domain experts, are hard to enumerate and choose w.r.t. the quality of the similarity scores. This makes the existing similarity measures difficult to use in real applications. To address this problem, we extend SimRank, a well-known similarity measure for homogeneous graphs, to HINs, by introducing the concept of decay graph. The newly proposed relevance measure is called HowSim, which has the property of being meta-path free, and capturing the structural and semantic similarity simultaneously. The generality and effectiveness of HowSim, are demonstrated by extensive experiments.

Recent years witnessed the emergence of various applications on knowledge graphs, which are often represented as RDF graphs. However, due to the lack of data schema and the complexity of SPARQL language, there is usually a gap between the user's real desire and the actual meaning of a SPARQL query, especially when the query itself is complicated. In this paper, we try to narrow this gap by modifying a given query with a set of modifiers, so that its result approaches a user-provided example set. Specifically, we model this problem as two individual sub-problems, query-restricting, and query-relaxing, both of which are shown to be NP-hard. We further prove that unless P=NP, query-restricting has no polynomial-time approximation scheme (PTAS), and query-relaxing has no polynomial-time constant-factor approximation algorithm. Despite their hardness, we propose a (1-1/ε)-approximation method for query-restricting and 2 heuristics for query-relaxing. Extensive experiments have been conducted on real-world knowledge graphs to evaluate the effectiveness and efficiency of our proposed solutions.

Measuring similarities among different nodes is important in graph analysis. SimRank is one of the most popular similarity measures. Given a graph G ( V , E ) and a source node u , a single-source Sim-Rank query returns the similarities between u and each node v ∈ V. This type of query is often used in link prediction, personalized recommendation and spam detection. While dealing with a large graph is beyond the ability of a single machine due to its limited memory and computational power, it is necessary to process single-source SimRank queries in a distributed environment, where the graph is partitioned and distributed across multiple machines. However, most current solutions are based on shared-memory model, where the whole graph is loaded into a shared memory and all processors can access the graph randomly. It is difficult to deploy such algorithms on shared-nothing model. In this paper, we present DISK, a distributed framework for processing single-source SimRank queries. DISK follows the linearized formulation of SimRank, and consists of offline and online phases. In the offline phase, a tree-based method is used to estimate the diagonal correction matrix of SimRank accurately, and in the online phase, single-source similarities are computed iteratively. Under this framework, we propose different optimization techniques to boost the indexing and queries. DISK guarantees both accuracy and parallel scalability, which distinguishes itself from existing solutions. Its accuracy, efficiency, parallel scalability and scalability are also verified by extensive experimental studies. The experiments show that DISK scales up to graphs of billions of nodes and edges, and answers online queries within seconds, while ensuring the accuracy bounds.

Truss decomposition is to divide a graph into a hierarchy of subgraphs, or trusses. A subgraph is a k -truss ( k ≥ 2) if each edge is in at least k --- 2 triangles in the subgraph. Existing algorithms work by first counting the number of triangles each edge is in and then iteratively incrementing k to peel off the edges that will not appear in ( k + 1)-truss. Due to the data and computation intensity, truss decomposition on billion-edge graphs takes hours to complete on a commodity computer. We propose to accelerate in-memory truss decomposition by (1) compacting intermediate results to optimize memory access, (2) dynamically adjusting the computation based on data characteristics, and (3) parallelizing the algorithm on both the multicore CPU and the GPU. In particular, we optimize the triangle enumeration with data skew handling, and determine at runtime whether to pursue peeling or direct triangle counting to obtain a certain k -truss. We further develop a CPU-GPU co-processing strategy in which the CPU first computes intermediate results and sends the compacted results to the GPU for further computation. Our experiments on real-world datasets show that our implementations outperform the state of the art by up to an order of magnitude. Our source code is publicly available at https://github.com/RapidsAtHKUST/AccTrussDecomposition.

Community search in heterogeneous information networks (HINs) has attracted much attention in graph analysis. Given a vertex, the goal is to find a densely-connected sub-graph that contains the vertex. In practice, the user may need to restrict the number of connections between vertices, but none of the existing methods can handle such queries. In this paper, we propose the relational constraint that allows the user to specify fine-grained connection requirements between vertices. Base on this, we define the relational community as well as the problems of detecting and searching relational communities, respectively. For the detection problem, we propose an efficient solution that has near-linear time complexity. For the searching problem, although it is shown to be NP-hard and even hard-to-approximate, we devise two efficient approximate solutions. We further design the round index to accelerate the searching algorithm and show that it can handle dynamic graphs by its nature. Extensive experiments on both synthetic and real-world graphs are conducted to evaluate both the effectiveness and efficiency of our proposed methods.

In this paper, we propose an efficient hierarchical index, G*-tree, to optimize spatial queries on road networks. Most existing graph indexes can only support one kind of query, and thus we need to build multiple indexes on a road network to handle various kinds of spatial queries, which is inefficient and unscalable for real-world applications. To address the problem, a recent study proposes G-tree to support multiple types of spatial queries on road networks within one framework. However, the assembly-based method on G-tree is not efficient enough to handle spatial queries when vertices, which are close in a road network, are distant in G-tree. To address the inefficiency problem of G-tree, in this paper, we propose a novel index structure on road networks, namely G*-tree, whose key idea is to build shortcuts between selected leaf nodes. Based on G*-tree, we propose three shortcut-based algorithms to answer distance queries, k-nearest neighbor queries and range queries, respectively, which are more efficient than the existing assembly-based algorithms on G-tree. Moreover, we propose a shortcut selection algorithm to optimize the performance of spatial queries on G*-tree. We conduct extensive experiments to compare our G*-tree and the state-of-the-art indexing methods on various large-scale road networks, where the results demonstrate that our G*-tree has better efficiency and scalability than the competitors to handle spatial queries.

SimRank is a popular link-based similarity measurement among nodes in a graph. To compute the all-pairs SimRank matrix accurately, iterative methods are usually used. For static graphs, current iterative solutions are not efficient enough, both in time and space, due to unnecessary cost and storage by the nature of iterative updating. For dynamic graphs, all current incremental solutions for updating the Sim-Rank matrix are based on an approximated SimRank definition, and thus have no accuracy guarantee. In this paper, we propose a novel local push based algorithm for computing all-pairs SimRank. We show that our algorithms outperform the state-of-the-art static and dynamic all-pairs SimRank algorithms.

Community search problem, which is to find good communities given a set of query nodes in a graph, has attracted increasing research interest recently. Though various measurement models have been proposed to define and solve community search problem. Few of them could define a community concisely and have good quality of query results. They either involve additional constraints for modeling communities, such as size and diameter, or suffer from the free rider effect, i.e., include irrelevant subgraphs. In this paper, we propose a new k-plex based community model for community search. We show that our model not only is simple and clear, but also meets with basic requirements of defining a community search problem. We formulate the maximum k-plex community query (MCKPQ) problem, that is, given a set of query nodes Q , searching for optimal k-plex containing Q . We prove that MCKPQ is NP-hard, and it is hard to approximate in any constant factor. We first give exact solutions. Then, we propose an efficient branch-and-bound (B&B) method and design an effective upper bound function and a pruning strategy. Furthermore, we optimize the basic B&B by fast candidate generation. We also give a fast heuristic solution, which produces high-quality results in practice. The effectiveness of our model of community and the efficiency of our methods are verified by elaborate experiments.

In the initial publication, first name and family name of the second author Xun Jian were switched around. The original article has been corrected.