Knowledge graphs have been a useful tool for many biomedical applications because of their effective representation of biological concepts. Plentiful evidence exists linking the gut microbiome to disease in a correlative context, but uncovering the mechanistic explanation for those associations remains a challenge. Here we demonstrate the potential of knowledge graphs to hypothesize plausible mechanistic accounts of host-microbe interactions in disease. We have constructed a knowledge graph of linked microbes, genes and metabolites called MGMLink, and, using a shortest path or template-based search through the graph and a novel path-prioritization methodology based on the structure of the knowledge graph, we show that this knowledge supports inference of mechanistic hypotheses that explain observed relationships between microbes and disease phenotypes. We discuss specific applications of this methodology in inflammatory bowel disease and Parkinson's disease. This approach enables mechanistic hypotheses surrounding the complex interactions between gut microbes and disease to be generated in a scalable and comprehensive manner.