Besides the often-quoted complexity of cellular networks, the prevalence of uncertainties about components, interactions, and their quantitative features provides a largely underestimated hallmark of current systems biology. This uncertainty impedes the development of mechanistic mathematical models to achieve a true systems-level understanding. However, there is increasing evidence that theoretical approaches from diverse scientific domains can extract relevant biological knowledge efficiently, even from poorly characterized biological systems. As a common denominator, the methods focus on structural, rather than more detailed, kinetic network properties. A deeper understanding, better scaling, and the ability to combine the approaches pose formidable challenges for future theory developments.