Search

Temporal graphs are graphs whose edges are associated with timestamps. Subgraph matching on temporal graphs retrieves temporal subgraphs whose edge timestamps satisfy user-specified temporal orders. In this paper, a temporal query pattern is composed of a query graph with an arbitrary structure and a partial order on the edge set of the query graph. Moreover, the time span between the minimum and the maximum edge timestamps in a matching is required to be less than or equal to a specified threshold. This paper proposes a temporal subgraph matching algorithm based on two key techniques. First, a memory-efficient index structure called TO-tree is designed to compactly store all necessary information required for finding all temporal subgraph matchings. The TO-tree constructed for a temporal query pattern is much smaller than the temporal graph because unnecessary information is mostly excluded from the TO-tree by three powerful filters. The second technique is a temporal subgraph matching enumeration method that runs on the TO-tree instead of on the temporal graph. This enumeration method expands temporal subgraph matchings in an edge-by-edge manner. Since the TO-tree can fit into the main memory, the enumeration method runs very fast on the TO-tree. An extensive experimental evaluation has been carried out. The experimental results show that the TO-tree index structure is memory-efficient, which in turn enables a fast temporal subgraph matching enumeration. Overall, our algorithm is at least 3X faster than the baseline algorithm adapted from the state-of-the-art non-temporal subgraph matching algorithm CECI and is at least 4X faster than the temporal subgraph matching algorithm HASSE .

When characterizing the cohesion of a subgraph, many cohesive subgraph models impose various constraints on the relationship between the minimum degree of vertices and the number of vertices in the subgraph. However, the constraints imposed by the clique, quasi-clique and k-core models are so rigid that they cannot simultaneously characterize cohesive subgraphs of various scales in a graph. This paper characterizes the flexibility of a cohesive subgraph model by the constraint it imposes on this relationship and proposes f -constraint core (f -CC), a new model that can flexibly characterize cohesive subgraphs of different scales. We formalize the FlexCS problem that finds r representative f -CCs in a graph that are most diversified. This problem is NP-hard and is even NP-hard to be approximated within |V |1−𝜖 for any 𝜖 > 0. To solve the problem efficiently, a divide-and-conquer algorithm is proposed together with some effective techniques including f -CC generation, sub-problem filtering, early termination, and index-based connected component retrieval. Extensive experiments verify the flexibility of the f -CC model and the effectiveness of the proposed algorithm.

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 kd-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. Furthermore, we propose some optimization techniques to further speed up the algorithms. 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.

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.

Making massive graph data easily understandable by people is a demanding task in a variety of real applications. Graph compression is an effective approach to reducing the size of graph data as well as its complexity in structures. This paper proposes a simple yet effective graph compression method called the star-based graph compression. This method compresses a graph by shrinking a collection of disjoint subgraphs called stars. Compressing a graph into the optimal star-based compressed graph with the highest compression ratio is shown to be NP-complete. We propose a greedy compression algorithm called StarZip. We experimentally verify that StarZip achieves compression ratios of 3.8–45.7 and 2.9–241.6 in terms of vertex count and edge count, respectively. Besides, we study the shortest path queries on compressed graphs. On the real graphs, the StarSSSP algorithm for processing shortest path queries on compressed graphs is 4X–20X faster than Dijkstra’s algorithm running on original graphs. The average absolute error between the query results of StarSSSP and the exact shortest distances is about 1. On the synthetic graphs, StarSSSP is up to 313X faster than Dijkstra’s algorithm, and the average absolute error is also about 1.

The k-truss of a graph is the largest edge-induced subgraph such that every edge is contained in at least k triangles within the subgraph, where a triangle is a cycle consisting of three vertices. As a new notion of cohesive subgraphs, truss has recently attracted a lot of research attentions in the database and data mining fields. At the same time, uncertainty is an intrinsic property of massive graph data, and truss decomposition (i.e., finding all k-trusses of a graph) has become a key primitive on uncertain graphs. In this paper, we study the truss decomposition problem on uncertain graphs, that is, finding all highly probable k-trusses of an uncertain graph. We first give an formal statement of the truss decomposition problem on uncertain graphs. Then, we prove that the truss decomposition of an uncertain graph attains two elegant properties, namely uniqueness and hierarchy. We show that the truss decomposition of an uncertain graph can be found in $$O(m^{1.5}Q)$$O(m1.5Q) time by proposing an in-memory algorithm called $$\mathtt {TD_{mem}}$$TDmem, where m is the number of edges of the uncertain graph, and Q is at most the maximum number of common neighbors of the endpoints of an edge. When an uncertain graph is too large to fit into main memory, we propose an external-memory algorithm $$\mathtt {TD_{I/O}}$$TDI/O to find the truss decomposition of the uncertain graph. Extensive experiments have been carried out to evaluate the practical performance of the proposed algorithms. The experimental results verify that both $$\mathtt {TD_{mem}}$$TDmem and $$\mathtt {TD_{I/O}}$$TDI/O are efficient when an uncertain graph is small enough to fit into main memory, and that $$\mathtt {TD_{I/O}}$$TDI/O is much faster than $$\mathtt {TD_{mem}}$$TDmem when the graph is too large to fit into main memory.

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., Comment: Full Version, 17 Pages

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., 14 pages, under review by ICDE'16

Uncertain graph data has been collected, processed and analyzed in a wide range of applications. Under the possible world model, an uncertain graph represents a probability distribution over all its possible worlds. Each possible world is a deterministic graph in which the uncertain graph may be present in practice. To deal with the hardness of computations on uncertain graphs, Parchas et al. first proposed the concept of a degree-based representative possible world. This approach is distinguished from the sampling approach in that it computes on one representative possible world instead of on a large number of possible worlds sampled at random. However, the degree-based representative possible world only tries to preserve vertex degrees. In this paper, we are motivated by the fact that motif structures such as triangles can affect the structural properties of graphs and propose the concept of a triangle-based representative possible world. We also develop an algorithm for finding the triangle-based representative possible world of an uncertain graph. We conducted extensive experimental evaluations and show that the triangle-based representative possible world outperforms the degree-based representative possible world in preserving the structural characteristics of an uncertain graph in expectation.

Frequent subgraph mining has been extensively studied on certain graph data. However, uncertainty is intrinsic in graph data in practice, but there is very few work on mining uncertain graph data. This paper focuses on mining frequent subgraphs over uncertain graph data under the probabilistic semantics. Specifically, a measure called $${\varphi}$$ -frequent probability is introduced to evaluate the degree of recurrence of subgraphs. Given a set of uncertain graphs and two real numbers $${0 < \varphi, \tau < 1}$$ , the goal is to quickly find all subgraphs with $${\varphi}$$ -frequent probability at least ?. Due to the NP-hardness of the problem and to the #P-hardness of computing the $${\varphi}$$ -frequent probability of a subgraph, an approximate mining algorithm is proposed to produce an $${(\varepsilon, \delta)}$$ -approximate set ? of "frequent subgraphs", where $${0 < \varepsilon < \tau}$$ is error tolerance, and 0 < ? < 1 is a confidence bound. The algorithm guarantees that (1) any frequent subgraph S is contained in ? with probability at least ((1 ? ?) /2) s , where s is the number of edges in S; (2) any infrequent subgraph with $${\varphi}$$ -frequent probability less than $${\tau - \varepsilon}$$ is contained in ? with probability at most ?/2. The theoretical analysis shows that to obtain any frequent subgraph with probability at least 1 ? Δ, the input parameter ? of the algorithm must be set to at most $${1 - 2 (1 - \Delta)^{1 / \ell_{\max}}}$$ , where 0 < Δ < 1, and ? max is the maximum number of edges in frequent subgraphs. Extensive experiments on real uncertain graph data verify that the proposed algorithm is practically efficient and has very high approximation quality. Moreover, the difference between the probabilistic semantics and the expected semantics on mining frequent subgraphs over uncertain graph data has been discussed in this paper for the first time.

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.

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

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.

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 outper-form the existing similar algorithms by one to two orders of magnitude.