Data-driven link formation in complex networks: a statistical–mechanical analysis of subgraph-based graph neural networks

Graph neural networks (GNNs) achieve state-of-the-art performance on link prediction, yet the link formation mechanisms they implicitly learn on complex networks remain poorly understood. From a statistical–mechanical and data-driven perspective, we ask which local structural descriptors drive their predictions, how these depend on network type, and to what extent they go beyond classical heuristics. We address these questions for SEAL, a representative subgraph-based GNN, on 27 undirected real-world networks spanning social-like, collaboration, biological and technological domains. For each candidate edge, SEAL operates on its enclosing subgraph. In parallel, we compute a common set of interpretable structural descriptors—neighborhood overlap (common neighbors, Adamic–Adar, resource allocation, Jaccard), shortest-path distance, degree statistics, local clustering and triangle counts—and train global surrogate models (decision trees and explainable boosting machines, EBMs) to approximate SEAL’s outputs and directly predict ground-truth links. This yields quantitative feature-importance profiles characterising both the label-side link formation behaviour and the GNN’s decision function. Across the 27 networks, short distances, neighborhood overlap and triadic closure systematically dominate link formation, while degree-based features play a secondary role. Triangle importance correlates strongly with global clustering, and PCA/t-SNE embeddings of the global importance vectors summarise how structural importance profiles vary across networks. We treat these embeddings as exploratory visualizations of cross-network patterns rather than as evidence for statistically significant domain separation. Degree-preserving randomization suppresses triangle and similarity-related features and leaves distance plus degree as the dominant mechanism, with limited loss in predictive performance. Overall, SEAL largely reuses classical structural heuristics as effective low-order interactions, while exploiting additional higher-order subgraph patterns in specific network domains. Clinical trial number: not applicable.