# Terminology for graphs whose vertices can be graphs

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!

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.

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.