Representing Tuple in Graph with Trail Structure

Zhongbao Zhang

doi:10.1145/3795689

Return

Representing Tuple in Graph with Trail Structure

2026-03-01

PRE

DOI：10.1145/3795689

Original request for help

Save

Abstract

En 中文

In recent years, Message Passing Neural Networks (MPNNs) have emerged as a leading paradigm for learning over graph-structured data, owing to their simple architecture and excellent scalability. However, their expressive power is strictly limited by the one-dimensional Weisfeiler-Leman (1-WL) test. A common approach to enhance expressivity is designing models based on higher-order k-WL and k-Folklore WL (k-FWL) tests, collectively referred to as tuple-based GNNs. Despite their greater expressive power, these methods face two major challenges: (1) The neighboring tuples in k-WL/F WL are generated by replacing any node in the graph, disregarding adjacency relationships and thus failing to capture structural dependencies between tuples. (2) The design of k-WL/F WL lacks flexibility, while increasing k enhances expressivity, it also results in an exponential surge in time and space complexity. To overcome these limitations, we propose Trail-WL, a more expressive variant of the WL test, along with its neural network counterpart, Trail-based Tuple Neural Network (TTNN). We redefine node tuples as collections of trail structures, providing a more intuitive representation of graph connectivity compared to prior tuple-based methods. By incorporating variable trail lengths and node distance constraints, our model adaptively balances expressivity and scalability while preserving essential structural features. Furthermore, we propose and formally prove three theoretical expressivity theorems for Trail-WL. Finally, we conduct comprehensive experiments on both synthetic and real-world datasets, demonstrating that our approach consistently matches or outperforms baseline methods, thereby substantiating its effectiveness.

Keywords:

Graph Neural Networks

Graph Representation Learning

Expressive Power of GNNs