Accurate segmentation of the first and second heart sounds (S1 and S2) in phonocardiogram (PCG) recordings is essential for automated cardiac analysis. While deep learning approaches such as CNN-LSTM achieve high segmentation performance, they rely on large numbers of trainable parameters and often lack interpretability. This raises the question of whether an effective preprocessing strategy can enable simpler, low-complexity models without compromising performance. In this work, we propose a pipeline combining a graph learning-based denoising method with a Logistic Regression–Hidden Semi-Markov Model (LR-HSMM) for interpretable and computationally efficient heart sound segmentation. The denoising leverages two intrinsic properties of heart sounds: (i) quasi-periodicity of S1 and S2 across successive heartbeats, and (ii) temporal sparsity, as these events occupy short time intervals within each cardiac cycle. These properties allow the denoising problem to be formulated as a constrained low-rank matrix inference problem, with constraints promoting both sparsity and pseudo-periodicity. This pseud-periodicity property led to model S1 and S2 as graph signals that are smooth over a latent graph structure learned directly from the data, highlighting coherent heartbeats in the available recordings. Segmentation is then performed using five envelope features: Hilbert, homomorphic, wavelet, power spectral density, and Shannon. The proposed pipeline was evaluated on the CirCor DigiScope dataset (3,163 recordings from 943 patients) using subject-stratified 10-fold cross-validation. Without denoising, LR-HSMM achieved an accuracy of 0.830 and an F1-score of 0.819, compared to 0.931 and 0.923 for CNN-LSTM. With graph-based denoising, LR-HSMM improved to 0.907 accuracy and 0.891 F1-score, with SNR gains of 5.18% for S1 and 7.94% for S2. For murmur classification, the proposed pipeline outperformed both baseline methods, achieving an accuracy of 0.751 and an F1-score of 0.731.