Links on Links (and Graphs)
1. Motivation
Statements about statements show up wherever graphs carry real-world knowledge:
-
Provenance and trust: Carol claims that Alice knows Bob.
-
Time and validity: Alice works at ACME — and that fact was superseded by Alice works at Initech.
-
Annotation and review: a reviewer disputes a specific relation, not the nodes it connects.
-
Biology and processes: an enzyme catalyzes a reaction, where the reaction is itself a (hyper-)edge between substrates and products.
The same holds one level up, for statements about a whole graph:
-
Datasets: the graph Social Network was published by ACME, is licensed under CC-BY, was derived from another graph.
Today, Connected JSON can only express these by turning the inner edge or graph into a node (manual reification). That changes the shape of the graph, and every consumer has to know the convention.
1.1. Edges and Graphs Already Have an Identity
In Connected JSON, an edge and a graph may have an id, and ids are unique per document across nodes, edges and graphs.
So edges and graphs are already addressable.
The only missing piece is that an endpoint cannot address them.
1.2. RDF 1.2 Goes in the Same Direction
RDF 1.2 adds triple terms: a triple can be used as the object of another triple.
Statements about statements are made through a reifier, a resource that rdf:reifies a triple term:
PREFIX ex: <https://example.org/>
ex:alice ex:knows ex:bob ~ ex:e1 . # e1 is the reifier of the triple
ex:carol ex:claims ex:e1 . # a statement about that triple
A Connected JSON edge with an id plays exactly the role of such a reifier.
For graphs, RDF has had named graphs (RDF datasets) since RDF 1.1: the graph name is an IRI, and other triples can use it.
A Connected JSON graph with an id plays the role of a named graph.
See Interpretation as RDF 1.2.
2. Proposal
2.1. Endpoint to Edge or Graph
An endpoint gets two new properties, edge and graph, as alternatives to node:
| Property | Type | Description |
|---|---|---|
|
|
Node id. The id of the node to which this endpoint is attached.
Required, unless |
|
|
New. Edge id. The id of the edge to which this endpoint is attached. |
|
|
New. Graph id. The id of the graph to which this endpoint is attached. |
|
|
Only allowed together with |
direction, type and data work exactly as for endpoints that point to nodes.
-
An endpoint has exactly one of
node,edgeorgraph. -
The referenced edge or graph MUST exist in the same document and MUST have an
id. Unlike nodes, edges and graphs are never implied by a reference: an edge without endpoints carries no information, and an empty graph carries none either. -
The referenced edge or graph may live anywhere in the document, including nested graphs (ids are document-wide).
-
An edge may point to an edge that itself points to an edge (chains of any length). Cycles are allowed; consumers MUST NOT assume that edge-to-edge references form a tree or a DAG.
-
An edge may point to a graph that contains the edge itself, e.g. a statement about the graph made inside that graph.
-
An edge may mix endpoints to nodes, edges and graphs (hyperedges included).
Since node, edge and graph ids share one document-wide scope, node alone would already be unambiguous.
Separate edge and graph properties are still proposed: they keep the reference type visible to readers and to JSON Schema, and let a parser check the reference without a lookup.
|
2.2. Example
The graph g1 contains Alice knows Bob (e1) and Carol claims that (e2).
Edge e3 states that g1 was published by ACME:
{
"graphs": [ {
"id": "g1",
"nodes": [
{ "id": "alice" },
{ "id": "bob" },
{ "id": "carol" },
{ "id": "acme" }
],
"edges": [
{ "id": "e1",
"type": "knows",
"endpoints": [
{ "node": "alice", "direction": "in" },
{ "node": "bob", "direction": "out" }
]
},
{ "id": "e2",
"type": "claims",
"endpoints": [
{ "node": "carol", "direction": "in" },
{ "edge": "e1", "direction": "out" }
]
},
{ "id": "e3",
"type": "publishedBy",
"endpoints": [
{ "graph": "g1", "direction": "in" },
{ "node": "acme", "direction": "out" }
]
}
]
} ]
}
e2 points to edge e1, e3 points to graph g12.3. Interpretation as RDF 1.2
This extends Interpretation as RDF, which turns each endpoint pair into triples.
-
An edge with an
idthat is referenced by another edge becomes the reifier of the triples it induces: for every triple(s, p, o)induced by edgee1, emit<< s p o ~ e1 >>(i.e.e1 rdf:reifies <<( s p o )>>). -
A graph with an
idthat is referenced by an edge becomes a named graph with the URI of itsid, containing the triples induced by its own edges. Nested graphs with anidare named graphs of their own. -
An endpoint with
edgeorgraphcontributes the URI of the referenced id (expanded via@context) wherever an endpoint would contribute the node URI.
A hyperedge can induce several triples. Its reifier then reifies all of them; RDF 1.2 allows one reifier for several triple terms.
The example above becomes (TriG syntax):
PREFIX ex: <https://example.org/>
ex:g1 {
ex:alice ex:knows ex:bob ~ ex:e1 .
ex:carol ex:claims ex:e1 .
ex:g1 ex:publishedBy ex:acme .
}
3. Mapping to GraphML: Proxy Nodes
GraphML has no links on links:
<edge> has source and target attributes, and <hyperedge>/<endpoint> has a node attribute.
All of them reference nodes only.
So, on export, each edge or graph that is referenced by an endpoint is represented by an additional proxy node. The proxy node stands in for the edge or graph wherever it is used as an endpoint, and it carries the id of what it represents as a data attribute.
3.1. Proxy Node Key
A GraphML document that contains proxy nodes declares this key:
<key id="cj.proxyFor" for="node" attr.name="cj:proxyFor" attr.type="string"/>
A proxy node is a GraphML <node> with a <data key="cj.proxyFor"> whose value is the id of the represented GraphML <edge>, <hyperedge> or <graph>.
3.2. Export Algorithm (Connected JSON to GraphML)
-
Export all nodes, edges and graphs as usual (see Migrating from GraphML). Every edge and graph keeps its Connected JSON
idas GraphMLidattribute. -
Collect the set R of edges and graphs that are referenced by at least one endpoint via
edgeorgraph. -
For each element
Xin R, create one proxy node:-
id:X.id, the same id as the element it represents. This never collides with another node, because Connected JSON ids are unique across nodes, edges and graphs. GraphML allows a node to share its id with an edge or graph. -
placed
-
for an edge: in the same
<graph>as the edge, -
for a graph: in its parent
<graph>, or in the graph itself if it is a top-level graph.
-
-
<data key="cj.proxyFor">with the valueX.id. -
no other data, no ports, no nested graph. Label, type and data of
Xstay on the GraphML elementXonly; the proxy node does not copy them, not even the label, so there is a single source of truth.
-
-
Each endpoint
{ "edge": X.id }or{ "graph": X.id }is written as an endpoint to the proxy node ofX:-
as
sourceortargetof an<edge>, if the referencing edge is a bi-edge, -
as
<endpoint node="…"/>of a<hyperedge>, otherwise.Direction and endpoint data are mapped as for node endpoints. If the proxy node lives in a different graph than the referencing edge, the usual GraphML rules for edges between nested graphs apply, exactly as for regular nodes.
-
The proxy node is not connected to the element it represents; GraphML cannot express that.
The link exists only through the cj:proxyFor value.
<graphml xmlns="http://graphml.graphdrawing.org/xmlns">
<key id="cj.proxyFor" for="node" attr.name="cj:proxyFor" attr.type="string"/>
<key id="ex.type" for="edge" attr.name="ex:type" attr.type="string"/>
<graph id="g1" edgedefault="directed">
<node id="alice"/>
<node id="bob"/>
<node id="carol"/>
<node id="acme"/>
<node id="e1">
<data key="cj.proxyFor">e1</data>
</node>
<node id="g1">
<data key="cj.proxyFor">g1</data>
</node>
<edge id="e1" source="alice" target="bob">
<data key="ex.type">knows</data>
</edge>
<edge id="e2" source="carol" target="e1">
<data key="ex.type">claims</data>
</edge>
<edge id="e3" source="g1" target="acme">
<data key="ex.type">publishedBy</data>
</edge>
</graph>
</graphml>
3.3. Import Algorithm (GraphML to Connected JSON)
-
Read the GraphML document as usual.
-
Find all candidate proxy nodes: nodes with a
cj:proxyFordata value. -
A candidate is a valid proxy node if
-
its
cj:proxyForvalue is theidof exactly one<edge>,<hyperedge>or<graph>in the same document, -
no other proxy node points to the same element,
-
it has no other data, no ports and no nested graph, and
-
no edge connects to it via a
sourceport,targetportorport.
-
-
For each valid proxy node
Prepresenting elementX:-
rewrite every endpoint that references
Pinto{ "edge": "X" }ifXis an edge or hyperedge, or{ "graph": "X" }ifXis a graph, keeping direction, type and data; -
drop
P.The id of
Pplays no role; it usually equals the id ofX.
-
-
Importers MUST accept GraphML in which a node shares its id with an edge or a graph, as GraphML permits this.
-
Candidates that are not valid are kept as regular nodes, including their
cj:proxyFordata, and the importer SHOULD report a warning. Nothing is lost; the document just does not use links on links.
3.4. Round Trip
Export followed by import restores the original Connected JSON document: proxy nodes are only created for referenced edges and graphs, and the import removes exactly those. Proxy nodes do not appear in Connected JSON at all.
Tools that do not know cj:proxyFor still read a valid GraphML graph.
They see each proxy node as an ordinary node, so the structure is preserved, only the meaning "this node is that edge (or graph)" is lost.