The analysis of human brain connectivity networks has become an increasingly prevalent task in neuroimaging. A few recent studies have shown the possibility of decoding brain states based on brain graph classification. Graph kernels have emerged as a powerful tool for graph comparison that allows the direct use of machine learning classifiers on brain graph collections. They allow classifying graphs with different number of nodes and therefore the inter-subject analysis without any kind of previous alignment of individual subject's data. Using whole-brain fMRI data, in this paper we present a method based on graph kernels that provides above-chance accuracy results for the inter-subject discrimination of two different types of auditory stimuli. We focus our research on determining whether this method is sensitive to the relational information in the data. Indeed, we show that the discriminative information is not only coming from topological features of the graphs like node degree distribution, but also from more complex relational patterns in the neighborhood of each node. Moreover, we investigate the suitability of two different graph representation methods, both based on data-driven parcellation techniques. Finally, we study the influence of noisy connections in our graphs and provide a way to alleviate this problem.