Kaliningraph is a purely functional graph library with a DSL for constructing graphs and visualizing the behavior of graph algorithms.
Kaliningraph is hosted on JitPack.
repositories {
maven("https://jitpack.io")
}
dependencies {
implementation("com.github.breandan:kaliningraph:-SNAPSHOT")
}<project>
<repositories>
<repository>
<id>jitpack.io</id>
<url>https://jitpack.io</url>
</repository>
</repositories>
<dependency>
<groupId>com.github.breandan</groupId>
<artifactId>kaliningraph</artifactId>
<version>0.0.1</version>
</dependency>
</project>First install the Kotlin Jupyter kernel, then run the jupyterInstall task to install the library descriptor:
./gradlew jupyterInstall [-Path=~/.jupyter_kotlin/libraries]
To access notebook support, use the following line magic:
%use kaliningraph
For more information, explore the tutorial.
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.
Run the demo via ./gradlew HelloKaliningraph to get started.
To construct a graph, the graph builder DSL provides an small alphabet:
val graph = Graph { a - b - c - d - e; a - c - e }This is the same as:
val abcde = Graph { a - b - c - d - e }
val ace = Graph { a - c - e }
val graph = abcde + aceEquality is supported using the Weisfeiler-Lehman test:
val x = Graph { a - b - c - d - e; a - c - e }
val y = Graph { b - c - d - e - f; b - d - f }
assertEquals(x == y) // trueKaliningraph supports a number of graph visualizations.
Graph visualization is made possible thanks to KraphViz.
val de = Graph { d - e }
val dacbe = Graph { d - a - c - b - e }
val dce = Graph { d - c - e }
val abcd = Graph { a - b - c - d }
val cfde = Graph { c - "a" - f - d - e }
val dg = Graph(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 PrefAttach).
Computational notebooks prototyping is also supported.
Notebook {
a = b + c
f = b - h
}.show()
The above snippet should display something like the following:
Bidirectional translation to various graph formats, including Graphviz, JGraphT, Tinkerpop and RedisGraph is supported:
val g = Graph { a - b - c - a }
.toJGraphT().toKaliningraph()
.toTinkerpop().toKaliningraph()
.toGraphviz().toKaliningraph()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:
- 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 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?
- 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?
- λ expressions can be represented as a graph/matrix
- Maybe Arrighi and Dowek (2017) have the answer?
- Look into optimal beta reduction and Lamping's optimal reduction algorithm
- Solutio problematis ad geometriam situs pertinentis, Euler (1741)
- Account of the Icosian Calculus, Hamilton (1858)
- Mathematical Foundations of the GraphBLAS, Kepner et al. (2016)
- Graph Algorithms in the Language of Linear Algebra, Kepner and Gilbert (2011)
- Graph Representation Learning, Hamilton (2020)
- Spectral Graph Theory with Applications to ML, Miller (2020)
- Neural Execution of Graph Algorithms, Veličković et al. (2020)
- Functional programming with structured graphs, Oliveira and Cook (2012)
- Think Like a Vertex, Behave Like a Function! A Functional DSL for Vertex-Centric Big Graph Processing, Emoto et al. (2016)
- Inductive Graphs and Functional Graph Algorithms, Erwig (2001)
- Fully Persistent Graphs – Which One To Choose?, Erwig (1997)
- The Program Dependence Graph and its Use for Optimization, Ferrante et al. (1987)
- Seam: Provably Safe Local Edits on Graphs, Papadakis et al. (2017)
- Equational term graph rewriting, Ariola and Klop (1997)
- Bisimilarity in Term Graph Rewriting, Ariola et al. (2000)
- LEAN: An intermediate language based on graph rewriting, Barendregt et al. (1988)
- An Algorithm for Optimal Lambda Calculus Reduction, Lamping (1990)
- A New Implementation Technique for Applicative Languages, Turner (1979)
- A Reformulation of Matrix Graph Grammars with Boolean Complexes, Velasco and de Lara (2009)
- Towards a GPU-based implementation of interaction nets, Jiresch (2012)
- A Catalogue of Canonical Term Rewriting Systems, Hullot (1980)
- Graph Unification and Matching, Plump and Habel (1996)
- Unification with Drags, Jouannaud and Orejas (2020)
- The identity problem for elementary functions and constants, Richardson and Fitch (1994)
- Duplicate code detection using anti-unification, Bulychev and Minea (2008)
- Proving Termination of Graph Transformation Systems using Weighted Type Graphs over Semirings, Bruggink (2015)
- Termination of string rewriting with matrix interpretations, Hofbauer (2006)
- Matrix Interpretations for Proving Termination of Term Rewriting, Endrullis et al. (2007)
- Graph Path Orderings, Dershowitz and Jouannaud (2019)
- Algebraic Graphs with Class (Functional Pearl), Mokhov (2017)
- Fun with Semirings, Dolan (2013)
- Introduction to Algebraic Theory of Graph Grammars, Erhig (1978)
- Drags: A Simple Algebraic Framework For Graph Rewriting, Dershowitz and Jouannaud (2018)
- An Algebraic Theory of Graph Reduction, Arnborg (1993)
- Lineal: A linear-algebraic λ-calculus, Arrighi and Dowek (2017)
- Graph products, Wikipedia
- Graphs and Geometry, Lovász (2019)
- Efficient parallel evaluation of straight-line code and arithmetic circuits, Miller (1986)
- Algebraic Decision Diagrams and Their Applications, Bahar et al. (1997)
- Arithmetic Circuit Verification Based on Word-Level Decision Diagrams, Chen (1998)
- An Efficient Graph Representation for Arithmetic Circuit Verification, Chen and Bryant (2001)
- A Top-Down Compiler for Sentential Decision Diagrams, Oztok and Darwiche (2015)
- Representations of Elementary Functions Using Edge-Valued MDDs, Nagayama and Sasao (2007)
- Complexities of Graph-Based Representations for Elementary Functions, Nagayama and Sasao (2008)
- Numerical Function Generators Using LUT Cascades, Sasao and Nagayama (2007)
- Unifying Graph Convolutional Neural Networks and Label Propagation, Wang and Leskovec (2020)
- Equilibrium Propagation: Bridging the Gap between Energy-Based Models and Backpropagation Scellier and Bengio (2017)
- Expectation Propagation for Approximate Bayesian Inference, Minka (2001)
- Propagation Networks: A Flexible and Expressive Substrate for Computation, Radul (2009)
- The Art of the Propagator, Radul and Sussman (2009)
- Fusion, propagation, and structuring in belief networks, Pearl (1986)
- Random Walks on Graphs: A Survey, Lovász (1993)
- String Edit Distance, Random Walks and Graph Matching, Kelly and Hancock (2002)
- Exact and Approximate Graph Matching Using Random Walks, Gori and Maggini (2005)
- Reweighted random walks for graph matching, Cho and Lee (2010)
- Small Subgraphs in the trace of a random walk, Krivelevich and Michaeli (2018)
- Biased random walk on the trace of a biased random walk on the trace of..., Crydon and Holmes (2019)
- KnightKing: A Fast Distributed Graph Random Walk Engine, Yang et al. (2019)
- Getting F-Bounded Polymorphism into Shape, Tate (2014)
- Frequent Subgraph Analysis and its Software Engineering Applications, Henderson (2017)
- Semantic Enrichment of Data Science Code, Patterson (2020)
- Finally, a Polymorphic Linear Algebra Language, Shaikhha and Parreaux (2019)
- Towards an API for the Real Numbers, Boehm (2020)
- Generative Language Modeling for Automated Theorem Proving, Polu et al. (2020)
- Towards Proof Synthesis Guided by Neural Machine Translation for Intuitionistic Propositional Logic, Sekiyama et al. (2020)
- Can Neural Networks Learn Symbolic Rewriting?, Piotrowski et al. (2020)
- Tree Neural Networks in HOL4, Gauthier (2020)
- Modelling High-Level Mathematical Reasoning in Mechanised Declarative Proofs, Li et al. (2020)
- Approximate Online Pattern Matching in Sub-linear Time, Chakraborty et al. (2018)
- Improved online algorithms for jumbled matching, Ghuman et al. (2018)
- Parallelizing Exact and Approximate String Matching via Inclusive Scan on a GPU, Mitani et al. (2017)
- A Novel Algorithm for Online Inexact String Matching and its FPGA Implementation, Cinti et al. (2019)
- Context-Free Path Querying by Matrix Multiplication, Azimov and Grigorev (2018)
- Code Search on Bytecode for Mobile App Development, Nguyen et al. (2019)
- Uses a HMM to model transitions between method calls
- 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
- 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
