  Graph Neural Networks (GNNs) are increasingly becoming the favorite method
for graph learning. They exploit the semi-supervised nature of deep learning,
and they bypass computational bottlenecks associated with traditional graph
learning methods. In addition to the feature matrix $X$, GNNs need an adjacency
matrix $A$ to perform feature propagation. In many cases, the adjacency matrix
$A$ is missing. We introduce a graph construction scheme that constructs the
adjacency matrix $A$ using unsupervised and supervised information.
Unsupervised information characterizes the neighborhood around points. We used
Principal Axis trees (PA-trees) as a source for unsupervised information, where
we create edges between points falling onto the same leaf node. For supervised
information, we used the concept of penalty and intrinsic graphs. A penalty
graph connects points with different class labels, whereas an intrinsic graph
connects points with the same class labels. We used the penalty and intrinsic
graphs to remove or add edges to the graph constructed via PA-tree. We tested
this graph construction scheme on two well-known GNNs: 1) Graph Convolutional
Network (GCN) and 2) Simple Graph Convolution (SGC). The experiments show that
it is better to use SGC because it is faster and delivers better or the same
results as GCN. We also test the effect of oversmoothing on both GCN and SGC.
We found out that the level of smoothing has to be carefully selected for SGC
to avoid oversmoothing.
