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 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 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.