The identification and prediction of variation in genetic data can be explored using graph-based machine learning methods. In particular, the comprehension of phenotypic effects at the cellular level is an accelerating research area in pharmacogenomics. Understanding the effect of drugs or disease on the underlying bionetwork could facilitate future drug development and improvement of precision medicine.In this article, a novel graph theoretic approach is proposed to infer a co-occurrence network from 16S microbiome data, specialised to handle small sampled data sets. Small data sets exacerbate the significant challenges faced by biological data, which exhibit properties such as sparsity, compositionality, and complexity of interactions. Methodologies are also proposed to statistically enrich and filter the inferred networks. The method is specialised for small data sets, which are abundant, but it can be generally applied to any 16S data set, and can also be extended to be integrated with other multi-omics data.The proposed methodology is tested on a data set of chickens vaccinated against and challenged by the protozoan parasite Eimeria tenella. Analysis of the expression of network features under three different stages of disease progression derive biologically intuitive conclusions from purely statistical methods. The distributions reveal clusters of species interacting mutualistically and parasitically, as expected. Moreover, a specific subnetwork is found to persist through all experimental conditions, representative of a 'core microbiome'.