Graph-based network science has evolved from its traditional foundations in discrete mathematics into an interdisciplinary field that integrates graph algorithms, network analysis, machine learning, artificial intelligence, knowledge representation, and temporal modelling. This study critically reviews this evolution, with particular emphasis on the transition from classical graph structures and algorithms to Graph Neural Networks (GNNs), knowledge graphs, dynamic graphs, and spatiotemporal graph learning. The study adopts a critical literature review approach, examining relevant academic research primarily published during 2020–2026 while incorporating foundational studies to establish the theoretical development of graph theory. The review focuses on five interconnected areas: graph-theoretical foundations and network structures, graph algorithms and network analytics, graph machine learning and GNNs, knowledge graphs and semantic reasoning, and dynamic and spatiotemporal graph learning. The findings indicate that traditional graph theory continues to provide the structural and mathematical foundation for contemporary network analysis, while GNNs enable data-driven learning from complex relational structures. Knowledge graphs further enhance graph intelligence by integrating semantic relationships and reasoning, whereas dynamic and spatiotemporal models provide more realistic representations of continuously evolving networks. However, the review identifies significant theoretical, computational and practical challenges, including scalability, interpretability, data quality, computational complexity, temporal evolution, heterogeneous network structures, privacy and reproducibility. A major gap identified is the fragmented treatment of classical graph theory, graph algorithms, graph learning, knowledge representation and dynamic network analysis. To address this gap, the study proposes an integrated graph-intelligence framework connecting mathematical graph foundations with algorithms, GNNs, knowledge graphs, dynamic and spatiotemporal learning, and intelligent decision support. The study concludes that future graph-based network science should emphasise scalable, explainable, adaptive and semantically informed graph-learning systems capable of transforming complex and continuously evolving relational data into reliable and actionable decision support.....