InvGNN: Learning Invertible Node Representations on Graphs

Over the past decade, Graph Neural Networks (GNNs) have become a standard tool for solving machine learning problems on graphs. While many aspects of GNNs have been studied in depth, including their efficiency and expressive power, the invertibility of these models has remained largely unexplored. Standard aggregation functions, such as the mean, max and sum operators, are not invertible, which limits their applicability in tasks requiring invertible transformations. In this work, we introduce an invertible GNN layer. By stacking multiple such layers, we construct fully invertible GNN models, which we refer to as InvGNNs. These models inherit the benefits of invertible neural networks, including low memory usage for deep architectures, exact likelihood computation, and generative modeling capabilities. We demonstrate that InvGNNs can match the expressive power of the 1-dimensional Weisfeiler-Leman algorithm, showing that invertibility does not compromise model expressiveness. On standard graph classification benchmarks, our model performs comparably to other well-established GNNs. Beyond classification, we demonstrate the potential of invertible layers through density estimation tasks, including outlier detection and node feature generation.

While invertible architectures exist in several domains, such as images and sequences, invertible neural network layers for graph-structured data remain underexplored. This motivated us to investigate the design of an invertible neighborhood aggregation scheme for graphs. To address this challenge, we build on an invertible graph operator based on the matrix exponential of the adjacency matrix. This operator enables invertible neighborhood aggregation, and when combined with invertible fully-connected transformations and invertible activation functions, it yields fully invertible graph neural network layers. This work is important because it enables invertible modeling in the graph domain, unlocking several key advantages. Invertible GNNs support exact likelihood computation, reduce memory usage during training of deep architectures, and enable generative modeling of graph-structured data.