Classical graph algorithms and machine learning on graphs are often studied in isolation, yet each has much to offer the other. This talk explores the interplay from three angles. First, it shows how Graph Neural Networks can accelerate exact data reduction rules for the Maximum Weight Independent Set problem, allowing expensive reductions to be applied selectively and at scale, and yielding state-of-the-art solver performance on real-world instances. Second, the relationship is turned around: streaming graph partitioning is used to speed up distributed GNN training itself, balancing both vertices and edges to reduce communication overhead across workers. Finally, the talk presents a systematic experimental survey of modularity-based community detection, jointly evaluating classical heuristic, multilevel, metaheuristic, and exact methods alongside recent neural approaches within a unified benchmarking framework. Together, these results highlight where learning-based methods complement well-engineered combinatorial algorithms, where they fall short, and where the most promising opportunities for hybrid approaches lie.