Hierarchical Graph Tsetlin Machine. A canonical reference library for stacked GraphTM layers with independent automata, projected feedback for intermediate layers, and an inter-layer encoding kernel that turns each layer's per-node clause-output bits into the next layer's literal field.
University of Agder (UiA).
+-----------------------------------------------------------------+
| ALPHA (v0.1.5) |
| |
| Code: complete, 25 / 25 tests passing |
| C reference: builds with make, 8 / 8 demo OK |
| L=1 cair parity: VERIFIED bit-exact on MUTAG. HGTM L=1 |
| and cair v0.3.3 give 0.4474 from same |
| seed on identical data. |
| L=2 (joint training): TRIED twice, FAILED both times. |
| v0.1 placeholder kernel collapses to |
| majority. v0.1.5 rewritten kernel with |
| downstream include-bit walk also |
| collapses (27-run sweeps for both, |
| see docs/parity_sweep.jsonl and |
| docs/parity_sweep_v015_fixed_kernel |
| .jsonl). Diagnosis is in |
| docs/benchmarks.md: chicken-and-egg at |
| init -> upstream signal is always zero |
| -> layer 1 never trains. Open research. |
| L=2 (greedy training): SHIPPED as a separate module |
| (HierarchicalGraphTsetlinMachine/ |
| greedy.py). Layer 1 trains on labels |
| directly; layer 2 trains on layer 1's |
| transformed features. Recommended L=2 |
| entry point in v0.1.5. |
| v0.1.5 claim: "canonical library + stacking |
| infrastructure + working greedy L=2"; |
| NOT "joint L=2 beats L=1". |
| ISTM 2026: target submission, ~ June 23 2026. |
+-----------------------------------------------------------------+
| Component | State |
|---|---|
Canonical 3-axis definition (docs/canonical_definition.md) |
done |
Novelty audit, 5 closest works (docs/novelty_audit.md) |
done |
Architecture contract (docs/ARCHITECTURE.md) |
done |
Python + CUDA library (HierarchicalGraphTsetlinMachine/) |
done |
Pure-C CPU reference (c_reference/) |
done, 8 / 8 demo passes |
encode_layer_output_as_literals CUDA kernel (new) |
done, runs |
compute_projected_feedback CUDA kernel (new, v0.1.5 rewrite) |
runs, but collapses to majority-class prediction; root cause documented in docs/benchmarks.md |
HierarchicalGraphTsetlinMachine.greedy.GreedyHGTM (new) |
done, recommended L=2 entry point |
Layer count L >= 2 orchestration |
done, runs without errors |
Cair drop-in compatibility (layers=None) |
done, validated bit-exact on MUTAG |
| Synthetic depth-N parity sweep (27 runs) | done, L=2 at chance everywhere |
| Five examples, seven test files | done |
| Five-seed FEVER / TUDataset evaluation | not started; will run after credit-assignment fix |
Paper draft (PAPER.md) |
in progress |
| ISTM 2026 submission | not yet drafted |
+---> class sum
|
+-- LAYER L -----+
| | K_L clauses, T_L, s_L, depth D_L
+-- ^------------+
| encode_layer_output_as_literals
|
+-- LAYER L - 1 -+
| | K_{L-1} clauses, T_{L-1}, s_{L-1}, D_{L-1}
+-- ^------------+
|
...
|
+-- LAYER 1 -----+
| | K_1 clauses, T_1, s_1, depth D_1
+-- ^------------+
|
input graph
(Graphs object)
Each layer is an independent GraphTM with its own clauses, automata, threshold, specificity, and message-passing depth. The final layer is the class-voting head. Intermediate layers train via projected feedback through a new CUDA-C kernel.
Setting layers=None collapses to a single GraphTM that is
bit-compatible with cair/GraphTsetlinMachine v0.3.3 on the same
seed. The L >= 2 path is the canonical contribution.
flowchart LR
A[Layer count L<br/>stacking depth]
B[Message-passing<br/>rounds D per layer]
C[Tsetlin automata<br/>state bits]
A --> H{HGTM}
B --> H
C --> H
Setting any axis to its trivial value recovers an existing TM-family model exactly. Combining them is the canonical HGTM.
| L | D | observed model |
|---|---|---|
| 1 | 1 | flat-clause single-layer GraphTM |
| 1 | k > 1 | cair GraphTM with deep message passing (existing) |
| >= 2 | 1 | stacked GraphTMs, each local (Tarasyuk 2024 lifted to graphs) |
| >= 2 | k > 1 | canonical HGTM (this library) |
sequenceDiagram
participant U as user
participant G as Graphs
participant H as HGTM
participant L1 as Layer 1
participant L2 as Layer 2
U->>G: build per-graph nodes, edges, properties
G->>G: encode
U->>H: fit(graphs, Y, epochs)
loop per sample
H->>L1: calculate_messages + (depth - 1) message rounds
L1-->>H: clause_node_output (K_1 bits per node)
H->>L2: encode_layer_output_as_literals
Note over H,L2: Layer 1's clause outputs become Layer 2's literals
H->>L2: calculate_messages + (depth - 1) message rounds
L2-->>H: clause_node_output (K_2 bits per node)
H->>L2: evaluate -> class sums
H->>L2: select_clause_node + Type-I/II feedback (y)
H->>L1: compute_projected_feedback (downstream signs)
H->>L1: update (projected feedback)
end
flowchart LR
G[Graphs object<br/>encoded] --> CM1[calculate_messages<br/>layer 1]
CM1 --> MP1{depth > 1?}
MP1 -- yes --> EX1[exchange_messages<br/>encode_messages]
EX1 --> CMC1[calculate_messages<br/>conditional]
CMC1 --> MP1
MP1 -- no --> ENC[encode_layer_output<br/>as_literals]
ENC --> CM2[calculate_messages<br/>layer 2]
CM2 --> MP2{depth > 1?}
MP2 -- yes --> EX2[exchange_messages<br/>encode_messages]
EX2 --> CMC2[calculate_messages<br/>conditional]
CMC2 --> MP2
MP2 -- no --> EV[evaluate<br/>class sums]
EV --> P[predict]
flowchart TB
subgraph M1[M1 graphs builder]
GR[graphs.py:<br/>Graphs class]
end
subgraph M2[M2 CUDA kernels]
KE[kernels.py:<br/>17 CUDA kernels]
end
subgraph M3[M3 model classes]
TM[tm.py:<br/>HGTM + MultiClass*<br/>+ MultiOutput* + binary]
end
subgraph M4[M4 CPU reference]
CR[c_reference/<br/>TsetlinMachine.c +<br/>MultiClassGraphTM.c]
end
subgraph M5[M5 tests]
TS[tests/<br/>25 tests passing]
end
subgraph M6[M6 examples]
EX[examples/<br/>5 demos]
end
subgraph M7[M7 docs]
DC[docs/<br/>4 reference docs]
end
subgraph M8[M8 packaging]
PK[setup.py + pyproject.toml<br/>+ requirements.txt]
end
M1 --> M3
M2 --> M3
M3 --> M5
M3 --> M6
M3 -.parity oracle.-> M4
M7 -.cites.-> M3
M8 -.installs.-> M3
quadrantChart
title TM-family library coverage
x-axis "Tabular" --> "Graph-structured"
y-axis "Single layer" --> "Stacked layers"
quadrant-1 "Stacked + graph (HGTM goal)"
quadrant-2 "Stacked + tabular"
quadrant-3 "Single + tabular"
quadrant-4 "Single + graph"
"TM (Granmo 2018)": [0.1, 0.1]
"HTM (Granmo, Saha)": [0.1, 0.8]
"MLTM (Tarasyuk 2024)": [0.15, 0.85]
"GraphTM (Granmo 2025)": [0.85, 0.15]
"SGI-TM (Blakely 2025)": [0.85, 0.2]
"HGTM (this work)": [0.9, 0.9]
| Capability | cair GraphTM v0.3.3 | cair HTM (C) | SGI-TM | MLTM | HGTM |
|---|---|---|---|---|---|
| Per-node clause evaluation | yes | -- | yes | -- | yes |
| Message passing on graphs | yes (depth axis) | -- | yes (HD encoder) | -- | yes |
| Independent TMs per layer | -- | yes (tabular) | -- | yes (tabular) | yes (graphs) |
| Inter-layer encoding kernel | -- | -- | -- | -- | yes |
| Projected feedback for intermediate layers | -- | yes (tabular) | -- | implicit | yes (graphs) |
| Single-layer drop-in compatible with cair | is cair | -- | -- | -- | yes |
| Public code released | yes | yes | -- | -- | yes |
| Pure-C CPU reference | -- | yes | -- | -- | yes |
The empty intersection per docs/novelty_audit.md is the canonical
HGTM contribution: stacked GraphTMs with projected feedback and a
bit-exact inter-layer encoding kernel, none of which is available in
any published TM library today.
HGTM/
README.md, PAPER.md, LICENSE, CITATION.cff, .gitignore
setup.py, pyproject.toml, requirements.txt
HierarchicalGraphTsetlinMachine/
__init__.py version pinning
graphs.py host-side dataset builder (port of cair v0.3.3)
kernels.py CUDA-C kernel strings (15 cair + 2 new HGTM)
tm.py public classes + per-layer orchestration
c_reference/
TsetlinMachine.{h,c} flat-clause TM
MultiClassGraphTsetlinMachine.{h,c} one-vs-rest wrapper
XORDemo.c builds, 8 / 8 on existence task
Makefile
README.md
examples/
NoisyXORHGTMDemo.py smallest Python demo
DepthNParityOnPathDemo.py hierarchy-is-doing-work proof
MUTAGHGTMDemo.py classical TUDataset
NCI1HGTMDemo.py medium TUDataset
MNISTSuperpixelHGTMDemo.py cair parity at L=1
tests/
test_imports.py
test_graphs.py
test_layer_config.py
test_synthetic_parity.py CUDA-required, skips gracefully
test_save_load.py
test_kernels_compile.py CUDA-required, skips gracefully
test_c_reference.py
docs/
canonical_definition.md the 3-axis definition
ARCHITECTURE.md frozen interface contract
novelty_audit.md 5-way empty intersection proof
benchmarks.md target numbers, methodology
# 1. Install (CUDA-capable device required for fit / predict)
pip install -e .
# 2. CPU tests pass on a CPU box; GPU tests skip gracefully
pytest tests/ -q
# 3. C reference, smallest end-to-end demo
make -C c_reference
./c_reference/XORDemo
# 4. Smallest Python demo on the GPU
python examples/NoisyXORHGTMDemo.py
# 5. The hierarchy-is-doing-work proof
python examples/DepthNParityOnPathDemo.pyfrom HierarchicalGraphTsetlinMachine.graphs import Graphs
from HierarchicalGraphTsetlinMachine.tm import (
HierarchicalGraphTsetlinMachine, # binary
MultiClassHierarchicalGraphTsetlinMachine, # multi-class
MultiOutputHierarchicalGraphTsetlinMachine, # multi-output
)
# Single-layer mode (drop-in cair-compatible on the same seed)
model = MultiClassHierarchicalGraphTsetlinMachine(
number_of_clauses=2000,
T=1500,
s=10.0,
depth=2,
)
# Multi-layer mode (the canonical HGTM)
model = MultiClassHierarchicalGraphTsetlinMachine(
number_of_clauses=2000, T=1500, s=10.0,
layers=[
dict(number_of_clauses=1000, T=1500, s=10.0, depth=2),
dict(number_of_clauses=2000, T=2000, s=5.0, depth=2),
],
)
model.fit(graphs, Y, epochs=100)
preds = model.predict(test_graphs)
# Introspection
ta_states = model.get_ta_states(layer=-1, depth=0)
weights = model.get_weights(layer=-1)
state = model.save("hgtm_state.pkl")| Source | Component | Role in HGTM |
|---|---|---|
| Granmo 2018, arXiv 1804.01508 | original Tsetlin Machine | propositional clause learner |
| Granmo et al. 2025, arXiv 2507.14874 | GraphTM (per-node + OR + message passing) | layer-local mechanism |
| Granmo and Saha (cair/HierarchicalTsetlinMachine, C) | HTM stacking idea | inspiration for projected feedback |
| Tarasyuk et al. ISTM 2024 (IEEE 10931518) | Multi-Layer TM (tabular, no code) | confirms stacking direction |
| cair/GraphTsetlinMachine v0.3.3 | canonical Python + CUDA reference | shared kernel set + Graphs class with attribution |
What is genuinely new in HGTM and unimplemented anywhere else:
- Multi-layer GraphTM with independent automata per layer.
encode_layer_output_as_literalsCUDA-C kernel (inter-layer encoding, bit-exact and reversible).compute_projected_feedbackCUDA-C kernel (credit assignment for intermediate layers).- End-to-end orchestration in
tm.pyforL >= 2stacking. - The depth-N parity-on-path demo as the planned empirical proof that the stacking axis contributes capacity.
- Accuracy on canonical TUDatasets is expected to land 1 to 3 percentage points above single-layer GraphTM and 1 to 3 percentage points below GIN-family GNNs. The pitch is canonical reference quality and reproducible interpretability, not state-of-the-art accuracy.
- Projected feedback for intermediate layers is a documented
heuristic, not a proven convergence scheme. The same shape that
Granmo and Saha use in tabular HTM. A
freeze_layer(ell)API for strict greedy layer-wise training is a v0.2 item. - HTM-style 5-level AND-OR-AND-OR-AND tree clauses inside each layer are not yet implemented. Combining tree clauses with the stacking pipeline is a v0.2 goal.
- The depth-N parity-on-path demo is load-bearing. If that demo does
not exhibit the expected separation between
L=1andL=2, the paper's premise is in trouble. Run that demo first. - This is a single-author repository. All code, docs, and the paper draft are by Anwar (University of Agder).
@misc{anwar2026hgtm,
author = {Anwar},
title = {Hierarchical Graph Tsetlin Machine: Canonical Reference Library},
year = {2026},
howpublished = {\url{https://github.com/AnwarDebes/HGTM}},
note = {University of Agder. Work in progress.}
}MIT. Code, configs, and result JSONs are free for academic and
commercial use. See LICENSE for the full notice and upstream
attributions (cair/GraphTsetlinMachine v0.3.3 and Granmo and Saha
HTM C reference, both MIT).
Anwar, University of Agder (UiA).