WalkGCN: a biased sampling strategy for GNNs on non-attributed graphs

Graph Neural Networks (GNNs) typically assume the presence of node attributes to capture interactions in a graph structure. However, real-world graph data often has incomplete or completely-missing attribute information. GNN approaches to dealing with incomplete attributes are widely implemented, yet there is a paucity of research on graphs without attributes. DeepWalk and node2vec can be exploited to generate artificial attributes in Graph Convolutional Networks (GCN). However, the stochastic nature of random walks disrupts consistent performance. Furthermore, it introduces a degree bias, which causes the over-sampling of hub nodes and the under-representation of low-degree nodes. To address this limitation, we propose Walk Graph Convolutional Networks (WalkGCN) for generating artificial node attributes. WalkGCN employs a biased sampling strategy that mitigates degree-induced bias during node sequence generation. It increases the sampling frequency of leaf nodes to balance the training data. The node embeddings generated in the preceding phase are employed as artificial attributes for each node. The graph with artificial attributes is then fed to the vanilla graph convolutional networks model, which performs node classification. The results of extensive experiments on three graph datasets demonstrate that WalkGCN effectively generates artificial attributes that are independent of the hyperparameters or randomness of the random walk. Furthermore, the proposed model outperforms a variety of baseline models. The code is available at https://github.com/mincheol-shin-cau/WalkGCN .