I'm not sure if your question is easy to answer, but I will try to provide an intuition. I am not an expert in non-negative matrix factorisation so I can't explain the connections there. 

Let's restrict out attention to simple, undirected graphs $G$ with $n$ vertices. I will assume by low-rank you mean, low-rank of the adjacency matrix.  These properties are derived from [here][1] Here's are a characterisation low-rank graphs: 

- the graph with no vertices is the only graph with rank 0 
- a complete bipartite graph is the only connected graph with rank 2  
- a complete tripartite graph is the only connected graph with rank 3

Rank is known to be preserved between subgraphs as follows:

- if H is an induced subgraph of G, then $rank(H) \leq rank(G) $.
- Let $G = G1 \cup G2 \cup··· \cup G_n$, where $G_1, G_2,...,G_n$ are connected components of G, then $rank(G) = \sum_i^n rank(G_i)$

Since the complete graph has rank $n$, it follow from this that $largest \_clique(G) \leq rank(G)$.

What is the rank of an average graph? Consider this simple model of a random graph $G$: for every pair of vertices flip a fair coin to determine whether there is an edge between them. [It has been shown][2] that with very high probability $G$ has rank $n$. 

This suggests to me that low rank graphs are locally sparse or have a densely connected component but have lots of isolated vertices. A graph picked at random is likely to be full rank, however.

  [1]: http://elib.mi.sanu.ac.rs/files/journals/zr/22/zbr14137.pdf
  [2]: https://arxiv.org/abs/math/0505156