Scaling Higher-Order Graph Learning with Maximal Clique Complexes
This work provides a scalable topological learning framework for higher-order graph representation, which is a significant improvement for researchers and practitioners working with complex graph data.
This paper addresses the scalability issues of higher-order graph neural networks, which are typically limited to pairwise interactions. They introduce simplified and factored cellular Weisfeiler Leman tests (sCWL and fCWL) and the maximal clique complex, which significantly reduce time and memory complexity while maintaining strong empirical performance. They also propose CliqueWalk, a linear-scaling random walk for sampling maximal cliques.
Graph neural networks (GNNs) are limited to modeling pairwise interactions, while higher-order models based on cell complexes achieve greater expressivity but often suffer from poor scalability. We introduce simplified and factored cellular Weisfeiler Leman tests (sCWL and fCWL), which preserve the expressivity of the CWL test while improving computational efficiency. We further introduce the maximal clique complex, enabling scalable CWNs with reduced time and memory complexity while retaining strong empirical performance. To avoid explicit clique enumeration, we propose CliqueWalk, a biased random walk that samples maximal cliques and scales linearly with graph size. These contributions yield a scalable topological learning framework for higher-order graph representation.