gapa 0.0.2

A PyTorch library for accelerating Genetic Algorithm in Perturbed SubStructure Optimization.

GAPA is a Python library that accelerates Perturbed SubStructure Optimization(PSSO). This challenging field has many vital applications, such as Community Detection Attacks (CDA), Critical Node Detection(CND), Node Classification Attacks (NCA), and Link Prediction Attacks (LPA).

GAPA proposes a parallel acceleration framework to achieve fast computation of the Genetic Algorithm (GA) in PSSO. Currently, GAPA contains 10 PSSO algorithms implemented by GA. All algorithms built upon PyTorch.

Basic Environment

• python == 3.9
• pytorch == 2.3.0

See requirements.txt for more information.

Installation

Install from pip

pip install gapa

Install from source

git clone xxx
cd GAPA
python setup.py install

If you find the dependencies are complex to install, please try the following: python setup_empty.py install (only install GAPA without installing other packages)

File tree

├─GAPA
| |
| |-gapa  # Origin Files with Framework and Algorithms
| | └─algorithm  # The Files of Algorithms
| | | ├─CDA
| | | ├─CND
| | | ├─LPA
| | | └─NCA
| | ├─DeepLearning  # Some Key File for NCA Task
| | └─framework
| | | ├─body.py  # The Main Part of GA like Mutation
| | | ├─controller.py  # The Workflow Controller of all Acceleration Modes
| | | └─evaluator.py  # Class of Fitness Function
| | └─utils  # Some helpful Functions
| |-tests  # Examples for ten Algorithms and Custom Method
| | ├─absolute_path.py  # The main path of This project and Others.
| | ├─CDA_new.py  #  Kickstart Algorithms of CDA Tasks
| | ├─CND_new.py  #  Kickstart Algorithms of CND Tasks
| | ├─LPA_new.py  #  Kickstart Algorithms of LPA Tasks
| | ├─NCA_new.py  #  Kickstart Algorithms of NCA Tasks
| | ├─Custom.py  #  Example for Custom Method
| | ├─run.py  #  Kickstart a Custom Method
| | |
| | ├─Evotorch_SixDST.py  # The implements of examples with Evotorch and Evox
| | ├─Evotorch_CDA_EDA.py
| | ├─Evox_SixDST.py
| | ├─Evox_CDA_EDA.py

Test Examples

We provide four example files in tests/ to illustrate how to use our optimization code. The relationship between the algorithm and the reference file is as follows:

File	Algorithm
CDA_new.py	QAttack, CGN, CDA-EDA
CND_new.py	CutOff, SixDST, TDE
NCA_new.py	GANI, NCA-GA
LPA_new.py	LPA-EDA, LPA-GA

Kickstart an algorithm:

python CND_new.py --dataset=ForestFire_n500 --method=SixDST --pop_size=100 --mode=m

or you can choose your way to start an algorithm.

We also provide application examples of SixDST and CDA-EDA algorithms on Evotorch and Evox for users‘ reference.

File
Evotorch_CDA_EDA.py
Evotorch_CDA_EDA.py
Evox_SixDST.py
Evox__CDA_EDA.py

Custom Method

We also provide a way to start a custom method. See more details in custom.py, run.py and absolute_path.py.

1. Set up your path.

project_path = ...  # ~/
dataset_path = ...
# If NCA -> Set model path
model_path = ...

2. Create your own evaluator and controller classes.

import torch
from gapa.framework.evaluator import BasicEvaluator
from gapa.framework.controller import CustomController


class ExampleEvaluator(BasicEvaluator):
    def __init__(self, pop_size, adj: torch.Tensor, device):
        super().__init__(
            pop_size=pop_size,
            device=device
        )
        ...
    def forward(self, population):
        ...
        

class ExampleController(CustomController):
    def __init__(self, budget, pop_size, pc, pm, side, mode, num_to_eval, device):
        super().__init__(
            side=side,
            mode=mode,
            budget=budget,
            pop_size=pop_size,
            num_to_eval=num_to_eval,
            device=device
        )
        self.crossover_rate = pc
        self.mutate_rate = pm
        ...
        
    def setup(self, data_loader, evaluator, **kwargs):
        ...
        return evaluator

    def init(self, body):
        ...
        return ONE, population

    def SelectionAndCrossover(self, body, population, fitness_list, ONE):
        ...
        return crossover_population

    def Mutation(self, body, crossover_population, ONE):
        ...
        return mutation_population

    def Eval(self, generation, population, fitness_list, critical_genes):
        metric = MetricFunc(args)
        return {
            "Metric": metric
        }

3. Create a new python file and initialize your device. Use world_size to choose the desired number of processes:

import os
from gapa.utils.init_device import init_device
device, world_size = init_device(world_size=2)

4. Then import other package.

import torch
import networkx as nx
from custom import ExampleEvaluator, ExampleController
from absolute_path import dataset_path
from gapa.utils.DataLoader import Loader
from gapa.framework.controller import Start
from gapa.framework.body import Body

5. Load your data.

dataset = ...
data_loader = Loader(
    dataset, device
)
...

6. Run your method.

body = Body(nodes_num, budget, pop_size, "min", device)
evaluator = ExampleEvaluator(pop_size, adj, device)
controller = ExampleController(budget, pop_size, pc, pm, fit_side, "s", num_to_eval, device)
Start(max_generation, data_loader, controller, evaluator, body, world_size)

Implemented Algorithms

Abbr	Years	Type	Ref	Code
Q-Attack	2019	CDA	[1]	-
CGN	2022	CDA	[2]	Link
CDA-EDA	2020	CDA	[3]	-
CutOff	2023	CND	[4]	-
SixDST	2024	CND	-	-
TDE	2022	CND	[5]	-
LPA-EDA	2019	LPA	[6]	Link
LPA-GA	2019	LPA	[6]	-
GANI	2023	NCA	[7]	Link
NCA-GA	2018	NCA	[8]	Link

Changelog

• 12/2024: Open source code, providing ten algorithms for four tasks under GA-based PSSO problem.

• 04/2025: Update the communication of arbitrary populations in M mode and MNM mode under different GPUs. Optimized the fitness calculation of CDA-EDA. Provides CDA-EDA and SixDST acceleration use cases based on Evox and Evotorch.

Citing GAPA

If you use GAPA in your research and want to cite in your work, please use:

@article{
    title = Efficient Parallel Genetic Algorithm for Perturbed Substructure Optimization in Complex Network
    author = Shanqing Yu, Meng Zhou, Jintao Zhou, Minghao Zhao, Yidan Song, Yao Lu, Zeyu Wang, Qi Xuan
    journal = arXiv preprint arXiv:2412.20980
    year = {2024}
    doi = {https://doi.org/10.48550/arXiv.2412.20980}
}

References

[1] Jinyin Chen, Lihong Chen, Yixian Chen, Minghao Zhao, Shanqing Yu, Qi Xuan, and Xiaoniu Yang. Ga-based q-attack on community detection. IEEE Transactions on Computational Social Systems, 6(3):491–503, 2019.

[2] Liu Dong, Zhengchao Chang, Guoliang Yang, and Enhong Chen. "Hiding ourselves from community detection through genetic algorithms." Information Sciences 614 (2022): 123-137.

[3] Shanqing Yu, Jun Zheng, Jinyin Chen, Qi Xuan, and Qingpeng Zhang. Unsupervised euclidean distance attack on network embedding. In 2020 IEEE Fifth International Conference on Data Science in Cyberspace (DSC), pages 71–77, 2020.

[4] Yu, Shanqing, Jiaxiang Li, Xu Fang, Yongqi Wang, Jinhuan Wang, Qi Xuan, and Chenbo Fu. "GA-Based Multipopulation Synergistic Gene Screening Strategy on Critical Nodes Detection." IEEE Transactions on Computational Social Systems (2023).

[5] Yu, Shanqing, Yongqi Wang, Jiaxiang Li, Xu Fang, Jinyin Chen, Ziwan Zheng, and Chenbo Fu. "An improved differential evolution framework using network topology information for critical nodes detection." IEEE Transactions on Computational Social Systems 10, no. 2 (2022): 448-457.

[6] Yu, Shanqing, Minghao Zhao, Chenbo Fu, Jun Zheng, Huimin Huang, Xincheng Shu, Qi Xuan, and Guanrong Chen. "Target defense against link-prediction-based attacks via evolutionary perturbations." IEEE Transactions on Knowledge and Data Engineering 33, no. 2 (2019): 754-767.

[7] Fang, Junyuan, Haixian Wen, Jiajing Wu, Qi Xuan, Zibin Zheng, and K. Tse Chi. "Gani: Global attacks on graph neural networks via imperceptible node injections." IEEE Transactions on Computational Social Systems (2024).

[8] Dai, Hanjun, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. "Adversarial attack on graph structured data." In International conference on machine learning, pp. 1115-1124. PMLR, 2018.