Graph machine learning algorithms have been effectively applied to various learning tasks across numerous applications. In node classification, these algorithms leverage the input network to develop generalizable models by utilizing the relationship between network topology and node labels. However, real-world networks often exhibit significant variability in how node labels are distributed. Research has focused on understanding the relationship between network topology and label distribution in terms of homophily, heterophily, and label informativeness. Although specific algorithms have been designed to target particular distributions, there is no universal solution that can handle all network types effectively. Here, we introduce RoNE (Robust Network Enhancement), a network enhancement algorithm that can be integrated with any graph machine learning algorithm to improve homophily in the input network while preserving its topological characteristics. RoNE models the distribution of path lengths between any pair of labels in a network and uses a Bayesian framework to create a new network by adding or removing edges according to this distribution. To assess the value added by RoNE, we conduct extensive experiments on three homophilic and three heterophilic networks, in combination with three state-of-the-art graph machine learning algorithms. Our results demonstrate that RoNE consistently (and often significantly) enhances the node classification performance of these algorithms. We also find that path lengths of up to two are the most informative for network enhancement. We provide the Python implementation of RoNE at https://github.com/yorgancioglukaan/Network_enhancement .