Synthesizing Composite Hierarchical Structure from Symbolic Music Corpora

Ilana Shapiro, Ruanqianqian (Lisa) Huang, Zachary Novack, Cheng-i Wang, Hao-Wen Dong, Taylor Berg-Kirkpatrick, Shlomo Dubnov, Sorin Lerner

Abstract

Western music is characterized by a complex, multi-layered hierarchy ranging from individual notes to large-scale formal sections. Traditional computational models often fail to capture the vertical and horizontal interactions between these layers or provide a means to summarize the structural "template" of a corpus. This paper introduces the Structural Temporal Graph (STG), a k-partite directed acyclic graph designed to represent these hierarchies. By leveraging simulated annealing for graph alignment and Satisfiability Modulo Theories (SMT) for structural repair, the authors develop a robust metric for structural distance and a method for synthesizing "centroid" graphs that represent the structural DNA of a musical collection. Experimental results demonstrate that the STG-based distance metric correlates strongly with human stylistic perception ($\rho_s = 0.8207$) and accurately recovers structural signatures from mutated data.

Introduction

Music analysis has long struggled with the "integration problem": while algorithms exist to detect beats, motifs, or harmonic progressions in isolation, they rarely account for how these layers interact. A motif is not just a sequence of notes; it is a rhythmic pattern situated within a specific harmonic context, which in turn belongs to a larger formal section like a verse or chorus. Furthermore, there is a lack of mathematical tools to describe the "average" structure of a musical corpus—the shared structural template that defines a composer's style or a specific genre.

Methodology: The Structural Temporal Graph

The core contribution of this research is the Structural Temporal Graph (STG). The STG is a $k$-partite directed acyclic graph where each level represents a different structural granularity, such as sections, motifs, chords, and melodic intervals. Edges in the graph represent temporal containment and sequence, capturing both the "vertical" hierarchy and "horizontal" progression of the music.

Figure 3: Mapping the hierarchical layers of the STG (sections, chords, intervals) onto a musical score.

To compare two musical pieces, the authors calculate a Structural Distance based on Graph Edit Distance (GED). Because finding optimal alignments between complex graphs is NP-hard, the researchers employ Simulated Annealing (SA), a stochastic optimization technique, to find near-optimal alignments that minimize the difference between STGs.

Centroid Derivation and Graph Repair

To summarize a corpus, the authors seek a "centroid" graph—a single STG that minimizes the total distance to all other graphs in the set. This process involves a nested optimization problem. To ensure that the resulting "average" graph is musically logical (e.g., ensuring a chord does not start before the section it belongs to), the Z3 SMT solver is used to "repair" the graph, enforcing strict global and musical constraints.

Experimental Results

The researchers evaluated their framework using polyphonic MIDI datasets from composers such as J.S. Bach, Mozart, and Beethoven.

Stylistic Similarity

The STG-based distance metric achieved a Spearman’s rank correlation ($\rho_s$) of 0.8207 when compared against ground-truth stylistic similarity indices. This significantly outperformed baseline methods, including standard MIDI feature extraction (0.4681) and audio-based similarity metrics (0.5775). Ablation studies further revealed that removing hierarchical layers significantly reduced the model's ability to differentiate between composers, suggesting that musical style is emergent from the interaction between levels.

Mathematical Robustness

In controlled "mutation" tests, the algorithm demonstrated a high capacity to recover an original structural signature. By applying random mutations to a known graph and then attempting to derive the centroid, the researchers found that the relative error remained near zero for moderate mutation levels across various compositions.

Figure 5: Relative error in centroid recovery across different mutation levels (p) for various musical works.

Conclusion

The STG framework provides a powerful new way to map the "DNA" of musical structure. By combining the flexibility of simulated annealing with the logical rigor of SMT solvers, the authors have created a tool that can both analyze individual works and synthesize representative templates for entire corpora. Future work may explore the generative potential of these graphs, using them as structural constraints for AI-driven composition to ensure outputs maintain human-like hierarchical sophistication.

Summary updated

Abstract

Western music is an innately hierarchical system of interacting levels of structure, from fine-grained melody to high-level form. In order to analyze music compositions holistically and at multiple granularities, we propose a unified, hierarchical meta-representation of musical structure called the structural temporal graph (STG). For a single piece, the STG is a data structure that defines a hierarchy of progressively finer structural musical features and the temporal relationships between them. We use the STG to enable a novel approach for deriving a representative structural summary of a music corpus, which we formalize as a dually NP-hard combinatorial optimization problem. Our approach first applies simulated annealing to develop a measure of structural distance between two music pieces rooted in graph isomorphism. Our approach then combines the formal guarantees of SMT solvers with nested simulated annealing over structural distances to produce a structurally sound, representative centroid STG for an entire corpus of STGs from individual pieces. To evaluate our approach, we conduct experiments verifying that structural distance accurately differentiates between music pieces, and that derived centroids accurately structurally characterize their corpora.
BibTeX
@inproceedings{shapiro2025synthesizing,
  author = {Ilana Shapiro and Ruanqianqian (Lisa) Huang and Zachary Novack and Cheng-i Wang and Hao-Wen Dong and Taylor Berg-Kirkpatrick and Shlomo Dubnov and Sorin Lerner},
  title = {{Synthesizing Composite Hierarchical Structure from Symbolic Music Corpora}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/1128},
}
Figure