Graph Algorithm Design and Optimization for Detecting Black Market Users in Virtual Networks

Introduction Virtual networks contain malicious users who exploit illegal activities for profit, threatening the health of various services. Traditional tree‑based models and community detection have limitations, so this work explores graph representation learning combined with clustering to better uncover black‑market accounts.

1. Background and Goals of Graph Algorithm Design Malicious accounts are the source of black‑market activity; targeting them at the account level enables precise disruption. Challenges include high adversarial resistance, the need for proactive detection before crimes occur, and the difficulty of influencing user behavior.

2. Graph Algorithm Design Objectives The algorithm should achieve high coverage and precision, produce reasonably sized user clusters for practical use, and support incremental features for dynamic networks without retraining the entire model.

3. GraphSAGE Core Idea GraphSAGE relies on neighbor sampling and feature aggregation. Each node’s own attributes and sampled neighbor attributes undergo linear transformations, are concatenated, and transformed again to obtain node embeddings, which can be used for downstream tasks via unsupervised training such as NCE loss.

4. Advantages of GraphSAGE Neighbor sampling mitigates memory explosion in GCNs and converts transductive learning into inductive learning, enabling incremental feature support and reducing over‑fitting.

5. Limitations of GraphSAGE Original GraphSAGE cannot handle weighted graphs, introduces randomness that makes embeddings unstable during inference, may lose local information due to limited sampling, and deep GCN layers can cause over‑smoothing.

6. Optimizations of GraphSAGE a) Aggregation optimization: normalize edge weights before aggregation so that more influential neighbors contribute more. b) Pruning optimization: keep only the top‑K weighted edges per node during inference to stabilize embeddings and reduce memory usage. c) Sampling optimization: use DGL‑based sampling that concatenates a node’s own features with the mean of its neighbors, preserving more local information and avoiding over‑smoothing.

7. Effect Evaluation Metrics include clustering accuracy and malicious recall rate. Compared with FastUnfolding and node2vec, the optimized approach shows improvements in accuracy, recall, average community size, and runtime.

8. Isolation and Heterogeneity in Black‑Market Scenarios Isolated nodes (cold‑start) are addressed by EGES, which maps node attributes to embeddings via attention, allowing new nodes to be represented without relying on graph connections. Heterogeneous networks, where malicious and normal users intermix, are handled by adjusting graph structure—removing links between malicious and normal accounts and strengthening malicious‑malicious connections—using LDS to learn a more reasonable adjacency matrix.

9. Summary and Reflections Key takeaways: (1) Feature engineering and graph construction are crucial; (2) No single algorithm fits all scenarios—algorithm selection must be context‑aware; (3) Simple, production‑ready algorithms often yield the best results in industry deployments.

Thank you for reading.