Introduction

This repository contains implementations and evaluations of various Community Search (CS) approaches, including both non-learning-based and learning-based approaches, along with a recommendation model (RecCS) for selecting the top-k CS approaches for a given query.

Overview

This project consists of three main components:

1. Model Evaluation: Comprehensive evaluation of CS approaches, including:

   • Non-learning-based approaches: QDC, LM, SGM, DMCS, PPR, kcore, ktruss, kclique, kecc
   • Learning-based approaches: ICS-GNN, QD-GNN, CommunityAF, CommunityDF, COCLEP, CSFormer, TransZero

2. Ground-truth Community Analysis: Analyzing and visualizing ground-truth community characteristics, including community statistics, community visualization, and performance correlation analysis with community properties (e.g., size, density).

3. RecCS: A model that recommends the top-k CS approaches for a given query.

Environment

• Python: 3.10.18
• PyTorch: 2.2.1
• CUDA: 12.0
• Key Libraries: PyG, DGL

Other dependencies can be found at requirements.txt

Installation

# 1. Create conda environment
conda create -n <env_name> python=3.10.18
conda activate <env_name>

# 2. Run installation script
bash env_bash.sh

Data

Data Sources:

• PyTorch
  • PyG: PyTorch Geometric
  • DGL: Deep Graph Library
• SNAP: Stanford Network Analysis Project

Data Processing:

The details of data preprocessing and query generation can be found at data_process.py.

We include preprocessed citeseer and amazon datasets in data/datasets as examples.

Usage

Part 1: Evaluation of CS approaches

The evaluation experiments are implemented in base.py. You should run experiments with exp_mod == 1 to ensure all models are trained or built in their default state before running other experiments.

Step 1: Run Default Experiments

This step trains/builds all models and evaluates them on the default setting:

for method in QDC LM SGM DMCS PPR kcore ktruss kclique kecc ICS_GNN QD_GNN CommunityAF CommunityDF COCLEP CSFormer TransZero; do
    python base.py --all_models "$method" --exp_mod 1 --dataset <dataset_name> --phase train
    python base.py --all_models "$method" --exp_mod 1 --dataset <dataset_name> --phase test
done

Example with citeseer dataset:

for method in QDC LM SGM DMCS PPR kcore ktruss kclique kecc ICS_GNN QD_GNN CommunityAF CommunityDF COCLEP CSFormer TransZero; do
    python base.py --all_models "$method" --exp_mod 1 --dataset citeseer --phase train
    python base.py --all_models "$method" --exp_mod 1 --dataset citeseer --phase test
done

Find Best Model of Query:

After running the test phase, you can analyze which model performs best for each query:

python base.py --dataset <dataset_name> --eval_bestQ

The script generates a CSV file containing best model statistics saved to output/result/<dataset_name>_best_1_0.csv.

Step 2: Run Additional Experiments

Query Size Experiment (params: 2, 4, 6, 8):

python base.py --all_models <method_name> --exp_mod 3 --params <query_size> --dataset <dataset_name> --phase train
python base.py --all_models <method_name> --exp_mod 3 --params <query_size> --dataset <dataset_name> --phase test

Scalability Experiment (params: 20, 40, 60, 80):

python base.py --all_models <method_name> --exp_mod 4 --params <vertex_percentage> --dataset <dataset_name> --phase train
python base.py --all_models <method_name> --exp_mod 4 --params <vertex_percentage> --dataset <dataset_name> --phase test

Robustness Experiment (params: 10, 20, 30):

python base.py --all_models <method_name> --exp_mod 5 --params <edge_percentage> --dataset <dataset_name> --phase train
python base.py --all_models <method_name> --exp_mod 5 --params <edge_percentage> --dataset <dataset_name> --phase test

Boundary Query Vertices:

python base.py --all_models <method_name> --exp_mod 9 --dataset <dataset_name> --phase test

Internal Query Vertices:

python base.py --all_models <method_name> --exp_mod 10 --dataset <dataset_name> --phase test

Part 2: Impact of Ground-truth Communities

Community Statistics

python community_stats.py --dataset <dataset_name>

The script generates a CSV file containing community statistics saved to output/result/community_stats/<dataset_name>_community_stats.csv.

Community Visualization

The community_visualize.py script creates visualizations of communities based on the statistics generated by community_stats.py.

Note: Make sure you have run community_stats.py first to generate the required statistics file.

python community_visualize.py --dataset <dataset_name>

The visualization outputs are saved to output/result/community_landscape/.

Ground-Truth Property Analysis

Before analyzing ground-truth community properties and their correlation with model performance, make sure you have run exp_mod=1 test phase first to generate the required result files.

python base.py --dataset <dataset_name> --eval_gt_property

The output results are saved to output/result/<dataset_name>_gt_size_1_0.csv and output/result/<dataset_name>_gt_density_1_0.csv.

Part 3: Recommendation Model (RecCS)

Step 1: Generate Recommendation Labels

Note: Make sure you have already run exp_mod=1 to build all models before generating recommendation labels.

Before training RecCS, you should generate labels for training, validation, and testing. All generated label files will be saved to output/process/.

Generate training labels:

for method in QDC LM SGM DMCS PPR kcore ktruss kclique kecc ICS_GNN QD_GNN CommunityAF CommunityDF COCLEP CSFormer TransZero; do
    python recommend.py --recommend_model "$method" --dataset <dataset_name> --phase test --generate_mod recLabel --rec_task generate
done

Generate validation labels:

for method in QDC LM SGM DMCS PPR kcore ktruss kclique kecc ICS_GNN QD_GNN CommunityAF CommunityDF COCLEP CSFormer TransZero; do
    python recommend.py --recommend_model "$method" --dataset <dataset_name> --phase test --generate_mod recValid --rec_task generate
done

Generate testing labels:

for method in QDC LM SGM DMCS PPR kcore ktruss kclique kecc ICS_GNN QD_GNN CommunityAF CommunityDF COCLEP CSFormer TransZero; do
    python recommend.py --recommend_model "$method" --dataset <dataset_name> --phase test --generate_mod recExact --rec_task generate
done

Step 2: Train and Test RecCS

After generating labels, train and test the recommendation model:

Default recommendation:

# Training
python recommend.py --dataset <dataset_name> --phase train --rec_task recommend --rec_exp_mod 1

# Testing
python recommend.py --dataset <dataset_name> --phase test --rec_task recommend --rec_exp_mod 1

Top-k sensitivity (exp_param: 1, 3, 5, 7):

python recommend.py --dataset <dataset_name> --phase test --rec_task recommend --rec_exp_mod 2 --exp_param <topk>

Subgraph size sensitivity (exp_param: 100, 300, 500, 700):

# Training
python recommend.py --dataset <dataset_name> --phase train --rec_task recommend --rec_exp_mod 3 --exp_param <topn>

# Testing
python recommend.py --dataset <dataset_name> --phase test --rec_task recommend --rec_exp_mod 3 --exp_param <topn>

Ablation studies:

# RecCS w/o Q 
python recommend.py --dataset <dataset_name> --phase train --rec_task recommend --rec_exp_mod 11
python recommend.py --dataset <dataset_name> --phase test --rec_task recommend --rec_exp_mod 11

# RecCS w/o KL
python recommend.py --dataset <dataset_name> --phase train --rec_task recommend --rec_exp_mod 14
python recommend.py --dataset <dataset_name> --phase test --rec_task recommend --rec_exp_mod 14

Output

Results are saved in the output/ directory:

• output/model/: Trained models and indexes
• output/result/: Evaluation results
• output/result/community_stats/: Community statistics files
• output/result/community_landscape/: Community visualization images
• output/train/: Training logs
• output/process/: Processed data and recommendation labels