Introduction
Traditionally, cover song identification has been framed as a standard information retrieval (IR) task: given a query song, the system returns a ranked list of potential covers. However, this approach often ignores the inherent "collaborative" relationships between songs. If Song A is a cover of Song B, and Song B is a cover of Song C, then Song A and Song C are also related. This paper, presented at ISMIR 2009, proposes a paradigm shift by treating cover song identification as a community detection problem. By grouping songs into "cover sets," the authors demonstrate significant improvements in retrieval accuracy and provide a method for identifying the "original" version within a set.
Methodology
The authors evaluate several unsupervised grouping strategies to detect cover sets without prior knowledge of the number of sets or their sizes. These strategies are categorized into three main types:
- Classical Clustering: Testing standard algorithms like K-medoids and Hierarchical Clustering (Single Linkage, Complete Linkage, UPGMA, and WPGMA).
- Proposed Network Methods: Introducing three methods based on complex networks where songs are vertices and edges represent high similarity. These methods utilize "triangular coherence" to reinforce connections between related songs and reduce uncertainty.
- Modularity Optimization: A technique borrowed from social network analysis to find community structures in large graphs.
Identifying the Original Song
To identify the original version, the authors employ the concept of a medoid: the song within a detected set that has the minimum average distance to all other songs in that set. The hypothesis is that the original song acts as the "musical prototype" or geometric center from which other versions deviate.
Experimental Evaluation
The study utilized both artificial and real-world data. Artificial distance matrices with varying levels of Gaussian noise were used to stress-test robustness. The real-world evaluation used a collection of 2,135 songs, including 525 cover sets. For the original identification task, 426 original versions were manually verified.
Results and Discussion
Accuracy Boost
Using cover set detection as a post-processing step significantly improves Mean Average Precision (MAP). As shown in Figure 3, the relative MAP increase can reach up to 25% on artificial data, particularly as the number of covers per set ($C$) increases. On real-world data, the approach provided a 13.6% relative increment in accuracy over standard IR baselines.
Scalability and Performance
While hierarchical methods like UPGMA and WPGMA performed best for set detection under noise, they require full $N \times N$ distance matrices, which are computationally expensive. The proposed network-based methods (PM1, PM2, PM3) are nearly as accurate but offer better scalability. Figure 1 illustrates the computational time across different experimental setups, highlighting the efficiency of the network-based approaches for larger datasets.
Original Identification
The medoid-based approach correctly identified the original song in 50-70% of cases. This is a substantial improvement over the random-choice baseline (~16-25%), supporting the theory that the original version often serves as the central reference point for a cover set.
Conclusion
This research demonstrates that moving from a query-retrieval framework to an unsupervised clustering approach can "fix" errors in distance measurements by leveraging collaborative relationships. While the medoid-as-original assumption is an oversimplification—as a very popular cover might displace an obscure original—the results suggest that community detection is a powerful tool for improving the coherence and accuracy of Music Information Retrieval systems.
Summary updated