Given a directed graph G, the directed densest subgraph (DDS) problem refers to finding a subgraph from G, whose density is the highest among all subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fake follower detection and community mining. However, existing DDS solutions often provide weaker theoretical guarantees. To tackle these issues, we present a theoretically efficient (1+ε) approximate DDS discovery algorithm in this paper. Specifically, we first introduce a novel LP formulation for the DDS problem and then propose an efficient approximation algorithm based on the accelerated random coordinate descent method (ACDM) to solve it efficiently. We theoretically prove that our algorithm requires fewer iterations to achieve the same solution accuracy compared to state-of-the-art approximation DDS algorithms. We have performed an extensive empirical evaluation of our approaches on 15 real large datasets. The results show that our proposed algorithms are up to 1000× faster than the current state-of-the-art.

Node importance estimation, a classical problem in network analysis, underpins various web applications. Previous methods either exploit intrinsic topological characteristics, e.g., graph centrality, or leverage additional information, e.g., data heterogeneity, for node feature enhancement. However, these methods follow the supervised learning setting, overlooking the fact that ground-truth node-importance data are usually partially labeled in practice. In this work, we propose the first semi-supervised node importance estimation framework, i.e., EASING, to improve learning quality for unlabeled data in heterogeneous graphs. Different from previous approaches, EASING explicitly captures uncertainty to reflect the confidence of model predictions. To jointly estimate the importance values and uncertainties, EASING incorporates DJE, a deep encoder-decoder neural architecture. DJE introduces distribution modeling for graph nodes, where the distribution representations derive both importance and uncertainty estimates. Additionally, DJE facilitates effective pseudo-label generation for the unlabeled data to enrich the training samples. Based on labeled and pseudo-labeled data, EASING develops effective semi-supervised heteroscedastic learning with the varying node uncertainty regularization. Extensive experiments on three real-world datasets highlight the superior performance of EASING compared to competing methods. Codes are available via https://github.com/yankai-chen/EASING.

In many real-world applications (e.g., email networks, social networks, and phone call networks), the relationships between entities can be modeled as a temporal graph, in which each edge is associated with a timestamp representing the interaction time. As a fundamental task in temporal graph analysis, triangle counting has received much attention, and several triangle models have been developed, including δ-temporal triangle, sliding-window triangle, and (δ 1,3 , δ 1,2 , δ 2,3 )-temporal triangle. In particular, the δ-temporal triangle, requiring the gap of timestamps of any two edges within it to be bounded by a threshold δ, has been demonstrated effective in many real applications, such as cohesiveness analysis, transitivity, clustering coefficient, and graph classification. In this paper, we study fast algorithms for counting δ-temporal triangles in a given query time window. We first propose an online algorithm, which enumerates all edges in the graph and for each edge, calculates how many δ-temporal triangles end with the edge. We further develop an efficient index-based solution, which maps δ-temporal triangles into points of the 2-dimensional space and further compactly organizes these points using hierarchical structures. Besides, we study the problem of binary δ-temporal triangle counting by considering the existence of δ-temporal triangle among three vertices. Experiments on large temporal graphs show that our online algorithm is up to 70× faster than the state-of-the-art algorithm, and our index-based algorithm is up to 10 8 × faster than the online algorithm.

As a building block of many graph-based areas, the s-t path enumeration problem aims to find all paths between s and t by satisfying a given constraint, e.g., hop numbers. In many real-world scenarios, graphs are multi-attribute, where vertices and edges are associated with numerical attributes, such as expense or distance in road networks. However, existing methods have not fully leveraged all attributes in s-t path analysis. Hence, in this paper, we study the problem of skyline path enumeration, which aims to identify paths that balance multiple attributes, ensuring that no skyline result is dominated by another, thus meeting diverse user needs. To efficiently tackle this problem, we design a task-oriented core attribute index, called CAI, to rule out all redundant vertices and edges not located in any skyline path. Additionally, we introduce a hop-dependency label propagation strategy to construct the CAI index in parallel, improving the indexing process. Based on this index, we further design a CAI-based querying strategy that reduces fruitless explorations between candidate vertices not in the same skyline path, significantly optimizing query processing time. Experimental evaluations on fifteen real-world graphs show that CAI outperforms existing methods by up to four orders of magnitude in speed while demonstrating enhanced scalability and well-bound memory costs.

Given a directed graph G , the directed densest subgraph (DDS) problem refers to finding a subgraph from G , whose density is the highest among all subgraphs of G . The DDS problem is fundamental to a wide range of applications, such as fake follower detection and community mining. However, existing DDS solutions often incur significant redundant computations and have weaker theoretical guarantees. To tackle these issues, we present both practically and theoretically efficient DDS discovery algorithms (including both approximation and exact methods) in this paper. Specifically, we first introduce a novel graph reduction technique that locates the DDS into a highly smaller subgraph, with non-trivial theoretical guarantees. We further develop an efficient approximation algorithm by employing gradient projection and theoretically prove that it requires fewer iterations to achieve the same solution accuracy compared to state-of-the-art approximation DDS algorithms. Finally, we propose an efficient exact algorithm based on this novel approximation algorithm. We have performed an extensive empirical evaluation of our approaches on 15 real and 8 synthetic large datasets. The results show that our proposed algorithms are up to two orders of magnitude faster than the state-of-the-art.

Bipartite graphs are ubiquitous in many domains, e.g., e-commerce platforms, social networks, and academia, by modeling interactions between distinct entity sets. Within these graphs, the butterfly motif, a complete 2×2 biclique, represents the simplest yet significant subgraph structure, crucial for analyzing complex network patterns. Counting the butterflies offers significant benefits across various applications, including community analysis and recommender systems. Additionally, the temporal dimension of bipartite graphs, where edges activate within specific time frames, introduces the concept of historical butterfly counting, i.e., counting butterflies within a given time interval. This temporal analysis sheds light on the dynamics and evolution of network interactions, offering new insights into their mechanisms. Despite its importance, no existing algorithm can efficiently solve the historical butterfly counting task. To address this, we design two novel indices whose memory footprints are dependent on #butterflies and #wedges, respectively. Combining these indices, we propose a graph structure-aware indexing approach that significantly reduces memory usage while preserving exceptional query speed. To further reduce the index size and boost the query efficiency, we design an index compression strategy, enabling the fast, high-quality, and unbiased approximation of historical butterfly counts. We theoretically prove that our approach is particularly advantageous on power-law graphs, a common characteristic of real-world bipartite graphs, by surpassing traditional complexity barriers for general graphs. Extensive experiments reveal that our query algorithms outperform existing methods by up to five magnitudes, effectively balancing speed with manageable memory requirements.

Cardinality estimation is a fundamental functionality in database systems. Most existing cardinality estimators focus on handling predicates over numeric or categorical data. They have largely omitted an important data type, set-valued data, which frequently occur in contemporary applications such as information retrieval and recommender systems. The few existing estimators for such data either favor high-frequency elements or rely on a partial independence assumption , which limits their practical applicability. We propose ACE, an Attention-based Cardinality Estimator for estimating the cardinality of queries over set-valued data. We first design a distillation-based data encoder to condense the dataset into a compact matrix. We then design an attention-based query analyzer to capture correlations among query elements. To handle variable-sized queries, a pooling module is introduced, followed by a regression model (MLP) to generate final cardinality estimates. We evaluate ACE on three datasets with varying query element distributions, demonstrating that ACE outperforms the state-of-the-art competitors in terms of both accuracy and efficiency.

Heterogeneous information networks (HINs) are prevalent in various domains, including bibliographic information networks, social media, and knowledge graphs. As a fundamental topic in HIN mining, community mining has found various real applications, such as recommendation, biological data analysis, and event organization. Most existing works often rely on meta-paths, relational constraints, spectral partitioning, label propagation, and network representation to define the communities. However, almost all these works do not explicitly consider the structural similarity between vertices, which plays a vital role in modeling communities and also ignore the specific roles of vertices. In this paper, we propose a novel community model, called structurally similar community (SSC) , which models the HIN communities by explicitly considering the structural similarity between vertices. In particular, SSC can not only support various structural similarity measures, but also identify different roles of the vertices in the community, such as cores, non-cores, hubs, and outliers. Based on the SSC, we develop fast online and index-based algorithms that support both efficient searching and detecting SSCs in large HINs, where the former one searches an SSC containing a specific query vertex while the latter one detects all the SSCs from the HIN. Extensive experiments on real-world datasets demonstrate the effectiveness of SSC model in revealing meaningful communities and the high efficiency of our proposed algorithms.

2-hop labeling has been widely utilized to accelerate the efficiency of online shortest distance queries. Given the nature of frequent changes in real-world graphs, the efficient maintenance of 2-hop labeling index has been extensively studied recently. However, existing methods cannot efficiently process large-scale graphs due to their high time and memory costs, and most of them process large batches of updates sequentially, significantly decreasing efficiency. In this paper, we propose a novel algorithm for maintaining the 2-hop labeling index in a parallel manner, called M2HL , which can efficiently handle both edge insertions and deletions. Moreover, we theoretically prove that M2HL maintains both correctness and minimality for the updated 2-hop labeling index. Our experiments on ten large-scale graphs demonstrate that M2HL outperforms the state-of-the-art 2-hop labeling maintenance methods by up to four orders of magnitude in speed while maintaining correctness and minimality, as well as exhibiting strong scalability and low memory usage.

Densest subgraph discovery (DSD) is a fundamental topic in graph mining. It has been studied for decades, and is widely used in various areas, including network science, biological analysis, and graph databases. As a typical problem of DSD, the k -clique densest subgraph (CDS) problem aims to detect a subgraph from a graph, such that the number of k -cliques over the number of its vertices is maximized. While the CDS problem has received plenty of attention in the literature, existing CDS algorithms that perform best in practice often have weaker theoretical guarantees, while those with the stronger theoretical assurances tend to perform worse in practice. Besides, all the existing CDS algorithms struggle with graphs with high degeneracy values, a characteristic commonly found in real-world graphs. To bridge the huge gap between practice and theory, in this paper, we first introduce a novel graph reduction technique, which locates the CDS into a very small subgraph, with non-trivial theoretical guarantees. We further propose a new efficient approximation algorithm by employing the state-of-the-art k -clique counting algorithm, which shares all the advantages of existing algorithms, achieving both strong practical efficiency and theoretical guarantees. Extensive experiments on 12 real-world large graphs demonstrate the high efficiency of our CDS algorithm. Particularly, our algorithm is up to four orders of magnitude faster than the state-of-the-art algorithm while maintaining the same accuracy guarantees and requiring much less memory.

Job-market mobility prediction plays a crucial role in optimizing human capital usage for both employees and employers. Most conventional methods primarily focus on learning sequential career sequences while ignoring the sufficient information extraction of mutual entity correlations in the job market. In this work, we push forward to exploit the heterogeneous relational knowledge among the job market structures by proposing a model namely Attentive Heterogeneous Knowledge Learning and Synergy (AHKLS). Equipped with the subsequent module of time-aware perception, AHKLS achieves effective career trajectory encoding for job-market mobility prediction. To evaluate the AHKLS performance, we conduct extensive experiments on three real-world datasets with different sizes. The empirical analyses demonstrate not only the performance superiority of AHKLS over several competing methods, but also the module effectiveness and model compatibility with other methods in enhancing the mobility prediction tasks accordingly.

Core decomposition is a critical metric for evaluating the vertex importance and analyzing graph structure. Given a graph$G$, a k-core is the largest subgraph of$G$where each vertex has at least$k$neighbors. Most existing works mainly focus on homogeneous graphs in which edges are of the same type and cannot be applied to heterogeneous information networks (HINs) directly. However, most real-world networks are HINs which consist of different vertex types and edge types. To reveal the cohesive subgraphs with hierarchical relations on HINs, we adopt the well-known$(k,\mathcal{P})$-core model to compute coreness over HINs, where$\mathcal{P}$is a meta-path, i.e., a sequence of relations defined between different types of vertices. Hence, the$(k,\mathcal{P})$-core is a subgraph where each vertex is connected to at least$k$other vertices via instances of$\mathcal{P}$. Based on two kinds of sparse matrix products, we propose two kinds of algebraic core decomposition algorithms, which are suitable for general HINs and locally dense HINs, respectively. We have performed extensive empirical evaluations of our algorithms on six large real-world HINs. The results show that the proposed solutions are highly efficient for core decomposition and achieve up to$258.84\times$speedup than the state-of-the-art parallel algorithm on 20 cores. Moreover, other HIN tasks that involve homogeneous graph construction can also benefit from our algorithms.

Identifying dense subgraphs called quasi-cliques is pivotal in various graph mining tasks across domains like biology, social networks, and e-commerce. However, recent algorithms still suffer from efficiency issues when mining large quasi-cliques in massive and complex graphs. Our key insight is that vertices within a quasi-clique exhibit similar neighborhoods to some extent. Based on this, we introduce NBSim and FastNBSim, efficient algorithms that find near-maximum quasi-cliques by exploiting vertex neighborhood similarity. FastNBSim further uses MinHash approximations to reduce the time complexity for similarity computation. Empirical evaluation on 10 real-world graphs shows that our algorithms deliver up to three orders of magnitude speedup versus the state-of-the-art algorithms, while ensuring high-quality quasi-clique extraction.

Sparse matrices are often used to model the interactions among different objects and they are prevalent in many areas including e-commerce, social network, and biology. As one of the fundamental matrix operations, the sparse matrix chain multiplication (SMCM) aims to efficiently multiply a chain of sparse matrices, which has found various real-world applications in areas like network analysis, data mining, and machine learning. The efficiency of SMCM largely hinges on the order of multiplying the matrices, which further relies on the accurate estimation of the sparsity values of intermediate matrices. Existing matrix sparsity estimators often struggle with large sparse matrices, because they suffer from the accuracy issue in both theory and practice. To enable efficient SMCM, in this paper we introduce a novel row-wise sparsity estimator (RS-estimator), a straightforward yet effective estimator that leverages matrix structural properties to achieve efficient, accurate, and theoretically guaranteed sparsity estimation. Based on the RS-estimator, we propose a novel ordering algorithm for determining a good order of efficient SMCM. We further develop an efficient parallel SMCM algorithm by effectively utilizing multiple CPU threads. We have conducted experiments by multiplying various chains of large sparse matrices extracted from five real-world large graph datasets, and the results demonstrate the effectiveness and efficiency of our proposed methods. In particular, our SMCM algorithm is up to three orders of magnitude faster than the state-of-the-art algorithms.

The enumeration of hop-constrained simple paths is a building block in many graph-based areas. Due to the enormous search spaces in large-scale graphs, a single machine can hardly satisfy the requirements of both efficiency and memory, which causes an urgent need for efficient distributed methods. In practice, it is inevitable to produce plenty of intermediate results when directly extending centralized methods to the distributed environment, thereby causing a memory crisis and weakening the query performance. The state-of-the-art distributed method HybridEnum designed a hybrid search paradigm to enumerate simple paths. However, it makes massive exploration for the redundant vertices not located in any simple path, thereby resulting in poor query performance. To alleviate this problem, we design a distributed approach DistriEnum to optimize query performance and scalability with well-bound memory consumption. Firstly, DistriEnum adopts a graph reduction strategy to rule out the redundant vertices without satisfying the constraint of hop number. Then, a core search paradigm is designed to simultaneously reduce the traversal of shared subpaths and the storage of intermediate results. Moreover, DistriEnum is equipped with a task division strategy to theoretically achieve workload balance. Finally, a vertex migration strategy is devised to reduce the communication cost during the enumeration. The comprehensive experimental results on 10 real-world graphs demonstrate that DistriEnum achieves up to 3 orders of magnitude speedup than HybridEnum in query performance and exhibits superior performances on scalability, communication cost, and memory consumption.

Densest subgraph discovery (DSD) is a fundamental topic in graph mining. It has been extensively studied in the literature and has found many real applications in a wide range of fields, such as biology, finance, and social networks. As a typical problem of DSD, the k-clique densest subgraph (CDS) problem aims to detect a subgraph from a graph, such that the ratio of the number of k-cliques over the number of its vertices is maximized. This problem has received plenty of attention in the literature, and is widely used in identifying larger ''near-cliques''. Existing CDS solutions, either k-core or convex programming based solutions, often need to enumerate almost all the k-cliques, which is very inefficient because real-world graphs usually have a vast number of k-cliques. To improve the efficiency, in this paper, we propose a novel framework based on the Frank-Wolfe algorithm, which only needs k-clique counting, rather than k-clique enumeration, where the former one is often much faster than the latter one. Based on the framework, we develop an efficient approximation algorithm, by employing the state-of-the-art k-clique counting algorithm and proposing some optimization techniques. We have performed extensive experimental evaluation on 14 real-world large graphs and the results demonstrate the high efficiency of our algorithms. Particularly, our algorithm is up to seven orders of magnitude faster than the state-of-the-art algorithm with the same accuracy guarantee.

Directed graphs are prevalent in social networks, web networks, and communication networks. A well-known concept of the directed graph is the D-core, or ( k, l )-core, which is the maximal subgraph in which each vertex has an in-degree not less than k and an out-degree not less than l. Computing the non-empty D-cores for all possible values of k and l , a.k.a. D-core decomposition, has found versatile applications spanning social network analysis, community search, and graph visualization. However, existing algorithms of D-core decomposition suffer from efficiency and scalability issues on large graphs, because serial peeling-based algorithms are limited by single-core utilization, while skyline coreness-based methods exhibit notably high time complexity. To tackle these issues, in this paper, we propose efficient parallel algorithms for D-core decomposition by leveraging the computational prowess of multicore CPUs. Specifically, we first propose a novel algorithm that computes the D-cores for each possible k value, by exploiting an implicit level-by-level vertex removal strategy, which not only diminishes dependencies between vertices but also maintains a time complexity akin to that of sequential algorithms. We further develop an advanced algorithm by introducing a novel concept of D-shell, which allows us to curtail redundant computations by reducing the necessary k values when computing corresponding D-cores, and deriving D-cores with larger k values from the D-cores currently computed based on D-shell. Extensive experiments on ten real-world large graphs show that our algorithms are highly efficient and scalable, and the advanced algorithm is up to two orders of magnitude faster than the state-of-the-art parallel decomposition algorithm with 32 threads.

Interactive graph search (IGS) over DAGs aims to find a hidden target by asking interactive questions as few as possible. IGS is useful for many applications, e.g., facilitating supervised learning tasks by harnessing labeled data, image categorization, and product classification. However, most of the existing IGS methods only work for either single target search on DAGs or multiple targets search on simple trees. To overcome the gap, it motivates us to study a challenging and yet not solved problem of multiple targets search over DAGs. We analyze the new problem in-depth and propose a key concept of uncertain candidates. Based on it, we design an effective gain function to determine the best vertex to be asked questions and shrink the search space of potential targets greatly. Leveraging our uncertain candidates and gain function, we develop a unified k-EIS framework to search both single target and multiple targets. We analyze all algorithm complexities and theoretically show that our solution can significantly improve existing DFS-tree-based methods by asking O ( n ) questions to O (log 2 n ) questions in worst cases. To further improve IGS for multiple targets, we propose an advanced solution by dividing the whole DAG into k disjoint subgraphs with single targets and then tackling each subgraph one by one independently. Extensive experiments on real-world datasets validate that our proposed k-EIS framework can save lots of questions to search exact targets against four state-of-the-art IGS competitors.

Distance labeling approaches are widely adopted to speed up the shortest-distance query performance. Due to the explosive growth of data graphs, a single machine can hardly satisfy the requirements of both computational power and memory capacity, which causes an urgent need for efficient distributed methods. As the graph is distributed across different machines, it is inevitable to frequently exchange messages among different machines when deploying the existing centralized distance labeling methods on the distributed environment, thereby producing serious communication costs and weakening the scalability. To alleviate this problem, we design a distributed hop-based indexDH-Index, which is designed based on a newly proposed boundary graph structure and restricts the index-based hop number of each connected vertex pair within 4 hops. In addition, we propose a hierarchical algorithm to accelerate the index construction and reduce the communication cost. Furthermore, a bidirectional searching strategy is proposed to efficiently resolve the query tasks based on DH-Index. The comprehensive experimental results on eight real-world graphs demonstrate that DH-Index achieves up to 65.5× and 3 orders of magnitude speedup than the existing methods in indexing time and query performance respectively, and exhibits superior capabilities on memory space, communication cost, and scalability.

In the heterogeneous information network (HIN), a motif-clique is a "complete graph" for a given motif (or a small connected graph) that could capture the desired relationship in the motif. The maximal motif-cliques of HINs have found various applications in community discovery, recommendation, and biological network analysis. The state-of-the-art algorithm for enumerating maximal motif-cliques may have to explore all possible subgraphs of a maximal motif-clique and check whether a maximal motif-clique has been enumerated at each recursive step, which is very time-consuming. To improve the efficiency of enumeration, in this paper, we develop efficient algorithms for maximal motif-clique enumeration over large HINs. We first introduce an order-based framework to avoid duplicated enumeration, which results in lower time complexity compared to the existing algorithm. We then propose a pivot-based pruning strategy, which significantly reduces the search space. We further optimize the process of identifying the candidate sets and locating the subgraphs containing the maximal motif-cliques. Extensive experiments on five real-world HINs demonstrate that our proposed algorithm achieves high efficiency and is up to three orders of magnitude faster than the state-of-the-art algorithm.

As a fundamental topic in graph mining, Densest Subgraph Discovery (DSD) has found a wide spectrum of real applications. Several DSD algorithms, including exact and approximation algorithms, have been proposed in the literature. However, these algorithms have not been systematically and comprehensively compared under the same experimental settings. In this paper, we first summarize a unified framework to incorporate all DSD algorithms from a high-level perspective. We then extensively compare representative DSD algorithms over a range of graphs - from small to billion-scale - and examine the effectiveness of all methods, providing a thorough analysis of DSD algorithms. As a byproduct of our experimental analysis, we are also able to identify new variants of the DSD algorithms over undirected graphs, by combining existing techniques, which are up to 10× faster than the state-of-the-art algorithm with the same accuracy guarantee. Finally, based on the findings, we offer promising research opportunities. We believe that a deeper understanding of the behavior of existing algorithms can provide new valuable insights for future research.

Searching on bipartite graphs serves as a fundamental task for various real-world applications, such as recommendation systems, database retrieval, and document querying. Conventional approaches rely on similarity matching in continuous euclidean space of vectorized node embeddings. To handle intensive similarity computation efficiently, hashing techniques for graph-structured data have emerged as a prominent research direction. However, despite the retrieval efficiency in Hamming space, previous studies have encounteredcatastrophic performance decay. To address this challenge, we investigate the problem of hashing with Graph Convolutional Network for effective Top-N search. Our findings indicate the learning effectiveness of incorporating hashing techniques within the exploration of bipartite graph reception fields, as opposed to simply treating hashing as post-processing to output embeddings. To further enhance the model performance, we advance upon these findings and proposeBipartiteGraphContrastiveHashing (BGCH+). BGCH+ introduces a novel dual augmentation approach to bothintermediate informationandhash code outputsin the latent feature spaces, thereby producing more expressive and robust hash codes within a dual self-supervised learning paradigm. Comprehensive empirical analyses on six real-world benchmarks validate the effectiveness of our dual feature contrastive learning in boosting the performance of BGCH+ compared to existing approaches.

Graphs in real-world applications usually evolve constantly presenting dynamic behaviors such as social networks and transportation networks. Hence, dynamic graph embedding has gained much attention recently. In dynamic graphs, both the topology and node attributes could change over time, which pose great challenges for developing effective embedding models. Typically, the evolution process of a dynamic graph can be recorded as a series of snapshots. We observe that the evolution process inherently provides both prior information (previous snapshots) and validation information (the next snapshot). The prior information can be used to fit the evolution process, while the validation information can be used to improve the generalization ability of a graph embedding model. However, existing dynamic graph embedding models only utilize the prior information, but overlook the validation information. To tackle this issue, this paper proposes a novel dynamic graph embedding method via Model-Agnostic Meta-Learning, which utilizes both kinds of information to obtain better graph representation. The extensive experiments on eight real-world datasets demonstrate the superiority of our proposed method over state-of-the-art methods on various graph analysis tasks.

As a fundamental problem in graph data mining, Densest Subgraph Discovery (DSD) aims to find the subgraph with the highest density from a graph. It has been studied for several decades and found a large number of real-world applications, such as network community detection, regulatory motif discovery in DNA, graph index construction, and fake follower detection. Although there are many existing DSD algorithms, they are often not scalable or efficient to process large-scale graphs, since most of them are serial algorithms and can only leverage the computing resource of a single CPU core. To tackle these issues, in this paper we propose efficient parallel algorithms for solving the DSD problems on both undirected and directed graphs at scale. Our main idea is to use the k-cores (a kind of dense subgraph) to approximate the densest subgraph in the undirected graphs, and then propose efficient parallel algorithms for computing the cores by optimizing the iterative process and also reducing the number of iterations. We further extend this idea for directed graphs by introducing a novel concept, named w-induced subgraph, to avoid unnecessary enumerations of x or y when searching [x,y]-cores (a kind of directed dense subgraph to approximate the densest). To verify the scalability and efficiency of the proposed algorithms, we have conducted extensive experiments on 12 large real-world graphs, and four of them are billion-scale. The experimental results show that our proposed algorithms outperform the state-of-the-art algorithms on both undirected and directed graphs, in terms of scalability and efficiency.

Bipartite graph is an important data structure that widely exists in disease prevention and control, community detection, and other real-life applications. In a bipartite graph, edges not only connect entries of different types but also are bridges of different communities in the above applications. However, research to date has not yet focused on edge importance in bipartite graphs. Inspired by this, we study a new problem of top-k edge search in bipartite graphs with the goal of finding k most important edges for a given bipartite graph; these edges are crucial bridges among communities. In particular, we introduce the measure of ego-betweenness for evaluating the importance of edges. To handle this problem effectively, a lazy bound-based algorithm is first proposed by integrating an upper bound pruning strategy. After that, to further get better efficiency, a greedy bound-based heuristic algorithm is explored on the basis of a tighter upper bound which contributes to reducing redundant computation for calculating ego-betweenness. Last but not least, two parallel techniques with different levels of granularity, called P -src and P -task, are respectively introduced to further improve the search efficiency. The experimental results on both real-world and synthetic graphs demonstrate the efficiency and scalability of the proposed algorithms.

Searching on bipartite graphs is basal and versatile to many real-world Web applications, e.g., online recommendation, database retrieval, and query-document searching. Given a query node, the conventional approaches rely on the similarity matching with the vectorized node embeddings in the continuous Euclidean space. To efficiently manage intensive similarity computation, developing hashing techniques for graph-structured data has recently become an emerging research direction. Despite the retrieval efficiency in Hamming space, prior work is however confronted with catastrophic performance decay. In this work, we investigate the problem of hashing with Graph Convolutional Network on bipartite graphs for effective Top-N search. We propose an end-to-end Bipartite Graph Convolutional Hashing approach, namely BGCH, which consists of three novel and effective modules: (1) adaptive graph convolutional hashing, (2) latent feature dispersion, and (3) Fourier serialized gradient estimation. Specifically, the former two modules achieve the substantial retention of the structural information against the inevitable information loss in hash encoding; the last module develops Fourier Series decomposition to the hashing function in the frequency domain mainly for more accurate gradient estimation. The extensive experiments on six real-world datasets not only show the performance superiority over the competing hashing-based counterparts, but also demonstrate the effectiveness of all proposed model components contained therein.

As an important cohesive subgraph model in bipartite graphs, the (α, β)-core (a.k.a. bi-core) has found a wide spectrum of real-world applications, such as product recommendation, fraudster detection, and community search. In these applications, the bipartite graphs are often large and dynamic, where vertices and edges are inserted and deleted frequently, so it is costly to recompute (α, β)-cores from scratch when the graph has changed. Recently, a few works have attempted to study how to maintain (α, β)-cores in the dynamic bipartite graph, but their performance is still far from perfect, due to the huge size of graphs and their frequent changes. To alleviate this issue, in this paper we present efficient (α, β)-core maintenance algorithms over bipartite graphs. We first introduce a novel concept, called bi-core numbers, for the vertices of bipartite graphs. Based on this concept, we theoretically analyze the effect of inserting and deleting edges on the changes of vertices' bi-core numbers, which can be further used to narrow down the scope of the updates, thereby reducing the computational redundancy. We then propose efficient (α, β)-core maintenance algorithms for handling the edge insertion and edge deletion respectively, by exploiting the above theoretical analysis results. Finally, extensive experimental evaluations are performed on both real and synthetic datasets, and the results show that our proposed algorithms are up to two orders of magnitude faster than the state-of-the-art approaches.

Spatial objects often come with textual information, such as Points of Interest (POIs) with their descriptions, which are referred to as geo-textual data. To retrieve such data, spatial keyword queries that take into account both spatial proximity and textual relevance have been extensively studied. Existing indexes designed for spatial keyword queries are mostly built based on the geo-textual data without considering the distribution of queries already received. However, previous studies have shown that utilizing the known query distribution can improve the index structure for future query processing. In this paper, we propose WISK, a learned index for spatial keyword queries, which self-adapts for optimizing querying costs given a query workload. One key challenge is how to utilize both structured spatial attributes and unstructured textual information during learning the index. We first divide the data objects into partitions, aiming to minimize the processing costs of the given query workload. We prove the NP-hardness of the partitioning problem and propose a machine learning model to find the optimal partitions. Then, to achieve more pruning power, we build a hierarchical structure based on the generated partitions in a bottom-up manner with a reinforcement learning-based approach. We conduct extensive experiments on real-world datasets and query workloads with various distributions, and the results show that WISK outperforms all competitors, achieving up to 8× speedup in querying time with comparable storage overhead.

In this paper, for the first time, we introduce the concepts of window-CCs and window-SCCs on undirected and directed temporal graphs, respectively. We then study the queries of window-CC and window-SCC by developing several efficient index-based query solutions. The space costs of the best indices are linear to the sizes of the temporal graphs. The extensive experimental evaluation on 12 real-world datasets demonstrates the high efficiency and effectiveness of the proposed solutions. In the future, we will develop distributed index construction algorithms, which would be useful for very large temporal graphs containing billions of edges. In the future, we will implement our algorithms by using a distributed computing platform (e.g., Pregel), which would be very useful when the temporal graph is too large to be kept by a single machine.

The densest subgraph problem (DSP) is of great significance due to its wide applications in different domains. Meanwhile, diverse requirements in various applications lead to different density variants for DSP. Unfortunately, existing DSP algorithms cannot be easily extended to handle those variants efficiently and accurately. To fill this gap, we first unify different density metrics into a generalized density definition. We further propose a new model, c-core, to locate the general densest subgraph and show its advantage in accelerating the searching process. Extensive experiments show that our c-core-based optimization can provide up to three orders of magnitude speedup over baselines. Moreover, we study an important variant of DSP under a size constraint, namely the densest-at-least-k-subgraph (DalkS) problem. We propose an algorithm based on graph decomposition, and it is likely to give a solution that is at least 0.8 of the optimal density in our experiments, while the state-of-the-art method can only ensure a solution with density at least 0.5 of the optimal density. Our experiments show that our DalkS algorithm can achieve at least 0.99 of the optimal density for over one-third of all possible size constraints.

Recently, the topic of influential community search has gained much attention. Given a graph, it aims to find communities of vertices with high importance values from it. Existing works mainly focus on conventional homogeneous networks, where vertices are of the same type. Thus, they cannot be applied to heterogeneous information networks (HINs) like bibliographic networks and knowledge graphs, where vertices are of multiple types and their importance values are of heterogeneity (i.e., for vertices of different types, their importance meanings are also different). In this paper, we study the problem of influential community search over large HINs. We introduce a novel community model, called heterogeneous influential community (HIC), or a set of closely connected vertices that are of the same type and high importance values, using the meta-path-based core model. An HIC not only captures the importance of vertices in a community, but also considers the influence on meta-paths connecting them. To search the HICs, we mainly consider meta-paths with two and three vertex types. Then, we develop basic algorithms by iteratively peeling vertices with low importance values, and further propose advanced algorithms by identifying the key vertices and designing pruning strategies that allow us to quickly eliminate vertices with low importance values. Extensive experiments on four real large HINs show that our solutions are effective for searching HICs, and the advanced algorithms significantly outperform baselines.

Heterogeneous graphs, which contain nodes and edges of multiple types, are prevalent in various domains, including bibliographic networks, social media, and knowledge graphs. As a fundamental task in analyzing heterogeneous graphs, relevance measure aims to calculate the relevance between two objects of different types, which has been used in many applications such as web search, recommendation, and community detection. Most of existing relevance measures focus on homogeneous networks where objects are of the same type, and a few measures are developed for heterogeneous graphs, but they often need the pre-defined meta-path. Defining meaningful meta-paths requires much domain knowledge, which largely limits their applications, especially on schema-rich heterogeneous graphs like knowledge graphs. Recently, the Graph Neural Network (GNN) has been widely applied in many graph mining tasks, but it has not been applied for measuring relevance yet. To address the aforementioned problems, we propose a novel GNN-based relevance measure, namely GSim. Specifically, we first theoretically analyze and show that GNN is effective for measuring the relevance of nodes in the graph. We then propose a context path-based graph neural network (CP-GNN) to automatically leverage the semantics in heterogeneous graphs. Moreover, we exploit CP-GNN to support relevance measures between two objects of any type. Extensive experiments demonstrate that GSim outperforms existing measures. (Coda and data is available at this linkhttps://github.com/RManLuo/GSim).

In this paper, we study the problem of constrained path search with submodular function maximization (CPS-SM). We aim to find the path with the best submodular function score under a given constraint (e.g., a length limit), where the submodular function score is computed over the set of nodes in this path. This problem can be used in many applications. For example, tourists may want to search the most diversified path (e.g., a path passing by the most diverse facilities such as parks and museums) given that the traveling time is less than 6 hours. We show that the CPS-SM problem is NP-hard. We first propose a concept called “submodular$\alpha$-dominance” by utilizing the submodular function properties, and we develop an algorithm with a guaranteed error bound based on this concept. By relaxing the submodular$\alpha$-dominance conditions, we design another more efficient algorithm that has the same error bound. We also utilize the way of bi-directional path search to further improve the efficiency of the algorithms. We finally propose a heuristic algorithm that is efficient yet effective in practice. The experiments conducted on several real datasets show that our proposed algorithms can achieve high accuracy and are faster than one state-of-the-art method by orders of magnitude.

Node importance estimation is a fundamental task in graph data analysis. Extensive studies have focused on this task, and various downstream applications have benefited from it, such as recommendation, resource allocation optimization, and missing value completion. However, existing works either focus on the homogeneous network or only study importance-based ranking. We are the first to consider the node importance values as heterogeneous values in heterogeneous information networks (HINs). A typical HIN is built of several distinguished node types where each type has its own measure of importance value (e.g., in the DBLP network, the importance values of authors and papers can be reflected by their h-index and citation numbers, respectively). This characteristic makes the above problem more challenging than computing the node importance in conventional homogeneous networks. In this paper, we formally introduce the problem of node importance value estimation in HINs; that is, given the importance values of a subset of nodes in an HIN, we aim to estimate the importance values of the remaining nodes. To solve this problem, we propose an effective graph neural network (GNN) model, called HIN Importance Value Estimation Network (HIVEN). HIVEN traces the local information of each node, specifically by utilizing the heterogeneity of the HIN. Furthermore, the meta schema is deployed to alleviate the node type domination issue. Additionally, HIVEN exploits the node similarity within each type to remedy the shortcoming of GNN models in capturing global information. Extensive experiments on real-world HIN datasets demonstrate that HIVEN superiorly outperforms the baseline methods.

Given a directed graph G, the directed densest subgraph (DDS) problem refers to finding a subgraph from G, whose density is the highest among all subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fake follower detection and community mining. Theoretically, the DDS problem closely connects to other essential graph problems, such as network flow and bipartite matching. However, existing DDS solutions suffer from efficiency and scalability issues. In this paper, we develop a convex-programming-based solution by transforming the DDS problem into a set of linear programs. Based on the duality of linear programs, we develop efficient exact and approximation algorithms. Especially, our approximation algorithm can support flexible parameterized approximation guarantees. We have performed an extensive empirical evaluation of our approaches on eight real large datasets. The results show that our proposed algorithms are up to five orders of magnitude faster than the state-of-the-art.

As one of the most fundamental problems in graph data mining, the densest subgraph discovery (DSD) problem has found a broad spectrum of real applications, such as social network community detection, graph index construction, regulatory motif discovery in DNA, fake follower detection, and so on. Theoretically, DSD closely relates to other fundamental graph problems, such as network flow and bipartite matching. Triggered by these applications and connections, DSD has garnered much attention from the database, data mining, theory, and network communities. In this tutorial, we first highlight the importance of DSD in various applications and the unique challenges that need to be addressed. Subsequently, we classify existing DSD solutions into several groups, which cover around 50 research papers published in many well-known venues (e.g., SIGMOD, PVLDB, TODS, WWW), and conduct a thorough review of these solutions in each group. Afterwards, we analyze and compare the models and solutions in these works. Finally, we point out a list of promising future research directions. We believe that this tutorial not only helps researchers have a better understanding of existing densest subgraph models and solutions, but also provides them insights for future study.

Community search (CS) enables personalized community discovery and has found a wide spectrum of emerging applications such as setting up social events and friend recommendation. While CS has been extensively studied for conventional homogeneous networks, the problem for heterogeneous information networks (HINs) has received attention only recently. However, existing studies suffer from several limitations, e.g., they either require users to specify a meta-path or relational constraints, which pose great challenges to users who are not familiar with HINs. To address these limitations, in this paper, we systematically study the problem of CS over large star-schema HINs without asking users to specify these constraints; that is, given a set Q of query vertices with the same type, find the most-likely community from a star-schema HIN containing Q , in which all the vertices are with the same type and close relationships. To capture the close relationships among vertices of the community, we employ the meta-path-based core model, and maximize the number of shared meta-paths such that each of them results in a cohesive core containing Q. To enable efficient CS, we first develop online algorithms via exploiting the anti-monotonicity property of shared meta-paths. We further boost the efficiency by proposing a novel index and an efficient index-based algorithm with elegant pruning techniques. Extensive experiments on four real large star-schema HINs show that our solutions are effective and efficient for searching communities, and the index-based algorithm is much faster than the online algorithms.

Given a heterogeneous information network (HIN) H, a head node h , a meta-path P, and a tail node t , the meta-path prediction aims at predicting whether h can be linked to t by an instance of P. Most existing solutions either require predefined meta-paths, which limits their scalability to schema-rich HINs and long meta-paths, or do not aim at predicting the existence of an instance of P. To address these issues, in this article, we propose a novel prediction model, called ABLE, by exploiting the A ttention mechanism and B i L STM for E mbedding. Particularly, we present a concatenation node embedding method by considering the node types and a dynamic meta-path embedding method that carefully considers the importance and positions of edge types in the meta-paths by the Attention mechanism and BiLSTM model, respectively. A triplet embedding is then derived to complete the prediction. We conduct extensive experiments on four real datasets. The empirical results show that ABLE outperforms the state-of-the-art methods by up to 20% and 22% of improvement of AUC and AP scores, respectively.

Community detection, aiming to group the graph nodes into clusters with dense inner-connection, is a fundamental graph mining task. Recently, it has been studied on the heterogeneous graph, which contains multiple types of nodes and edges, posing great challenges for modeling the high-order relationship between nodes. With the surge of graph embedding mechanism, it has also been adopted to community detection. A remarkable group of works use the meta-path to capture the high-order relationship between nodes and embed them into nodes' embedding to facilitate community detection. However, defining meaningful meta-paths requires much domain knowledge, which largely limits their applications, especially on schema-rich heterogeneous graphs like knowledge graphs. To alleviate this issue, in this paper, we propose to exploit the context path to capture the high-order relationship between nodes, and build a Context Path-based Graph Neural Network (CP-GNN) model. It recursively embeds the high-order relationship between nodes into the node embedding with attention mechanisms to discriminate the importance of different relationships. By maximizing the expectation of the co-occurrence of nodes connected by context paths, the model can learn the nodes' embeddings that both well preserve the high-order relationship between nodes and are helpful for community detection. Extensive experimental results on four real-world datasets show that CP-GNN outperforms the state-of-the-art community detection methods1.

Relation prediction is a fundamental task in network analysis which aims to predict the relationship between two nodes. Thus, this differes from the traditional link prediction problem predicting whether a link exists between a pair of nodes, which can be viewed as a binary classification task. However, in the heterogeneous information network (HIN) which contains multiple types of nodes and multiple relations between nodes, the relation prediction task is more challenging. In addition, the HIN might have missing relation types on some edges and missing node types on some nodes, which makes the problem even harder.

With the advent of a wide spectrum of recent applications, querying heterogeneous information networks (HINs) has received a great deal of attention from both academic and industrial societies. HINs involve objects (vertices) and links (edges) that are classified into multiple types; examples include bibliography networks, knowledge networks, and user-item networks in E-business. An important component of these HINs is the cohesive subgraph, or a subgraph containing vertices that are densely connected internally. Searching cohesive subgraphs over HINs has found many real applications, such as community search, product recommendation, fraud detection, and so on. Consequently, how to design effective cohesive subgraph models and how to efficiently search cohesive subgraphs on large HINs become important research topics in the era of big data. In this tutorial, we first highlight the importance of cohesive subgraph search over HINs in various applications and the unique challenges that need to be addressed. Subsequently, we conduct a thorough review of existing works of cohesive subgraph search over HINs. Then, we analyze and compare the models and solutions in these works. Finally, we point out new research directions. We believe that this tutorial not only helps researchers to have a better understanding of existing cohesive subgraph search models and solutions, but also provides them insights for future study.

A bipartite network is a network with two disjoint vertex sets and its edges only exist between vertices from different sets. It has received much interest since it can be used to model the relationship between two different sets of objects in many applications (e.g., the relationship between users and items in E-commerce). In this paper, we study the problem of efficient bi-triangle counting for a large bipartite network, where a bi-triangle is a cycle with three vertices from one vertex set and three vertices from another vertex set. Counting bi-triangles has found many real applications such as computing the transitivity coefficient and clustering coefficient for bipartite networks. To enable efficient bi-triangle counting, we first develop a baseline algorithm relying on the observation that each bi-triangle can be considered as the join of three wedges. Then, we propose a more sophisticated algorithm which regards a bi-triangle as the join of two super-wedges, where a wedge is a path with two edges while a super-wedge is a path with three edges. We further optimize the algorithm by ranking vertices according to their degrees. We have performed extensive experiments on both real and synthetic bipartite networks, where the largest one contains more than one billion edges, and the results show that the proposed solutions are up to five orders of magnitude faster than the baseline method.

Given a directed graph G , the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G , whose density is the highest among all the subgraphs of G . The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a 3,000-edge graph, it takes three days for one of the best exact algorithms to complete. In this article, we develop an efficient and scalable DDS solution. We introduce the notion of [ x , y ]-core, which is a dense subgraph for G , and show that the densest subgraph can be accurately located through the [ x , y ]-core with theoretical guarantees. Based on the [ x , y ]-core, we develop exact and approximation algorithms. We further study the problems of maintaining the DDS over dynamic directed graphs and finding the weighted DDS on weighted directed graphs, and we develop efficient non-trivial algorithms to solve these two problems by extending our DDS algorithms. We have performed an extensive evaluation of our approaches on 15 real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.

A huge volume of spatio-textual objects generated from location-based services enable a wide range of spatial keyword queries. Recently, researchers have proposed a novel query, called Spatial Pattern Matching (SPM), which uses a pattern to capture users' intention. It has been demonstrated to be useful but computationally intractable. Existing algorithms suffer from the low efficiency issue, especially on large scale datasets. To enhance the performance of SPM, in this paper we propose a novel Efficient Spatial Pattern Matching (ESPM) algorithm, which exploits the inverted linear quadtree index and computes matched node pairs and object pairs level by level in a top-down manner. In particular, it focuses on pruning unpromising nodes and node pairs at the high levels, resulting in a large number of unpromising objects and object pairs to be pruned before accessing them from disk. Our experimental results on real large datasets show that ESPM is over one order of magnitude faster than the state-of-the-art algorithm, and also uses much less I/O cost.

Large networks with labeled nodes are prevalent in various applications, such as biological graphs, social networks, and e-commerce graphs. To extract insight from this rich information source, we propose MC-Explorer, which is an advanced analysis and visualization system. A highlight of MC-Explorer is its ability to discover motif-cliques from a graph with labeled nodes. A motif, such as a 3-node triangle, is a fundamental building block of a graph. A motif-clique is a "complete" subgraph in a network with respect to a desired higher-order connection pattern. For example, on a large biological graph, we found out some motif-cliques, which disclose new side effects of a drug, and potential drugs for healing diseases. MC-Explorer includes online and interactive facilities for exploring a large labeled network through the use of motif-cliques. We will demonstrate how MC-Explorer can facilitate the analysis and visualization of a labeled biological network.An online demo video of MC-Explorer can be accessed from https://www.dropbox.com/s/vkalumc28wqp8yl/demo.mov.

Recently, the topic of truss computation has gained plenty of attention, where the k-truss of a graph is the maximum subgraph in which each edge participates in at least (k-2) triangles. Existing solutions mainly focus on homogeneous networks, where vertices are of the same type, and thus cannot be applied to heterogeneous information networks which consist of multi-typed and interconnected objects, such as the bibliographic networks and knowledge graphs. In this paper, we study the problem of truss computation over HINs, which aims to find groups of vertices that are of the same type and densely connected. To model the relationship between two vertices of the same type, we adopt the well-known concept of meta-path, which is a sequence of vertex types and edge types between two given vertex types. We then introduce two kinds of HIN triangles for three vertices, regarding a specific meta-path P. The first one requires that each pair of vertices is connected by an instance of P, while the second one also has such a connectivity constraint but further needs that the three instances of P form a circle. Based on these two kinds of triangles, we propose two HIN truss models respectively. We further develop efficient truss computation algorithms. We have performed extensive experiments on five real large HINs, and the results show that the proposed solutions are highly effective and efficient.

Given a directed graph G, the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G, whose density is the highest among all the subgraphs of G. The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a three-thousand-edge graph, it takes three days for one of the best exact algorithms to complete. In this paper, we develop an efficient and scalable DDS solution. We introduce the notion of [x, y]-core, which is a dense subgraph for G, and show that the densest subgraph can be accurately located through the [x, y]-core with theoretical guarantees. Based on the [x, y]-core, we develop exact and approximation algorithms. We have performed an extensive evaluation of our approaches on eight real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.

Recently, the topic of community search (CS) has gained plenty of attention. Given a query vertex, CS looks for a dense subgraph that contains it. Existing studies mainly focus on homogeneous graphs in which vertices are of the same type, and cannot be directly applied to heterogeneous information networks (HINs) that consist of multi-typed, interconnected objects, such as the bibliographic networks and knowledge graphs. In this paper, we study the problem of community search over large HINs; that is, given a query vertex q , find a community from an HIN containing q , in which all the vertices are with the same type of q and have close relationships. To model the relationship between two vertices of the same type, we adopt the well-known concept of meta-path , which is a sequence of relations defined between different types of vertices. We then measure the cohesiveness of the community by extending the classic minimum degree metric with a meta-path. We further propose efficient query algorithms for finding communities using these cohesiveness metrics. We have performed extensive experiments on five real large HINs, and the results show that the proposed solutions are effective for searching communities. Moreover, they are much faster than the baseline solutions.

With recent advances in information technologies such as global position system and mobile internet, a huge volume of spatio-textual objects have been generated from location-based services, which enable a wide range of spatial keyword queries. Recently, researchers have proposed a novel query, called Spatial Pattern Matching (SPM), which uses a pattern to capture the user's intention. It has been demonstrated to be fundamental and useful for many real applications. Despite its usefulness, the SPM problem is computationally intractable. Existing algorithms suffer from the low efficiency issue, especially on large scale datasets. To enhance the performance of SPM, in this paper we propose a novel Efficient Spatial Pattern Matching (ESPM) algorithm, which exploits the inverted linear quadtree index and computes matched node pairs and object pairs level by level in a top-down manner. In particular, it focuses on pruning unpromising nodes and node pairs at the high levels, resulting in a large number of unpromising objects and object pairs to be pruned before accessing them from disk. We experimentally evaluate the performance of ESPM on real large datasets. Our results show that ESPM is over one order of magnitude faster than the state-of-the-art algorithm, and also uses much less I/O cost.

Given a graph G and a vertex q ∊ G, the community search (CS) problem aims to efficiently find a subgraph of G whose vertices are closely related to q. Communities are prevalent in social and biological networks, and can be used in product advertisement and social event recommendation. In this paper, we study profiled community search (PCS), where CS is performed on a profiled graph. This is a graph in which each vertex has labels arranged in a hierarchical manner. Compared with existing CS approaches, PCS can sufficiently identify vertices with semantic commonalities and thus find more high-quality diverse communities. As a naive solution for PCS is highly expensive, we have developed a tree index, which facilitates efficient and online solutions for PCS.

Communities are prevalent in social networks, knowledge graphs, and biological networks. Recently, the topic of community search (CS), extracting a dense subgraph containing a query vertex q from a graph, has received great attention. However, existing CS solutions are designed for undirected graphs, and overlook directions of edges which potentially lose useful information carried on directions. In many applications (e.g., Twitter), users' relationships are often modeled as directed graphs (e.g., if a user a follows another user b, then there is an edge from a to b). In this paper, we study the problem of CS on directed graph. Given a vertex q of a graph G, we aim to find a densely connected subgraph containing q from G, in which vertices have strong interactions and high similarities, by using the minimum in/out-degrees metric. We first develop a baseline algorithm based on the concept of D-core. We further propose three index structures and corresponding query algorithms. Our experimental results on seven real graphs show that our solutions are very effective and efficient.

We study the discovery of cliques (or "complete" subgraphs) in heterogeneous information networks (HINs). Existing clique-finding solutions often ignore the rich semantics of HINs. We propose motif clique, or m-clique, which redefines subgraph completeness with respect to a given motif. A motif, essentially a small subgraph pattern, is a fundamental building block of an HIN. The m-clique concept is general and allows us to analyse "complete" subgraphs in an HIN with respect to desired high-order connection patterns. We further investigate the maximal m-clique enumeration problem (MMCE), which finds all maximal m-cliques not contained in any other m-cliques. Because MMCE is NP-hard, developing an accurate and efficient solution for MMCE is not straightforward. We thus present the META algorithm, which employs advanced pruning strategies to effectively reduce the search space. We also design fast techniques to avoid generating duplicated maximal m-clique instances. Our extensive experiments on large real and synthetic HINs show that META is highly effective and efficient.

Densest subgraph discovery (DSD) is a fundamental problem in graph mining. It has been studied for decades, and is widely used in various areas, including network science, biological analysis, and graph databases. Given a graph G , DSD aims to find a subgraph D of G with the highest density (e.g., the number of edges over the number of vertices in D ). Because DSD is difficult to solve, we propose a new solution paradigm in this paper. Our main observation is that the densest subgraph can be accurately found through a k -core (a kind of dense subgraph of G ), with theoretical guarantees. Based on this intuition, we develop efficient exact and approximation solutions for DSD. Moreover, our solutions are able to find the densest subgraphs for a wide range of graph density definitions, including clique-based- and general pattern-based density. We have performed extensive experimental evaluation on both real and synthetic datasets. Our results show that our algorithms are up to four orders of magnitude faster than existing approaches.

In graph applications (e.g., biological and social networks), various analytics tasks (e.g., clustering and community search) are carried out to extract insight from large and complex graphs. Central to these tasks is the counting of the number of motifs , which are graphs with a few nodes. Recently, researchers have developed several fast motif counting algorithms. Most of these solutions assume that graphs are deterministic, i.e., the graph edges are certain to exist. However, due to measurement and statistical prediction errors, this assumption may not hold, and hence the analysis quality can be affected. To address this issue, we examine how to count motifs on uncertain graphs, whose edges only exist probabilistically. Particularly, we propose a solution framework that can be used by existing deterministic motif counting algorithms. We further propose an approximation algorithm. Extensive experiments on real datasets show that our algorithms are more effective and efficient than existing solutions.

Given a graph $G$G and a vertex $q\in G$q∈G, the community search (CS) problem aims to efficiently find a subgraph of $G$G whose vertices are closely related to $q$q. Communities are prevalent in social and biological networks, and can be used in product advertisement and social event recommendation. In this paper, we study profiled community search (PCS), where CS is performed on a profiled graph. This is a graph in which each vertex has labels arranged in a hierarchical manner. Extensive experiments show that PCS can identify communities with themes that are common to their vertices, and is more effective than existing CS approaches. As a naive solution for PCS is highly expensive, we have also developed a tree index, which facilitates efficient and online solutions for PCS.

Communities are prevalent in social networks, knowledge graphs, and biological networks. Recently, the topic of community search (CS) has received plenty of attention. The CS problem aims to look for a dense subgraph that contains a query vertex. Existing CS solutions do not consider the spatial extent of a community. They can yield communities whose locations of vertices span large areas. In applications that facilitate setting social events (e.g., finding conference attendees to join a dinner), it is important to find groups of people who are physically close to each other, so it is desirable to have aspatial-aware community(or SAC), whose vertices are close structurally and spatially. Given a graph$G$and a query vertex$q$, we develop an exact solution to find the SAC containing$q$, but it cannot scale to large datasets, so we design three approximation algorithms. We further study the problem of continuous SAC search on a “dynamic spatial graph,” whose vertices’ locations change with time, and propose three fast solutions. We evaluate the solutions on both real and synthetic datasets, and the results show that SACs are better than communities returned by existing solutions. Moreover, our approximation solutions perform accurately and efficiently.

Communities are prevalent in social networks, knowledge graphs, and biological networks. Recently, the topic of community search (CS), extracting a dense subgraph containing a query vertex q from a graph, has received great attention. However, existing CS solutions are designed for undirected graphs, and overlook directions of edges which potentially lose useful information carried on directions. In many applications (e.g., Twitter), users' relationships are often modeled as directed graphs (e.g., if a user a follows another user b, then there is an edge from a to b). In this paper, we study the problem of CS on directed graph. Given a vertex q of a graph G, we aim to find a densely connected subgraph containing q from G, in which vertices have strong interactions and high similarities, by using the minimum in/out-degrees metric. We first develop a baseline algorithm based on the concept of D-core. We further propose three index structures and corresponding query algorithms. Our experimental results on seven real graphs show that our solutions are very effective and efficient. For example, on a graph with over 1 billion of edges, we only need around 40mins to index it and 1~2sec to answer a query.

International audience

In this paper, we study the spatial pattern matching (SPM) query. Given a set D of spatial objects (e.g., houses and shops), each with a textual description, we aim at finding all combinations of objects from D that match a user-defined spatial pattern P. A pattern P is a graph where vertices represent spatial objects, and edges denote distance relationships between them. The SPM query returns the instances that satisfy P. An example of P can be "a house within 10-minute walk from a school, which is at least 2km away from a hospital". The SPM query can benefit users such as house buyers, urban planners, and archaeologists. We prove that answering such queries is computationally intractable, and propose two efficient algorithms for their evaluation. Extensive experimental evaluation and cases studies on four real datasets show that our proposed solutions are highly effective and efficient.

Spatial objects associated with keywords are prevalent in applications such as Google Maps and Twitter. Recently, the topic of spatial keyword queries has received plenty of attention. Spatial Group Keyword (SGK) search is a popular class of queries; their goal is to find a set of objects which are close to each other and are associated to a set of input keywords. In this paper, we propose SpaceKey, a system for retrieving and visualizing spatial objects returned by SGK queries. In addition to existing SGK query types, SpaceKey supports a novel query, called SPM query. An SPM query is defined by a spatial pattern, a graph whose vertices contain keywords and its edges are associated with distance constraints. The results are sets of objects that match the pattern. SpaceKey allows users to perform comparison analysis between different SGK query types. We plan to make SpaceKey an open-source web-based platform, and design API functions for software developers to plug other SGK query algorithms into our system.

Clustering of customer transaction data is an important procedure to analyze customer behaviors in retail and e-commerce companies. Note that products from companies are often organized as a product tree, in which the leaf nodes are goods to sell, and the internal nodes (except root node) could be multiple product categories. Based on this tree, we propose the “personalized product tree”, named purchase tree, to represent a customer's transaction records. So the customers' transaction data set can be compressed into a set of purchase trees. We propose a partitional clustering algorithm, named PurTreeClust, for fast clustering of purchase trees. A new distance metric is proposed to effectively compute the distance between two purchase trees. To cluster the purchase tree data, we first rank the purchase trees as candidate representative trees with a novel separate density, and then select the top k customers as the representatives of k customer groups. Finally, the clustering results are obtained by assigning each customer to the nearest representative. We also propose a gap statistic based method to evaluate the number of clusters. A series of experiments were conducted on ten real-life transaction data sets, and experimental results show the superior performance of the proposed method.

Graph data are prevalent in communication networks, social media, and biological networks. These data, which are often noisy or inexact, can be represented by uncertain graphs, whose edges are associated with probabilities to indicate the chances that they exist. Recently, researchers have studied various algorithms (e.g., clustering, classification, and k-NN) for uncertain graphs. These solutions face two problems: (1) high dimensionality: uncertain graphs are often highly complex, which can affect the mining quality; and (2) low reusability, where an existing mining algorithm has to be redesigned to deal with uncertain graphs. To tackle these problems, we propose a solution called URGE, or UnceRtain Graph Embedding. Given an uncertain graph G, URGE generates G's embedding, or a set of low-dimensional vectors, which carry the proximity information of nodes in G. This embedding enables the dimensionality of G to be reduced, without destroying node proximity information. Due to its simplicity, existing mining solutions can be used on the embedding. We investigate two low- and high-order node proximity measures in the embedding generation process, and develop novel algorithms to enable fast evaluation.

Community retrieval (CR) algorithms, which enable the extraction of subgraphs from large social networks (e.g., Facebook and Twitter), have attracted tremendous interest. Various CR solutions, such as k -core and codicil , have been proposed to obtain graphs whose vertices are closely related. In this paper, we propose the C-Explorer system to assist users in extracting, visualizing, and analyzing communities. C-Explorer provides online and interactive CR facilities, allowing a user to view her interesting graphs, indicate her required vertex q , and display the communities to which q belongs. A seminal feature of C-Explorer is that it uses an attributed graph , whose vertices are associated with labels and keywords, and looks for an attributed community (or AC), whose vertices are structurally and semantically related. Moreover, C-Explorer implements several state-of-the-art CR algorithms, as well as functions for analyzing their effectiveness. We plan to make C-Explorer an open-source web-based platform, and design API functions for software developers to test their CR algorithms in our system.

Communities are prevalent in social networks, knowledge graphs, and biological networks. Recently, the topic of community search (CS) has received plenty of attention. Given a query vertex, CS looks for a dense subgraph that contains it. Existing CS solutions do not consider the spatial extent of a community. They can yield communities whose locations of vertices span large areas. In applications that facilitate the creation of social events (e.g., finding conference attendees to join a dinner), it is important to find groups of people who are physically close to each other. In this situation, it is desirable to have a spatial-aware community (or SAC), whose vertices are close structurally and spatially. Given a graph G and a query vertex q , we develop exact solutions for finding an SAC that contains q . Since these solutions cannot scale to large datasets, we have further designed three approximation algorithms to compute an SAC. We have performed an experimental evaluation for these solutions on both large real and synthetic datasets. Experimental results show that SAC is better than the communities returned by existing solutions. Moreover, our approximation solutions can find SACs accurately and efficiently.

Given a graph G and a set Q of query nodes, we examine the Steiner Maximum-Connected Subgraph (SMCS) problem. The SMCS, or G's induced subgraph that contains Q with the largest connectivity, can be useful for customer prediction, product promotion, and team assembling. Despite its importance, the SMCS problem has only been recently studied. Existing solutions evaluate the maximum SMCS, whose number of nodes is the largest among all the SMCSs of Q. However, the maximum SMCS, which may contain a lot of nodes, can be difficult to interpret. In this paper, we investigate the minimal SMCS, which is the minimal subgraph of G with the maximum connectivity containing Q. The minimal SMCS contains much fewer nodes than its maximum counterpart, and is thus easier to be understood. However, the minimal SMCS can be costly to evaluate. We thus propose efficient Expand-Refine algorithms, as well as their approximate versions with accuracy guarantees. We further develop a cache-based processing model to improve the efficiency for an important case when Q consists of a single node. Extensive experiments on large real and synthetic graph datasets validate the effectiveness and efficiency of our approaches.

Given a graph G and a set Q of query nodes, we examine the Steiner Maximum-Connected Subgraph (SMCS). The SMCS, or G's induced subgraph that contains Q with the largest connectivity, can be useful for customer prediction, product promotion, and team assembling. Despite its importance, the SMCS problem has only been recently studied. Existing solutions evaluate the maximum SMCS, whose number of nodes is the largest among all the SMCSs of Q. However, the maximum SMCS, which may contain a lot of nodes, can be difficult to interpret. In this paper, we investigate the minimal SMCS, which is the minimal subgraph of G with the maximum connectivity containing Q. The minimal SMCS contains much fewer nodes than its maximum counterpart, and is thus easier to be understood. However, the minimal SMCS can be costly to evaluate. We thus propose efficient Expand-Refine algorithms, as well as their approximate versions with accuracy guarantees. Extensive experiments on six large real graph datasets validate the effectiveness and efficiency of our approaches.

Trajectory data are prevalent in systems that monitor the locations of moving objects. In a location-based service, for instance, the positions of vehicles are continuously monitored through GPS; the trajectory of each vehicle describes its movement history. We study joins on two sets of trajectories, generated by two sets M and R of moving objects. For each entity in M, a join returns its k nearest neighbors from R. We examine how this query can be evaluated in cloud environments. This problem is not trivial, due to the complexity of the trajectory, and the fact that both the spatial and temporal dimensions of the data have to be handled. To facilitate this operation, we propose a parallel solution framework based on MapReduce. We also develop a novel bounding technique, which enables trajectories to be pruned in parallel. Our approach can be used to parallelize existing single-machine trajectory join algorithms. To evaluate the efficiency and the scalability of our solutions, we have performed extensive experiments on a real dataset.

Given a graph G and a vertex q ∈ G , the community search query returns a subgraph of G that contains vertices related to q . Communities, which are prevalent in attributed graphs such as social networks and knowledge bases, can be used in emerging applications such as product advertisement and setting up of social events. In this paper, we investigate the attributed community query (or ACQ), which returns an attributed community (AC) for an attributed graph . The AC is a subgraph of G , which satisfies both structure cohesiveness (i.e., its vertices are tightly connected) and keyword cohesiveness (i.e., its vertices share common keywords). The AC enables a better understanding of how and why a community is formed (e.g., members of an AC have a common interest in music, because they all have the same keyword "music"). An AC can be "personalized"; for example, an ACQ user may specify that an AC returned should be related to some specific keywords like "research" and "sports". To enable efficient AC search, we develop the CL-tree index structure and three algorithms based on it. We evaluate our solutions on four large graphs, namely Flickr, DBLP, Tencent, and DBpedia. Our results show that ACs are more effective and efficient than existing community retrieval approaches. Moreover, an AC contains more precise and personalized information than that of existing community search and detection methods.

Trajectory data are prevalent in systems that monitor the locations of moving objects. In a location-based service, for instance, the positions of vehicles are continuously monitored through GPS; the trajectory of each vehicle describes its movement history. We study joins on two sets of trajectories, generated by two sets M and R of moving objects. For each entity in M, a join returns its k nearest neighbors from R. We examine how this query can be evaluated in cloud environments. This problem is not trivial, due to the complexity of the trajectory, and the fact that both the spatial and temporal dimensions of the data have to be handled. To facilitate this operation, we propose a parallel solution framework based on MapReduce. We also develop a novel bounding technique, which enables trajectories to be pruned in parallel. Our approach can be used to parallelize existing single-machine trajectory join algorithms. We also study a variant of the join, which can further improve query efficiency. To evaluate the efficiency and the scalability of our solutions, we have performed extensive experiments on large real and synthetic datasets.

Despite its popularity, SimRank is computationally costly, in both time and space. In particular, its recursive nature poses a great challenge in using modern distributed computing power, and also prevents querying similarities individually. Existing solutions suffer greatly from these practical issues. In this paper, we break such dependency for maximum efficiency possible. Our method consists of offline and online phases. In offline phase, a length- n indexing vector is derived by solving a linear system in parallel. At online query time, the similarities are computed instantly from the index vector. Throughout, the Monte Carlo method is used to maximally reduce time and space. Our algorithm, called CloudWalker, is highly parallelizable, with only linear time and space. Remarkably, it responses to both single-pair and single-source queries in constant time. CloudWalker is orders of magnitude more efficient and scalable than existing solutions for large-scale problems. Implemented on Spark with 10 machines and tested on the web-scale clue-web graph with 1 billion nodes and 43 billion edges, it takes 110 hours for offline indexing, 64 seconds for a single-pair query, and 188 seconds for a single-source query. To the best of our knowledge, our work is the first to report results on clue-web, which is 10x larger than the largest graph ever reported for SimRank computation.