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

📄 arXiv: 2507.14874v1 📥 PDF

作者: Ole-Christoffer Granmo, Youmna Abdelwahab, Per-Arne Andersen, Paul F. A. Clarke, Kunal Dumbre, Ylva Grønninsæter, Vojtech Halenka, Runar Helin, Lei Jiao, Ahmed Khalid, Rebekka Omslandseter, Rupsa Saha, Mayur Shende, Xuan Zhang

分类: cs.LG, cs.AI

发布日期: 2025-07-20

备注: 34 pages, 10 figures

💡 一句话要点

提出Graph Tsetlin Machine，用于图结构数据的可解释深度逻辑学习与推理。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 图神经网络 可解释性 Tsetlin Machine 逻辑推理 深度学习 图表示学习 消息传递

📋 核心要点

  1. 现有方法难以从图结构数据中学习可解释的深度逻辑规则，限制了其在复杂关系推理任务中的应用。
  2. GraphTM通过消息传递机制构建嵌套的深度子句，从而能够高效地识别图结构中的复杂模式。
  3. 实验结果表明，GraphTM在图像分类、动作共指、推荐系统和基因组序列分析等任务上均取得了显著的性能提升。

📝 摘要（中文）

Tsetlin Machine (TM) 通过简洁的扁平AND规则实现模式识别，兼具可解释性和效率。本文提出 Graph Tsetlin Machine (GraphTM)，用于从图结构输入中学习可解释的深度子句。GraphTM突破了扁平、固定长度输入的限制，支持序列、网格、关系和多模态数据。通过消息传递，GraphTM构建嵌套的深度子句，以指数级更少的子句识别子图模式，从而提高可解释性和数据利用率。在图像分类中，GraphTM在CIFAR-10上的准确率比卷积TM高3.86个百分点。在跟踪动作共指方面，GraphTM优于其他强化学习方法，最高提升20.6个百分点。在推荐系统中，GraphTM比图卷积神经网络(GCN)更能容忍噪声，例如，在噪声比为0.1时，GraphTM的准确率为89.86%，而GCN为70.87%。最后，对于病毒基因组序列数据，GraphTM在准确性方面与BiLSTM-CNN和GCN具有竞争力，并且训练速度比GCN快2.5倍。GraphTM在这些不同领域的应用展示了图表示学习和深度子句如何为TM学习带来新的可能性。

🔬 方法详解

问题定义：现有Tsetlin Machine (TM) 主要处理扁平、固定长度的输入，难以直接应用于图结构数据，无法有效捕捉图中的复杂关系和依赖。现有方法在处理图结构数据时，通常缺乏可解释性，并且在数据利用率方面存在不足。

核心思路：GraphTM的核心思路是利用消息传递机制，在图结构数据上构建嵌套的深度子句。通过迭代地聚合邻居节点的信息，GraphTM能够学习到节点之间的复杂关系，并将其编码到可解释的逻辑规则中。这种设计使得GraphTM能够以指数级更少的子句识别子图模式，从而提高可解释性和数据利用率。

技术框架：GraphTM的整体框架包括以下几个主要阶段：1) 图表示构建：将输入数据表示为图结构，节点表示实体，边表示关系。2) 消息传递：通过迭代地聚合邻居节点的信息，更新节点表示。3) 深度子句学习：利用Tsetlin Automata学习嵌套的深度子句，用于识别图中的模式。4) 推理：利用学习到的深度子句进行推理和预测。

关键创新：GraphTM最重要的技术创新点在于其能够从图结构数据中学习可解释的深度子句。与传统的图神经网络相比，GraphTM的输出是可解释的逻辑规则，而非黑盒的数值向量。此外，GraphTM通过消息传递机制，能够有效地捕捉图中的复杂关系，从而提高模型的性能。

关键设计：GraphTM的关键设计包括：1) 消息传递函数的设计，用于聚合邻居节点的信息。2) Tsetlin Automata的参数设置，用于控制子句的学习过程。3) 损失函数的设计，用于优化模型的性能。具体的消息传递函数和损失函数根据不同的应用场景进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

GraphTM在多个任务上取得了显著的性能提升。在CIFAR-10图像分类任务中，GraphTM的准确率比卷积TM高3.86个百分点。在动作共指任务中，GraphTM优于其他强化学习方法，最高提升20.6个百分点。在推荐系统中，GraphTM比GCN更能容忍噪声，例如，在噪声比为0.1时，GraphTM的准确率为89.86%，而GCN为70.87%。在病毒基因组序列数据分析中，GraphTM在准确性方面与BiLSTM-CNN和GCN具有竞争力，并且训练速度比GCN快2.5倍。

🎯 应用场景

GraphTM具有广泛的应用前景，包括但不限于：图像分类、动作共指、推荐系统、基因组序列分析、社交网络分析、知识图谱推理等。其可解释性使得模型能够提供决策依据，增强用户信任。未来，GraphTM有望在医疗诊断、金融风控等高风险领域发挥重要作用。

📄 摘要（原文）

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 greater extent than a Graph Convolutional Neural Network (GCN), e.g., for noise ratio 0.1, GraphTM obtains accuracy 89.86% compared to GCN's 70.87%. 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.