Abstract Precise cosmic web classification of observed galaxies in massive spectroscopic surveys can be either highly uncertain or computationally expensive. As an alternative, we explore a fast Machine Learning-based approach to infer the underlying dark matter tidal cosmic web environment of a galaxy distribution from its β -skeleton graph. We develop and test our methodology using the cosmological magnetohydrodynamic simulation Illustris-TNG at z = 0. We explore three different tree-based machine-learning algorithms to find that a random forest classifier can best use graph-based features to classify a galaxy as belonging to a peak, filament, or sheet as defined by the T-Web classification algorithm. The best match between the galaxies and the dark matter T-Web corresponds to a density field smoothed over scales of 2 Mpc, a threshold over the eigenvalues of the dimensionless tidal tensor of λ th = 0.0, and galaxy number densities around 8 × 10 −3 Mpc −3 . This methodology results on a weighted F1 score of 0.728 and a global accuracy of 74%. More extensive tests that take into account light-cone effects and redshift space distortions are left for future work. We make one of our highest ranking random forest models available on a public repository for future reference and reuse.