A Data-Driven Graph Neural Network Framework for Predicting Topological Indices of Unicyclic and Bicyclic Graphs
Journal
Algorithms
ISSN
1999-4893
Date Issued
August 11, 2026
Author(s)
Abstract
Topological indices provide numerical descriptions of graph structure and support graph analysis in cheminformatics, network design, and graph mining. This study presents a reproducible computational framework that combines controlled cyclic-graph generation, structure-preserving transformations, exact computation of six classical topological indices, and multi-output graph neural network regression. The framework evaluates the Wiener, Merrifield–Simmons, Hosoya, first Zagreb, second Zagreb, and Randi’c indices for unicyclic and bicyclic graphs. It represents each graph using sparse connectivity and node-level features that encode degree, cycle membership, pendant connectivity, leaf status, and normalized eccentricity. A graph isomorphism network (GIN) jointly predicts the six indices and is compared with graph convolutional networks (GCNs), graph attention networks (GATs), and descriptor-based regression baselines. The controlled benchmark shows that nonlinear descriptor-based models achieve the lowest aggregate errors because the supplied graph-level descriptors contain strong prior information about graph size, degree structure, branching, and cycle complexity. Although GIN does not achieve the highest overall accuracy, it provides the strongest graph-native performance by learning directly from sparse connectivity and node-level features without requiring a fixed handcrafted graph-level descriptor vector. The proposed surrogate does not replace exact evaluation for isolated small graphs, where exact computation remains more appropriate. Instead, its practical value emerges through repeated evaluations of larger, more complex graph instances. To examine this setting, a computational stress experiment evaluates sparse multicyclic graphs under increasing cyclomatic complexity and measures exact computation time, timeout frequency, prediction accuracy, and the amortized break-even point. The results indicate that surrogate prediction becomes beneficial when combinatorial index computation becomes sufficiently expensive, and the trained model is reused across many structurally related graph queries. An external experiment on circulant graphs also demonstrates that the framework can extend beyond the original graph generators by modifying only the graph-construction stage.
Affiliation
School of Computing Sciences, Pak-Austria Fachhochschule IAST
Eastern Michigan University
University of Poonch
Funding
This research received no external funding.
File(s)![Thumbnail Image]()
Name
algorithms-19-00668.pdf
Size
4.73 MB
Format
Adobe PDF
Checksum (MD5)
d21ae4faae66589b095cb30b1f248ccc