SP-GNN: Learning structure and position information from graphs

Abstract

<p>Graph <a href="https://www.sciencedirect.com/topics/mathematics/neural-network" title="Learn more about neural network from ScienceDirect's AI-generated Topic Pages">neural network</a> (GNN) is a powerful model for learning from graph data. However, existing GNNs may have limited <a href="https://www.sciencedirect.com/topics/computer-science/expressive-power" title="Learn more about expressive power from ScienceDirect's AI-generated Topic Pages">expressive power</a>, especially in terms of capturing adequate structural and positional information of input graphs. Structure properties and node position information are unique to graph-structured data, but few GNNs are capable of capturing them. This paper proposes <em>Structure-</em> and <em>Position-aware Graph Neural Networks (SP-GNN)</em>, a new class of GNNs offering generic and <a href="https://www.sciencedirect.com/topics/computer-science/expressive-power" title="Learn more about expressive power from ScienceDirect's AI-generated Topic Pages">expressive power</a> of graph data. SP-GNN enhances the expressive power of GNN architectures by incorporating a near-isometric proximity-aware position encoder and a scalable structure encoder. Further, given a GNN learning task, SP-GNN can be used to analyze positional and structural awareness of GNN tasks using the corresponding embeddings computed by the encoders. The awareness scores can guide fusion strategies of the extracted positional and structural information with raw features for better performance of GNNs on downstream tasks. We conduct extensive experiments using SP-GNN on various graph datasets and observe significant improvement in classification over existing GNN models.<br></p>