What is meant by "non-perturbative" string theory? I often hear people talk about finding a non-perturbative formulation of string theory. 
What does this mean exactly? To my knowledge string theory is a perturbative method. Just like Feynman graphs are a perturbative method. But people don't talk about a non-peturbative formulation of Feynman graphs. (Or do they?)
If someone found a theory to which could be calculated with the perturbation method of strings. Should this theory really be called a "string theory"? Wouldn't it be a different separate theory? What properties would this theory have, and how do we know some theory like Supergravity isn't this theory?
 A: "But people don't talk about a non-peturbative formulation of Feynman graphs. (Or do they?)"
Actually sometimes they do. It is common in quantum theory to apply variational techniques to approximate a ground state configuration and there are some QFT methods that make use of this approach.  They are equivalent to summing a subset of the associated Feynman diagrams to infinite order and are thus refered to as nonperturbative methods.  In many body physics these are sometimes called mean field methods.
A: In the case of Yang-Mills theory, QCD for example, we have a complete (non-perturbative) formulation of the theory in terms of the Lagrangian and the path integral. Feynman diagrams are then a perturbative method to calculate scattering amplitudes, but you can perform non-perturbative calculations by doing lattice QCD for example.
The formulation of string theory from the world sheet is inherently perturbatively stated in terms of an expansion in the string coupling. It gives the prescription for calculating the S-matrix in perturbation theory, but does in a sense not explicitly tells us fundamentally which theory we are dealing with. 
Likewise the 10D Lagrangians one works with in string theory are only low-energy effective Lagrangians, namely supergravity.
The approaches to understanding the non-perturbative formulation of string theory would seem to go through M/F-theory and string field theory. 
A: Feynman graphs are perturbative. If you wish to discuss Non-Perturbative QFT, a Perturbative Expansion should not be brought up. An equivalent statement to Feynman graphs in QFT is a worldsheet approach to SST. Non-perturbative approaches to SST are: M-theory (or F-theory), matrix models, field theory, etc. In summary, "what is meant by non-perturbative SST" is equivalent to asking "what is meant by non-perturbative QFT" in a more specific context. If you are unfamiliar with the answer to the general question regarding the case of non-perturbative QFTs, I am unsure of why at all you are asking it in the case of SSTs.

For further readings on the topic of non-perturbative SST, a brief introduction is given in the text "An Introduction to Non-Perturbative String Theory" [Ashoke, S. 98]. For readings in the seminal papers introducing non-perturbative effects, "Combinatorics of coundaries in String Theory" [Polchinski, J. 94], "Five-Branes, Membranes and Non-Perturbative String Theory" [Strominger, A. et all. 95], "String Theory Dynamics in Various Dimensions" [Witten, E. 95], "Evidence for F-theory" [Vafa, C. 96], "Proposals on Non-Perturbative Superstring Interactions" [Motl, L. 97] and "Matrix String Theory" [Verlinde, E. 97], "Noncommutative Geometry and String Field Theory" [Witten, E. 86] and "Introduction to String Field Theory" [Siegel, W. 01], etc. respectively. In some cases I could not recall the original text and instead listed introductory resources on the subject. 
