l1-Graph Based Music Structure Analysis

Yannis Panagakis, Constantine Kotropoulos, Gonzalo R. ArceISMIR 2011 · OpenReview

Abstract

This paper presents an unsupervised framework for music structure analysis, the task of segmenting a musical recording into semantic sections such as verses and choruses. By modeling music segments as distinct mathematical subspaces and employing sparse representation to construct $\ell_1$-graphs, the proposed method captures high-level relationships between repetitive sections more effectively than traditional pairwise similarity metrics. Experimental results on benchmark datasets demonstrate that combining Auditory Temporal Modulations (ATMs) with $\ell_1$-graph-based segmentation achieves state-of-the-art performance, offering a robust solution for automated music information retrieval.

Introduction

Automatic music structure analysis is a fundamental challenge in Music Information Retrieval (MIR), with significant implications for song summarization, recommendation, and automated remixing. The primary difficulty lies in defining a robust similarity measure that can identify recurring structural elements despite variations in performance or recording noise. Traditional methods typically rely on one-to-one comparisons, such as Euclidean distance, to generate a Self-Similarity Matrix (SDM). However, these metrics often fail to capture the latent global structure of a song. This work addresses these limitations by introducing a "one-to-all" approach based on sparse representation and subspace modeling.

Methodology

The proposed framework consists of a three-stage pipeline: feature extraction, graph construction, and spectral clustering.

  1. Feature Extraction: The authors evaluate three feature types: Mel-Frequency Cepstral Coefficients (MFCCs) for timbre, Chroma for harmonic content, and Auditory Temporal Modulations (ATMs). ATMs are particularly noteworthy as they model the human auditory system's response to both spectral and temporal changes.
  2. $\ell_1$-Graph Construction: This stage represents the core innovation. Assuming that feature vectors from the same musical section lie within the same linear subspace, the similarity between a beat and the rest of the song is determined by solving a sparse optimization problem. Each beat is reconstructed as a sparse linear combination of all other beats, where the non-zero coefficients define the edges of the $\ell_1$-graph.
  3. Spectral Clustering: The resulting graph is partitioned into $K$ clusters using Normalized Cuts, effectively labeling the structural segments of the track.
Comparison of similarity matrices: (a) traditional SDM, (b) l1-graph with MFCCs, and (c) l1-graph with ATMs. The l1-graph with ATMs reveals a clearer block-diagonal structure.

Key Insights: The Subspace Assumption

The effectiveness of the $\ell_1$-graph stems from the "subspace assumption." By treating different musical sections as distinct subspaces, sparse coding naturally selects the most relevant neighbors for a given segment while filtering out noise. This global "one-to-all" reconstruction captures relationships that local pairwise comparisons miss. Furthermore, the study highlights that ATMs are uniquely suited for this subspace approach, producing a cleaner "block-diagonal" similarity structure compared to MFCCs or Chroma, as visualized in the comparison between traditional SDMs and the proposed graph weights.

Results and Performance

The framework was evaluated on the PopMusic and UPF Beatles datasets. As shown in the performance data, the combination of ATMs and $\ell_1$-graph-based segmentation consistently outperformed traditional SDM-based methods and other feature combinations.

Performance comparison of the proposed framework against various baselines across different datasets.

The system achieved a pairwise F-measure of approximately 0.61 on the Beatles datasets, matching or exceeding the performance of existing state-of-the-art unsupervised methods. Notably, the $\ell_1$-graph approach demonstrated superior robustness to audio noise, a common hurdle in real-world MIR applications.

Conclusion

The use of $\ell_1$-graphs and subspace modeling represents a significant advancement in unsupervised music segmentation. While the current method requires a predefined number of clusters ($K$), it provides a highly robust and accurate framework for identifying musical structure. Future work will focus on automatically determining the optimal number of segments and incorporating temporal constraints to further refine segment boundaries.

Summary updated

BibTeX
@inproceedings{panagakis2011l,
  author = {Yannis Panagakis and Constantine Kotropoulos and Gonzalo R. Arce},
  title = {{l1-Graph Based Music Structure Analysis}},
  booktitle = {ISMIR},
  year = {2011},
  url = {https://openreview.net/forum?id=K2s_yVvOgk},
}
Figure