The wide variety of bacterial population in the human gastrointestinal tract (the gut) are the key players in maintaining host physiological functions and colon health. Also, these gut microbiota-mediated productions of metabolites, while mostly beneficial to the host, have also been shown to contribute to the imbalance of the protective versus harmful intestinal bacterial species (dysbiosis). Such imbalance could result in intestinal and extra-intestinal disorders, including inflammatory bowel disease (IBD), diabetes mellitus (DM), obesity, etc. Furthermore, herbal medicines are capable of modulating the bacterial metabolic pathways by affecting the bacterial gene functions that serving as drug targets. This holds a great promise in balancing the gut ecosystem and prevent microbial-associated diseases. However, the diversity of small molecules in the herbs and the complexity of their mechanism of action poses a great challenge for data integration and herbal drug-target association identification. To overcome this challenge and get invaluable insights into microbiome-associated disease biology, a systems-level characterization of the effects of the small molecules from herbs on the bacterial genes and metabolic pathways were made in the current study. We proposed a computational network-based approach; the multi-stage probabilistic bipartite graph algorithm (MPBA), which integrates the complex heterogeneous metabolism/pathway data from herbs and gut bacteria. This approach provided a graphically intuitive solution to study the impact of herbs on gut microorganisms and employed a probabilistic latent semantic analysis (PLSA) framework to allow estimation of candidate entities. A case study using the 8 most important pathways during IBD and 405 enzymes belonging to these pathways was conducted. Our results show that 273 pathway enzymes were harbored by the bacteria, and 262 of them were targeted by small molecules present in 24 culinary herbs. The proposed MPBA enabled simplification of complex biological models needed for an in-depth study of the herb-microbes complex system.