Terminology for graphs whose vertices can be graphs

Question

Let $W_0$ be some fixed, finite set of "atomic vertices". Noting $2^X$ the power set of some set $X$, we consider $\bigl\{ (V, E) \bigm| V \in 2^{W_0}, E \in 2^{\{ (s, t) | s, t \in V \}} \bigr\}$, the set of all graphs whose vertices come from $W_0$. We are interested in the case where such graphs could appear as vertices in a graph (together with "atomic vertices" from $W_0$), and recursively consider such graphs-of-graphs as vertices in "higher-order" graphs

$$\forall n \in \mathbb{N}, \quad W_{n+1} = W_n \cup \bigl\{ (V, E) \bigm| V \in 2^{W_n}, E \in 2^{\{ (s, t) | s, t ∈ V \}} \bigr\}\quad .$$

I'm considering a Computer Science and/or Knowledge Graph and/or Philosophy application involving such "graphs-of-graphs". Before reinventing the wheel, I would like to know what the literature has to say about this, but I don't know where to start looking.

Are you aware of any terminology/conventions/notations for such "graphs"? Are there issues/paradoxes that I should be aware of in the limit $n \to \infty$? Are there works, especially accessible ones, that you would recommend on the topic? Thanks!

---

Following Mike's Comment/Answer, I decided to add a few explicit examples.

First suppose that $W_0 = \emptyset$, in which case $W_1 = \bigl\{\bigr (\emptyset, \emptyset) \}$ because the only graph you can build with no vertices is the empty graph (with no vertices nor edges). But for $W_2$, we may treat the graph $(\emptyset, \emptyset)$ as a vertex, giving

\begin{align} W_2 = \Bigl\{ & (\emptyset, \emptyset),\\ & \bigl(\{(\emptyset, \emptyset)\}, \emptyset\bigr),\\ & \bigl(\{(\emptyset, \emptyset)\}, ((\emptyset, \emptyset), (\emptyset, \emptyset))\bigr) \Bigr\} \quad , \end{align}

i.e., the set comprised of 1. the empty graph, 2. a graph with no edge and the empty graph as a vertex, and 3. a graph with a single edge joining the empty graph to itself (self-loop). We could then continue with $W_3$, this time with 3 vertices available as building blocks.

In the limit $n \to \infty$, I believe that recursive definitions like the following would be valid

$$g = \Bigl( \bigl\{(\emptyset, \emptyset), g\bigr\}, \bigl\{ \bigl((\emptyset, \emptyset), g\bigr) \bigr\} \Bigr) \quad ,$$

i.e., the graph $g$ has the empty graph and itself as vertices, with a single edge oriented from the empty graph to the graph $g$. But this is the kind of "hand waving" that could eventually lead to issues/paradoxes...

Up to this point, I considered $W_0 = \emptyset$, but what if we allow for some "atomic vertices"? My understanding is that if $W_0$ only contains graphs that would have been valid in the above (e.g., $W_0 = \{(\emptyset, \emptyset)\}$), this will affect "shallow" layers but leave the limit $n \to \infty$ unaltered. However, if we instead add something new (and perhaps not even a graph, say $W_0 = \{42\}$), then this would increase the expressiveness of limit $n \to \infty$.

Please note that I have a very "applied" perspective here: I'm thinking of such graphs as a candidate tool to represent concepts. As an example of where I'm coming from, please consider Figure 19(c) from https://arxiv.org/abs/2003.02320 . Ignoring the edge labels "flight" and "valid from", this knowledge graph could be represented as

\begin{align} \Bigl(\Bigl\{ & \bigl( \bigl(\{\text{Santiago}, \text{Arica}\},\{\bigl(\text{Santiago}, \text{Arica}\bigr)\}\bigr), 1956 \Bigr\},\\ \Bigl\{& \bigl( \bigl(\{\text{Santiago}, \text{Arica}\},\{\bigl(\text{Santiago}, \text{Arica}\bigr)\}\bigr) , 1956\bigr)\Bigr\}\Bigr) \quad . \end{align}

This kind of representation is already quite powerful, and I'm wondering how far we can push it.

Answer 1

For whatever reason, my internet browser won't let me get into writing a comment, which is what this is.

As far as this specific example, I am not sure. But, for comprehension, better to both write in in concise formal mathematical language, and then explain a bit less formally with words. Meanwhile, is the graph you wrote out even well-defined? So $S,T \in \cal{P}(S_{n-1})$ are adjacent in $G_n$ iff $|S|=|T|$ and $s_it_i \in E(G_{n-1})$ for each $i=1,2,\ldots, |S|$ and some ordering of $S$ and $T$?

IN GENERAL:Your best bet is to just say explicitly what you mean. Say "Let $G$ be a graph. And then in turn, we replace each vertex $v \in V(G)$ with a graph $H_v$ of the following structure, and then we put an edge between a vertex $u_v \in H_v$ and $u_w \in H_w$ iff $vw$ is an edge in $G$, and ...."

The term commonly used for what you are describing is "graph product", but there are many flavors of such graph products i.e., do you replace each edge $vw$ in $G$ with a complete bipartite graph between $V(H_v)$ and $V(H_w)$ or just a matching between $V(H_v)$ and $V(H_w)$, or even just one edge; are the $H_v$s; $v \in V(G)$ all the same graph, and even, are the $H_v$s vertex-disjoint.