Synthesizing Composite Hierarchical Structure from Symbolic Music Corpora

1 Introduction

A prevailing theory among Western music theorists and musicologists states that Western classical music exhibits an implicitly hierarchical structure [Simonetta et al., 2018]. While several different theoretical systems have been proposed to formalize this structural hierarchy [Marsden et al., 2013], a widely accepted modern interpretation of the hierarchy states that melodies form the bottom, followed by harmonic contour, rhythmic patterns, disjoint and possibly overlapping motifs, and finally contiguous sections [Nieto, 2015; Mount, 2020; Dai et al., 2024]. Together, this composite hierarchy encapsulates the overall structure of a piece.

To analyze musical structure computationally, many automatic approaches have been developed for extracting structure at single levels of the structural hierarchy [Hsiao et al., 2023; Lev´e et al., 2011; Chen and Su, 2021; Salamon et al., 2014], including methods to analyze sub-hierarchies within a single level [McFee et al., 2017]. However, music perception researchers have shown that the levels are not perceptually independent: they relate to one another in both "vertical" (structural) and "horizontal" (temporal) directions [Narmour, 1983], interactions that have more recently been proven computationally [Dai et al., 2024]. A comprehensive analysis of a piece thus must integrate these inter- and intra-level interactions into a unified model. Furthermore, while attempts have been made to generate structured music [Young et al., 2022; Huang et al., 2023; Wang et al., 2024], to our knowledge, no existing research has examined generating music adhering to a complete, musically representative structural hierarchy, since no mechanism to computationally derive a complete structural specification from a desired music corpus currently exists. Such an encapsulation of music structure could also play a critical role in the generation of well-formed music by serving as a system of constraints on generative models.

Despite prior attempts at such an integrated, computational model of musical form, two challenges remain. First, prior approaches do not completely encapsulate the vertical and horizontal relationships of the structural hierarchy, cannot handle polyphonic music, or are not fully automatic [Hamanaka et al., 2016; Simonetta et al., 2018; Mokbel et al., 2009; Carvalho and Bernardes, 2020]. Second, to our knowledge, existing methodologies focus only on individual pieces with no attempt to summarize the hierarchy over a music corpus to synthesize its overall structure and obtain a holistic representation of the entirety of the corpus.

To address these challenges, we introduce the structural temporal graph (STG) as a unified model of complete musical structure. The STG is a k-partite directed acyclic graph whose levels form the structural hierarchy, and edges encode temporal relationships between adjacent levels. We use simulated annealing to develop a measure of structural distance between two STGs based on graph isomorphism, and to obtain the overarching structure of a corpus of pieces, we develop an approach to derive a representative centroid graph from a corpus of STGs. We formalize centroid derivation as a nested NP-hard combinatorial optimization problem extending the Generalized Median Graph problem [Jiang et al., 2001], and propose a solution combining nested simulated annealing with the formal guarantees of SMT solvers to produce a structurally sound result. Our experiments show that structural distance accurately differentiates pieces, with its performance reliant on the complete hierarchy, and that derived centroids accurately structurally characterize their corpora. 1

In summary, the contributions of this paper are as follows:

1. We propose the structural temporal graph, a metarepresentation of musical form unifying the entire structural hierarchy, and develop a structural distance measure between two STGs rooted in graph isomorphism.
2. We formalize the music summarization problem as a nested NP-hard combinatorial optimization problem, and contribute a novel solution using both stochastic and SMT-based techniques.
3. We conduct experiments verifying structural distance accurately differentiate pieces, and music corpora are accurately characterized by their derived centroids.

2 RelatedWork

Single-Level Analyses. Many existing algorithms extract structure at single levels of the music structural hierarchy. To extract segmentation, The Music Structure Analysis Framework (MSAF) toolkit [Nieto, 2015] features factorizationbased techniques, including ordinal linear discriminant analysis [McFee and Ellis, 2014b], convex nonnegative matrix factorization [Nieto and Jehan, ], checkerboard [Foote, 2000], spectral clustering [McFee and Ellis, 2014a], the Structural Features algorithm [Serr`a et al., 2014], 2D-Fourier Magnitude Coefficients [Nieto and Bello, 2014], and the Variable Markov Oracle [Wang and Mysore, 2016]. Motif discovery algorithms search for disjoint, repeating, and possibly overlapping patterns in a piece. String-based approaches [Wang et al., 2015] represent music as a chromagram and detect patterns with sub-string matching, and geometry-based approaches [Hsiao et al., 2023] represent music as multidimensional point sets, and translatable subsets identify patterns. Recent approaches in harmony identification are centered around neural networks, such as using transformers to incorporate chord segmentation into the recognition process [Chen and Su, 2019; Chen and Su, 2021]. Until very recently, the Melodia algorithm was the state of the art in melody extraction, but recent approaches have shifted to neural networks [Kosta et al., 2022; Chou et al., 2021].

Integrated Models of Structure. Music theorists have attempted to unify the structural hierarchy with frameworks such as Schenkerian theory [Marsden, 2010] and the Generative Theory of Tonal Music (GTTM) [Lerdahl and Jackendoff, 2020]. Schenkerian analysis applies a series of reductions that progressively simplify a musical piece by removing layers of structure. Attempts to automatically derive Scherkerian analyses are intractable for all but very short pieces, and have low accuracy [Marsden, 2010]. GTTM generates four different structural hierarchies (grouping structure, metrical structure, time-span tree, and prolongational tree) for a piece of music, to model human cognition [Hamanaka et al.,

1 Paper code: https://github.com/ilanashapiro/stg optimization

2016]. Computational implementations GTTM (e.g. the Automatic Timespan Tree Analyser [Hamanaka et al., 2016]) cannot handle polyphonic music, and are not fully automatic. Improved results with these theories are unlikely, as neither gives the precision required for complete computational implementation [Marsden et al., 2013].

Such theoretical limitations led to a modern interpretation of the structural hierarchy: segmentation, motifs (disjoint/repeating patterns), rhythm, harmony, and melody [Nieto, 2015; Mount, 2020; Dai et al., 2024]. Many approaches partially encode the hierarchy in graphs: topographic mappings for melodic progressions [Mokbel et al., 2009], graphs for interactions between sections, melody, harmony and rhythm [Dai et al., 2020], multi-edge graphs for bar-level relations [Bhandari and Colton, 2024], and undirected graphs for melodies and their reductions [Orio and Rod`a, 2009]. The prototype graph [Young et al., 2022] is a bipartite network relating prototype elements to the music they represent. Attempts to model the structural hierarchy with formal grammars [Sidorov et al., 2014; Finkensiep et al., ] are limited to segmentation and motifs.

None of these approaches encapsulate the entire hierarchy, and to our knowledge, there have also been no attempts to synthesize representative structure from a music corpus.

3 Structural Temporal Graph

To address the lack of a fully automatic complete encapsulation of polyphonic musical structure, we introduce the structural temporal graph (STG), a unified meta-representation of musical structure that captures the levels of the music structural hierarchy and the temporal relationships between them. The STG is a k-partite directed acyclic graph (DAG), where each of the k layers encodes a level in the music structural hierarchy. 2 Following the modern music theoretic interpretation of the hierarchy [Nieto, 2015; Mount, 2020; Dai et al., 2024], from top to bottom we denote the levels to be contiguous segmentation, motifs (both disjoint and overlapping), rhythmic contour, relative keys, functional harmonic chords, and melodic contour. The STGs we build include every level in the hierarchy except rhythmic contour, for which we were unable to access an analysis algorithm. We run individual analysis algorithms to generate each level of the hierarchy, which is elucidated in Section 6. Before formally defining the STG, we build intuition by walking through the derivation of an STG from an annotated piece.

Building the Graph. We walk through the derivation of an STG from Beethoven's Biamonti Sketch No. 461 that unifies contiguous segmentation; disjoint, overlapping motifs; relative keys; functional harmonic chords; and melodic contour. First, we manually analyze the piece by annotating its score with computer-generated hierarchical structure analyses in Figure 1. Each colored annotation corresponds to one level of the structural hierarchy. In purple, we see that this piece has one large contiguous segment, labeled 0. Next, disjoint motifs are in red. Motif 0 appears twice, at the beginning of bars 1 and 2. The gray filler bar indicates no more motifs appear in the latter half. In orange, we see this piece is in a single key, Eb Major. We label this key symbolically as 0M to indicate this is relative key number 0 (i.e. the first key) in M for major. Subsequent keys would be numbered by their positive interval difference from the previous key within the 12-tone scale. We next see functional harmonic chords in green annotated with Roman numeral chord symbols, and finally melodic contour intervals in blue. Notably, such generated analyses may be slightly inaccurate (e.g. the third green I chord should correspond to the previous beat). Since the STG is a fully automatic meta-representation of musical structure, it is only as accurate as the analysis algorithms it uses.

2 Individual levels themselves can form sub-hierarchies of increasing granularity, which the STG supports

We then equivalently represent the ground-truth annotations in Figure 1 as the stacked rectangles in Figure 2 to elucidate how each level of the structural hierarchy relates to the next. Finally, we transition to the STG in Figure 3. There is a surjection between Figures 1, 2, and 3. The edges and nodes of the STG, respectively, correspond to the vertical and horizontal alignments of the rectangles in Figure 2. All motif nodes, including the gray filler node indicating no motifs for that interval, fall into the time interval of purple segmentation node 0. The orange key node 0M starts in the first red motif node 0, and ends in the last gray motif filler node (i.e. the key spans the entire piece). All the green chord nodes fall in the orange key node's interval. Finally, we see how blue melodic contour nodes relate to green chord nodes. For instance, the first melody interval -2 begins and ends in the first chord node I, and the penultimate melody interval -1 begins in the fourth V7 chord node and ends in the fifth I chord node.

Formally, the nodes of an STG encode labeled musical sections along with their associated time intervals generated by the relevant analysis algorithm. Nodes are sorted within each level based on start time, and edges encode temporal relationships between nodes of adjacent levels. Specifically, for node n at level i, n must have either one or two parents in level i - 1 directly above it: one if its associated time interval is a total subset of its parent's, and two if its time interval begins in one parent's, and ends in the other's.

4 Structural Distance

At a high level, the distance between two STGs is the minimum number of edit operations (deletion, insertion, and substitution of nodes/edges) required to transform one graph to the other, also known as graph edit distance (GED) [Serratosa, 2021]. However, GED measures isomorphic similarity between two graphs, i.e. it evaluates how closely graph structures match independent of labeling. We cannot currently leverage STG isomorphism because STGs are "compressed," with structure encoded in node ids. Specifically, structure is encoded in the defining features of each node id, and in the intra-level linear temporal orderings for each analysis (i.e. the horizontal order of each level in the graph, currently determined by node index). Thus, in order to reason about STGs isomorphically, we must augment them to encode all structural attributes directly within the graph's topology.

To encode element labels, recall that each node id encodes a defining feature set. All nodes can thus be alternatively encoded as instances of their feature prototypes. We create a prototype node for each feature and assign it as a parent of the corresponding instance node(s) with that feature. For instance, segmentation nodes encode a single feature: the section number they correspond to. Finally, to encode intra-level linear temporal relationships, we form a linear chain with edges between pairs of horizontally adjacent nodes. This results in a structurally complete STG we can reason about isomorphically. Figure 4 shows the first two levels of the STG from Figure 3, with yellow prototype nodes on the left for each instance feature (section number for segmentation nodes S, and pattern number and filler for motif/pattern nodes P), red edges connecting prototype features to instance nodes, and green edges for the pattern layer intra-level linear chain.

4.1 Graph Alignment Annealing

GED is a NP-hard combinatorial optimization problem [Serratosa, 2021], intractable for most STGs. Most GED approximation algorithms are slow and of dubious accuracy, and more generalized than we require [Abu-Aisheh et al., 2015]. We thus introduce a new measure of structural distance computed with simulated annealing (SA), a stochastic optimization technique that estimates the global optimum of a discrete cost function. It comprises an objective "energy" function to minimize and a "move" function for generating a new solu-

Algorithm 1 Alignment Annealer Move Function

• 1: function MOVE
• 2: Choose random index i in P
• 3: Choose random index j from the same partition to which i belongs
• 4: Swap rows i and j in P
• 5: end function

tion from the current state. An annealer begins at a high temperature indicating the likelihood of accepting worse solutions to explore the solution space, and ends at a low temperature to refine near-optimal solutions [Guilmeau et al., 2021].

To use SA, we convert the augmented STGs to adjacency matrices, and pad each matrix with zero-arity "dummy nodes" so they have identical dimensions. Given such matrices AG1 and AG2 , their distance is given in Equation 1, where ∥.∥F denotes the Frobenius norm. When AG1 and AG2 are optimally aligned, DIST(AG1 ,AG2 ) is simply √GED.

Finding permutation matrix P optimally aligning AG2 to AG1 to minimize Equation 1 is NP-hard, so we use SA. The alignment annealer's energy function is given in Equation 2. Given optimal P, Equation 2 computes the structural distance between AG1 and AG2 .

The move function for modifying P at each step of SA is given in Algorithm 1. A partition is either the set of instance nodes at a single level in the STG (e.g. the set of functional harmonic key nodes), or the set of prototype nodes for a given feature (e.g. chord quality). Permuting only within valid partitions leverages the STG's inherent structure to avoid invalid moves globally detrimental to Equation 2.

We set the alignment annealer's initial state to P = I, the identity matrix. By running the annealer for sufficiently many steps, we obtain optimal P .

5 Centroid Derivation

Centroid STG derivation is a constrained version of the Generalized Median Graph (GMG) problem, which, given a set of graphs, seeks to construct a prototype graph minimizing the distances over the input set graphs [Blumenthal et al., 2021]. Formally, given a corpus of graphs C, the GMG g is:

1. No self-loops
2. No instance-prototype or prototype-prototype edges
3. No edges from a prototype to an instance whose feature set does not include the proto feature (e.g. melody interval sign proto-segmentation instance)
4. No edges from lower to higher level instance levels (must respect the hierarchy)
5. No edges between non-adjacent instance levels (must respect k-partite structure)

Table 1: Global Constraints

where d is the distance measure. GMGs have wide applications in representation-based learning, particularly in biological settings [Mukherjee et al., 2009]. Prior attempts at the GMG use genetic search [Jiang et al., 2001], linear programming[Mukherjee et al., 2009], block coordinate updates [Blumenthal et al., 2021], and median graph shift clustering [Jouili et al., 2010]. To our knowledge, GMGs have never been applied to the music domain. Centroid STG derivation also operates in a significantly more constrained search space than the canonical GMG, since the centroid must be a well-formed STG. We thus propose a new approach combining nested simulated annealing with SMT solving.

5.1 Bi-Level Simulated Annealing

Given padded adjacency matrix Ag for an augmented centroid STG and its associated corpus of matrices C = {AG} that are optimally aligned to Ag, we seek to minimize LOSS in Equation 4, where DIST is as in Equation 1.

The centroid annealer's energy function is given in Equation 5, where Caligned is the corpus aligned to the current centroid Ag, a process itself requiring SA as in Section 4.1 to obtain the optimal alignments. Finding the centroid Ag minimizing Equation 4 is thus a nested NP-hard problem (GED and minimizing over these distances) requiring nested SA.

As the centroid annealer's temperature cools, the loss converges as the centroid is increasingly closely aligned to its corpus. Thus, as the centroid annealer's temperature cools, we scale down the number of steps and max temperature of the nested alignment annealer. 3

The centroid annealer's move function for modifying the centroid Ag at each step of SA is given in Algorithm 2. To move strategically, we build the score matrix S revealing which edge(s) in Ag contribute most to the loss. We add or remove the edge at a highest score coordinate meeting the criterion in Algorithm 2. In particular, a globally structurally invalid move induces a terminally invalid structure in the centroid by violating one of the rules in Table 1. Some locally invalid moves, however, such as removing an edge in an intralevel linear chain, must be allowed as intermediate steps to a

3 See Appendix A on arXiv (https://arxiv.org/abs/2502.15849) for precise cooling schedule

Algorithm 2 Centroid Annealer Move Function

• 1: function MOVE
• 2: Calculate the list of absolute difference matrices DL = [|Ag - AGi | for AGi ∈ Caligned]
• 3: Calculate the element-wise sum-of-distances score matrix. Higher score at coord (i, j) means that coord has a higher impact on the loss
• 4: Flatten X and sort in descending score order
• 5: Partition Xflat by unique score, and shuffle each partition randomly (increases variability of moves)
• 6: Iterate through the indices (i, j) of the sorted, partition-shuffled Xflat. Stop at the first (highest score) (i, j) such that flipping the (i, j) edge in Ag is not:
• a globally structurally invalid move
• a move undoing the most recently accepted move (avoid oscillating states)
• a move the annealer has already locally rejected since the last accept (avoid getting stuck)
• 7: Execute move: Ag[i, j] = 1-Ag[i, j]

8: end function

more optimal structurally valid state. Importantly, the STGs being compared must have the same number of levels; otherwise, edges spanning multiple levels must be allowed as they can be intermediate states towards the deletion of an entire level. Based on our experiments, this would be unacceptably detrimental to the performance of the annealer.

We set the centroid annealer's initial state Ag to the corpus STG in the corpus with the min loss over the rest of the corpus. Running the annealer for sufficient steps gives an approximate centroid that may contain locally invalid states.

5.2 Graph Repair with SMT Solving

In order to obtain a structurally sound centroid, we must "repair" the approximate centroid Ag by projecting it to the nearest valid STG. We achieve this by encoding the STG's structure as constraints in quantifier-free first-order logic formulae in the SMT (satisfiable modulo theory) solver Z3 [De Moura and Bjørner, 2008], which gives us formal guarantees on the soundness of the centroid. We use Z3's optimizer to minimize an objective over the constraints. Given approximate centroid Ag and valid centroid A′g , our objective is Equation 6.

Our constraints include the global rules in Table 1, as well as additional constraints for instance nodes in Table 2, and finally prototype nodes in Table 3. We model relationships between nodes with uninterpreted functions.

Z3's optimizer supports integration with large neighborhood search (LNS) and can return intermediate semioptimized solutions after a timeout. We run the optimizer with LNS, with initial soft constraints set to the approximate centroid Ag to guide the optimizer. Even so, naively running

4 Segmentation, keys, chords, and melody, but not motifs

5 Segmentation, keys, and chords only

1. Every instance node must have 1 or 2 instance parents in the level above
2. The instances nodes at level l must form a linear chain/total ordering via intra-level edges
3. The start and end nodes of the linear chain must have the previous level linear chain's start and end nodes, respectively, as parents.
4. In instance levels with non-overlapping nodes, 4 the first parent of a node at linear chain index i > 0, must not come before node i - 1's last parent in the previous instance level's linear chain
5. The first parent of an instance node at linear chain index i > 0, must not come before node i -1's first parent in the previous level's linear chain

Table 2: Instance Constraints

1. Every instance node must have exactly one prototype parent per feature
2. For levels that require it, 5 no two linearly adjacent instance nodes can have identical prototype parent sets

Table 3: Prototype Constraints

the optimizer on a full STG is generally intractable due to combinatorial explosion, so we partition Ag into subsets we can apply the constraints to incrementally.

We first partition Ag into pairs of consecutive instance levels without their prototypes (e.g. a segmentation/motif pair of instance levels), and optimize the instance constraints in Table 2 and relevant global constraints in Table 1 over each partition incrementally. We combine the results of each partition until we build a valid centroid subgraph of instance nodes. Then, we partition Ag into single levels, each containing the instance nodes of that level and all prototype nodes for each instance feature at that level (e.g. segmentation instance nodes + section number prototype nodes). The instance constraints are already optimized; we need only optimize the prototype constraints in Table 2 and relevant global constraints in Table 1 over the possible prototypes. This gives us the complete, structurally sound centroid A′g we seek. 6

6 Experiments

We conduct experiments to verify that: (1) structural distance accurately differentiates individual pieces, with its performance reliant on the complete hierarchy, and (2) the centroid encapsulates the overarching structure of its corpus.

To evaluate our approach, we create a dataset of polyphonic, symbolic MIDI piano music from the Kunstderfuge and Classical Piano MIDI datasets.Since some single-level analyses we use to generate STGs require the data to be in audio and CSV format, we convert MIDI to CSV (with a manual script) and to MP3 (with Fluidsynth).

We then generate an STG for each piece. For segmentation, we use the flat Structural Features algorithm [Serr`a et al., 2014] for segment boundaries and 2D-Fourier Magnitude Coefficients [Nieto and Bello, 2014] for segment labels, both of which are provided by the Music Structure Analysis Framework [Nieto, 2015]. For motifs, we use the BPS-motif discovery algorithm [Hsiao et al., 2023], and for relative keys and functional harmonic chords we use the pretrained Harmony Transformer V2 [Chen and Su, 2021]. Finally, for melodic contour, we use the Melodia algorithm [Salamon et al., 2014].

6 See Appendix B on arXiv for centroid derivation visualization

6.1 Structural Distance Evaluation

Mathematical Verification. Given two STGs G1,G2 recall that under optimal alignment, DIST(AG1 ,AG2 ) is √GED. To evaluate our alignment annealer, we set G1 with |E1| edges as the "base graph." From G1, we generate a series of STGs G2 by randomly adding ⌈|E1| · p⌉ valid edits to G1 (add/remove edge, verified with Section 5.2 Z3 solver), where p ∈ {0.1, 0.2, . . . , 3} (i.e. p ranges from 10-300% edits in the size of |E1|). We evaluate structural distance as a function of p for five base STGs G1 by computing the relative error from experimental DIST(AG1 ,AG2 ) to ground truth structural distance √⌈|E1| · p⌉ (Figure 5). Relative error is close to 0 (perfect alignment) for p < 1.8, and only deteriorates, at worst, to 10.33% at p = 3 for the Beethoven 461 base graph.

Musical Evaluation. To verify structural distance accurately differentiates pieces, we construct 210 STG sets from 32 pieces by J.S. Bach (21), Mozart (2), Beethoven (3), Schubert (2), and Chopin (4). Each set is a unique combination of 5 pieces, one from each composer, such that a piece's duration is within 7 seconds of any other piece in the set, since structural distance between disparate length pieces could be due to STG size differences rather than the local structural variations we aim to distinguish. 7 We compute pairwise structural distances between the STGs in each set with our Section 4 graph alignment annealer (2000 iterations, max and min temperature of 2 and 0.01) on 8 Nvidia RTX 2080 GPUs with 11GB RAM. This results in 210 structural distance matrices, which we average to a single mean distance matrix.

We evaluate structural distance against three baselines over the same 210 piece combinations. Baseline 1 is the mean distance matrix obtained by taking the cosine similarity between feature vectors extracted from each MIDI file using Music21. Baseline 2 is the mean distance matrix over pairwise Stent weighted audio similarities (SWAS) for each piece's paired MP3 file. SWAS is a composite audio similarity metric comprising zero-crossing rate, rhythm, chroma, spectral contrast, and perceptual similarity metrics, which we weigh equally. To demonstrate existing graph comparison metrics are insufficient, Baseline 3 is the Weisfeiler-Lehman (WL) Kernel applied pairwise to the STGs in each set, with five iterations and Neighborhood Hash (NH) as the base kernel. The WL Kernel iteratively refines node labels based on their neighbors, and uses a base kernel (in this case, NH, which efficiently captures local graph structure by distinguishing neighborhood configurations) to compare them [Shervashidze et al., 2011]. Our ground-truth is the stylistic similarity indices between composers using human annotations and metadata from "The Classical Music Navigator" [Smith and Georges, 2014].

7 See Appendix C on arXiv for input pieces/sets details

We normalize all matrices to [0, 1] range and apply the Mantel test with Spearman's rank correlation coefficient ρs to evaluate our results against the ground-truth similarity from the Classical Music Navigator (Table 4). ρs is highest (with p < 0.05) for structural distance (SD in Table 4), verifying that structural distance accurately differentiates between pieces and captures human conception of musical similarity.

Finally, to verify the importance of the full hierarchy, we repeat this experiment with bottom-up level ablations of the STG (Table 5). The structural distance algorithm's performance incrementally declines each time a layer of the STG is removed, confirming the necessity of the complete hierarchy.

6.2 Centroid Evaluation

Mathematical Verification. As a correctness check, we evaluate derived centroids against constructed ground truth centroids. Given base STG g with |E| edges, we create a synthetic corpus Ck of k STGs by randomly adding ⌈ |E| 2 ⌉ valid edits to g, k times, as in Section 6.1. By construction, g must be a true centroid with min possible loss over Ck (Equation 4). 8 We derive candidate centroid gd from Ck, and compare to g. We evaluate gd against the naive centroid gn, i.e., the STG already in Ck with min loss over the rest of Ck.

8 Proof in Appendix D on arXiv

We choose our base STG g to be Beethoven's Biamonti Sketch No. 461, which, when augmented, has |E| = 97 edges. Thus, we add ⌈ 97 2 ⌉ = 49 edits to g, k times, to generate a synthetic corpus Ck of size k with g as its true centroid. 49 edits is structural distance of 7.0, since structural distance between optimally aligned graphs is √GED (Equation 1).

We repeat this process for k ∈ [3, 14]. For each corpus Ck, we use the same GPU infrastructure as Section 6.1 to generate approximate centroids with the centroid annealer (1000 iterations, max and min temperature of 2.5 and 0.05). At each iteration, we run the nested graph alignment annealer, starting at 500 steps, max and min temperature of 1 and 0.01, and ending at 5 steps, max and min temperature of 0.05 and 0.01, as the outer centroid annealer's loss converges (see Section 5.1). We run our Z3 optimizer to generate each final, repaired centroid gd, using 24 Intel Xeon cores and 32GB RAM.

There may be multiple non-isomorphic true centroids with the same minimal loss over Ck. Evaluating the relative error between optimal loss from g and experimental loss from gd thus gives a more rigorous assessment of gd than directly comparing gd to g. Figure 6 shows the relative error in loss Eg gd between g and gd for k ∈ [3, 14] in red, compared to the relative error in loss Eg gn between g and gn in blue. We observe Eg gd is consistently small, with max Eg gd = 2.99% at k = 5, and min Eg gd = 0 (i.e. gd is a true centroid) at k = 10, 11. gd also greatly outperforms gn: for nonzero Eg gd , Eg gn is on average 17.23 times worse than Eg gd .

Musical Evaluation. This experiment requires pieces with more length (and STG size) variation than Section 6.1, as centroids derived from very similar input graphs may be trivial by construction and fail to generalize to more diverse corpora. We thus relax the Section 6.1 relative duration restriction to 80 seconds, and generate centroid STGs for four corpora with pieces by Alkan (11), Chopin (8), Haydn (12), and Mozart (14) with the same architecture as before. 9

To verify each derived centroid g musically characterizes its corpus C, we use rustworkx [Treinish et al., 2022] to enumerate the set of all 5-node subgraphs ({S5}) common to every STG in C, thus extracting the most structurally salient musical relationships in C. 10 For each C, we evaluate the percentage of the graphs in {S5} that are also subgraphs of g; i.e.

9 See Appendix C on arXiv for input pieces details

10 Larger subgraphs encode more robust relationships, but mining k-node subgraphs for k > 5 was intractable, and approximate subgraph mining tools were too imprecise for meaningful conclusions

we evaluate how well g captures the most structurally salient musical relationships in C (Table 6). On average, 70.33% of each {S5} aligns perfectly with g, confirming each centroid captures the musically essential information of its corpus. To visualize these essential musical substructures, consider a 5node subgraph common to the Mozart corpus and captured in its centroid (Figure 7). This reveals that a characterizing feature of the Mozart corpus is two consecutive major chords in the same major key, which in turn falls in a motif/pattern.

7 Conclusion and FutureWork

We presented the structural temporal graph (STG) to encapsulate complete, hierarchical musical structure; a measure of structural distance between STGs; and an algorithm to derive a centroid STG structurally representing a music corpus. We showed structural distance and derived centroids both mathematically approximate ground truth; structural distance accurately differentiates music pieces; and derived centroids capture the essential structural relationships of their corpora.

The STG and derived centroids lay the groundwork for structured, controllable sequence data generation. For example, users could modify the STG of a generated music piece to update constraints on a generative model. Beyond music, the STG can model structural hierarchies for any sequence data given algorithms for analyses at each level. For instance, an STG could encode a poetry hierarchy-verses, stanzas, lines-with its centroid structurally summarizing the poetry corpus. Such applications enable human refinement of machine-generated data to meet desired structural specifications across fields.

Acknowledgments

This work is supported by National Science Foundation grants #1955457, #2220892, #2146151, and #2200333, and by the European Research Council under Europe's Horizon 2020 program, grant #883313 (ERC REACH).