The fast-growing networked computing devices create many distributed systems and generate new signals on a large scale. Typical applications include peer-to-peer streaming of multimedia data, crowdsourcing, and measurement by sensor networks. Therefore, the massive amount of networked data is a form of big data, calling for new data structures and algorithms different from classical ones suitable for small data sizes. We consider a vital data format for recording information from networked distributed systems: signals on graphs. A significant concern is to protect the privacy of large scales of signals when processed at third parties, such as cloud data centers. A de-facto solution is to outsource encrypted data before they arrive at the third-parties. We propose a novel and efficient privacy-protected outsourced denoising algorithm based on the information-theoretic secure multi-party computation (secure MPC). Among the operations of signals on graphs, denoising is useful before further meaningful processing can occur. The experimental results demonstrate good efficiency of our approach compared to others.