Given the huge size of music collections available on the Web, automatic genre classification is crucial for the organization, search, retrieval and recommendation of music. Different kinds of features have been employed as input to classification models which have been shown to achieve high accuracy in classification scenarios under controlled environments. In this work, we investigate two components of the music genre classification process: a novel feature vector obtained directly from a description of the musical structure described in MIDI files (named as structural features), and the performance of relational classifiers compared to the traditional ones. Neither structural features nor relational classifiers have been previously applied to the music genre classification problem. Our hypotheses are: (i) the structural features provide a more effective description than those currently employed in automatic music genre classification tasks, and (ii) relational classifiers can outperform traditional algorithms, as they operate on graph models of the data that embed information on the similarity between music tracks. Results from experiments carried out on a music dataset with unbalanced distribution of genres indicate these hypotheses are promising and deserve further investigation.