GLINKX: A Scalable Unified Framework For Homophilous and Heterophilous Graphs
Authors: Marios Papachristou
Rishab Goel
Frank Portman
Matthew Miller
Rong Jin
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph learning
node classification
homophily
heterophily
positional embeddings
knowledge graph embeddings
monophily
label propagation

Abstract: In graph learning, there have been two predominant inductive biases regarding graph-inspired architectures: On the one hand, higher-order interactions and message passing work well on homophilous graphs and are leveraged by GCNs and GATs. Such architectures, however, cannot easily scale to large real-world graphs. On the other hand,  shallow (or node-level) models using ego features and adjacency embeddings work well in heterophilous graphs. In this work, we propose a novel scalable shallow method -- GLINKX -- that can work both on homophilous and heterophilous graphs. GLINKX leverages (i) novel monophilous label propagations (ii) ego/node features, (iii) knowledge graph embeddings as positional embeddings, (iv) node-level training, and (v) low-dimensional message passing. Formally, we prove novel error bounds and justify the components of GLINKX. Experimentally, we show its effectiveness of it on several homophilous and heterophilous datasets.

Under review as a conference paper at ICLR 2023
GLINKX: A SCALABLE UNIFIED FRAMEWORK FOR HOMOPHILOUS AND HETEROPHILOUS GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
In graph learning, there have been two predominant inductive biases regarding graph-inspired architectures: On the one hand, higher-order interactions and mes- sage passing work well on homophilous graphs and are leveraged by GCNs and GAT's Such architectures, however, cannot easily scale to large real-world graphs. On the other hand, shallow (or node-level) models using ego features and adjacency embeddings work well in heterophilous graphs. In this work, we propose a novel scalable shallow method GLINKX that can work both homophilous and heterophilous graphs. GLINKX leverages (i) novel monophilous label propagations (ii) ego/node features, (iii) knowledge graph embeddings as positional embeddings, (iv) node-level training, and (v) low-dimensional message passing. Formally, we prove novel error bounds and justify the components of GLINKX. Experimentally, we show its effectiveness on several homophilous and heterophilous datasets.
INTRODUCTION
In recent years, graph learning methods have emerged with a strong performance for various ML. tasks. Graph ML methods leverage the topology of graphs underlying the data (Battaglia et al., 2018) to improve their performance. Two very important design options for proposing graph ML based architectures in the context of node classification are related to whether the data is homophilous or heterophilous.
For homophilous data where neighboring nodes share similar labels (McPherson et al., 2001; Altenburger & Ugander, 2018a) - Graph Neural Network (GNN)-based methods are able to achieve high accuracy. Specifically, a broad subclass sucessfull GNNs are Graph Convolutional Networks (GCNs) (e.g., GCN, GAT, etc.) (Kipf & Welling, 2016; Veličković et al., 2017: Zhu et al., 2020). In the GCN paradigm, message passing and higher-order interactions help node classification tasks in the homophilous setting since such inductive biases tend to bring the learned representations of linked nodes close to each other. However, GCN-based architectures suffer from scalability issues. Performing (higher-order) propagations during the training stage hard to scale in large graphs because the number of nodes grows exponentially with the increase of the filter receptive field. Thus, for practical purposes, GCN-based methods require node sampling, substantially increasing their training time. For this reason, architectures (Huang et al., 2020; Zhang et al., 2022b; Sun et al., 2021; Maurya al., 2021; Rossi al., 2020) that leverage propagations outside of the training loop (as preprocessing step) have shown promising results in terms of scaling to large graphs
In heterophilous datasets (Rogers al., 2014), the nodes that connected tend to have different labels. Currently, many works that address heterophily can be classified into two categories concerning scale. On the one hand, recent successful architectures (in terms of accuracy) (Jin al., 2022a; Di Giovanni et al.. 2022; Zheng et al., 2022b; Luan et al., 2021; Chien et al., 2020; Lei et al.. 2022) that address heterophily resemble GCNs in terms of design and thus suffer from the same scalability issues. On the other hand, shallow or node-level models (see, e.g., (Lim et al., 2021; Zhong et al., 2022)), i.e., models that are treating graph data as tabular data and do not involve propagations during training, has shown a lot of promise for large heterophilous graphs. In (Lim et al., 2021). it is shown that combining ego embeddings (node features) and adjacency embeddings works in the heterophilous setting. One element that LINKX exploits via the adjacency embeddings is monophily (Altenburger & Ugander, 2018a;b), namely the similarity of the labels of a node's neighbors. However, their design is still impractical in real-world data since the method (LINKX) is not inductive (see Section 2),

---

Under review as a conference paper at ICLR 2023
and embedding the adjacency matrix directly requires many parameters in model. In LINKX, the adjacency embedding of a node can alternatively be thought of as a positional embedding (PE) of the node in the graph, and recent developments (Kim et al., 2022; Dwivedi et al., 2021; Lim et al., 2021) have shown the importance of PEs in both homophilous and heterophilous settings. However, most of these works suggest PE parametrizations that are difficult compute in large-scale settings. We argue that PEs can be obtained in a scalable manner by utilizing knowledge graph embeddings, which, according to prior work, can (El-Kishky et al., 2022; Lerer et al., 2019; Bordes al., 2013; Yang et al., 2014) be trained in very large networks.
Goal Contribution: In this work, we develop scalable method for node classification that: (i) works both on homophilous and heterophilous graphs, (ii) is simpler faster than conventional message passing networks (by avoiding the neighhor sampling and message passing overhead during training), and (iii) can work in both transductive and an inductive' setting. For method to be scalable, we argue that should: (i) run models on node-scale (thus leveraging i.i.d. minibatching), (ii) avoid doing message passing during training and do a constant number of times before training. and (iii) transmit small messages along the edges. Our proposed method GLINKX (see Section 3) combines all the above desiderata. GLINKX has three components: (i) ego embeddings (ii) PEs inspired by architectures suited for heterophilous settings, and (iii) scalable 2nd-hop- End-hop-neighhorhoodd propagations inspired by architectures suited for monophilous settings (Section 2.5). We provide novel theoretical error bounds and justify components of our method (Section 3.4). Finally, we evaluate GLINKX's empirical effectiveness on several homophilous and heterophilous datasets (Section 4).
2
PRELIMINARIES
2.1 NOTATION
We denote scalars with lower-case, vectors with bold lower-case letters, and matrices with bold upper- case. We consider directed graph G = G(V, E) with vertex set V with [V] nodes, and edge set E with E = m edges, and adjacency matrix A. X E Raxdx represents the dx-dimensional features and P R=xdp represent the dp-dimensional PE matrix. A node has feature vector I; E Rdx and a positional embedding P: E Rd and belongs to a class y; E {L....,c) c}. The training set denoted by Guran Vurain(uaann (Vrzinn Furan), the validation set by (Saaia(Valla Evatia); and test set by Grese( (V (Viet; E I(.} is the indicator function. r. is the c-dimensional simplex.
2.2 GRAPH CONVOLUTIONAL NEURAL NETWORKS
In homophilous datasets, GCN-based methods have been used for node classification. GCNs (Kipf & Welling, 2016) utilize feature propagations together with non-linearities to produce node embeddings. Specifically, GCN consists of multiple layers where each layer collects i-th hop information from the nodes through propagations and forwards this information to the i + 1-th layer. More specifically, if G has a caameetrccallynoomaiiiee adjacency matrix A'ym (with self-loops) (ignoring the directionality of edges), then a GCN layer has the form
H X, H++1) (A HOOWly Vi E [4], Y = ssotmaa (H!!)).
Here (0) is the embedding from the previous layer, ( is a learnable projection matrix and (-)) a non-linearity (e.g. ReLU, sigmoid, etc.).
2.3 LINKX
In heterophilous datasets, the simple method of LINKX has been shown to perform well. LINKX combines two components MLP on the node features X and LINK regression (Altenburger & Ugander, 201 8a) on the adjacency matrix as follows:
For this paper, we operate in the transductive setting. See App. B for the inductive setting.
We use ego embeddings and node features interchangeably.
2

---

Under review as a conference paper at ICLR 2023
Algorithm 1 GLINKX Algorithm
Input: Graph G(V, E)) with train set Virain S V. node features X, labels Y
Output: Node Label Predictions Yima
1st Stage (KGEs). Pre-train knowledge graph embeddings P with Pytorch Biggraph.
2nd Stage (MLaP). Propagate labels and predict neighbor distribution
1. MLaP Forward: Calculate the distribution of each training node's neighbors, i.e.
Dt LyeVinn (, Finis V)
(J Em for all V
2. Learn distribution of node's neighbors:
(a) For each epoch, calculate ÿ. = (ar, pi; 01) for i E Vimin
(b) Update the parameters s.t. the negative cross-entropy
1 (01)
Σiev Vmm CB(U: D:: 81) is maximized in order to bring ye statistically
close to ÿt.
(c) Let Oj be the parameters the end of the training that correspond to the epoch with the best validation accuracy.
Leevin for all Virain- where
3. MLaP Backward: Calculate y [LEVI(
Dj - fi Pj; 0.).
3rd Stage (Final Model). Predicting node's own label distribution:
1. For each epoch, calculate yinal, = fa( Pt: t.:y 02).
2. Update the parameters s.t. the negative cross-entropy
2CE,2 (02) = DieVin CE(y;, Mimul,;; 02) ) maximized.
Return final
Hx MLPx(X), HA = ML)x((), Y ResNet HA).
2.4 NODE CLASSIFICATION
In node classification problems on graphs, we have model f(X, Yusin: A; A; that takes input the node features X, the training labels Yuain and the graph topology A and produces a prediction for each node i of G, which corresponds to the probability that a given node belongs any of c classes (with the sum of such probabilities being one). The model is trained with back paok-propagation. Once trained, the model can be used for the prediction of labels of nodes in the test set.
There are two training regimes: transductive and inductive. In the transductive training regime, we have full knowledge of the graph topology (for the train, test, and validation sets) and the node features, and the task is to predict the labels of the validation and test set. In the inductive regime, only the graph induced by Viainn is known at the time of training, and then the full graph revealed for prediction the validation and test sets. In real-world scenarios, such as online social networks, the dynamic nature of problems makes the inductive regime particularly useful.
2.5 HOMOPHILY, HETEROPHILY & MONOPHILY
Homophily and Heterophily: There various measures of homophily in the GNN literature like node homophily and edge homophily Lim et al. (2021). Intuitively, homophily in a graph implies that nodes with similar labels are connected. GNN-based approaches like GCN, GAT, etc., leverage this property to improve the node classification performance. Alternatively, if a graph has low homophily namely, nodes that connect tend to have different labels it is said to be heterophilous. In other words, graph is heterophilous if neighboring nodes do not share similar labels.
Generally, we define a graph be monophilous if the label of node similar to that of its neighbors' neighbors?. Etymologically. the word "monophily" is derived from the Greek words " "monos" " (unique) and "philos" " (friend), which our context means that a node regardless of its label has neighbors of primarily one label. In the context of directed graph, monophily can be
Monophily:
A similar definition of monophily has appeared in (A (Altenburger & Ugander, 10),,, whereby many nodes have extreme preferences for connecting certain class.
3

---

Under review as a conference paper at ICLR 2023
Original Graph
Positional Embeddings
1tt Stage
Eath R
V'LiEVrrainn
Propagation
43
Ochey
P
PEs
fi
(chee
Loss
Vtheev traan
Propagation #2
X
Ego
LCE,1
Fronat
P
PEs
f2
Lass Leau
X
Ego
1 1.8% Vauacl HI
(b) 2nd Stage
(c) 3rd Stage
Figure 1: Block Diagrams of GLINKX stages.
thought of as structure that resembles Fig. 2(a) where similar nodes (in this case, three green nodes connected to yellow node) are connected to a node with a different label.
We argue that encoding monophily into model homophilous graphs (see Figs. 3(b) and 3(c)), which one of the main motivators behind our work. In homophilous graphs, monophily will fundamentally encode the 2nd-hop neighbor's label information, and since in such graphs, neighboring nodes have similar labels, it can provide a helpful signal for node classification. neighbors may share the same label, providing helpful information for node classification. Monophily effective for heterophilous graphs (Lim al., 2021). Therefore, an approach encoding monophily has an advantage over methods designed specifically for homophilous and heterophilous graphs, especially when varying levels of homophily can exist between different sub-regions the same graph (see Section 3.3). It may also not be apparent if the (sub-)grua -rrph is purely hommphilousshhctropphllooo (since these are not binary constructs), which makes a unified architecture that can leverage graph information for both settings all the more important.
be helpful for both heterophilous and
heterophily, neighboring nodes have different labels, but the 2nd-hop
METHOD
3.1 COMPONENTS & MOTIVATION
The desiderata laid down Section be realized by three components: (i) PEs, (ii) ego embeddings, and (iii) label propagations that encode monophily. More specifically, ego embeddings and PEs are used as primary features, which have been shown work for both homophilous and heterophilous graphs for the models we end up training. Finally, the propagation step is used to encode monophily provide additional information to our final prediction.
Positional Embeddings: We use PEs to provide our model information about the position of each node and hypothesize that PEs are an important piece of information in the context of large-scale node classification. PEs have been used to help discriminate isomorphic graph (sub)-structures (Kim et al., 2022; Dwivedì et al., 2021; Srinivasan & Ribeiro, 2019). This useful both homophily (Kim et al., 2022; Dwivedi et al., 2021) and heterophily (Lim et al., 2021) because isomorphic (sub)-structures can exist both the settings. In the homophilous case, adding positional information can help distinguish nodes that have the same neighborhood but distinct position (Dwivedi et al., 2021; Morris et al., 2019; Xu et al., 2019), circumventing the need to do higher-order propagations (Dwivedi et al., 2021: Li al., 2019; Bresson & Laurent, 2017) which 2021). ). In heterophily, structural similarity among nodes is important for classification, as in the case of LINKX where adjacency embedding be considered a PE. However, in large graphs, using
prone to over over-squashing (Alon & Yahav,
4

---

Under review as a conference paper at ICLR 2023
adjacency embeddings Laplacian eigenvectors (as methods such as (Kim et al., 2022) suggest) can be a computational bottleneck and may be infeasible.
In this work, we leverage knowledge graph embeddings (KGEs) to encode positional information about the nodes, and embed the graph. Using KGEs has two benefits: Firstly, KGEs can be trained quickly for large graphs. This is because KGEs compress the adjacency matrix into fixed-sized embedding, and adjacency matrices have been shown to be effective in heterophilous cases. Further, KGEs are lower-dimensional than the adjacency matrix (e.g., dp ~ 102), allowing for faster training and inference times. Secondly, KGEs can be pre-trained efficiently on such graphs (Lerer et al., 2019) and can be used off-the-shelf for other downstream tasks, including node classification (EI- Kishky et al.. 2022)*. So, in the 1st Stage of our methods in Alg. 1 (Fig. (a)) we train KGEs model on the available graph structure. Here, we fix this positional encoding once they are pre-trained for downstream usage. Finally, we note that this step is transductive but we can easily make it inductive (EI-Kishky et al., 2022; Albooyeh et al., 2020).
Ego Embeddings: We get ego embeddings from the node features. Such embeddings have been used in homophilous and heterophilous settings (Lim et al., 2021; Zhu et al., 2020). Node embeddings are useful for tasks where the graph structure provides little/no information about the task.
Monophilous Label Propagations: We now propose a novel monophily (refer Section 2.5) inspired label propagation which we refer to as Monophilous Label Propagation (MLaP). MLaP has the advantage that we can use both for homophilous and heterophilous graphs or in a scenario with varying levels of graph homophily (see Section 3.3) as it encodes monophily (Section 2.5).
To understand how MLaP encodes monophily, we consider the example in Fig. 2. In this example, we have three green nodes connected to yellow node and two nodes of different colors connected to the yellow node. Then, one way to encode monophily in Fig. 2(a) while predicting label for je. & E (5), is to get distribution of labels of nodes connected to node i thus encoding its neighbors distribution. The fact that there are more nodes with green color than other colors can be used by the model to make a prediction. But this information may only sometimes be present, or there may be few labeled nodes around node i. Consequently, we propose to use a model that predicts the label distribution of nodes connected to We use the node features (æ;) and PE (p,) of node i to build this model since nodes that are connected to node i share similar labels, and thus, the features of node i must be predictive of its neighbors. So, in Fig. 2(a), we train a model to predict distribution of i's neighbors. Next, we provide je the learned distribution of i's neighbors by propagating the learned distribution from back to je. Eqs. (I) to (3) correspond to MLaP. We train a final model that leverages this information together with node features and PEs (Fig. 2(b)).
3.2 OUR METHOP:: GLINKX
We put the components discussed in Section 3.1 together into three stages. In the first stage, we pre-train the PEs by using KGEs. Next, encode monophily into our model by training a model that predicts node's neighbors' distribution and by propagating the soft labels from the fitted model. Finally, we combine the propagated information, node features, and PEs to train a final model. GLINKX described in Alg. and consists of three main components detailed as block diagrams in Fig. 1. Fig. 2 shows the GLINKX stages from Alg. I on a toy graph:
1st Stage (KGEs): We train DistMult KGEs with Pytorch-Biggraph (Yang et al., 2014) treating as a knowledge graph with only one relation (see App. A.4 for more details). Here we have decided to use DistMult, but one can use their method of choice to embed the graph.
2nd Stage (MLaP): First (2nd Stage in Alg. 1, Fig. 1(b), and Fig. 2(a)), for node we want to learn the distribution of its neighbors. To achieve this, we propagate the labels from a node's 's neighbors (we call this step MLaP Forward), i.e. calculate
EjeVin (fA) Di
g. = Hi E Virain (j,i) E E
Vi E Virain
*Positional information can also he provided by other methods such as node2vec (Grover & Leskovec, 2016). however, most of such methods less scalable.
5

---

Under review as a conference paper at ICLR 2023
j1
j2
j4
js
y/4
5'5'5' Nhsinal P1o
[1,0,00]]
1.0.0.01100110000
j2
j3
j+
is
[1,0,0,0]
[0,0,1,0]
111 5'5'3'0
9
5 5'5'5'
= yi = f((UP)
(a) MLaP Forward Neighbor Model
(b) MLaP Backward & Final Model
Figure 2: Example. For node i we want to learn model that takes i's features æ; [2x and PEs P: E Rddr and predict a value Yr E IR that matches the label distribution of it's neighbors neighbors Y; using shallow model. Next, distribution of node back to its neighbors and use it together with the ego features and the PEs to make prediction about node's own label. We propagate ÿi to its neighbors ji js. For example, for j1, we encode the propagated distribution estimate y. from to form y/ We predict the label by using y J1 P/
want propagate (outside the training loop) the (predicted)
Then, we train a model that predicts the distribution of neighbors, which we denote with ÿs using the ego features (Es and the PEs {p: Vevin and maximize the negative cross-entropy with treating (Úi):Ev.n. as ground truth labels, namely we maximize
LCE. (01) - Σ Σ
D., log(Da))
iE Vinia LE|e]
where 0; = (x:: P;;
01) 01) and 01 E O₂ is a learnable parameter vector. Although in this paper we assume to be in the transductive setting, this step allows us to be inductive (see App. B). In Section 3.4 we give theoretical justification of this step, namely "why is it good to use parametric model to predict the distribution of neighbors?".
Finally, we propagate the predicted soft-labels ÿi back to the original nodes, i.e. calculate
EjEVILnEE DS y (JEV:(..)) FH
Vi Virain
where the soft labels {Ū. Jivima have been computed with the parameter 01 of the epoch with the best validation accuracy from model fi (-)))) We call this step MI.P Backward.
3rd Stage (Final Model): We make the final predictions yiuui, f2(2; Pi: vl: 02) by combining the
ego embeddings, PEs, and the (back)- (lock)-propee propaggtee soft labels (0, is a learnable parameter vector). We
use the soft-labels Y, instead of the actual labels one-hot (ys) in order to avoid label leakage, which
hurts performance (see also (Shi et al., 2020) for different way to combat label leakage). Finally, we maximize the negative cross-entropy with respect node's own labels.
2CE)
Σ
Σ
I( = 13 (egn) i,1),
(4)
VE VEVA LE(A]
Overall, Stage 2 corresponds to learning the neighbor distributions and propagating these distributions, and Stage uses these distributions train new model which predicts a node's 's labels. In Section 3.4, prove that such two-step procedure incurs lower errors than directly using the features to predict a node's 's labels.
Scalability: GLINKX is highly scalable as it performs message passing constant number of times by paying an O(mc) cost, where the dimensionality of classes is usually small (compared to dx that GCNs rely on). In both Stages 2 and 3 of Alg. 1. we train node-level MLPs, which allow to leverage i.id. (row-wise) mini-batching, like tabular data, and thus our complexity is similar to other shallow methods (LINKX, FSGNN) (Lim al., 2021; Maurya et al., 2021). This, combined with the

---

Under review as a conference paper at ICLR 2023
Disribution
Homophlly
Class Homoptly
(a) Node and class homophily
(b) Homophilous example (c) Heterophilous example
Figure 3: Top: Node and class homophily distributions for the yelp-chi dataset. Bottom: Examples of homophilous (Fig. 3(b) and a heterophilous (Fig. 3(c)) region the same graph that are both monophilous, namely they connected to many neighbors of the same kind. In spam network, the homophilous region corresponds to many non-spam reviews connecting to non-spam reviews (which the expected behaviour of non-spammer user), and the heterophilous region corresponds to spam reviews targeting non-spam reviews (which is the expected behaviour of spammers), thus, yielding a graph with both homophilous and heterophilous regions such in Fig. ((a).
propagation outside the training loops, circumvents the scalability issues of GCNs. For more details, refer App. A.3.
3.3 VARYING HOMOPHILY
Graphs with monophily experience homophily, heterophily, or both. For instance, the yelp-chi dataset where we classify review as spam/non-spam (see Fig. 3) we observe case of monophily together with varying homophily. Specifically in this dataset, spam reviews are linked to non-spam reviews. and non-spam reviews usually connect other non-spam reviews, which makes the node homophily distribution bimodal. Here the 2nd-order similarity makes the MLaP mechanism effective.
3.4 THEORETICAL ANALYSIS
Justification of Stage 2: In Stage 2, we train a parametric model to learn the distribution of node's neighbors from the node features E. Arguably, we can learn such distribution naïvely by counting the neighbors that belong to each class. This motivates our first theoretical result. In summary, we show that training a parametric model for learning the distribution of node's neighbors (as in Stage 2) yields a lower error than the naïve solution. Below we present the Thm. (proof App. F) for undirected graphs (the case of directed graphs is the same, but we omit it for simplicity of exposition):
Theorem 1. Let G([r], E) be an undirected graph of minimum degree K >> 2² and let Q; E I be the likelihood, from the viewpoint of node of any node its neighborhood ( to assigned to different classes for every node i E [n). The following two facts are true (under standard assumptions for SGD and the losses):
E (n], we have that maxjeld EllQr, Qi,1] < TE @:1lo0)5 ( / Kc) 1. Let Q be the sample average of Q i.e. Qu, = WiJ ELEN(O) 18 =j.. Then, for every
(Vieet
K
2. Let q(-1E;;0) O) be a model parametrized by RDD that uses the features & of each node i to predict Q, We estimate the parameter 0, by running SGD for = n steps to maximize L(0) 1 _ Eÿ=1 Q4,f log q(ilE:: 0). Then, for every [n], we have that
maxjele| E[q(i: E,; 01) Qu, 0
logn n
'In Scction 3.1, E:s correspond the augmented features & [a> Pp]
7

---

Under review as a conference paper at ICLR 2023
It is evident here that if the minimum degree K is much smaller than n. then the parametric model has lower error than the naive approach, namely O(n-1/3) compared to 0/22)
Justification of Stages 2 and 3: We now provide theoretical foundations for the two-stage approach. Specifically, we argue that two-stage procedure involving learning the distribution of a node's s 2nd-hop neighbor distributions (we assume for simplicity, again, that the graph is undirected) first with a parametric model such as in Thm. 1, and then running two-phase algorithm to learn parametric model that predicts a node's label, yields a lower error than naively training a shallow parametric model to learn a node's labels. The first phase of the two-phase algorithm involves training the model first by minimizing the cross-entropy between the predictions and the 2nd-hop neighborhood distribution. Then the model trains joint objective that uses the learned neighbor distributions and the actual labels starting from the model learned in the previous phase.
Theorem 2. Let G(mm], E) be an undirected graph of minimum degree K > c² and, let P; be the likelihood of node Thm. 1. Let pl-1š;; w) be model parametrized by w E RD that is used to predict the class assignments y/s ~ p(-(&;;)) w). Let w. be the optimal parameter. The following are true (under standard assumptions for SGD and the losses):
be assigned to a different class, and let Q;.9(-1E;;0:)) defined as in
1. The naive optimization scheme that runs SGD to maximize g(un)
1 -i=1 Ei=1 P.,j logp(j w) for n steps has ervor [[((( - G(w.)] S logn
1
2. The two-phase optimization scheme that runs SGD to maximize G(ww) ExEN(H q(ilEu; 01)) log plgp(,,;; f)r nı steps, to estimate a so- lution wT and then runs SGD on the objective λā(w) + (1 ()G(w) ) for n steps starting from w', achieves error E[G((n++1) [(w-)] S O /Tog i log log
You can find the proof in App. F. We observe that the two-phase optimization scheme can reduce the error by a factor of / log n/ log log n highlighting the importance of using the distribution of the 2nd-hop neighbors of a node predict its label and holds regardless of the homophily properties of the graph. Also, note that the above two-phase optimization scheme differs from the description of the method we gave Alg. 1. The difference is that the distribution of a node's neighbors is embedded into the model in the case of Alg. 1, and the distribution of node's ie neighbors are embedded into the loss function in Thm. 2 as a regularizer. In Alg. 1, we chose to incorporate this information in the model because using multiple losses harms scalability and makes training harder in practice. In the same spirit, the conception of GCNs (Kipf & Welling, 2016) replaces explicit regularization with the graph Laplacian with the topology into the model (see also (Hamilton et al., 2017; Yang et al., 2016)).
3.5 COMPLEMENTARITY
Different components of GLINKX provide a complementary signal to components proposed in the GNN literature (Maurya et al., 2021; Zhang et al., 2022b; Rossi et al., 2020). One can combine GLINKX with cxisting architectures (c.g. feature propagations (Maurya et al., 2021; Rossi et al., 2020), label propagations (Zhang et al., 2022b)) for potential metric gains. For example, SIGN computes a series of r E N feature propagations [X, 4 x² ΦxX] (e.g., normalized adjacency complementary signal, namely, embed each of the propagated features and combine them in the 3rd Stage to GLINKX. Overall, although in this paper want to keep GLINKX simple highlight its main components, we conjecture that adding more components to GLINKX would improve its performance on datasets with highly variable homophily (see Section 3.3).
X] where +b is a matrix preprocessing step. We can include this
normalized Laplacian)
4 EXPERIMENTS & CONCLUSIONS
We experiment with homophilous and heterophilous datasets (see Tab. I and App. D.3). We train KGEs with ertorch-Biggrpp (Lerer et al., 2019; Yang et al., 2014). For homophilous datasets, compare with vanilla GCN and GAT, FSGNN, and Label Propagation (LP). For fair comparison, we compare with one-layer GCNIGAT/FSGNNIPP since our method is one-hop. We also compare with higher-order (h.o.) GCN/GTT/SSNNI/L .P with 2 and 3 layers. In the heterophilous
Comparisons:
8

---

Under review as a conference paper at ICLR 2023
Table I: Experimental results. (*) results from the OGB leaderboard.
Homophilons Datasets
Hoterophilous Datasets
PubMed
ogba-arxiv
squirrel
yelp-chi
arxi--year
19.7K
169.3K
5.2K
169.3K
45,9K
44.3K
1.66M
216.9K
7.73M
1.16M
Edge-in invensiienii homophily (Lim et al., 2021)
0.66
0,02
0.27
dx /cc
200/27
128 /40
2089/5 /
32/2
128/5
GLINKX w/ KGES
87.95 0.33
69.27 0:25
45.83 +
87.82 ::0.20
54.09
1.661
GLINKX w/ Adjacency
88.03 0.33
69.09 10.13
69.15 1.87
89.32 : 1:0.45
53.07
0.29
Label Propogation (1 (1-hop)
83.02 0.33
69.59 0.00
32:22 +: 1:445
85.98 1:0.28
43,71
0:0.2
LINKX (Lim al., 2021))
10.24
1.34
LINKX (our runs)
87:55 00.37
63.91 10.18
61,46 1.60
88.25 2:0.24 NIA
53,78
#0006
GCN w/ Layer
86.43 0.7.4
50.76 10.20
GAT Layer
86.41 #0.53
54.42 1:0.0
N/A
PSGNN w/ Layer
88.93 =0.31
61.88 61.82 0.84
64.06
86,36
3:0.66
42.86 #0.22
Higher-order GCN
86.29 20.46
71.18 +-0.27 (*)
N/A
Higher-order GAT
86.64 00.40
73.66 0.11 (*)
N/A
Higher-order FSGNN
89,37 0.449
69.26 0.336
68.04 +2.19
86.33
+:0.30
44.89 00229
Label Propagation (2-hop)
83.44 0.35
69.78 1.000
43.41 1:1.4
85.95
1:0.26
46.30 1.2.7
Lahel Prop. [(A²
02
1.333
10.00
1.118
1.0.32
Table Ablation Study, We use the hyperparameters the best run from Tab. with KGEs.
Ablation Type
Stages
All
Remove embeddings
Remove propagation
Remove PEs
Heterophilous
arxiv-year arxiv-year
All Stages
54.09 =0.61
$3.52 +:077
50.83 #0.24
39.06 +0.35
3rd Stage
54.09 00.61
53.69 1:0.65
50.83 +0224
49.13 1:110
Homophilous
ogbe-arxiv
All Stages
69.27 =0225
61.26 +0.33
62.70 00.34
63.64 10.18
ogba-arxiv
3rd Stage
69.27 0.25
67.60 +:039
62.70 0.34
69.62 ::0.15
case, we compare with LINKX because it is scalable and is shown to work better than other baselines (e.g., H2GCN, MixHop, etc.) and with FSGNN. Note that we do not compare GLINKX with other more complex methods because GLINKX is complementary to them (see Section 3.5), and we can incorporate these designs into GLINKX. We use a ResNer module to combine our algorithm's 's components from Stages 2 and 3. Details about the hyperparameters we use are in App. C.
In the heterophilous datasets, GLINKX outperforms LINKX (except for arxiv-year, where we are within the confidence interval). Moreover, the performance gap between using KGEs and adjaceney embeddings shrinks as the dataset grows. In the homophilous datasets, GLINKX outperforms 1-layer CCN/GATT/LP/FSGGN and LINKX. In PubMed, GLINKX beats h.o. GCN/GAT and in arxiv-year GLINKX is very close to the performance of GCN/GAT.
Finally, we note that our method produces consistent results across regime shifts. In detail, in the heterophilous regime, our method performs on par with LINKX; however, when we shift to the homophilous regime, LINKX's performance drops, whereas our method's performance continues to be high. Similarly. while FSGNN performs similarly to GLINKX on the homophilous datasets, we observe a significant performance drop on the heterophilous datasets (see arxiv-year).
Ablation Study: We ablate each component of Alg. to see each component's 's performance con- tribution. We use the hyperparameters of the best model from Tab. 1. We perform two types of ablations: (i) we remove each of the components from all stages of the training, and (ii) we remove the corresponding components only from the 3rd Stage. Except for removing the PEs from the 3rd Stage only ogbn-arxiv. all components contribute to increased performance both datasets. Note that adding PEs in the 1st Stage does improve performance, suggesting the primary use case of PEs.
Conclusion: We present GLINKX, scalable method for node classification in homophilous and heterophilous graphs that combines three components: (i) ego embeddings, (ii) PEs, and (iii) monophilous propagations. As future work, (i) GLINKX can be extended in heterogeneous graphs, (ii) use more expressive methods such as attention or Wasserstein barycenters (Cuturi & Doucet, 2014) for averaging the low-dimensional messages, and (iii) add complementary signals.
We have run our method with hyperparameter space that is a subset of the sweeps reported in (Lim et al., 2021) due to resource constraints. A bigger hyperparameter search would improve our results.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Marjan Albooych, Rishab Goel, and Seyed Mehran Kazemi. Out-of-sample representation learning for knowledge graphs. In Findings of the Association for Computational Linguistics: EMNLP 2020, pp. 2657-2666 2020.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. URL http::::///ppeeevviiiii net forum? 1d-1800PhocvH22
Kristen M Altenburger and Johan Ugander. Monophily in social networks introduces similarity among friends-of-freends. Nature human behaviour, 2(4):284-290, 2018a.
Kristen M Altenburger and Johan Ugander. Node attribute prediction: An evaluation of within-versus versus across-network tasks. In NeurlPS Workshop on Relational Representation Learning, 2018b.
Peter W Battaglia, Jessica B Hamrick, Vietor Bapst, Alvaro Gonzalz- Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 1806.v8800.110 012611, 2018.
K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma. The extreme classi- fication repository: Multi-label datasets and code, 2016. URL http: /ttp///aannnaaaaaaaa///// org/ downloads/ //cd www.aa///////////opoooooo tory httll.
Antoine Bordes, Nicolas Usunier, Alberto Carcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 26, 2013.
Xavier Bresson and Thomas Laurent. Residual arXiv:1711.07533, 2017.
gated graph convnets.
arXiv preprint
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07888, 2020.
Marco Cuturi and Amnad Doucet. Fast computation of wasserstein barycenters. In Eric Xing and Tony Jebara (eds.), Proceedings of the 31st International Conference Muchine Learning, volume of Proceedings of Machine Learning Research, pp. 685-693, Bejing, China, 22-24 Jun 2014. PMLR. URL https::///// http:///coceeeeeeeeeeeeeee/.esss mlr press h/////uuurrl44 1.tri.441..............
Francesco Di Giovanni, James Rowbottom, Benjamin Chamberlain, Thomas Markovich, and Michael M Bronstein. Graph neural networks as gradient flows. arXiv preprint arXiv:2206.10991, 2022.
Yingtong Dou, Zhiwei Liu, Li Sun, Yutong Deng, Hao Peng, and Philip S Yu. Enhancing graph neural network-basee fraud detectors against camouflaged fraudsters. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp. 315-324, 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with Iearnable structural and positional representations. arXiv preprint arXhv:2110.07875. 2021.
Ahmed El-Kishky, Thomas Markovich, Serim Park, Chetan Verma, Baekjin Kim. Ramy Eskan- der, Yury Malkov, Frank Portman, Sofía Samaniego, Ying Xiao, et al. Twhin: Embedding the twitter heterogeneous information network for personalized recommendation. arXiv preprint arXiv:2202.05387, 2022.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs Advances in neural information processing systems, 30, 2017.
10

---

Under review as a conference paper at ICLR 2023
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 118 13:22118-22113, 2020.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propa- gation and simple models out-performs graph neural networks. arXiv preprini arXiv:2010. 13993, 2020.
Di Jin, Rui Wang, Meng Ge, Dongxiao He, Xiang Li, Wei Lin, and Weixiong Zhang. Raw-gmn Random walk aggregation based graph neural network. arXiv preprint arXiv:2206.11995. 2022a.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. In International Conference on Learning Representations, 2022b. URL https:/ http//pppeeeeeeeeeeeeeeeeeeeeeee net http:/wwwweeeeeeeeeeeeeeeee forum?id-@1Ex3JJo
Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. arXiv preprint arXiv:2207.02500 2022.
Thomas Kipf and Max Welling. Semi cumi--uperviied classification with graph convolutional networks. arXiv preprint 1609.0296000 2016.
Jon M Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5):604-632, 1999.
Runlin Lei, Zhen Wang. Yaliang Li, Bolin Ding, and Zhewei Wei. Evennet: Ignoring odd-hop neighbors improves robustness of graph neural networks. arXiv preprint arXiv:2205. 13892, 2022.
Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. hytorch-biggraan A large scale graph embedding system. Proceedings of Machine Learning and Systems, I: 1:120-131, 2019.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9267- 9276, 2019.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-War Chang, and Doina Precup. heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint (00.:2209900644: 2021.
Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Improving graph neural networks with simple architecture design. arXiv preprint arXiv:2/05.07634 2021.
Miller McPherson, Lynn Smith-Lovin, and James M Cook. Birds of feather: Homophily in social networks. Annual review of sociology, pp. 415-444, 2001.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602-4609, 2019.
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.
Everett M Rogers, Arvind Singhal, and Margaret M Quinlan. Diffusion of innovations. In An integrated approach to communication theory and research, pp. 432-448. Routledge, 2014.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard. Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint S5t1:2004.111999 7:15, 2020.
11

---

Under review as a conference paper at ICLR 2023
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnab014, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rat Collective classification in network data. Al magazine, 29(3):93-93, 2008
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong. Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03500 2020.
Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference on world wide web, pp. 243-246, 2015.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. arXiv preprint arXiv:1910.00452, 2019.
Chuxiong Sun, Hongming Gu, and Jie Hu. Scalable and adaptive graph neural networks with self-label-enhanced training. arXiv preprini arXiv: 104.02300 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint
2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https: //openreview. net /
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6575, 2014.
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.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old MLPs new tricks via distillation. In International Conference on Learning Representations, 2022a.
URL https::///// wpwpreveeneeeeeeeeeeeeeeeeeeeeem net rurum? 1dd4-6.6. 4d= 5HBWPCH.
Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. Graph attention multi-layer perceptron. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022b.
Wenqing Zheng, Edward W Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node representations with incomplete or missing neigh- borhoods. In International Conference on Learning Representations, 2022a. URL https: //openrevies eew. net. forum? i d=1 uggmmm
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07082, 2022b.
Zhiqiang Zhong, Sergey Ivanov, and Jun Pang. Simplifying node classification on heterophilous graphs with compatible label propagation. arXiv preprint (tti::2005009888 2022.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804, 2020.
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 2021.
Intelligence, volume 35, pp.
12


Reviews:
[{"review_id": "upeRb_jBQU", "reviewer": "Reviewer_E2RU", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 LINKX by considering the monophily with monophilous label propagation. A graph is monophilous if the label of a node is similar to that of its neighbors’ neighbors.  To this end, it proposes two stages label propagations to meet the monophily property. Experimental evaluations show the marginal performance improvement.\n", "summary_of_the_review": "My main concerns are the weak novelty, poor writing and insufficient evaluations.\n", "strength_and_weaknesses": "Strength\n- It is interesting to make LINKX both inductive by using label propagation.\n\nWeaknesses \n- This is not the first to consider monophily in GNNs, such as H2GCN and EvenNet, although this may be the first to imcorporate it with label propagation.\n- The writing and organization are poor. Many components are redundant, such as the propagation formula in main body, algorithm and figure 1.\n- Some parts of the paper is not clear, such as the meaning of Figure 3.\n- The experimental evaluations are insufficient. The employed datasets are too little. Besides, the performance improvements is marginal compared with LINKX.", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "sjeYPqhtmZ0", "reviewer": "Reviewer_shiF", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper proposes a method GLINKX that combines knowledge graph embedding, ego embeddings, and label propagation to tackle node classification on both homophily and heterophily graphs. Experiments are conducted on several OGB benchmarks and show some effectiveness.", "summary_of_the_review": "Regarding the details of some weaknesses above:\n- Using knowledge graph embeddings as the pre-trained position encodings does not make sense, especially on the datasets where no knowledge can be used for pre-training, e.g., Cora, Citeseer, etc. There's no relation semantic at all.\n- On homophily graphs, the proposed method actually does not perform better even than a two-layer GCN. On heterophily graphs, the proposed method performs better than the baseline methods used in the paper, but there are many other more powerful GNN models in the literature and the authors are suggested to compare with those methods.\n\n", "strength_and_weaknesses": "Strength:\n- The proposed method is light-weight and thus can be used for large graphs.\n\nWeaknesses:\n- The proposed method is not applicable to many graphs as it requires knowledge graph embeddings to provide node positional encodings. \n- The novelty of the paper is quite limited. It's a incremental combination of the existing methods.\n- Experimental results do not show better performance on homophily graphs.\n- On heterophily graphs, there are lots of many other approaches that need to be compared with.", "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": "cS1BWfULl01", "reviewer": "Reviewer_XQ6r", "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 studies the problem of GNNs under homophily and heterophily and the authors propose a scalable unified framework named GLINKX for this problem. The proposed GLINKX works in three separate stages:\n- Making use of KEG to learn positional embeddings.\n- Propagating information about labels from node's neighbors.\n- Propagating the predicted labels and making final predictions.\n\nGLINKX is also guaranteed with theories. Experimental studies on large-scale homophilous and heterophilous graphs demonstrate the effectiveness and efficiency of the proposed method.", "summary_of_the_review": "This paper studies an interesting and important problem. Overall this paper is well-organized and easy to read. Experiments from different aspects have been conducted. However, I have some concerns about the novelty and the selection of one component. Therefore, I will recommend a weak rejection of the paper, which I am willing to turn into an acceptance if all issues are addressed.", "strength_and_weaknesses": "Strengths:\n- The paper is well-organized and easy to follow and the target problem of GNNs for homophilous and heterophilous graphs is very important.\n- The proposed method is effective and efficient in handling homophily and heterophily of large-scale graphs with some theoretical guarantee.\n- Extensive experiments have been conducted to demonstrate the superiority of the proposed method from different aspects.\n\nWeakness:\n- The novelty of this paper is limited: the proposed framework is the combination of KGEs and LP.\n- There are different ways to get positional embeddings, i.e., the embeddings that can preserve global/local structures of graphs. For example, traditional structural role discovery methods such as RolX [1] and network embedding methods such as node2vec [2]. So the questions are:\n1) what are the reasons to make use of KGEs as PEs?\n2) it is possible to compare different PEs?\n- If there are errors/noises from the 1st stage of PEs, is it possible to handle the noises in the following stages?\n\nThere are also some minor concerns:\n- Page 3: what is the meaning of \\epsilon?\n- Page 4: circumventing the to do\n- Page 5: Alg. 1 (??)\n\n[1] RolX: Structural Role Extraction & Mining in Large Graphs\n\n[2] node2vec: Scalable Feature Learning for Networks\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VMpw5oQ9G-W", "reviewer": "Reviewer_gBBT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The paper proposes an extension of LINKX to be robust on both heterophilic and homophilic graphs.", "summary_of_the_review": "The paper proposes an extension of LINKX model to address both heterophily and homophily. However, the paper requires significant rewrite to clearly highlight how the algorithm works and why should we expect it to work for heterophilic scenario. The experiment should still compare with non-scalable methods on datasets which are small enough. Also, the paper should report training time, memory usage etc. to understand the scalability aspect of the model.\n\nAs it stands, I am inclined to reject the paper.", "strength_and_weaknesses": "# Strengths:\n1. Building scalable shallow method is a very important problem in the area of Graph Neural Networks.\n# Weaknesses:\n1. The paper and the algorithm are both difficult to follow and understand.\n2. Since scalability is the primary goal, some information on training time, memory usage etc. would have been useful.\n3. Albeit, the related work cites several papers, but comparison seems to drop them due to the fact that these methods are not scalable. However, there are a few datasets of fairly small size in the experiment, so at least for those, the numbers for these other methods can still be reported, if only to understand whether there is a trade-off involved between accuracy and scalability, and how much is it?", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject