Enhancing Balanced Graph Edge Partition with Effective Local Search
Authors: Zhenyu Guo, Mingyu Xiao, Yi Zhou, Dongxiang Zhang, Kian-Lee Tan12336-12343
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To evaluate the performance of our algorithms, we first provide adequate theoretical analysis in terms of the approximation quality. We significantly improve the previously known approximation ratio for this problem. Then we conduct extensive experiments on a large number of benchmark datasets and stateof-the-art edge partition strategies. The results show that our proposed local search framework can further improve the quality of graph partition by a wide margin. |
| Researcher Affiliation | Academia | 1 University of Electronic Science and Technology of China 2 Zhejiang University 3 National University of Singapore |
| Pseudocode | Yes | Algorithm 1 RA(C) and Algorithm 2 LS-G are provided in the paper. |
| Open Source Code | Yes | Our code is put in https://github.com/fafafafafafafa7/LS Algorithm |
| Open Datasets | Yes | We use real datasets from the Network Data Repository online (Rossi and Ahmed 2015) |
| Dataset Splits | No | The paper specifies using '1872 datasets' and a 'default setting k = 64 and α = 1.1' but does not provide explicit information on how these datasets were split into training, validation, or testing sets. There is no mention of percentages, absolute counts, or a specific splitting methodology for reproduction. |
| Hardware Specification | Yes | These experiments are carried out under Ubuntu 16.04.3 LTS, using an Intel Core i5-7200U CPU at 2.50GHZ and 8GB RAM. |
| Software Dependencies | Yes | Our algorithms are implemented in C++ and compiled with g++ version 5.4.0 with -O3 option. |
| Experiment Setup | Yes | Overall, we get an average improvement of 12.07% for LS-G and 13.20% for LS-F. Although LS-F get more average improvements, LS-G uses less average running time. We show the performance of LS-F with different initial partitions in Fig. 4, where also give the proportion of best results among all results with four initial partitions. The detailed performance of LS-G and the running time are omitted here due to the limited space. The improvements on NE are not significant. However, for most instances, the performance of METIS+LS-G and METIS+LS-F is much better than that of NE+LS-G and NE+LS-F. For LS-F, about 42.51% best results are obtained by using initial partitions of METIS. Detailed Comparisons. To give clear comparisons, we select four instances from the 1872 instances as examples to illustrate the details. The four instances are selected from different domains with different size levels: coauthors-dblp (540486, 15245729) from collaboration networks , gridyeast (6008, 156945) from biological networks , Texas84 (36364, 1590651) from Facebook networks , and lastfm (1191805, 4519330) from social networks . The two numbers in the brackets are the numbers of vertices and edges. Most previous algorithms, say METIS, NE, SHEEP, and SPAC, fixed the balance value α = 1.1. We also take this setting and show the results under different values of k in Fig. 5. As k grows, LS-G and LS-F can consistently and effectively enhance the results produced by initial algorithms. |