Structured machine learning on knowledge graphs with rich semantics has a plethora of advantages. First, complex ML models can be learned from small training data sets by exploiting background knowledge. Moreover, the models computed in this manner are expressive and explainable. However, most of the current approaches to structured machine learning cannot yet be deployed on real knowledge graphs. In this talk, we present some recent results on accelerating machine learning on knowledge graphs with rich semantics. In particular, we focus on algorithms which improve the runtime of ML approaches by exploiting multiple representations. We also discuss current challenges faced by this family of approaches.