ProtoGNN: Prototype-Assisted Message Passing Framework for Non-Homophilous Graphs
Authors: Yanfei Dong
Mohammed Haroon Dupty
Lambert Deng
Yong Liang Goh
Wee Sun Lee
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Neural Networks
Graph representation learning
Non-homophilous Graph
Heterophily
Non-homophily
Node Classification

Abstract: Many well-known Graph Neural Network (GNN) models assume the underlying graphs are homophilous, where nodes share similar features and labels with their neighbours. They rely on message passing that iteratively aggregates neighbour's features and often suffer performance degradation on non-homophilous graphs where useful information is hardly available in the local neighbourhood. In addition, earlier studies show that in some cases GNNs are even outperformed by Multi-Layer Perceptron, indicating insufficient exploitation of node feature information. Motivated by the two limitations, we propose ProtoGNN, a novel message passing framework that augments existing GNNs by effectively combining node features with structural information. ProtoGNN learns multiple class prototypes for each class from raw node features with the slot-attention mechanism. These prototype representations are then transferred onto the structural node features with explicit message passing to all non-training nodes irrespective of distance. This form of message passing, from training nodes to class prototypes to non-training nodes, also serves as a shortcut that bypasses local graph neighbourhoods and captures global information. ProtoGNN is a generic framework which can be applied onto any of the existing GNN backbones to improve node representations when node features are strong and local graph information is scarce. We demonstrate through extensive experiments that ProtoGNN brings performance improvement to various GNN backbones and achieves state-of-the-art on several non-homophilous datasets.

Under review as a conference paper at ICLR 2023
PROTOGNN: PROTOTYPE-ASSISTED MESSAGE PASS- ING FRAMEWORK FOR NON-HOMOPHILOUS GRAPHS
Anonymous authors
Paper under double-blind review
ABSTRACT
Many well-known Graph Neural Network (GNN) models assume the underlying graphs are homophilous, where nodes share similar features and labels with their neighbours. They rely on message passing that iteratively aggregates neighbour's features and often suffer performance degradation on non-homophilous graphs where useful information is hardly available in the local neighbourhood. In ad- dition, earlier studies show that in some cases, GNNs are even outperformed by Multi-Layer Perceptron, indicating insufficient exploitation of node feature informa- tion. Motivated by these two limitations, we propose ProtoGNN, a novel message passing framework that augments existing GNNs by effectively combining node features with structural information. ProtoGNN learns multiple class prototypes for each class from node features with the slot-attention mechanism. These prototype representations are then transferred onto the structural node features with explicit message passing all non- training nodes irrespective of distance. This form of message passing, from training nodes to class prototypes to non-training nodes, also serves as a shorteut that bypasses local graph neighbourhoods and cap- tures global information. ProtoGNN is generic framework which can be applied onto any of the existing GNN backbones to improve node representations when node features are strong and local graph information is scarce. We demonstrate through extensive experiments that ProtoGNN brings performance improvement various GNN backbones and achieves state-of-the- ofrt---rr--rttttt performance on several non-homophilous datasets.
INTRODUCTION
Graph Neural Networks (GNNs) have emerged as prominent models for learning representations on graph-structured data. GNNs iteratively update the node embeddings based the node features of its own and its local neighbors on the graph (Kipf & Welling 2016; Defferrard et al. 2016 Gilmer et al. (017). This form of iterative message passing provides strong structural inductive bias that assumes the presence of useful information in local neighborhoods. This assumption holds true for homophilous graphs whose connected nodes tend to share similar features and labels. However, many real-world graphs are structured in heterophilous way wherein nodes tend to be dissimilar with their local neighbors. Such homohooop graphs can be found in domains of fraud detection (Shi et al.
2022
Pandit et al. 2007), molecular biology (Ye et al. 2022 and certain social networks (Lim et al.
2021
Recent studies show that many GNNs (e.g. GCN (Kipf & Welling 2016)) fail to learn well on non- homophilous graphs (Zhu et al., 20206 202T), and are even outperformed by simple architectures such as Multi-Layer Perceptron (MLP) that ignore graph structures and only leverage node features. This indicates two limitations of these GNNs. First, information of node features is not sufficiently exploited and might be diluted by iterative message passing. Second, the prevailing structural inductive bias that utilizes local neighbourhood information may not be helpful on non-hoooppilous graphs, since useful information is often scarce within the local neighbourhood.
Therefore, it is essential to go beyond the local neighborhood for useful information. Existing works either explicitly capture multi-hop information (Zhu et al. (020bb try to leverage globally available correlations with distant nodes (Suresh et al.) 2021 Li et al. However, such methods often
go beyond the linear complexity of GNN message passing (Suresh et al., 2021). More importantly,

---

Under review as a conference paper at ICLR 2023
30
Penn94
Twitch Gamers
(a)
(b)
(a) Visualization of features for Penn94 and Twitch Gamers datasets. The plots show clustering patterns of the nodes in the feature space. (b) Illustration of information transfer from training nodes to prototypes. Yellow and blue represent different classes. The prototype nodes learn multiple representations per class from the training nodes and transfer the information to non-training nodes through attention.
Figure 1:
since relevant information is often scattered within the vast amount distant nodes, identifying and extracting such information is challenging task.
To address the two limitations, we draw inspiration from prototypical networks (Snell et al. 2017) (017). an efficient and effective paradigm that constructs single representation for each class called a prototype to assist learning in data-scarce settings. Learning node representations on graph structures using class prototypes can facilitate information flow from distant nodes and capture global correlations efficiently. We observe that in many datasets, nodes from the same class form multiple clusters (see Fig. a.). If we use a single prototype for each class, the prototype representation would be inaccurate or insufficient. For example, the single prototype may learn to represent the average of different clusters. Alternatively, the single prototype may learn to represent one of the dominant clusters in the feature space, therefore failing to capture information of the remaining clusters. Hence using a single prototype for each class may lead to suboptimal performance.
In this work, we propose ProtoGNN, novel message- message-passing passing framework that augments existing GNNs and overcomes two limitations of GNNs on heterophilous graphs by facilitating efficient information transfer from distant nodes. In ProtoGNN, information from the graph in the form of node feature view and structure view. With the node features of the training nodes, we construct multiple prototypes from each class independent of graph structure by adapting the mechanism of slot-attention (Locatello et al. 2020). These class prototypes are learnt from the node feature space via multiple rounds of attention. It provides an effective way of soft-clustering the node features as well as the needed model capacity for learning different clusters within the same class. Alternatively, this process can also be viewed as message passing from training nodes to prototype nodes as illustrated in Fig. [b). The learned prototype representations are then transferred onto all node representations from the structure view to make them more discriminative.
first disentangle the two sources of
To enhance the effectiveness of ProtoGNN, we design two regularizers. To exploit the presence of the feature and structure views for regularization, we enforce cross-view compatibility between the prototypes (feature view) and node embeddings (structure view) through hierarchical compatibility function which handles the presence of multiple prototypes within each class. To further exploit the full power of prototypes, regularize them so that they are distinct from each other by encouraging the prototypes to be orthogonal to each other through an orthogonality loss.
The learning of prototypes introduces artificial edges from training nodes of each class all non- training nodes via prototype nodes. This serves as shortcut in message passing which bypasses local graph neighbourhoods and captures global information, while maintaining the linear complexity with respect to the backbone GNNs. Additionally, since the prototypes are learnt from node feature space, it preserves strong feature information that might be diluted by traditional message passing.
Overall, ProtoGNN is a generic framework which presents the following advantages: (1) It is orthogonal to existing GNN backbones and can be applied onto any of them improve node representations in heterophilous graphs. (2) It is efficient and can capture global node correlations with only Onn) additional edges. (3) It can be useful in graphs where distant information is helpful and node feature information is strong, even in homophilous settings when label rate is low. (4) It preserves the node features from dilution due to message passing. We conduct extensive experiments
2

---

Under review as a conference paper at ICLR 2023
on several non-homophilous datasets which show consistent improvement various backbone GNN models, achieving state-of-the-an performance in multiple instances.
RELATED WORKS
GNN models like GCN (Kipf & Welling 2016) and GAT (Veličković et al. 2017) have performed profoundly well on graph-structured data in a multitude of domains. However, GCN-like models have an intrinsic assumption of homophily on graphs, and it has been noted by multiple works that they perform poorly on heterophilous graphs (Pei et al., 2020 Zhu et al., 2020b). Farly works tried to address this issue either through multi-hop neighbourhood aggregation or building auxiliary graph structures based on node and structural features. Since then, various ways have been proposed to make GNNs work better on non-homophilous graphs (Bo al. 202T; Yan al. 2021 Chien et al. 2020; Dong et al.
2021; Suresh et al.) 2021 Yang et al. 2021 Lim et al. [02]] Luan et al. 2021 I Zhu 2020al Liu et al. (021). Some of these methods leverage global information by letting the
model choose either proximity or structural information or both for prediction (Suresh et al. 202 ),
while other methods like GGCN (Yan et al. 202T) address this by introducing signed messages the
propagation scheme based on over-smoothing effect observed in GCN-like models.
More recently, LINKX (Zhu et al., 202I) showed that a simple MLP applied on node features and adjacency matrix can perform well many heterophilous graph datasets. In addition, GloGNN (Li ct al. 2022) showed substantial improvements when further global information is captured. However, despite introducing
efficient approach to do this, it can take quadratic runtime when the graph is dense. In this work, we capture relevant information from distant nodes, which is often scattered within the graph structure. Identifying and extracting such information challenging task. Inspired by prototypical networks (Snell et al. 2017). we construct class prototypes to enable efficient information transfer from distant nodes with linear complexity. Furthermore, with the observation that node features occur in several clusters in heterophilous graphs, we learn multiple prototypes for each class with an adapted form of slot-attention (Locatello al., 2020). There are also a few works that use prototype-basee
learning in graphs. One uses prototypes to make the predictions more explainable (Zhang et al. 2022) while another considers few-shot setting (Ding et al., 2020). However, they do not integrate prototype learning with backbone GNNs, use multiple prototypes per class or consider heterophilous graphs. Very recently, Xu et al. (2022) proposed using memory units to capture global patterns in the graph. However, unlike Xu et al. (2022), train multiple prototypes per class and are inductively-biit biased with slot attention mechanism to capture node clusters.
PRELIMINARIES
Notations. Let (V, represent undirected graph, where V == {er H is the set of nodes and & CVV V is the set of edges on the graph. A denotes the adjacency matrix of the graph, where Ai represents the edge eaj between nodes v; and by. X represents the feature matrix of nodes, where X; is the features of node i, and Xtrain and Nonttaii are the feature matrices for all the training and non-training nodes, respectively. Y denotes the node class labels, and y, is the label for node 2i.
Homophily and heterophily Homophily refers to the degree of similarity between connected neighboring nodes in terms of their features labels. There are many types of homophily measures proposed, including edge homophily (Zhu et all 2020b), node homophily (Pei et al., 2020), and class insensitive homophily (Lim al., 2021). In this work, we the homophily matrix proposed in [im et al. (2021). since it can better reflect class-wise homophily. The homophiliy matrix is defined as:
[u, v) E E Cu C12 Co =====00 0zl
Har.0
[u, v) :
for classes ej and C22 Harey denotes the proportion of edges between from nodes of class oj to nodes of class 02 A homophilous graph has high values the diagonal entries.
4 PROTOGNN
With the aim of capturing scattered but useful information from distant nodes without diluting the strong node features, propose ProtoGNN, which learns the node representations by decoupling
3

---

Under review as a conference paper at ICLR 2023
Feature View
Node Multi-Prototype Leaming
MLP
Structure View
Information Fusion
GNN
Attention
V
H
AGG
Figure 2: Overall architecture of ProtoGNN: ProtoGNN disentangles the input graph into two views, one considering only node features i.c. feature view, the other considering both graph structure and node features i.c. the structure view. In the feature view, ProtoGNN learns multiple prototype representations for each class from the node features.
structure view, a backbone GNN generates node embeddings with the assistance of information from the feature view. After each GNN layer, generated node embeddings could be augmented by attending to prototypes. The whole pipeline is trained with a combination of three loss functions.
the feature view and the structural view from the graph and fusing them to produce effective representations. ProtoGNN can be broken down into the following key components: (1) feature view which involves learning multiple prototype representations for each class from only node features, (2) structure view that consists of any GNN model, (3) information fusion which combines information from the two views via the attention mechanism. The whole pipeline is trained with three loss functions. In the following, we discuss the three stages in details.
Feature View: In order to fully exploit the node features and be able to transfer information to distant nodes, we learn prototype representations of each class without the structural inductive bias. This forms the feature view of the graph, wherein nodes are clustered in feature space irrespective of their topological affinities. The prototype features then be used to transfer information onto the structural representations for the model to learn the most effective embeddings adaptively.
In real-world graphs, we observe that the feature distribution for each class of nodes is usually multi-modal, as illustrated by the feature space visualization in Fig. Fig. Ta). Using a single prototype to represent multi-modal distributions is insufficient and often inaccurate. Therefore, prototype nodes for each class to enable them to capture different modes in feature distribution. The embeddings of these prototype nodes learned via adapted slot attention mechanism (Locatello et al. 2020). In the original setting, a fixed number of slots are learnt to represent different objects in computer vision tasks.
design multiple
In ProtoGNN, we extend slot attention mechanism to learn the prototypes/cluserss of node features of each class. The learning is done via attention where the class prototypes compete for explanations of each node, resulting in soft clustering effects such that each slot dominates in certain groups of nodes.
For learning the prototypes. we first transform the node features using an MLP to generate the node embeddings. These embeddings are averaged and used to initialize the mean μl of a Gaussian distribution Al (1,, Σ) with randomly initialized and learned co- co-variance We initialize K prototypes for each class c, denoted by pe E R by sampling from the distribution N N(u, E). We then iteratively update the embeddings. In each iteration, compute dot product attention (Luong et al., 2013) between the prototypes and nodes, followed by softmax operation that normalizes over the prototypes, such that the assignment scores each prototype sum up one for given node. In this way, the prototypes will compete for an assignment of nodes which acts as a soft clustering on the node feature space. Specifically, the attention weights Mc Ma for class is
X (T.a(
4

---

Under review as a conference paper at ICLR 2023
[P-Wa]- [W (X Prran))
M attn Softmax
RRKxNinain
vd
where d is the hidden dimension, train is the number of training nodes belonging class c, WQ and W are query and key transformation matrices respectively, and is small coefficient added for numerical stability. Then, we normalize the attention matrix Mattn over the training node dimension, so that for each prototype, assigned weights in all training nodes sum up to one. We then update the prototype embeddings Pe using the weighted average of training node features X train
pe= Norm (oom(Mattn))) X W
E Rkxd
where WV is parameter matrix. The learning of prototypes serves as a soft clustering of feature space. It can also be viewed as message passing from training nodes to prototypes via artificially added edges.
Structure View. We use GNN learn the structure view representation of nodes. GNN takes both node features and adjacency matrix inputs. After each layer of message passing processing, GNN produces a structure view node embedding matrix H' E RdNxd, Note that we can use any GNN as backbone to generate the structure view embeddings.
H' GA,
where HD Xraw
(5)
Information Transfer/Fusion. Once we have all the class prototypes P from the feature view and node embeddings H from the structure view, we can then transfer the information from prototype nodes onto the structure view embeddings. This is done by first computing dot product attention between prototypes from all classes and all non-training nodes, and then using the softmax function normalize over the prototype dimension, that the weight of all prototypes sum up to one for each non-training node.
Satt = Sestmaxx('nnntraan P") E IR
M Mundrrain XCK XCK
(6)
Next, we compute the message to be passed from prototype nodes to non-training nodes by taking the weighted average of prototype embeddings according to the dot product attention weights. Finally, we fuse the prototype messages from the feature view with the node embeddings from the structure view through aggregation function. We allow the structure view of node embeddings be taken from any layer of the GNN, making it an architectural choice.
H' = AGG(H ( Mproto)
where
Mproto Sattn
This information transfer process can also be viewed as a message passing from prototype nodes to non-training nodes. Therefore, the ProtoGNN framework essentially constructs shorteut between all the nodes in the graph. This is especially beneficial in the non-homophilous setting where useful information is less available in the graph local neighborhood. This also helps in some homophilous settings as well when useful information is distant.
Training. To exploit the full potential of the multiple prototypes of each class, we regularize training with two additional loss functions besides the cross-entropy loss. First, the cross-view compatibility loss regularizes by encouraging the structure and feature views to agree. Second, the orthogonality loss encourages the prototypes to be distinct from each other.
We modify the compatibility loss function from Snell et al. (2017). making hierarchical in order to handle multiple prototypes within each class. This is done with the help of additional aggregation function. We first compute the similarities between the prototypes of a class and node embedding in order to compute the likelihood that the embedding belongs to the class. The similarity scores with the multiple prototypes are then aggregated into a single score for the class. Multiple choices of aggregators are possible, e.g. could compute the average similarities between the embedding and
5

---

Under review as a conference paper at ICLR 2023
the prototypes in the class. We use the aggregator in order to select the most similar prototype within the class to the node. The compatibility loss is then computed as follows:
$
max REK
((f(h))
(8)
Coomp
O 88
+ log
Σ exp ( --5)) c'
(9)
CNtrain
iEN
where Nerain is the number of training nodes, C' is number classes, Cj is the class-label of 7dh training node, Pi is the kth prototype of class c, h is the node embedding before final classification, is MLP and prototypes, we regularize them so that they are distinct from each other. We do that by enforcing the prototypes to orthogonal each other through an orthogonality loss shown be useful according to Bianchi et al. (2020).
similarity function for which we use dot product. To exploit the full power of
pe P
Lortho
(10)
pe PClF
Vd
where ||-|| indicates the Frobenius norm. With the and 3 tuning hyperparameters, the full loss function used for training is
C= alcomp + BLorth
(11)
Complexity. In Tab. [ we compare the complexity of ProtoGNN with other baseline models which add additional edges. Particularly, GloGNN (Li et al. 2022), though efficient sparse graphs with small d (average degree), can quadratic for dense graphs.
Table comparison
H2GCN WR GAT GLOGNN PROTOGNN
MEAN O O(ulogaj OldCn) O(KCN)
ProtoGNN captures global information with only O(n) additional edges. More specifically, contains additional K Cn virtual edges, when the graph contains C' classes with K prototypes per
class. Note that both K, C' < n and hence, it preserves the linear complexity of GNNs.
EXPERIMENTS
5.1
EXPERIMENT SETUP
We conduct experiments on 10 datasets, including 7 non-homophilous datasets: Penn94, Pokec, Genius, Twitch-games gaatch-gamers, Cornel15 and Amherst41 released by Lim et al. (202I), and US- election dataset that we identify to be non-homophilous (Jia & Benson 2020p. We use the original train/validation/test splits such splits exist. The train/validation/tes. split is 60%, 20% 20% for US-election, and 50%, 25%, 25% for other datasets. We also evaluate the performance of ProtoGNN on three popular homophilous datasets: Cora, Citeseer and Pubmed (Pei et al., 2020), with a low label rate setting that labeled node is unlikely to be close node that needs be labeled. The statistics of the datasets are included in Tab. 2 More details of the datasets are in the appendix.
Datasets
Baselines ProtoGNN is generic framework that can be applied onto any of the existing GNN backbones. We first add ProtoGNN to 4 backbones: (1) GCN (Kipf & Welling 2016); (2) GCN with batch normalization, as we observe that batch normalization significantly improves performance in some datasets; (3) GCNII (Chen et al., 2020), a deeper GNN architecture; (4) LINKX (Lim et al. 2021), a model specifically designed for non-homophilous graphs. Following Lim et al. (2021) and Li al. (2022), we also compare ProtoGNN against 11 other baselines for comprehensive evaluation, including (1) MLP: (2) general GNNs, including GCN, GAT (Veličković et al. 2017).
MixHop (Abu-El-Haija et al. 2019) and GCNII; (3) baselines designed for non-homophilous graphs
including H,GCN (Zhu et al. 2020b), WRGAT (Suresh et al. 2021), GPR-GNN (Chien et al. 2020
ACM-GCN (Luan et al.
2021 LINKX and GloGNN (Li 2022

---

Under review as a conference paper at ICLR 2023
Table 2: Statistics of non non-hooophilous datasets and Classification performance of ProtoGNN vs backbones on non-homophilous datasets. Hom. Mat. refers to the homophily matrix described in Sec. S and stand for class labels. We report AUC for Genius (Lim et al. [021 and accuracy for other datasets with standard deviation over 3 trials. OOM refers to the out-of-memory error.
Ponn94
Pokee
Genius
Twitch-gamers
CornellS
Amberst41
US-election
ANodes aKdges
41,554
1,632, 803
421,961 984.979
168.114 6,797,557
18660 790,777
2235 90,954
3234
1,362,229
30,622,564
11,100
0.52
0.50
0.88
0.55
0.41
0.50
0.60
0.61
0.38
0.86
0.15
0.41
0.98
0.48
0.52
0.49
0.61
0.12
0.89
Hom, Mat.
OCN
77.08 (0:40)
66.52 (5.16)
$7.09 (0.51)
61.78 (0.12)
73.91 (0.32)
81.10 (1.51)
81.71 (2.55)
-ProtoGNN
81.43 (0.26)
73.59 (0.30)
(1.16)
(0.17)
81.03 (0.92)
(1.34)
OCNoN
82.17 (0.27)
75,45 (0.17)
87.42 (0.57)
62.18 (0.26)
80.15 (0.37)
81.41 (1.70)
82.07 (1 (L.65)
-ProtoGNN
82.97 (0.07)
76,91 (0.03)
87.16 (0.94)
62.62 (0.16)
89.73 (0.48)
$1.56 (2.00)
N2.74 (1.35)
GCNI
82,92 (0.59)
0OM
90124 (0.09)
63.39 (0.61)
78. 85 (0. 788)
76.02 (1.
82,90 (0) 29)
PrototNN
83.19 (0.31)
0OM
91.18 (0.13)
65.20
80.08 (0-48)
79.13
84.08 46-
LINKX
84.71 (0.52)
82,04 (0.07)
90.77 (0.27)
66:06 (0:
83. 42, (0) 50)
(1.04)
84.08 (0.67)
+ ProtoGNN
86.23 (0.34)
81.94 (0.10)
90.80 (0.10)
66.42 (0.34)
84.14 (0.13)
82.81 (1.34)
86.97 (1:21)
5.2
EXPERIMENTAL RESULTS
5.2.1 USING PROTOGNN TO ENHANCE EXISTING GNN BACKBONES
We are motivated to design ProtoGNN as a generic framework that is orthogonal to existing GNN models to boost their performance on heterophilous graphs. We therefore evaluate the effects of applying ProtoGNN onto various existing GNN backbones. We first apply ProtoGNN on GCN, one of the most widely used general-purpose GNNs, and observe performance improvement on out of 7 datasets, with substantial gains on Penn94, Pokec, Cornel15, and US-election (Tab. 2 GCN, we find that batch normalisation brings consistent performance boost to GCN on various non- non-honee cou-hompphilous datasets. We therefore add ProtoGNN on top of GCN with batch normalization to evaluate its performance this GCN variant. GCNgN+ProtoGNN achieves consistent performance improvement on all datasets except Genius.
During experiments
We then apply ProtoGNN on GCNII, deeper GNN model that is capable of retrieving global information by propagation through the additional layers. Though not designed for heterophilous graphs, it serves as strong baseline for heterophilous datasets. GCNIL+ProtoGNN achieves better performance than the original GCNII on all datasets, with pronounced improvement on 1
We next evaluate our framework's 's effectiveness graphs. LINKX+ProtOGNN performs consistently better than LINKX on 6 out of 7 datasets, with substantial enhancement on US-election. Penn94 and 1mherst41 datasets. Overall, the results demonstrate consistent improvement of ProtoGNN on various backbone GNNs and datasets.
backhone explicitly designed for heterophilous
5.2.2
COMPARISON AGAINST MORE BASELINES
Table 3: Classification performance comparison against haselines. Notations follow style in Tab
Penn94
Pokec
Genius
Twitch-gamers
CornellS
Amhersta1
US-election
MLP
73.61 (0:40)
62.37 (0.02)
86.68 (0.09)
60.92 (0:07)
68.86 (1.83)
60.43 (1.26)
81.92 (1.01)
GCN
82.47 (0.27)
75.45 (0.17)
87.42 (0.37)
62.18 (0.26)
80.15 (0.37)
81.41 (1.70)
82.07 (1.65)
GAT
81.53 (0.55)
71.77 (6)18)
55.80 (0.87)
59.89 (4.12)
78.9 (1.57)
79.33 (2.09)
84.17 (0.98)
MixHop
83.47 (0.71)
81.07 (0.16)
90.58 (0.16)
65.64 (0.27)
78.52 (1.22)
76.26 (2.56)
85.90 (1.55)
GCNII
82.92 (0.59)
0OM
90.24 (0.09)
63.39 (0.61)
78.85 (0.78)
76.02 (1.38)
82.90 (0.29)
H H'2GCN
81.31 (0.60)
0OM
00M
0OM
78.46 (0.75)
79.64 (1.63)
85.53 (0.77)
WRGAT
74.32 (0.53)
00M
00M
00M
71.11 (0.48)
62.59 (2.46)
84.45 (0.56)
GPR-GNN
81.38 (0.16)
78.83 (0.05)
90.05 (0.31)
61.89 (0.29)
73.30 (1.87)
67.00 (1.92)
84.49 (1.09)
ACM
82.52 (0.96)
63.81 (5.20)
80.33 (3.91)
62.01 (0.73)
78.17 (1.42)
70.11 (2.10)
85.14 (1.33)
LINKX
84.71 (0.52)
82.04 (0.07)
90,77 (0.27)
66.06 (0.19)
83,46 (0.61)
81.73 (1.94)
84.08 (0.67)
GleGNN++
85.74 (0.42)
83,05 (0.07)
90.91 (0.13)
66.34 (0.29)
83,96 (0.46)
81.81 (1.50)
85.48 (1.19)
ProtoGNN
86.23 (0.34)
81.94 (0.10) 91.18 (0.13)
66.42 (0.34)
84.14 (3) 82.81 (1.34)
86.97 (1.21)
To further evaluate the effectiveness of ProtoGNN, compare best results in Tab. 2 Jggansst 11 strong baselines following [Lim et al. (202T) and [i et al. (2022). including MLP and general- purpose GNNs: GCN, GAT, MixHop and GCNII. The remaining 6 baselines are GNNs built.
7

---

Under review as a conference paper at ICLR 2023
specifically for heterophilous graphs, including HGGCN, WRGAT, GPR-GNN, ACM- GCNN LinkX and GloGNN++. All ProtoGNN results in Tab. 3 are from LINKX+PrOOOGNN, except for Genius where GCNIL+ProtOGNN performs best.
ProtoGNN achieves state-of-the thr---rrtt on 6 out 7 datasets compared to all baselines, except on Pokec. While some methods incur OOM enrors when running large-scale datasets, ProtoGNN does not suffer OOM due to its linear complexity with respect to backbones.
5.2.3 IMPACT OF SHORTCUT CONSTRUCTION
An important property of ProtoGNN introducing shortcuts between training nodes and non-training nodes via the con- structed class prototypes. By facilitating the transfer of useful information from afar, shortcuts become especially helpful on heterophilous graphs, where useful information is often unavail- able in local neighbourhoods. We use the US-election dataset to illustrate the effect of shortcuts. Here, nodes represent counties, and edges connect bordering counties. Red and blue colors represent the election outcomes of the counties. As visualized in Fig. B] nodes on the east coast and west coast are separated by swathe of red counties, but share similar node features such as income, education and demographics. A shortcut between them via prototypes helps the message bypass the red counties in middle America, preventing message dilution in traditional message passing neural networks. Our results in Tab. 2 show that ProtoGNN achieves consistent performance improvement on US-election when added to all GNN backbones.
Figure 3: US 2012 election results map by county.
Table Classification accuracy on Cora, Citeseer and Pubmed with 5 labels per class.
To further evaluate the effects of shortcut con- struction, we consider generalized scenario on homophilous graphs where information from labeled nodes needs propagate long dis- tance to reach most unlabeled nodes. Specifi- cally, we evaluate our method on Cora, CiteSeer and Pubmed with only small number of training labels per class. We use single prototype for each class without slot attention and obtain prototype representations by taking the average of training node features, since the training labels are scarce. Our hypothesis is that information propagation becomes more challenging with increasing scarcity of useful training information, making the effects of shortcut construction more pronounced in sparsely-annotate graph datasets. The hypothesis is confirmed by experiment results. As shown in Tab. [ GCN+ProtoGNN beats vanilla GCN on all datasets, with substantial improvements on Cora and Pubmed.
CoRA 69.22 (3.39) 63.03 (4.48) 68.00 (3.75)
CITESEER
PUBMED
GCN
+PROTOGNN 71.79 (1.56) 64.00 (3.45) 72.67 (3.88)
5.2.4 ABLATION STUDIES
Number of prototypes per class Motivated by the observa- tion that node features tend to form clusters in feature space illustrated in Fig. D we assign multiple prototypes per class to capture the clusters. Our hypothesis is that multi-modal feature distribution is more accurately represented using mul- tiple prototypes. We test the hypothesis by varying the number of prototypes per class in ablative experiments. We train Pro- toGNN with combinations of different numbers of prototypes and hidden dimensions. Fig. 4 iillustrates ablative experiments of LINKX+ProtOGNN on Penn94. We observe that: (1) Pro- toGNN with a single prototype per class outperforms the back- bone. (2) ProtoGNN with multiple prototypes per class perform consistently better than their single prototype counterparts. Our prototypes per class(K). ablative experiments shows the effectiveness of using prototypes, as well as the benefits of using multiple prototypes per class over using single one. (3) The optimal number of slots depends on a number of factors, such as hidden dimension, dataset feature space and backbone model type.
86.2
ACCURACY
85.6
85.0
85.4
85.2
32
128
6%
HIDDEN DIMINSS
Figure 4: Effects of the number of
8

---

Under review as a conference paper at ICLR 2023
Loss functions To achieve the full potential of the soft-clustering objective of our model. we add two additional losses to learn prototypes effectively. The compatibility loss enforces similarity in embeddings, while the orthogonality loss acts regularizer con-
Table 5: Effects of Compatibility and Orthogonal- ity losses on Amherst41 and ComellS5 datasets.
Coomy (a) Cattha (3)
AMHERST41 CORNELL
81.36 (0.09) 83.05 (0.96)
0.1
0.01
81.88 (0.32) 84.14 (0.13)
straining the model to learn distinct prototype clusters for each class. In this ablation study, we evaluate the effect of these losses on model performance. We vary and 3 parameters in Eqn. 11 from the set {0, 0.01,0.13. with hidden dimension fixed to 64 and the number of slots set to 5. Results in Tab. show consistent performance improvements for all non-zero values of a and B on both datasets, compared to cross-entropy loss alone. This provides substantial evidence for the usefulness of the additional loss functions.
0.01
0.1
82.28 (0.73)
83.89 (0.12)
0.01
0.01
82.28 (0.42) 83.76 (0.16)
Aggregation operation in Compatibility loss In order to make the node embeddings similar prototype representations from the same class, we design the cross-view computibility loss Leomp- After computing the similarity between a node and each of the multiple prototypes from the same class, the choice of aggregation method critical. We evaluate the effectiveness of using the aggregation operator on 1 and Cornell5 datasets. Tab. O shows the effects of replacing the max aggregator with mcan
Table 6: Effects of aggregator func- tion used in Compatibility loss on 1 and Comell5 datasets.
AGG AMHERST41 CORNELLS
MEAN 81.17 (0.91) 82.73 (0.35)
SUM 81.17 (1.73) 83.53 (0.36)
MAX 82.81 (1,34) 84.14 (0.13)
and sum in computing compatibility loss. On both datasets, max outperforms both sum and mean, indicating the effectiveness of using max as the aggregation operation. Intuitively, taking the average of all similarity scores (mean) is sub-optimal. mean tends to make the node embeddings closer to the average of all prototypes from the same class, undermining the purpose of using multiple prototypes to represent different clusters. Similar to mean, summing up all similarity scores (sum) is more powerful yet requires more data to learn. max selects the maximum similarity score to compute compatibility loss and guides the node embeddings closer to one of the class prototypes, thus preserving the power of diversity in representation.
Node pulti-prototype learning. We adapt slot- attention mechanism to learn multiple prototypes for each class. In order to evaluate the effectiveness of learning prototypes with slot-attention, we ablate the model against two variants: J)ProtoGNN-Naive a variant where class prototypes are constructed by tak- ing the average of all training node features from that class. 2) ProtoGNN-SA, where we adopt the classic self attention mechanism to learn class proto- types. We show results on 1mherst41 and Cornell5 datasets keeping other hyperparameters fixed in both models. As shown in Tab. 7 we observe that ProtoGNN consistently outperforms both variants, signifying the effectiveness of using slot attention. Its better performance may be attributed to the ability to perform soft clustering that enables the multiple prototypes per class to capture the underlying clusters in feature space, which self-attention and taking the average of node features cannot do. A detailed comparison between ProtoGNN-SA and ProtoGNN can be found in Appendix.
Table 7: Effect of Slot Attention on 1 I and Cornell5 datascts.
SETTINGS
AMHERST41
CORNELLS
PROTOGNN NAIVE 80.84(1.94)
83.94 (0.08)
PROTOGNN-SA 82.15 (1.07) 83.25 14)
PROTOGNN 82.81 (1.34)
84.14 (0.13)
CONCLUSION
In this work, we address the two challenges in heterophilic graphs of efficiently capturing scattered but useful global information from distant nodes and preserving node feature information from dilution. For this, we propose ProtoGNN, a prototype-asiitedd message passing framework that aug- ments existing GNNs by effectively combining node feature information with structural information. ProtoGNN exploits strong node features by constructing multiple class prototypes from training nodes. It then passes the information from prototype nodes to non-training nodes, updating their structural embeddings learned through GNN backbones. It thus creates shortcuts that bypass the local graph neighbourhoods and efficiently captures global information. ProtoGNN is generic framework that can be applied to any existing GNN backbones. Our extensive experiments demonstrate that ProtoGNN brings consistent improvements when applied to various GNN backbones, achieving state-of-thee the-the-at art results on multiple datasets against strong baselines.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
Our work is generic framework to improve node representation learning on non-homophilous graphs. This work applies to GNNs generally and non-homophilous graph structured data specifically, Its ethical impacts (including positive and negative) depends on the specific domain of the data. We conduct our experiments on publicly available datasets in compliance with fair-use clauses.
REPRODUCIBILITY STATEMENT
Details of the datasets used can be found in Appendix A.1 For experiments, the settings can be found in Section 15. and details of the hyperparameter settings used for training are specified in Appendix A.2 To further facilitate reproducibility of this work, we will make the code publicly
available at anonymised repository
REFERENCES
Sami Abu-al-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In ICML, pp. 21-29, PMLR, 2019.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pp. 874 883. PMLR, 2020.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. arXiv preprint arXiv:2101.00799 2021.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, pp. 1725-1735. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint 20vv:206.077988, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. NeurlPS, 29:3844 3852, 2016.
Kaize Ding, Jianling Wang, Jundong Li, Kai Shu, Chenghao Liu, and Huan Liu. Graph prototyp- ical networks for few-shot learning attributed networks. In Proceedings of the 29th ACM International Conference on Information Knowledge Management, pp. 295-304, 2020.
Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Graph neural networks with adaptive frequency response filter. arXiv preprint a0Xiv:2104. 12840, 2021.
Justin Gilmer, Samuel Schoenholz, Patrick Rilcy, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pp. 1263-1272. PMLR, 2017.
Junteng Jia and Austion R Benson. Residual correlation in graph neural network regression. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 588-598, 2020.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arviv: 1609 0090000900..0. 2016.
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily, arXiv preprint M.Niv:2205.07330. 2022.
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. NeurIPS, 34, 2021.
10

---

Under review as a conference paper at ICLR 2023
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. TPAMI, 2021.
Francesco Locatello, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf. Object-centric learning with slot attention. Advances in Neural Information Processing Systems, 33:1 12211125-111 11538, 2020.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Is heterophily a real nightmare for graph neural networks to do node 2021.
classification? arXiv preprint arXiv:2
Minh-Thang Luong, Hieu Pham, and Christopher D Manning. Effective approaches to iitentiio-bused neural machine translation. arXiv preprint arXiv:1508.0400000 2015.
Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: a fast and scalable system for fraud detection in online auction networks. In Proceedings of the 16th international conference on World Wide Web, pp. 201-210,, 2007.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang. Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
Fengzhao Shi, Yanan Cao, Yanmin Shang. Yuchen Zhou, Chuan Zhou, and Jia Wu. H2-fdetector: A gnn-basee fraud detector with homophilic and heterophilic connections. In Proceedings of the ACM Web Conference 2022, pp. 1486-1494 2022.
Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning, Advances in neural information processing systems, 30, 2017.
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In KDD, pp. 1541-1551, 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: /710. /0903, 2017.
Junjie Xu, Enyan Dai, Xiang Zhang, and Suhang Wang. Hp-gmn: Graph memory networks for heterophilous graphs. arXiv preprint arXiv:2210.08195 2022.
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. arXiv preprint arXiv:2102.06462, 2021.
Yongyi Yang, Tang Liu, Yangkun Wang, Jinjing Zhou, Quan Gan, Zhewei Wei, Zheng Zhang, Zengfeng Huang, and David Wipf. Graph neural networks inspired by classical iterative algorithms. arXiv preprint
2021.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Wei Ye, Jiayi Yang, Sourav Medya, and Ambuj Singh. Incorporating heterophily into graph neural networks for graph classification. arXiv preprint arXiv:2203.0767 2022.
Zaixi Zhang, Qi Liu, Hao Wang, Chenggiang Lu, and Cheekong Lee. Protgnn: Towards self- explaining graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 1127-9135, 2022.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. arXiv preprint arXiv:2009. 13566, 2020a.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. arXiv preprint arXiv:2006. 1468, 2020b.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11 11168-11176. 2021.

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
A.1 DATASET DETAILS
Penn94, Cornell5 and Amherst41 (Lim et al. 2021) are friendship network datasets extracted from Facebook of students from selected universities from 2005. Each node in the datasets represent student, while node label represents the reported gender of the student. Node features include major, second major/minor, dorm/house, year, and high school.
Pokec (Lim et al. 2021) is a friendship graph dataset from a popular Slovak online social network, where nodes represent users and edges represent directed friendship relations. Node label represents the reported gender of user. Node features include geographical region, registration time, and age.
Genius (Lim et al. 202T>> is sub-network from website genius. com, crowd-sourced website of song lyrics annotations. Nodes represent users while edges connect users that follow each other. Node features include expertise scores expertise scores, counts of contributions and roles held by users. Around 20% of the users are marked with a "gone" label, indicating that they are more likely be spam users. The task predict which users are marked.
Twitch-gamers (Lim et al. (021) is a sub-graph extracted from the streaming platform Twitch. Each node represents Twitch account, while edges connect accounts that are mutual followers. Node features include number of views, creation and update dates, language, life time, and whether account dead. The task is to predict whether the account has explicit content.
US-election JJi & Benson 2020) is geographical dataset extracted from statistics of Unite States election of year 2012. Nodes represent US counties, while edges connect bordering counties. Node features include income, education, population etc. The task is binary classification to predict election outcome.
Cora, Citeseer and Pubmed (Pei et al. 2020) are citation graphs, where each node represents scientific paper and two papers are connected when a paper cites the other. Each node is labeled with the research field and the task is predict which field the paper belongs to. All three datasets homophilous.
A.2 HYPERPARAMENT DETAILS
MLP:
hidden dimension E {16, 32, 64), number of layers E (2,3). Activation function is ReLUU
GCN: Ir E .001), hidden dimension E {4, 16, 64). except for Pokec, where hidden dimension E (4,8, 16). number of layers E [2). Activation function is ReLU.
GAT: E (001, For Pokec: hidden channels E [4,8, 12) and gat heads E (2, 4). For the remaining datasets: hidden channels E {4, 1,,, 32} and gat heads E {2, 4, 8). number of layers E {2]. We use the ELU as activation.
MixHop: hidden dimension E {8, 16, 32}, number of layers E (2).
GCNII: number of layers [2. 8, 16, 32, 64), strength of initial residual connection a E {0.1, 0.2, 0.5]. hyperparameter for strength of the identity mapping {0.5, 1.0, 1.5).
H₃GCN: hidden dimension E [16,32), dropout E {0..5), number of layers E {1,2).
Model architecture follows Section 3.2 of Zhu al. (222b)).
WRGAT: Ir E {.01). hidden dimension (32).
GPR-GNN: Ir E {.01, 10,,005, hidden dimension {16, 32).
ACM-GCN: Ir E {.01}. weight decay (5e 5e 5e 4 5e -3) dropout e {0.1, 0.3, 0.5, 0.7, 0.9). hidden channels {64), number of layers E (2). display step E [1].
LINKX: hidden dimension {16, 32, 64), number of layers {1,2). Rest of the hyper- parameter settings follow Lim et al. (202T).
GloGNN++: Ir E {.001, ....0005.00. .01) weight decay E (0, .1,, dropout E [0..5. hidden channels E {128, 256), number of layers (1,2), (0, 1), 3 E (0.1,1)
12

---

Under review as a conference paper at ICLR 2023
? (0.2,0.5, 8 10.2,0.5) number of normalization layers {1,2), orders E {1,2,3) 3), display step E {1}.
ProtoGNN: Ir [.005,.01] weight decay E {0, 0.001. .0005), loss coefficients a, B E {0, (0.0.01, 0.1}, prototypes per class (K) {1.3, 5, 10), hidden dimension {16, 32, 64)
A.3 TRAINING SETTINGS
We run each experiment with three different splits, and report the mean and standard deviation the performance. All experiments are run single V100 GPU with 16G memory. We use Adam the optimizer and perform grid search to find the best hyper-parameter combination, with details listed in We report the baseline results directly if they are already public.
A.2
A.4
FEATURE SPACE VISUALIZATION
To illustrate how node features form clusters in feature space, we plot the data points for 7 non- homophilous datasets, with shown in Fig. [ We reduce the node feature dimension to sample 2000 nodes of the same class from each dataset, and plot them along the reduced dimensions. 5 55ssssss the t-sne plots of Pokec, Genius, Cornel15, 1mherst41 and US-election datasets. The plots show the clustering patterns of the nodes in feature space consistently across the most of the datasets. This observation is the main motivation for our modelling of multiple prototypes per class for transferring global information across the nodes.
30-
-55
-00
(a) Pokec
(b) Genius
(c) Cornel15
(d) Amherst41
(e) US-election
Figure 5: Feature space visualization of non-homophilous datasets.
A.5 FURTHER ABLATION STUDY
Self attention is classic mechanism that can be used to learn the class prototypes. In this ablation study, we discuss in detail the rationality of using slot attention instead of self attention our framework. In principle, slot attention is preferred over self attention because of the following reasons: Firstly, In slot attention, each slot/prototype will learn to compete for the explanation via the softmax-basee attention mechanism. Therefore, the learning of multiple slots/prototypes serves as soft clustering of the training nodes. Self attention, on the other hand, does not act as soft clustering. As shown in Fig. a and Fig. 6) visualized features for Penn94 and Twitch Gamers do tend to form clusters in feature space. It is beneficial to be able to capture such clustering information, as illustrated in Figure 4. Secondly, Slot attention is more efficient. In self attention, attention score computed for every pair nodes, and thus the number of computations needed is (n??). However, in slot attention, only need to compute the attention score between nodes and slots/prototypes,
13

---

Under review as a conference paper at ICLR 2023
so the number of computations needed is O(nk), where & is the number of prototypes and is much smaller than the number of nodes n.
We conduct an additional ablation study self-attention slot attention to empirically verify claims. We replace slot attention with self-attention in ProtoGNN and document the performance on 7 datasets in the following table. While ProtoGNN-SA with self-attention outperforms the backhone on most of the datasets, ProtoGNN with slot attention still outperforms on all 7 datasets.
Table 8: Classification performance comparison against basclines. Notations follow style in Tab
Penn94
Pokec
Genius
Twitch-gamers
Cornell5
Amherst41
US-clection
Backbone
84.71 (0.52)
82.04 (0.07)
90.77 (0.27)
66.06 (0.19)
83.46 (0.61)
81.73 (1.94)
84.08 (0.67)
ProtoGNN-SA
83.53 (0.28)
80.25 (0.45)
90.41 (0.24)
66.31 (0.28)
83.25 (0.14)
82.15 (1.07)
84.90 (0.65)
ProtoGNN
86.23 (0.34)
81.94 (0.10)
(0.13)
(0.34)
84.14 (0.13)
82.81 (1.34)
86.97 (1.21)
To verify the computation efficiency empirically, report the average runtime of ProtoGNN with self-attention and slot attention respectively, ProtoGNN with slot attention (10.14 milliseconds) runs much faster than ProtoGNN- SA (5.76 milliseconds).
A.6 HOMOPHILY MATRIX FOR HOMOPHILOUS DATASETS
Below are the homophily matrices for three well-known homophilous datasets: Cora, Citeseer and Pubmed Yang et al. 2016). High homophily is signified by the high numbers in diagonal cells, whereas values of non non-diand diagona cells mostly less than 0.1. This is different from the homophily matrices of non-homophilous datasets in Tab. where values of non-diagonal cells are similar or higher than diagonal cells.
01:000
0.023
3.002
0.00
0/085
0.124
5:18
0.585
0,031
5.755
0.955
3.527
0,302
0.322
0,813
0.044
3.555
0.399
0.000
8.055
0.301
0U257
5.004
3.29
0.525
0.48
3.099
0
0.000
ELBSS
5.033
3.05
0.366
8.02
0.30
0.06
0.006
0.006
0.765
3.58
0.222
0.008
D00e
0.057
0.827
(a) Cora
(b) Citeseer
(c) Pubmed
Figure 6: Homophily matrix for three homophilous datasets.
14


Reviews:
[{"review_id": "y-qaHZpT2z", "reviewer": "Reviewer_A8KJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper introduces a ProtoGNN for non-homophilous (or heterophilous) graphs, which could augment existing GNNs by combining node features with structural information. ProtoGNN could learn multiple prototypes for each class with slot attention. To further exploit the power of multiple prototypes, this paper uses two regularization losses: compatibility loss and orthogonality loss. The experimental results show that the proposed method is useful for several datasets.  ", "summary_of_the_review": "Overall, the proposed approach is interesting and the writing is clear. However, it is not quite clear why the paper uses slot attention rather than self-attention. Besides, the experimental results in Table 4 show that ProtoGNN only significantly outperforms GloGNN++ on 3 out of 7 datasets. ", "strength_and_weaknesses": "Strengths:\n1. Using multiple prototypes for each class is interesting.\n2. The experiments are conducted on both homophilous and heterophilous graphs.\n3. The writing of the paper is clear in general.\n\n\nWeakness:\n1. It is not quite clear how does self-attention perform. Self-attention is cheaper and more classic than slot-attention, and thus it is necessary to compare slot-attention with self-attention.\n2. ProtoGNN only significantly outperforms the SOTA method GloGNN++ on 3 over 7 datasets: Penn94, Genius and US-election. It is necessary to conduct t-tests for Twitch-gamers, Cornell5 and Amherst41.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "b-m23Pm2lR", "reviewer": "Reviewer_mEwF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper extends the transform-based GNN by enhance the memory with multiple cluster prototypes. It justifies the correctness by effective considering the nodes from the same class but with long range. Experimental evaluations demonstrate its effectiveness.", "summary_of_the_review": "My main concern is the limited novelty. It is not novel to introduce cluster prototypes into the transformer-based GNNs, although this may be the first which considers multiple prototypes.\n", "strength_and_weaknesses": "Strength\n\n- The writing and organization are good. \n- The experimental evaluations are sufficient.\n\nWeakness \n\n- The novelty is very limited. It is not novel to introduce cluster prototypes into the transformer-based GNNs such as [1]\n\n[1] Junjie Xu, Enyan Dai, Xiang Zhang, Suhang Wang. “HP-GMN:Graph Memory Networks for Heterophilous Graphs” Accepted by The IEEE International Conference on Data Mining (ICDM 2022)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "CSwTVZPZERm", "reviewer": "Reviewer_Fqiu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper targets the incapability of GNNs on heterophilous graphs and proposes to process the node feature and graph structures separately. Specifically, Multiple node feature prototypes are first generated with only the node feature information. Then, arbitrary GNN is used to obtain a structural view (embedding) of each node. Finally, the prototypes are aggregated into the structural embeddings via an attention based mechanism. Experiments are conducted on multiple datasets and compared with multiple baselines.\n", "summary_of_the_review": "Overall, this paper is well written and targets a meaningful problem, but the contribution is not significant, because the performance is mainly determined by the backbone, which is also shown in experiments.\n\nTherefore, I think this paper is only slightly above acceptance threshold", "strength_and_weaknesses": "Strengths:\n\n1. The paper is well written and easy to follow. The explanation on the model is very clear with a good logic.\n\n2. The studied problem of heterophilous graph learning is meaningful.\n\n3. The experiments are comprehensive, 10 datasets are used and some of them are very large. Also, many baselines are included in the commparison. \n\n\nweakness:\n\n1. when generating the structural view, if the GNN are the ones for homophilous graphs, then the obtained embedding should not be of high quality, and accordingly there is no reason to believe they can be used to properly aggregate the prototypes. But if the adopted GNNs are the ones for heterophilous graphs, then the mechanism proposed in this paper is only an incremental part of the whole model instead of a key module.\n\nTherefore, whether the proposed module works well highly depends on whether the adopted GNN backbone is good enough, making the contribution of this work not very significant. Also, according to the experiments, the improvement gained by including ProtoGNN is indeed not significant.\n\n2. what is the backbone GNN used in Table 4\n\n3. It would be better to also show the homophily matrix of the homophilous graphs. In the current version, althoug the homophily matrix of the heterophilous graphs are given, but it seems that most of the classes have half homophilous edges and half heterophilous edges, and not sure how to understand these values. E.g. is 0.5,0.5 enough to say this class is heterophilous enough? \n\n4. Are all the heterophilous datasets binary classification datasets with only two classes? Why is this? Isn't there any datasets with more classes?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2Wq1yRAIdK", "reviewer": "Reviewer_v2yj", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work attempts to deal with node heterogeneity for graph learning task. The proposed method dissects the node representations into feature and structure views. Finally a prototype-based node representation method is designed by separately modeling feature view with prototype-based MLP network and encoding graph structure with GNN.    ", "summary_of_the_review": "Though experimental results show promising aspects of the proposed method, it still needs a significant improvement over the presentation quality, especially the clarity of motivation.", "strength_and_weaknesses": "Node label heterogeneity raise unique challenge for effectively learning node representation. This work takes an important step to deal with it by not fully relying on a pure GNN model. However, there are still important questions that are not answered.\n\nStrength:\n1. A prototype-based method is proposed to deal with graph heterogeneity issue.\n2. Special regularizations are designed along with the proposed method for effectively controlling the prototype distribution.\n3. Extensive experiments are conducted on multiple datasets to show the classification performance of the proposed method.\n\nWeakness:\nMy main concern is about the novelty and motivation behind this work. More specifically, it's difficult for me to clearly catch up with the motivation and exact contribution to advancing GNN method for dealing with label heterogeneity issue. More specially, I have following concerns.\n\n1. The justification in the Introduction section is too weak to explaining why prototype can deal with the limitations mentioned in the second and third paragraphs.\n\n 2. It deserves more words to explain why we need multiple prototypes for each classes, and what is the connection between aggregating features from distant nodes and solving non-homophilous problem. The difference from previous works which also uses prototype or clustering centers is not discussed.\n\n3. Besides, it's difficult to understand what is the contribution of this work to advancing GNNs for better adapting to non-homophilous dataset. From the architecture shown in this work, we can see that the key component is a MLP-based encoder, while GNN layer can be initialized any GNN model. What if the selected GNN module like vanilla GCN, GAT etc. can not deal with the label heterogeneity problem? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject