Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation
Authors: Zhiqiang Zhong
Sergei Ivanov
Jun Pang
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs) have been predominant for graph learning tasks; however, recent studies showed that a well-known graph algorithm, Label Propagation (LP), combined with a shallow neural network can achieve comparable performance to GNNs in semi-supervised node classification on graphs with high homophily. In this paper, we show that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. To overcome this, we carefully design a combination of a base predictor with LP algorithm that enjoys a closed-form solution as well as convergence guarantees. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities. On a wide variety of benchmarks, we show that our approach achieves the leading performance on graphs with various levels of homophily. Meanwhile, it has orders of magnitude fewer parameters and requires less execution time. 

Published in Transactions on Machine Learning Research (10/2022)
Simplifying Node Classification on Heterophilous Graphs with Compatible Label Propagation
Zhiqiang Zhong
shigiong.zzhnng@hrr
University of Luzembourg
Sergey Ivanov
bwnnonsergg9900mmmal..com com
Criteo
Jun Pang
jun.pang Buni. bu
University of Luzzmbourg
Reviewed on OpenReview: https: // openreview. net/ forum? id= JBuCfBkkKKK
Abstract
Graph Neural Networks (GNNs) have been predominant for graph learning lasks; how- ever, recent studies showed that well-known graph algorithm, Label Propagation (LP), combined with a shallow neural network can achieve comparable performance GNNs in graphs with high homophily. In this paper, show
semi-supervised node classification that this approach falls short on graphs with low homophily, where nodes often connect to the nodes of the opposite classes. To overcome this, we carefully design a combination of a base predictor with LP algorithm that enjoys a closed-form solution as well as convergence guarantees. Our algorithm first learns the class compatibility matrix and then aggregates label predictions using LP algorithm weighted by class compatibilities. On a wide variety of benchmarks, we show that our approach achieves the leading performance on graphs with various levels of homophily. Meanwhile, it has orders of magnitude fewer parameters and requires less execution time.
1 Introduction
Following the triumph of deep learning in computer vision and natural languago processing, more and more success stories are coming from message-passing Graph Neural Networks (GNNs) suited for relational data such as graphs or meshes (Zhang et al. 2020 Wu al. 2021). The majority of modern deep learning architectures can be considered as special case of the GNN with specific geometrical structures (Bronstein) et al. 2021). These models have achieved state-of-the-art performance in tasks such (semi-)suppervieed node classification, common in real-world applications, and crested popular leaderboards such as Open Graph Benchmark (Hu et al. (220)). The landscape of GNNs is rich, and many new architectures have been recently proposed to compensate for limited expressivity (Velickovic et al.) 20188] Xu et al., 2019 Du 2019 Azizian Lelarge 2020) or solve specific problems such as over-smoothingg inherent to the
et al.
traditional messago-passing layers (Li et al., 2018 Zhao & Akoglu, 20200: Min al.) 2020: Yan et al. 2021 Unfortunately, these models attain desiderata with the extra price of being more complex and less intuitive during inspection of their performance gains, therefore restricting their applicability in practice.
To address these problems, several models were proposed recently that do not use messagc-passingg algo- rithun of GNNs but instead are based on well-studied a algorithms that show promising results in graph problems (Tian et al.) 2019 Rossi et al. 2020 Huang et al. 2021 Ivanov & Prokhorenkova 2021). Here, we resort a graph algorithm called Label Propagation (LP) (Zhou et al.) 2003 Zhu 2005) competitive algorithm in semi-supervised node classification setup, which was popular for more than decade. While
GNNs learn mapping functions between node features and class labels, T.P algorithm directly incorporates

---

Published in Transactions on Machine Learning Research (10/2022)
class labels of the train nodes to make predictions the test nodes. As traditional LP algorithm does not use node features (which may contain significant signal about the class labels of the nodes), it was recently shown (Huang et al. 2021 that by making "base predictions" by a linear network on the node features and then substituting the predictions to the LP algorithm, it is possible to boost the performance up to the results of more complex GNNs. These results, however, are often obtained for the graph datasets that exhibit only high homophily, i.c. structure where neighbouring nodes are likely to have the same class labels. In graphs with low homophily, known as heterophily ("opposites attract"), "), LP and traditional GNNs fall short and are often outperformed by simple methods such multi-layer perceptron (Rosenblatt, 1961) (shown in Section 6.3 In order to give precise description of the node label relationship of an arbitrary graph, here we introduce and formally define the homophily ratio of a graph.
Definition 1 (Homophily Ratio h). For an arbitrary graph G (V,E,X) its homophily ratio h is determined by the relalionship belween mode class labels and graph structure encoded in the adjacency malrix. Recent work commonly use two homophily metrics: edge homophily hedge [Zhu et al. 2021) and node homophily Pei et al. 2020). They can be formalated as:
mode
[(u, v): (u, ENDEEEM EE = =V.3
1 D
Ku u E N. A yn - ynH
Nedge=
hnode
(1)
[3
N.1
NE
where No is the set of adjacent nodes of node v and 1-1 represents the number of elements of the set. Specifically, hedge evaluates the fraction of edges in a graph that connect nodes that have the same class labels; Unode evaluates the overall fraction of neighbouring nodes that have the same class labels. In this paper, we focus on edge homophily and set h= hedge in the following sections.
Motivated by this limitation, several GNN architectures were proposed to make message- passing paradigm work on heterophilous graphs (Zhu et al. 2020 Chen et al. 2020 Yan et al. 2021 Bo et al. 2021 Zheng al., 2022). These models revolve around modifications of neighbourhoods used for aggregation schemes of GNNs to enrich the diversity of class labels among neighbours. For example, Zhuu et al. (2020) uses multiple-hov hop neighbourhoods for the aggregation in GNNs, which in turn provides more complete information about the connectivity of different classes. While such approaches bridge the gap for traditional GNNs on heterophilous graphs they often do so at the expense of more parameters and longer training time.
Instead, in this work, we modify LP algorithm to work well in supi-supe node classification on het- crophilous graphs. We start by conducting an experimental investigation over existing models' micro-level performance, i.., evaluating the node classification accuracy for node groups with subgraphs of different homophily ratios. The investigation results (as shown in Fig. [ demonstrate that recent GNNs designed for heterophilous graphs do not outperform simple neural network model that only relies raw on node features, i..., multi-layer perceptron, when the subgraph homophily ratio of a node is low. Inspired by this finding, we propose an elficient Iramework that relies on base predictions given by a simple neural network and further ameliorate the base predictions with a compatible LP algorithm. In particular, we propose a simple pipeline (CLP) with three main steps (Fig. 2 (i) base predictions of all nodes made by simple neural network purely the node features; (ii) a global compatibility matrix that computes connectivity of different class labels is estimated; and (iii) smoothing of the predictions across neighbours weighted by the compatibility of the class labels is performed. Intuitively, step (i) calculates the class probabilities for the test nodes, while step (ii) defines the weights on edges with which LP algorithm at step (iii) will propagate the class probabilities for each node. While steps (i) and (iii) have been tried independently for semi-supervised classification before (iipf & Welling, 2017 Ivanov Prokhorenkova, 2021), it learning the compatibility matrix at step (ii) that makes a big difference as we show in the experiments. In our theoretical analysis, we show that our approach can be computed via closed-fore solution that provides necessary and sufficient conditions for convergence. Empirically, extensive experimental results on a wide variety of benchmarks show the competitive and efficient performance of CLP.
A significant boost in the performance of our method is related to learning a global compatibility matrix between classes. This idea not new before the rise of noural networks for semi-supervised learning several algorithms such as DCE (P. et al., (2020). ZooBP (Eswaran et al. 2017). LinBP (Gatterbauer et al. 2015) and FaBP [Koutra et al. 2011) use compatibility matrix for peoiea-propaggtion algorithm. However,
2

---

Published in Transactions on Machine Learning Research (10/2022)
all of these methods are motivated by the regularisation framework, where the labelling function minimises some energy objective that does not depend on the node features (Gatterbauer, 2014) and were shown to have suboptimal performance to GNNs (P. et al., 2020). More recently, compatibility matrix was used for GNNs in the heterophily setting (Zhu et al. 2021 and showed a significant increase in performance. That being said, we find that learning a compalibility matrix from the node features significantly improves the performance of L.P on heterophilous graphs.
Overall, we generalise LP algorithm to arbitrary heterophily assumption, where the commonly used smooth- ness assumption (homophily) is special case with the identity matrix acting as the compatibility matrix. In this case, LP is orders of magnitude faster than log-likelihood estimators such as GNNs, and it presents new ways to understand the performance of graph learning through the lens of diffusion--bsee learning (Koutra et al. 2011: Gatterbauer 2014 Zhou et al. 2003 Zhu 2005). For example, the insights of using compatibility matrix and class labels as part of the training can be incorporated into existing GNN models. As such, we hope that the idcas of LP algorithm could be fruitful for other tasks such as node regression, and LP could become a commonly used baseline of graph learning practitioners.
2 Additional Related Work
GNNs for heterophily regime. The realisation that standard pressage-passing Graph Neural Network (GNNs) KKipf & Welling 2017; Velickovic et al. 2018; Battaglia et al.) 2018) are suboptimal for graphs with high heterophily was not immediate. At first, there was rich literature on solving the svor-smoog problem (Li et al. 2018) which prevents an increasing number of layers of GNNs without loss of performance (common to deep convolutional nets). After that, with new graph datasets with high heterophily (Pei et al. 2020 Abu-El-Haija et al. 2019 Lim et al.) 2021 Zheng et al. 2022) and new theory that connects the over-smoothing problem with the tendency of nodes to connect to the opposite classes (Yan et al.] 2021] it has become evident that GNNs must incorporate additional knowledge to be suited for heterophilous graphs. Several GNNs were proposed to deal with heterophily setting (Chien et al.) 2021; Bo et al., 2021:
Zhu et al. 2021;; however, usually improved accuracy of these GNNs is traded with an extra computational cost which makes it hard to scale for large datasets, unlike Label Propagation (LP) algorithm, which is a simple graph algorithm. Additionally, |Wang & Leskovee (2020) use label propagation as regularisation to assist messago-passing GNNs in learning proper edge weights, but their approach is still tailored only for homophilous datasets. A recent approach CPGNN (Zhu et al. 2021) uses compatibillty matrix with message- passing process; however, there are several notable differences compared to our approach. First, CPGNN adjusts the weight of the message only based on the class of a sending node and compatibility matrix. In turn, we additionally consider the class of receiving node, which significantly improves the results in our experiments. Second, we provide additional theoretical analysis of our method, giving a closed-form solution and convergence guarantees, which is not available for CPGNN model.
Label propagation for heterophily regime. Perhaps the closest work to ours is (Gatterbauer 2014 Gatterbauer et al. 2015), where a compatibility matrix is used the Linearised Belief Propagation (LinBP) algorithm. There, a compatibility matrix is provided or estimated via closed-form solution to minimise a convex energy function and does not use the node features that are crucial in the estimation of the right labelling functions. Several follow-ups aimed to generalise LinBP to various types of heterophily (Peel 2017) or Markov Random Fields (Gatterbauer 2017). It was later shown in the experiments that these methods are less effective than GNNs in graphs with node features (P. et al., 2020). In contrast, our method combines two orthogonal sources of information - one from the labelling function learned on the node features and another from LP algorithm that uses known labels together with the graph structure.
3 Preliminaries
An unweighted graph with n nodes can be formally represented as G = X),, where V is the set of nodes, x, E R represents node features (I is the
E VVVX V denotes the set of odges, and X fx1, dimensionality of node features). y stands for the set of possible class labels for u E V. For subsequent discussion, we summarise V and E into adjacency matrix A E (0, 10.1) 1
3

---

Published in Transactions on Machine Learning Research (10/2022)
Problem setup. In this paper, focus on the semi-supervised node classification task graph g where Ty C V with known class labels ye for all E TT.. We aim to infer the unknown class labels yo for all u E V Tv. In addition, TV is split into two subsets: T and TV where 73 is training set and T works as the validation set for early stopping or parameter fine-tune to prevent overfitting.
The homophily ratio defined in Definition | is suitable for measuring the overall homophily level in the graph. However, the actual homophily level is not necessarily uniform within all parts of the graph. One typical case is that the homophily level varies among different pairs of classes. To mcasure the variability of the homophily level, we further define the compatibility matriz H by measuring the fraction of outgoing edges from a node in class to node in class j.
Definition (Compatibility Matrix H). The compatibility matriz H has entries [H] that capture the fraction of outgoing edges from node in class to node in class j:
H [(u, v) (u, EAy. i j [(u,)): (u. y =
(2)
The example of Appendix A gives an intuitive explanation of how H measures the variability of the homophily level. In the semi-supervised node classification settings, compatibility matrix H empirically models the probability of nodes belonging to each pair of classes to connect. Mod- elling H is crucial for heterophily settings, but calculating the exact H would require knowledge to class labels of all nodes in the graph, which violates the semi-supervised node classification setting. Therefore it is not possible incorporate exact H. To fill this gap, in Sec. 5.2 we propose approach to estimate H based utilised after to assist the label propagation step (Sec. 5.3). An empirical study in Sec. 6.5] empirically discusses the quality of estimated H and its influence on the model performances.
1.0
Test Accuracy
0.7
GPRGNN
0.8
FAGON
GCN2
0.5
sparsely labelled graph, which is
GCN
MLP
H2GON
0.00
0.25
0.50
0.75
1.00
(a) Wiki
4 An Experimental Investigation
1.0
0.9
In this section, we conduct an empirical study to motivate the design of our approach. Unlike the classic macro-level node classification evaluation method, we provide a different way to understand cxisting models' micro- level effectiveness. The main idea of this experiment is to study how different models perform at the level of an individual node depending on the homophily ratio of the I-hop subgraphs. We define homophily ratio of an individual node h, as follows:
Test Accuracy
0.7
GPRGNN
0.8
FAGCN
GCN2
GCN
0.4
H2GCN
0.3
h2 v( E yoH
0.00
0.25
0.50
0.75
1.00
(3)
h,
E
(b) ACM
where En is the edge set of the induced 1-hop neighbourhood of v.
Figure 1: Classification accuracy for different 1-hop subgraph ho- mophily ratios on Wiki [Ia] and
We take two graphs as examples: a heterophily graph Wiki with 0.30
and homophily graph ACM with h = 0.82. Following the medium splilling (Sec. 6.2 includes details settings), we train different models on the training nodes of graph and compute predictions for the test nodes. We then aggregate the accuracy of predictions for each level of homophily,
ACM Ib graphs.
{0, 0..,,..,,0.. 0.,, 1}, and plot the obtained results in Fig. I Global accuracy across all test nodes can be found in Tab. 2 and Fig.
Results from Tab. 2 and Fig. demonstrate that general GNNs outperform multi-layer perceptron (MLP) Rosenblatt 1961). However, if we zoom in on local neighbourhoods, as shown in Fig. 0 the results of MI.P are often better than those of GNNs when the homophily ratio of a node's 1-hop subgraph is low.
4

---

Published in Transactions on Machine Learning Research (10/2022)
In particular, can see from Fig. 1 that (i) vanilla GCN has superior accuracy for nodes with strong subgraph homophily ratio (he 2 0.7) on both graphs; other advanced GNN models mainly improve the classification accuracy over nodes with low hep and (ii) MLP is relatively stable across different homophily ratio he and is a better model for nodes with low h2 compared to other GNNs. For instance, MLP achieves the best accuracy on nodes with hy S 0.3 on Wiki graph and nodes with h, S 0.6 on ACM graph.
This illustrates that recent GNN models designed for heterophilous graphs do not outperform MLP for nodes with a considerable fraction of neighbours with opposite class labels; instead, they have better global accuracy than MLP by having better accuracy nodes with high homophily ratio ha. Based on this evidence, we propose a simple but effective approach that mainly relics on the predictions of MLP to maintain its favourable performance on nodes with low homophily h, and that further ameliorates the classification results by incorporating the knowledge of the graph structure.
5 Compatible Label Propagation with Heterophily
Dataset
Step (i)
Step (ii)
Class match
X
MLP
B
H
Comparitiltt
Node features
Base predictins
Step (iii)
LP
Graph
Compatbilly
matrix
Labets
Figure 2: Overview of Compatible Label Propagation (CLP) model. Step (i): base predictor, MLP,, makes class predictions for each node using only node features. Step (ii): global compatibility matrix between classes is computed with Eq. 6 Step (iii): propagate class predictions with LP algorithm and get the classes for test nodes. Intuitively, compalibility matrix measures the weighted probabilities of any two largel classes being connected, and as such, it defines the edge weights in LP algorithm.
Our approach starts with simple base predictor over the topological structure. Any off-the-shelf graph-agnostic model can be plugged in to become a base predictor, which enables our approach to accommodate any node features. After, propose approach to estimate the compatibility matrix H of the overall graph and apply it to calculate the relation between each pair of nodes. Finally, we use label propagation algorithm with an estimated compatibility matrix to smooth the prior prediction probabilities on the weighted graph to get the final predictions.
node features, which does not rely on any learning
5.1 Simple Base Predictor
To start, use simple base predictor that does not rely graph structure to learn prior predictions. Specifically, we train model fo to minimise Every (xfo(x)) ve), where x, is the available feature of node and yo is its true class label, L is a loss function. In this paper, we adopt simple multi-layer perceptron (MLP) [Rosenblatt 1961 as the base predictor, where f-th layer can be formally formulated following:
D =(D( +b0))
(4)
where ((() are learnable parameters and (0) is the bias vector. is the activation function (e.g. RELU), and we initialise (0) X.
From fer we get a prior prediction D Softmax(D (D())) (1)) RPPD' where & L is the last layer. Omitting the graph for the prior predictions brings several benefits: (i) it avoids the sensitivity to homophity/etteriighhn
5

---

Published in Transactions on Machine Learning Research (10/2022)
of the graph (as was shown in Fig. 5 MLP's performance maintains good stability for graphs with different homophily ratios); and (ii) it significantly reduces the number of parameters that we need to learn, thus accelerating the approach (as shown in Fig. 8). Next, we use MLP's predictions to estimate the weights for label propagation algorithm.
5.2 Estimation of Compatibility Matrix
The focal idea of compatibility matrix is summarising the relative frequencies of classes between neighbours. Under the semi-supervised node classification scttings, we only know the class labels of a small fraction of nodes (7t). We derive the preliminary class labels of unknown nodes (V), (TT(T)7)))) as the base prediction D. Note that treat validation set nodes unknown nodes, which will be used to evaluate the performance of LP step and pick up the better final predictions. More specifically, denote the training mask M as:
1.
i TO The preliminary knowledge of class labels can be formally represented as:
[M].. = 0, otherwise
B (0) Mo Y M) D
(5)
where is the Hadamard (clement-wise) product, Y
RPIx and Yij = if yo = otherwise Y.j 0.
Next, we estimate a compatibility matrix H that calculates the probability that training node of one class is connected with node of another class.
À S Y)T ()
(6)
where S the Sinkhorn-Knopp function that ensures Á is doubly-stochastic (Sinkhorn & Knopp 1967
A compatibility matrix H can be represents one-hot encoded class labels of training nodes only. In turn, the matrix AB (0) computes the sum of class probabilities across all neighbours of each node. After multiplication of these two matrices, each entry (i.j) of (Mo Y) ( represents a score that a class i among training nodes connected with a node of class j estimated with prior probabilities D. A function converts these scores back to probabilities such that each entry (i,j) of H indicates a probability that class is connected with class j.
multiplication of two matrices, (Mo Y)T and ( The matrix
5.3 Compatible Label Propagation
After obtaining the estimation A. we propagate the knowledge about node class labels with the guide of H the graph. The key idea of our method is that the edge weight of message v in label propagation algorithm depends on both predicted classes of sending and receiving nodes. That contrasts with previous works (Gatterbauer et al. 2015 Zhu et al., 2021) where edge weight depends only on the sending node class probabilities. In particular, for each edge (i,j), we define an edge weight as follows:
F Fl ( (B.O). [B
Intuitively, edge weight [F]y depends on the probabilities that node is connected with some class k. [B] HH), and the probabilities that node j has the same class k. Naturally, to corresponding positions of adjacent matrix to get A E Ra where [A]] F)--
assign the edge weights
Let B and D be the final node class prediction matrix and the base prediction, respectively. A is the fixed weighted adjacent matrix. Then, the final node classifications are approximated by the equation system:
B = (1 + A B
(8)
where [AP F weights. a hyperparameter, which defines how much update the previous state each label propagation step makes.
+ Bl. = AF [B)., and A means the weighted adjacent matrix with k-th dimensional edge

---

Published in Transactions on Machine Learning Research (10/2022)
Iterative updates. Notice that Eq. 8 gives an implicit definition of the final node classification after convergence, it can also be used as iterative update equations, allowing iterative calculation of the final node classification predictions:
B(++1) - (1-a)D + + B(r)
(9)
Thus, the final node classification predictions be computed via linear matrix operations. Note that previous works GGatterbauer et al. 2015 Zhu et al. 2021 compute the compatibility matrix H for LP follows:
B(++1) - (1 a + a A
(10)
Eq. 10 defines an edge weight by the relation between the sending node and H. Hence, receiving nodes get the same message from sending node regardless of the class of the receiving nodes. We argue that the proper weight of message should be determined by both send- ing and receiving nodes (Fig. 3). Appendix A presents a detailed comparison between different L.P-relatdd meth- ods, and empirically demonstrate the advantages of
104
0.6
8
0.2
0.8
Propagation
Instance
10.2 0.8
lo.
0.2
CLP in Sec. 6.5
LP
LP with H
CLP 0.18
0.44
5.4
Theoretical Analysis of CLP
0.6.
10.56 0.44
10.66
0.34
Eq. g allows solving CLP Eq. via iterative updates. Here, we show alternative method that provides closed-form solution, which in turn sets convergence guar- antecs of CLP for each class k. We start by defining vectorisation of a matrix X, which stacks columns X side-by-side.
Figure Comparison of three propagation schemes, M represents the received messages af- ter one propagation itcration. In LP nodes 1 and 2 receive the same message; LP with H overturns the prior prediction of node 1; CLP adapts the heterophily of the graph and reassures confident prior predictions.
Definition (Matrix Vectorisation H. V. Henderson
1981)). Vectorisation of an m n matric X an mn veclor given by:
veel X) X11..... Xul, X12; ....... Xn2,
Xiny
Xun T
(11)
Additionally, the Kronecker product of X and Q is the mp x ng matrix is defined by:
X Q
X
Xin Q
X21 Q
Xy2 Q
X Q
X X T
(12)
Xm1 Q
Xm2
Xmn Q
We ready to give closed-form solution to Eq. Proposition 1 (Closed-form CLP). The closed-form solution for CLP (Eq. 8)
for class le is given by:
vec( [B)..) = (I (I - a) vec( (D)
(13)
Proof of Proposition refers Appendix
can compute the final node predictions in closed-form by using Eq. 13 as long as the inverse of the matrix exists. Based this closed-form solution we next establish necessary and sufficient criteria for convergence.
Therefore, instead of iterative updates Eq. 10
Convergence of iterative CLP. We remind that spectral radius of a matrix is the maximum eigenvalue, i.e. p(X) = ( CLP.
(A.))). (... With Eq, 13 we are now ready to establish convergence guarantees for
Proposition 2 (Convergence of CLP). For class k, CLP iterative updates Eq. ((AF) -1
15 converge and only if

---

Published in Transactions on Machine Learning Research (10/2022)
Proof of Proposition refers Appendix B
As computing the largest eigenvalue may be too expensive for large graphs, following the Gershgorin circle theorem (Weisstein] 2003). one can replace the spectral norm with any sub-multiplicative norm that is faster to compute and give an upper bound to the spectral radius. For || X 1|,= (E, E, (X(( we have p(X) <|| X |لما|| X Il. Hence, one can use Frobenius or 1-induced norm efficiently check if the sufficient condition for convergence is satisfied. In our experiments, we found that CLP converges for all datasets.
5.5
Summary
To review our approach, we start with base predictor, which purely learns from node features to make node class label predictions. Next, we estimate the global compatibility matrix H based on the sparsely labelled graph and base predictions. H describes the overall possibility of nodes belonging classes to connect, which can be utilised to estimate the relationship between cach pair of base prediction vectors. Finally, we perform an efficient LP step to smooth base predictions and obtain class labels with the assistance of the relationship between each pair of nodes.
each pair of
Comparod with cxisting GNN models, CLP similarly benefits from both node features and graph structure, yet. separates them into two processes. It is motivated by the investigation in Sec. 3 that MLP has better accuracy over other GNN models for nodes with low homophily hg Hence would like to maintain MLP's advantages and utilise graph structure to improve it to obtain final predictions. Following this way, both node features and graph structure are appropriately involved in our approach, and it only requires learning parameters specified by a base predictor. Next, we are going to demonstrate the competitive performances of CLP on node classification tasks.
6 Experiments
Table 1: Statistics for six synthetic datasets. (Prod) means contextual node features come from Ogbn- Products, or adopt the statistic features designed by 2D Gaussians.
Beuchmark Name # #Nodes [V]
# Edges |
# Classes
y
Homophily
#Avg. Degree
Syno(Prod)-1
10,
49, 446 to 50, 352
10
[0, 0.1, .... 1
4.95 to 5.02
Syn-(Prod)-2
10, 000
99, 556 to 99, 556
10
[0, 0.1,
1
9.96 to 10.01
Synn((rrod--3
10, 000
149, 090 to 15, 1494
10
[0, 0.1, ....
14.91 to 15.15
To validate our approach's effectiveness, we first empirically demonstrate the performance of CLP and state of the art (SOTA) models on real-world and synthetic dalasets with wide variely of settings. Second, we compare the number of required parameters, the quality of compatibility estimation, the models' execution time, and their performance on different graphs with different label rates. Third, we empirically show the advantages of our propagation method compared with the previous design. We also study the influence of different label rates on the compatibility matrix estimation and classification accuracy and show the efficiency of CLP in terms of the model size.
6.1 Datasets
Real-world datascts. We use a total of 19 real-world datascts (Texas, Wisconsin, Actor, Squirrel, Chameleon, USA-Airports, Brazil-Airports, Wiki, Cornell, Europe-Airports, deezer-europe, Twitch-EN, Twitch-RU, Ogbn-Proteins, WikiCS, DBLP, CS, ACM, Physics) in diverse domains (web-page, citation, co-author, flight transport, biomedical and online user relation). Note that we use ROC-AUC as the evalua- tion metric for the class imbalanced datasets, i.e., Twitch-EN, Twitch-RU and Ogbn-Proteins, following Lim et al. 2021 For other datasets, we use node classification accuracy as our general evaluation metric. See Appendix for detailed descriptions, statistics and references.
Synthetic datasets. We generate random synthetic graphs with various homophily ratios and node features by adopting similar approach (Abu-Fl-HHija et. al. 2019 Kim & Ohl 2027) but with some mod-
8

---

Published in Transactions on Machine Learning Research (10/2022)
ifications. For instance, synthetic graphs (Abu-El-Haipp et al. 2019 have no available contextual node attributes. Specifically, each synthetic graph has 10 classes and 1, 000 nodes per class. Nodes are assigned random features sampled from 2D Gaussians (Syn) or contextual features from real-world datasets (Hu et al. 2020) (Syn-Prod). Except for the homophily ratio, we also control the average degree of cach graph (around 5, 10 or 15) to investigale the performance with respect to graph sparsity. Here, we give detailed descriptions of the generation process.
Graph generation. We generate synthetic graph g of | nodes with |}] different class labels, and g has MI/ID1 nodes per class. [V] and [}'] are two prescribed numbers to determine the size of G. A synthetic graph's homophily ratio h is mainly controlled by Pin and Pout, where Pin mcans the possibility of cxisting an edge between two nodes with the same label and Pout is the possibility of existing an edge between two nodes with different class labels. Furthermore, the average degree of g is davg = |M//D// 6, where = Pin + (1>) - 1) Pout- Following the described graph generation process, with given [V], y and daeg: we choose Pin from (0.00016, 0.18, 0.25..... 0.900,, 0.999963. Note that the synthetic graph generation process requires both pin and Pout are positive numbers, hence we use Pin 0.00016 and 0.9999ø to estimate h = 0 and h = 1 cases, respectively.
Node features generation. In order to comprchensively evaluate the performances of different models, we assign each node with statistic features (Syn) or real-world contextual node features (Syn-Prod). For graphs with statistic node features, the feature values of nodes are sampled from 2D Gaussian (Abu-El- AAbu-El-Haija et al. 2019). The mean of Gaussian can be described in polar coordinates: each means has radius 300 and angle 2x (class id). The covariance matrix of each class is 3500 x diag[7, that is rotated by angle 2x (class id) For datasets with real-world contextual node features, we first establish a class mapping v : V + Vb between classes in the synthetic graph y to classes of existing benchmark graph V/. The only requirement for the target graph dataset is that the class size and node set size in the benchmark is larger than that of the synthetic graph, i.e., 311 S | and [V| S [V/b- In this paper, we adopt the large-scale benchmark, Ogbn-Products (Hu et al. 2020
6.2 Experimental Setup
Baseline methods. We compare our model against state-of-the-art graph neural networks and related node classification met hods for all da under fair sel peltings Specifically, MLP (Rosenblati 1961] is the baseline model that only utilises node attributes, while LINK (Zheleva & Getoor 2009) only utilises graph structure.
Mcanwhile, we also adopt general GNN models with undorlying homophily assumption: GCN <Kipf & Welling 2017), GAT (Velickovic al., 2018) and GCN2 (Chen et al.] 2020). Moreover, we adopt several models that are designed for heterophily graphs: Mixhop AAbu-El-Haijj et al. 2019), SuperGAT (Kim & Oh,
2021 GPRGNN (Chien et al., 2021), FAGCN (Bo et al.
2020) and CPGNN Zhu 2021). At last, two La-based models: LP (Zhu 2005 and C&SS (Huang et al.) 2021).
2021), H2GCN (Zhu et al.
ct al.
Implementation and splits. We follow the experimental setup of FAGCN and CPGNN with minor adjustments. Specifically, our experimental setup examines the semi-supervised node classification in the transductive setting. We consider three different choices for the random split into training/valle /et//vvvaaaitttteeeeeeeee settings, which we call sporse splittings (5%/5%%900). medium splitting (1%//10//80%) and dense split- respectively. The sparse splitting (5%/5%/90%% is similar to the original semi-
ting (18%/3%%/20%/ supervised setting in Kipf & Welling (2017), but we do not restrict each class to have the same number of training instances since it is the case closer to the real-world application. For fair comparison, we generate 10 fixed split. instances with different splitting and results are summarised after 10 runs with random seeds. Note that the Ogbn-Proteins dataset adopts its default splitting settings. Other model setups and hyperparameter settings can be found in Appendix E Our implementation available at https://github. htt.t//ww.coo//aiiggggggggggggga
6.3 Results on Real-world Graphs
Real-world graphs with heterophily. The performance of diverse methods on heterophily graphs under medium splitting is summarised in Tab. / top-2 performances of each graph are highlighted in colour. Ad- vanced GNN models that are designed for heterophily graphs generally perform better than GNNs designed
9

---

Published in Transactions on Machine Learning Research (10/2022)
Table 2: Summary of node classification results on heterophily graphs under medium splitting. $ indicates the results from Lim et al. (2021). Top-2 performances per benchmark are highlighted in and respectively.
Texas
Wiscousin
Actoe 0.22
Squievel 0.22
Chameloon 0.25
USA-A.
Bra.AA
Wildi
Coruell 0.50
Eu.AA
Tw.ENN 0.00
Tw-RU 0.639
O..Protcins
Raak
Hom..t
0.25
0.31
0.53
MLP
LINK
50
58.28.1.30
20,50
55,06araa
55.66usse
61.2
GON
56 Sa
47. 47.00v9.0
Ties
30.88 30.8
26 81
53 K1.15ea
55.511124
31.8bsa
18.9
72/0eual
GAT
54 12:3.2
46. 46.72.3.08
27 07777
0223000
36 16.0012:00
28 14
54 76.1
47.232::00
47.
05.181504
24.3421.1
36.9211.
55.060000
51 22
OUM!
12
GUN2
50 37
47.0324.0
14
05.505
36 29
36 g0
57 02:3
00 00.29pa
33.87ax.35
15.00
08.33
39.00
51. M8c 14
T4 14
Misdap
02.68.4404
18.1412.0
12.08
61 6L741139
51.504712
46.00.30
54.36.00
00.38
62. 1..5
GAp
88:2..4
45 28.56
30 40
5L
35.00 26.00:.36
97
83.232177
54,472177
24163:1.1
37.07a004
05.00:044
99 M4
00M
GPRGNS
22
11.8
ah.804415
31.0
02.344538
06.42amm
FAGCN
03:08.8.43
48.19
721121855
02.32:433
18.22-0
05.00as.s
00/06601
00.10.axe
B2GUN
05.67.404
20.011.
30.01117
14.2411.
70.574131
07.20u444
40.0..0
02.52
05:00.600
01.22-130
CPCNN
70000.124
30
28.7011:41
47.71314
20.21
70.15
05.041244
14.50.10
04,56u008
07.07.128
62.376444
00M
17.00
64,4204s
01.00aa4
D36
06
07.30
94g
83
71.49a117
07.01er
37.5050.
59-Mar14
ULP (Ours)
78
31 70
13 10
55.36
18.531110
T405a3
70.0644
38.8333
05.00a000
00.81x00
52 75
T3 73
with highhhoypphily assumption. MLP, which only utilises node features, achieves outstanding performances in several benchmarks. Our model, CLP, inherits the advantage of MI.P but also benefits from graph struc- ture, and it achieves outstanding and stable performance on all heterophily graphs. Moreover, many bascline methods lead to out-of-memory (OOM) issues on the large dataset, i.e., Ogbn-Proteins, but CL. avoids this problem, demonstrating its memory efficiency.
Real-world graphs with homophily. The performance of representative models on homophily graphs under medium splitting is summarised in Fig. f Inspired by [Huang et al.]
100
95
(2021), b we further adopt the spectral and diffusion features as additional node features to C&S and CLP and compare their performances with the best performance of SOTA GNN mod- els. C&St and CLPt refer to performance with additional node features and results from the figure demonstrates that CLP1 outperforms or matches the SOTA on homophily graphs.
90
Test Acauracy
85
80
75
70
SOTA C&S
CLP CLP
65
C&S!
6.4 Results on Synthetic Graphs
80
WikiCS
DELP
CS
ACM
Phyakss
Synthetic graphs without contextual node features. Most previous work (Kipf & Welling 2017 Bo et al., 2021 Zhu et al.] 2020) semi-supervised node classification has fo- cused only on graphs with contextual features on the nodes. However, the vast majority of graph data does not have node- level contextual features in practical applications, which sig- nificantly limits the utility of methods proposed in prior work.
Data
Figure 4: Performance comparison of C&SS and CLP with the best performance of GNN models (SOTA) on homophily graphs under medium splitting.
Besides, several components of our approach depend on node features. For instance, the compatibility matrix estimation (H) relies on the prior predictions which are learned from node features. H plays crucial role in the following T.P step. Therefore, it is natural to ask how CT.P performs over graphs without contextual node features compared with other competitive models?
To answer this question, we conduct extensive experiments on semi-supervised node classification with sparse, medium and dense splittings on three synthetic datasets with different average degrees. For instance, the Syn-1 datasct contains 11 graphs with from 0 to 1, and the average degrce per graph is sot to around 5 (4.95 to 5.02). Syn-2 and Syn-3 follow similar settings, but the average degree of each graph is set to 10 and 15, respectively.
We present the results of representative models of three synthetic datasets in Fig. (a. b, c). We observe similar trends in three figures: CLP has the best trend overall, outperforming SOTA methods in heterophily settings while matching with other SOTA methods in homophily settings. The performance of vanilla GCN and GCN2 increases with respect to the homophily level (h > 1). But, while synthetic graphs have no contextual node features, MLP is more accurate than them under strong heterophily (h th-+0 0). From Fig. 5 we can find that the classification accuracy of MT.P has been stable at about 45% relatively low level.
10

---

Published in Transactions on Machine Learning Research (10/2022)
CLP
1.0
1.0
H2GON
FAGON
Teat Acgurao
GPRGNN
Teot Accuraee
Test Actumcy
CLP
CLP
0.6
GCN
H2GON
H2GON
MLP
FAGON
FAGON
BPRGNN
GPRONN
BGN2
GON
GCN
(a) Syn-1, Label rate: 5%
(b) Syn-2, Label rate: 10%
(c) Syn-3, Label rate: 48%
Test Accurssy
Test Accuracy
Accurace
CLP
CLP
0.6
H26CN
H29CN
H2GCN
GPRGNN
GPRGNN
GPRGNN
0.5
GCN
BCN
0.4
GCN
MLP
MLP
MLP
0.0
0.2
04
0.6
0.8
1.0
0.0
0.2
0.4
0.8
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(d) Syn-Prod-1, Label rate: 5%
(e) Syn-Prod-2, Label rate: 10%
(I) Syn-Prod-3, Label rate: 48%
Figure 5: Classification accuracy of different methods with different label rates synthetic datasets. Only competitive results are presented duc to the space limit.
Yet, CLP still achieve the overall best performance. Overall, it indicates that approach works for graphs without contextual features.
Synthetic graphs with contextual node features. We perform extensive experiments on graphs with contextual features to further validate the performance of CLP under various settings.
Similar to the experiments on synthetic graphs without contextual node features, there are three synthetic graphs, ie., Syn-Prod-1, Syn-Prod-2 and Syn-Prod-3, which have the same graph structure as Syn-1, Syn-2 and Syn-3, but with contextual node features. Experimental results presented in Fig. (d, e, f). These figures emphasise that CLP is the best model for most heterophily cases (h + 1), which again confirms the effectiveness of our approach. It echoes the results of the real-world graphs (Tab. 2). Besides, GCN and GCN2, which were proposed with implicit homophily assumption, are significantly less accurate than MLP (near-flat performance curve as it is graph-agnostic) under strong heterophily (h < 0.4). Such evidence can be found in some cases for other helerophilous GNN models (H2GCN, FAGCN, GPRGNN). For instance, they perform significantly better than GCN but are outperformed by MLP on Syn- Prod-1 under h < 0.3 (Fig. 5d It reaffirms what we found in Sec. 4 i.c.
CLP
Aestracurary
0.8
0.5
0.0
0.2
0.4
0.6
0.8
1.0
Figure 6: Performance compari- son of CLP and CLP* on Syn-1 dataset with medium splitting. MLP could be a better choice for making classification for strong heterophily node groups. Our approach, CLP, can consistently achieve better performance than MLP in graphs with any heterophily levels and sparsity levels.
6.5 Additional Analysis
Comparison between two propagation schemes. In Sec. 5.3 we explained the design of our compatible LP process and discussed its advantages over prior work (Zhu al. 2020 The messages between two nodes are adaptively determined by nodes of both ends. Here, we perform extensive experiments to empirically compare the performance of LP steps with two propagation schemes. We choose one synthetic dataset with 11 graphs under various homophily (Syn-1) under the medium splitting. Other settings follow the common
11

---

Published in Transactions on Machine Learning Research (10/2022)
setup of CLP as described in Sec. 6.2
The approach that utilises Eq. 10 named CLP". Their performances 6 We observe that CL. has the better trend overall, outperforming CLP" in most heterophily settings (h S 0.9) and matching with CLP" in other settings.
are reported in Fig.
1.25
Brazil-Aimorts
Wiki
6.50s
Test Accuracy
90
Test Accuracy Wiki
1.00
4.81s
/ 8,075
80
Test Accuracy ACM
L2- 22-distance ACM
L2-distance Wiki
0.75
L2- (H.
Test Test Accuracy
0.408
0.44s
0.84s
Test Accuracy
60
6.03s
18.58s
40
0.50
0.778
70
0.25
H2GON CLP
20
M2GGN
5 10
Label rate (%)
48
2
logu(# Parameters)
4
8
11.5
logu Parameters)
12.0
Figure 7: Classification accuracy and L2- Figure 8: Classification accuracy and execution time of different distance ween estimated/ /ruee compati- methods with different layers on heterophily graphs. Execution bility matrix with different label rates. time is marked in the plot in terms of seconds (s).
Influence of label rate test accuracy and quality of compatibility matrix estimation. Another interesting question under semi-supervised learning to study is the influence of label rates. Fig. 7 presents the CLP's test accuracy and the quality of compatibility matrix estimation (H) with different splittings.
Specifically, the quality of H is evaluated by (H, fi) E (I)), -fil) It is not surprising
to find that higher label rates lead better performance and more accurate compatibility matrix estimation. Therefore, one of the future directions is learn better compatibility matrix estimation according to prior predictions and graph structure.
The number of parameters and execution time comparison. Our approach often requires dignificanlly fewer parameters than GNN models since only the base predictor has parameters to train, which is less than GNN models. Moreover, another gain faster training time because we do not use the graph structure for our prior predictions, and the LP step time-efficient [Gatterbauer] 2014 Gatterbauer et al. 2015). As an example, we plot the number of parameters vs test accuracy of CLP and H2GCN of two heterophily graphs, i.e. Brazil-Airports and Wisconsin, in Fig. g Note that H2GCN similarly contains an MLP component as a node feature encoder. We endow CLP and H2GCN with Linear, 2-layers and 3-layers MLP models base predictors (feature encoder for H2GCN). The hidden dimensions of CLP and H2GCN are the same as the general settings. Each model's execution time (average value of 10 runs) under different settings is shown in Fig. g We observe that CLP achieves much better performance with orders of magnitude fewer parameters and execution time.
7 Conclusion
In this paper, we focused on the graph learning tasks with challenging heterophily settings. Motivated by an experimental investigation of existing models' performance, we proposed an approach that extends LP algorithm to heterophily settings by smoothing the prior predictions across ncighbours weighted by the compatibility matrix. A theoretical analysis shows that CL.P has closed-form solution with mild conditions on an appropriate matrix and we can thus give a detailed explanation of when CLP will support convergence. Comprehensive experiments demonstrate the effectiveness and efficiency of our approach on real-world and synthetic graphs with different settings. In future work, we plan to investigate a better compatibility matrix estimation approach and generalise CLP to the heterophily setting of regression problems on graphs.
Acknowledgments
This work is supported by the Luxembourg PRIDEIS5/16616667/PPPPP
National
Research
Fund
through
grant
12

---

Published in Transactions on Machine Learning Research (10/2022)
References
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Stoeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 2019 International Conference on Machine Learning (ICML), pp. 21 29. JMLR, 2019.
Waiss Azizian and Marc Lelarge. Characterizing the expressive power of invariant and equivariant graph neural networks. CoRR, abs/ (b8/2006. 15646, 2020.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Sanzaez-Gonzalez, Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülgehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/ htt//1806002260 2018.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convo- lutional networks. In Proceedings of the 2021 AAAI Conference on Artificial Intelligence (AAAI), pp. AAAT, 2021.
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Velickovie. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. CoRR, abs/2104.13478, 2021.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In Proceedings of the 2020 International Conference Machine Learning (ICML). JMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In Proceedings of the 2021 International Conference on Learning Representations (ICLR), 2021.
Simon S. Du, Kangcheng Hou, Ruslan Salakhutdinov, Barnabás Póczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Proceedings of the 2019 Annual Conference on Neural Information Processing Systems (NeurIPS). NeurIPS, 2019.
Dhivya Eswaran, Stephan Günnemann, Christos Faloutsos, Disha Makhija, and Mohit Kumar. Zoobp: Belief propagation for heterogeneous networks. Proc. VLDB Endow., 10(5):625 636, 2017.
Wolfgang Gatterbauer. Semi-supervised learning with heterophily. CoRR, abs/ 1b1/1412,3100, 2014.
Wolfgang Gatterbauer. The linearization of belief propagation on pairwise markov random fields. In Pro- ceedingg of the 2017 AAAI Conference Artificial Intelligence (AAAT), pp. 3747 3753. AAAI, 2017.
Wolfgang Gatterbauer, Stephan Günnemann, Danai Koutra, and Christos Faloutsos. Linearized and single- pass belief propagation. Proc. VLDB Endow., 8(5):581-599) 2015.
S. R. Searle H. V. Henderson. The vec-permutation matrix, the vec operator and kronecker products: A review. Lineor and maltilinear algebra, 9(4):271-22) -288, 1981.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. In Proceedings of the 2020 Annual Conference on Neural Information Processing Systems (NeurIPS). NeurIPS, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R. Benson. Combining label propaga- tion and simple models out-performs graph neural networks. In Proceedings of the 2021 International Conference on Learning Represenlations (ICLR), 2021.
Sergei Ivanov and Lindmila Prokhorenkova. Boost then convolve: Gradient boosting meets graph neural networks. In Proceedings of the 2021 International Conference Learning Representations (ICLR), 2021.
13

---

Published in Transactions on Machine Learning Research (10/2022)
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self- supervision. In Proceedings of the 2021 International Conference on Learning Representations (TCLR), 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. Tn
Proceedings of the 2017 International Conference on Learning Representations (ICLR), 2017.
Danai Koutra, Tai-You Ke, U Kang, Duen Horng Chau, Hsing-Kuo Kenneth Pao, and Christos Faloutsos. Unifying guill-by-association approaches: Theorems and fast algorithms. In Machine Learning and Knowl- edge Discovery in Databases- Europeon Conference (ECMLPKDD), volume 6912, pp. 437-452 Springer, 2011.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding design provably more powerful graph neural networks for structural representation learning. In Proceedings of the 2020 Annual Conference Neural Information Processing Systems (NeurIPS). NeurIPS, 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In Proceedings of the 2018 AAAI Conference on Artificial Intelligence (AAAI), pp. 3538 3545. AAAT, 2018.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In Proceedings of the 2021 Annual Conference on Neural Information Processing Systems (NeurIPS). NeurIPS, 2021.
Péter Mernyei and Catalina Cangea. Wiki-cs: wikipedia-based benchmark for graph neural networks. CoRR, abs/2007.02901, 2020.
Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering GCN: overcoming oversmoothness in graph con- volutional networks. In Proceedings of the 2020 Annual Conference on Neural Information Processing Systems (NeurIPS). NeurIPS, 2020.
Krishna Kumar P., Paul Langton, and Wolfgang Gatterbauer. Factorized graph representations for semi- supervised learning from sparse data. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 1383 1398. ACM, 2020.
Leto Peel. Graph-based semi-supervised learning for relational networks. In Proceedings of the 2017 SIAM International Conference on Dala Mining, pp. 335-443. SIAM, 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In Proceedings of the 2020 International Conference on Learning Represenialions (ICLR), 2020.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word repre- sentation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1532-1543. ACL, 2014.
Frank Rosenblatt. Principles of neurodynamies. perceptrons and the theory of brain mechanisms. Technical report, Cornell Aeronautical Lab Inc Buffalo NY, 1961.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael M. Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. CoRR, abs/2004.11198, 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding, Journal of Complez Networks, (2), 2021.
Yousef Saad. Ieerulive methods for sparse linear systems. SIAM, 1981.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. CoRR, bbs//111..555 2018.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Richard Sinkhorn and Paul Knopp. Concerning nonnegative matrices and doubly stochastic matrices. Pacific Journal of Mathemalics, (1)333443 348, 1967.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceed- ings of the 2009 ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 807-816. ACM, 2009.
Yu Tian, Long Zhao, Xi Peng, and Dimitris N. Metaxas. Rethinking kernel methods for node representation learning on graphs. In Proceedings of the 2019 Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 11681-11692. NewrPPS, 2019.
Petar Velickovie, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proceedings of the 2018 International Conference on Learning Representa- tions (ICLR), 2018.
Hongwei Wang and Jure Leskovec. Unilying graph convolutional neural networks and label propagation. abs/ 0bs/2002.06700 2020.
Eric W Weisstein. Gershgorin circle theorem. https://mathwurid. wolfram. com/, 2003.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1): 4 4-24, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the 2019 International Conference on Machine Learning (ICML). JMLR, 2019.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. abs/2102.06462, 2021.
Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. Network representation learn- ing with rich text information. In Proceedings of the 2015 International Joint Conferences on Artifical Intelligence (IJCAI), pp. 2111-2117. IJCAI, 2015.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey, IEEE Transactions on Knowledge and Data Engineering, 2020.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. In Proceedings of the 2020 International Conference on Learning Representations (ICLR), 2020.
Elena Zheleva and Lise Getoor. To join or not join: the illusion of privacy social networks with mixed public and private user profiles. In Proceedings of the 2009 International Conference on World Wide Web (WWW), pp. 531-540. ACM, 2009.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Yu Philip S. Graph neural networks for graphs with heterophily: A survey. CoRR, abs/2202.07082, 2022.
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Beruhard Schölkopf. Learning with local and global consistency. In Proceedings of the 2003 Annual Conference on Neural Information Processing Systems (NIPS), pp. 321-328 NIPS, 2003.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Proceedings of the 2020 Annual Conference Neural Information Processing Systems (NewrIPS). NeurIPS, 2020.
Jiong Zhu, Ryan A. Rossi, Anup B. Rao, Tung Mai, Nodim Lipka, Nesroen K. Ahmod, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the 2021 AAAI Conference on Artificial Intel- ligence (AAAI), pp. 11168-11176. AAAI, 2021.
Xiaojin Zhu. semi-supprvised learning literature survey. Technical report, University of Wisconsin-Madiss Department of Computer Sciences, 2005.
15


Reviews:
[{"review_id": "JIHMVXrUvr", "reviewer": "Reviewer_5knR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n* A simple and efficient graph learning approach in heterophily settings. \n* The find-grained analysis of performance on nodes with different local homophily levels is interesting and maybe inspiring.\n* Seemingly good experimental performance with fast execution speed. \n\nWeakness:\n\n* Clarity. The definition of compatibility matrix in Equation (2) does not have enough explanation, and lacks of connection with Section 5.2.\n\n* Notations. In (6), \\hat{H} is derived from \\hat{B}; in (7) F is derived from \\hat{B} and \\hat{H}; and then in (8) \\{B} is further derived from \\{F}? The notations are quite confusing here. I suppose the authors mean \\hat{B}^0 in (6) and (7). If so, is A^F changed per layer, or computed only from the initial prediction and then fixed for all layers? \n\n* Experiments. It is good to have three different split settings which may help explain the advantage of proposed methods in a certain setting. However, the experiments do not show clear performance difference in difference split settings in the synthetic data; while on real-world graphs, they even only use the medium setting, which is different from all previous papers. In my opinion, on real-world graphs they should either use the same setting as previous papers, or show results on all three different split settings. Otherwise, it is a little astonishing to see so many SOTA methods perform so badly compared to MLP, especially considering that they perform much better in their original split setting.\n\n* What if we do not use a base network to learn the compatibility matrix H but only use the known ground truth labels (in the training part) to get it? This ablation study may be beneficial to show the advantage of learning the compatibility matrix.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The combination of label propagation and a simple shallow neural network can be used as an alternative of graph neural networks and achieve comparable performance on graphs with high homophily. However, it fails on heterophilous graphs. This paper generalizes LP algorithm to solve the heterophily issue by learning the class compatibility matrix and aggregating label predictions with LP algorithm weighted by the class compatibilities. It is demonstrated faster and performs well on graphs with various homophily levels.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Weakness 1-3. ", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ycCNcg0K2H", "reviewer": "Reviewer_xGNs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n- Presentation is good.\n- Proposed method is easy to implement.\n- Claims are supported by extensive experiments.\n\nWeaknesses\n\n- Theoretical statements are seemingly mathematically invalid.\n\n\nSoundness\n\n- This paper claimed that in semi-supervised transductive learning on graphs, existing GNNs did not perform well on nodes with high local heterophily. Experiments in Section 4 empirically verified this claim.\n- If I understand correctly, some mathematical statements appear to be invalid. Specifically, the Kronecker product $P\\otimes Q$ is defined for the matrices $P$ and $Q$. However, since $A^F$ is an order-3 tensor, $I \\otimes A^F$ in Proposition 1 eq. (8) is inconsistent.\n- This paper claimed the following three points in the empirical aspect of the proposed method:\n  - Good overall performance on various heterophily graphs.\n  - Good accuracy on nodes with high local heterophily.\n  - Efficient in terms of computational complexity and number of parameters.\nThese claims are numerically verified by experiments.\n\nRelevance\n\nThe problem of performance degradation found in Section 4 is a critical issue of GNNs that few papers have addressed. Therefore, developing methods for solving it is a relevant topic for the TMLR community.\n\nNovelty\n\nAs pointed out in this paper, existing studies such as Zhu et al. (2020) proposed models that utilized compatibility matrices. This paper explained the difference between proposed and existing methods in, e.g., Section 5.3. In addition, this paper numerically verified the effectiveness of the difference. Therefore, this paper has novelty and significance from this viewpoint.\n\nClarity\n\n- The overall organization of the paper is good. Therefore, I can understand the paper without much difficulty.\n- The introduction explained the line of research about heterophily GNNs and LP-based GNNs well and appropriately led us to the motivation of the proposed method. \n- The explanation of the proposed method's ideas and methodology is good.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a new Graph Neural Network (GNN) using Label Propagation (LP) that was effective for prediction tasks on graphs with various heterophily.\nFirst, this paper pointed out that existing GNNs did not have good prediction accuracies on nodes with high local heterophily, even though they were designed for high heterophily graphs.\nBased on this finding, this paper proposed a new GNN model, Compatible Label Propagation (CLP). CLP estimated the compatibility matrix using node features and predicted node labels using compatible label propagation.\nThis paper applied CLP to semi-supervised node prediction tasks on the synthesis and real graphs and verified its effectiveness in terms of accuracy and implementation merits.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "If I understand correctly, the statement of Proposition 1 looks invalid. Therefore, I suggest re-examining it.", "broader_impact_concerns": "This paper does not have a Broader Impact Statement. I did not find any ethical concerns that would require a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3bpkpINoyl", "reviewer": "Reviewer_moVS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n1. The algorithm design part is reasonable, i.e., by adding compatibility into LP, though there are some issues on the motivation and analysis (in the Weaknesses).\n2. The empirical results compare the latest LP and GNNs for heterophily.\n\n## Weaknesses:\n1. [The motivation example is confusing.] As mentioned by the authors, this compatibility measure was first introduced in a GNN work (the authors should fix the citations in Sec 2, as will be explained in Requested Changes). Later authors conduct an empirical study as a motivation to show that MLP is better than GNN in the low homophily ratio case. However, there seem to have several main issues on the logic here.\na. LP is not compared or discussed in Sec 4.\nb. Now the conclusion the authors present is: because MLP is better than GNN (using compatibility)  in the low homophily case, we should  consider handling heterophily in LP (in the next section).\nc. However, what I expect after reading Sec 4 is that, recent GNN models designed for heterophilous graphs do not outperform MLP in the low homophily case, so we should improve/design other GNNs that can avoid this.\nd. Thus, combining the above three points, I don’t think the toy example is suitable here. Authors can consider adding more explanations or replacing it with another motivation example.\n\n2. Later authors design an algorithm called CLP. It combines compatibility into LP. I have following questions here.\na. Why recent GNNs based on compatibility matrix can fail in this case, while LP with compatibility can work? The authors imply in Sec 4 that these recent GNNs may capture global information, but why this won’t happen for LP with compatibility (CLP)? Namely, both (GNN and LP) are using compatibility, why LP is better than GNN in capturing the “local” information? This is like the most fundamental question in this work; otherwise, this core idea of this paper is like: we empirically try LP with compatibility, and we observe that it works better than GNN with compatibility.\nb. The authors cover some analysis on the CLP to prove its convergence. This is great. Just about the connection to question a, are authors implying that GNNs with compatibility fail to converge and CLP can achieve this? If so, authors can explicitly claim and prove it (or refer to existing work). I haven’t seen any theories on GNNs fail to converge in this case, so feel free to add the citations if authors have them in mind.\nc. Besides, the analysis also provides the efficiency guarantee. The efficiency is only briefly discussed in Sec 6 (in OOM), which is not of the key focus of the current draft. If authors want to highlight the efficiency of CLP, then more experimental analysis is required. Otherwise, may consider moving the efficiency analysis to appendix.\nd. I think the authors can consider adding more analysis on question a. The efficiency in the current draft does not seem to be the main focus, and authors may consider leaving more space for the more fundamental question.\n\n3. The key recent GNNs are not sufficiently discussed in Sec 2, like GPRGNN, FAGCN, H2GCN.\n\n4. The writing of this paper can be further improved. See minor points in Requested Changes.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the effect of label propagation (LP) for transductive setting. It starts with the definition of homophily using homophily ratio. Then authors synthesize datasets with various homophily ratios and test MLP and GNNs on it. An empirical example illustrates that MLP is better in the lower homophily ratio case. Then motivated by this, authors design an LP algorithm by considering the compatibility. The empirical results can verify the effectiveness of CLP.\n", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Some minor points:\n1. In abstract, it seems that the following two sentences are redundant: “On a wide variety of benchmarks, …” and “Empirical evaluations demonstrate that …”. Can authors double-check this?\n2. Authors can change the citation format (e.g., by modifying the natbib or link color). The current format is not friendly to readers.\n3. In Sec 1, authors discussed the motivation, from homogeneous graph to heterogeneous graph. It would be better to movr the definition (i.e. the homophily ratio) in advance.\n4. The CLP composes of three steps, yet there are existing works adopt the same pipeline, e.g. [1]. The main difference is on step (2): [1] calculates uncertainty for correction, and this work proposes a compatibility matrix for correction; the other two steps (base prediction and label smoothing) are the same. Authors may as well give credit to [1] at this place. Now authors only mention “steps 1 and 3 have been tried independently …”\n5. The definition of homophily ratio of individual node (Eq 3) can be merged into Definition 1.\n6. Some citations are wrong. For example, the citations for CPGNN are different in several places in the paper. Besides, the citation [2] in Sec 2 is H2GCN, not CPGNN. The authors should carefully check it.\n7. According to the discussion in Sec 2 on the difference between H2GCN, authors should add it in Fig 1.\n\n\n[1] Huang, Qian, et al. \"Combining label propagation and simple models out-performs graph neural networks.\" arXiv preprint arXiv:2010.13993 (2020).\n[2] Zhu, Jiong, et al. \"Beyond homophily in graph neural networks: Current limitations and effective designs.\" Advances in Neural Information Processing Systems 33 (2020): 7793-7804.\n", "broader_impact_concerns": "Not applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "2ATfhpdkSm", "reviewer": "Reviewer_3KmR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The method sounds to be new for node classification over heterophilic networks.\n\n2. The empirical performance looks good. \n\nWeakness:\n1. Although the method is new, the idea is not completely novel. It combines previous works, the C&S framework for homophilic networks [1] plus compatibility matrix-based node classification over heterophilic networks [2,3].\n\n2. The method is ad-hoc. Previous work [2] gets the compatibility matrix-based node classification from belief propagation, while this work designs all components in a heuristic way, especially the design of the weighted adjacency matrix (Eq.(7)) /\n \n3. Real dataset evaluation misses other splitting settings and only presents the medium splitting case.\n\n4. The convergence analysis in 5.4 seems trivial to me, which is a standard result to analyze linear iterations.\n\n[1] Combining Label Propagation and Simple Models Out-performs Graph Neural Networks. ICLR 2021\n[2] Linearized and Single-Pass Belief Propagation. VLDB 2017\n[3] Graph Neural Networks with Heterophily. AAAI 2021", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes a new method to perform node classification over heterophilic networks. The new method first uses features on each node with the label to train a simple model to predict the label. Then, use this model to predict pseudo labels of the rest nodes in the graph.  Further, use pseudo labels to estimate the compatibility matrix which is essentially the weight for the message passing to neighbors in different classes. Finally, combine pseudo labels with the compatibility matrix to perform a Pagerank-type diffusion to get the final prediction. Experiments on real and synthetic datasets demonstrate the good performance of the method. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. The results of real data experiments in all splitting settings should be provided. \n\n2. Citation format is improper. Use \\citep instead of \\cite to add parentheses: e.g. xxx (Huang et al. 2021).\n\n3. Consider doing extensive experiments on synthetic CSBMs as suggested in [1]. \n\n\n[1]  Adaptive Universal Generalized PageRank Graph Neural Network. ICLR 2021", "broader_impact_concerns": "I did not see any concerns about the ethical side of this work. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel semi-supervised node classification method, called compatible label propagation (CLP).  The method first trains MLP on the training nodes based only on the node features, and computes the compatibility matrix by using the MLP predictions for the unlabelled nodes.  Then, label propagation is performed with the affinity matrix modified based on the compatibility matrix.

The proposed method is well-motivated, and shows SOTA performance.  Reviewers raised several major concerns on clarity, mathematical correctness, insufficient experiments, etc.  The authors have addressed most of the concerns and revised the paper accordingly.
Only the criticism on the limited novelty or technical contributions remains.  However, the difference from the existing methods is clearly described and marginal novelty cannot be the main reason for rejection according to the policy of TMLR.

Thanks to the reviewers' constructive comments and the authors' additional effort, the revised version is already in good shape except many minor flaws.  I only went through the revision quickly and didn't carefully check all the equations and sentences, but still I found a bunch of flaws.  I strongly recommend several authors (if this is a single author paper, ask two senior colleagues to proof-read) to check the whole manuscript and appendix very carefully.  The following are what I found.  I expect the authors will find much more flaws, all of which must be fixed before publication.

- Below Eq.(4), it is written \hat{D} = D^{(l)}, which is wrong.  It should read \hat{D} = Softmax(D^{(L)}), where l=L is the last layer.
- Above Eq.(5), "unknown nodes (V - T_V + T^v_V)".  Because each term is a set, set operators should be used: (V \setminus (T_V \setminus T^v_V)) or ((V \setminus T_V) \union T^v_V)).
- Below Eq.(8), What \| (double vertical lines) in \|_{k \in |Y|} means?  It's not defined.  Also, |Y| is the number of elements in the set Y, so k \in |Y| doesn't make sense.
- In Eq.(9), l is used for iteration counter, but it was used for the layer id in Eq.(4).  Use another character.
- Below Proposition 2, I don't understand what you mean by "Hence, one can use Frobenius or 1-induced norm to obtain sufficient convergence guarantees faster."?  Probably you should say "Hence, one can use Frobenius or 1-induced norm to efficiently check if the sufficient condition for convergence is satisfied."  Also, in "In our experiments, we found that CLP converges efficiently for all datasets." I don't understand what "efficient convergence" means.  Is there "inefficient convergence"?
- You can use Proposition 2 to bound the hyperparameter alpha for convergence guarantee.  Did you do this?  It's better to mention how you used Proposition 2 for your implementation.
- In the last paragraph of Section 5, "F is a function that guarantees that each message is a probability distribution."  I don't think this sentence defines F uniquely.  Can F be a constant distribution ignoring the argument?
- In Section 6.2, "We consider four different choices for ..." but I see only "sparse", "medium", and "dense".  What is the other one?  
- In the same paragraph "in (Kipt & Welling, 2017)" should read "in Kipt & Welling, 2017" (use \citet here).
- In Table 2, what the green and purple highlightings mean (should be explained in the caption)?  Also better to apply statistical tests, e.g., Wilcoxon signed-rank test, and highlight the methods which are not significantly worse than the best method.  The same highlightings should be applied to Tables 4 and 5 in Appendix.


Minor requests (not mandatory but recommended):

- The CLP result should be included in Figure 1 already, and you can mention in Section 4 how good the proposed method is.  I suppose CLP behaves similarly to in Figure 5 but it's better to show real data results.  Also showing that the proposed CLP outperforms the other methods at this point will better motivate readers to read the subsequent sections.  

- The proposed algorithm computes \hat{H} only once.  I'm curious what happens if you update \hat{H} after you get a better label prediction by LP than the prior prediction by MLP.  What happens if you iterate this process until convergence?  Possibilities are (1) the performance is degraded and it performs as other GNN approaches, (2) performance doesn't change much, or (3) performance improves.  I recommend the authors to investigate this point.  If the results are (1) or (2), it would be nice to give a single sentence explaining what happened.  If (3), it's nice to include the results in the paper with further improved performance.

- I'd say "the number of parameters" instead of "parameter number".

- I'd say "existing methods", "SOTA methods", "baseline methods", instead of "Competing methods"

Decision: Accept (poster)