The graph databases claim to be a new proposal within the NoSQL databases. However, network databases emerged several decades ago. But a network is basically a graph.
Ganesh Deka made an interesting answer to this question in the debate on "What is the Difference between RDBMS and NoSQL?" I invited him to write directly in this space.
It appeared that except Graph and Network descriptive models it is possible to find new purely geometrical models for the description of the phenomena in the nature. See, for example:
• A. V. Yurkin, Ray trajectories, binomial of a new type, and the binary system; on binomial distribution of the second (nonlinear) type for big binomial power.//arXiv.org, 1302.4842. New York, 2013.
• A. V. Yurkin, New view on the diffraction discovered by Grimaldi and Gaussian beams.//arXiv.org, 1302.6287, New York, 2013.
One more publication: A. Yurkin. New binomial and new view on light theory. About one new universal descriptive geometric model//Lambert Academic Publishing, 2013. ISBN 978-3-659-38404-2
I am aware that the geometric patterns are easy (or hard) identifiable in nature. In fact, I can identify a graph or a fractal, but what matters is the way we "represent." Thus, it is possible to find a wide range of models for this purpose. But again, the models are the object-oriented, the Entity-Relationship, the Relational, the Hierarchical, including the network model. But the graphs are the underlying mathematical structure of some of them (even the relational model, because I can represent relationships like nodes, and foreign key references as if they were directed arcs, and make graph-based algorithmic analysis). It is for this reason that promoters of graph databases, can say that the initial draft of the domain (perhaps the fact model?) is a "graph", and that the Entity-Relationship model is a graph as well. I think the graph databases are an annealing of the network databases (such as CODASYL) and have a basic problem of concepts.
It is true that the performance of the current SQL databases, begins to degrade as the normalization process deepens. The cause is the required number of joint operations. But remember, SQL is not the relational model, but is based on it. In addition, the relational model is a logical data model and physical representation (which may be based on a graph structure) should be independent. If you take the graph structure as storage strategy, then you will have all the power that possess such mathematical structure.