Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization

• URL: http://arxiv.org/abs/2508.10651v1
• Date: Thu, 14 Aug 2025 13:47:50 GMT
• Title: Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization
• Abstract summary: We investigate a class of Weisfeiler-Leman variants obtained by modifying the underlying logical framework.<n>We then test two selected variants on twelve benchmark datasets that span a range of different domains.<n>The experiments demonstrate that our approach matches the accuracy of state-of-the-art graph neural networks and graph kernels.
• Score: 3.701026888201779
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel approach for graph classification based on tabularizing graph data via variants of the Weisfeiler-Leman algorithm and then applying methods for tabular data. We investigate a comprehensive class of Weisfeiler-Leman variants obtained by modifying the underlying logical framework and establish a precise theoretical characterization of their expressive power. We then test two selected variants on twelve benchmark datasets that span a range of different domains. The experiments demonstrate that our approach matches the accuracy of state-of-the-art graph neural networks and graph kernels while being more time or memory efficient, depending on the dataset. We also briefly discuss directly extracting interpretable modal logic formulas from graph datasets.

Related papers

• Training A Foundation Model to Represent Graphs as Vectors [24.592499205332413]
  This paper aims to train a graph foundation model that is able to represent any graph as a vector preserving semantic information.<n>We provide a theoretical generalization bound to support the effectiveness of the proposed model.<n>The experimental results of few-shot graph classification and graph clustering show that our model outperforms strong baselines.
  arXiv  Detail & Related papers  (2026-02-04T06:06:28Z)
• X2Graph for Cancer Subtyping Prediction on Biological Tabular Data [8.26719624422426]
  We propose X2Graph, a novel deep learning method that achieves strong performance on small biological datasets.<n>X2Graph leverages external knowledge about the relationships between table columns, such as gene interactions, to convert each sample into a graph structure.<n>Our X2Graph method demonstrates superior performance compared to existing tree-based and deep learning methods across three cancer subtyping datasets.
  arXiv  Detail & Related papers  (2025-05-29T10:50:02Z)
• Graph-Dictionary Signal Model for Sparse Representations of Multivariate Data [49.77103348208835]
  We define a novel Graph-Dictionary signal model, where a finite set of graphs characterizes relationships in data distribution through a weighted sum of their Laplacians. We propose a framework to infer the graph dictionary representation from observed data, along with a bilinear generalization of the primal-dual splitting algorithm to solve the learning problem. We exploit graph-dictionary representations in a motor imagery decoding task on brain activity data, where we classify imagined motion better than standard methods.
  arXiv  Detail & Related papers  (2024-11-08T17:40:43Z)
• TabGSL: Graph Structure Learning for Tabular Data Prediction [10.66048003460524]
  We present a novel solution, Tabular Graph Structure Learning (TabGSL), to enhance tabular data prediction. Experiments conducted on 30 benchmark datasets demonstrate that TabGSL markedly outperforms both tree-based models and recent deep learning-based models.
  arXiv  Detail & Related papers  (2023-05-25T08:33:48Z)
• Joint Graph and Vertex Importance Learning [47.249968772606145]
  We propose a novel method to learn a graph with smaller edge weight upper bounds compared to Laplacian approaches. Experimentally, our approach yields much sparser graphs compared to a Laplacian approach, with a more interpretable model.
  arXiv  Detail & Related papers  (2023-03-15T12:12:13Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Learning to Learn Graph Topologies [27.782971146122218]
  We learn a mapping from node data to the graph structure based on the idea of learning to optimise (L2O) The model is trained in an end-to-end fashion with pairs of node data and graph samples. Experiments on both synthetic and real-world data demonstrate that our model is more efficient than classic iterative algorithms in learning a graph with specific topological properties.
  arXiv  Detail & Related papers  (2021-10-19T08:42:38Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations [39.8498896531672]
  Semi-supervised learning on graphs is a widely applicable problem in network science and machine learning. We develop a Markov random field model for the data generation process of node attributes. We show that label propagation, a linearized graph convolutional network, and their combination can all be derived as conditional expectations.
  arXiv  Detail & Related papers  (2021-01-19T17:07:08Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.