Recent advances in hybrid PET-MRI systems enable simultaneous acquisition of PET and MR data. PET is used to visualize and measure biochemically-specific metabolic processes, but has limited spatial resolution and signal-to-noise ratio. Combining diffusion MRI (dMRI) and PET data, which provide highly complementary information (e.g. structural connectivity and molecular information), has rarely been exploited previously in image postprocessing. The proposed CONNectome-based Non-Local Means (CONN-NLM) exploits synergies between dMRI-derived structural connectivity and PET intensity information to denoise PET data. This method is based on the rationale that structurally-connected voxels and voxels with similar intensity should be highly weighted when smoothing noise.