Applying Graph Algorithms and Graph Convolutional Networks for Advertising Anti‑Fraud at 58.com

Graphs model relationships between entities such as users, IPs, and devices; vertices represent objects while edges capture their interactions. Originating from Euler's Königsberg problem, graph theory has evolved into a foundation for many algorithms.

In advertising anti‑fraud, real‑world graphs (e.g., road networks, social networks) are constructed from behavior data, enabling detection of coordinated cheating groups.

Four key graph algorithms are introduced:

Connected subgraph (component) detection to find clusters of tightly linked nodes.

Label propagation for fast semi‑supervised community detection.

Louvain algorithm, which optimizes modularity for hierarchical clustering.

Graph Convolutional Networks (GCN) that combine structural information with node features via neural message passing.

The anti‑fraud workflow at 58.com first builds a bipartite graph from user actions (e.g., shared IPs). Unsupervised algorithms (connected components, label propagation, Louvain) generate clusters, which are filtered and manually verified to produce high‑quality black/white labels.

These labels serve as training data for a two‑layer GCN model (with dropout, ReLU activation, ADAM optimizer, and cross‑entropy loss). The GCN ingests the adjacency matrix and node feature matrix (53‑dimensional) for ~403k vertices and 3.12M edges, achieving 98.9% training accuracy and 98.2% test accuracy.

Experimental comparison shows that GCN outperforms a baseline XGBoost model and other unsupervised methods, delivering over 20% relative recall improvement while maintaining >95% precision.

Future work includes incorporating richer behavioral dimensions, edge weighting, and further tuning of the underlying graph algorithms to enhance detection robustness.