Graph networks have recently attracted considerable interest, and in particular in the context of semi-supervised learning. These methods typically work by generating node representations that are propagated throughout a given weighted graph.

 Here we argue that for semi-supervised learning, it is more natural to consider propagating labels in the graph instead. Towards this end, we propose a differentiable neural version of the classic Label Propagation (LP) algorithm. This formulation can be used for learning edge weights, unlike other methods where weights are set heuristically. Starting from a layer implementing a single iteration of LP, we proceed by adding several important non-linear steps that significantly enhance the label-propagating mechanism.

 Experiments in two distinct settings demonstrate the utility of our approach.
 We study the problem of graph-based semi-supervised learning (SSL), where the goal is to correctly label all nodes of a graph, of which only a few are labeled. Methods for this problem are often based on assumptions regarding the relation between the graph and the predicted labels. One such assumption is smoothness, which states that adjacent nodes are likely to have similar labels. Smoothness can be encouraged by optimizing an objective where a loss term L over the labeled nodes is augmented with a quadratic penalty over edges: (1) Here, y are the true labels, f are "soft" label predictions, S is the set of labeled nodes, and w are non-negative edge weights. The quadratic term in Eq. (1) is often referred to as Laplacian Regularization since (for directed graphs) it can equivalently be expressed using the graph Laplacian BID5 . Many early methods for SSL have adopted the general form of Eq. (1) BID51 BID50 BID4 BID6 BID0 BID42 BID47 . Algorithms such as the seminal Label Propagation BID51 are simple, efficient, and theoretically grounded but are limited in two important ways. First, predictions are parameterized either naïvely or not at all. Second, edge weights are assumed to be given as input, and in practice are often set heuristically.Recent deep learning methods address the first point by offering intricate predictive models that are trained discriminatively BID47 BID38 BID48 BID28 BID20 BID21 BID34 . Nonetheless, many of them still require w as input, which may be surprising given the large body of work highlighting the importance of good weights BID51 BID24 BID46 BID4 BID25 . While some methods consider some form of weight learning BID45 BID35 , to some extent they have drifted away from the original quadratic criterion.Other works address the second point by proposing disciplined ways for learning w. However, these either assume specific simple parameterizations BID49 BID25 , or altogether consider weights disjointly from predictions BID46 BID32 .Our goal in this paper is to simultaneously addresses both issues. We propose a framework that, given a graph, jointly learns both a parametric predictive model and the edge weights. To do this, we begin by revisiting the Label Propagation (LP), and casting it as a differentiable neural network. Each layer in the network corresponds to a single iterative update, making a forward pass equivalent to a full run of the algorithm. Since the network is differentiable, we can then optimize the weights of the LP solution using gradient descent. As we show, this can be done efficiently with a suitable loss function.The key modeling point in our work is that labeled information is used as input to both the loss and the network. In contrast to most current methods, our network's hidden layers directly propagate labeling information, rather than node or feature representations. Each layer is therefore a self-map over the probability simplex; special care is therefore needed when introducing non-linearities. To this end , we introduce two novel architectural components that are explicitly designed to operate on distributions. The first is an information-gated attention mechanism, where attention is directed based on the informativeness and similarity of neighboring nodes' states. The second is a novel "bifurcation" operator that dynamically controls label convergence, and acts as a balancing factor to the model's depth.Our main guideline in designing our model was to tailor it to the semi-supervised setting. The result is a slim model having relatively few parameters and only one model-specific hyper-parameter (depth), making it suitable for tasks where only few labeled nodes are available. The final network provides a powerful generalization of the original propagation algorithm that can be trained efficiently. Experiments on benchmark datasets in two distinct learning settings show that our model compares favorably against strong baselines. In this work we presented a deep network for graph-based SSL. Our design process revolved around two main ideas: that edge weights should be learned, and that labeled data should be propagated. We began by revisiting the classic LP algorithm, whose simple structure allowed us to encode it as a differentiable neural network. We then proposed two novel ad-hoc components: information-gated attention and bifurcation, and kept our design slim and lightly parameterized. The resulting model is a powerful generalization of the original algorithm, that can be trained efficiently using the leave-one-out loss using few labeled nodes.We point out two avenues for future work. First, despite its non-linearities, the current network still employs the same simple averaging updates that LP does. An interesting challenge is to design general parametric update schemes, that can perhaps be learned. Second, since the Laplacian's eigenvalues play an important role in both theory and in practice, an interesting question is whether these can be used as the basis for an explicit form of regularization. We leave this for future work.
Neural net for graph-based semi-supervised learning; revisits the classics and propagates *labels* rather than feature representations
{"src": "scitldr-AIC_train", "paper_id": "r1g7y2RqYX"}