Network analysis is an indispensable part of ecological studies. Specifically, networks have played a pivotal role in studying the diversity, dynamics and functionality of pollination systems. Recording plant-pollinator interaction networks is a laborious task, prone to missing or false negative interactions. Several methods enable the assessment of sampling completeness of the network with the use of species accumulation curves or Chao estimators. However, these methods do not provide a way to identify which interactions might be missed in the field. Methods that enable a more directed and focused field sampling are needed. Such methods would greatly benefit plant-pollinator studies and network studies in general. We additively decomposed the information of an interaction matrix into three parts: the difference in importance of the species, the specificity of the interactions, and the generality of the interactions. This information is exploited by a previously proposed linear filtering method to re-score absent interactions, thus pinpointing the likely missing interactions. We evaluated this approach using null models, intensive cross-validation, as well as external validation with the Web of Life database. By means of a case study, we provide insight into the structure of the network using an information-theoretic approach. We show how to use linear filtering to suggest missing interactions. A thorough evaluation shows that these results are both statistically stable and useful to guide the search for missing interactions in real-world networks. The non-uniformity of pollination interactions can be quantified using information theory and extracted using linear filtering. Our work can be valuable as a way to study different interaction networks as well as a tool to help identifying missing interactions.