Anatomical labeling of the cerebral arteries forming the Circle of Willis (CoW) enables inter-subject comparison, which is required for geometric characterization and discovering risk factors associated with cerebrovascular pathologies. We present a method for automated anatomical labeling of the CoW by detecting its main bifurcations. The CoW is modeled as rooted attributed relational graph, with bifurcations as its vertices, whose attributes are characterized as points on a Riemannian manifold. The method is first trained on a set of pre-labeled examples, where it learns the variability of local bifurcation features as well as the variability in the topology. Then, the labeling of the target vasculature is obtained as maximum a posteriori probability (MAP) estimate where the likelihood of labeling individual bifurcations is regularized by the prior structural knowledge of the graph they span. The method was evaluated by cross-validation on 50 subjects, imaged with magnetic resonance angiography, and showed a mean detection accuracy of 95%. In addition, besides providing the MAP, the method can rank the labelings. The proposed method naturally handles anatomical structural variability and is demonstrated to be suitable for labeling arterial segments of the CoW.