Learning Parametrised Graph Shift Operators

Abstract

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.

arXiv comment17 pages, 8 figures

References in corpus (13)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Stochastic blockmodels and community structure in networks
• Discrete Signal Processing on Graphs
• Simplifying Graph Convolutional Networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Towards Deeper Graph Neural Networks
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Benchmarking Graph Neural Networks
• Geom-GCN: Geometric Graph Convolutional Networks
• On the Bottleneck of Graph Neural Networks and its Practical Implications
• Position-aware Graph Neural Networks