Protein phosphorylation homoeostasis is tightly controlled and pathological conditions are caused by subtle alterations of the cell phosphorylation profile. Altered levels of kinase activities have already been associated to specific diseases. Less is known about the impact of phosphatases, the enzymes that down-regulate phosphorylation by removing the phosphate groups. This is partly due to our poor understanding of the phosphatase-substrate network. Much of phosphatase substrate specificity is not based on intrinsic enzyme specificity with the catalytic pocket recognizing the sequence/structure context of the phosphorylated residue. In addition many phosphatase catalytic subunits do not form a stable complex with their substrates. This makes the inference and validation of phosphatase substrates a non-trivial task. Here, we present a novel approach that builds on the observation that much of phosphatase substrate selection is based on the network of physical interactions linking the phosphatase to the substrate. We first used affinity proteomics coupled to quantitative mass spectrometry to saturate the interactome of eight phosphatases whose down regulations was shown to affect the activation of the RAS-PI3K pathway. By integrating information from functional siRNA with protein interaction information, we develop a strategy that aims at inferring phosphatase physiological substrates. Graph analysis is used to identify protein scaffolds that may link the catalytic subunits to their substrates. By this approach we rediscover several previously described phosphatase substrate interactions and characterize two new protein scaffolds that promote the dephosphorylation of PTPN11 and ERK by DUSP18 and DUSP26, respectively.