Abstract
Graph Neural Networks (GNNs), despite achieving remarkable performance acrossdifferent tasks, are theoretically bounded by the 1-Weisfeiler-Lehman test,resulting in limitations in terms of graph expressivity. Even though priorworks on topological higher-order GNNs overcome that boundary, these modelsoften depend on assumptions about sub-structures of graphs. Specifically,topological GNNs leverage the prevalence of cliques, cycles, and rings toenhance the message-passing procedure. Our study presents a novel perspectiveby focusing on simple paths within graphs during the topologicalmessage-passing process, thus liberating the model from restrictive inductivebiases. We prove that by lifting graphs to path complexes, our model cangeneralize the existing works on topology while inheriting several theoreticalresults on simplicial complexes and regular cell complexes. Without makingprior assumptions about graph sub-structures, our method outperforms earlierworks in other topological domains and achieves state-of-the-art results onvarious benchmarks.