Skip to content

Latest commit

 

History

History
401 lines (297 loc) · 25.5 KB

README.md

File metadata and controls

401 lines (297 loc) · 25.5 KB
Raw

Kaliningraph: A Type Family of Algebraic Graphs

Kotlin 1.6.20 Maven Central CI

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.

Installation

Kaliningraph is hosted on Maven Central.

Gradle

dependencies {
    implementation("ai.hypergraph:kaliningraph:0.1.8")
}

Maven

<dependency>
  <groupId>ai.hypergraph</groupId>
  <artifactId>kaliningraph</artifactId>
  <version>0.1.8</version>
</dependency>

Jupyter notebook

To access notebook support, use the following line magic:

@file:DependsOn("ai.hypergraph:kaliningraph:0.1.8")

For more information, explore our tutorials:

Graphs, inductively

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.

Circuits, inductively

What is a circuit? A circuit is either:

  • A Boolean logic gate (e.g., and, or, not)
  • A circuit that takes two inputs and swaps them (a, b) -> (b, a)
  • A circuit that takes one input and gives one output a -> b
  • The serial composition of two circuits (a->c, c->d) -> (a->d)
  • The parallel composition of two circuits (a->b, c->d) -> (a, b) -> (c, d)

Getting started

Run the demo via ./gradlew jvmTest --tests "ai.hypergraph.kaliningraph.HelloKaliningraph" to get started.

Usage

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

Visualization

Kaliningraph supports a number of graph visualizations.

Graphviz

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:

Matrix form

Graph visualization in both DOT and adjacency matrix format is supported.

DOT Graph Matrix
image image_1

It is also possible to visualize the state and transition matrices and step through the graph (./gradlew jsBrowserRun --continuous).

Computation graph

Computational notebooks prototyping is also supported.

Notebook {
  a = b + c
  f = b - h
}.show()

The above snippet should display something like the following:

Translation

Bidirectional translation to various graph formats, including Graphviz, JGraphT, Tinkerpop and RedisGraph is supported:

val g = LabeledGraph { a - b - c - a }
        .toJGraphT().toKaliningraph()
        .toTinkerpop().toKaliningraph()
        .toGraphviz().toKaliningraph()

Code2Vec

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.

Automata-based RegEx

A regex to NFA compiler is provided. To run the demo, run ./gradlew RegexDemo. You should see something like this:

Research questions

  • What is the best way to represent a graph?
  • Is it possible to statically check tensor arithmetic in the Kotlin type system?
  • How computationally powerful is matrix multiplication?
  • Is subgraph isomorphism feasible using random walks?
    • Treat graph as a sequence and run string convolution
    • Generate lazy random walk and halt after K steps
    • Convolve permuted variants of query in parallel
    • Need some kind of label permutation / edit distance metric
  • How do we represent a tensor/hypergraph?
  • How could we implement graph grammars/rewriting?
    • Rewrites as string substitution on the random walk sequence
    • Reconstruct graph from rewritten string using adjacency matrix
    • Is there an algebraic definition for graph grammars?
    • Maybe graph convolution. How to encode rewrites as a kernel?
    • Rectangular matrix multiplication or square with upper bound?
    • May be possible to represent using tensor contraction
    • Need to look into hyperedge replacement grammars
    • How do we identify confluent rewrite systems?
  • What are the advantages and disadvantages of graph rewriting?
    • Graphs as vertices and rewrites as edges in a nested graph?
    • Reduction/canonicalization versus expansion graph grammar
  • What happens if we represent the graph as a symbolic matrix?
    • Could we propagate functions instead of just values?
    • What if matrix elements were symbolic expressions? (cf. KeOps)
    • Should we represent the whole matrix as a big bold symbol?
  • Is there an efficient way to parallelize arithmetic circuits?
    • Translate formula graph to matrix using Miller's evaluator
    • How to distribute the work evenly across sparse matrices
  • What are some good way to visualize random walks?
    • Display states, transitions and graph occupancy side-by-side
  • Is there a connection between linear algebra and λ-calculus?

References

Knowledge graphs

Graph theory

Graph learning

Functional graphs

Graph rewriting

Unification

Termination checking

Algebra

Circuits

Propagation

Random walks

Software engineering

Proof search

Code search

Word problems

Software

Graphs

  • KeOps - Dense, sparse and symbolic tensor library
  • Alga - a library for algebraic construction and manipulation of graphs in Haskell
  • Bifurcan - high-quality JVM implementations of immutable data structures
  • Kraphviz - Graphviz with pure Java
  • JGraLab - a Java graph library implementing TGraphs: typed, attributed, ordered, and directed graphs (paper)
  • GraphBLAS - open effort to define standard building blocks for graph algorithms in the language of linear algebra
  • GraphBLAST - High-Performance Linear Algebra-based Graph Primitives on GPUs

Rewriting

  • Grez - graph transformation termination checker (manual)
  • GP2 - Rule-based graph programming language
  • AGG - development environment for attributed graph transformation systems supporting an algebraic approach to graph transformation (manual)
  • Henshin - an IDE for developing and simulating triple graph grammars (TGGs) (manual)
  • JavaSMT - Unified Java API for SMT solvers

Automata

Special thanks

The following individuals have helped inspire this project through their enthusiasm and thoughtful feedback. Please check out their work.