Title: No title found

Abstract: 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.

1. INTRODUCTION:

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:

min f L(y S , f S ) + λ (i,j)∈E w ij f i -f j 2 2 (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 (Belkin et al., 2006) .

Many early methods for SSL have adopted the general form of Eq. (1) (Zhu et al., 2003; Zhou et al., 2004; Belkin et al., 2004; Bengio et al., 2006; Baluja et al., 2008; Talukdar & Crammer, 2009; Weston et al., 2012) . Algorithms such as the seminal Label Propagation (Zhu et al., 2003) 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 (Weston et al., 2012; Perozzi et al., 2014; Yang et al., 2016; Kipf & Welling, 2016; Grover & Leskovec, 2016; Hamilton et al., 2017; Monti et al., 2017) . 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 (Zhu et al., 2003; Kapoor et al., 2006; Wang & Zhang, 2008; Belkin et al., 2004; Karasuyama & Mamitsuka, 2013) . While some methods consider some form of weight learning (Velickovic et al., 2017; Monti et al., 2018) , 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 (Zhang & Lee, 2007; Karasuyama & Mamitsuka, 2013) , or altogether consider weights disjointly from predictions (Wang & Zhang, 2008; Liu et al., 2010) .

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.

1.1. RELATED WORK:

Many SSL methods are based on Eq. (1) or on similar quadratic forms. These differ in their assumed input, the optimization objective, and the parametric form of predictions.

Classic methods such as LP (Zhu et al., 2003) assume no parametric form for predictions, and require edge weights as inputs. When node features are available, weights are often set heuristically based on some similarity measure (e.g., w ij = exp x i -x j 2 2 /σ 2 ). LP constrains predictions on S to agree with their true labels. Other propagation methods relax this assumption (Belkin et al., 2004; Bengio et al., 2006) , add regularization terms (Baluja et al., 2008) , or use other Laplacian forms (Zhou et al., 2004) . Some methods aim to learn edge weights, but do not directly optimize for accuracy. Instead, they either model the relations between the graph and features (Wang & Zhang, 2008; Liu et al., 2010) or simply require f as input (Daitch et al., 2009; Kalofolias, 2016; Dong et al., 2016) . Methods that focus on accuracy are often constrained to specific parameterizations or assumptions (Karasuyama & Mamitsuka, 2013) . Zhang & Lee (2007) optimize the leave-one-out loss (as we do), but require a series of costly matrix inversions.

Several recent works in deep learning have been focused on graph inputs in general (Battaglia et al., 2018) and specifically for inductive SSL. The main idea behind these methods is to utilize a weighted graph to create meaningful vector representations of nodes, which are then fed into a classifier. Methods are typically designed for one of two settings: when the input includes only a graph, and when node features are available.

When the input includes only a graph (and no features), node representations are generated using embedding techniques. Perozzi et al. (2014) use a SkipGram model over random walks on the graph, which are used to define context. Grover & Leskovec (2016) further this idea by introducing expressive parameterized random walks, while Tang et al. (2015) focus on optimizing similarities between pairs of node embeddings.

Various methods have been proposed to utilize node features, when available. Spectral methods, stemming from a CNN formulation for graphs (Bruna et al., 2014) , include different approximations of spectral graph convolutions (Defferrard et al., 2016; Kipf & Welling, 2016) adaptive convolution filters (Monti et al., 2017) , or attention mechanisms (Velickovic et al., 2017) Embedding approaches have been suggesting for handling bag-of-words representations (Yang et al., 2016) and general node attributes such as text or continuous features (Duran & Niepert, 2017) . Many of the above methods can be thought of as propagating features over the graph in various forms. Our method, in contrast, propagates labels. The main advantage label propagation is that labeled information is used not only to penalize predictions (in the loss), but also to generate predictions.

1.2. PRELIMINARIES:

We begin by describing the learning setup and introducing notation. The input includes a (possibly directed) graph G = (V, E), for which a subset of nodes S ⊂ V are labeled by y S = {y i } i∈S with y i ∈ {1, . . . , C}. We refer to S as the "seed" set, and denote the unlabeled nodes by U = V \ S, and the set of i's (incoming) neighbors by N i = {j : (j, i) ∈ E}. We use n = |V |, m = |E|, = |S|, and u = |U | so that n = + u. In a typical task, we expect to be much smaller than n.

We focus on the transductive setting where the goal is to predict the labels of all i ∈ U . Most methods (as well as ours) output "soft" labels f i ∈ ∆ C , where ∆ C is the C-dimensional probability simplex. For convenience we treat "hard" labels y i as one-hot vectors in ∆ C . All predictions are encoded as a matrix f with entries

f ic = P[y i = c].

For any matrix M , we will use M A to denote the sub-matrix with rows corresponding to A. Under this notation, given G, S, y S , and possibly x, our goal is to predict soft labels f U that match y U .

In some cases, the input may also include features for all nodes x = {x i } i∈V . Importantly, however, we do not assume the input includes edge weights w = {w e } e∈E , nor do we construct these from x. We denote by W the weighted adjacency matrix of w, and use W and w for the respective (row)-normalized weights.

2. UNROLLING LABEL PROPAGATION:

Many semi-supervised methods are based on the notion that predictions should be smooth across edges. A popular way to encourage such smoothness is to optimize a (weighted) quadratic objective. Intuitively, the objective encourages the predictions of all adjacent nodes to be similar. There are many variations on this idea; here we adopt the formulation of (Zhu et al., 2003) where predictions are set to minimize a quadratic term subject to an agreement constraint on the labeled nodes:

f * (w; S) = argmin f :f S =y S (i,j)∈E w ij f i -f j 2 2 (2)

In typical applications, w is assumed to be given as input. In contrast, our goal here is to learn them in a discriminative manner. A naïve approach would be to directly minimize the empirical loss. For a loss function L, regularization term R, and regularization constant λ, the objective would be:

EQUATION

While appealing, this approach introduces two main difficulties. First, f * is in itself the solution to an optimization problem (Eq. ( 2)), and so optimizing Eq. ( 3) is not straightforward. Second, the constraints in Eq. (2) ensure that f * i = y i for every i ∈ S, making the loss term in Eq. ( 3) redundant. While some methods solve this by replacing these with weak constraints, a third issue is that it is still not clear why optimizing edge weights for y S should generalize well to the unlabeled nodes.

In what follows, we describe how to overcome these issues. We begin by showing that a simple algorithm for approximating f * can be cast as a deep neural network. Under this view, the weights (as well as the algorithm itself) can be parametrized and optimized using gradient descent. We then propose a loss function suited to SSL, and show how the above network can be trained efficiently with it.

2.1. LABEL PROPAGATION:

Recall that we would like to learn f * (w; S). When w is symmetric, the objective in Eq. ( 2) is convex and has a closed form solution. This solution, however, requires the inversion of a large matrix, which can be costly, does not preserve sparsity, and is non-trivial to optimize. The LP algorithm (Zhu et al., 2003) circumvents this issue by approximating f * using simple iterative averaging updates. Let f (t) be the set of soft labels at iteration t and wij = w ij / k w ik , then for the following recursive relation:

f (t+1) i = j∈Ni wij f (t) j ∀i ∈ U (4)

it holds that lim t→∞ f (t) = f * for any initial f (0) (Zhu et al., 2003) . In practice, the iterative algorithm is run up to some iteration T , and predictions are given using f (T ) . This dynamic process can be thought of as labels propagating over the graph from labeled to unlabeled nodes over time.

Motivated by the above, the idea behind our method is to directly learn weights for f (T ) , rather than for f * . In other words, instead of optimizing the quadratic solution, our goal is to learn weights under which LP preforms well. This is achieved by first designing a neural architecture whose layers correspond to an "unrolling" of the iterative updates in Eq. ( 4), which we describe next.

2.2. ARCHITECTURE:

The main building block of our model is the basic label-propagation layer, which takes in two main inputs: a set of (predicted) soft labels h = {h i } n i=1 for all nodes, and the set of true labels y A for some A ⊆ S. For clarity we use A = S throughout this section. As output, the layer produces a new set of soft labels h = {h i } n i=1 for all nodes. Note that both h i and h i are in ∆ C . The layer's functional form borrows from the LP update rule in Eq. ( 4) where unlabeled nodes are assigned the weighted-average values of their neighbors, and labeled nodes are fixed to their true labels. For a given w, the output is:

EQUATION

)

where W is the row-normalized matrix of w. A basic network is obtained by composing T identical layers:

H(w; S) = h (T ) • h (T -1) • • • • • h (0) (6)

where the model's parameters w are shared across layers, and the depth T is the model's only hyper-parameter. The input layer h (0) is initialized to y i for each i ∈ S and to some prior ρ i (e.g., uniform) for each i ∈ U . Since each layer h (t) acts as a single iterative update, a forward pass unrolls the full algorithm, and hence H can be thought of as a parametrized and differentiable form of the LP algorithm.

In practice, rather than directly parameterizing H by w, it may be useful to use more sophisticated forms of parameterization. We will denote such general networks by H(θ), where θ are learned parameters. As a first step, given edge features {φ e } e∈E , we can further parametrize w using linear scores s ij and normalizing with softmax:

EQUATION

where θ φ ∈ R d are learned parameters. We propose using three types of features (detailed in Appendix B): Node-feature similarities: when available, node features can be used to define edge features by incorporating various similarity measures such as cosine similarity (φ ij = x i x j / x i x j ) and Gaussian similarity

h (t) S = y S h (t) U N i j i k i k h (t+1) i h (t+1) k α(θ)

(φ ij = exp{-x i -x j 2 2 /σ 2 })

, where each similarity measure induces a distinct feature. Graph measures: these include graph properties such as node attributes (e.g., source-node degree), edge centrality measures (e.g., edge betweenness), path-ensemble features (e.g., Katz distance), and graph-partitions (e.g., k-cores). These allow generalization across nodes based on local and global edge properties.

Seed relations: relations between the edge (i, j) and nodes in S, such the minimal (unweighted) distance to i from some s ∈ S. Since closer nodes are more likely to be labeled correctly, these features are used to quantify the reliability of nodes as sources of information, and can be class-specific.

3. GENERALIZING LABEL PROPAGATION:

The label propagation layers in H pass distributions rather than node feature representations. It is important to take this into account when adding non-linearities. We therefore introduce two novel components that are explicitly designed to handle distributions, and can be used to generalize the basic layer in Eq. ( 5) The general layer (illustrated in Figure 1 ) replaces weights and inputs with functions of the previous layer's output:

EQUATION

where Ã(•) is a normalized weight matrix (replacing W ), µ(•) is a soft-label matrix (replacing h (t) ), and θ α and θ τ are corresponding learned parameters. The edge-weight function Ã offers an information-gated attention mechanism that dynamically allocates weights according to the "states" of a node and its neighbors. The labeling function µ is a time-dependent bifurcation mechanism which controls the rate of label convergence. We next describe our choice of Ã and µ in detail.

3.1. INFORMATION-GATED ATTENTION:

The LP update (Eq. ( 4)) uses fixed weights w. The importance of a neighbor j is hence predetermined, and is the same regardless of, for instance, whether h j is close to some y, or close to uniform. Here we propose to relax this constraint and allow weights to change over time. Thinking of h (t) i as the state of i at time t, we replace w ij with dynamic weights a (t) ij that depend on the states of i and j through an attention mechanism α:

a (t+1) ij ∝ α ij (h (t) i , h (t) j ; θ α ) (9)

where θ α are the attention parameters. Ã in Eq. ( 8) is the corresponding row-normalized weight matrix.

★ ★ ★ ★ ★ h (t+1) i = Ã(h (t) ) ⋅ h (t) i d j e j d k e k d l e l h (t) j h (t) k h (t) l neighbor nodes j, k, l ∈ N i node i h (t) i h (t+1) i a (t) ji a (t) ki a (t) li θ ent θ div α(θ)

(1,0,0) (0,0,1) When designing α, one should take into account the nature of its inputs. Since both h i and h j are label distributions, we have found it useful to let α depend on information theoretic measures and relations. We use negative entropy e to quantify the certainty of a label, and negative KL-divergence d to measure cross-label similarity. Both are parameterized by respective class-dependent weights θ e c and θ d c , which are learned:

EQUATION

where:

EQUATION

In a typical setting, unlabeled nodes start out with uniform labels, making the overall entropy high. As distributions pass through the layers, labeled information propagates, and both entropy and divergence change.

The attention of node i is then directed according to the informativeness (entropy) and similarity (divergence) of the states of its neighbors. As we show in the experiments (Sec. 5), this is especially useful when the data does not include node features (from which weights are typically derived). Figure 2 (left) exemplifies this.

3.2. BIFURCATION FOR CONTROLLING LABEL CONVERGENCE:

Although the updates in Eq. ( 4) converge for any w, this can be slow. Even with many updates, predictions are often close to uniform and thus sensitive to noise (Rosenfeld & Globerson, 2018) . One effective solution is to dynamically bootstrap confident predictions as hard labels (Kveton et al., 2010; Eliav & Cohen, 2018) . This process speeds up the rate of convergence by decreasing the entropy of low-entropy labels.

Here we generalize this idea, and propose a flexible bifurcation mechanism. This mechanism allows for dynamically increasing or decreasing the entropy of labels. For node i and some τ ∈ R, h ic is replaced with:

bif c (h i ; τ ) (h ic ) τ C c =1 (h ic ) τ = µ c (h i ; τ ) (12)

Note that since h i ∈ ∆ C , this definition ensures that, for any τ , we have that µ(h i ) ∈ ∆ C as well.

When τ > 1 and as τ increases, entropy decreases, and confident labels are amplified. In contrast, when 0 < τ < 1 and as approaches 0, entropy decreases, and labels become uniform. For τ < 0 the effects are reversed, and setting τ = 1 gives µ(h i ) = h i , showing that Eq. ( 8) generalizes Eq. ( 5). Hence, τ acts as a bifurcation parameter that changes the point of convergence when µ is repetitively applied. In practice, it is useful to parameterize τ as a function of time. For learned parameters θ τ = [a, b], we use:

τ (t; θ τ ) = a• t + b + 1 (13)

Thus, when θ τ = 0, Eq. ( 13) allows for time-dependent variation in the bifurcation effects of Eq. ( 12). Figure 2 (right) illustrates how bif(•) operates on points in ∆ for different values of τ .

4. LEARNING:

Recall that our goal is to learn the parameters θ of the network H(θ; S). Note that by Eq. ( 5), for all i ∈ S it holds that H i (θ; S) = y i . In other words, as in LP, predictions for all labeled nodes are constrained to their true value. Due to this, the standard empirical loss becomes degenerate, as it penalizes H i (θ; S) only according to y i , and the loss becomes zero for all i ∈ S and for any choice of θ.

As an alternative, we propose to follow Zhang & Lee (2007) and minimize the leave-one-out loss:

EQUATION

where S -i = S \ {i}, L is a loss function, R is a regularization term with coefficient λ, and θ contains all model parameters (such as θ φ , θ α , and θ τ ). Here, each true label y i is compared to the model's prediction given all labeled points except i. Thus, the model is encouraged to propagate the labels of all nodes but one in a way which is consistent with the held-out node. In practice we have found it useful to weight examples in the loss by the inverse class ratio (estimated on S).

The leave-one-out loss is a well-studied un-biased estimator of the expected loss with strong generalization guarantees (Kearns & Ron, 1999; Bousquet & Elisseeff, 2002; Kale et al., 2011) . In general settings, training the model on all sets {S -i } i∈S introduces a significant computational overhead. However, in SSL, when is sufficiently small, this becomes feasible (Zhang & Lee, 2007) . For larger values of , a possible solution is to instead minimize the leave-k-out loss, using any number of sets with k randomly removed examples.

When λ is small, θ is unconstrained, and the model can easily overfit. Intuitively, this can happen when only a small subset of edges is sufficient for correctly propagating labels within S. This should result in noisy labels for all nodes in U . In the other extreme, when λ is large, w approaches 0, and by Eq. ( 15) w is uniform.

5. EXPERIMENTS:

The current graph-SSL literature includes two distinct evaluation settings: one where the input includes a graph and node features, and one where a graph is available but features are not. We evaluate our method in both settings, which we refer to as the "features setting" and "no-features setting", respectively. We use benchmark datasets that include real networked data (citation networks, social networks, product networks, etc.). Our evaluation scheme follows the standard SSL setup1 (Zhu et al., 2003; Zhou et al., 2004; Chapelle et al., 2006; Zhang & Lee, 2007; Perozzi et al., 2014; Grover & Leskovec, 2016; Tang et al., 2015; Monti et al., 2017) . First, we sample k labeled nodes uniformly at random, and ensure at least one per class. Each method then uses the input (graph, labeled set, and features when available) to generate soft labels for all remaining nodes. Hard labels are set using argmax. We repeat this for 10 random splits using k = 1% labeled nodes. For further details please see Appendices A and C.

For each experimental setting we use different Label Propagation Network (LPN) variant that differ in how edge weights are determined. Both variants use bifurcation with linear time-dependency (Sec. 3.2), and include a-symmetric bi-directional edge weights. In all tasks, LPN was initialized to simulate vanilla LP with uniform weights by setting θ = 0. Hence, we expect the learned model deviate from LP (by utilizing edge features, attention, or bifurcation) only if this results in more accurate predictions. We choose T ∈ {10, 20, . . . , 100} by running cross-validation on LP rather than LPN. This process does not require learning and so is extremely fast, and due to bifurcation, quite robust (see Figure 4 ). For training we use a class-balanced cross-entropy loss with 2 regularization, and set λ by 5-fold cross-validation. We optimize with Adam (Kingma & Ba, 2014) using a learning rate of 0.01.

Features setting::

We use all relevant datasets from the LINQS collection (Sen et al., 2008) . These include three citation graphs, where nodes are papers, edges link citing papers, and features are bag-of-words. As described in Sec. 2.2, for this setting we use a model (LPN φ ) where w is parameterized using a linear function of roughly 30 edge features (φ). These are based on the given "raw" node features, the graph, and the labeled set. See Appendix B for more details. Baselines include LP (Zhu et al., 2003) with uniform (LP U ) and RBF (LP RBF ) weights, the LP variant ADSORPTION (Baluja et al., 2008) , ICA (Lu & Getoor, 2003) , Graph Convolutional Networks (GCN, Kipf & Welling (2016)), and Graph Attention Networks (GAT, Velickovic et al. (2017) ). 2 We also add a features-only baseline (RIDGEREG) and a graph-only baseline (NODE2VEC).

No-features setting: We use the FLIP collection (Saha et al., 2014) , which includes several types of real networks. As no features are available, for generating meaningful weights we equip our model (LPN α ) with the attention mechanism (Sec. 3.1), letting weights vary according to node states. Baselines include LP with uniform weights (LP U ), the spectral embedding LEM (Belkin & Niyogi, 2003) , and the deep embedding DEEPWALK (Perozzi et al., 2014) , LINE (Tang et al., 2015) , and NODE2VEC (Grover & Leskovec, 2016) .

Results: Table 3 includes accuracies for both features and no-features settings, each averaged over 10 random splits. As can be seen, LPN outperforms other baselines on most datasetes, and consistently ranks high. Since LPN generalizes LP, the comparison to LP U and LP RBF quantifies the gain achieved by learning weights (as opposed to setting them heuristically). When weights are parameterized using features, accuracy improves by 13.4% on average. When attention is used, accuracy improves by a similar 13.7%.

While some deep methods perform well on some datasets, they fail on others, and their overall performance is volatile. This is true for both learning settings. A possible explanation is that, due to their large number of parameters and hyper-parameters, they require more labeled data. Deep methods tend to perform well when more labeled nodes are available, and when tuning is done on a large validation set, or even on an entire dataset (see, e. Analysis: Figure 3 gives some insight as to why LPN learns good weights. It is well known that the Laplacian's eigenvalues (and specifically λ 2 , the second smallest one) play an important role in the generalization of spectral methods (Belkin et al., 2004) . The figure shows how λ 2 and accuracy change over the training process. As can be seen, learning leads to weights with increasing λ 2 , followed by an increase in accuracy.

Figure 4 demonstrates the effect of bifurcation for different depths T . As can be seen, a model with bifurcation (LPN bif ) clearly outperforms the same model without it (LPN nobif ). While adding depth generally improves LPN bif , it is quite robust across T . This is mediated by larger values of τ that increase label convergence rate for smaller T . Interestingly, LPN nobif degrades with large T , and even τ slightly above 1 makes a difference.

6. CONCLUSIONS:

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.

Appendices:

A DATASETS Dataset statistics are summarized in Table 1 . As described in Sec. 5, there are two collections of data, LINQS3 (Sen et al., 2008) and FLIP4 (Saha et al., 2014) for two distinct settings: semi-supervised learning with and without features, respectively. For each dataset we use the largest connected component. 

B EDGE FEATURES FOR PARAMETERIZING WEIGHTS:

Although possible, parameterizing H directly by w will likely lead to overfitting. Instead, we set edge weights to be a function of edge features φ ij ∈ R d and parameters θ φ ∈ R d , and normalize using softmax over scores:

EQUATION

Our main guideline in choosing features is to keep in line with the typical SSL settings where there are only few labeled nodes. To this end, we use only a handful of features, thus keeping the number of model parameters to a minimum.

We propose three types of features suited for different settings. Most works consider only "raw" node features (e.g., bag-of-words for papers in a citation network). The model, however, requires edge features for parameterizing edge weights. Edge features are therefore implicitly constructed from node features, typically by considering node-pair similarities in features space. This has three limitations. First, node feature spaces tend to be large and can thus lead to over-parameterization and eventually overfitting. Second, edge features are inherently local, as they are based only on the features of corresponding nodes, and global graph-dependent properties of edges are not taken into account. Third, parameterization is completely independent of the labeled set, meaning that edges are treated similarly regardless of whether they are in an informative region of the graph (e.g., close to labeled nodes) or not (e.g., far from any labeled node).

In accordance, we propose three types of features that overcome these issues by leveraging raw features, the graph, and the labeled "seed" set.

:

This differs from the setup inYang et al. (2016),Kipf & Welling (2016), and others, and so results may also differ.

GCN requires a validation set for early stopping, for which we used an 80:20 split.

http://linqs.umiacs.umd.edu/projects/projects/lbc/

http://cs.gmu.edu/~tsaha/Homepage/Projects.html

https://www.nvidia.com/en-us/data-center/dgx-1/

Figures and Tables:

Figure 1: The label-propagation layer with attention (Sec. 3.1) and bifurcation (Sec. 3.2)

Figure 2: (Left) A real example of an information-gated attention update. Green bars depict soft labels h (C = 4), stars mark true labels. Red and blue bars (right) show values of θ. Arrow width indicates attentive weight. determined by e and d (boxed bars), which are computed using h (t) and θ. Here θ directs attention at the informative and similar neighbor (thick arrow), and the update amplifies the value of the correct label. (Right) The bifurcation mechanism for C = 3 and various τ . Arrows map each h ∈ ∆ C to bif(h) ∈ ∆ C .

g.,Yang et al. (2016);Kipf & Welling (2016);Monti et al. (2017);Velickovic et al. (2017)). In contrast, LPN requires relatively few parameters (θ) and only a singe model-specific hyper-parameter (T ).

Figure 3: As learning progresses, the Laplacian's 2 nd smallest eigenvalue increases, and accuracy follows.

Figure4: The added gain of controlling label convergence rates with a bifurcation mechanism.

Accuracy of different methods for the features setting (left) and no-features setting (right).

Table content: <table><tr><td>Method</td><td colspan="3">CiteSeer CoRA PubMed</td><td/><td/><td/><td/><td/></tr><tr><td>LPN φ</td><td>56.2</td><td>66.6</td><td>75.0</td><td>Method</td><td colspan="5">CoRA DBLP Flickr IMDb Industry</td></tr><tr><td>LP U LP RBF ADSORP ICA GCN GAT NODE2VEC</td><td>50.0 50.0 51.1 46.4 52.0 47.7 46.4</td><td>43.4 41.3 58.8 46.1 61.3 55.3 53.1</td><td>65.2 65.4 70.5 37.8 41.9 41.0 74.4</td><td colspan="2">LPNα LP U LEM DEEPWALK 48.3 67.0 44.0 46.0 LINE 30.9 NODE2VEC 53.3</td><td>73.6 57.5 56.9 65.6 44.6 67.0</td><td>68.2 45.2 63.8 80.0 80.0 81.4</td><td>52.9 51.3 59.0 52.0 51.4 55.5</td><td>25.5 20.5 21.6 21.7 19.8 21.7</td></tr><tr><td>RIDGEREG</td><td>23.7</td><td>26.9</td><td>39.5</td><td/><td/><td/><td/><td/></tr></table>

Details of datasets used in the experiment.

Table content: <table><tr><td colspan="3">Collection Dataset Nodes</td><td>Edges</td><td colspan="2">Classes Features</td></tr><tr><td/><td colspan="2">Citeseer 2,708</td><td>5,278</td><td>7</td><td>1,433</td></tr><tr><td>LINQS</td><td>CoRA</td><td>3,132</td><td>4,713</td><td>6</td><td>3,703</td></tr><tr><td/><td colspan="3">Pubmed 19,717 44,324</td><td>3</td><td>500</td></tr><tr><td/><td>CoRA</td><td>2,708</td><td>5,278</td><td>7</td><td>-</td></tr><tr><td/><td>DBLP</td><td>5,329</td><td>21,880</td><td>6</td><td>-</td></tr><tr><td>FLIP</td><td>Flickr</td><td colspan="2">7,971 478,980</td><td>7</td><td>-</td></tr><tr><td/><td>IMDb</td><td>2,411</td><td>12,255</td><td>22</td><td>-</td></tr><tr><td/><td colspan="2">Industry 2,189</td><td>11,666</td><td>12</td><td>-</td></tr></table>

Peer review (iclr2019):
 **** After Revision *********** I thank the authors for diligently revising the paper according to the reviewers* suggestions. I have increased my score for the paper. I still think the experimental evaluation can be more thorough. For example, it would be good to show the effect of varying the .tau parameter and the number of available labels (k). It would also be good to experiment with the Flickr graph without any sparsification and to add uncertainty estimates to the results in Table 1. **** After Revision *********** This paper proposes a framework for non-linear label propagation where the weights are learned simultaneously. There are model specific and experimental setup design decisions that require justification. There also needs to be a number of ablation studies to justify the effectiveness of the different components of this framework. Finally, there seems to be an insufficient comparison (both experimentally and theoretically) to the large amount of related literature. - What is the total number of parameters in the proposed network? Please clarify how this is "relatively few parameters" as compared to other methods. - Please compare how your method for learning weights relates to the following papers and the references therein [1,2] [1] Online Learning of Multiple Tasks and Their Relationships. Saha et al, AISTATS, 2011. [2] Convex Learning of Multiple Tasks and their Structure, Cilberto et al, 2015. - It would be good to have an ablation study in order to discern what is the contribution of learning the weights vs propagating labels (instead of embeddings). - For clarity, please specify that .theta are the parameters to be learned. - Please explain the intuition of using entropy and KL divergence for the attention weights. Shouldn*t the attention for an edge be inversely proportional to the entropy i.e. the attention should be higher if the neighboring node*s label is more certain? - Instead of the bifurcation mechanism proposed in section 3.2, isn*t it possible to use a threshold to round the resulting prediction to a hard label? - In equation 13, are the hyper-parameters a, b tuned using cross-validation? Can*t we learn the .tau in the same training procedure? Please justify this design decision? - What is the performance if the loss in equation 14 is replaced by the standard empirical loss? There needs to be an ablation study on this. - If the node features are available, how are they used in this framework? - In the experimental section, why is k chosen to be equal to 1%? Please show results while varying this. - Please justify the line "parameterizes w using a small number (~20) of informative features based on the raw features (e.g., dimensionality reduction), the graph (e.g., edge betweenness), and the labeled set (e.g., distance from labeled nodes). " Isn*t it possible to get similar performance by reducing the number of parameters so that model doesn*t overfit? - Please clearly state what is the difference in the framework from the Kipf and Welling, 2016 paper? - Why isn*t there a comparison to methods like Graph-Sage? - Please explain this line "LPNnobif degrades with large T, and even .tau slightly above 1 makes a difference" - Finally, please explain the trend in the results in Table 1. For example, why is the performance of the proposed method poor on the Flickr dataset, but better on the DBLP dataset? - It would good to have uncertainty estimates for the results reported in Table 1.