检索结果-内蒙古大学图书馆

6th International Conference on Innovation in Artificial Intelligence (ICIAI)

作者： Pan, Zeting Chang, Junsheng Natl Univ Def Technol Coll Comp Changsha Peoples R China

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

关键词： graph inference graph Neural Networks distributed graph computing

来源：评论

学校读者我要写书评

暂无评论

Hybrid Pulling/Pushing for I/O-Efficient distributed and Iterative graph computing 16

Hybrid Pulling/Pushing for I/O-Efficient Distributed and Ite...

引用

ACM SIGMOD International Conference on Management of Data

作者： Wang, Zhigang Gu, Yu Bao, Yubin Yu, Ge Yu, Jeffrey Xu Northeastern Univ Shenyang Liaoning Peoples R China Chinese Univ Hong Kong Hong Kong Hong Kong Peoples R China

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.

关键词： I/O-Efficient distributed graph computing Push Pull

来源：评论

学校读者我要写书评

暂无评论

PECC: parallel expansion based on clustering coefficient for efficient graph partitioning

引用

distributed AND PARALLEL DATABASES 2024年第4期42卷 447-467页

作者： Shi, Chengcheng Xie, Zhenping Jiangnan 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 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.

关键词： graph partitioning distributed graph computing Clustering coefficient distributed lock

来源：评论

学校读者我要写书评

暂无评论

Taking Heuristic Based graph Edge Partitioning One Step Ahead via OffStream Partitioning Approach 37

Taking Heuristic Based Graph Edge Partitioning One Step Ahea...

引用

37th IEEE International Conference on Data Engineering (IEEE ICDE)

作者： Ayall, Tewodros Duan, Hancong Liu, Changhong Gereme, Fantahun Abegaz, Mohammed Deleli, Mesay Sch Comp Sci & Engn Chengdu Peoples R China Univ Elect Sci & Technol China Chengdu Peoples R China

ISBN: (纸本)9781728191843

In the modern era of big data, large-scale graph computing has become challenging because of the dramatic rise in graph data size. graph edge partitioning (GEP) is a crucial preprocessing step to distributed graph 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.

关键词： distributed graph computing Edge partitioning Hybrid edge partitioning Offline approach OffStream approach Stateful partition state and Stream approach

来源：评论

学校读者我要写书评

暂无评论

distributed aggregation-based attributed graph summarization for summary-based approximate attributed graph queries

引用

EXPERT SYSTEMS WITH APPLICATIONS 2021年 176卷 114921-114921页

作者： Yang, Shang Yang, Zhipeng Chen, Xiaona Zhao, Jingpeng Ma, Yinglong North China Elect Power Univ Sch Control & Comp Engn Beijing 102206 Peoples R China

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.

关键词： graph summarization Attributed graph distributed graph computing graph aggregation graph query

来源：评论

学校读者我要写书评

暂无评论

Local graph Edge Partitioning

引用

ACM TRANSACTIONS ON INTELLIGENT SYSTEMS AND TECHNOLOGY 2021年第5期12卷 61-61页

作者： Ji, Shengwei Bu, Chenyang Li, Lei Wu, Xindong Iefei Univ Technol Key Lab Knowledge Engn Big Data Minist Educ China Hefei Peoples R China Hefei Univ Technol Sch Comp Sci & Informat Engn Hefei Peoples R China Hefei Univ Technol Inst Big Knowledge Sci 420 Fei Cui Rd Hefei Anhui Peoples R China Mininglamp Technol Mininglamp Acad Sci 420 Fei Cui Rd Hefei Anhui Peoples R China

graph edge partitioning, which is essential for the efficiency of distributed graph 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.

关键词： Local information graph edge partitioning distributed graph computing

来源：评论

学校读者我要写书评

暂无评论

DETER: Streaming graph Partitioning via Combined Degree and Cluster Information 19th

DETER: Streaming Graph Partitioning via Combined Degree and ...

引用

19th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP)

作者： Hu, Cong Zhong, Jiang Li, Qi Li, Qing Chongqing Univ Chongqing 400044 Peoples R China Chongqing Univ Key Lab Dependable Serv Comp Cyber Phys Soc Chongqing 400044 Peoples R China

ISBN: (纸本)9783030389918;9783030389901

Efficient graph partitioning plays an important role in distributed graph 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.

关键词： graph partitioning Vertex-cut Streaming distributed graph computing

来源：评论

学校读者我要写书评

暂无评论

OffStreamNG: Partial Stream Hybrid graph Edge Partitioning Based on Neighborhood Expansion and Greedy Heuristic 1

引用

24th East-European Conference on Advances in Databases and Information Systems/24th International Conference on Theory and Practice of Digital Libraries/16th Workshop on Business Intelligence and Big Data (ADBIS/TPDL/EDA)

作者： Ayalew, Tewodros Duan, Hancong Liu, Changhong Gereme, Fantahun Delele, Mesay Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China Univ Elect Sci & Technol China Inst Fundamental & Frontier Sci Chengdu Peoples R China Univ Elect Sci & Technol China Sch Informat Sci & Engn Chengdu Peoples R China

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.

关键词： Edge partitioning Stream approach Offline approach distributed graph computing Hybrid edge partitioning Saved partition state

来源：评论

学校读者我要写书评

暂无评论

Local graph Edge Partitioning with a Two-Stage Heuristic Method 39

Local Graph Edge Partitioning with a Two-Stage Heuristic Met...

引用

39th IEEE International Conference on distributed computing Systems (ICDCS)

作者： Ji, Shengwei Bu, Chenyang Li, Lei Wu, Xindong Hefei Univ Technol Sch Comp Sci & Informat Engn Hefei Peoples R China Hefei Univ Technol Key Lab Knowledge Engn Big Data Minist Educ Hefei Peoples R China Hefei Univ Technol Inst Big Knowledge Sci Hefei Peoples R China Mininglamp Acad Sci Mininglamp Technol Beijing Peoples R China

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

关键词： graph edge partitioning distributed graph computing Local information

来源：评论

学校读者我要写书评

暂无评论

Finding Mutual X at WeChat-Scale Social Network in Ten Minitues

Finding Mutual X at WeChat-Scale Social Network in Ten Minit...

引用

IEEE International Conference on Big Data (Big Data)

作者： He, Conghui Sun, Shijie Li, Benli Tu, Xiaogang Yu, Donghai Tencent Inc Shenzhen Guangdong Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Guangdong Peoples R China

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.

关键词： distributed graph computing High Performance computing Big Data

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：