The main focus of this paper is on the problem of noisy source coding wherein observed signals from an inaccessible source shall be compressed. To that end, rather than resorting to the conventional methods from Rate-Distortion theory, the so-called Information Bottleneck paradigm is deployed in order to obtain a highly informative representing signal w.r.t. the given source. An efficient, generic and highly flexible graph-based message passing routine for clustering, known as the Affinity Propagation is successfully applied here as a novel treatment for that purpose. The fundamental differences and the performance-wise comparison w.r.t. the state-of-the-art KL-Means-IB algorithm is provided as well.