Contrastive Graph Poisson Networks: Semi-Supervised Learning with Extremely Limited Labels
Year: 2021

Abstract:
Graph Neural Networks (GNNs) have achieved remarkable performance in the task of semi-supervised node classification. However, most existing GNN models require sufficient labeled data for effective network training. Their performance can be seriously degraded when labels are extremely limited. To address this issue, we propose a new framework termed Contrastive Graph Poisson Networks (CGPN) for node classification under extremely limited labeled data. Specifically, our CGPN derives from variational inference; integrates a newly designed Graph Poisson Network (GPN) to effectively propagate the limited labels to the entire graph and a normal GNN, such as Graph Attention Network, that flexibly guides the propagation of GPN; applies a contrastive objective to further exploit the supervision information from the learning process of GPN and GNN models. Essentially, our CGPN can enhance the learning performance of GNNs under extremely limited labels by contrastively propagating the limited labels to the entire graph. We conducted extensive experiments on different types of datasets to demonstrate the superiority of CGPN.

heading: 1 Introduction
text: Graph-based Semi-Supervised Learning (SSL) refers to classifying unlabeled data based on a handful of labeled data and a given graph structure indicating the connections between all data. Recently, graph-based SSL has attracted increasing attention due to its solid mathematical foundation, and satisfactory performance [1, 2, 3].
As the mainstream to solve graph-based SSL problems, Graph Neural Networks (GNNs), which operate in the graph domain, have achieved impressive performance in recent years [4, 5, 6, 7]. Nevertheless, current GNNs, such as Graph Convolutional Networks (GCNs) [8] and graph attention networks (GATs) [9], require sufficient labeled data to obtain satisfactory generalization abilities. Unfortunately, the reliance on sufficient labeled data increases the burden of data collection, and the number of labels can be extremely limited in some real-world scenarios. The performance of most
∗This work was done when Sheng was a research intern at JD Explore Academy. †C. Gong is the corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
current GNNs seriously declines as the label size shrinks, since the scarce supervision signals are insufficient to train a model with satisfactory discriminative ability, see Figure 1. To the best of our knowledge, few studies have focused on semi-supervised classification with GNNs at extremely low label rates [10].
In line with the aforementioned observations, this paper proposes a new framework termed Contrastive Graph Poisson Networks (CGPN) to address the problem of semi-supervised node classification under extremely low label rates. Deriving from the variational inference [12, 13], our proposed CGPN framework approximates the intractable posterior with a surrogate distribution, where two types of GNNs have been adopted for instantiation.
Accordingly, we first design a new Graph Poisson Network (GPN) to propagate the limited labels to the entire graph effectively. Specifically, our GPN is motivated by Poisson learning [14]; flexibly models the Poisson label propagation based on attention mechanism; and leverages the structural
information to better guide the propagation of labels. Meanwhile, we exploit another GNN, such as GAT, together with the proposed GPN to model the approximated posterior according to variational inference.
On this basis, we acquire predictions from two comparable views, where a contrastive objective can be naturally incorporated to jointly refine the learning process of the GPN and GNN models. Moreover, the supervision signals implicitly contained in the massive unlabeled data can be exploited with the formulated contrastive loss. As a result, the model learning ability of our proposed framework can be lifted. Experimental results on benchmark datasets confirm the strong benefits of our proposed CGPN when dealing with semi-supervised node classification at very low label rates.
In summary, the contributions of this paper lie in three folds:
First, we propose a novel GNN framework termed CGPN to solve the semi-supervised node classification with extremely limited labels. CGPN significantly outperforms the existing GNNs.
Second, we design a new Graph Poisson Network (GPN). Different from the Poisson learning algorithm, our GPN incorporates graph-structure information and could be trained in an end-to-end manner to guide the propagation of labels more flexibly.
Third, we integrate contrastive learning into the variational inference framework, so that extra supervision information can be explored from the massive unlabeled data to help train our CGPN framework.

heading: 2 Problem description
text: We start by formally introducing the problem of graph-based SSL. Given a set of n = l+ u examples Ψ = {x1, · · · ,xl,xl+1, · · · ,xn}, where the first l examples are provided with the labels {yi}li=1 and the remaining u examples constitute the unlabeled set with typically l≪ u. Let X ∈ Rn×d denote the feature matrix with the i-th row formed by the feature vector xi, and Y ∈ Rn×c denote the label matrix with its (i, j)-th element Yij = 1 if xi belongs to the j-th class and 0 otherwise. Here d is the feature dimension and c is the number of classes. The dataset Φ is represented by an undirected graph G = ⟨V, E⟩, where V represents the node set containing all examples and E is the edge set modeling the similarity among the nodes/examples. The adjacency matrix of G is denoted as A, where Aij = 1 if there exists an edge between xi and xj and Aij = 0, otherwise. In this paper, we target transductive graph-based SSL which aims to find the labels yl+1, yl+2, · · · , yn of the unlabeled examples xl+1,xl+2, · · · ,xn based on Ψ.

heading: 3 Related work

heading: 3.1 Graph-based semi-supervised learning
text: SSL methods focus on training models with small amounts of labeled data as well as relatively large amounts of unlabeled data for [15, 16, 17, 18, 19]. Graph-based SSL algorithms have been one of the most popular research topics during the past decades. The early graph-based techniques are designed based on the simple assumption that nearby nodes are likely to have the same label. This goal can be achieved through the low-dimensional embeddings with Laplacian eigenmaps [20, 21], Markov random walks [22], etc. Meanwhile, graph partition [23] offers another important line in graph-based SSL. To further enhance the learning capacities, various techniques have been proposed to model the data features and graph structure jointly, such as Planetoid [24], where the supervised classifier is regularized with a Laplacian regularizer or an embedding-based regularizer. Recently, a set of graph-based SSL approaches have been proposed to improve the performance of the above-mentioned techniques, including [25, 14, 26].

heading: 3.2 Graph neural networks
text: In the past few years, increasing attention has been paid to GNN models [27, 28, 26, 29, 30, 31, 32]. Early-staged works aim to derive diverse types of graph convolution in spectral-domain based on the graph spectral theory [8, 33, 4]. In [33], a general graph convolution framework based on graph Laplacian is first proposed. Afterwards, Defferrard et al. [4] approximate the convolutional filter via using a K-order Chebyshev polynomial, in order to avoid the intense calculations of eigendecomposition of the normalized graph Laplacian. In addition to this, Kipf and Welling [8] further simplify the graph convolution by a localized first-order approximation, which brings about more efficient filtering operations than spectral CNNs. Another line of research efforts focus on directly performing graph convolution in the spatial domain [5, 27, 34, 35]. In spatial GNN models, the convolution operation is defined as a weighted average function over the neighbors of each node, which characterizes the impact exerting to the target node from its neighboring ones. For instance, Hamilton et al. [5] propose a general inductive framework called GraphSAGE, which is able to learn an embedding function generalizing to previously unseen graph nodes. Besides, in [9], the graph attention network (GAT) is devised by utilizing the attention mechanism, which assigns different weights to the neighboring nodes and aggregates feature with discrimination. Although these models exploit the inter-dependencies among labeled and unlabeled nodes, their performances can still degrade dramatically when the number of labels is extremely limited.

heading: 3.3 Poisson learning
text: Poisson learning is motivated by the need to address the degeneracy of Laplacian SSL when label information is very limited. To be concrete, traditional Laplacian learning algorithm [15] aims at solving the following problem:{
Lu(xi) = 0, if l + 1 ≤ i ≤ n, u(xi) = yi, if 1 ≤ i ≤ l, , (1)
where L represents the unnormalized graph Laplacian and u(xi) ∈ Rc is the label vector of xi. Here, the node xi belongs to the j-th class if the j-th component uj(xi) is the largest in u(xi). Although Laplacian learning works very well for SSL tasks with a moderate number of labeled examples, the performance becomes quite poor at very low label rates.
Different from Laplacian learning, where labels are imposed as boundary conditions, in Poisson learning, labels appear as the source term. The solution of a Poisson equation can be computed as
Lu(xi) = l∑
j=1
(yj − ȳ)δij for i = 1, ..., n (2)
satisfying ∑n
i=1 diu(xi) = 0, where δij = 1 if i = j and δij = 0, otherwise, ȳ = 1 lF1 with F ∈ Rc×l denoting the label matrix of the l labeled nodes, and di = ∑n
j=1 Aij . The Poisson equation (2) can be solved efficiently with a simple iteration, and the result of the (t+ 1)-th iteration can be obtained as
U(t+1) ← U(t) +D−1(B⊤ − LU(t)), (3)
where D is the diagonal matrix with Dii = di, L is the Laplacian matrix, and B = [F− ȳ,O] is the source term. Here, O ∈ Rc×(n−l) indicates a zero matrix. After T iterations, the prediction can be acquired as U(T ). The specific interpretation of Poisson learning algorithm can be found in [14].

heading: 4 Methodology
text: This section details our proposed CGPN framework. Specifically, we describe the critical components of CGPN by explaining the variational inference framework, presenting the instantiation with GPN and GNN models, and illustrating the contrastive label inference.

heading: 4.1 Inference framework
text: To infer the labels of the unlabeled nodes, i.e., YU , we need to estimate the posterior distribution given the node features X, the observed labels YL, and the adjacency matrix A, namely pθ(YU |A,X,YL) with parameters θ. Computation of this posterior is usually analytically intractable, so we resort to approximate posterior inference methods. Inspired by the recent advances in scalable variational inference [36, 37], we introduce a distribution qϕ(YU |A,X,YL) parameterized by ϕ to approximate the true posterior pθ(YU |A,X,YL). Afterwards, we can write the Evidence Lower BOund (ELBO) as LELBO(θ, ϕ) = log pθ(YL|A,X)−DKL(qϕ(YU |A,X,YL)||pθ(YU |A,X)), (4) where DKL(·||·) represents the Kullback-Leibler divergence between two distributions. For practical use, it remains to specify the parametric forms of qϕ(YU |A,X,YL) and pθ(Y|A,X) with GNNs.

heading: 4.2 Instantiations
text: In this section, the instantiation of qϕ(Y|A,X,YL) and pθ(Y|A,X) will be illustrated.

heading: 4.2.1 Instantiation of qϕ(Y|A,X,YL) with Graph Poisson Networks
text: To approximate the posterior model qϕ(Y|A,X,YL), we need a strong function with the inputs A, X, and YL and outputs the probability of Y. Due to the extremely scarce label information in YL, most existing methods are ineffective here. Fortunately, the Poisson learning algorithm [14] is recently proposed to address the scenarios with very limited labels. The superiority of Poisson learning over traditional Laplacian learning has been proven both theoretically and experimentally at very low label rates [14]. However, the graph structure has not been fully leveraged to guide the propagation of labels in Poisson learning. Concretely, Poisson learning relies on a fixed graph which can be noisy in reality, and thus the intrinsic relationships among graph nodes cannot be well explored. Meanwhile, the structural information constituted by the neighboring node features has not been exploited, since Poisson learning mainly emphasizes the propagation of the input label information. As a consequence, inaccurate label predictions can be accumulated with iterative propagation, which inevitably results in performance degradation. To handle these difficulties, we propose a more flexible GNN model called ‘Graph Poisson Networks’ (GPN).
Inspired by GAT [9], we intend to adaptively capture the importance of the neighbors exerting to the target node via attention mechanism. In this way, the graph information can be gradually refined via network training, which makes the propagation of labels more reasonable. To be specific, we first compute the attention coefficient eij between nodes xi and xj as
eij = a⃗ ⊤[Wxi;Wxj ], (5)
where a⃗ is a trainable weight vector, W is a trainable weight matrix, and [·; ·] denotes the concatenation operation. The attention coefficient eij is usually normalized across the neighbors of xi with a softmax function to make it comparable across nodes:
αij = exp(eij)∑
k∈Ni exp(eik) , (6)
where Ni denotes the indices of xi’s neighbors. In our GPN, the normalized attention coefficient αij is adopted to represent the edge weights of the input adjacency matrix A and can be further optimized
via network training. In this way, improved edge weights can help guide the propagation of labels in a more reasonable way. At this point, the output of our GPN can be obtained by the following iteration:
Ũ(t) ← Ũ(t−1) + D̃−1 ( B⊤ − L̃Ũ(t−1) ) , (7)
where D̃ and L̃ represent the diagonal matrix and Laplacian matrix of the attention-based graph, respectively, and Ũ(t) is the result of the t-th iteration.
Note that Eq. (7) fails to incorporate the structural information formed by the node features, as the prediction in each iteration mainly relies on the label information. To capture the meaningful structural information, a feature transformation module fFT is adopted to introduce feature information explicitly. Specifically, the feature transformation module fFT predicts labels based on the node features and can be expressed as a single-layer perceptron. Afterwards, by propagating the predictions of fFT iteratively, the feature information within the neighborhood structure can be incorporated correspondingly and further improve the final predictions. Therefore, we modify the output of the (T − 2)-th iteration, namely Ũ(T−2), to
Ũ(T−2) ← Ũ(T−2) + fFT (X), (8) where T denotes the number of iterations. By doing so, the involved feature information can be further propagated and the extracted structural information can help refine the label predictions. In addition, the feature transformation module can also accelerate the convergence of the iterative process shown in Eq. (7). Note that the outcomes of fFT can only be propagated in the last two iterations to avoid performance degradation which is caused by over-smoothing.

heading: 4.2.2 Instantiation of pθ(Y|A,X) with graph neural networks
text: For pθ(Y|A,X) in the ELBO obejective function, we can flexibly instantiate it with a GNN model that takes A and X as the inputs and outputs the probability of Y. Note that most of the existing GNN models are applicable. In this paper, the well-known Graph Convolutional Networks (GCN) [8] and GAT [9] are considered for instantiation. Note that when we employ GAT to instantiate pθ(Y|A,X), the attention coefficients are shared across GPN and GAT, so that the scale of network parameters can be reduced. Additionally, the GAT can help guide the propagation of labels through the shared attention coefficients.

heading: 4.3 Contrastive label inference
text: Furthermore, we intend to leverage the supervision signals beyond the limited labels. In this paper, contrastive learning [38, 39] is utilized to explore extra supervision information from the massive unlabeled data for model training, which can improve the performance of label inference. To be specific, we maximize the agreement between the predictions of the same node that are generated from qϕ(Y|A,X,YL) and pθ(Y|A,X), i.e., zi and z̃i. Meanwhile, we pull the predictions of different node pairs away. As a result, the pairwise contrastive loss between zi and z̃i can be defined as
LPC(zi, z̃i) = −log exp(⟨zi, z̃i⟩ /τ) exp(⟨zi, z̃i⟩ /τ) + n∑
j=1
1[j ̸=i] exp(⟨zi, z̃j⟩ /τ) + n∑
j=1
1[j ̸=i] exp(⟨zi, zj⟩ /τ) ,
(9)
where ⟨·, ·⟩ denotes the inner product and τ is a tunable temperature parameter. Based on Eq. (9), the overall contrastive objective to be minimized is
LCont = 1
2n n∑ i=1 (LPC(zi, z̃i) + LPC(z̃i, zi)). (10)
In addition to the contrastive loss, a standard multiclass softmax cross-entropy loss LCE should also be applied to penalize the difference between the outcomes of qϕ(Y|A,X,YL) and the ground-truth labels, i.e., ZL and YL. Hence, by assigning the weight hyperparameters λ1 and λ2 to LCE and LCont correspondingly, we arrive at the total loss as
L(θ, ϕ) = −LELBO(θ, ϕ) + λ1LCE(ZL,YL) + λ2LCont, (11)
where ZL is generated by the instantiated model qϕ(Y|A,X,YL) denoting the prediction of the labeled examples XL. With the contrastive objective across the GPN and GNN models, the mutual information can be exploited to improve the ability of label inference. The overall framework is referred to as Contrastive Graph Poisson Networks (CGPN), of which the overview is exhibited in Figure 2.

heading: 5 Experiments
text: To reveal the effectiveness of our proposed CGPN framework, extensive experiments have been conducted on the task of semi-supervised node classification. We mainly focus on evaluating the model performance under label-scarce settings.

heading: 5.1 Experimental settings
text: Datasets. The experiments are conducted on four commonly used benchmark datasets, including three widely-used citation networks (i.e., Cora, CiteSeer, and PubMed) [11, 40], and one Amazon product co-purchase networks (i.e., Amazon Photo) [41]. In the citation networks, the nodes represent documents and their links refer to citations between documents, where each node is associated with a bag-of-words feature vector and a ground-truth label. In the product co-purchase networks, the nodes represent goods and the links indicate that two goods are frequently bought together, where node features are bag-of-words encoded product reviews, and class labels correspond to the product categories. The dataset statistics are summarized in Table 1.
Baselines. When we evaluate the performance of different methods in the label-scarce settings, six state-of-the-art models are used for comparison, including GCN [8], GAT [9], Bayesian Graph Convolutional Neural Networks (BGCN) [42], Multi-View Graph Representation Learning (MVGRL) [43], Generalized PageRank Graph Neural Networks (GPRGNN) [44], and Approximate Personalized Propagation of Neural Predictions (APPNP) [45]. BGCN enhances the learning ability of GNNs by modeling the uncertainty of the graph structure. MVGRL explores the supervision information contained in the unlabeled data by contrasting the encodings from two structural views of graphs. GPRGNN jointly optimizes node feature and topological information extraction to obtain excellent learning performance for label patterns. APPNP leverages a large and adjustable neighborhood for convolution by using the relationship between GCN and PageRank. Besides, we also include the Multi-Layer Perceptron (MLP) without using any graph information as a competitor, where the
number of layers is set to two. For the proposed CGPN framework, we implement two model variants where GCN and GAT are used for instantiation, namely CPGN-GCN and CGPN-GAT.
Training details. For all the adopted datasets, we randomly choose one, two, three, and four labeled nodes per class for training, respectively, in order to evaluate the model performance under label-scarce settings. The hyperparameters, such as the number of hidden units and the learning rate, are determined via grid search. In our experiments, the original architecture of GCN is adopted in both the baselines and CGPN-GCN. In CGPN-GAT, the attention coefficients are shared between GPN and GAT, where only the single-head attention mechanism is utilized for simplicity. The experiments are conducted on a Linux server equipped with a Tesla P40 GPU.

heading: 5.2 Node classification results
text: Here, we present the classification results of our proposed CGPN framework (CGPN-GCN and CGPN-GAT) and the baseline methods at different label rates. The experimental results on Cora, CiteSeer, PubMed, and Amazon Photo datasets are shown in Tables 2, 3, 4, and 5, respectively, where the highest record at each label rate is highlighted in bold. We observe that both CGPN-GCN and CGPN-GAT achieve substantial performance gains at different label rates when compared with the baselines. In particular, the margin between our proposed framework and the best baseline method can exceed 4% on Cora and CiteSeer datasets given one labeled node per class, which demonstrates that the CGPN framework could effectively enhance the learning performance of GNNs. Although MVGRL utilizes the contrastive objective for graph representation learning, our proposed CGPN-GCN and CGPN-GAT exhibit better classification results. We hypothesize that the gap between MVGRL and our CGPN in accuracy is mainly due to that the devised GPN transfers as much knowledge as possible from the limited labeled nodes to the massive unlabeled ones. Notably, we could also find that the performance of the two variants, i.e., CGPN-GCN and CGPN-GAT, seems quite similar since CGPN is a flexible framework and is insensitive to the choices of GNN instantiations.

heading: 5.3 Parametric sensitivity
text: There are two important hyperparameters that should be manually tuned in our objective function Eq. (11). The first is λ1 used to regularize the cross-entropy loss of GPN. Another is λ2 assigned to the contrastive objective. By varying λ1 and λ2 from 0.1 to 1.5 with an interval of 0.2, the corresponding parametric sensitivity is shown in Figure 3. We find that the behavior of the proposed CGPN framework is relatively stable with the change of λ1 and λ2. We speculate that GPN and contrastive modules are mutually beneficial and can collaborate to obtain promising results. Generally, the two hyperparameters are not difficult to tune in practical applications.

heading: 5.4 Ablation study
text: Inspired by the Poisson Learning (PL) algorithm, the devised GPN model learns to propagate the limited labels to the entire graph with structural information in an end-to-end way. To shed light on this critical component, we report the classification results obtained by using GPN and PL in Table 6 and 7, where the sizes of labeled nodes per class are kept identical to those in Sec. 5.2. The results
show that our GPN model can effectively boost the performance of Poisson learning at extremely limited label rates. Meanwhile, the margin between GPN and CGPN frameworks cannot be ignored, which reveals the power of the extra supervision information explored from massive unlabeled data.

heading: 6 Conclusion
text: In this paper, we propose a novel CGPN framework for semi-supervised node classification with extremely limited labels. To alleviate the performance degeneracy of the existing GNNs, we devise a new model termed GPN, which can flexibly propagate the limited labels to the entire graph by exploiting the structural information. Meanwhile, a contrastive objective is employed to extract supervision information from massive unlabeled data. As a consequence, the performance of our CGPN can be effectively enhanced by optimizing the overall objective function. Experimental results reveal the superiority of our method when compared with various baseline methods. Note that how to generalize our proposed method to inductive settings will be an interesting focus of study in the future.

heading: 7 Broader impact
text: Our work could have the following positive impacts: (1) This paper provides a new framework for SSL on graph-structured data. (2) Our proposed framework can improve the performance of GNNs, especially when labeled data are extremely limited. (3) The proposed framework is compatible with different types of GNNs (e.g., GAT and GCN).
Similar to many other machine learning algorithms, the proposed framework can be used for good and also be used for harm at the same time. Note that GNNs and our method are not immune to such misuse. Although we have no optimal solution to such a problem, we believe that this can be solved in the future.
To sum up, we believe our proposed work can be beneficial to society since many important real-world applications stand to benefit from CGPN when label information is very limited.

heading: 8 Acknowledgments
text: This research was supported in part by NSF of China (Nos: 61973162 and 62002090), NSF of Jiangsu Province (No: BZ2021013), the Fundamental Research Funds for the Central Universities (Nos: 30920032202, 30921013114), CCF-Tencent Open Fund (No: RAGR20200101), Hong Kong Scholars Program (No: XJ2019036), and Australian Research Council project (Nos: DP-180103424 and FL-170100117).

Review summaries:
This paper focuses on semi-supervised node classification with extremely limited labels and the authors propose a new framework termed Contrastive Graph Poisson Networks (CGPN). Specifically, they design a Graph Poisson Networks to propagate the limited labels to the entire graph and employ a Graph Neural Network (GNN) to guide the propagation. Meanwhile, labeled data and unlabeled data are also considered in the final objective function. For the labeled data, they simply use a cross-entropy loss and for the unlabeled data, they apply a pairwise contrastive loss to explore extra supervision information. 

In this paper, authors propose the Graph Poisson Network (GPN) to  effectively propagate the information of limited labels to the entire graph, which is developed for semi-supervised node classification. The main contributions are as follows.  Firstly,  they integrate contrastive learning and variational inference framework into Poisson learning algorithm. This novel combination can propagate the label information more flexible.  Secondly, as they claimed, they achieve a significant improvement on semi-supervised node classification tasks. 

For node classification tasks with extremely limited labeled data, this paper proposes a new GNN architecture GPN that extends Poisson learning to incorporate graph structure information and its contrastive learning method. The goal is to propagate the limited labels to the entire graph effectively to enhance classification performance. The framework consists of GNN for $p_\theta(Y|A, X)$ and GPN for $q_\phi(Y|A,X,Y_L)$ which are trained with ELBO loss and contrastive loss. GPN, inspired by GAN, is instantiated to learn attention-based edge weights used to construct a new diagonal matrix and graph Laplacian for Poisson learning.