The central role of protein-protein interactions (PPIs) in biology has stimulated colossal efforts to identify thousands of them in several organisms. The resulting PPI maps are commonly represented as graphs, where nodes denote proteins and edges represent physical interactions. However, the methods used to generate PPI data on a large scale do not readily allow one to discriminate features such as interaction strength (affinity), type (protein-protein or protein-peptide interaction) or spatiotemporal existence (where and when the proteins are present and interact). Yet, in recent years, a number of studies have tackled these limitations by projecting additional information onto PPIs, revealing novel properties in terms of their evolution and dynamics. In this review we examine these properties both at the binary interaction level and at the network level. We suggest that the diverse and sometimes contradictory results described by different research groups are mostly due to incomplete data coverage and limited data types. Finally, we discuss recently developed methods that will improve this picture in the future.