Stable and Transferable Hyper-Graph Neural Networks
This work addresses stability and transferability issues in hypergraph signal processing, which is incremental as it extends existing GNN frameworks to hypergraphs with new theoretical bounds.
The authors tackled the problem of processing signals on hypergraphs using graph neural networks (GNNs) by introducing a Hyper-graph Expansion Neural Network (HENN), providing the first bounds on stability and transferability error, and showing that these errors depend on spectral similarity and improve with larger graphs.
We introduce an architecture for processing signals supported on hypergraphs via graph neural networks (GNNs), which we call a Hyper-graph Expansion Neural Network (HENN), and provide the first bounds on the stability and transferability error of a hypergraph signal processing model. To do so, we provide a framework for bounding the stability and transferability error of GNNs across arbitrary graphs via spectral similarity. By bounding the difference between two graph shift operators (GSOs) in the positive semi-definite sense via their eigenvalue spectrum, we show that this error depends only on the properties of the GNN and the magnitude of spectral similarity of the GSOs. Moreover, we show that existing transferability results that assume the graphs are small perturbations of one another, or that the graphs are random and drawn from the same distribution or sampled from the same graphon can be recovered using our approach. Thus, both GNNs and our HENNs (trained using normalized Laplacians as graph shift operators) will be increasingly stable and transferable as the graphs become larger. Experimental results illustrate the importance of considering multiple graph representations in HENN, and show its superior performance when transferability is desired.