Efficient Parallel Genetic Algorithm for Perturbed Substructure Optimization in Complex Network

Shanqing Yu, Meng Zhou, Jintao Zhou, Minghao Zhao, Yidan Song, Yao Lu, Zeyu Wang, Qi Xuan · 2024

Read Efficient Parallel Genetic Algorithm for Perturbed Substructure Optimization in Complex Network by Shanqing Yu, Meng Zhou, Jintao Zhou, Minghao Zhao, Yidan Song, Yao Lu, Zeyu Wang, Qi Xuan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-20980.txt.

Description

A 2024 arXiv research paper by Shanqing Yu, Meng Zhou, Jintao Zhou, Minghao Zhao, Yidan Song, Yao Lu, Zeyu Wang, Qi Xuan. Evolutionary computing, particularly genetic algorithm (GA), is a combinatorial optimization method inspired by natural selection and the transmission of genetic information, which is widely used to identify optimal solutions to complex problems through simulated programming and iteration.

Catalog record

CREATORShanqing Yu, Meng Zhou, Jintao Zhou, Minghao Zhao, Yidan Song, Yao Lu, Zeyu Wang, Qi Xuan
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE61 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-20980

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Parallel Genetic Algorithm for Perturbed Substructure Optimization in Complex Network Thanks: This work was supported in part by the Key R&D Program of Zhejiang under Grant 2022C01018 and 2024C01025, by the National Natural Science Foundation of China under Grant 62103374 and U21B2001, by Key Technology Research and Development Program Project of Hangzhou under Grant 2024SZD1A23, and by the Zhejiang Provincial Natural Science Foundation of China under Grant ZCLY24F0302. Shanqing Yu, Meng Zhou, Jintao Zhou, Yidan Song, Yao Lu, Zeyu Wang, Qi Xuan are with the Institute of Cyberspace Security, College of Information Engineering, Zhejiang University of Technology, Hangzhou, China; Binjiang Institute of Artificial Intelligence, Zhejiang University of Technology, 310056, Hangzhou, China (E-mail: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]). Minghao Zhao is with the Binjiang Institute of Artificial Intelligence, Zhejiang University of Technology, 310056, Hangzhou, China (E-mail: [email protected]). Corresponding author: Zeyu Wang. Shanqing Yu, Meng Zhou, Jintao Zhou, Minghao Zhao, Yidan Song, Yao Lu, Zeyu Wang, Qi Xuan Abstract Evolutionary computing, particularly genetic algorithm (GA), is a combinatorial optimization method inspired by natural selection and the transmission of genetic information, which is widely used to identify optimal solutions to complex problems through simulated programming and iteration. Due to its strong adaptability, flexibility, and robustness, GA has shown significant performance and potentiality on perturbed substructure optimization (PSSO), an important graph mining problem that achieves its goals by modifying network structures. However, the efficiency and practicality of GA-based PSSO face enormous challenges due to the complexity and diversity of application scenarios. While some research has explored acceleration frameworks in evolutionary computing, their performance on PSSO remains limited due to a lack of scenario generalizability. Based on these, this paper is the first to present the GA-based PSSO Acceleration framework (GAPA), which simplifies the GA development process and supports distributed acceleration. Specifically, it reconstructs the genetic operation and designs a development framework for efficient parallel acceleration. Meanwhile, GAPA includes an extensible library that optimizes and accelerates 10 PSSO algorithms, covering 4 crucial tasks for graph mining. Comprehensive experiments on 18 datasets across 4 tasks and 10 algorithms effectively demonstrate the superiority of GAPA, achieving an average of 4x the acceleration of Evox. The repository is in https://github.com/NetAlsGroup/GAPA . I Introduction Evolutionary computation is an algorithm inspired by the natural evolutionary process, that can explore the optimal solution of complex combinatorial optimization problems by simulating the biological evolutionary process, with high adaptability and flexibility [ 1 , 2 ] . Among them, the evolutionary algorithms represented by Genetic Algorithm(GA) prefer the natural selection mechanism and the law of genetic information transfer in biological evolution, which is widely used in neural evolution [ 3 , 4 , 5 ] , natural language processing [ 6 ] , graph mining [ 7 , 8 , 9 ] , etc. Particularly, it has achieved excellent performance on the perturbed substructure optimization (PSSO) problem, which is a typical combinatorial optimization problem in graph mining. PSSO is a task that aims to achieve specific goals by modifying the network structures with a perturbation budget [ 10 ] , covering various applications such as critical node detection [ 11 , 8 , 12 , 13 , 14 , 15 ] , community detection [ 7 , 16 , 17 , 18 , 19 , 20 ] , link prediction [ 9 ] , node classification [ 21 , 22 ] , etc. Essentially, PSSO is a problem that searches for optimal perturbed substructures from huge topological combinations, and GA has gained wide attention for its powerful global search capability. For example, Chen et al. [ 16 ] used GA to implement a community detection attack. Yu et al. [ 7 ] proposed an Euclidean distance attack method using a genetic algorithm to scramble edges and thus turn off downstream data mining. Fang et al. [ 22 ] injected fake nodes through GA to affect the ability of node classification models. However, the increasing complexity of application scenarios presents significant challenges for GA-based PSSO in terms of efficiency and computational cost, putting higher demands on the efficiency and generalizability of GA as well as further optimization and acceleration. Therefore, acceleration frameworks for GA have received widespread attention. GPU hardware offers powerful parallel computing capabilities, making it a vital tool for accelerating deep learning model training tasks [ 23 ] . Many researchers have explored the use of GPUs to accelerate evolution algorithms with promising results [ 24 , 25 , 26 , 27 , 28 , 29 ] . Among them, Evotorch [ 28 ] provides an acceleration framework based on PyTorch for evolutionary algorithms. However, it lacks architectural design flexibility and a unified programming model, making it challenging to implement general-purpose evolutionary algorithms efficiently [ 29 ] . Evox [ 29 ] introduces a scalable and user-friendly acceleration framework for evolutionary computation based on JAX to address these limitations. While JAX offers powerful capabilities, it requires precompilation and transformation of functions, such as fitness functions. JAX also suggests using pure functions that neither read nor modify external states. Meanwhile, it discourages using iterators in functions, aligning with its functional programming paradigm. However, in PSSO tasks, a graph is often subject to disturbances, necessitating GA to read and modify state variables and perform iterative computations within fitness or auxiliary functions. Additionally, libraries like Evotorch and Evox excel in general-purpose evolutionary computation but are not explicitly designed for GA-based PSSO problems. The genetic operation in GA, particularly for PSSO tasks, differ significantly from traditional evolutionary algorithms. For example, Evox does not support complex mutation operations. Porting such operations to the JAX framework demands a deep understanding of JAX, which poses a significant challenge for users. As a result, these frameworks may not be applicable or rapidly deployable when solving domain-specific problems like PSSO. To address these challenges, we propose GAPA, a GA acceleration framework based on PyTorch customized for the PSSO problem. For that, we reconstruct the genetic operation and design general acceleration modes. Specifically, on the genetic operation side, we reconstruct and simplify the genetic operation. Especially for the fitness function in the genetic operation, considering its diversity, we propose a strategy for designing a fitness function with the goal of efficient parallel calculation. On the acceleration mode side, We propose four computation modes based on different levels of parallelism to satisfy the demands of various algorithms and common applications. Finally, we organize the above work into a generic functional programming framework, covering 4 PSSO tasks and 10 GA-based PSSO algorithms, which supports fast and easy deployment of GA-based PSSO algorithms. To demonstrate the superiority of GAPA in parallel acceleration, we utilize it to accelerate 10 GA algorithms across these four tasks with 12 datasets. The main contributions of this work are as follows: • We are the first to propose and implement a customized GA-based PSSO acceleration framework, GAPA, which implements parallel acceleration for GA from three perspectives: genetic operation, fitness function design, and acceleration mode design. Meanwhile, GAPA supports simple and functional programming for PSSO algorithms. • Based on the GAPA, we have built and publicized a GA acceleration library for the PSSO problem for the first time. The library covers 4 important graph mining tasks, contains 10

Read the complete text