Author name cluster

Zhenyu Guo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

AAAI Conference 2021 Conference Paper

Enhancing Balanced Graph Edge Partition with Effective Local Search

Zhenyu Guo
Mingyu Xiao
Yi Zhou
Dongxiang Zhang
Kian-Lee Tan

Graph partition is a key component to achieve workload balance and reduce job completion time in parallel graph processing systems. Among the various partition strategies, edge partition has demonstrated more promising performance in power-law graphs than vertex partition and thereby has been more widely adopted as the default partition strategy by existing graph systems. The graph edge partition problem, which is to split the edge set into multiple balanced parts to minimize the total number of copied vertices, has been widely studied from the view of optimization and algorithms. In this paper, we study local search algorithms for this problem to further improve the partition results from existing methods. More specifically, we propose two novel concepts, namely adjustable edges and blocks. Based on these, we develop a greedy heuristic as well as an improved search algorithm utilizing the property of the max-flow model. 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.

PDF Details

AAAI Conference 2020 Conference Paper

Enumerating Maximal k -Plexes with Worst-Case Time Guarantee

Yi Zhou
Jingwei Xu
Zhenyu Guo
Mingyu Xiao
Yan Jin

The problem of enumerating all maximal cliques in a graph is a key primitive in a variety of real-world applications such as community detection and so on. However, in practice, communities are rarely formed as cliques due to data noise. Hence, k-plex, a subgraph in which any vertex is adjacent to all but at most k vertices, is introduced as a relaxation of clique. In this paper, we investigate the problem of enumerating all maximal k-plexes and present FaPlexen, an enumeration algorithm which integrates the “pivot” heuristic and new branching schemes. To our best knowledge, for the ﬁrst time, FaPlexen lists all maximal k-plexes with provably worst-case running time O(n2 γn ) in a graph with n vertices, where γ < 2. Then, we propose another algorithm CommuPlex which non-trivially extends FaPlexen to ﬁnd all maximal kplexes of prescribed size for community detection in massive real-life networks. We ﬁnally carry out experiments on both real and synthetic graphs and demonstrate that our algorithms run much faster than the state-of-the-art algorithms.

PDF Details