  Graph Neural Networks have shown excellent performance on semi-supervised
classification tasks. However, they assume access to a graph that may not be
often available in practice. In the absence of any graph, constructing
k-Nearest Neighbor (kNN) graphs from the given data have shown to give
improvements when used with GNNs over other semi-supervised methods. This paper
proposes a semi-supervised graph learning method for cases when there are no
graphs available. This method learns a graph as a convex combination of the
unsupervised kNN graph and a supervised label-affinity graph. The
label-affinity graph directly captures all the nodes' label-affinity with the
labeled nodes, i.e., how likely a node has the same label as the labeled nodes.
This affinity measure contrasts with the kNN graph where the metric measures
closeness in the feature space. Our experiments suggest that this approach
gives close to or better performance (up to 1.5%), while being simpler and
faster (up to 70x) to train, than state-of-the-art graph learning methods. We
also conduct several experiments to highlight the importance of individual
components and contrast them with state-of-the-art methods.
