用逻辑增强的图同构检测方法，把图数据转成表格后高效分类。
Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization
- 基于逻辑框架改进威斯费勒-莱曼算法，提升图结构表达能力
- 在14个数据集上达到GNN/Transformer水平，最大4万样本
- 无需GPU、调参少，速度比主流方法快5到20倍
我们提出一种新的图分类方法：通过改进的威斯费勒-莱曼算法将图数据转化为表格形式，再应用传统表格数据方法进行分类。改进基于逻辑框架的重构，并通过广义量化符的双人博弈论拓展，精确刻画了新算法的表达能力。在涵盖多个应用领域的14个数据集上测试，结果表明：在最多40,000样本的数据集上，该方法性能普遍接近图神经网络（GNN）与图变换器（Graph Transformer），且无需使用GPU或复杂超参数调优。即使包含本方法的调参时间而未计入基线调参时间，其速度仍快5至20倍；当所有方法均包含调参耗时时，优势更加显著。
原文摘要 · Abstract (English)
We present a novel approach for graph classification based on tabularizing graph data via new variants of the Weisfeiler-Leman algorithm and then applying methods for tabular data. The variants are obtained by modifying the underlying logical framework, and we establish a precise theoretical characterization of their expressive power using a novel generalization of the bisimulation game for generalized quantifiers. We then test our method on 14 datasets that span a range of application domains. The experiments demonstrate that on datasets with up to 40 000 samples, our approach generally matches the predictive performance of graph neural networks and graph transformers, without requiring a GPU or extensive hyperparameter tuning. Even when our method's tuning time is included and the baselines' is not, our method is 5-20 times faster. When tuning time is included for all methods, the gap is significantly greater in favour of our method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。