Cycle Invariant Positional Encoding for Graph Representation Learning
Preprint
Abstract
Cycles are fundamental elements in graph-structured data and have demonstrated their effectiveness in enhancing graph learning models. To encode such information into a graph learning framework, prior works often extract a summary quantity, ranging from the number of cycles to the more sophisticated persistence diagram summaries. However, more detailed information, such as which edges are encoded in a cycle, has not yet been used in graph neural networks. In this paper, we make one step towards addressing this gap, and propose a structure encoding module, called CycleNet, that encodes cycle information via edge structure encoding in a permutation invariant manner. To efficiently encode the space of all cycles, we start with a cycle basis (i.e., a minimal set of cycles generating the cycle space) which we compute via the kernel of the 1-dimensional Hodge Laplacian of the input graph. To guarantee the encoding is invariant w.r.t. the choice of cycle basis, we encode the cycle information via the orthogonal projector of the cycle basis, which is inspired by BasisNet proposed by Lim et al. We also develop a more efficient variant which however requires that the input graph has a unique shortest cycle basis. To demonstrate the effectiveness of the proposed module, we provide some theoretical understandings of its expressive power. Moreover, we show via a range of experiments that networks enhanced by our CycleNet module perform better in various benchmarks compared to several existing SOTA models.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Improving Graph Neural Network Expressivity via Subgraph Isomorphism CountingIEEE Transactions on Pattern Analysis and Machine Intelligence, 2022
- On Weisfeiler-Leman invariance: Subgraph counts and related graph propertiesJournal of Computer and System Sciences, 2020
- Graph neural networks: A review of methods and applicationsAI Open, 2020
- Hodge Laplacians on GraphsSIAM Review, 2020
- SLIC Superpixels Compared to State-of-the-Art Superpixel MethodsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2012
- Statistical ranking and combinatorial Hodge theoryMathematical Programming, 2010
- An efficient algorithm for detecting frequent subgraphs in biological networksBioinformatics, 2004
- Automated Approaches for Classifying Structures2002
- An optimal lower bound on the number of variables for graph identificationCombinatorica, 1992