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 entry on or above the diagonal we flip a fair coin and mark the entry as 1 or 0. It has been shown that $G$ almost surely has rank $n$.

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

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.