A Collective Learning Framework to Boost GNN Expressiveness
Mengyue Hang Jennifer Neville Bruno Ribeiro
cs.LG stat.ML
























































A Collective Learning Framework to
 Boost GNN Expressiveness
    Mengyue Hang 

Department of Computer Science 

Purdue University 



Jennifer Neville 

Department of Computer Science 

Purdue University 



Bruno Ribeiro 

Department of Computer Science 

Purdue University 



    December 30, 2023
==========================================================================================================================================================================================================================





Graph Neural Networks (GNNs) have recently been used for node and graph classification tasks with great success.
Unfortunately, existing GNNs are not universal (i.e., most-expressive) graph representations.
In this work, we propose collective learning, a general collective classification Monte Carlo approach for graph representation learning that provably increases the representation power of existing GNNs. 
We show that our use of Monte Carlo sampling is key in these results.
Our experiments consider the task of inductive node classification across partially-labeled graphs using five real-world network datasets and demonstrate a consistent, significant boost in node classification accuracy when our framework is combined with a variety of state-of-the-art GNNs.



















§ INTRODUCTION


Graph Neural Networks (GNNs) have recently shown great success at node and graph classification tasks <cit.>. GNNs have been applied in both transductive settings (where the test nodes are embedded in the training graph) and inductive settings (where the training and test graphs are disjoint). 

Despite their success, existing GNNs are no more powerful than the Weisfeiler-Lehman (WL) graph isomorphism test, and thus, inherit its shortcomings, i.e. they are not universal (most-expressive) graph representations <cit.>.
In other words, these GNNs (which we refer to as WL-GNNs and also include GCNs <cit.>) are not expressive enough for some node classification tasks, since their representation can provably fail to distinguish non-isomorphic nodes with different labels.

At the same time, a large body of work in relational learning has focused on strengthening poorly-expressive (i.e., local) classifiers in relational models (e.g., relational logistic regression, naive Bayes, decision trees <cit.>) in collective classification frameworks, by incorporating dependencies among node labels and propagating inferences during classification to improve performance, particularly in semi-supervised settings <cit.>.

In this work, we theoretically and empirically investigate the hypothesis that, by explicitly incorporating label dependencies among neighboring nodes via predicted label sampling—akin to how collective classification improves not-so-expressive classifiers—it is possible to devise an add-on training and inference procedure that can improve the expressiveness of any existing WL-GNN for inductive node classification tasks, which we denote collective learning. 























Contributions. We first show that collective classification is provably unnecessary if one can obtain GNNs that are most-expressive. 
Then, because current WL-GNNs are not most-expressive, we propose an add-on general collective learning framework to GNNs that provably boosts their expressiveness, beyond that of an optimal  WL-GNN[We use the term optimal WL-GNN to refer to the most expressive version of a GNN–one that has the same distinguishing power as a Weisfeiler-Lehman test. Note this is not a universal graph representation.]. Our framework, which we call , involves the use of self-supervised learning and sampled embeddings to incorporate node labels during inductive learning—and it can be implemented with any component GNN. 
In addition to being strictly more expressive than optimal WL-GNNs, we also show how collective learning improves finite d-layer WL-GNNs in practice by extending their power to distinguish non-isomorphic nodes from d-hop neighborhoods to 2d.
We also show that, in contrast to our proposed framework, attempts to incorporate collective classification ideas into WL-GNNs without sampled embeddings (e.g., <cit.>) cannot increase expressivity beyond that of an optimal WL-GNN.  

Our empirical evaluation shows achieves a consistent improvement of node classification accuracy, across a variety of state-of-the-art WL-GNNs, for tasks involving unlabeled and partially-labeled test graphs. 















§ PROBLEM FORMULATION





We consider the problem of inductive node classification across partially-labeled graphs, which takes as input a graph G^(tr) = (V^(tr), E^(tr), ^(tr), ^(tr)_L ) for training, where V^(tr) is a set of n^(tr) vertices, E^(tr)⊂ V^(tr)× V^(tr) is a set of edges with adjacency matrix ^(tr), ^(tr) is a n^(tr)× p matrix containing node attributes as p-dimensional vectors, and ^(tr)_L is a set of observed labels (with C classes) of a connected set of nodes V^(tr)_L ⊂ V^(tr), where V^(tr)_L is assumed to be a proper subset of V^(tr), noting that V^(tr)_L ≠∅.
Let _U^(tr) be the unknown labels of nodes V^(tr)_U = V^(tr)∖ V^(tr)_L.

The goal is to learn a joint model of _U^(tr)∼ P(_U | G^(tr)) and apply this same model to predict hidden labels _U^(te) in another test graph G^(te), i.e., _U^(te) = __U P(_U | G^(te)). The test graph G^(te) can be partially labeled or unlabeled so V^(te)_L ⊇∅.



Graph Neural Networks (GNNs), which aggregate node attribute information to produce node representations, have been successfully used for this task. At the same time, relational machine learning (RML) methods, which use collective inference to boost the performance of local node classifiers via (predicted) label dependencies, have also been successfully applied to this task. 

Since state-of-the-art GNNs are not most-expressive <cit.>, collective classification ideas may help to improve the expressiveness of GNNs. In particular, collective inference methods often sample predicted labels (conditioned on observed labels) to improve the local representation around nodes and approximate the joint distribution P(_U | G^(te)). We also know from recent research that sampling randomized features can boost GNN expressiveness <cit.>.    


This leads to the key conjecture of this work <Ref>, which we prove theoretically in <Ref> and validate empirically by extensive experimentation in <Ref>.



Since current Graph Neural Networks (e.g. GCN, GraphSAGE, TK-GNN) cannot produce most expressive graph representations, collective learning (which takes label dependencies into account via Monte Carlo sampling) can improve the accuracy of node classification by producing a more expressive graph representation. 


Why? Because WL-GNNs can extract more information about local neighborhood dependencies via sampling <cit.>, and sampling predicted labels allows the GNN to pay attention to the relationship between node attributes, the graph topology, and label dependencies in local neighborhoods. 
With collective learning, GNNs will be able to incorporate more information into the estimated joint label distribution. 





Next, we describe our collective learning framework. 





§ PROPOSED FRAMEWORK: COLLECTIVE LEARNING TO BOOST GNNS








In this section, we outline . It is a general framework to incorporate any GNN, and combines self-supervised learning approach and Monte Carlo embedding sampling in an iterative process to improve inductive learning on partially labeled graphs. 
























Specifically, given a partially labeled training graph G^(tr) = (V^(tr), E^(tr), ^(tr), _L^(tr)) with adjacency matrix ^(tr) and a partially-labeled test graph G^(te) = (V^(te), E^(te), ^(te), _L^(te)) with adjacency matrix ^(te). 
The goal of inductive node classification task is to train a joint model on G^(tr) to learn P(_U|G^(tr)) 

and apply it to G^(te) by replacing the input graph G^(tr) with G^(te).


Suppose the graphs G^(tr) and G^(te), we can define ^(tr)_L as a binary (0-1) matrix of dimension |V^(tr)|× C, and _L^(te) of dimension |V^(te)|× C, where the rows corresponding to the one-hot encoding of the (available) labels.

(Background) GNN and representation learning.
Given a partially labeled graphs G^(tr), WL-GNNs generate node representation by propagating feature information throughout the graph. Specifically, ∀ v ∈ V^(tr), 

    P(_v|^(tr), ^(tr)_L, ^(tr))  = σ( W_v +  b),

where _v = GNN(^(tr), ^(tr); Θ)_v is the GNN representation of node v, σ(·) is the softmax activation, and Θ, W and b are model parameters, which are learned by minimizing the cross-entropy loss between true labels ^(tr)_L and the predicted labels.



The collective learning framework. Following <Ref>, we propose Collective Learning GNNs (), which includes label information as input to GNNs to produce a more expressive representation. 
The overall framework follows three steps: (Step 1) Include labels in the input using a random mask; (Step 2) Sample predicted labels for whatever is masked, use as input to WL-GNN that also takes all node labels as input, and average representations of the WL-GNN over the sampled predicted labels; (Step 3) Perform one optimization step by minimizing a negative log-likelihood upper bound (per <Ref>). Collective learning for WL-GNNs then consists of iterating over Steps 1-3 for t=1,…,T iterations. Finally, once optimized, we perform inference via Monte Carlo estimates.








Step 1. Random masking and self supervised learning. 
The input to GNNs is typically the full graph G^(tr). If we included the observed labels ^(tr)_L directly in the input, then it would be trivial to learn a model that predicts part of the input. Instead, we either (scenario test-unlabeled) mask all label inputs if the test graph G^(te) is expected to be unlabeled; or (scenario test-partial) if G^(te) is expected to have partial labels, we apply a mask to the labels we wish to predict in training so they do not appear in the input ^(tr)_L. 

In (scenario test-partial), where G^(te) is expected to have some observed labels, at each stochastic gradient descent step, we randomly sample a binary mask ∼Uniform() from a set of masks, where  is a |V^(tr)|× C binary (0-1) matrix with the same |V^(tr)|-dimensional vector in each column.
By applying the mask on the observed labels _L^(tr), the set of true labels is effectively partitioned into two parts, where part of true labels _L^(tr)⊙ are used as input to , and the other part _L^(tr)⊙ are used as optimization target, where :=  1 - is the bitwise negated matrix of . 

Step 2. loss and its representation averaging.

At the t-th step of our optimization —these steps can be coarser than a gradient step— we either (scenario test-partial) sample a mask ^(t)∼Uniform() or (scenario test-unlabeled) set ^(t) =  0.

For now, we
assume we can sample Ŷ^(t-1)=(_v^(t-1))_v ∈ V^(tr) from an estimate of the distribution P(_v^(tr)|^(tr), _L^(tr)⊙^(t), ^(tr)) —we will come back to this assumption soon. 
Let __L^(tr),^(t-1),^(t)^(tr) be the matrix  concatenation between ^(tr)_L⊙^(t) + ^(t-1)⊙^(t) and ^(tr), where again :=  1 - is the bitwise negated matrix of .
Let

    _v^(t)(^(t);Θ)= _^(t-1)[ GNN(__L^(tr),^(t-1),^(t)^(tr) , ^(tr) ; Θ)_v ],

where GNN represents an arbitrary graph neural network model and Z_v^t is the 's representation obtained for node v ∈ V^(tr) at step t ≥ 1. 



Our optimization is defined over the expectation of _v^(t)(^(t)) w.r.t. to the sampled predicted labels ^(t-1) (<Ref>) and over a loss averaged over all sampled masks (noting that the case where ^(t) =  0 is trivial):

    Θ_t,    W_t, b_t 
       = _Θ, W, b𝔼_^(t)[-∑_v∈ V_L^(tr)^(t)_v logσ( W_v^(t)(^(t);Θ) +  b)_y^(tr)_v],


where again, σ(·) is the softmax activation function, and V_L^(tr) are the labeled nodes in training graph.

Obtaining Ŷ^(t-1).

At iteration t, we use the learned model parameter Θ_t-1 to obtain _v^(t-1) according to <Ref> and use the model parameters W_t-1, b_t-1 to obtain the label prediction recursively

    ^(t-1)_v ∼Categorical(σ( W_t-1^(t-1)_v(^(t)
        ;Θ_t-1) +  b_t-1)),   v ∈ V^(tr),



starting the recursion with ^(t-2) =  0. 



Step 3. Stochastic optimization of <Ref>.

<Ref> is based on a pseudolikelihood, where the joint distribution of the labels {_v^(tr) : v ∈ V_L^(tr) s.t. ^(t)_v = 1} is decomposed as marginal distributions resulting in the sum over V_L^(tr) in <Ref>.

In order to optimize <Ref>, we compute gradient estimates w.r.t. Θ and b using the
following sampling procedure.

1. We first need to compute an unbiased estimate of {^(t-1)_v}_v ∈ V_L^(tr) in <Ref> using K i.i.d. samples ^(t-1) from the model obtained at time step t-1 (as describe above).
Note that the time/space complexity of the is K times the time/space complexity of the corresponding GNN model as we have to compute K representations for each node at each stochastic gradient step. 

2. Next, we need an unbiased estimate of the expectation over ^(t) in <Ref>.
In (scenario test-partial) the unbiased estimates are obtained by sampling ^(t)∼Uniform(), in the (scenario test-unlabeled) the value obtained is exact since ^(t) =  0.
<Ref> shows that the above procedure is a proper surrogate upperbound of the loss function

Inference with learned model.

We apply the same procedure as in obtaining Ŷ^(t-1), but transferring the learned parameters to a different test graph.

Specifically, at iteration t, parameters Θ_t, _t, _t are learned according to <Ref> on the training graph G^(tr). Suppose the iteration contains J gradient steps, thus J sampled masks are used. Given an any-size attributed graph G^(te), we sample another J masks ^(t) of size |V^(te)|, either (scenario test-partial) sampling ^(t)∼Uniform() or (scenario test-unlabeled) set ^(t) =  0. We also sample K predicted labels {Ŷ^(te), (t-1)_1, ⋯, Ŷ^(te), (t-1)_K} from the predicted probability distribution where Ŷ^(te), (t-1)_k=(_v^(t-1))_v ∈ V^(te) 

. The node representations for v ∈ V^(te) are obtained using ^(t) and Ŷ^(te), (t-1)_1,⋯,K:  


    _v^(t) = 1/J K∑_j=1^J ∑_k=1^K GNN(^(te)__L^(te),_k^(te),(t-1),^(t)_j , ^(te) ; Θ_t)_v ,  ∀ v ∈ V^(te),

where again, J is the number of gradient steps per iteration t and K is the number of Monte Carlo samples of Ŷ^(te), (t-1).
Then the label predictions are obtained using the learned parameters _t, _t:

    _v^(t)∼Categorical(σ( W_t_v^(t) +  b_t)_v),  ∀ v ∈ V^(te).


Note that the test label predictions ^(te),(t) are also recursively updated, and the recursion starts with ^(te),(t-2) =  0. 
















































































§ COLLECTIVE LEARNING ANALYSIS
 

Is collective classification able to better represent target label distributions than graph representation learning?

The answer to this question is both yes (for WL-GNNs) and no (for most-expressive representations).
<Ref> shows that a most-expressive graph representation <cit.> would not benefit from a collective learning boost.
All proofs can be found in the .



[Collective classification can be unnecessary]theoremthmCCun

Consider the task of predicting node labels when no labels are available in test data.
Let Γ^⋆(v,G^(te)) be a most-expressive representation of node v ∈ V^(te) in graph G^(te) . 
Then, for any collective learning procedure predicting the class label of v ∈ V^(te), there exists a classifier that takes Γ^⋆(v,G^(te)) as input and predicts the label of v with equal or higher accuracy.




While <Ref> shows that the most-expressive graph representation does not need collective classification, WL-GNNs are not most-expressive <cit.>. Indeed, <Ref> and <Ref> show that  boosts the expressiveness of optimal WL-GNN and practical WL-GNNs, respectivelly.
Then, we show that the stochastic optimization in Step 3 optimizes a loss surrogate upper bound.








 §.§ Expressive power of 

<cit.> and <cit.> show that WL-GNNs are no more powerful in distinguishing non-isomorphic graphs and nodes as the standard Weisfeiler-Lehman graph isomorphism test (1-WL or just WL test). 
Two nodes are assumed isomorphic by the WL test if they have the same color assignment in the stable coloring. 



The node-expressivity of a parameterized graph representation Γ (with parameter Γ(·;)) can then be determined by the set of graphs for which Γ can identify non-isomorphic nodes:

    (Γ) =  {  G :  ∃^⋆_G,  s.t. ∀ u,v ∈ V_G,  Γ(G;^⋆_G)_v = Γ(G;^⋆_G)_u  iff  u ,  v  are isomorphic, G ∈},

where  is the set of all any-size attributed graphs, V_G is the set of nodes in graph G.
 
We call (Γ) the identifiable set of graph representation Γ. 


The most expressive graph representation Γ^⋆ has an identifiable set of all any-size attributed graphs, i.e. (Γ^⋆) =. We refer to the WL-GNN that is equally expressive as WL test as the optimal WL-GNN (or WLGNN^⋆), which is at least as expressive as all other WL-GNNs.

In this section we show that collective learning can boost the optimal WLGNN^⋆, i.e., the identifiable set of WLGNN^⋆ is a proper subset of collective learning over WLGNN^⋆ (denoted ^⋆)


    (WLGNN^⋆) ⊊(^⋆).



















 

































[^⋆ expressive power]theoremthmclpower

Let WLGNN^⋆ be an optimal WL-GNN.
Then, the collective learning representation of <Ref>, using WLGNN^⋆ as the GNN component,  (denoted ^⋆) is strictly more expressive than this WLGNN^⋆ representation model applied to the same tasks.




<Ref> answers <Ref>, by showing that by incorporating collective learning and sampling procedures, can boost the expressiveness of WL-GNNs, including the optimal WLGNN^⋆. 

 
Consider a graph representation learning method that, at iteration t, replaces ^(t-1), in <Ref> with a deterministic function over ^(t-1), e.g., a softmax function that outputs (P(^(t-1)_v| ^(t-1)))_v ∈ V^(tr). 
Then, such method will be no more expressive than the optimal WLGNN^⋆ and, hence, less expressive than ^⋆. 


<Ref> shows that existing graph representation methods that —on the surface— may even look like , but do not perform the crucial step of sampling (_v^(t-1))_v ∈ V^(tr), unfortunately, are no more expressive than  WL-GNNs. Examples of such methods include <cit.>.


Next, we see that the practical benefits of collective learning are even greater when the WL-GNN has limited expressive power due to a constraint on the number of message-passing layers.



 §.§ How further expands the power of few-layer WL-GNNs


A d-layer (d > 1) WL-GNN will only aggregate neighborhood information within d hops of any given node (i.e., over a d-hop egonet, defined as the graph representing the connections among all nodes that are at most d hops away from the center node).
In practice —mostly for computational reasons— WL-GNNs have many fewer layers than the graph's diameter D, i.e., d < D. 


For instance, GCN <cit.>  and GraphSAGE <cit.> both used d = 2 in their experiments.
Hence, they cannot differentiate two non-isomorphic nodes that are isomorphic within their d-hop neighborhood. 
We now show that can gather 2d-hop neighborhood information with a d-layer WL-GNN. 



propositionpropexpandpower

Let G_v^d be the d-hop egonet of a node v in graph G with diameter D > d.
Let v_1 and v_2 be two non-isomorphic nodes whose d-hop egonets are isomorphic (i.e., G_v_1^d is isomorphic to G_v_2^d) but 2d-hop egonets are not isomorphic.
Then, a WL-GNN representation with d layers will generate identical representations for v_1 and v_2 while is capable of giving distinct node representations.


<Ref> shows that collective learning has yet another benefit: further boosts the power of WL-GNNs with limited message-passing layers by gathering neighborhood information within a larger radius. 
Specifically, built on a WL-GNN with d layers can enlarge the effective neighborhood radius from d to 2d in <Ref> , while WL-GNN would have to stack 2d layers to achieve the same neighborhood radius, which in practice may cause optimization challenges (i.e., d=2 is a common hyperparameter value in the literature).









 §.§ Optimization of 




propositionpropopt


If ∀ v ∈ V_L^(tr), ∇_Θ ( W_v^(t)(^(t);Θ))_y^(tr)_v 
is bounded (e.g., via gradient clipping), then the optimization in <Ref>, with the unbiased sampling of {^(t-1)_v}_v ∈ V^(tr) and ^(t) described above, results in a Robbins-Monro <cit.> stochastic optimization algorithm that optimizes a surrogate upper bound of the loss in <Ref>.




Since the optimization objective in <Ref> is computationally impractical, as it requires computing all possible binary masks and label predictions, <Ref> shows that the sampling procedures used in that considers K samples of label predictions and a random mask at each gradient step is a feasible approach of estimating an unbiased upper bound of the objective.





§ EXPERIMENTS








 §.§ Experiment Setup
 
Datasets.

We use datasets of Cora, Pubmed, Friendster, Facebook, and Protein. The largest dataset (Friendster <cit.>) has 43,880 nodes, which is a social network of users where the node attributes include numerical features (e.g number of photos posted) and categorical features (e.g. gender, college, music interests, etc) encoded as binary one-hot features. The node labels represent one of the five age groups. Please refer to <Ref> for more details.



Train/Test split.
To conduct inductive learning tasks, for each dataset we split the graphs for training and testing, and the nodes are sampled to guarantee that there is no overlapping between any two sets of V_L^(tr), V_L^(te) and V_T. In our experiments, we tested two different label rates in test graph: 0 (unlabeled) and 50%. We run five trials for all the experiments, and in each trial we randomly split the nodes/graphs for training/validation and testing. 

As our method can be applied to any GNN models, we tested three GNNs as examples:



    
  * GCN <cit.> which includes two graph convolutional layers. Here we implemented an inductive variant of the original GCN model for our tasks. 


    
  * Supervised GraphSage <cit.> (denoted by GS) with Mean pooling aggregator. We use sample size of 5 for neighbor sampling.


    
  * Truncated Krylov GCN <cit.> (denoted by TK), a recent GNN model that leverages multi-scale information in different ways and are scalable in depth. The TK has stronger expressive power and achieved state-of-the-art performance on node classification tasks. We implemented Snowball architecture which achieved comparable performance with the other truncated Krylov architecture according to the original paper. 




For each of GNNs, we compare its baseline performance (on its own) to the performance achieved using collective learning in . Note that we set the number of layers to be 2 for GCN <cit.> and GraphSage <cit.> as set in their original papers, and use 10 layers for TK <cit.>. For a fair comparison, the baseline GNN and are trained with the same hyper-parameters, e.g. number of layers, hidden dimensions, learning rate, early-stopping procedures. Please refer to <Ref> for details.


In addition, we also compare to three relational classifiers, ICA <cit.>, PL-EM <cit.> and GMNN <cit.>. The first two models apply collective learning and inference with simple local classifiers —— Naive Bayes for PL-EM and Logistic regression for ICA. GMNN is the state-of-the-art collective model with GNNs, which uses two GCN models to model label dependency and node attribute dependency respectively. All the three models take true labels in their input, thus we use _L^(tr) for training and _L^(te) for testing. 

We report the average accuracy score and standard error of five trials for the baseline models, and compute the absolute improvement of accuracy of our method over the corresponding base GNN. We report the balanced accuracy scores on Friendster dataset as the labels are highly imbalanced. To evaluate the significance of our model's improvements, we performed a paired t-test with five trials.





 §.§ Results

The node classification accuracy of all the models is shown in <Ref>. Our proposed collective learning boost is denoted as +CL (for Collective Learning) in the results and our model performance (absolute % of improvement over the corresponding baseline GNN) is shown in shaded area. Numbers in bold represent significant improvement over the baseline GNN based on a paired t-test (p < 0.05), and numbers with ^* is the best performing method in each column. 




Comparison with baseline GNN models. <Ref> shows that our method improves the corresponding non-collective GNN models for all the three model architectures (i.e. GCN, GraphSage and TK). Although all the models have large variances over multiple trials — which is because different parts of the graphs are being trained and tested on in different trials, our model consistently improves the baseline GNN. The results from a paired t-test comparing the performance of our method and the corresponding non-collective GNN shows that the improvement is almost always significant (marked as bold), with only four exceptions. 
Comparing the gains on different datasets, our method achieved smaller gains on Friendster. This is because the Friendster graph is much more sparse than all other graphs (e.g. edge density of Friendster is 1.5e-4 and edge density of Cora is 1.44e-3 <cit.>), which makes it hard for any model to propagate label information and capture the dependency. 

Moreover, comparing the improvement over GCN and TK, we can observe that in general our method adds more gains to GCN performance. For example, with 3% training labels on Cora, our method when combining with GCN has an average of 6.29% improvement over GCN, 2.35% improvement over GraphSage, and 0.96% improvement over TK. This is in line with our assumption <Ref> that collective learning can help GNNs produce a more expressive representation. As GCN is provably less expressive than TK <cit.>, there is a larger room to increase its expressiveness. 

Note the we use different trials for the two test label rates, the gains are generally larger when 50% of the labels are available. For example, when combining with GCN, the improvements of our method are 6.29% and 1.72% for unlabeled Cora and Facebook test sets, but with partially-labeled test data, the improvements are 15.69% and 2.95% respectively. This shows the importance of modeling label dependency especially when the some test data labels are observed. 


Comparison with other relational classifiers
The two baseline non-GNN relational models, i.e. PL-EM and ICA generally perform worse than the three GNNs, with the only exception on Protein dataset. This could be because the two non-GNN models generally need a larger portion of labeled set to train the weak local classifier, whereas GNNs utilize a neural network architecture as "local classifier", which is better at representation learning by transforming and aggregating node attribute information. However, when the model is trained with a large training set (e.g. with 30% nodes on Protein dataset), modeling the label dependency becomes crucial. At the same time, our method is still able to improve the performance of the corresponding GNNs.

For GMNN, the collective GNN model, it achieved better performance than its non-collective base model, i.e. GCN, and we can see that our model combining with GCN achieved comparable or slightly better performance than GMNN. When combing with other more powerful GNNs, our model can easily out-perform it, e.g. on Cora, Pubmed and Facebook datasets, the TK performs better than GMNN and our method adds extra gains over TK. 




We did two ablation studies to investigate the usage of predicted labels (detailed in <Ref>), which showed that (1) adding predicted labels in model input had extra value comparing to using true labels only, and (2) the gain of our framework is from using samples of the predicted labels rather than random one-hot vectors.
 

Runtime analysis. computes K embeddings at each stochastic gradient step, therefore 


overall, per-gradient step, is K slower than its component WL-GNN. Overall, after T iterations of Steps 1-3, total runtime increases by T × K over the original runtime of its component WL-GNN.


Our experiments are conducted on a single Nvidia GTX 1080Ti with 11 GB of shared memory. built on GCN on the largest dataset (i.e. Friendster with 43K nodes) takes 66.31 minutes for training and inference (the longest time), with a total of T=10 iterations, while the corresponding GCN takes only 1.04 minutes for the same operations. In the same dataset, built on TK takes 132.33 minutes for training and inference, while the corresponding TK takes 1.93 minutes.
We give a detailed account of running times on smaller graphs in <Ref>.
We note that we spent nearly no time engineering for speed or for improving our results. 
Our interest in this paper lies entirely on the gains of a direct application of . 

We fully expect that further engineering advances can significantly reduce the performance penalty and increase accuracy gains.
For instance, parallelism can significantly reduce the time to collect K samples in .





§ RELATED WORK




On collective learning and neural networks.
There has been work on applying deep learning to collective classification. For example, <cit.> proposed to use LSTM-based RNNs for classification tasks on graphs. They transform each node and its set of neighbors into an unordered sequence and use an RNN to predict the class label as the output of that sequence. <cit.> designed a deep learning model for collective classification in multi-relational domains, which learns local and relational features simultaneously to encodes multi-relations between any two instances. 

The closest work to ours is <cit.>, which proposed a recurrent collective classification (RCC) framework, a variant of ICA <cit.> including dynamic relational features encoding label information. Unlike our framework, this method does not sample labels , opting for an end-to-end training procedure.
<cit.> opts for a similar no-sample RCC end-to-end training method as <cit.>, now combining a differentiable graph kernel with an iterative stage.
Graph Markov Neural Network (GMNN) <cit.> is another promising approach that applies statistical relational learning to GNNs.
GMNNs model the joint label distribution with a conditional random field trained with the variational EM algorithm. 
GMNNs are trained by alternating between an E-step and an M-step, and two WL-GCNs are trained for the two steps respectively.
These studies represent different ideas for bringing the power of collective classification to neural networks.
Unfortunately, <Ref> shows that, without sampling , the above methods are still WL-GNNs, and hence, their use of collective classification fails to deliver any increase in expressiveness beyond an optimal WL-GNN (e.g., <cit.>).





In parallel to our work, <cit.> considers regression tasks by modeling the joint GNN residual of a target set (y - ŷ) as a multivariate Gaussian, defining the loss function as the marginal likelihood only over labeled nodes ŷ_L.  In contrast, by using the more general foundation of collective classification, our framework can seamlessly model both classification and regression tasks, and include model predictions over the entire graph  as 's input, thus affecting both the model prediction and the GNN training in inductive node classification tasks. 




On self-supervised learning and semi-supervised learning.
Self-supervised learning is closely related to semi-supervised learning.
In fact, self-supervised learning can be seen as a self-imposed semi-supervised learning task, where part of the input is masked (or transformed) and must be predicted back by the model <cit.>.
Recently, self-supervised learning has been broadly applied to achieve state-of-the-art accuracy in computer vision <cit.> and natural language processing <cit.> supervised learning tasks. 
The use of self-supervised learning in graph representation learning is intimately related to the use of pseudolikelihood to approximate true likelihood functions.


Collective classification for semi-supervised learning tasks.

Conventional relational machine learning (RML) developed methods to learn joint models from labeled graphs <cit.>, and applied the learned classifier to jointly infer the labels for unseen examples with collective inference.
When the goal is to learn and predict within a partially-labeled graph, RML methods have considered semi-supervised formulations <cit.> to model the joint probability distribution:

    P (_U|_L,, ).

In this case RML methods use both collective learning and collective inference procedures for semi-supervised learning. 

RML methods typically consider a Markov assumption to simplify the above expressions —every node v_i ∈ V is considered conditionally independent of the rest of the network given its Markov Blanket (ℳℬ(v_i)). For undirected graphs, this is often simply the set of the immediate neighbors of v_i. Given the Markov blanket assumption, RML methods typically use a local conditional model (e.g., relational Naive Bayes <cit.>, relational logistic regression <cit.>) to learn and infer labels within the network. 


Semi-supervised RML methods utilizes the unlabeled data to make better predictions within the network. Given the estimated values of unlabeled examples, i.e.P(_U^(tr)|_L^(tr), ^(tr), ^(tr)), the local model parameters can be learned by maximizing the pseudolikelihood of the labeled part:


    O = ∑_v ∈ V^(tr)log P(y_v^(tr) | ^(tr)_ℳℬ(v), ^(tr), ^(tr)).


The key difference between <Ref> and the GNNs objective in <Ref>: the RML model is always conditioned on the labels (either true labels ^(tr)_L or estimated labels ^(tr)_U) even when there are no observed labels in the test data, i.e., even when _L^(te) = ∅. 


The most common form of semi-supervised RML utilizes expectation maximization (EM) <cit.>, which iteratively relearn the parameters given the expected values of the unlabeled examples. For instance, the PL-EM algorithm <cit.> optimizes the pseudolikelihood over the entire graph:

    E-Step: evaluate  P(_U^(tr)|_L^(tr), ^(tr), ^(tr), Θ_t-1)
       M-Step: learn Θ_t:
       Θ_t = _Θ∑__U^(tr)∈Γ_UP(_U^(tr)|_L^(tr), ^(tr), ^(tr), Θ_t-1) 
      ∑_v ∈ V^(tr)log P(y_v^(tr)|_ℳℬ(v)^(tr), ^(tr), ^(tr), Θ).


In comparison to semi-supervised RML, our proposed framework performs collective learning to strengthen GNN, which is a more powerful and flexible "local" classifier compared to the typical weak local classifier used in RML methods (e.g. relational Naive Bayes). For parameter learning (M-step), also optimizes pseudolikelihood, but incorporates Monte Carlo sampling from label prediction ^(t-1) instead of directly using the predicted probability of unlabeled nodes P(_U^(tr)|_L^(tr), ^(tr), ^(tr), Θ_t-1).

Collective inference. When the model is applied to make predictions on unlabeled nodes (in the E-step), joint (i.e., collective) inference methods such as variational inference or Gibbs sampling must be applied in order to use the conditionals from <Ref>. This combines the local conditional probabilities with global inference to estimate the joint distribution over the unlabeled vertices, e.g.,:

    P(_U|_L, ) ≈ Q(_U) = Π_v_i ∈ V_UQ_i(y),

where each component Q_i(y) is iteratively updated.

Alternatively, a Gibbs sampler iteratively draws a label from the corresponding conditional distributions of the unlabeled vertices:

    ŷ_v ∼ P(y_v | Ŷ_ℳℬ(v), _L,  , A),  ∀ v ∈ V.

In Gibbs sampling, it is the sampling of labels that allow us to sample from the joint distribution, which is what enriches the simple models often used in collective inference.


















§ CONCLUSION



In this work, we answer the question “can collective learning and sampling techniques improve the expressiveness of state-of-the-art GNNs in inductive node classification tasks?” 

We first show that with the most expressive GNNs there is no need to do collective learning; however, since we do not have the most expressive models, we present the collective learning framework (exemplified in ), that can be combined with any existing GNNs to provably improve WL-GNN expressiveness. We considered the inductive node classification tasks across graphs, and showed by extensive empirical study that our collective learning significantly boosts GNNs performance on all the tasks.




§ POTENTIAL BIASES


This work presents an algorithm for node classification that works on arbitrary graphs, including real-world social networks, citation networks, etc..
Any classification algorithm that learns from data runs the risk of producing biased predictions reflective of the training data — our work, which learns an inductive node classifier from training graph examples, is no exception. However, our main focus in this paper is on introducing a general algorithmic framework that can increase the expressivity of existing graph representation learning methods, rather than particular real-world applications. 






icml2020





 



§ SUPPLEMENTARY MATERIAL OF COLLECTIVE LEARNING GNN




§ PROOF OF <REF>


We restate the theorem for completeness.
*

Let Ŷ(v) = φ (Γ^⋆(v,G)) be a classifier function that takes the most expressive representation Γ^⋆(v,G) of node v as input and outputs a predicted class label for v. 

Let ^(t) be the set of predicted labels at iteration t of collective classification and let Y_v be the true label of node v ∈ V. 
Then either (1) Y_v _Γ^⋆(v,G),φ^(t), or (2) Y_v _Γ^⋆(v,G),φ^(t). 

Case (1): Given the classifier φ and the most expressive representation Γ^⋆(v,G), the true label of v is independent of the labels predicted with collective classification. In this case, the predicted labels of v's neighbors offer no additional information and, thus, collective classification is unnecessary.

Case (2): In this case, the true label of v is not independent of the predicted labels. By Theorem 1 of <cit.>, we know that for any random variable H_v attached to node v ∈ V, it must be that ∃φ' a measurable function independent of G s.t. 

    H_v a.s.=φ' (Γ^⋆(v,G),ϵ_v),

where ϵ_v is an noise source exogenous to G (pure noise), and a.s. implies almost sure equality. Defining H_v := Y_v,  

    φ' (Γ^⋆(v,G),ϵ_v) _Γ^⋆(v,G),φ^(t),


which means ^(t) must either be dependent on ϵ_v or contain domain knowledge information about the function φ' that is not in φ. Since ^(t) is a vector of random variables fully determined by G and φ, it cannot depend on an exogenous variable ϵ_v, Thus, the predictions must contain domain knowledge of φ'. 
Hence, we can directly incorporate this domain knowledge into another classifier φ^† s.t. Y_v _Γ^⋆(v,G),φ^†^(t), for instance φ^† is a function of φ'. In this case, φ^† will predict the label of v with equal or higher accuracy than collective classification based on predicted labels , which finishes our proof.



















§ PROOF OF <REF>



    
*
 
As defined, WLGNN is a most-expressive WL-GNN.
We need to prove (WL-GNN) ⊊().
We will do that by first showing () = (WL-GNN) ∪ S' and then showing that ∃ G ∈()  s.t.  G ∉(WLGNN).

() = (WL-GNN) ∪ S': First, we need to show that for any mask M ∈, ∃ S ⊆() such that S = (WL-GNN).
This is clearly true since, for labeled tests, in <Ref> we can always construct a WLGNN^0 for a 
    _v^(t)(WLGNN^0)= _^(t-1)[    WLGNN^0(^(tr), ^(tr)_L⊙ M, 
     ^(t-1)⊙M, ^(tr) ; Θ)_v ],

that ignores the  inputs.
Similarly, for unlabeled tests,  in <Ref>  we can always construct a WLGNN^1 for a 
    _v^(t)(WLGNN^1) = _^(t-1)[ WLGNN^1(^(tr), ^(t-1), ^(tr) ; Θ)_v ],

that ignores the ^(t-1) inputs.

∃ G ∈()  s.t.  G ∉(WL-GNN):

Let G be the graph in <Ref>.
We will first consider the case where the test data has partial labels. The case without labels follows directly from it.
Using the graph G in <Ref>(a) (training) and <Ref>(c) (partially-labeled testing) we show that a WL-GNN is unable,  in test, to correctly give representations to the left-most nodes {1,2,3,4} that are distinct from the right-most nodes {5,6,7,8} (the same happens for the unlabeled test graph in <Ref>(b)).
We then show that the representation ^(t)_v of <Ref> is able to distinguish these two sets of nodes.

WL-CNN is not powerful enough  to give distinct representations to nodes {1,…,8} in <Ref>(c):
Consider giving an arbitrary feature value (say, the “color white”) to all uncolored nodes {1,…,8} in <Ref>(c).
We will start showing that the 1-WL test is unable to give different colors to the nodes {1,…,8} in this graph.
Since WL-GNNs are no more expressive than the 1-WL test <cit.>, showing that the above is a stable coloring for nodes {1,…,8} in the 1-WL test, proves the first part of our result.
A stable 1-WL coloring is defined as a coloring scheme on the graph that has a 1-to-1 correspondence with the colors in the previous step of the 1-WL algorithm.
Since the input to the hash function of the 1-WL test is the same for all of nodes v ∈{1,…,8}: The node itself has color white while the color set of the neighbors is the set {white,yellow}. 
In the next 1-WL round, all the white nodes will be mapped to the same color by the hash function. The colors of node {9,10} will be not the same as {1,…,8}.
Hence, the initial coloring of all nodes {1,…,8} white and {9,10} yellow is a stable coloring for 1-WL.
Consequently, WL-GNN will give the same representation to all nodes in {1,…,8}.








    

    
 gives the same representations within the sets {1,…,4} and {5,…,8}: 
At iteration t ≥ 0 of ,
we start with the base of the recursion ^(t-2) =  0.






Now consider a given mask ^(t)∈.


 Note that to sample ^(t-1)_v for v ∈{1,…,8} we apply ^(t-2) =  0 into  <Ref> to obtain _v^(t-1), and then apply _v^(t-1) into <Ref>, defining __L^(tr),^(t-1),^(t)^(tr) = [^(tr),^(tr)_L⊙^(t) ,  0], which will give us ^(t-1)_v ∼ P(^(t-1)_v   |  WLGNN([^(tr),^(tr)_L⊙^(t) ,  0], ^(tr) ; Θ)_v), and any classes has a non-zero probability of being sampled since our output is a softmax.
 
Since nodes {1,…,8} all get the same representation in the above WLGNN, their respective sampled ^(t-1)_v, v ∈{1,…,8}, will have the same distribution but possibly not the same values (due to sampling).
Note that the nodes {1,…,4} will get the same average in <Ref> since ^(t-1)_v, v ∈{1,…,4}, has the same distribution and the nodes are isomorphic (even given the colors on nodes 9 and 10).
Similarly, the nodes {5,…,8} will also get the same average in <Ref>.

 gives distinct  representations accross the sets  {1,…,4} and {5,…,8}:
Finally, we now prove that exists a WL-GNN, which we will denote WLGNN^2, such that _v^(t)(WLGNN^2) ≠_u^(t)(WLGNN^2) for v ∈{1,…,4} and u∈{5,…,8}.
We will show that there is a joint sample of _1^(t-1),…,_8^(t-1) where there is no symmetry between the representations of nodes in {1,…,4} and {5,…,8}.
Since each layer of WLGNN^2 can have different parameters, we can easily encode differences in the number of hops it takes to reach a certain color. 
Moreover, at any WLGNN^2 layer, the representation of a node can perfectly encode its own last-layer representation and the last-layer representation of its neighbors through a most-expressive multiset representation function <cit.>.

It is enough for us to show that for a sampled ^(t-1) the sets of nodes {1,…,4} and {5,…,8} can get distinct unique representations under WLGNN^2.
By unique, we mean, {1,…,4} can get representations in WLGNN^2 that cannot be obtained by the nodes in {5,…,8}.
This representation uniqueness makes sure the averages in <Ref> are different.
Without loss of generality we will consider giving a special sampled label to only one node i ∈{1,5} in one of the sets.
The sampled labels
_i^(t-1) = green, while all other nodes {1,…,8}\{i} get red, will happen with non-zero probability, hence, they must be part of the expectation in <Ref>.
Note that node 2 (for i=1) and 6 (for i=5) will feel the effects of the green color in their neighbors differently.
That is, for i=5 there is a parameter choice for the layers of WLGNN^2 where the representation of node 6 uniquely encodes that the color green is within hops 1 (node 5) and 3 (from node 5 through nodes 9 and 10) of node 6 (if 6 treats its own representation differently from its neighbors). 
For i=1, node 2's representation will encode that green is observed hops 1 (node 1) and 2 (from node 1 through node 9) (similarly, 2 treats its own representation differently from its neighbors).
Hence, these representations can be made unique by WLGNN^2, i.e., no other ^(t-1) assignments will create the same patterns for nodes 2 and 6, and thus, since WLGNN^2 has most-expressive multiset representations, it can give a unique representation to nodes 2 and 6 for these two unique ^(t-1) configurations.
These unique representations are enough to ensure _2^(t)(WLGNN^2) ≠_6^(t)(WLGNN^2) for any t ≥ 1, which concludes our proof.














 















    

    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    







§ PROOF OF <REF>




*

Let G be the graph in <Ref>(a) with no node features, and let WLGNN be of order 2, meaning it will generate node embeddings based on 2nd-order neighborhoods (shown in (b)). Since node 1 and 2 have the same 2nd-order neighborhood structure, WLGNN will generate identical node representation for them, which gives random label predictions. Meanwhile, as nodes 5 and 6 have distinct 2nd-order neighborhood structures, WLGNN generates different node representations for them, which enables the model to learn from the labels y_5 and y_6. We can assume the predicted label probability P(^(0)_5= green) = 0.99 and P(Ŷ^(0)_6 = red) = 0.98. For , at iteration t = 1, we sample ^(0) from the WLGNN output P(^(0)) and use the samples as input. In the worst case, nodes 3, 4 and 7, 8 get the same distribution and sampled labels (i.e. _3^(0) = _4^(0), _7^(0) = _8^(0)). Since the distribution of _5^(0) and _6^(0) are different, the samples of _5^(0) and _6^(0) are different, which breaks the tie between the 2nd-order neighborhood of nodes 1 and 2. Therefore, will produce different node representation starting from iteration t = 1 for nodes 1 and 2, which enables the model to learn from the training label y_1 and y_2, and thus gives more accurate predictions. 



The advantage of collective inference is more clear when it is used to strengthen less-expressive local classifiers, e.g. logistic regression
Although GNN are much powerful than these local classifiers by aggregating high(er)-order graph information, collective learning can still help if GNN fail to make use of “global” information in graphs (or equivalently, if the order of GNN is small than graph diameter).
Previous work <cit.> investigating the power of collective inference also showed that methods for collective inference benefit from a clever factoring of the space of dependencies, by arguing that these (collective inference) methods benefit from information propagated from outside of their local neighborhood. Predictions about the class label on other objects essentially “bundle information” about the graph beyond the immediate neighborhood. 








§ PROOF OF <REF>

*

In our optimization, we only need to sample two variables 







^(t-1) and ^(t).

We obtain unbiased bounded-variance estimates of the derivative of the loss function if we sample ^(t)∼Uniform() (and exact values when ^(t) =  0).
We can now compound that with unbiased bounded-variance estimates of the derivative if we estimate the expectation in <Ref> {^(t-1)_v}_v ∈ V by i.i.d. sampling ^(t-1).
The loss in <Ref> is convex on _v^(t) since the negative log-likelihood of the multi-class logistic regression is convex on W, which means it is also convex on _v^(t) as the loss is defined on the affine transformation W_v^(t). 
The expectation of the loss always exist, since we assume ∇_Θ ( W_v^(t)(^(t);Θ))_y^(tr)_v is bounded for all ∀ v ∈ V_L^(tr).
Hence, as the loss is convex w.r.t. _v^(t), the expection w.r.t. _v^(t) exists, and we obtain an unbiased estimate of _v^(t), we can apply Jensen's inequality to show that the resulting Robbins-Monro stochastic optimization optimizes an upper bound of the loss in <Ref>.







§ ADDITIONAL INFORMATION ON DATASETS AND EXPERIMENT SETUP


Datasets.
We use five datasets for evaluation, with the dataset statistics shown in <Ref>. 






    
  * Cora and Pubmed are benchmark datasets for node classification tasks from <cit.>. They are citation networks with nodes representing publications and edges representing citation relation. Node attributes are bag-of-word features of each document, and the predicted label is the corresponding research field. 


    
  * Facebook <cit.> is social network of Facebook users from Purdue university, where nodes represent users and edges represent friendship. The features of the nodes are: religious views, gender and whether the user’s hometown is in Indiana. The predicted labels is political view. 


    
  * Friendster <cit.> is social network. Nodes represent users and edges represent friendship. The node attributes include numerical features (e.g number of photos posted, etc) and categorical features (e.g. gender, college, music interests, etc), encoded as binary one-hot features. The node labels represent one of the five age groups: 0-24, 25-30, 36-40, 46-50 and over 50. This  version of the graph contain 40K nodes, 25K of which are labeled.


    
  * Protein is a collection of protein graphs  from <cit.>. Each node is labeled with a functional role of the protein, and has a 29 dimensional feature vector. We use 85 graphs with an average size of 150 nodes. 




Data splits.
To conduct inductive learning tasks, we have to properly split the graphs into labeled and unlabeled parts. For datasets containing only one graph (Cora, Pubmed, Facebook and Friendster), we randomly sample a connected component to be V_L^(tr), and then sample a test set (V_T) from the remainder nodes (V_U). To make partially-labeled test data available, we sample another connected component as V_L^(te) with the same size as V_L^(tr). The nodes are sampled to guarantee that there is no overlapping between any two sets of V_L^(tr), V_L^(te) and V_T. Here G^(tr) and G^(te) have the same graph structure but with different labeled nodes.

For the protein dataset, as we have 85 disjoint graphs, we randomly choose 51 (60%) graphs for training, 17 (20%) graphs for validation and the remaining 17 (20%) graphs for testing. To simulate semi-supervised learning settings, we mask out 50% of true labels on the training graphs. For the tasks with partially-labeled test data, we randomly select 50% of the nodes in the test graphs as labeled nodes, and test on the remaining 50% nodes. We run five trials for all the experiments, and in each trial we randomly split the nodes/graphs as described. 


As seen in <Ref>, to approximate an inductive learning setting, we use a different train/test data split procedure (i.e. connected training set) on Cora and Pubmed networks from the public version (i.e. random training set) used in most of the existing GNN models <cit.>. This is illustrated in <Ref>, where the random training set of the traditional GNN evaluation methods (in e.g., <cit.>) is shown on the left, contrasted with our harder task of connected training set shown on the right. 
This difference in task is the reason why the model performance reported in our paper is not directly comparable with the reported results in previous GNN papers, even though we used the same implementations and hyperparameter search procedures.




Hyperparameter setting.
For hyperparameter tuning, we searched the initial learning rate within {0.005, 0.01, 0.05} with weight decay of 0.0005. Dropout is applied to all the layers with p = 0.5. Hidden units are searched within {16, 32} if the dataset wasn't used by the original GNN paper, or set as the same number as originally chosen in the GNN paper. The number of layers is set to 2 for both GCN <cit.> and GraphSage <cit.> as used in their paper, and we use 10 layers for TK <cit.>. For GraphSage <cit.>, the neighborhood sample size is set to 5. We use the same GNN structure (i.e. layers, hidden units, neighborhood sample size) for the non-collective version and in for fair comparison. 

For , the additional hyperparameters are (1) the sample size of predicted labels Ŷ (K), and (2) the number of model iterations (T). we set sample size K = 8 for friendster dataset and K = 10 for all other datasets. For label rate of 50%, the model is trained for T = 10 iterations, and each iteration contains 100 epochs. Note that we sample a new binary mask for each epoch as described in <Ref>. For label rate of 0%, the model is trained for T = 3 iterations, and each iteration contains up to 500 epochs which can be early stopped if the validation accuracy decreases for a specified consecutive epochs. The numbers of iterations are empirically determined as only marginal improvements are observed after 3 iterations for unlabeled test data and 10 iterations for partially-labeled test data. The validation accuracy is used to choose the best epoch. 

Note that the hyper-parameter tuning could be done more aggressively to further boost the performance of , e.g. using more layers for TK <cit.>, but our main goal is to evaluate the relative improvements of on the corresponding non-collective GNNs. 






§ RUNNING TIMES FOR GNN MODELS ON MULTIPLE DATASETS
 




<Ref> shows the running times for and the corresponding non-collective GNNs on various datasets. As mentioned in , for partially-labeled G^(te), applied random masks at each epoch, and ran for 10 iterations, whereas for unlabeled G^(te), ran for 3 iterations. 



§ PERFORMANCE WITH VARYING TRAINING LABEL RATES

To investigate the impact of the training label rates on the node classification accuracy, we repeated the experiments on Cora and Pubmed datasets with various numbers of training labels, on unlabeled test data and partially-labeled test data. <Ref> and <Ref> show the results for test labels rates of 0% and 50% respectively. We can see that in general framework achieved a larger improvement when fewer labels are available in the training graph. For example, with label rates of 1.52%, 1.90% and 3.04% on Pubmed, the improvements of our framework combining with GCN are 4.48%, 3.30% and 0.98% respectively. This shows that the framework is especially useful when only a small number of labels are available in training, which is the common use case of GNNs. 

















































§ ABLATION STUDY
 


 §.§ With or without predicted labels as input

 

 To investigate if adding predicted labels in model input adds extra information with partially-labeled test data, we tested the performance of a model variant which only use true labels as input with the same node masking procedure. <Ref> shows two examples on Cora with GCN (<Ref>) and Pubmed with TK (<Ref>), where including predicted labels achieves better performance. We run the model 10 times and calculate the average and standard deviation (shown as shaded area) of classification accuracy at each iteration t as described in <Ref>. We can see that adding predicted labels starts to improve the performance after the first iteration and achieves consistent gains.
 







 §.§ Sampling from predicted labels or random ids


Creating more expressive GNN representations by averaging out random features was first proposed by <cit.>. 
<cit.> shows a whole-graph classification application, Circulant Skip Links (CSL) graphs, where such randomized feature averaging is provably (and empirically) more expressive than GNNs.

Our Monte Carlo collective learning method can be seen as a type of feature averaging GNN representation though, unlike <cit.>, the feature sampling is not at random, but rather driven by our own model recursively.
Hence, it is fair to ask if our performance gains are simply because random feature averaging is beneficial to GNN representations? 
Or does collective learning sampling actually improve performance?
We need an ablation study.

Therefore, in this section we investigate whether the gains of our method for unlabeled test data are from incorporating feature randomness, or from sampling w.r.t predicted labels (collective learning). To do so, we replace the samples drawn from previous prediction  as uniformly drawn from the set of class labels at each gradient step in . The results are shown in <Ref>.
Clearly, the random features are not able to consistently improve the model performance as our method does (contrast <Ref> with <Ref> and <Ref>). 
In summary, collective learning goes beyond the purely randomized approach of <cit.>, providing much larger, statistically significant,  gains.




































































