graphs within graphs · learning: questions

what type of mathematical structure allows one to express this type of structure: a labelled directed graph where nodes can themselves be graphs and arrows can be related (for example to say that loves is a subrelation of knows)
Can one express that in @Evan Patterson's Bicategory of Relations too?
(I also want to link to a node within another graph too)
Laura Lane believes what Clark Kent tells her about Superman

Keith Elliott Peterson (Jul 05 2023 at 04:23):

Well, seeing as a graph can be modeled as a set, I would think that a graph of graphs would just itself be a graph.

That being said, the category of

Graphs

is a topos, and the above could also be seen as an "over-graph" in the overcategory/overtopos

Graphs/G

, where

G

is the graph corresponding to the "outer" graph with four edges and four nodes containing the "inner" graphs in the example you've given.

Nathaniel Virgo (Jul 05 2023 at 07:04):

Henry Story you probably need to be a bit more specific about what you want. The following gives something that might be useful, but it doesn't quite match the picture you've drawn, so I don't know.

Define a [[reflexive graph]] as a graph with a distinguished edge from each node to itself. These are sort of like the identity morphisms in a category, so I'll call them identities, but they don't have to obey any special conditions like identity morphisms do, they just exist. A morphism of reflexive graphs is the same as a morphism of graphs except that it also has to map identities to identities.

Then a morphism of reflexive graphs

G'\to G

defines a kind of "graph of graphs". The point is that for each node

x\in G

there is associated a subgraph of

G'

, whose nodes are all the nodes that map to

x

and whose edges are all the edges that map to the identity morphism of

x

. (This is why we needed to consider reflexive graphs.) Given a node

x'

above

x

(i.e.

x'\in G'

such that

x'

maps to

x\in G

) and

y'

above

y

you can have an arrow from

x'

y'

, but only if there is an arrow from

x

y

. (The arrow

x'\to y'

must map to some arrow

x\to y

.) I don't know if that constraint is something you want, but maybe it is, since you talked about sub-relations.

However, in your picture you have an arrow from the "CK" node to the big circle at the top, and that isn't something you can have in this construction. So maybe it's not what you want.

Henry Story (Jul 05 2023 at 09:53):

Thanks @Keith Elliott Peterson and @Nathaniel Virgo. The structures you present both involve mapping one graph to another one.
Interestingly David Cornfield explains how modalities arise out of adjunctions between slice categories, and structurally we need these graphs in the nodes of graphs to allow the basic modality of "S says P" which is the core of BAN Logic (Burrows-Abadi-Needham) for decentralised access control. So that is very interesting.

I am not sure if the arrow CK to the big box is needed, as one could place a copy of the graph in the big top circle in the lower right circle. But I think if one can name these graphs, then then that link can be made.

Programmatically I think this is should be definable recursively. An RGraph could be defines as having nodes that can be literals (Strings, ints, ...), named or blank nodes, or RGraphs. There are some good example and pictures of this in this 2016 blog post A Comonad of Graph Decompositions.

Where such named directed labelled multi-edge graphs are used by the semantic web stack (RDF) to describe positive statements of facts (regular logic) which @Evan Patterson's looks at in the first part of Knowledge Representation in the Bicategories of relations, allowing graphs in the nodes of graphs should give one full first order logic, i.e. what is known as geometric or coherent logic and which Evan looks at in chapter 9.

This at least is the bet of the RDF Surfaces: Computer Says No⋆ paper which explains some of the motivations of the W3C Community work described with illustrations in the RDF Surfaces Primer which is inspired by Peirce's work. In "computer says no" they define an H-graph recursively too.

But it is still early work.
It is a puzzling still how the bicategory of relations, the graphs slice categories and the recurive definitions are related.

(btw. the above reasoning suggests that "isTrue" and "isFalse" are basic modal notions. Perhaps the simplest ones)

Kevin Arlin (Jul 05 2023 at 17:46):

This is a relatively trivial comment, but coherent logic, geometric logic, and full first-order logic are all different things. Neither coherent logic nor geometric logic allow negation or universal quantification in general; first-order logic certainly does but does not allow the infinite disjunctions in geometric logic.

Henry Story (Jul 05 2023 at 17:57):

In "Knowledge Representation in the Bicategories of relations" Evan Patterson writes on p. 47

Kevin Arlin (Jul 05 2023 at 18:24):

It is true that every first-order theory can be expressed as a coherent theory, but that is by no means the same thing as saying that first order logic is the same as coherent logic. People do use universal quantifiers in practice, after all! I see upon checking that some people apparently do say "geometric" for "coherent" and vice versa; when I said they aren't the same, I was using "geometric" for the logic allowing infinitary disjunctions and "coherent" for the logic allowing only finite ones.

Henry Story (Jul 05 2023 at 18:54):

So universal quantifiers appear on the RDF-Surfaces approach as blank nodes on a negative surface. So here a top plain graph is always a positive surface, where blank nodes are existential quantifiers.
Graphs inside nodes can be inside a negative node or a positive node. If inside a negative node, blank nodes are interpreted as universal quantifiers.
They have some good diagrams in the RDF Surfaces doc. (the negative surfaces are those surrounded by red dotted lines in the diagrams)

Henry Story (Jul 06 2023 at 09:31):

I found this via a number of routes, but most interestingly is a 2007 technical report An Abstract Data Model for the Tabulator Data Browser, where the Tabulator is Tim Berners-Lee's project for a generic RDF User Interface.

Ryan Wisnesky (Jul 06 2023 at 18:43):

I suppose the textbook answer here is that in the same way you can encode graphs using relations and query them with relational algebra, you can encode nested graphs using nested relations and query them using nested relational algebra (and this is why implementations of nested relations have names such as "GraphQL"). Anyway there's a theorem that says for queries of fixed depth, the two approaches have the same expressive power; that you can always "shred" a nested graph into a flat one plus extra structure specifying the hierarchy. Many modern RDBMSs do indeed shred nested structures into flat ones for processing

Henry Story (Jul 06 2023 at 20:49):

So I guess that is the case with RDF too, @Ryan Wisnesky , since RDF was defined in 1999 as a

S \times R \times O

triple, where

O

can be a plain node or a literal such as an integer, string, language string or XML. But the XML string could be an RDF/XML string, which has a graph interpretation, and which could itself have nodes which were RDF XML literals. But that tends to make me think that the notion of a recursive graph data structure was already there at the beginning. it would be interesting to see if it is in Guha 1995 phd thesis Contexts A Formalization and Some Applications as Guha was one of the earliest people who worked on RDF.

But it is true that that can be shredded into the N-Quads structure

Q \subseteq S \times R \times O \times G

where

G

are identifiers for graphs. All

\{ (s ,r, o) | \exists g, (s,r,o,g) \in Q \}

triples that have the same g form a graph which can be thought to be at the node of any triple

(s, r, g)

. So yes, we seem to recover the graphs within graph nodes. (I wonder if one every needs quints?)

One advantage of the hypernode view may just be that it helps to visualise graphs within graphs that way.

Henry Story (Jul 06 2023 at 21:01):

Btw. I was looking at this because I want to implement a pure Scala RDF library. There are many ways to do this. But one option would be to use a construct known as an inductive graph a concept that comes from a 2001 Haskell paper (see links in discussion) and which was also implemented in Scala.
Does anyone have feedback on using an inductive graph structure?
It is pictures like this from an excellent 2016 blog post A Comonad of Graph Decompositions by Rúnar Bjarnason that got me very interested.

Robin Piedeleu (Jul 07 2023 at 07:38):

The paradigmatic example in Set Operads in Combinatorics and Computer Science by Miguel Méndez, is an operad of graphs whose composition is defined by flattening graphs of graphs (defined more or less as you've described). I did not follow this whole thread and am not sure why you need this structure, but you might want to find a copy of the book and check it out.

Robin Piedeleu (Jul 07 2023 at 07:40):

There's a whole lot of fascinating theory associated with this operad, closely related to the modular decomposition of graphs btw.

Simon Burton (Jul 07 2023 at 09:10):

Henry Story (Jul 08 2023 at 17:14):

One very good presentation of RDF in terms of Category Theory from a Graph Theoretician is Benjamin Braatz's "Formal Modelling and Application of Graph Transformations in the Resource Description Framework". Graphs there are used as descriptions of the world, with various implication relations between graphs forming a category. But the graphs there are plain labelled directed multigraphs.

So we are missing the graphs within graph nodes allowed by RDF. That would also come then with some rules such as if a graph is declared to be True then it implies a graph with only the contents.

{ :snow is :White } a log:Truth .

:snow :is :White

Thanks for the pointers. to Miguel Mendez's book on Set Operads. I found the notion of a product of two species

G.G[V]

very interesting.
And the definition of substitution on p17. (I think they are the same thing?). But for RDF one would need

G[V] + G.G[V] + G.G.G[V] + ....

But that structure may require the nesting of graphs at each node to be the same, whereas in RDF some nodes can be named, others can contain literals like numbers or strings, and other nodes can contain graphs, others graphs of graphs, etc....

That feels like something like labelled directed simplicial sets (if those exist), where the head of a pyramid connects the graphs below. @Eric Neumann had some more elaborated thoughts on that.

that seems more like what is usually called the flatten or mu natural transformation, of a monad, right?
I don't see that as being that useful for RDF. The flattening of graphs within graphs does not seem to have that interesting an interpretation in a declarative logic.

The main interest for graphs within nodes is that it allows contexts for who said what or where information came from to be kept, which is essential when dealing with data on the web.

Henry Story (Jul 09 2023 at 09:02):

@Robin Piedeleu, The interest of these graphs with context is that they allow us to understand the different points of view various agents can have on a subject. For example we can express that
Laura Lane Believes what Clark Kent says, namely that Superman loves Superwoman. But perhaps that is not true. Perhaps Clark Kent just wants Laura Lane to take an interest in him and forget about the already taken Superman. But if Clark Kent is Superman then does Laura Lane believe that Clark Kent is a Flying Being? No, because she does not know that equality. Ie these are contexts which are not substitutable salva veritate. These are topics that come up in undergraduate courses in Philosophy, at least they were when I was studying in the late 1980s.
We end up straight into modal epistemic and doxastic logic here, which is what is needed if we want to be able to discuss ideas with other people on the internet. Namely we have to be able to consider their point of view (not in geometric terms as the angle from which they see one single reality which I also see from a different angle with different photons touching our respective retinas), but in the more general sense of us having collected different relations about the way we believe the world to be, which are up for questioning (this is deeply explored by Robert Brandom's work in Analytic Pragmatism).

Henry Story (Jul 09 2023 at 11:31):

Very interesting. From my reading of the first 7 pages it looks like that 2022 paper "Deconstructing the Calculus of Relations with Tape Diagrams" by @Filippo Bonchi, @Alessandro Di Giorgio and Alessio Santamaria, could be a chapter in a book that follows @Evan Patterson's 2017 paper Knowledge Representation in Bicategories of Relations. I think Patterson did indeed point out that there was not at the time a coherent diagramatic way to bring together regular logic and its dual. This paper answers that problem.

It is indeed interesting that the RDF surfaces spec needed this concept graphs on surfaces to get that duality to work together and give us first order logic. (also see RDF Surfaces - computer says no!.

I wonder how string diagrammaticians would get us to index modal logics such as ABN-logic of saying that, or other modal logical relations such as S knows P which Abadi somewhere links to indexed strong monads (perhaps here: Access control in a core calculus of dependency). I think I can work those rules quite well into morphisms between graphs with potentially graphs in their nodes, which looks like they correspond to the hypergraph models).

Alessandro Di Giorgio (Jul 09 2023 at 12:28):

Just to be precise: in our paper we don’t fully capture regular logic

(\exists, \wedge, \top)

and it’s dual

(\forall, \vee, \bot)

. The outer monoidal product and its associated (co)monoids allow you to express

\vee

and

\bot

but one still misses a way to express

\forall

Regarding modal logic, Pierce extended his EGs with another operation drawn as a dashed circle around the diagrams, intuitively representing a modality. In your RDF diagrams it would mean to have one other notion of surface in addition to the positive and negative ones.

Henry Story (Jul 21 2023 at 20:55):

The 1965 film The Saragosa Manuscripts was a favourite of Grateful Dead lead singer Jerry Garcia, and it contains 7 levels of stories within stories. So in our graph within graph model we would have graphs within graphs seven lvels deep.
https://www.youtube.com/watch?v=PXPhTAYB1rc

Henry Story (Sep 05 2023 at 10:00):

I read the paper "Compositional Diagrammatic FO Logic" which you pointed me to, and it does seem to perfectly match the work the RDF Surfaces group are doing. No wonder: they are also inspired by Peirce!
(I found the reasoning on p13 a bit confusing, and I even got the feeling that variables were mislabelled there)
But now this opens a very interesting possibility to introduce all RDF developers as they move to N3 to Category Theory on a path where they get the basics for understanding for Quantum String Diagrams as per the recent book by Bob Coeke Quantum in Pictures.

Category Theory
Zulip Server
Archive

Stream: learning: questions

Topic: graphs within graphs

Henry Story (Jul 04 2023 at 12:53):