Crate open_hypergraphs

Expand description

§Open Hypergraphs

open-hypergraphs is a GPU-accelerated implementation of the OpenHypergraph datastructure from the paper “Data-Parallel Algorithms for String Diagrams”. Open hypergraphs are used for representing, evaluating, and differentiating large networks of operations with multiple inputs and outputs.

Here’s a drawing of an open hypergraph with labeled nodes ● and hyperedges □.

                   /───────────────────────────────────   x
                  ╱
  x   ───────────●
                i8\      ┌─────┐
                   \─────┤     │        ┌─────┐
           2             │ Sub ├───●────┤ Neg ├───●───    -(x - y)
  y   ─────●─────────────┤     │  i8    └─────┘  i8
          i8             └─────┘

This open hypergraph represents a circuit with two inputs, x and y. this circuit computes x on its first output and - (x - y) on its second. (The input/output labels x, y, and -(x - y) are only illustrative, and not part of the datastructure.)

Note carefully: in contrast to typical graph-based syntax representations, operations correspond to hyperedges, and values correspond to nodes! This is why nodes are labeled with types like i8 and hyperedges with operations like Sub.

See the datastructure section for a formal definition.

§What are Open Hypergraphs For?

Open Hypergraphs are a general, differentiable and data-parallel datastructure for syntax. Here’s a few examples of suitable uses:

Differentiable array programs for deep learning in catgrad
Terms in first order logic
Programs in the λ-calculus
Circuits with feedback
Interaction nets

Open Hypergraphs have some unique advantages compared to tree-based representations of syntax. For example, they can represent operations with multiple outputs, and structures with feedback. See the comparison to trees and graphs for more detail.

Differentiability of open hypergraphs (as used in catgrad) comes from the data-parallel algorithm for generalised ahead-of-time automatic differentiation by optic composition. This algorithm is actually more general than just differentiability: read more in the papers “Categorical Foundations of Gradient-Based Learning” and “Data-Parallel Algorithms for String Diagrams”. See the Theory section for more pointers.

§Usage

If you’re new to the library, you should start with the crate::lax module. This provides a mutable, imperative, single-threaded interface to building open hypergraphs which should be familiar if you’ve used a graph library before.

We can build the example open hypergraph above as follows:

use open_hypergraphs::lax::*;

pub enum NodeLabel { I8 };
pub enum EdgeLabel { Sub, Neg };

#[test]
fn build() -> OpenHypergraph<NodeLabel, EdgeLabel> {
    use NodeLabel::*;
    use EdgeLabel::*;

    // Create an empty OpenHypergraph.
    let mut example = OpenHypergraph::<NodeLabel, EdgeLabel>::empty();

    // Create all 4 nodes
    let x = example.new_node(I8);
    let a = example.new_node(I8);
    let y = example.new_node(I8);
    let z = example.new_node(I8);

    // Add the "Sub" hyperedge with source nodes `[x, y]` and targets `[a]`
    example.new_edge(Sub, Hyperedge { sources: vec![x, y], targets: vec![a] });

    // Add the 'Neg' hyperedge with sources `[a]` and targets `[z]`
    example.new_edge(Neg, Hyperedge { sources: vec![a], targets: vec![z] });

    // set the sources and targets of the example
    example.sources = vec![x, y];
    example.targets = vec![x, z];

    // return the example
    example
}

The crate::lax::var::Var struct is a helper on top of the imperative interface which reduces some boilerplate, especially when operators are involved. We can rewrite the above example as follows:

pub fn example() {
    let state = OpenHypergraph::empty();
    let x = Var::new(state, I8);
    let y = Var::new(state, I8);
    let (z0, z1) = (x.clone(), -(x - y));
}

See examples/adder.rs for a more complete example using this interface to build an n-bit full adder from half-adder circuits.

By contrast, the crate::strict module in principle supports GPU acceleration, but has a much more complicated interface.

§Datastructure

Before giving the formal definition, let’s revisit the example above.

                 /───────────────────────────────────
               0╱
    ───────────●
              i8\      ┌─────┐
                 \─────┤     │   1    ┌─────┐   3
         2             │ Sub ├───●────┤ Neg ├───●───
    ─────●─────────────┤     │  i8    └─────┘  i8
        i8             └─────┘

There are 4 nodes in this open hypergraph, depicted as ● with a label i8 and a node ID in the set {0..3}. There are two hyperedges depicted as a boxes labeled Sub and Neg.

Each hyperedge has an ordered list of sources and targets. For example, the Sub edge has sources [0, 2] and targets [1], while Neg has sources [1] and targets [3]. Note: the order is important! Without it, we couldn’t represent non-commutative operations like Sub.

As well as the sources and targets for each hyperedge, the whole “open hypergraph” also has sources and targets. These are drawn as dangling wires on the left and right. In this example, the sources are [0, 2], and the targets are [0, 3].

There are no restrictions on how many times a node can appear as a source or target of both hyperedges and the open hypergraph as a whole.

For example, node 0 is a source and target of the open hypergraph, and a source of the Sub edge. Another example: node 1 is not a source or target of the open hypergraph, although it is a target of the Sub hyperedge and a source of the Neg hyperedge.

It’s also possible to have nodes which are neither sources nor targets of the open hypergraph or any hyperedge, but that isn’t pictured here. See the theory section for more detail.

§Formal Definition

Formally, an open hypergraph is a triple of:

A Hypergraph h with N ∈ ℕ nodes
An array s of length A ∈ ℕ whose elements s_i ∈ {0..N-1} are nodes
An array t of length B ∈ ℕ whose elements t_i ∈ {0..N-1} are nodes

Many different kinds of Hypergraph exist, but an open hypergraph uses a specific kind of directed hypergraph, which has:

A finite set of N nodes, labeled with an element from a set Σ₀
A finite set of E hyperedges, labeled from the set Σ₁
For each hyperedge e ∈ E,
- An ordered array of source nodes
- An ordered array of target nodes

§Comparison to Trees and Graphs

Let’s compare the open hypergraph representation of the example term above against tree and graph representations.

When considered as a tree, the term (x, - (x - y)) can be drawn as follows:

There are two problems here:

To handle multiple outputs, we had to include a tuple constructor “Pair” in our language. This means we’d also need to add other functions to deal with pairs, “polluting” the base language.
The “sharing” of variables is not evident from the tree structure: x is used twice, but we have to compare strings to “discover” that fact.

In contrast, the open hypergraph:

Allows for terms with multiple outputs, without having to introduce a tuple type to the language.
Encodes the sharing of variables naturally by allowing nodes to appear in multiple sources and targets.

Another common approach is to use a graph for syntax where nodes are operations, and an edge between two nodes indicates the output of the source node is the input of the target. Problems:

Nodes don’t distinguish the order of edges, so argument order has to be tracked separately
There is no notion of input or output to the whole system.

In contrast, the open hypergraph:

Naturally handles operations with multiple ordered inputs and outputs (as hyperedges)
Comes equipped with global source and target nodes

Open Hypergraphs have general utility because they model any system which can be described in terms of symmetric monoidal categories. Some examples are listed above; see the Theory section for more pointers to detail on the mathematical underpinnings.

§Theory

Formally, an OpenHypergraph<Σ₀, Σ₁> is an arrow of the free symmetric monoidal category presented by the signature (Σ₀, Σ₁) plus “Special Frobenius” structure.

This extra structure is sometimes useful (e.g. in autodiff), but can be removed by restricting the open hypergraph such that nodes always appear in exactly one source and target. This condition is called “monogamous acyclicity”.

A complete mathematical explanation can be found in the papers String Diagram Rewrite Theory I, II, and III, which also includes details on how to rewrite open hypergraphs.

The implementation in this library is based on the data-parallel algorithms described in the paper Data Parallel Algorithms for String Diagrams. In particular, the “generalised autodiff” algorithm can be found in Section 10 (“Optic Composition using Frobenius Structure”) of that paper.

Modules§

array: A minimal set of array operations which are sufficient to implement open hypergraphs.
category: Traits for types forming hypergraph and symmetric monoidal categories
finite_function: Finite Functions represented as arrays of natural numbers
indexed_coproduct: Indexed coproducts over finite and semifinite functions
lax: An imperative/sequential interface for constructing “Lax” Open Hypergraphs.
operations: Tensorings of operations
semifinite: Arrays of arbitrary types, pre-composable with finite functions
strict: An implementation of Open Hypergraphs directly following the paper “Data-Parallel Algorithms for String Diagrams”.

Crate open_hypergraphsCopy item path