*A graph is a structure that can express the relationship between objects. The emergence of GNN enables deep learning to be applied in the field of graphs. However, most GNNs are trained offline and cannot be directly...
详细信息
ISBN:
(纸本)9781450395502
*A graph is a structure that can express the relationship between objects. The emergence of GNN enables deep learning to be applied in the field of graphs. However, most GNNs are trained offline and cannot be directly used in real-time monitoring scenarios such as financial risk control. In addition, due to the large scale of graph data, a single machine often cannot meet actual needs, and there are bottlenecks such as throughput performance. Therefore, we propose a distributedgraph inference computing framework, which can be applied to Encoder-Decoder GNN models. We complete the adaptation of the model by disassembling the graph data and using the extension storage and dynamic invocation mechanism to solve the model invocation problem. For inference performance, we implement dynamic graph construction through incremental composition and decouple the inference process to apply to different scenarios, so that GNNs conforming to the Encoder-Decoder style can be applied to the framework. A large number of experiments show that this method has good timeliness while improving the throughput upper limit, and can maintain the model effect of multi-tasking.
Billion-node graphs are rapidly growing in size in many applications such as online social networks. Most graph algorithms generate a large number of messages during iterative computations. Vertex-centric distributed ...
详细信息
ISBN:
(纸本)9781450335317
Billion-node graphs are rapidly growing in size in many applications such as online social networks. Most graph algorithms generate a large number of messages during iterative computations. Vertex-centric distributed systems usually store graph data and message data on disk to improve scalability. Currently, these distributed systems with disk-resident data take a push-based approach to handle messages. This works well if few messages reside on disk. Otherwise, it is I/O-inefficient due to expensive random writes. By contrast, the existing memory-resident pull-based approach individually pulls messages for each vertex on demand. Although it can be used to avoid disk operations regarding messages, expensive I/O costs are incurred by random and frequent access to vertices. This paper proposes a hybrid solution to support switching between push and pull adaptively, to obtain optimal performance for distributed systems with disk-resident data in different scenarios. We first employ a new block-centric technique (b-pull) to improve the I/O-performance of pulling messages, although the iterative computation is vertex-centric. I/O costs of data accesses are shifted from the receiver side where messages are written/read by push to the sender side where graph data are read by b-pull. graph data are organized by clustering vertices and edges to achieve high I/O efficiency in b-pull. Second, we design a seamless switching mechanism and a prominent performance prediction method to guarantee efficiency when switching between push and b-pull. We conduct extensive performance studies to confirm the effectiveness of our proposals over existing up-to-date solutions using a broad spectrum of real-world graphs.
作者：
Shi, ChengchengXie, ZhenpingJiangnan Univ
Sch Artificial Intelligence & Comp Sci Wuxi 214122 Jiangsu Peoples R China Jiangnan Univ
Jiangsu Key Univ Lab Software & Media Technol Huma Wuxi 214122 Jiangsu Peoples R China
In the pursuit of graph processing performance, graph partitioning, as a crucial preprocessing step, has been widely concerned. Based on an in-depth analysis of Neighbor Expansion (NE) graph partitioning algorithm, we...
详细信息
In the pursuit of graph processing performance, graph partitioning, as a crucial preprocessing step, has been widely concerned. Based on an in-depth analysis of Neighbor Expansion (NE) graph partitioning algorithm, we propose Parallel Expansion based on Clustering Coefficient (PECC). Firstly, to address the partition disturbance caused by internal structural changes during the process of vertex neighborhood expansion in the traditional NE algorithm, we perform a formal redefinition of the vertex state during the partitioning process and introduce the concept of clustering coefficient. Then, PECC uses the clustering coefficient as a metric to measure the closeness between vertices and potential partitions. Based on this metric, a novel parallel partitioning strategy in the distributed environment is proposed. This strategy consists of two core steps: the expansion process and the allocation process. Through two steps, PECC can effectively improve the operating efficiency of programs and significantly reduce the partitioning time. In addition, to ensure data consistency during parallel expansion, we adopt a distributed locking engine to solve concurrency management problems. Our evaluations on large real-world graphs show that in many cases, PECC achieves a balance between partitioning quality and computational efficiency. Finally, we show that PECC integrated on graphX outperforms the built-in native algorithms.
In the modern era of big data, large-scale graphcomputing has become challenging because of the dramatic rise in graph data size. graph edge partitioning (GEP) is a crucial preprocessing step to distributedgraph pla...
详细信息
ISBN:
(纸本)9781728191843
In the modern era of big data, large-scale graphcomputing has become challenging because of the dramatic rise in graph data size. graph edge partitioning (GEP) is a crucial preprocessing step to distributedgraph platforms, yet it is challenging to partition the large-scale graphs. GEP has shown better partition quality than the graph vertex partitioning for the graph's skewed degree distribution. Existing GEP approaches are classified into two as stream and offline. The former category assigns edges to the partitions based on the previously received edge information. It has less partitioning quality and is affected by stream order compared to the latter while supporting big graph partitioning. The latter uses complete knowledge of a graph during partitioning and hence has a better partitioning quality than the former;however, it does not support large-scale graphs. In this study, we propose a novel OffStream partitioning approach (OSPA) and hybrid graph edge partitioner OffStreamNH. OSPA leverages both the offline and stream graph partitioning approaches through stateful partitioning by introducing a state layer. This stateful partition state is recorded while offline is partitioning its input graph. It contains partial knowledge of previously partitioned data and is used by the stream partitioner. The OffStreamNH uses Neighborhood Expansion (NE) and Higher Degree Replicated First (HDRF) algorithms for the offline and online;respectively, with minor modifications of both algorithms. Experimental results show that OffStreamNH outperforms the state of the art stream partitioners in terms of replication factor, load balance and tolerates the effect of stream orders.
graph edge partitioning, which is essential for the efficiency of distributedgraph computation systems, divides a graph into several balanced partitions within a given size to minimize the number of vertices to be cu...
详细信息
graph edge partitioning, which is essential for the efficiency of distributedgraph computation systems, divides a graph into several balanced partitions within a given size to minimize the number of vertices to be cut. Existing graph partitioning models can be classified into two categories: offline and streaming graph partitioning models. The former requires global graph information during the partitioning, which is expensive in terms of time and memory for large-scale graphs. The latter creates partitions based solely on the received graph information. However, the streaming model may result in a lower partitioning quality compared with the offline model. Therefore, this study introduces a Local graph Edge Partitioning model, which considers only the local information (i.e., a portion of a graph instead of the entire graph) during the partitioning. Considering only the local graph information is meaningful because acquiring complete information for large-scale graphs is expensive. Based on the Local graph Edge Partitioning model, two local graph edge partitioning algorithms Two-stage Local Partitioning and Adaptive Local Partitioning are given. Experimental results obtained on 14 real-world graphs demonstrate that the proposed algorithms outperform rival algorithms in most tested cases. Furthermore, the proposed algorithms are proven to significantly improve the efficiency of the real graph computation system graphX.
With the drastically increasing size of graph data with more diversified and complex structures, it becomes more challenging to summarize and query large attributed graph data. In this paper, we propose a holistic app...
详细信息
With the drastically increasing size of graph data with more diversified and complex structures, it becomes more challenging to summarize and query large attributed graph data. In this paper, we propose a holistic approach for distributed aggregation-based attributed graph summarization for large-scale approximate attributed graph queries, which incorporates node attributes and relationships into topological structure for generating semantic understandable graph summary in a bottom-up way. First, we propose a holistic strategy of node aggregation to calculate the topological and attributed error increments of merging node pairs. Second, we propose a three-stage distributed implementation framework, where a novel heuristic measure for efficient parallelization is presented to reduce computation and communication costs across multiple machines. Third, a summary-based approximate graph query approach is introduced to accelerate graph query while maintaining high query accuracy. At last, extensive experiments were made over three real-world and synthetic attributed graphs. The results show that our approach has competitive performance in maintaining low error increment and computational costs in comparison with the state-of-the-art aggregation-based graph summarization approach, and that our summarybased approximate graph query can accelerate graph query while maintaining high query accuracy.
Efficient graph partitioning plays an important role in distributedgraph processing systems with the rapid growth of the scale of graph data. The quality of partitioning affects the performance of systems greatly. Ho...
详细信息
ISBN:
(纸本)9783030389918;9783030389901
Efficient graph partitioning plays an important role in distributedgraph processing systems with the rapid growth of the scale of graph data. The quality of partitioning affects the performance of systems greatly. However, most existing vertex-cut graph partitioning algorithms only focused on degree information and ignored the cluster information of a coming edge when assigning edges. It is beneficial to assign an edge to a partition with more neighbors because keeping a dense subgraph in one partition would reduce the communication cost. In this paper, we propose DETER, an efficient vertex-cut streaming graph partitioning algorithm that takes both degree and cluster information into account when assigning an edge to one partition. Our evaluations suggest that DETER algorithm owns the ability to efficiently partition large graphs and reduce communication cost significantly compared to state-of-the-art graph partitioning algorithms.
Recently, graph edge partitioning has shown better partitioning quality than the vertex graph partitioning for the skewed degree distribution of real-world graph data. graph edge partitioning can be classified as stre...
详细信息
ISBN:
(数字)9783030546236
ISBN:
(纸本)9783030546229;9783030546236
Recently, graph edge partitioning has shown better partitioning quality than the vertex graph partitioning for the skewed degree distribution of real-world graph data. graph edge partitioning can be classified as stream and offline. The stream edge partitioning approach supports a big graph partitioning;however, it has lower partitioning quality, is affected by stream order, and it has taken much time to make partitioning compared with the offline edge partitioning. Conversely, the offline edge partitioning approach has better partitioning quality than stream edge partitioning;however, it does not support big graph partitioning. In this study, we propose partial stream hybrid graph edge partitioning OffStreamNG, which leverages the advantage of both offline and stream edge partitioning approaches by interconnecting via saved partition state layer. The OffStreamNG holds vertex and load states as partition state, while the offline component is partitioning using neighborhood expansion heuristic. And it is transferring this partition state to the online component of Greedy heuristic with minor modification of both algorithms. Experimental results show that OffStreamNG achieves attractive results in terms of replication factor, load balance, and total partitioning time.
graph edge partitioning divides the edges of an input graph into multiple balanced partitions of a given size to minimize the sum of vertices that are cut, which is critical to the performance of distributedgraph com...
详细信息
ISBN:
(纸本)9781728125190
graph edge partitioning divides the edges of an input graph into multiple balanced partitions of a given size to minimize the sum of vertices that are cut, which is critical to the performance of distributedgraph computation platforms. Existing graph partitioning methods can be classified into two categories: offline graph partitioning and streaming graph partitioning. The first category requires global information for a graph during the partitioning, which is expensive in terms of time and memory for large-scale graphs. The second category, however, creates partitions solely based on the received edge information, which may result in lower performance than the offline methods. Therefore, in this study, the concept of local graph partitioning is introduced from local community detection to consider only local information, i.e., a part of the graph, instead of the graph as a whole, during the partitioning. The characteristic of storing only local information is important because real-world graphs are often large in scale, or they increase incrementally. Based on this idea, we propose a two-stage local partitioning algorithm, where the partitioning process is divided into two stages according to the structural changes of the current partition, and two different strategies are introduced to deal with the respective stages. Experimental results with real-world graphs demonstrate that the proposed algorithm outperforms the rival algorithms in most cases, including the state-of-the-art algorithm METIS.
The problem of finding mutual X is essential in mining and analysis of complex social networks. X can be user's public data such as friends, education information, etc. However, massive social networks pose a sign...
详细信息
ISBN:
(纸本)9781728108582
The problem of finding mutual X is essential in mining and analysis of complex social networks. X can be user's public data such as friends, education information, etc. However, massive social networks pose a significant challenge at this problem as these networks consist of billions of nodes and hundreds of billions of edges. This paper presents a high-performance and memory-efficient solution for finding mutual X in social networks with billions of users, with three main contributions. First, a distributed algorithm for finding mutual X;second, an intra-node optimization strategy including pipelined workflow, NUMA-aware sub-partitioning, and Dual Sliding Window set intersection algorithm based on SIMD;third, a semicircular computing and communication scheme to further improve internode performance and avoid load imbalance. Our design is well validated using multiple real-world datasets, and it takes less than 10 minutes to find all mutual X in the WeChat social network. Compared with existing industrial solutions based on graphX, we achieve 22-36x speedup and 36x memory reduction. Compared with Powergraph, our solution achieves 12.7x speedup and 11 x memory reduction.
暂无评论