Centrality-based and similarity-based neighborhood extension in graph neural networks

In recent years, Graph Neural Networks (GNNs) have become a key technique to address various graph-based machine learning tasks. Most of existing GNNs use simple neighborhoods based on immediate neighbors of nodes, to update nodes’ features through message passing. However, on the one hand, there usually exist influential nodes in a network that impact many other nodes that are not necessarily directly connected to them. On the other hand, nodes that are similar to each other in the graph should also find similar embeddings by GNNs in the embeddings space. Therefore, it seems reasonable to include such similar nodes in the neighborhoods of each other. Taking these observations into account, in this paper, we propose two methods to extend neighborhoods of nodes, for message passing in graph neural networks. Our first method is based on node centrality notions, where we connect some important (central) nodes to a number of randomly chosen nodes. Our second method is based on node similarity notions, where we select and connect some pairs of unconnected nodes, sampled proportional to similarity scores between their two nodes. Our extensive experiments reveal that our proposed methods improve the performance of GNNs, for tasks such as link prediction and node classification up to 8.2% and 5.3%, respectively.