# The Tsetlin Machine Goes Deep: Logical Learning and Reasoning With Graphs

arXiv: https://arxiv.org/abs/2507.14874 · HTML: https://mlsanity.com/paper/2507.14874/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 36 references that are in the map.
- First posted on arXiv 20 Jul 2025.

## Builds on (most cited first, 20 of 20)

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Character-level Convolutional Networks for Text Classification](https://mlsanity.com/paper/1509.01626/) (2015)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [Variational Autoencoders for Collaborative Filtering](https://mlsanity.com/paper/1802.05814/) (2018)
- [The Tsetlin Machine -- A Game Theoretic Bandit Driven Approach to Optimal Pattern Recognition with Propositional Logic](https://mlsanity.com/paper/1804.01508/) (2018)
- [Multimodal learning with graphs](https://mlsanity.com/paper/2209.03299/) (2022)
- [From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood](https://mlsanity.com/paper/1704.07926/) (2017)
- [The Convolutional Tsetlin Machine](https://mlsanity.com/paper/1905.09688/) (2019)
- [Simpler Context-Dependent Logical Forms via Model Projections](https://mlsanity.com/paper/1606.05378/) (2016)
- [Elliot: a Comprehensive and Rigorous Framework for Reproducible Recommender Systems Evaluation](https://mlsanity.com/paper/2103.02590/) (2021)
- [Coalesced Multi-Output Tsetlin Machines with Clause Sharing](https://mlsanity.com/paper/2108.07594/) (2021)
- [On the Convergence of Tsetlin Machines for the XOR Operator](https://mlsanity.com/paper/2101.02547/) (2021)
- [Tsetlin Machine Embedding: Representing Words Using Logical Expressions](https://mlsanity.com/paper/2301.00709/) (2023)
- [Enhancing Interpretable Clauses Semantically using Pretrained Word Representation](https://mlsanity.com/paper/2104.06901/) (2021)
- [Tsetlin Machine for Solving Contextual Bandit Problems](https://mlsanity.com/paper/2202.01914/) (2022)
- [An Optimized Toolbox for Advanced Image Processing with Tsetlin Machine Composites](https://mlsanity.com/paper/2406.00704/) (2024)
- [Exploring Effects of Hyperdimensional Vectors for Tsetlin Machines](https://mlsanity.com/paper/2406.02648/) (2024)
- [Our Model Achieves Excellent Performance on MovieLens: What Does it Mean?](https://mlsanity.com/paper/2307.09985/) (2023)

## Built on by (most cited first, 2 of 2)

- [Macroeconomic Message Passing for Anticipating Foreign Exchange Regime Changes: A Deep Logical Learning Approach using Graph Tsetlin Machines](https://mlsanity.com/paper/2607.06719/) (2026)
- [Autonomous Collaborative Learning Among an Ensemble of Tsetlin Machines with Consensus-Based Inference](https://mlsanity.com/paper/2607.20124/) (2026)

## Abstract (arXiv)

Pattern recognition with concise and flat AND-rules makes the Tsetlin Machine (TM) both interpretable and efficient, while the power of Tsetlin automata enables accuracy comparable to deep learning on an increasing number of datasets. We introduce the Graph Tsetlin Machine (GraphTM) for learning interpretable deep clauses from graph-structured input. Moving beyond flat, fixed-length input, the GraphTM gets more versatile, supporting sequences, grids, relations, and multimodality. Through message passing, the GraphTM builds nested deep clauses to recognize sub-graph patterns with exponentially fewer clauses, increasing both interpretability and data utilization. For image classification, GraphTM preserves interpretability and achieves 3.86%-points higher accuracy on CIFAR-10 than a convolutional TM. For tracking action coreference, faced with increasingly challenging tasks, GraphTM outperforms other reinforcement learning methods by up to 20.6%-points. In recommendation systems, it tolerates increasing noise to a great extent, similar to a GCN. Finally, for viral genome sequence data, GraphTM is competitive with BiLSTM-CNN and GCN accuracy-wise, training ~2.5x faster than GCN. The GraphTM's application to these varied fields demonstrates how graph representation learning and deep clauses bring new possibilities for TM learning.