The increase of bacterial resistance to currently available antibiotics has underlined the urgent need to develop new antibiotic drugs. Antimicrobial peptides (AMPs), alone or in combination with other peptides and/or existing antibiotics, have emerged as promising candidates for this task. However, given that there are thousands of known AMPs and an even larger number can be synthesized, it is impossible to comprehensively test all of them using standard wet lab experimental methods. These observations stimulated an application of machine-learning methods to identify promising AMPs. Currently, machine learning studies combine very different bacteria without considering bacteria-specific features or interactions with AMPs. In addition, the sparsity of current AMP data sets disqualifies the application of traditional machine-learning methods or makes the results unreliable. Here, we present a new approach, featuring neighborhood-based collaborative filtering, to predict with high accuracy a given bacteria's response to untested AMPs based on similarities between bacterial responses. Furthermore, we also developed a complementary bacteria-specific link prediction approach that can be used to visualize networks of AMP-antibiotic combinations, enabling us to propose new combinations that are likely to be effective.