While studies have explored differences in gut microbiome development for infant liquid diets (breastmilk, formula), little is known about the impact of complementary foods on infant gut microbiome development. Here, we investigated how different protein-rich foods (i.e., meat vs. dairy) affect fecal metagenomics and metabolomics during early complementary feeding from 5-12 months in U.S. formula-fed infants from a randomized controlled feeding trial. We used a network representation learning approach to model the time-dependent, complex interactions between microbiome features, metabolite compounds, and diet. We then used the embedded space to detect features associated with age and diet type and found the meat diet group was enriched with microbial genes encoding amino acid, nucleic acid, and carbohydrate metabolism. Compared to a more traditional differential abundance analysis, which analyzes features independently and found no significant diet associations, network node embedding represents the infant samples, microbiome features, and metabolites in a single transformed space revealing otherwise undetected associations between infant diet and the gut microbiome.