Random projection forest initialization for graph convolutional networks

Graph convolutional networks (GCNs) were a great step towards extending deep learning to graphs. GCN uses the graph [Formula: see text] and the feature matrix [Formula: see text] as inputs. However, in most cases the graph [Formula: see text] is missing and we are only provided with the feature matrix [Formula: see text]. To solve this problem, classical graphs such as [Formula: see text]-nearest neighbor ([Formula: see text]-nn) are usually used to construct the graph [Formula: see text] and initialize the GCN. Although it is computationally efficient to construct [Formula: see text]-nn graphs, the constructed graph might not be very useful for learning. In a [Formula: see text]-nn graph, points are restricted to have a fixed number of edges, and all edges in the graph have equal weights. Our contribution is Initializing GCN using a graph with varying weights on edges, which provides better performance compared to [Formula: see text]-nn initialization. Our proposed method is based on random projection forest (rpForest). rpForest enables us to assign varying weights on edges indicating varying importance, which enhanced the learning. The number of trees is a hyperparameter in rpForest. We performed spectral analysis to help us setting this parameter in the right range. In the experiments, initializing the GCN using rpForest provides better results compared to [Formula: see text]-nn initialization. • Constructing the graph [Formula: see text] using rpForest sets varying weights on edges, which represents the similarity between a pair of samples.Unlike [Formula: see text]-nearest neighbor graph where all weights are equal. • Using rpForest graph to initialize GCN provides better results compared to [Formula: see text]-nn initialization. The varying weights in rpForest graph quantify the similarity between samples, which guided the GCN training to deliver better results. • The rpForest graph involves the tuning of the hyperparameter (number of trees [Formula: see text]). We provided an informative way to set this hyperparameter through spectral analysis.