Graph Neural Networks Rely on Classical Structural Heuristics

A new analysis published in EPJ Data Science reveals that graph neural networks, specifically the subgraph-based model known as SEAL, largely rely on classical structural heuristics to predict link formation in complex networks. The study, published in August 2026, investigates the data-driven mechanisms behind link prediction by applying a statistical-mechanical perspective to understand which local structural descriptors drive the predictions of these advanced machine learning models. While graph neural networks have achieved state-of-the-art performance in identifying potential connections within networks, the specific mechanisms they implicitly learn have remained poorly understood until now. The authors sought to determine how these mechanisms depend on the type of network and to what extent they surpass traditional, simpler heuristics.

The investigation focused on 27 undirected real-world networks, spanning social, collaboration, biological, and technological domains. For each candidate edge in these networks, the researchers utilized the SEAL model, which operates on the enclosing subgraph of the potential link. In parallel with the neural network’s operations, the team computed a common set of interpretable structural descriptors. These included neighborhood overlap metrics such as common neighbors, Adamic–Adar, resource allocation, and Jaccard coefficients, as well as shortest-path distance, degree statistics, local clustering, and triangle counts. This parallel computation allowed for a direct comparison between the complex decision-making of the neural network and established structural measures.

To bridge the gap between the black-box nature of the neural network and interpretable structural features, the researchers trained global surrogate models. These surrogates, consisting of decision trees and explainable boosting machines, were designed to approximate the outputs of the SEAL model and directly predict ground-truth links. This methodological approach yielded quantitative feature-importance profiles that characterize both the actual link formation behavior in the networks and the specific decision functions employed by the graph neural network. By using explainable boosting machines, the study provided a transparent view into which features the model prioritizes when making predictions.

The results across the 27 networks indicated that short distances, neighborhood overlap, and triadic closure systematically dominate the process of link formation. In contrast, degree-based features played a secondary role in the predictive power of the model. The importance of triangles in the network structure correlated strongly with global clustering. Additionally, the researchers used principal component analysis and t-distributed stochastic neighbor embedding to create visualizations of the global importance vectors. These embeddings summarized how structural importance profiles vary across different networks, although the authors explicitly noted that these should be treated as exploratory visualizations rather than evidence for statistically significant domain separation.

A key finding emerged from the degree-preserving randomization experiments, which suppressed triangle and similarity-related features. In these randomized scenarios, distance and degree remained the dominant mechanisms for link prediction, with only a limited loss in overall predictive performance. This suggests that while higher-order structural patterns contribute to the model’s accuracy, the fundamental predictive power is rooted in simpler, lower-order interactions. The study concludes that SEAL largely reuses classical structural heuristics as effective low-order interactions, while also exploiting additional higher-order subgraph patterns in specific network domains.

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

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

Article References: Liu, D. (2026). Data-driven link formation in complex networks: a statistical–mechanical analysis of subgraph-based graph neural networks. EPJ Data Science, 15(1), Article 88. https://doi.org/10.1140/epjds/s13688-026-00690-x

Image Credits: AI Generated

DOI: 10.1140/epjds/s13688-026-00690-x

Keywords: Data-driven, link, formation, complex, networks, statistical, mechanical, analysis, subgraph-based, graph, neural, scientific research