Querying graphs and conducting graph analytics become important in data processing since many real applications are dealing with massive graphs, such as online social networks, Semantic Web, knowledge graphs, etc. Over the years, many distributed graph processing systems have been developed to support graph analytics using various programming models, and many graph querying languages have been proposed. A natural question that arises is how to integrate graph data and traditional non-graph data in a distributed system for users to conduct analytics. There are two issues. One issue is related to expressiveness on how to specify graph analytics as well as data analytics by a querying language. The other issue is related to efficiency on how to process analytics in a distributed system. For the first issue, SQL is a best candidate, since SQL is a well-accepted language for data processing. We concentrate on SQL for graph analytics. Our early work shows that graph analytics can be supported by SQL in a way from “semiring + while” to “relational algebra + while” via the enhanced recursive SQL queries. In this article, we focus on the second issue on how to process such enhanced recursive SQL queries based on the GAS (Gather-Apply-Scatter) model under which efficient graph processing systems can be developed. To demonstrate the efficiency, we implemented a system by tightly coupling Spark SQL and GraphX on Spark which is one of the most popular in-memory data-flow processing platforms. First, we enhance Spark SQL by adding the capability of supporting the enhanced recursive SQL queries for graph analytics. In this regard, graph analytics can be processed using a distributed SQL engine alone. Second, we further propose new transformation rules to optimize/translate the operations for recursive SQL queries to the operations by GraphX. In this regard, graph analytics by SQL can be processed in a similar way as done by a distributed graph processing system using the APIs provided by the system. We conduct extensive performance studies to test graph analytics using large real graphs. We show that our approach can achieve similar or even higher efficiency, in comparison to the built-in graph algorithms in the existing graph processing systems.

In this paper we use a time-evolving graph which consists of a sequence of graph snapshots over time to model many real-world networks. We study the path classification problem in a time-evolving graph, which has many applications in real-world scenarios, for example, predicting path failure in a telecommunication network and predicting path congestion in a traffic network in the near future. In order to capture the temporal dependency and graph structure dynamics, we design a novel deep neural network named Long Short-Term Memory R-GCN (LRGCN). LRGCN considers temporal dependency between time-adjacent graph snapshots as a special relation with memory, and uses relational GCN to jointly process both intra-time and inter-time relations. We also propose a new path representation method named self-attentive path embedding (SAPE), to embed paths of arbitrary length into fixed-length vectors. Through experiments on a real-world telecommunication network and a traffic network in California, we demonstrate the superiority of LRGCN to other competing methods in path failure prediction, and prove the effectiveness of SAPE on path representation.

Community search is a fundamental graph mining task. Unfortunately, most previous community search studies focus mainly on identifying communities in a network without temporal information. In this paper, we study the problem of finding persistent communities in a temporal network, in which every edge is associated with a timestamp. Our goal is to identify the communities that are persistent over time. To this end, we propose a novel persistent community model called (θ,τ) community. We prove that the problem of identifying the maximum (θ,τ) persistent k-core is NP-hard. To solve this problem, we propose a novel branch and bound algorithm with several carefully-designed pruning rules to find the maximum (θ,τ)-persistent. We conduct k-cores efficiently. We conduct extensive experiments in several real-world temporal networks. The results demonstrate the efficiency, scalability, and effectiveness of the proposed solutions.

As an important graph operator, reachability query has been extensively studied over decades, which is to check whether a vertex can reach another vertex over a large directed graph G with n vertices and m edges. The efforts made in the reported studies have greatly improved the query time of answering reachability queries online, while reducing the offline index construction time to construct an index with a reasonable size given the approach taken, where an entry in an index for a vertex is called a label of the vertex. Among all the work, the recent development of IP (Independent Permutation) employs randomness using k-min-wise independent permutations to process reachability queries, and shows the advantages for both query time and index construction time. In this paper, we propose a new Bloom filter Labeling, denoted as BFL. We show that the probability to answer reachability queries by BFL can be bounded, and BFL has high pruning power to answer more reachability queries directly. We give algorithms and analyze the pruning power of BFL. We conduct extensive studies using 19 large datasets. We show that BFL with an interval label performs best in the index construction time for all 19 cases, and performs best in query time for 16 out of 19 cases.