Learning Parametrised Graph Shift Operators
This work addresses the need for more flexible graph representations in machine learning, offering a novel operator that can enhance state-of-the-art GNNs, though it appears incremental as it builds on existing GSO frameworks.
The authors tackled the problem of improving graph neural network (GNN) performance by proposing a parametrised graph shift operator (PGSO) that generalizes common operators like adjacency and Laplacian matrices, and they showed that integrating PGSO into GNN architectures boosts accuracy in node- and graph-classification tasks on real-world datasets.
In many domains data is currently represented as graphs and therefore, the graph representation of this data becomes increasingly important in machine learning. Network data is, implicitly or explicitly, always represented using a graph shift operator (GSO) with the most common choices being the adjacency, Laplacian matrices and their normalisations. In this paper, a novel parametrised GSO (PGSO) is proposed, where specific parameter values result in the most commonly used GSOs and message-passing operators in graph neural network (GNN) frameworks. The PGSO is suggested as a replacement of the standard GSOs that are used in state-of-the-art GNN architectures and the optimisation of the PGSO parameters is seamlessly included in the model training. It is proved that the PGSO has real eigenvalues and a set of real eigenvectors independent of the parameter values and spectral bounds on the PGSO are derived. PGSO parameters are shown to adapt to the sparsity of the graph structure in a study on stochastic blockmodel networks, where they are found to automatically replicate the GSO regularisation found in the literature. On several real-world datasets the accuracy of state-of-the-art GNN architectures is improved by the inclusion of the PGSO in both node- and graph-classification tasks.