  In problems involving approximation, completion, denoising, dimension
reduction, estimation, interpolation, modeling, order reduction, regression,
etc, we argue that the near-universal practice of assuming that a function,
matrix, or tensor (which we will see are all the same object in this context)
has \emph{low rank} may be ill-justified. There are many natural instances
where the object in question has high rank with respect to the classical
notions of rank: matrix rank, tensor rank, multilinear rank --- the latter two
being the most straightforward generalizations of the former. To remedy this,
we show that one may vastly expand these classical notions of ranks: Given any
undirected graph $G$, there is a notion of $G$-rank associated with $G$, which
provides us with as many different kinds of ranks as there are undirected
graphs. In particular, the popular tensor network states in physics (e.g.,
\textsc{mps}, \textsc{ttns}, \textsc{peps}) may be regarded as functions of a
specific $G$-rank for various choices of $G$. Among other things, we will see
that a function, matrix, or tensor may have very high matrix, tensor, or
multilinear rank and yet very low $G$-rank for some $G$. In fact the difference
is in the orders of magnitudes and the gaps between $G$-ranks and these
classical ranks are arbitrarily large for some important objects in computer
science, mathematics, and physics. Furthermore, we show that there is a $G$
such that almost every tensor has $G$-rank exponentially lower than its rank or
the dimension of its ambient space.
