The very few basic principles of relativity and quantum mechanics like the frame independence of the speed of light and unitarity put very strict constraints on possible theories, for example only particles with spin 0, 1/2, 1, 3/2 and 2 are possible. String theory on the other hand turned out to allow a ridicules large number - like 10 to the 500 - of different vacuum states and therefore you can have more or less whatever you want by fixing parameters in this way or another.
I may of course be totally wrong but that were my first thoughts, unless you can somehow derive a lot of constraints, using graphs to explain the universe seems a way to general idea to me. But again, I never read anything about Wolfram's ideas, at least nothing I can remember.
Prior to reading his proposal, I likely would have agreed with you that ontology is lost; I'm less sure now. After reading his ideas, I see a glimmer of hope for discovering a small, simple set of primitives and rules for modeling the universe. A graph/knot-based theory would be composed of far more simple primitives than differential equation based theories; the more abstract differential equation models would arise through statistical mechanics.
By the way, I think in some sense space is already discrete in QM. E.g. for a particle in a box you have a discrete set of states.
1. I started my PhD doing quantum information. People in quantum information spend a lot of time thinking about properties of entanglement. Someone below mentioned "a lack of new ideas". There have been quite a few important ideas in AdS/CFT (as a subset of string theory) over the past decade. One of the most exciting is called the Ryu-Takayanagi conjecture and it relates the amount of entanglement in a subsystem to the area of a minimal surface bounding said subregion.
2. Again, as someone who started purely as a QI person, it's shocking how much of the MATH of string theory has entered my research.
3. In my opinion, it's true that string theory hasn't made much progress over the past 20 years or so towards elucidating its potential role as a theory of quantum gravity; but in parallel there are amazing connections being made between string theory and quantum information. Look at the work being done by the "It from Qubit" collaboration for a sampling. This latter point is ~equally related to the recent decoherence of string theory as a subdiscipline. It's more like it tunneled to a state closer to QI.
4. The Firewall paradox is fascinating and it was originated by a bunch of string theorists (Almheiri, Marolf, Polchinski and Sully.)
5. Supersymmetry is in a corner; which is bad for string theory. But string theory is proving to be a powerful lens through which to study quantum entanglement. One step back, one step forward?
Anyways, saying that "string theory is our savior" or anything like that is bad etiquette. But the community is doing interesting things today.