  Extremal graphical models encode the conditional independence structure of
multivariate extremes. Key statistics for learning extremal graphical
structures are empirical extremal variograms, for which we prove non-asymptotic
concentration bounds that hold under general domain of attraction conditions.
For the popular class of H\"usler--Reiss models, we propose a majority voting
algorithm for learning the underlying graph from data through $L^1$ regularized
optimization. Our concentration bounds are used to derive explicit conditions
that ensure the consistent recovery of any connected graph. The methodology is
illustrated through a simulation study as well as the analysis of river
discharge and currency exchange data.
