An approach to study population differences in cerebral vasculature is proposed. This is done by 1) extending the concept of encoding cerebral blood vessel networks as spatial graphs and 2) quantifying graph similarity in a kernel-based discriminant classifier setup. We argue that augmenting graph vertices with information about their proximity to selected brain structures adds discriminative information and consequently leads to a more expressive encoding. Using graph-kernels then allows us to quantify graph similarity in a principled way. To demonstrate our approach, we assess the hypothesis that gender differences manifest as variations in the architecture of cerebral blood vessels, an observation that previously had only been tested and confirmed for the Circle of Willis. Our results strongly support this hypothesis, i.e, we can demonstrate non-trivial, statistically significant deviations from random gender classification in a cross-validation setup on 40 healthy patients.