What is low rank intuitively for an adjacency matrix? 
If you have a graph represented by an adjacency matrix, what
  intuitively in terms of the original graph would low rank correspond
  to?

I am interested in this for both directed and undirected graphs.
This is relevant because low rank is very important in common techniques such as non-negative matrix factorization and it would be interesting to understand what the assumptions mean for graphs.
 A: 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.
