Coordinated behavior among groups of biological units, such as co-expressed genes, is common in biological systems including the human microbiome, which is important in a variety of physiologic and pathological processes. While many methods infer such groupings, principled identification of interactions between groups remains under-explored. We present Host-Microbe Groups Interaction Model (HM-GIM), a generative Bayesian deep learning approach for uncovering group-level interactions in host-microbiome data. HM-GIM jointly infers groups of host genes or microbes, along with latent factors that induce a sparse, undirected dependency structure among them. Key innovations include: (1) modeling undirected and multi-way interactions, (2) avoiding distortions from simplex-based models, and (3) enabling flexible count-based error models. We demonstrate on paired human gene expression and microbiome data from a longitudinal cohort of patients with tuberculosis (TB) that HM-GIM outperforms existing methods in finding biologically meaningful groupings, and provide a case study identifying host-microbe interactions involved in innate and adaptive host immunity.