Several recent works utilize deep learning (DL) techniques for subgraph retrieval via matching, yet most only return approximate isomorphism relations between queries and data graphs--failing to retrieve all exact matching locations, a critical demand for structured graph retrieval in information retrieval. Unlike these DL-based approximate methods, we propose a learning-based framework for subgraph retrieval, called the graph neural network (GNN)-based anchor embedding framework (GNN-AE), which can efficiently retrieve all exact matching locations. In contrast to most traditional exact subgraph matching methods, which create auxiliary structures online for each query, our method has two core optimizations: (1) We construct offline, one-time-only efficient embedding indices for small feature subgraphs (namely, anchored subgraphs and anchored paths) in the data graph and obtain candidates for the query on these indexed feature subgraphs, trading space for time to reduce online query latency; (2) We leverage GNNs to perform graph isomorphism tests on indexed feature subgraphs and generate low-conflict embeddings for these feature subgraphs, yielding a high-quality, compact set of candidates that further enhances query efficiency. Beyond these core optimizations, we develop a parallel matching growth algorithm and design a cost-based DFS query strategy to retrieve all matching locations. Extensive experiments on both real and synthetic datasets validate the efficiency and effectiveness of our GNN-AE for exact subgraph retrieval.

The densest subgraphs in multilayer (ML) graphs unveil intricate relationships that are missed by simple graph representations, offering profound insights and applications across diverse domains. In this paper, we present a layer-oriented view of existing density measures for ML graphs and highlight their problems in identifying the densest subgraphs under the layer-oriented densities, including inefficiency, poor approximation ratios, and the lack of a unified algorithmic framework. In light of this, we introduce a new family of vertex-oriented density measures called generalized density. The two parameters$q$and$p$allow the generalized density to flexibly adjust its focus in the density evaluation. We investigate the problem of finding the ML subgraph that maximizes the generalized density and show that the problem can be solved using a unified greedy vertex peeling framework with strong approximation guarantees for half of the$(q, p)$parameter space. Specifically, for four regimes of$(q, p)$, we design tailored vertex-peeling strategies that lead to approximation algorithms with provable approximation ratios and precise time complexity bounds. We also develop a highly efficient implementation that reduces the execution time of greedy peeling to near-linear time for two of the four explored regimes of$(q, p)$. Extensive experiments on ten real-world ML graphs reveal that our generalized density and greedy peeling algorithms can effectively uncover different types of dense ML subgraphs in large-scale ML graphs.

Finding the maximum biclique in a bipartite graph is a fundamental graph analysis problem. Existing methods for maximum biclique search are not very efficient because they cannot effectively reduce the size of a bipartite graph composed of large bicliques that are loosely linked together because the graph reduction strategies adopted by these methods only consider local densities of vertices. This paper proposes a novel approach to maximum biclique search. The unique feature of this approach is building a linear-space data-driven index called BCviz that helps accurately identify subgraphs containing all bicliques with sizes no less than a certain threshold. The core technique of BCviz is determining a total order of vertices that can reveal both the local density and the connectivity of the vertices. Notably, our work is the first one to take connectivity into account in graph reduction. Interestingly, the total order of vertices entails BCviz an illustrative visualization of the distribution of cohesive subgraphs in the input graph. To deeply understand BCviz, we carry out a theoretical study on its properties and reveal how it enables more effective graph reduction. Based on BCviz, we propose an exact maximum biclique search algorithm that searches for results on much smaller subgraphs than any existing method does. In addition, we improve the efficiency of index construction by two techniques. One is approximating an edge's local density with an upper bound that can be derived in linear time. The other is a lightweight vertex ordering method called one-spot ordering which reduces unnecessary cohesion computations. Extensive experiments indicate that the proposed maximum biclique search methods based on BCviz and its variants outperform the state-of-the-art search-based methods by 2--3 orders of magnitude. Compared with the state-of-the-art index for maximum biclique search, the improved BCviz index can reduce the index size by 1--2 orders of magnitude and the index construction time by up to 2 orders of magnitude.

Multi-layer graphs have emerged as a new representation of multi-faceted relationships between entities in the real world. Community detection on multi-layer graphs has been investigated to gain deeper insights into the modular structures of real-world graphs. As an effective and efficient approach to community detection, structural clustering has been investigated on single-layer graphs. However, it has been overlooked in the study of community detection on multi-layer graphs. In this paper, we give a formulation of structural clustering on multilayer graphs for the first time. Two polynomial-time algorithms are proposed to solve the problem. Furthermore, two indexes, namely the core index and the interval index, with respective peferences to time efficiency and space efficiency, are designed to improve the efficiency of the algorithms. The experiments demonstrate the effectiveness of structural clustering in improving the quality of community detection results on multi-layer graphs. The experiments also verify the improvement in running time due to the use of the proposed indexes.

Mining dense subgraphs on multilayer graphs offers the opportunity for more in-depth discoveries than classical dense subgraph mining on single-layer graphs. However, the existing approaches fail to ensure the denseness of a discovered subgraph on layers of users’ interest and simultaneously gain partial supports on the denseness from other layers. In this paper, we introduce a novel dense subgraph model calledFocusCore(FoCore for short) for multilayer graphs, which can pay more attention to the layers focused by users. The FoCore decomposition problem, that is, identifying all nonempty FoCores in a multilayer graph, can be addressed by executing the peeling process with respect to all possible configurations of focus and background layers. Using the nice properties of FoCores, we devise an interleaved peeling algorithm and a vertex-centric algorithm toward efficient FoCore decomposition. We further design a novel cache to minimize the average retrieval time for an arbitrary FoCore without the need for full FoCore decomposition, which significantly improves efficiency in large-scale graph mining tasks. As an application, we propose a FoCore-decomposition-based algorithm to approximate the densest subgraph in a multilayer graph with a provable approximation guarantee. The extensive experiments on real-world datasets verify the effectiveness of the FoCore model and the efficiency of the proposed algorithms.

Community search on multilayer graphs has significant applications in fields such as bioinformatics, social network analysis, and financial fraud detection, offering deeper insights compared to traditional community search on single-layer graphs. However, existing approaches often suffer from several key limitations, including inefficiency and a lack of flexibility in accommodating query requirements. To address these challenges, we investigate the problem of community search over large multilayer graphs. Specifically, we introduce a novel multilayer community model calledPivotTrussCommunity (PiTC) with provably nice structural guarantees. We formalize the PiTC search (PiTCS) problem, which aims to efficiently identify personalized PiTCs for a given query vertex. To solve the PiTCS problem, we propose an efficient algorithm and design an elegant index to accelerate the search process. In addition, we propose a parameter recommendation method to improve the usability of PiTCS. To further optimize performance, we introduce a method to compact the index by making a trade-off between search time and index size. Extensive experiments on real-world datasets demonstrate the effectiveness and efficiency of our proposed algorithms.

Index tuning is crucial for optimizing database performance by selecting optimal indexes based on workload. The key to this process lies in an accurate and efficient benefit estimator. Traditional methods relying on what-if tools often suffer from inefficiency and inaccuracy. In contrast, learning-based models provide a promising alternative but face challenges such as instability, lack of interpretability, and complex management. To overcome these limitations, we adopt a novel approach: quantifying the uncertainty in learning-based models' results, thereby combining the strengths of both traditional and learning-based methods for reliable index tuning. We proposeBeauty, the first uncertainty-aware framework that enhances learning-based models with uncertainty quantification and uses what-if tools as a complementary mechanism to improve reliability and reduce management complexity. Specifically, we introduce a novel method that combines AutoEncoder and Monte Carlo Dropout to jointly quantify uncertainty, tailored to the characteristics of benefit estimation tasks. In experiments involving sixteen models, our approach outperformed existing uncertainty quantification methods in the majority of cases. We also conducted index tuning tests on six datasets. By applying theBeautyframework, we eliminated worst-case scenarios and more than tripled the occurrence of best-case scenarios.

The multilayer (ML) graph model provides a robust representation of multi-sourced relationships among real-world entities, laying a solid foundation for reliable knowledge discovery. ML core decomposition is a fundamental analytical tool for ML graphs. It offers valuable insights into the dense structures in ML graphs and forms the basis for many complex analysis tasks. However, existing ML core decomposition algorithms face performance issues due to unavoidably unnecessary computations and are inherently serial, unable to fully leverage the multi-core processors. In this paper, we reformulate the search space of this problem with a tree-shaped structure called MLC-tree. Based on it, we present an efficient serial ML core decomposition algorithm that achieves improved time complexity over existing solutions and the first parallel framework for this problem by exploiting the path-decomposition of the MLC-tree. Two practical optimizations are introduced to further boost the parallel efficiency. To facilitate applications built upon ML cores, we construct a compact storage and index structure for ML cores based on the MLC-tree. The usefulness of this index is showcased through two applications: ML core search and a novel weighted densest sub graph discovery problem. Extensive experiments on 9 real-world ML graphs show that our MLC-tree-based ML core decomposition algorithm achieves a speedup of up to$128\times$over existing baselines and the parallel approach attains an additional speedup of up to$30.6\times$using 40 cores. Moreover, the MLC-tree index can efficiently support the studied applications.

Mining dense subgraphs on multilayer graphs offers the opportunity for more in-depth discoveries than classical dense subgraph mining on single-layer graphs. However, the existing approaches fail to ensure the denseness of a discovered subgraph on layers of users' interest and simultaneously gain partial supports on the denseness from other layers. In this paper, we introduce a novel dense subgraph model called FocusCore (FoCore) for multilayer graphs, which can pay more attention to layers focused on by users. The FoCore decomposition problem, i.e., identifying all nonempty FoCores in a multilayer graph, can be addressed by executing the peeling process with respect to all possible configurations of focus and background layers. By utilizing the nice properties of FoCores, we devise an interleaved peeling algorithm and a vertex-centric algorithm towards efficient FoCore decomposition. As an application, we propose a FoCore-decomposition-based algorithm to approximate the densest subgraph in a multilayer graph with a provable approximation guarantee. The extensive experiments on real-world datasets verify the effectiveness of the FoCore model and the efficiency of the proposed algorithms.

Index tuning is a challenging task aiming to improve query performance by selecting the most effective indexes for a database and a workload. Existing automatic index tuning methods typically rely on "what-if tools" to evaluate the benefit of an index configuration, which is costly and sometimes inaccurate. In this paper, we propose RIBE, a novel method that effectively eliminates redundant queries from the workload and harnesses statistical information of query plans to enable fast and accurate estimation of the benefit of an index configuration. With RIBE, a considerable portion of what-if calls can be skipped, thereby reducing index tuning time and increasing estimation accuracy. At the heart of RIBE is a deep learning model based on attention mechanism that predicts the impact of indexes on queries. A practical advantage of RIBE is that it achieves both improved accuracy of benefit estimation and time savings without making any changes to DBMS implementation and index configuration enumeration algorithms. Our evaluation shows that RIBE can achieve competitive tuning results and 1--2 orders of magnitude faster performance compared with the tuning method based on the full workload, and RIBE also attains higher tuning quality and comparable efficiency against the tuning methods based on the state-of-the-art workload compression methods.

As multi-layer graphs can give a more accurate and reliable picture of the complex relationships between entities, cohesive subgraph mining, a fundamental task in graph analysis, has been studied on multi-layer graphs in the literature. However, existing cohesive subgraph models are designated for special multi-layer graphs such as multiplex networks and heterogeneous information networks. In this paper, we propose generalized core (gCore), a new notion of cohesive subgraph on general multi-layer graphs without any predefined constraints on the interconnections between vertices. The gCore model considers both the intra-layer and cross-layer cohesiveness of vertices. Three related problems are studied in this paper including gCore search (GCS), gCore decomposition (GCD), and gCore indexing (GCI). A polynomial-time algorithm based on the peeling paradigm is proposed to solve the GCS problem. By considering the containment among gCores, a "tree of trees" data structure called KP-tree is designed for efficiently solving the GCD problem and serving as a compact storage and index of all gCores. Several advanced lossless compaction techniques including node/subtree elimination, subtree transplant, and subtree merge are proposed to help reduce the storage overhead of the KP-tree and speed up the process of solving GCD and GCI. Besides, a KP-tree-based GCS algorithm is designed, which can retrieve any gCore in linear time in the size of the gCore and the height of the KP-tree. The experiments on 10 real-world graphs verify the effectiveness of the gCore model and the efficiency of the proposed algorithms.

In this paper, we study the problem of multi-source cross-network node classification, which aims to classify unlabeled nodes in a target network by leveraging the knowledge learned from the rich labeled nodes in multiple source networks. The existing multi-source transfer learning approaches generally fail to model the structural information of networks, and the current cross-network node classification models mainly neglect that not all source networks can boost the task performance in the target network. Thus, none can be directly applied to the multi-source cross-network node classification task. To this end, in this paper, we propose a novel multi-source data selection (MSDS) based framework for cross-network node classification, which integrates multi-source transfer learning with network embedding to learn label-discriminative and network-invariant node representations. In MSDS, we first propose the multi-source network data selection, which applies three distances to jointly select the transferable source networks to well alleviate the problem of suboptimal solution or even negative transfer. In addition, we devise a new feature information alignment technique to make node vector representations network-invariant. Moreover, we incorporate aggregated structural information and feature information to make node representations label-discriminative. Extensive experiments on real-world datasets demonstrate that the proposed approaches outperform the state-of-the-art non-transfer and single-source transfer approaches in terms of classification accuracy.

Durable subgraph matching on a temporal graph finds all subgraphs in the temporal graph that not only match the given query graph but also have duration longer than a user-specified duration threshold. The state-of-the-art algorithm (Semertzidis and Pitoura, 2016, 2019) for solving this problem requires lots of memory when the input temporal graph is large. In this paper, a new algorithm is proposed to solve this problem. Many effective techniques are developed to improve the performance of this algorithm, including the DFS-based query decomposition method, the TD-tree index structure, the sort-based vertex matching order, and the time instance set compaction method. The experimental results show that the proposed algorithm is an order of magnitude faster and requires significantly less memory than the state-of-the-art algorithm.

Centrality is a family of metrics for characterizing the importance of a vertex in a graph. Although a large number of centrality metrics have been proposed, a majority of them ignores uncertainty in graph data. In this article, we formulate closeness centrality on uncertain graphs and define the batch closeness centrality evaluation problem that computes the closeness centrality of a subset of vertices in an uncertain graph. We develop three algorithms, MS-BCC , MG-BCC, and MGMS-BCC , based on sampling to approximate the closeness centrality of the specified vertices. All these algorithms require to perform breadth-first searches (BFS) starting from the specified vertices on a large number of sampled possible worlds of the uncertain graph. To improve the efficiency of the algorithms, we exploit operation-level parallelism of the BFS traversals and simultaneously execute the shared sequences of operations in the breadth-first searches. Parallelization is realized at different levels in these algorithms. The experimental results show that the proposed algorithms can efficiently and accurately approximate the closeness centrality of the given vertices. MGMS-BCC is faster than both MS-BCC and MG-BCC because it avoids more repeated executions of the shared operation sequences in the BFS traversals.

Interactive graph search leverages human intelligence to categorize target labels in a hierarchy, which is useful for image classification, product categorization, and database search. However, many existing interactive graph search studies aim at identifying a single target optimally, and suffer from the limitations of asking too many questions and not being able to handle multiple targets. To address these two limitations, in this paper, we study a new problem of budget constrained interactive graph search for multiple targets called kBM-IGS problem. Specifically, given a set of multiple targets T in a hierarchy and two parameters k and b , the goal is to identify a k -sized set of selections S , such that the closeness between selections S and targets T is as small as possible, by asking at most a budget of b questions. We theoretically analyze the updating rules and design a penalty function to capture the closeness between selections and targets. To tackle the kBM-IGS problem, we develop a novel framework to ask questions using the best vertex with the largest expected gain, which provides a balanced trade-off between target probability and benefit gain. Based on the kBM-IGS framework, we first propose an efficient algorithm STBIS to handle the SingleTarget problem, which is a special case of kBM-IGS. Then, we propose a dynamic programming based method kBM-DP to tackle the MultipleTargets problem. To further improve efficiency, we propose two heuristic but efficient algorithms, kBM-Topk and kBM-DP+. Experiments on large real-world datasets with ground-truths verify both the effectiveness and efficiency of our algorithms.

Mining dense subgraphs on multi-layer graphs is an interesting problem, which has witnessed lots of applications in practice. To overcome the limitations of the quasi-clique-based approach, we propose d-coherent core (d-CC), a new notion of dense subgraph on multi-layer graphs, which has several elegant properties. We formalize the diversified coherent core search (DCCS) problem, which finds k d-CCs that can cover the largest number of vertices. We propose a greedy algorithm with an approximation ratio of 1 - 1/e and two search algorithms with an approximation ratio of 1/4. The experiments verify that the search algorithms are faster than the greedy algorithm and produce comparably good results as the greedy algorithm in practice. As opposed to the quasi-clique-based approach, our DCCS algorithms can fast detect larger dense subgraphs that cover most of the quasi-clique-based results.

Rectangle has been recognized as an essential motif in a large number of real-world networks. Counting rectangles in a network plays an important role in network analysis. This paper comprehensively studies the rectangle counting problem on large networks. We propose a novel counting paradigm called the wedge-centric counting, where a wedge is a simple path consisting of three vertices. Unlike the traditional edge-centric counting, the wedge-centric counting uses wedges instead of edges as building blocks of rectangles. The main advantage of the wedge-centric counting is that it does not need to access two-hop neighbors. Based on this paradigm, we develop a collection of rectangle counting algorithms, including an in-memory algorithm with lower time complexity, an external-memory algorithm with the optimal I/O complexity, and two randomized algorithms with provable error bounds. The experimental results on a variety of real networks verify the effectiveness and the efficiency of the proposed wedge-centric rectangle counting algorithms.

This paper studies a novel approach to processing massive uncertain graph data. In this approach, we propose a new framework to simultaneously process a query on a set of randomly sampled possible worlds of an uncertain graph. Based on this framework, we develop a series of algorithms to analyze massive uncertain graphs, including breadth-first search, shortest distance queries, triangle counting, and core decomposition. We implement this approach based on GraphLab, one of the stateof-the-art graph processing frameworks. By sharing fine-grained internal processing steps on common substructures of sampled possible worlds, the new approach achieves tens to hundreds of times speedup in execution time on a cluster of 20 servers.

SimRank is a similarity measure between vertices in a graph. Recently, many algorithms have been proposed to efficiently evaluate SimRank similarities. However, the existing algorithms either overlook uncertainty in graph structures or depends on an unreasonable assumption. In this paper, we study SimRank on uncertain graphs. Following the random-walk-based formulation of SimRank on deterministic graphs and the possible world model of uncertain graphs, we first define random walks on uncertain graphs and show that our definition of random walks satisfies Markov's property. We formulate our SimRank measure based on random walks on uncertain graphs. We discover a critical difference between random walks on uncertain graphs and random walks on deterministic graphs, which makes all existing SimRank computation algorithms on deterministic graphs inapplicable to uncertain graphs. For SimRank computation, we consider computing both single-pair SimRank and single-source top-K SimRank. We propose three algorithms, namely the sampling algorithm with high efficiency, the two-phase algorithm with comparable efficiency and higher accuracy, and a speeding-up algorithm with much higher efficiency. Meanwhile, we present an optimized algorithm for efficient computing the single-source top-K SimRank. The experimental results verify the effectiveness of our SimRank measure and the efficiency of the proposed SimRank computation algorithms.

SimRank is a similarity measure between vertices in a graph, which has become a fundamental technique in graph analytics. Recently, many algorithms have been proposed for efficient evaluation of SimRank similarities. However, the existing SimRank computation algorithms either overlook uncertainty in graph structures or is based on an unreasonable assumption (Du et al). In this paper, we study SimRank similarities on uncertain graphs based on the possible world model of uncertain graphs. Following the random-walk-based formulation of SimRank on deterministic graphs and the possible worlds model of uncertain graphs, we define random walks on uncertain graphs for the first time and show that our definition of random walks satisfies Markov's property. We formulate the SimRank measure based on random walks on uncertain graphs. We discover a critical difference between random walks on uncertain graphs and random walks on deterministic graphs, which makes all existing SimRank computation algorithms on deterministic graphs inapplicable to uncertain graphs. To efficiently compute SimRank similarities, we propose three algorithms, namely the baseline algorithm with high accuracy, the sampling algorithm with high efficiency, and the two-phase algorithm with comparable efficiency as the sampling algorithm and about an order of magnitude smaller relative error than the sampling algorithm. The extensive experiments and case studies verify the effectiveness of our SimRank measure and the efficiency of our SimRank computation algorithms.

Uncertain graphs have been widely used to represent graph data with inherent uncertainty in structures. Reliability search is a fundamental problem in uncertain graph analytics. This paper studies a new problem, the top-k reliability search problem on uncertain graphs, that is, finding k vertices v with the highest reliabilities of connections from a source vertex s to v. Note that the existing algorithm for the threshold-based reliability search problem is inefficient for the top-k reliability search problem. We propose a new algorithm to efficiently solve the top-k reliability search problem. The algorithm adopts two important techniques, namely the BFS sharing technique and the offline sampling technique. The BFS sharing technique exploits overlaps among different sampled possible worlds of the input uncertain graph and performs a single BFS on all possible worlds simultaneously. The offline sampling technique samples possible worlds offline and stored them using a compact structure. The algorithm also takes advantages of bit vectors and bitwise operations to improve efficiency. Moreover, we generalize the top-k reliability search problem to the multi-source case and show that the multi-source case of the problem can be equivalently converted to the single-source case of the problem. Extensive experiments carried out on both real and synthetic datasets verify that the optimized algorithm outperforms the baselines by 1 - 2 orders of magnitude in execution time while achieving comparable accuracy. Meanwhile, the optimized algorithm exhibits linear scalability with respect to the size of the input uncertain graph.

Structural-context similarities between vertices in graphs, such as the Jaccard similarity, the Dice similarity, and the cosine similarity, play important roles in a number of graph data analysis techniques. However, uncertainty is inherent in massive graph data, and therefore the classical definitions of structural-context similarities on exact graphs don't make sense on uncertain graphs. In this paper, we propose a generic definition of structural-context similarity for uncertain graphs. Since it is computationally prohibitive to compute the similarity between two vertices of an uncertain graph directly by its definition, we investigate two efficient approaches to computing similarities, namely the polynomial-time exact algorithms and the linear-time approximation algorithms. The experimental results on real uncertain graphs verify the effectiveness of the proposed structural-context similarities as well as the accuracy and efficiency of the proposed evaluation algorithms.

Existing studies on graph mining focus on exact graphs that are precise and complete. However, graph data tends to be uncertain in practice due to noise, incompleteness and inaccuracy. This paper investigates the problem of finding top-k maximal cliques in an uncertain graph. A new model of uncertain graphs is presented, and an intuitive measure is introduced to evaluate the significance of vertex sets. An optimized branch-and-bound algorithm is developed to find top-k maximal cliques, which adopts efficient pruning rules, a new searching strategy and effective preprocessing methods. The extensive experimental results show that the proposed algorithm is very efficient on real uncertain graphs, and the top-k maximal cliques are very useful for real applications, e.g. protein complex prediction.

Frequent subgraph mining has been extensively studied on certain graph data. However, uncertainties are inherently accompanied with graph data in practice, and there is very few work on mining uncertain graph data. This paper investigates frequent subgraph mining on uncertain graphs under probabilistic semantics. Specifically, a measure called φ-frequent probability is introduced to evaluate the degree of recurrence of subgraphs. Given a set of uncertain graphs and two numbers 0 < φ,τ < 1, the goal is to quickly find all subgraphs with φ-frequent probability at least τ. Due to the NP-hardness of the problem, an approximate mining algorithm is proposed for this problem. Let 0 < δ < 1 be a parameter. The algorithm guarantees to find any frequent subgraph S with probability at least (1 - δ/2)s, where s is the number of edges of S. In addition, it is thoroughly discussed how to set δ to guarantee the overall approximation quality of the algorithm. The extensive experiments on real uncertain graph data verify that the algorithm is efficient and that the mining results have very high quality.

In many real applications, graph data is subject to uncertainties due to incompleteness and imprecision of data. Mining such uncertain graph data is semantically different from and computationally more challenging than mining conventional exact graph data. This paper investigates the problem of mining uncertain graph data and especially focuses on mining frequent subgraph patterns on an uncertain graph database. A novel model of uncertain graphs is presented, and the frequent subgraph pattern mining problem is formalized by introducing a new measure, called expected support. This problem is proved to be NP-hard. An approximate mining algorithm is proposed to find a set of approximately frequent subgraph patterns by allowing an error tolerance on expected supports of discovered subgraph patterns. The algorithm uses efficient methods to determine whether a subgraph pattern can be output or not and a new pruning method to reduce the complexity of examining subgraph patterns. Analytical and experimental results show that the algorithm is very efficient, accurate, and scalable for large uncertain graph databases. To the best of our knowledge, this paper is the first one to investigate the problem of mining frequent subgraph patterns from uncertain graph data.

Graph data are subject to uncertainties in many applications due to incompleteness and imprecision of data. Mining uncertain graph data is semantically different from and computationally more challenging than mining exact graph data. This paper investigates the problem of mining frequent subgraph patterns from uncertain graph data. The frequent subgraph pattern mining problem is formalized by designing a new measure called expected support. An approximate mining algorithm is proposed to find an approximate set of frequent subgraph patterns by allowing an error tolerance on the expected supports of the discovered subgraph patterns. The algorithm uses an efficient approximation algorithm to determine whether a subgraph pattern can be output or not. The analytical and experimental results show that the algorithm is very efficient, accurate and scalable for large uncertain graph databases.

In recent years, large amount of data modeled by graphs, namely graph data, have been collected in various domains. Efficiently processing queries on graph databases has attracted a lot of research attentions. Supergraph query is a kind of new and important queries in practice. A supergraph query, q, on a graph database D is to retrieve all graphs in D such that q is a supergraph of them. Because the number of graphs in databases is large and subgraph isomorphism testing is NP-complete, efficiently processing such queries is a big challenge. This paper first proposes an optimal compact method for organizing graph databases. Common subgraphs of the graphs in a database are stored only once in the compact organization of the database, in order to reduce the overall cost of subgraph isomorphism testings from stored graphs to queries during query processing. Then, an exact algorithm and an approximate algorithm for generating significant feature set with optimal order are proposed to construct indices on graph databases. The optimal order on the feature set is to reduce the number of subgraph isomorphism testings during query processing. Based on the compact organization of graph databases, a novel algorithm of testing subgraph isomorphisms from multiple graphs to one graph is presented. Finally, based on all these techniques, a query processing method is proposed. Analytical and experimental results show that the proposed algorithms outperform the existing similar algorithms by one to two orders of magnitude. 1.