We present a novel machine learning algorithm for integrating gene expression data with protein-protein, kinase-substrate, and protein-DNA interaction data in order to infer the activity and cross-talk of signaling pathways. Our algorithmic approach combines boosting with an efficient, state-of-the-art graph mining technique to learn subgraphs of the phosphorylome and regulatory protein interaction network whose patterns of expression predict the differential regulation of the target genes of transcription factors. The set of candidate transcription factors that can occupy the promoter of each target is based on genomewide protein-DNA binding data from chromatin immunoprecipitation microarray (ChIP chip) experiments. We learn a global, context-specific, and predictive model of the activation and interaction of signaling pathways and the transcription factors that they control. We demonstrate predictive performance statistically, by showing that the model accurately predicts the differential expression of target genes in held-out gene expression experiments. We also present a case study to show the reconstruction of signaling pathways that controls the transcription factor MSN4 in the stress response in yeast, and we show that the inferred signaling interactions contain the well-known PKA pathway.