Counting triangles is an important topic in many practical applications, such as anomaly detection, community search, and recommendation systems. For triangle counting in large and dynamic graphs, recent work has focused on distributed streaming algorithms. These works assume that the graph is processed in the same location, while in reality, the graph stream may be generated and processed in datacenters that are geographically distributed. This raises new challenges to existing triangle counting algorithms, due to the multi-level heterogeneities in network bandwidth and communication prices in geo-distributed datacenters. In this article, we propose a cost-aware framework named${\sf GeoTri}$based on the Master-Worker-Aggregator architecture, which takes both the cost and performance objectives into consideration for triangle counting in geo-distributed datacenters. The two core parts of this framework are the cost-aware nodes assignment strategy in master, which is critical to obtain node's position and distribute edges reasonably to reduce the cost (i.e., time cost and monetary cost), and cost-aware neighbor transfer strategy among workers, which further eliminates redundancy in data transfers. Additionally, we conduct extensive experiments on seven real-world graphs, and the results demonstrate that${\sf GeoTri}$significantly lowers both runtime and monetary cost while exhibiting nice accuracy and scalability.

In this paper, we propose neural-symbolic graph databases (NSGDs) that extends traditional graph data with content and structural embeddings in every node. The content embeddings can represent unstructured data (e.g., images, videos, and texts), while structural embeddings can be used to deal with incomplete graphs. We can advocate machine learning models (e.g., deep learning) to transform unstructured data and graph nodes to these embeddings. NSGDs can support a wide range of applications (e.g., online recommendation and natural language question answering) in social-media networks, multi-modal knowledge graphs and etc. As a typical search over graphs, we study subgraph search over a large NSGD, called neural-symbolic subgraph matching (NSMatch) that includes a novel ranking search function. Specifically, we develop a general algorithmic framework to process NSMatch efficiently. Using real-life multi-modal graphs, we experimentally verify the effectiveness, scalability and efficiency of NSMatch.

When the target magnetic structures have clear interfaces and significant petrophysical contrasts to the surrounding strata, the focusing (or sharp-boundary) inversion methods are preferred over the smooth inversion methods. The result of focusing inversions depends on the types of the focusing model constraint (stabilizer). In this study, we propose an adjustable exponential minimum support (AEMS) stabilizer, which is an extension of the previously introduced exponential minimum support (EMS) stabilizer. AEMS is similar to EMS, but it includes an adjustable focusing scheme to control the sharpness of the resulting structure. Using synthetic models, we compared the inversion results obtained with the AEMS method to those obtained by smoothing stabilizers and other focusing stabilizers. AEMS inversion results have a more accurate physical-property distribution and are closer to the true models, indicating an improved model recovery from the other inversion methods. The improvement is mainly attributed to the adjustable scheme of the focusing parameter in the AEMS method. Then, we inverted a field dataset using the AEMS inversion method to obtain a new reference model for copper-gold porphyry deposit detection and interpretation.

Subgraph matching over graphs has been extensive-ly studied, due to its wide applications in knowledge bases, social networks, and among others. To catch the inconsistency and errors that commonly exist in these graphs, this paper studies consistent subgraph matching (CSM), i.e., finding the common matches in every consistent graph repair w.r.t a set of conditional graph dependencies (CGDs). We concentrate on subset, superset and symmetric difference graph repairs. We study fundamental problems for CGDs and CSM. We show that the satisfiability, im-plication, and validation problems of CGDs are coNP-complete, coNP-complete and NP-complete, respectively. We also show that the CSM problem (under any kind of repair) is NP-complete. We provide (parallel) algorithms to solve CSM, and guarantee to reduce running time when given more processors. Using real-life and synthetic graphs, we empirically verify the efficiency and effectiveness of our algorithms.

Many real-life applications require processing graph data across heterogeneous sources. In this paper, we define the graph federation that indicates that the graph data sources are temporarily federated and offer their data for users. Next, we propose a new framework FedGraph to efficiently and effectively perform subgraph matching, which is a crucial application in graph federation. FedGraph consists of three phases, including query decomposition, distributed matching, and distributed joining. We also develop new efficient approximation algorithms and apply them in each phase to attack the NP-hard problem. The evaluations are conducted in a real test bed using both real-life and synthetic graph datasets. FedGraph outperforms the state-of-the-art methods, reducing the execution time and communication cost by 37.3 × and 61.8 ×, respectively.

Graph queries have emerged as one of the fundamental techniques to support modern search services, such as PageRank web search, social networking search and knowledge graph search. As such graphs are maintained globally and very huge (e.g., billions of nodes), we need to efficiently process graph queries across multiple geographically distributed datacenters, running geo-distributed graph queries. Existing graph computing frameworks may not work well for geographically distributed datacenters, because they implement a Bulk Synchronous Parallel model that requires excessive inter-datacenter transfers, thereby introducing extremely large latency for query processing. In this paper, we propose GeoGraph --a universal framework to support efficient geo-distributed graph query processing based on clustering datacenters and meta-graph, while reducing the inter-datacenter communication. Our new framework can be applied to many types of graph algorithms without any modification. The framework is developed on the top of Apache Giraph. The experiments were conducted by applying four important graph queries, i.e., shortest path, graph keyword search, subgraph isomorphism and PageRank. The evaluation results show that our proposed framework can achieve up to 82% faster convergence, 42% lower WAN bandwidth usage, and 45% less total monetary cost for the four graph queries, with input graphs stored across ten geo-distributed datacenters.