Nonwoven materials consist of random fiber structures. They are essential to diverse application areas such as clothing, insulation and filtering. A long term goal in industry is the simulation-based optimization of material properties in dependence of the manufacturing parameters. Recent works developed a framework to predict tensile strength properties representing the fiber structure as a stochastic graph. In this paper we present an efficient machine learning approach using a regression model trained on features extracted from the graph, for which we develop a novel graph stretching algorithm. We demonstrate that applying our method to a practically relevant dataset yields similar prediction results as the original ODE approach (), while achieving a significant speedup by up to three orders of magnitude. This opens the field to optimization, as Monte Carlo simulations accounting for the stochastic nature of nonwovens become easily accessible. Our model generalizes well to unseen parameter combinations. Additionally, our approach produces interpretable results by using a simple linear model for the regression task.