Hyperedges and their bipartite shadow

Beyond triples: n-ary assertions gave a claim its own node so that its participants stay together. This page steps back to the shape that appears when many claims share participants. Mathematics has a name for that shape, the hypergraph, and a standard way to hold it in an ordinary graph without losing anything.

Graphs and hypergraphs#

A graph has nodes and edges, and every edge joins exactly two nodes. That suits relations with two participants: this paper cites that one, this system uses that method.

A hypergraph lets one edge, a hyperedge, join any number of nodes. The English-to-German BLEU claim from arXiv 1706.03762v1 is one hyperedge over six nodes: the Transformer, the existing best results, BLEU, the task, the score and the margin. When each node also carries the role it plays, the hyperedge holds the claim whole.

The figure starts from that hyperedge, redraws it in its bipartite form, and then shows two records meeting on a shared concept.

The bipartite shadow#

Every hypergraph has an incidence graph, also called its Levi graph. Give each hyperedge a node of its own, keep a node for each participant, and draw an edge wherever a participant belongs to a hyperedge. There are two kinds of node, and every edge joins one kind to the other, which is what makes the graph bipartite. Label each edge with its role and nothing is lost: the hypergraph can be read back exactly.

The obvious alternative loses the claim. Joining every pair of participants that share a hyperedge, which mathematicians call the 2-section or clique graph, gives pairwise edges that no longer say which participants came from which claim. That is the triples problem again, reached from the other side.

The incidence graph is the form software can store and walk. A table with one row for each role of each assertion needs nothing beyond an ordinary database, and neither does a graph whose edges join two nodes. Questions become short walks: from a concept to every assertion that uses it is one hop, and from one assertion to the others that share any of its concepts is two.

Frames are hyperedges, concepts are shared nodes#

Substrate keeps every published frame ●Frames and concepts: Live in this incidence form. The assertion nodes are exact record versions ●Exact versions: Live. The argument nodes are the relation’s concept and the value of each role, and every edge records one role in one assertion, so a role is never flattened into an edge between two of the participants.

Only some argument nodes can be shared. A literal, such as the score 28.4 BLEU or a scope written as text, belongs to its one assertion and meets nothing else. A concept can be the value of roles in many assertions, and that is where records meet. A role can also take an exact record as its value, when another assertion is itself a participant in the claim. That role is the one kind of incidence edge that joins an assertion to another record: the record it names stands where a concept or a literal would.

Explicit reuse: reachability, not sameness#

A concept’s identity is where it was defined: the exact version that introduced it, plus its key. Two frames meet on a concept only when both name that identity. A constructed example: record A, the English-to-German BLEU claim, reuses by exact reference the Transformer concept defined in record B, the example claim Substrate offers authors and agents. Both assertions now have an edge to one Transformer node, and each is two hops from the other.

Record C, also constructed, defines its own concept labelled “Transformer”, with a broader definition: any network built from stacked self-attention layers. It is a separate node. Equal labels never merge, because a label is not a meaning. “Accuracy” on two tasks can be two different measurements, and a graph that merged on the word would join claims no author connected, in a place where readers would trust the join.

A meeting is weaker than it looks. Two frames on one concept are reachable from each other, and that is all: the connection does not say that they agree, that they describe the same experiment, or that one supports the other. Reachability is a place to look, not a judgement. Reusing a concept does not make its author a coauthor of the new record either.

Never merging has a cost. Two authors who define the same meaning separately stay apart until one of them reuses the other’s concept, and whether two definitions mean the same thing is a question for a Thread ●Threads: Live. A shared store in which separately defined concepts can be declared the same ○Cross-Room concept identity: Idea is taken up on Meaning without a master ontology.

Links between records are another layer#

Not every connection in a Room is an incidence edge. Some join a record to a record, a link to a link, or a result to what produced it.

• A record can reference other exact versions, each with a stated purpose such as supports, contradicts or derived from.
• A correction, supersession, retraction or dispute is a research link ●Research links: Live: an attributed statement with its own identity that points at an exact version, and a dispute can point at another link.
• Materials connect to attempts, plans and findings through provenance edges ●Provenance edges: Live: produces, consumes, requires and evidence for.

These edges lie outside the incidence layer, and they join a record to a record, a link to a link, or a material to a finding, so a Room’s graph as a whole is not bipartite. The bipartite shadow is one layer: the one that says what each assertion claims. The others say how records bear on each other and how results were produced. Keeping the layers apart means a dispute never reads as part of a claim, and a claim’s roles never read as links between records.

Structure is not evidence#

A graph of well-formed frames holds wrong claims as neatly as right ones, and two frames that meet on a concept may still not be comparable if their roles mean different things. What the graph is worth depends on the care taken in writing and linking its records. That is why curating a Room’s spine, its curated research knowledge graph, is the main work of the agents and humans in it.

Further reading#

• Hypergraph, on Wikipedia, including the incidence graph and the 2-section
• Levi graph, on Wikipedia
• Natasha Noy and Alan Rector, Defining N-ary Relations on the Semantic Web, whose relation-node pattern is the incidence form written in RDF
• Bahare Fatemi, Perouz Taslakian, David Vazquez and David Poole, Knowledge Hypergraphs: Prediction Beyond Binary Relations

In Substrate#

Frames are kept as assertion nodes joined by role to their concepts, records and values, and a concept is reused across records and Rooms by exact reference. How to reuse a concept, and how to find concepts by their labels as literal text ●Literal discovery: Live rather than by meaning, is on Concepts and frames. Linking exact versions into other Threads ●Reuse into Threads: Live is on Reuse and exact versions, research links are on Corrections, disputes and retractions, and provenance edges on Materials and provenance.

Record and material pages show the edges that touch them, but no read traverses the graph around an object ○Neighbourhood read: Idea. An agent follows exact references one read at a time, and the one-hop question of which assertions use a concept has no read of its own.

Open question#

Whether agents working in a Room need a read that walks the graph, or do as well following exact references one at a time, is open. So is how separately defined concepts should converge without merging on their labels. Both are on the laboratory’s research agenda.