Implements a novel computational model for graph computation, translating to iterated matrix multiplication on GPUs. Supports algebraic circuits, neural networks, proof networks, and various propagation schemes using message passing. Provides visualization, translation between graph formats, and tools for regex to NFA compilation.
This library implements a new computational model which we call graph computation. In contrast with prior work, e.g., Turing's machine and Church's λ-calculus, the advantage of this model is that it can be directly translated to iterated matrix multiplication on GPUs and has many desirable algebraic properties. Furthermore, it offers a natural way to express algebraic circuits, neural networks, factor graphs, proof networks, and enjoys many connections to programming language theory, automata theory and category theory.
Kaliningraph currently supports backpropagation in Kotlin∇. Efforts to lower other propagation schemes, e.g., belief propagation, uncertainty propagation, unit propagation, survey propagation and constraint propagation are ongoing. All of these schemes operate according to a principle known as message passing and are in general known to be Turing complete. This unification allows us to study many common problems in related domains using well-studied tools from arithmetic circuit complexity, to spectral and algebraic graph theory.
Kaliningraph is hosted on Maven Central.
dependencies {
implementation("ai.hypergraph:kaliningraph:0.1.8")
}
<dependency>
<groupId>ai.hypergraph</groupId>
<artifactId>kaliningraph</artifactId>
<version>0.1.8</version>
</dependency>
To access notebook support, use the following line magic:
@file:DependsOn("ai.hypergraph:kaliningraph:0.1.8")
For more information, explore our tutorials:
What are graphs? A graph is a (possibly empty) set of vertices.
What are vertices? A vertex is a unique label with neighbors (possibly containing itself).
What are neighbors? Neighbors are a graph.
What is a circuit? A circuit is either:
and, or, not)(a, b) -> (b, a)Run the demo via ./gradlew jvmTest --tests "ai.hypergraph.kaliningraph.HelloKaliningraph" to get started.
Kaliningraph treats string adjacency and graph adjacency as the same. To construct a graph, simply enumerate walks.
This can be done using a raw string, in which case unique characters will form the vertex set. Whitespace delimits walks:
val graph = LabeledGraph { "abcde ace" }
Vertices can also be linked via the - operator. The graph builder DSL provides a small alphabet:
val graph = LabeledGraph { a - b - "c" - d - e; a - c - e }
This is equivalent to:
val abcde = LabeledGraph { a - b - c - d - e }
val ace = LabeledGraph { a - "c" - e }
val graph = abcde + ace
Equality is supported using the Weisfeiler-Lehman test:
val x = LabeledGraph { a - b - c - d - e; a - c - e }
val y = LabeledGraph { b - c - d - e - f; b - d - f }
assertEquals(x == y) // true
Kaliningraph supports a number of graph visualizations.
Graph visualization is made possible thanks to KraphViz.
val de = LabeledGraph { d - e }
val dacbe = LabeledGraph { d - a - c - b - e }
val dce = LabeledGraph { d - c - e }
val abcd = LabeledGraph { a - b - c - d }
val cfde = LabeledGraph { c - "a" - f - d - e }
val dg = LabeledGraph(dacbe, dce, de) + Graph(abcd, cfde)
dg.show()
Running the above snippet will cause the following figure to be rendered in the browser:
Graph visualization in both DOT and adjacency matrix format is supported.
| DOT Graph | Matrix |
|---|---|
 |  |
It is also possible to visualize the state and transition matrices and step through the graph (./gradlew jsBrowserRun --continuous).
Computational notebooks prototyping is also supported.
Notebook {
a = b + c
f = b - h
}.show()
The above snippet should display something like the following:
Code2Vec generation and visualization is supported. The following demo was generated using message passing on the adjacency matrix, for graphs of varying height. The technique to create the embeddings is described here. We use TSNE to visualize the resulting vectors in 2D, and can clearly distinguish the clusters.
A regex to NFA compiler is provided. To run the demo, run ./gradlew RegexDemo. You should see something like this:
The following individuals have helped inspire this project through their enthusiasm and thoughtful feedback. Please check out their work.
a -> b(a->c, c->d) -> (a->d)(a->b, c->d) -> (a, b) -> (c, d)Surfaced from shared tags and platforms — no rankings paid for.