Encoding information about submatrix determinants $M$ is an $n\times n$ matrix. Consider the submatrices $M(P;Q)$ formed from $P$ rows and $Q$ columns of $M$ where $P$ and $Q$ are disjoint indices.
Is there some way to encode the various determinants such as $\det M((1,2,4);(3,5,6))$, $\det M((1,2);(3,5))$, and $\det M((1,3);(2,4))$ in a single object much like chromatic polynomials and generating functions.
As a motivation, such determinants represent some kind of information about connections in an adjacency matrix of a graph and connections have information interrelated among each other. Therefore, it feels like the various determinants should be interrelated and that therefore there should be a way to intertwine them all in a single object like chromatic polynomials and generating functions.
 A: If you consider $M\colon V\to V$ as a linear map of an $n$-dimensional vector space $V$ into itself (with some canonical basis $e_i$ used to express $M$ as a matrix), then the $k$-minors (which you called subdeterminants) of $M$ are the components of the induced linear map $\bigwedge^k M\colon \bigwedge^k V \to \bigwedge^k V$ of the $k$-th exterior power of $V$, provided you use the canonical basis $e_{i_1}\wedge\cdots\wedge e_{i_k}$ to express it as a matrix.
Since you are not interested in minors that have the same index appearing in both the row and column lists, you can just set those components of $\bigwedge^k M$ to zero. From the linear algebra point of view, this can be accomplished by applying a certain projector to this matrix, whose precise form is not difficult to figure out. The result, say denoted by $[\bigwedge^k M]$, is still an map from $\bigwedge^k V$ to itself. Thus you can capture some information about $[\bigwedge^k M]$ in its characteristic polynomial. This polynomial will be invariant under permutations of the graph vertices. Though probably not all the coefficients this polynomial will be independent invariants.
I'm not sure if this is exactly the kind of construction you were looking for, but at least the output is a polynomial like in your hint.
