The expressive power of GNN
Can you attach a unique polynomial to a graph? Not really.
If it would be possible it would help with identifying similar graphs (technically, isomorphic). But identifying isomorphic graphs is a problem still without a known efficient solution and one of the few natural problems sitting in the murky zone between P and NP-complete. Read: it has not been proven that graph isomorphisms can be computed in polynomial time. Most people believe it isn’t.
That said, there’s no shortage of polynomials you can build from a graph. The characteristic polynomial (from the adjacency matrix), the chromatic polynomial (counts proper colorings), the Tutte polynomial (chromatic, flow, and reliability polynomials all fall out of it as special cases) and more. Each is well-defined, computable and genuinely useful. None of them is however a complete invariant. Non-isomorphic graphs can share the exact same characteristic polynomial (they are cospectral) and such pairs already show up with graphs with as little as 5–6 vertices. The same collision problem hits the chromatic polynomial and even the much stronger Tutte polynomial. Different graphs have identical fingerprints.
A question presumes a solution space. Polynomials can’t, but maybe vector embeddings can? The answer is no and related to the Weisfeiler-Leman ceiling. You can try all sorts of spaces (and fail miserably): Gromov-Wasserstein distances, quantum walks, heat kernel signatures, persistent homology, Selberg zeta functions and many more.
Graphs do not like to have a single identity.
- Weisfeiler-Leman test: https://en.wikipedia.org/wiki/Weisfeiler_Leman_graph_isomorphism_test
- Expressive Power Of Graph Neural Networks And The Weisfeiler-Lehman Test: https://www.experfy.com/blog/ai-ml/expressive-power-graph-neural-networks-weisfeiler-lehman