MOTIVATION: Understanding the molecular mechanisms of thermal stability is a challenge in protein biology. Indeed, knowing the temperature at which proteins are stable has important theoretical implications, which are intimately linked with properties of the native fold, and a wide range of potential applications from drug design to the optimization of enzyme activity. RESULTS: Here, we present a novel graph-theoretical framework to assess thermal stability based on the structure without any a priori information. In this approach we describe proteins as energy-weighted graphs and compare them using ensembles of interaction networks. Investigating the position of specific interactions within the 3D native structure, we developed a parameter-free network descriptor that permits to distinguish thermostable and mesostable proteins with an accuracy of 76% and area under the receiver operating characteristic curve of 78%. AVAILABILITY AND IMPLEMENTATION: Code is available upon request to [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.