Predicting Global Label Relationship Matrix for Graph Neural Networks under Heterophily
Authors: Langzhang Liang
Xiangjing Hu
Zenglin Xu
Zixing Song
Irwin King
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural networks
heterophily problem
global label relationship matrix
TL;DR: In this paper, graph convolution is performed with a predicted global label relationship matrix.

Abstract: Graph Neural Networks (GNNs) have been shown to achieve remarkable performance on node classification tasks by exploiting both graph structures and node features. The majority of existing GNNs rely on the implicit homophily assumption. Recent studies have demonstrated that GNNs may struggle to model heterophilous graphs where nodes with different labels are more likely connected. To address this issue, we propose a generic GNN applicable to both homophilous and heterophilous graphs, namely Low-Rank Graph Neural Network (LRGNN). Our analysis demonstrates that a signed graph's global label relationship matrix has a low rank. This insight inspires us to predict the label relationship matrix by solving a robust low-rank matrix approximation problem, as prior research has proven that low-rank approximation could achieve perfect recovery under certain conditions. The experimental results reveal that the solution bears a strong resemblance to the label relationship matrix, presenting two advantages for graph modeling: a block diagonal structure and varying distributions of within-class and between-class entries.

Predicting Global Label Relationship Matrix for Graph Neural Networks under Heterophily
Langzhang Liang
Xiangjing Hu
Harbin Institute of Technology, Shenzhen lezylaliang@mail.cc com
Harbin Institute of Technology. Shenzhen starry hxj @gmail. com
Zenglin Xu*
Harbin Institute of Technology, Shenzhen & Pengcheng Lab zenglin@gmaile com
Zixing Song The Chinese University of Hong Kong zxsongâcse. cuhk. edu. hk
Irwin King
The Chinese University of Hong Kong kingêcse. cuhk, edu. hk
Abstract
Graph Neural Networks (GNNs) have been shown to achieve remarkable per- formance on node classification tasks by exploiting both graph structures and node features. The majority of existing GNNs rely the implicit homophily assumption. Recent studies have demonstrated that GNNs may struggle to model heterophilous graphs where nodes with different labels are more likely connected. To address this issue, we propose generic GNN applicable to both homophilous and heterophilous graphs, namely Low-Rank Graph Neural Network (LRGNN). Our analysis demonstrates that a signed graph's 's global label relationship matrix has low rank. This insight inspires to predict the label relationship matrix by solving a robust low-rank matrix approximation problem, as prior research has proven that low-rank approximation could achieve perfect recovery under certain conditions. The experimental results reveal that the solution bears strong resemblance to the label relationship matrix, presenting two advantages for graph modeling: a block diagonal structure and varying distributions of within-class and between-class entries.
1 Introduction
Graphs (or networks) ubiquitous in various fields, such social networks [TTang et al., 2013, Xu et al., 2015, 2019b), biology [Guzzi and Zitnik, 2022), and chemistry [Gilmer et al., 2017]. Many real-world networks follow the Homophily assumption, i.e., linked nodes tend to share the same label or have similar features; while for graphs with heterophily, nodes with different labels are more likely form link. For example, many people tend connect with people of the opposite sex in dating networks. Graph Neural Networks (GNNs) [Kipf and Welling, 2017, Velickovic et al., 2018] have shown significant success in tackling diverse set of graph mining tasks, such as NLP [Song and King, 2022, Chen et al., 2023] and clustering [Huang et al., 2023, Kang et al., 2020]. There are also studies dedicated to enhancing the representational power of GNNs [Liang al., 2023, Xu al., 2019a]. Recently, researchers have observed that GNNs may face difficulties in learning on graphs
"Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1
+
1
2
+
-1
-1
T
T2
T3
T4
approa 2)
Class
Class
O Class
Positive Link
Negative Link
LRGNN:
H ZH
Figure Undirected signed triads. Structural balance theory states that Ti and T2 are balanced, whereas Ta and 74 are unbalanced. Weak balance states that only T3 is unbalanced. Clearly, triads of signed graphs obey weak balance. Consequently, the label relationship matrix Z exhibits low-rank structure. Then Z can be recovered by low-rank approximation.
with heterophily due to the smoothing operation, which tends generate similar node representations for adjacent nodes, even though their labels differ [Abu-EI-Haijp et al., 2019, Zhu et al., 2020].
Various designs [Zhu et al., 2020, Chien et al., 2021, Lim et al., 2021] have been proposed to enhance the performance of GNNs under heterophilous scenarios (see Zheng al. [2022] for survey). Among them, high-pass filters are the most frequently used components as they can push away node from its neighbors in the embedding space, aligning with the characteristic of heterophily. Spectral-based -based methods [Chien et al., 2021, Luan et al., 2021] combine high-pass filters with low-pass ones by fusing the outputs from intermediate layers. However, these methods cannot capture the node-level homophily ratio, as they use only one convolutional filter type in each layer. Alternatively, some methods [Bo et al., 2021, Yang et al., 2021] enable neural networks to learn the aggregation coefficients. Specifically, these methods update node representation by computing a learned signed weighted combination of neighbors' representations by adopting graph attention function [Velickovic et al., 2018). However, the graph attention function has been proven compute form of static attention: the ranking of attention scores remains unconditioned on the query [Brody et al., 2022].
According to Zhu et al. [2020], under specific conditions, a node's ' 2- 2-hop neighborhood is expected to be predominantly homophilic. To capitalize on this result, they suggest amplifying a node's influence using its 2-hop neighbors. Building on this, GloGNN [Li et al., 2022] introduces subspace clustering approach to derive global coefficient matrix. Nonetheless, Liu et al. [2010] proves that this matrix's 's between-clat entries are almost zero. This indicates that while GloGNN taps into global homophily, it rarely employs remote heterophilous nodes for feature propagation. Moreover, the subspace clustering approach ensures dense within-class matrix entries but does not account for the sign of these entries.
In this paper, we aim at recovering a global label relationship matrix 2 such that Z.j if node U; and Vj have the same label (homophilous) and -1 otherwise (heterophilous). In this case, we exploit global homophily and heterophily by assigning proper signs. Determining 2.j. which requires knowledge node labels, seems impractical due to the unavailability of many labels during training. Here a question arises: can we infer the unknown Z,, from a small set of observations?
Unlike previous neural network-based methods, we employ sign inference to solve the problem. Signed social networks (SSNs) utilize positive links to denote friendship between two users and negative links to represent enmity. Sign inference is the task of predicting the signs of unknown links using the knowledge of available ones. The structural balance theory [Cartwright and Harary, 1956), fundamental principle of SSN, postulates that individuals in signed networks are disposed to following specific patterns of "an enemy of my friend is my enemy" (c-f-e), "a friend of my friend is my friend" (f-f-f), "a friend of my enemy is my enemy" (f-e-e), and "an enemy of my enemy is my friend" (e-e-f). However, the last assumption could contradict actual scenarios. Therefore, a more general notion, called weak balance,
introduced to address this issue [Davis, 1967].
We study signed graphs, wherein a negative edge signifies that the two nodes possess distinct labels. Figure illustrates that triads in signed graphs follow the weak balance theory, which suggests that the signed graph has global low-rank structure [Hsieh et al., 2012]. An intriguing finding [Candès and Tao, 2010] demonstrates that if matrix has low rank, it can be accurately recovered from

---

limited number of observations. Motivated by this, we approximate 2 with the solution to low-rank matrix approximation problem. which is then used for feature propagation.
Since the solution is a low-rank matrix, our new model is termed Low-Rank Graph Neural Network (LRGNN).. We summarize the contributions of this paper as:
We show that triads in signed graphs obey weak balance, based on which the unknown label relationship between two nodes can be inferred by looking up the known ones.
We prove that variant of signed GNNs shows a tendency to follow the structural balance theory, which can be enhanced by eliminating the faulty assumption from the model design.
We propose effective model LRGNN. Using both real-world and synthetic datasets, we provide comprehensive experimental results, thereby highlighting the superior performance of LRGNN over other state-of-the-ee methods.
2 Preliminaries
We first introduce the notations used in this paper.
Notations. Denote by G = E), an undirected graph, where V and & denote the node set and edge set, respectively. The nodes are described by node feature matrix X E RRxx where and f are the number of nodes and number of features per node, respectively. Y R is the node label matrix. The neighbor set of node is denoted by M₁. Let A E R=*" denote the adjacency matrix where A.j = 1 if (i,j) E & and O otherwise. We define label relationship matrix 2 E RRax for signed graph, where 2
if (i,j) share the same label and -1 otherwise. Let Å be signed adjacency matrix indicated by an observation set Ω with A.j = 2.,, if (i, Q and 0 otherwise. The Frobenius norm of matrix given by || |1 Ai; represents the i-th row of matrix A.
2.1 Link Sign Prediction via Low-Rank Matrix Completion
Next, we discuss the problem of link sign prediction and the theoretical support for using low-rank matrix completion.
Link Sign Prediction.
The link sign prediction task involves determining the signs of unobserved links in a network, where some links are already labeled as positive or negative. This work specifically considers scenarios where only one link exists between each node pair (i, E V x V. To be precise, given A partly observed from 2, the objective is to predict the signs of the unknown entries of 2. Note that the observed entries task difficult in general because of the low supervised ratio. For instance, if the supervised ratio is 30%, we need to guess 91% of entries of 2 using the knowledge of the rest 9% of entries.
be constructed using available labels from the training set. This
Here is a fact that significantly changes the task's premise, rendering it practical. The rank of 2 is equivalent to the number of classes if > 2. This low-rank structure is described by the weak balance theory: for homophilous node pair (i,j) and any 4/ E V. if 2 = 1 then 2 1 (f-f-f), then Żμ
if 2,,a then 2 = - (f-e-e); for heterophilous (i,j), if Z
(e-f-e).
Therefore, has e linearly independent distinct rows if c 2 2 (rank (2) = c). Inspired by this finding, employ Matrix Completion to address this challenge.
Matrix Completion. The task of matrix completion involves predicting the missing values in an unknown matrix based on a limited number of observed entries in the observation set Ω. Exact recovery of matrix from a small But the search for solutions becomes meaningful as soon the unknown matrix has low rank: numerous algorithms can accomplish near-perfect recovery with high probability under mild assumptions. This is known the Low-Rank Matrix Completion (LRMC) problem.
impossible without making any assumption about the matrix.
Low-Rank Matrix Completion. Given a signed adjacency matrix À and the observation set S the task of LRMC to find the lowest-rank solution among all the feasible solutions as follows,
min
rank
s.t. (Z) PA)
(I)
3

---

where Z is the decision variable and Pn(() is the projection onto the observation set. Unfortunately, (I) an NP-hard problem without known algorithms capable of solving problems practical time [Candès and Tao, 2010]. A matrix of rank r has exactly nonzero singular values. Hence, the rank function is simply the number of nonvanishing singular values. As the / fi-miimmization the tightest convex relaxation of the combinatorial fo-minimization problem [Candès and Plan, 2010]. An alternative is the nuclear minimization problem.
min
||||,, s... Pn(Z) (s)(),,
where |Z||- denotes the nuclear norm of Z, which is the sum of the singular values. Equivalently we can reformulate (2) in Lagrange form
min Pa -)) \|//||-
where À 2 0 a regularization parameter. A surprising result involving LRMC is that under certain assumptions, the missing entries of A can be accurately predicted.
Theorem 1. [Candès and Tao, 2010] Let 2 E RRaxn be a fixed matrix of rank = (1) obeying the strong incoherence property with parameter e. Suppose
observe entries of 2 with locations sampled uniformly at random. Then there is a positive numerical constant C such that if
m N C'"'n(logm) n)²
then 2 is the unique solution to (2) with probability at least - n -3. In other words: with high probability, nuclear-norm minimization recovers all the entries of with no error.
Solving (2) requires the computation of a SVD of a potentially large matrix, which can be computationally expensive. To reduce this cost, can use SVD-free low-rank matrix factorization (LRMF) problem formulated as follows:
min X
[|P(UUVT A) + XUU + IV
(5)
U,
where c S. 9 < n is the operating rank. There is a remarkable fact that ties the LRMF problem and the nuclear-norm regularized problem (3) [Mazumder et al., 2010]: by selecting q 2 c, the solution to (5) also provides a solution to (3) The equivalence between the solutions allows us to approximate 2 by the solution to (5).
We present some fundamental facts that support the recovery of 2. The first fact is that the rank of 2 is deterministie. Ideally, g = rank 2) should be the optimal choice [Hastie et al., 2015]. The second fact is that 2,,- 2 holds for any homophilous (i. j). This implies that class imbalance is the upper bound of the coherence parameter E. In most cases, E = O(1). Furthermore, if A., = 1 is observed, U, and v can combine their observations. For example, if A, is observed, then A,, is also ascertainable, regardless of whether directly observed or not (A,,k Ag.k). As a result, there is significant increase in the observation rate.
In real-life data, we typically witness deviation from the assumption that observations exhibit uni- form distribution. Nonetheless, this deviation only moderately influences the performance. Suppose node lacks any observed samples. In that case, exact recovery is theoretically impossible, but it would not hinder the recovery of other rows. Low-rank approximation methods have been applied to practical applications with fair amount of success, such as the Netflix problem [Koren et al., 2009].
3 Structural Balance Theory and Signed GNNs
We consider variant of signed GNNs [Bo et al., 2021] that updates node representations (1+1)
Σ
1 ai a fo .n.))
(6)
jEN(()
where fo(;)) :) refers to a neural network that measures the similarity between the inputs and returns a scalar ranging in 11, Let Vi.j = 1 if two neighboring nodes v; and vj belong to the same class and yi.j = -1 otherwise. Let < i, k > be a triad such that vy is a neighbor of v; and 1 is a neighbor of eyy while e and Us not directly linked. We have the following result.

---

Theorem 2. Consider that we apply a L-layer signed GNN (L 2 2) on triad. The output of the signed GNN is equivalent to H = ZH(), where Z is a matrix. Assume that each coefficient and independent of other coefficients and the probability that the model can precisely predict the sign of each coefficient is p. namely Pr(sign(a..) = 3k.)) = p. Also, assume that all the celf-cooefscients are positive. The probability that at least one of Zz, and N are correct in sign and the product & Z,, Z,, > 0 is given by ps- Then Ps is monotonically increasing concerning p. Especially, if p = 1, Z Z,,, > 0 always holds.
Remark 1. A triad is said to be balanced iff its product is positive as the four types of triads given by balance theory have two or zero negative signs.
The above result suggests that multi-layer signed GNNs may implicitly implement the structural balance theory as they frequently create balanced triads. When p equals all triads are balanced, indicating that the model is fol- lowing the idea that "a heterophilous neighbor of my het- erophilous neighbor a homophilous node." Nonetheless, this notion does not necessarily hold under multi-class classification tasks. Hence, even if the model can predict the label relationship between direct neighbors accurately, will still likely predict the relationship between 2-hop neighbors inaccurately. This suggests that multiple-layer signed GNNs are sub-optimal. Signed Graph Convolu- tional Networks (SignedGNNs) [Derr et al., 2018] utilizes the balance theory to model signed graphs. By eliminating the assumption "e-e-f" (see Supplement for implementa- tion details), we obtain a weakly balanced version of SignedGNNs termed WB-SignedGNNs. To evaluate their vulnerability over-smoothing, we compared the performance of WB-SignedGCC and SignedGCN at different depths, ranging from 4 to 24. As Figure 2 illustrates, SignedGiNN suffer from over-smoothing, and this problem can be largely resolved by dropping the incorrect assumption in the model's design. Such minute adjustment in the design can result in substantial performance enhancement for 24-layer SignedGCN (80% vs. 53% on Wisconsin dataset).
WB- WB-SignesBCH SignedG.CN
85
80
Accuracy (%6
75
70
65
12
16
20
24
#Layer
Figure 2: Over-smoothing analysis.
4 Approach
In this section, we present the overall framework of the Low-Rank Graph Neural Networks.
4.1 Predicting the label relationship matrix via robust low-rank approximation
Note that in 2, the information on the original graph topology is lost: we cannot tell whether two given nodes are linked or not since all entries are nonzero. To preserve the graph topology information, following Lim et al. [2021], we first apply MLPs to fuse feature matrix and adjacency matrix into matrix H E Raxe.
H (0) = (1 - (X) + (AMLPA(A),
where 0 ب < is the balance term. Next, we utilize LRMF to recover 2 with the edge set being the observation set (? E), matching the time complexity of vanilla GCNs [Kipf and Welling, 2017]. Furthermore, an attention term [Bahdanau et al., 2015] is incorporated into Eq.(5) as a supplement to the matrix completion. We approximate Ż with Z = V by solving the following robust low-rank matrix factorization problem,
F.(U.V) = Σ min(((VV)) )as - A.s) Tb)) + U/ + A|VI
(KJ)EE
T Wh ),)²
(8)
where 0 and 7 > 0 are haper-parameters, Wa a parameter matrix, h 1.00 Wh an attention coefficient, Te.j parameter of the capped norm. Low-rank matrix approximation models are prone
(0)
5

---

to outliers due to the square loss function [Keshavan et al., 2010]. To mitigate this issue, this work applies capped norm to limit the contribution of the approximation error ((UV)); )., A ). This strategy has been extensively utilized by researchers [Nie al., 2014, 2017, Jiang al., 2015]. Note that here each sample (i,j) has an independent parameter Ti which will be explained in detail later. The min operator render the function non-differentiable, and the projection function prevents us from obtaining closed-fomn solution. It seems that solving (q.(8) is infeasible. Using the surrogate function and Majorization-N -itrttioon-Miinizationn algorithm [Hastie et al., 2015], we can ensure that the objective function does not increase after each iteration. The optimization algorithm, initialization method, and proof of convergence can be found in the Supplement.
Once we have derived U. V² by minimizing (8.( the output of the model is formulated as
Hout = ((1 3) + SI, H
where the identity matrix I, is used to augment the ego-information and 0 < 3 < 1 is hyper- parameter. A 1-layer network sufficient aggregate nodes' representations for a node, also averts the implicit usage of the balance theory.
Remark 2. The time complexity of LRGNN is proportional the number of edges. A detailed discussion can be found in the Supplement.
4.2 Parameterized outlier detection
This section outlines a practical algorithm for detecting outliers based on the reliability of the estimated A.jj To generate the signed adjacency matrix A, we can use off-the-shelf neural network classifier generate pseudo labels. Additionally, the known node labels in training set Ty and label matrix Y can also be utilized. Similar to Zhu et al. [2021], the pseudo labels are generated as follows.
== + (1 0)
Ý softmax(P), P (X),
(10)
where (.)(() denotes trained neural network named estimator, @ the Hadamard product, and O2 = iff Ty and otherwise. The signed adjacency matrix defined as
Aij (Yan Y 5 (i,j) E
(11)
0 otherwise
Here 0 < 8 < 1 is a parameter that controls the ratio of negative edge weights. (.-) denotes the inner product of two vectors. Although this strategy appears simple, is highly effective. The critical point here is that we do not need to know the exact classes of the two nodes and we just care about whether they belong the same class. Let p be the accuracy of the estimator and assume that there is uniform distribution chance of being any incorrect class, namely e-1
1-p
The estimator has probability of (1-p)(ectc-2)
(e-1)) 1)2 to identify any two heterophilous nodes as homophilous nodes. This probability is less than 1 1- provided that e 2 3 and < 1. For instance, when the accuracy of the estimator is 50% and с = 5, for heterophilous (i. the probability of assigning them different labels is about 82.8% 22.8% which is significantly higher than 50%. In our experiments, we use simple estimators including GCN and MIP for faimess.
Edge Hom. #Nodes
#Edges
#Features #Classes
Texas
0.21
183
295
1,703
5
Wisconsin
0.11
251
466
1,703
5
Cornell
0.30
183
1,703
Actor
0.22
7,600
26,752
931
Squirrel
0.22
5,201
198,493
2,089
5
Chameleon
0.23
2,277
31,421
2,325
5
Cora
0.81
2,708
5,278
1,433
Citeseer
0.74
3.327
4,676
3,703
Pubmed
0.80
19,717
44,327
500
3
Penn94
0.47
41,554
1,362,229
5
2
arXiv-year
0.22
169,343
1,166,243
128
5
genius
0.61
421,961
984,979
12
The succeeding section discusses the design of Tij. which can be ex- pressed as Ti.j C.j T. where
Table 1: Dataset statisties.
O < Cij < 1 is a parameter. We adopt a widely accepted definition of outliers [Yeh, 2007].
q3 + 1.5 (gs 91),
(12)

---

Texas
Wiscon.
Cornell
Actor
Squir.
Chamel.
Cora
Citeseer Pubmed
MLP
80,81 85. 29+3.31 81. 81.89+6.40 66.53+0.70 70 26.77 26.21=2999 75.69+2.0 74.02=1 90 87.16s0.3
GCN
55.14
16 51. 76:066 60,54+5.30 30 27. 17 53.43+2.01 64.82+2.24 86. 98 76.50=1.36 36 88, 38.4220..0
GAT
52. $1.89 +4.41
27 44.44.088 89 40.72+1.5.
60.26+2.50 50 87.30=1.10 76.55=1.22
+0.3
H:GON
84.86=7.23 87.65+4.98 82.70=5.22 35. 100000000 36.4821.86 86 60.11=2.15
87.87=1.20 17.1 89 29,49
GPR-GNN
78.3824.36 82, 32.9424.21 80.27 11 34.63+1.2 31.6111.4 46.58=1.71
87 17. 77.13=1.67 87. 87.5420.33
WRGAT
83.62+5.50
86.98+3.78 81.62+1.90 36.53+0.77 48. 75 65.24=0.87 88, 20 76,81 =1 89 88.52+0.92
GloGNN+
84,05=4900
88.04+3.22
85.95+5.10
37.70+1.4D
57.88+1.76
71.21 84 88.33=1.09 77.22=1.78 89.24=0.39
GGCN
84.86+4.55
86.86+3.2
85.68+6.6
37.54+1.56
55.17 71.14=1 84 87.95=1.05 77.14=1 89. 15
ACM-GCN
87.8424.40
88.4313.22
35.1426.07
36.28s1.09
54.40a1.88
66.93=1.85
27.91 77.32a1.70 90.00a0.52
LINKX 74.60z8.37
75.49a5.72 77.8425.81
36. 10.1.5
61.81
68. 68.42.1.38
84.6421.13 73.19 87. 37.8620.77
OGNN 86.22+t412 88. 04.3.4433 87.0324.73 37.99 12.4421.96 72. 22.2842.29 88.37 11.3 10.15 25
LRGNN 90.27 88.2313.54 86.48.5.65 37.34 74.38 19.16 88.3 77.53a1.31 90.2440.64
Table 2: Node classification accuracy (%) small real-world benchmark datasets. The best results are highlighted in bold, whereas runner-up results are underlined. Each experiment is executed 10 times.
GCN
GAT
GPR-GNN GloGNN++ ACM-GCN
LINKX
OGNN
LRGNN
Penn94
82.47=0.27 81.53 #0.55 81,38+0.16
85.74+0.42
84.71=0.5 83.31 86.48 0.52 47.37+0.59
82.52+0.96
arXiv-year 46.02+0.26 46.05+0.51
45,07+0211 54.79+0.25
56,00=134 54, 54.4920.29 55.68 0.35
genius 87.42a0.37 55.80&0.87 90.05a0.31
80.3343.91 90.91
90.77s0.27 88.5220.45 91.13 0.12
Table 3: Node classification accuracy (%) on large-scale datasets.
where a1 and 93 are the first and third quartiles, respectively. Mathematically, c.j is defined
Ct = a1 Y f. 12 UIY J.: 112 2 t log(e- -
-11- 1+ A.,))) + Sigmoid((""eeluU 116 D),
(13)
where [a1, 022 ag] Softmax (W.), W. R || denotes vector concatenation, and e is the natural logarithm.
The Euclidean norm term measures the quality of the pscudo label since uniformly distributed 1 suggests that the estimator has confidence in the class of u;. The absolute value term takes into account that extreme values are typically more reliable. For example, a zero A., indicates that the relationship between and 1j is ambiguous. The third term employs graph attention [Velickovic al., 2018, Brody et al., 2022] adapt C. accordingly.
Experiment
This section evaluates the performance of LRGNN. We put the experimental results w.r.t. ablation study and robustness in the Supplement due to space limitation.
Datasets. We use three homophilous datasets including Cora, Citeseer and Pubmed [Yang et al., 2016], along with 6 heterophilous datasets released in Pei et al. [2020] and Rozemberczki et al. [2021], and three large-scale heterophilous graphs [Lim et al., 2021]. The traiiin//aliddtioon/esingg splits used in this paper are the same as [Li et al., 2022].
Baselines. We compare LRGNN with 11 baselines, including (1) classic GNN models: vanilla
GCN [Kipf and Welling, 2,d GAT [Velickovic et al., 2018). (2) models specifically designed to handle heterophily: H₂GCN [7hu et al., 2020], GPR-GNN [Chien et al., 2021], WRGAT [Suresh et al., 2021], LINKX [Lim et al., 2021], GGCN [Yan et al., 2021], ACM-GCN [Luan et al., 2021] }. GloGNN+ [Li et al., 2022], and Ordered GNN (OGNN) [Song et al., 2023). (3) 2-layer MLP. We specifically choose GloGNN+ and ACM-GCN they generally outperforme the other variants proposed in their respective papers.
Node classification results. Table 2 and Table 3 provide a summary of the test accuracy of the tested methods on 12 datasets with diverse homophily ratios and scales. Some baselines experience out-of- memory errors on large datasets, thus the corresponding results are excluded. From the tables, can
7

---

Wisconsin
Chameleon
Squirel
Comell
0.35
0.30
0. 3.40
0.38
0.30
0.25
0.36
38
0.36
0.25
0.20
0.34
0.20
0.15
0.32
0.32
0.10
0.30
7 9 11 13 15 29
5 9 13 19 21
7 9 11 13 15
7 11
15 19
Operating rank q
Operating rank q
Operating rark
Operating rank
Figure 3: Recovery error. The lowest point is associated with a vertical line. The shaded region corresponds to 95% confidence interval.
wither-dbus
williie
uitii cloe
10a
10'
185
10
10"
10'
10
AsD maation Conficients
-24
-0.3
E2
-123 -010 -0:2 -0. 353 223
Aggregation
052
-10
Aggregation Confriients
Visualization result of Z. The entries have been grouped into two categories based on the Figure 4:
label relationship between the two nodes.
draw several observations. Firstly, MLP is a strong baseline for heterophilous datasets, outperforming GCN and GAT on Texas, Wisconsin, and Cornell datasets. Secondly, methods designed specifically for heterophilous graphs generally perform better than MLP and traditional GNNs. Thirdly, H,GCN, WRGAT, GGCN, ACM-GCN, GloGNN++, and LRGNN are the top performers on small datasets. However, H,GCN, WRGAT, and GGCN lack scalability, thereby limiting their widespread adoption for large datasets. Fourthly, LRGNN performs the best in terms of the average rank, emerging as the winner runner-up all datasets except for Actor.
The results suggest that LRGNN consistently offers superior performance on both homophilous and heterophilous graphs. Notably, LRGNN achieved the highest score on Squirrel, with approximately 19% improvement over the runner-up score achieved by OGNN. The excellent performance on Squirrel and Chameleon could be attributed to the relatively large average node degrees of these two datasets, providing more observations to recover the label relationship matrix. Moreover, the performance of LRGNN these three large datasets demonstrates the scalability of our model.
Sign inference accuracy w.r.f. operating rank q. We investigate the effect of the operating rank q the recovery loss: err 2n Ev, ssign((.VV, )..)) sign(Zr.)).. 3 shows that the error decreases initially when q increases, then it increases gradually after reaching the minimum point. The best result is consistently achieved when q is approximately 5, the number of classes. Empirically, this supports the use of low-rank approximation to predict the label relationship matrix: the appropriate dimensionality for the factors can be determined based on the number of classes. In a standard LRMF problem, the rank of the matrix of interest is inaccessible. Therefore, we have to select a sufficiently large q to ensure that surpasses the rank, which guarantees that the solution to LRMF problem provides solution the LRMC problem. Nevertheless, selecting excessively large q can substantially increase the number of iterations required to converge.
Visualizing the predicted label relationship matrix Z. There are two main desirable traits of 2 we want Z to possess. The first that within-class entries are positive while between-class entries are negative. This ensures that nodes are embedded close to their homophilous nodes and distant from the heterophilous nodes in the embedding space. The second is that 2, and Zj.- are identical if they share the same label, that X 2j.XX Consequently, we visualize Z in two different styles.
First, as shown in Figure 4, dividing the entries into two groups reveals that the distribution is similar to Gaussian distribution. Although most entries converge around zero, within-class entries and between-class entries are positioned on opposite sides of the zero.
To illustrate the second trait, we visualize Z with reordered rows and columns based on ground truth labels. As shown Figure 5, the matrices exhibit the structure of a block diagonal matrix. But here the entries of sub-matrices along the diagonal are positive, whereas off-diagonal sub-matrices contain
8

---

Texas
Wisconsin
Cornell
Chameleon
100
259
100
150
20
250
5x
50%
USW
2300
100
0.00
50
6M0
4.75
200
3,00
2005
Figure 5: Visualization result of Z. Both row and column indices have been reordered based on the ground truth labels.
negative entries. On closer inspection of the figure, we notice that nodes in the same class share high degree of similarity, with the rows' pixels showing comparable patterns. In conclusion, Z exhibits both desirable traits of 2. This helps explain the effectiveness of LRGNN.
Synthelic Grapits
Real-World Graph
Avg. Degree= 0.5
Avg. Degrae= 5.0
Avg. Degres= 20.0
Texas
Accuracy
0.6
08
CCN
08
ADHDOV
UMK
04
0.0
URGNN
02
0.5
0.5
0.5
0.0.11 000102020440
Node-LLvvll Homophily Ratio
Node-Loval Homophily Ratio
Node-Loval Homophily Ratio
Figure 6: The first three subfigures are results on synthetic graphs and the last one is the result on corrupted Texas. Error bars indicate 95% confidence interval.
Results on synthetic graphs. To comprehensively evaluate the performance of LRGNN, we leverage random partition graphs [Kim and Oh, 2021] generated by the stochastic block model. The node features are sampled from Gaussian distributions where the centers of clusters are vertices of a hypercube. Notably, the distance between Gaussian distribution means is small, thus, it is challenging to differentiate between node features of distinct classes. This is evident by MLP's unsatisfactory performance on the synthetic graphs. We use 15 synthetic random graphs with varying node-level homophily ratios and average degrees. More information about the synthetic graphs can be found in the Supplement.
can be observed from Figure 6 that, when the homophily ratio or node degree is low, LRGNN is the only model that outperforms MLP. Also, LRGNN performs significantly better than other models when the homophily ratio is below 0.5. These results suggest that LRGNN performs particularly well on random graphs, which we attribute to two reasons. Firstly, the observed entries of these graphs are uniformly distributed, meeting one of the conditions for exact recovery. Secondly, to derive aggregation coefficients, low-rank approximation methods utilize only the observed entries of 2, while neural network based methods rely on the raw features. However, in this case, node features are not that informative since the means of Gaussian distributions are close. To validate the second reason, we use the Texas dataset and degrad the quality of its features by adding Gaussian variables. We obtain a degraded feature matrix by X' ' Xi. + Ej. with ej i.i.d. sampled from a Gaussian distribution (0, o²). Note that the original features will be overwhelmed by the Gaussian random variables a large applied. We compare the performance of representative models that included GloGNN++ H2GCN, and MLP with that of LRGNN. It can be observed that, as the features get less informative, the performance of GloGNN++, H2GCN, and MIP decreases significantly, while LRGNN's accuracy remains above 80%. In addition to that, a large also makes their training process erratic, which accompanied by significant error bars. These empirical results confirm our previous analysis.

---

Conclusion
This paper presents a method for extending GNNs to heterophilous graphs through the use a label relationship matrix. In order utilize the low-rank properties of weakly-balanced graphs, propose a robust low-rank matrix approximation technique for the prediction of the label relationship matrix. The proposed LRGNN has been thoroughly evaluated through extensive experiments. We conduct extensive experiments to evaluate our proposed LRGNN. Our results indicate that LRGNN outperforms other baseline methods on both synthetic and real-world graphs. Notably, when the node degree distribution of the graph conforms to uniform distribution, LRGNN exhibits significantly superior performance over other baseline methods.
7 Limitations
The main theoretical support for our approach assumes a uniform distribution of node degrees. However, in practice, node degree distributions frequently follow a power-law distribution that is non-uniform. Although the main results of this paper are obtained using real-world graphs with non- uniform node degree distributions, it is unclear how this affects the theoretical results. Additionally, is acknowledged that LRGNN's performance affected by the accuracy of the generated pseudo labels. The supplementary material provides the corresponding experiment that indicates LRGNN demonstrates a non-sensitive response to this impact. However, further exploration and discussion are helpful to investigate the theoretical implications fully.
Acknowledgements
This work was partially supported by the National Key Research and Development Program of China (No. 2018AAA0100204), a key program of fundamental research from Shenzhen Science and Technology Innovation Commission (No. JCYJ202001091 10900000191144382666 the Major Key Project of PCL (No. 20222D0115301,, and an Open Research Project of Zhejiang Lab (N0.2022RCOAB04)
References
Sami Abu-EI-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, volume of Proceedings of Machine Learning Research, pages 21-29. PMLR, 2019.
Dzmitry Bahdanau. Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Yoshua Bengio and Yann LeCun, editors, ICLR 2015, 2015.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks, In AAAI, pages 3950-3957. AAAI Press, 2021.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? ICLR. OpenReview.net, 2022.
A. M. Buchanan and Andrew W. Fitzgibbon. Damped newton algorithms for matrix factorization
with missing data. CVPR (2), pages 316-322, IEBE Computer Society, 2005.
Emmanuel Candès and Yaniv Plan. Matrix completion with noise. Proc. IEEE, 98(6):925-936, 2010. doi: 10. 10.1109/PRO...0099.0 2005522..
Emmanuel J. Candès and Terence Tao. The power of convex relaxation: near-optimal matrix
completion. IEEE Trans. Inf. Theory, 56(5):2053-2800, 2010. doi: 10. 10.1109711220002244406.
Dorwin Cartwright and Frank Harary. Structural balance: generalization of heider's theory.
Psychological review, 63(5)2277, 1956.
Pei Chen. Optimization algorithms on subspaces: Revisiting missing data problem in low-rank matrix.
Int. J. Comput. Vis., 80(1):125-142, 2008.
10

---

Yankai Chen, Yifei Zhang, Menglin Yang, Zixing Song. Chen Ma, and Irwin King. WSFE: wasser- stein sub-graph feature encoder for effective user segmentation in collaborative filtering. CoRR. abs/2305.044100 2023.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR. OpenReview.net, 2021.
Mark A. Davenport and Justin K. Romberg. An overview of low-rank matrix recovery from incomplete observations. IEEE Sel. Top. Signal Process., 10(4):608-622, 2016.
James A Davis. Clustering and structural balance in graphs. Human relations, 20(2):181-187, 1967.
Tyler Demr, Yao Ma, and Jiliang Tang. Signed graph convolutional networks. In IEEE International Conference Data Mining, ICDM 2018, Singapore, November 17-20, 2018, pages 929-934. IEEE Computer Society, 2018. doi: 10.1 109/CCDDM.2118.00 1.01
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arvi 1et.i.903000444 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F, Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh, editors, ICML 2017, volume 70 Proceedings of Machine Learning Research, pages 1263-1272 PMLR, 2017.
Pietro Hiram Guzzi and Marinka Zitnik. Editorial deep learning and graph embeddings for network biology. IEEE ACM Trans. Comput. Biol. Bioinform., 19(2):653-654, 2022. doi: 10. 109/TCBB. 2021.3110279.
Trevor Hastie, Rahul Mazumder, Jason D. Lee, and Reza Zadeh. Matrix completion and low-rank SVD via fast alternating least squares. J. Mach. Learn Res., 16:3367-3402, 2015.
Cho-Jui Hsieh, Kai- Kai-Yang Chiang, and Inderjit S. Dhillon. Low rank modeling of signed networks. In KDD, pages 507-515. ACM, 2012.
Zongmo Huang, Yazhou Ren, Xiaorong Pu, Shudong Huang. Zenglin Xu, and Lifang He. Self- supervised graph attention networks for deep weighted multi-view clustering. In Brian Williams, Yiling Chen, and Jennifer Neville, editors, AAAI, pages 7936-7943. AAAI Press, 2023. doi:
10.1609/aaii.v3 www.....79..9.
Du Q. Huynh, R. Hartley, and Anders Heyden. Outlier correction in image sequences for the affine camera. In ICCV, pages 585-590. IEEE Computer Society, 2003.
Wenhao Jiang, Feiping Nie, and Heng Huang. Robust dictionary learning with capped 11-norm. In Qiang Yang and Michael Wooldridge, editors, IJCAI 2015, pages 3590-3596. AAAI Press, 2015.
Zhao Kang, Wangtao Zhou, Zhitong Zhao, Junming Shao, Meng Han, and Zenglin Xu. Large-scale multi-view subspace clustering linear time. AAAI, pages 4412-4419, AAAI Press, 2020. doi:
Raghunandan H. Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. IEEE Trans. Inf. Theory, 2666))2980-2998, 2010. doi: 10. 109/TTT:2010.2446205.
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self-supervision. ICLR. OpenReview.net, 2021.
Thomas N. Kipf and Max Welling. semi-supervised classification with graph convolutional networks. In ICLR (Poster). OpenReview.net, 2017.
Ychuda Koren, Robert M. Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009, doi: 10. 20.1009/CC.0009.66..
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. In ICML, volume 162 of Proceedings of Machine Learning Research, pages 13242-13256. PMLR, 2022.

---

Langzhang Liang. Zenglin Xu, Zixing Song, Irwin King, Yuan Qi, and Jieping Ye. Tackling long-tailed distribution issue in graph neural networks via normalization. IEEE Transactions on Knowledge and Data Engineering, 2023.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning on non non-hooophilous graphs: New benchmarks and strong simple methods. In NeurIPS, pages 20887-20902, 2021.
Guangcan Liu, Zhouchen Lin, and Yong Yu. Robust subspace segmentation by low-rank representa- tion. In ICML, pages 663-670. Omnipress, 2010.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Rajesh Gupta, Yan Liu, Jiliang Tang. and Aditya Prakash, editors, KDD '20, pages 338-348. ACM, 2020. doi: 10.1 141/333444666634030777
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wao Chang, and Doina Precup. Is heterophily A real nightmare for graph neural networks to do node classification? CoRR, 0as/2109.05644 2021.
Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices.
J. Mach. Leamn Res., 11:2287-2322, 2010. doi: 10.5555/
1756006.1859931
Feiping Nie. Jianjun Yuan, and Heng Huang. Optimal mean robust principal component analysis. In ICML 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 1062-1070. IMLR.org. 2014.
Feiping Nie, Zhouyuan Huo, and Heng Huang. Joint capped norms minimization for robust matrix recovery. In Carles Sierra, editor, IJCAI 2017, pages 2557-2563. ijeai.org, 2017. doi: 10.24963/ ijcai.2017/356.
Takayuki Okatani and Koichiro Deguchi. On the wiberg algorithm for matrix factorization in the presence of missing components. J. Comput. Vis., 72(3):329-337 2007.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR. OpenReview.net, 2020.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In ICLR 2023. OvenReview.net, 2023.
Benedek Rozemberczki. Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. J. Complex Networks, 9(2), 2021.
Heung-Yerne Yeung Shum, Katsushi Ikeuchi, and Raj Reddy. Principal component analysis with missing data and its application polyhedral object modeling. IEEE Trans. Pattern Anal. Mach. Intell., 869) 1995.
Yunchong Song, Chenghu Zhou, Xinbing Wang, and Zhouhan Lin. Ordered GNN: ordering message passing to deal with heterophily and over-smoothing. CoRR, abs/2302.01524, 2023. doi: 10. 088500arxiv.2202.01522
Zixing Song and Irwin King, Hierarchical heterogeneous graph attention network for syntax-aware summarization. In AAAL, pages 1 11340-1133 11348. AAAI Press, 2022.
Nathan Srebro, Jason D. M. Rennie, and Tommi S. Jaakkola. Maximum-margin margin matrix factorization.
In Advances in Neural Information Processing Systems 17 (NIPS 2004), pages 1329- 2004.
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, pages 1541-1555 ACM, 2021.
Jiliang Tang, Xia Hu, Huiji Gao, and Huan Liu. Exploiting local and global social context for recommendation. In JJCAI pages 2712-2718, LICAI/AAAL, 2013.
12

---

Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liō, and Yoshua Bengio. Graph attention networks. In ICLR (Poster). OpenReview.net, 2018.
Wiberg. Computation of principal components when data are missing. In Proc, of Second Symp. Computational Statistics, pages 229-236, 1976.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019. OpenRe- view.net, 2019a.
Zenglin Xu, Feng Yan, and Yuan (Alan) Qi. Bayesian nonparametric models for multiway data analysis. IEEE Trans. Pattern Anal. Mach. Intell., 37(2):475-477, 2015.
Zenglin Xu, Bin Liu, Shandian Zhe, Haoli Bai, Zihan Wang. and Jennifer Neville. Variational random function model for network modeling. IEEE Trans. Neural Networks Learn. Syst., 30(1):318-322 2019b.
Yujum Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. CoRR, abs/2102.064622, 2021.
Liang Yang, Mengzhe Li, Liyang Liu, Bingxin Niu, Chuan Wang, Xiaochun Cao, and Yuanfang Guo. Diverse message passing for attribute with heterophily. In NeurlPS, pages 4751-4763, 2021.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pages 40 48. JMLR.org. 2016.
Arthur B. Yeh. A modern introduction to probability and statistics. Technometrics, 49(3):359, 2007. doi: 10. 1911199/tchhh0e0 200.cch...07..55....
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang. Di Jin, and Philip S. Yu. Graph neural networks for graphs with heterophily: A survey. CoRR, has/2202.07082/ 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. In NeurlPS, 2020.
Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra, Graph neural networks with heterophily. AAAL pages 11168 11176. AAAI Press. 2021.
13


Reviews:
[{"review_id": "CChOPWeZID", "reviewer": "Reviewer_rmTT", "summary": "This paper introduces the LRGNN method, which aims to enhance the performance on heterophilous graphs by re-constructing the signed relationships. The approach involves optimizing the low-rank signed matrix using the SVD-free LRMF strategy.\n", "questions": "Please check the weakness", "limitations": "Please check the weakness", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The utilization of the low-rank signed relationship matrix in heterophilous graph representation is intriguing and promising.\n", "weaknesses": "Weaknesses:\n\n1. The limitations on the first contribution. \nOne of the limitations of this method is its reliance on the data split. The success of low-rank matrix completion is highly dependent on the availability and quality of the signed adjacency matrix and the observation set. In cases where the observation set is small, there may be nodes that have no neighbors selected, as mentioned in Line 140. This poses challenges in effectively guessing the values of U and V, potentially impacting the accuracy of the low-rank matrix completion process.\n\n2. Limited novelty:\nAlthough the method incorporates low-rank optimization, the overall novelty of the approach is somewhat limited. The designed method in Section 4 shares similarities with other existing methods. For instance, when compared to the general compatibility matrix used in [1,2], the primary difference lies in both matrices' objective to measure whether two nodes belong to the same class.\n\n3. Concerns with the experiments:  \na. Effectiveness of low-rank recovery of Z (Eq. 7 and 10):\nTo further justify the effectiveness of the low-rank recovery of Z, it is essential to provide evaluations for Eq. (7) and (10). Demonstrating the accuracy and reliability of the low-rank recovery process would strengthen the paper's claims.  \nb. Parameter numbers:  Including the parameter numbers in the paper would provide valuable insights, especially regarding the growth of the matrices U and V in correlation with the number of nodes. This information would contribute to a more comprehensive understanding of the method's scalability and resource requirements.\n\n\nDetailed comments:\n1. Fig.1: In panel t3, the color of the circle appears to be incorrect. Please ensure that the color \ncorresponds accurately to the represented class.\n\n2. Fig.4 Wisconsin: There seems to be a discrepancy in the edge numbers of in-class and between-class connections. Given that this dataset is heterophilous, the number of edges within the same class and between different classes should differ significantly. Please review and verify the edge counts for accuracy.\n\n[1] Graph Neural Networks with Heterophily.   \n[2] Powerful Graph Convolutioal Networks with Adaptive Propagation Mechanism for Homophily and Heterophily. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the detailed review. We address the concerns in below.\n\n**Q1: The reliance on the size of the observation set**\n\n**R** In order to align with the time complexity of other GNNs, we define the observation set as the edge set. However, it is important to note that the performance of the GNN algorithm is known to be influenced by the number of edges present in the graph. So if a small observation set poses a challenge to the low-rank approximation method, it would be also a challenge to GNN models, since they use the same edge set. There is no evidence suggesting that the low-rank approximation method is more sensitive to this size than a GNN model. In fact, our experimental results demonstrate that our LRGNN achieves the best or runner-up results on sparse graphs such as the Texas, Wisconsin, and Cornell datasets. Furthermore, the visualization results presented in Figures 4 and 5 showcase that low-rank approximation can recover good label relationship matrices even if the edges are sparse.\nAdditionally, there is no difference between low-ran approximation and GNNs when encountering isolated nodes. For instance, when a node contains no links, the output representation of this node by a GNN model is equivalent to that of its MLP counterpart. Similarly, the corresponding row of the node in the matrix recovered by a low-rank approximation model has only one non-zero element, then using it for propagation we also obtain the same outcome as an MLP. \n\nSince all types of GNNs are influenced by the number of edges and there is empirical evidence that low-rank matrix completion performs effectively with limited observation sets, this should not be considered a particular drawback of our proposed approach or paper.\n\n**Q2:  the reliance on the quality of the signed adjacency matrix** \n\n**R** Suppose the accurate signed adjacency matrix is given by $A_{ground}$, then the estimated signed adjacency matrix can be expressed as $\\tilde A = A_{ground} + N$, where $N$ is a noise matrix.  We have dedicated much effort to exploring the influence of the noise in Appendix B, including the effectiveness of the capped norm and the change in performance of LRGNN when the entries of $N$ are i.i.d. drawn from Gaussian distribution. \n\nFor example, LRGNN outperforms the runner-up OGNN by a substantial margin on the Squirrel dataset. It is worth noting that the signed adjacency matrix of Squirrel is particularly inaccurate, as reflected by the estimator's low accuracy of approximately 50%. There is also a visualization result of the recovered $Z$ on Squirrel presented on page 21, figure 14(b). These results suggest that the quality of the generated signed adjacency matrix has a very slight impact on LRGNN’s performance, and the outstanding performance of LRGNN is not conditioned on a very accurate signed adjacency matrix. \n\n**Q3: limited novelty**\n\n**R** While compatibility matrices are commonly employed to model node affinity, our paper delves into several innovative aspects that set it apart. Firstly, we introduce low-rank matrix completion to the GNNs, showcasing its power in predicting the label relationship matrix.  Secondly, we establish that predominant signed GNNs find their foundation in balance theory. Our empirical analysis further highlights that these can be significantly enhanced by reconsidering the 'e-e-f' assumption, which might not always hold true.  Notably, the reviewer has also positively remarked on our approach, mentioning, \"The exploitation of the low-rank signed relationship matrix in heterophilous graph representation is both intriguing and holds promise.\" This attests to the novelty we're bringing into the domain. In summation, our primary contributions and the claims made in the paper distinctively address areas that have been relatively untouched in preceding research, thereby underscoring the paper's innovative value.\n\n**Q4 Effectiveness of low-rank recovery of Z (Eq. 7 and 10)**\n\n**R** We would like to clarify a few points. Firstly, Eq. 7 pertains to a different aspect of our methodology and does not directly address the recovery of Z. Conversely, Eq. 10 is instrumental in generating the signed adjacency matrix. As for the low-rank recovery's precision, our study showcases a plethora of visualization results underscoring its effectiveness. These include the recovery error rate on real-world graphs illustrated in Figure 3, visualization of the recovered Z in Figures 4 and 5, and recovery accuracy on generated data with a minimal observation rate presented in Figures 7 and 8 (Appendix A). We invite you to review these figures for a more comprehensive understanding.\n\n**Q5 Parameter numbers**\n\n**R** U and V are not parameterized, and they are expressed as a series of matrix multiplication, see Eq. 25 and Eq. 27 for their formulation. Regarding the size of U and V, they are of size $n \\times q$, where q is a small number typically close to the # of classes. Therefore, U and V would not require more computational or storage resources than a typical node representation matrix in a GNN model. The parameter number of LRGNN is $ O(fd+dc+nd) $, where $f$ is the dimension of the raw feature, $d$ is the hidden size, $n$ the number of nodes. As a comparison, the parameter number of GCN is $O(fd+dc+d^2)$, and the additional parameters of LRGNN is only linear to the number of nodes.\n\n**Q6 Fig.1 & Fig. 4**\n\n**R** We will correct that mistake in Fig 1. Note that Figure 4 is the visualization of $Z$ with $n \\times n$ non-zero entries, which can be viewed as the predicted adjacency matrix of a signed **complete graph**, not the sparse adjacency matrix. Therefore, the number of edges within the same class and between different classes is only related to the class balance, irrespective of heterophily or homophily. Fig.4 Wisconsin is accurate.\n"}, {"review_id": "CHqjkFpPmz", "reviewer": "Reviewer_JZ4m", "summary": "This paper consider predicting the global label relationship matrix as a low rank matrix completion problem. This formulation is based on the observation that the rank of the global label relationship matrix shall equal the number of classes. The authors proposed an efficient solution to the low rank matrix completion problem and the predicted global relationship matrix is used to mix features into the node embedding for predicting node labels. The authors compared the proposed method with a series of baselines and find the proposed method consistently outperform or on-par with the state-of-the-art methods.\n\nBesides the LRGNN, the authors also prove that a variant of signed GNNs shows a tendency to follow the structural balance\n72 theory, which can be enhanced by eliminating the faulty assumption from the model design.", "questions": "It is not clear to me how the \\tilde{A} entries are defined. In particular, assuming a graph has 30% of labels being known, then only roughly 9% of the edge signs are known. I am not sure how the rest of the values are determined, are they simply set to 0?\n\nFurthermore, I am not sure how intuitively matrix completion would help determine the label relation of a node with other nodes in the graph, if the graph has no edges that has a know sign. In particular, the authors states:\n\n*Finally, at least one observation is present per row and per column (\\tilde{A}_i,i = 1)*\n\nYet I am not sure why that information alone would be helpful.\n\nwould appreciate if you can provide more intuition", "limitations": "...", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The idea of computing the global label relationship matrix and then use it as a one-hop GNN is quite novel.\n2. The formulation of predicting the global label relationship matrix as a signed low rank matrix completion problem is elegant.\n3. The paper is extremely well-written and the logic well organized.\n\n*I am not able to verify the math behind the matrix completion solution, but the rest of the method looks sound to me*", "weaknesses": "The weakness of the paper is well-discussed in the last section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive comments and for taking the time to review our paper. We appreciate your insights and would like to address your concerns.\n\nFirst, regarding our optimization algorithm for the matrix completion problem, we would like to provide some additional information.\n\nThe optimization algorithm we used follows the approach outlined in a highly regarded paper [1] and we have properly cited and acknowledged this source in our paper. The Majorization-Minimization technique, upon which our algorithm is based, is elegant and conceptually straightforward. Its correctness is easily verifiable. We have put significant effort into verifying the mathematical aspects of this algorithm to ensure its correctness. We would love to describe the basic operations of the Majorization-Minimization to make sure that you would not have concerns about the correctness of the algorithm.\n\nConsider we wish to solve $\\underset { x}{min} f(x)$ that is so **complicated** that we cannot handle the problem directly. We aim to find a sequence $\\left\\\\{x_k\\right\\\\}$ such that $f(x_{k+1})\\le f(x_{k})$. The idea is about using the variable x at the current iteration ($x_k$) to construct a **simpler** surrogate function $g(x|x_k)$, so we can obtain $x_{k+1}$ by solving $x_{k+1} = \\underset { x}{arg min} \\\\; g(x|x_k)$, where $g(x|x_k)$ can be any function once it satisfies the following two conditions:\n\n **(1)** $f(x) \\le g(x|x_k)$, $\\forall x$\n\n**(2)** $f(x_k) = g(x_k|x_k)$, $\\forall x_k$ \n\nWe can easily prove $f(x_{k+1}) \\underset {(1)} {\\le} g(x_{k+1}|x_k) \\underset {\\text{by definition}}{\\le} g(x_k|x_k) \\underset {(2)}{=} f(x_k)$. The intuition is to minimize $f$ by another simpler function $g$ such that minimizing $g$ ’helps’ minimize $f$.\n\nNow back to our paper, the construction of the surrogate function is described by Eq.(24) (page 22), and the proof of the two conditions above refers to Eq.(37),(38), and (39) (page 24). \n\n**Q1** I am not sure how the rest of the values are determined, are they simply set to 0?\n\n**R1** Yes! We just simply set the unknown entries to 0, but you can set them to any other specific values if you like. The rest values of $\\tilde{A}$ do not affect the objective function or the values of $U$ and $V$ because only the known entries contribute to the objective function Eq.(8). Specifically, the first term of the objective function is given by $\\sum_{(i,j)\\in \\mathcal{E}} (UV^T_{i,j}-\\tilde{A}_{i,j})$. Here, $\\mathcal{E}$ represents the observation set, which includes the known entries.\n\n**Q2** Finally, at least one observation is present per row and per column (\\tilde{A}_i,i = 1). Why that information alone would be helpful.\n\n**R2**  This is only a consideration at the theoretical level. Look at the objective function again.\n\n$O= \\sum_{(i,j)\\in \\mathcal{E}} (UV^T_{i,j}-\\tilde{A}_{i,j})$\n\nIf there are no observed entries in a specific row, such as row 1 with $(1,j)\\notin \\mathcal{E}, \\forall j$, the value of $U_{1,:}$ does not affect $O$. Consequently, the value of $U_{1,:}$ remains unchanged throughout the iteration process, as it does not contribute to the gradient. Thus, its value is solely determined by the initialization method and random seed employed. Knowing $\\tilde A_{i,i} = 1$ alone is **insufficient** to infer its label relationships by matrix completion, but at least we can generate a unique $U_{i,:}$ and $V_{i,:}$ that are independent of the initialization method and the random seed. For other cases demonstrating how the label relation of a node with other nodes can aid in matrix completion, please refer to Appendix Section A.\n\nThanks for your time and effort again! Please let us know if you have any further question.\n\n[1] Hastie, Trevor, et al. \"Matrix completion and low-rank SVD via fast alternating least squares.\" The Journal of Machine Learning Research 16.1 (2015): 3367-3402.\n"}, {"review_id": "FvK7vyPYtp", "reviewer": "Reviewer_mJPn", "summary": "Graph Neural Networks (GNNs) do not operate effectively when the graph is heterophilic with respect to the task. Addressing this issue is an important problem. The paper starts by analyzing SignedGNN model and demonstrates through a simple analysis that SignedGNNs might be implicitly implementing balance theory (at least for binary scenario). This fails in multi-class setting because e-e-f is not right. To address this issue, the aggregation is modified to remove the e-e-f aggregation, creating the weak-balanced model. However, this requires the knowledge of friends and enemies. Another model is used to predict this relationship labels. The actual model incorporates this signedGCN model along with a matrix factorization component that compares low rank behavior with the learned representations. So, the learnt representations capture low rank matrix factorization behavior while aggregating over reasonably right neighbors.", "questions": "1. While individual terms of $c_{ij}$ have been explained in the writing and some ablation study in the supplementary have been performed to show how well it works. It will still be good to understand why the three terms can be put in a very simple additive model combined with some values through Softmax.\n2. It will be good to perform some hyper-parameter sensitivity study.\n3. The \"Impact of the Accuracy of the Estimated Signed Adjacency Matrix\" was a very interesting section. It seems almost unintuitive that the model is robust to arbitrary corruption of the estimated signed adjacency matrix. However, would it not indicate that the proposed approach could also work with SignedGNN instead of WB-SignedGCN?", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. **Easy Approach**: The proposed approach is fairly simple.\n2. **Clarity**: The paper was easy to read and follow.\n3. **Good Results**: The presented results are good.", "weaknesses": "1. **Weak Novelty**: The proposed approach is similar to GloGNN [A]. Also, the low rank pattern has been observed in some of the prior works [B]. [C] also builds a compatibility matrix to use in their model. However, what this paper has achieved is to put these ideas together in an effective way.\n2. **Unintuitive modeling choices**: The definition of $c_{ij}$ is quite unintuitive. While the individual terms have been explained, the way they are put together is inexplicable.\n3. **Large number of hyperparameters**: The number of hyperparameters go up significantly in this approach. It would be useful to have a hyperparameter sensitivity study.\n\n[A] Finding Global Homophily in Graph Neural Networks When Meeting Heterophily, ICML 2022.\n[B] Simple Truncated SVD based Model for Node Classification on Heterophilic Graphs, KDD 2021 Workshop on Deep Learning on Graphs.\n[C] Graph Neural Networks with Heterophily, AAAI 2021.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive and valuable comments! Here are our responses to your concerns.\n\n**W1 The differences between LRGNN and existing GNNs.**\n\n**R1**  We put the discussion comparing LRGNN and GloGNN [1] in Appendix Sec. E, please refer to it for a detailed description. Please refer to it for a comprehensive description. Although we acknowledge that the compatibility matrix is a commonly used technique for modeling node affinity and that the low-rank pattern is not a new discovery, we firmly believe that our paper introduces novel contributions and claims. Specifically, our use of low-rank matrix completion to predict label relationship matrices and the modeling of heterophilous graphs present unique contributions. Additionally, our paper identifies limitations of existing signed GNNs and proposes a promising solution by incorporating weak balance theory. These distinct aspects of our work effectively demonstrate its novelty.\n\n**Q2 Why the three terms can be put in a very simple additive model...**\n\n**R2** The first two terms take into account the reliability of the signed adjacency matrix from varying perspectives. Intuitively, when the estimator (the pseudo label $\\bar Y$) is more accurate, greater importance should be attributed to the Euclidean term. In heterophilous settings, greater importance should be assigned to the absolute term due to the effectiveness of the signed adjacency matrix generation algorithm in identifying heterophilous node pairs, as described in Section 4.2. Consequently, the significance of each term varies depending on the dataset. We leave the neural network to determine their importance using learned parameters. We visualize the learned weights using three datasets characterized by varying levels of edge homophily and estimator accuracy. \n\n|  weights  |  Wisconsin (E. H. = 0.11, Acc.=0.85) |  Cora (E. H. = 0.81, Acc.=0.87) | Squirrel (E. H. = 0.22, Acc.=0.53)|\n|  ----  | ----  | ---- |----| \n| Euclidean  |  0.38|  0.36 | 0.22 |\n| Absolute  | 0.40 |  0.34 |  0.36|\n| Attention  |    0.22|0.30 | 0.41|\n\nThe table indicates that the weight assigned to the Euclidean term is slightly higher when the accuracy of the estimator is high, and the Absolute term holds great importance under heterophily settings.\n\n**Q3 It seems almost unintuitive that the model is robust to arbitrary corruption...**\n\n**R3** Our experiments show that LRGNN exhibits robustness against **Gaussian noise with a standard deviation of less than 1**. This can be attributed to the use of a square loss that provides robustness against small and dense noise, namely the Gaussian noise, as it significantly diminishes the impact of a small noise (less than 1) through squaring. In fact, the L2 norm is considered optimal when attempting to recover a matrix corrupted by Gaussian noise [4]. Further, the capped norm also effectively improves its robustness against outliers.\n\nHowever, this is not the case for SignedGCN. In the case of e-e-f, nodes with different labels are occasionally misclassified as belonging to the same class. This misclassification introduces sparse noise with a large value of 2, which does not align with the characteristics of \"small and dense\".\n\n[1]Finding Global Homophily in Graph Neural Networks When Meeting Heterophily, ICML 2022. \n\n[2]Simple Truncated SVD based Model for Node Classification on Heterophilic Graphs, KDD 2021 Workshop on Deep Learning on Graphs.\n\n[3]Graph Neural Networks with Heterophily, AAAI 2021.\n\n[4]Robust matrix factorization with unknown noise, CVPR 2013.\n\n\n\n**Q4 Concern about the number of hyperparameters**\n\n**R4** We focus on the extra hyper-parameters introduced by LRGNN, namely \n|Notation| Effect |  Search space |\n| ----| ----| ----|\n|β | weight of initial residual|  [0.5, 0.9] |\n|μ | weight of adjacency matrix for constructing the initial node representation | [0.1, 0.9]|\n|δ| tendency to generate negative edges in signed adjacency matrix| [0, 0.9] |\n|γ|  weight of the attention term in the objective function| {0.0001, 0.001, 0.002, 0} |\n|q| Operating rank| dependent on the number of classes|\n|λ | weight of L2 regularization on $U$ and $V$ |  [0.01, 0.02, 0.05, 0.001]|\n|K | number of iterations to minimize the objective function| {1, 2} |\n|Estimator| the neural network used to generate signed adjacency matrix | {GCN,MLP} |\n\nHere K and Estimator have only two choices. The Estimator can be selected based on the accuracy of these two Estimators on the designated datasets. Additionally, q can be straightforwardly set to the number of classes. As a result, there is no need to tune the hyper-parameters Estimator and q. \n\nDuring fine-tuning the hyper-parameters we found that our model is insensitive to the choice of K, the values of λ, and the value of γ. In fact, the selection of K and the values of λ and γ (if within the search space for λ and γ, respectively) have a very small impact on accuracy. To demonstrate, we fix these three hyper-parameters as K=1, λ=0.01, and γ=0.001, and fine-tune other hyper-parameters. The results are presented in the table below.\n\n| | Texas | Wiscon. | Cornell| Actor| Squirrel | Chamel.| Cora| Citeseer | Pubmed|\n| ----| ----| ----| ----| ----| ----| ----| ----| ----|  ----| \n|LRGNN|90.27| 88.23| 86.22| 37.34| 74.38 |79.16| 88.33| 77.53| 90.16|\n|LRGNN-restricted|88.34 $\\scriptsize{\\downarrow1.94}$  |82.94 $\\scriptsize{\\downarrow 5.29}$|85.95 $\\scriptsize{\\downarrow0.27}$|35.21 $\\\\scriptsize{\\downarrow2.13}$  |72.35 $\\scriptsize{\\downarrow 2.03}$ |77.93 $\\scriptsize{\\downarrow1.23}$ |88.37$\\scriptsize{\\uparrow 0.04}$|76.82$\\scriptsize{\\downarrow{0.71}}$|  90.12$\\scriptsize{\\downarrow0.04}$|\n\nHere LRGNN-restricted refers to LRGNN with these three hyper-parameters being fixed and q is the number of classes. It can be observed that the decrease in accuracy is minimal, consistent with our previous statement. Thus, careful tuning is necessary only for β, μ, and δ. Tuning the hyper-parameters for LRGNN is not difficult."}, {"review_id": "U5hGgpdNje", "reviewer": "Reviewer_jP2E", "summary": "This paper introduces sign links to model both the homophilous and heterophilous relationships in the global graph, thus extending the applicability of GNNs beyond heterophily. Additionally, the paper leverages the weak balance theory to support the existence of a global low-rank structure in the signed graph and formulates sign link prediction as a robust low-rank matrix approximation problem. Experimental results demonstrate the effectiveness and performance improvement of the proposed approach.", "questions": "1. The idea behind LRGNN bears similarities to FAGCN; however, the author fails to provide a detailed explanation of the differences between them.\n2. There is a lack of experimental comparisons with state-of-the-art (SOTA) models such as FAGCN [1], DMP [4], and Ordered GNN [5].\n3. The paper lacks experimental comparisons with other popular large-scale datasets, as mentioned in [6], such as pokec, snap-patents, and twitch-gamers.\n4. Figure 3 solely displays the recovery loss on heterophily graphs. It would be valuable to include the results on homophily graphs as well.\n\n[4]Yang, L., Li, M., Liu, L., Wang, C., Cao, X., & Guo, Y. (2021). Diverse message passing for attribute with heterophily. In NeurIPS, 34, 4751-4763.\n\n[5]Song, Y., Zhou, C., Wang, X., & Lin, Z. (2023). Ordered GNN: Ordering message passing to deal with heterophily and over-smoothing. In ICLR.\n\n[6]Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., & Lim, S. N. (2021). Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In NeurIPS, 34, 20887-20902.\n\n---------\nUpdate: Most of the above concerns have been addressed.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Clarity:\n1. The submission demonstrates clear writing, readability, and a well-organized structure.\n2. The supplementary material provides additional details that enhance the reproducibility of the results.\n\nQuality:\n1. The claims put forth in the submission are strongly backed by theoretical and empirical analyses.\n2. The inclusion of the structural balance theory and conducting accuracy comparison, ablation, and visualization experiments significantly bolsters the overall quality of the submission.", "weaknesses": "Originality\n1. The originality of the contributions can be strengthened by explaining the differences and comparing them with several relevant existing works, such as FAGCN [1], HOG-GCN [2], etc.\n2. In particular, the description in the paper about how the proposed signed GNN can better work for heterophily problems is insufficient.\n\nSignificance\n1. Most heterophily datasets considered in the paper have issues (e.g., small scale, train-test data leakage, etc.) as pointed out by recent publications on high-quality heterophily datasets [3].\n2. Strengthening the significance of the contributions can be achieved by incorporating important references and conducting experimental comparisons.\n\n[1]Bo, D., Wang, X., Shi, C., & Shen, H. (2021). Beyond low-frequency information in graph convolutional networks. In AAAI, 35, 3950-3957.\n\n[2]Wang, T., Jin, D., Wang, R., He, D., & Huang, Y. (2022). Powerful graph convolutional networks with adaptive propagation mechanism for homophily and heterophily. In AAAI, 36, 4210-4218.\n\n[3]Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2023). A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. In ICLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable suggestions for improving our paper and for appraising the quality and clarity of our paper. Here are our responses to your questions, and we put the tables in the uploaded pdf file.\n\n**Q1 On the differences between LRGNN and existing models.**\n\n**R1** Thanks for the suggestion, and we would like to discuss the limitation concerning the expressive power of FAGCN. FAGCN derives the propagation weights using neural networks, while LRGNN is based on traditional matrix completion.  In FAGCN, the propagation weight for edge $(i,j)$ is computed as\n\n$\\alpha_{i,j} = tanh(g^T [h_i || h_j]) = tanh (g_1^T h_i + g_2^Th_j), g = [g_1||g_2]$ \n\nThis attention function has been proven to be static, as shown in recent research [1]. \nSince tanh is a monotonic function, for $\\forall i,j,m,n$,  if $\\alpha_{i,m}>\\alpha_{i,n}$, we have $g_1^T h_i + g_2^Th_m > g_1^T h_i + g_2^Th_n$. Therefore, $g_2^Th_m>g_2^Th_n$, which indicates $g_1^T h_j+ g_2^Th_m > g_1^T h_j + g_2^Th_n$ and $\\alpha_{j,m}>\\alpha_{j,n}$. In short, for FAGCN, if we observe $\\alpha_{i,m}>\\alpha_{i,n}$, then we know $\\alpha_{j,m}>\\alpha_{j,n}$, irrespective of the label relationships between $j$ and $m$, or $j$ and $n$.  Hence, the ranking of the attention scores is unconditioned on the query node, $i$ and $j$ in this case. \n\nIn contrast, our visualization results (Fig. 4) demonstrate that For LRGNN, the within-class, and between-class weights are positioned on opposite sides of the zero.  As discussed in Sec. 3, FAGCN is a standard signed GNN based on structural balance theory, while LRGNN is a naturally weakly-balanced model as it aggregates all nodes’ representations for a node in one-hop propagation. This together explains LRGNN's superiority over FAGCN.\n\nThe signed feature propagation has not been explicitly modeled **in HOG-GCN**. This is crucial because negative propagation weights are necessary to push away node pairs with different labels in the embedding space. Additionally, HOG-GCN amplifies the neighborhood of nodes by explicitly computing $A^k$. However, this calculation greatly increases the time complexity. For instance, when $k=3$, the time complexity of HOG-GCN becomes cubic, while the time complexity of LRGNN is linear to the # of edges.\n\n[1] Brody, Shaked, Uri Alon, and Eran Yahav. \"How attentive are graph attention networks?.\" ICLR 2022.\n\n**Q2 There is a lack of experimental comparisons with state-of-the-art (SOTA) models...**\n\n**R2** We **included Ordered GNN** as a baseline model in our experiment section for performance comparison. Please refer to line 272, table 2, and table 3 (**abbreviated as OGNN** in the table otherwise the page will be overwhelmed by the table). Unfortunately, it seems that the authors of DMP and HOG-GCN did not make their source codes publicly available, as we could not find any relevant implementations on GitHub or any links to the source codes in their papers. Additionally, the dataset split used in DMP differs from our own, and the experimental results provided in the HOG-GCN paper only cover a subset of the datasets used in our paper.  Given these limitations, we can only implement FAGCN and directly use the available results from the HOG-GCN paper for comparison. Please see the pdf file for the results.\n\n**Q3 The limitations of the datasets considered in the paper**\n\n**R3** Actually, we read the paper [2] during its reviewing phase and highly valued its insights and contributions to the community. Nevertheless, we selected these datasets as they are currently the most widely utilized by the community, despite their known limitations. For example, a recent paper [3] accepted at ICML and the most recent papers [4][5] published on arXiv adopted these datasets for their experiments. We duly appreciate the reviewer's efforts in advancing the evaluation of GNNs under heterophily. We provide the results on the datasets from [2] for your reference. Note that the results of baselines are directly taken from [2].\n\nAs indicated by [2], classic GNNs generally perform better than heterophily-specific models on these datasets. The performance of LRGNN is comparable to FSGNN and surpasses other heterophily-specific models. \n\n[2] Platonov, Oleg, et al. \"A critical look at the evaluation of GNNs under heterophily: are we really making progress?.\" ICLR 2023.\n\n[3] Zheng, Yizhen, et al. \"Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs.\" ICML 2023.\n\n[4] Wang, Junfu, et al. \"Heterophily-Aware Graph Attention Network.\" arXiv preprint arXiv:2302.03228 (2023).\n\n[5] Yang, Wenhan, and Baharan Mirzasoleiman. \"Contrastive Learning under Heterophily.\" arXiv preprint arXiv:2303.06344 (2023).\n\n**Q4 The paper lacks experimental comparisons with other popular large-scale datasets...**\n\n**R4** We have included three out of six large-scale datasets released by [6] for evaluation. However, the remaining datasets, pokec, snap-patents, and twitch-gamers are too large, and such a huge scale presents significant computational challenges for our machines. For instance, pokec consists of over 1.6 million nodes and 30 million edges. We acknowledge the significance of evaluating a new method using large-scale datasets and understand the concern expressed by the reviewer. We are sorry that, unfortunately, due to limited resources, we are unable to conduct experiments on pokec and snap-patents. Thus, we only present the results on the twitch-gamers dataset, which is processed using CPUs. We will consider other datasets in our future work once more computational resources are available. \n\n[6] Lim, Derek, et al. \"Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.\" NeurIPS 2022.\n\n**Q5 Figure 3 solely displays the recovery loss on heterophily graphs...**\n\n**R5** The visualization results on the homophily graphs can be found in the newly uploaded PDF file. Kindly refer to it for further information.\n"}, {"review_id": "usCnHuQxD5", "reviewer": "Reviewer_B8tM", "summary": "The paper proposes a Low-Rank Graph Neural Network (LRGNN) that can model both homophilous and heterophilous graphs via signed propogation (two nodes with the same class label share a positive edge and with different class share a negative edge). The authors predict the label relationship matrix by solving a robust low-rank matrix approximation problem, which results in a block diagonal structure and varying distributions of within-class and between-class entries.\n", "questions": "N/A", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Clarity: The paper is generally easy to follow.\n\nNovelty: The authors propose a low-rank matrix approximation technique for predicting the label relationship matrix and enhancing the representation power of nodes. This technique is designed to utilize the low-rank properties of weakly-balanced graphs. \n\nExperiments: The authors have conducted extensive experiments on both synthetic and real-world graphs to evaluate the proposed method. The results indicate that LRGNN outperforms other baseline methods on both synthetic and real-world graphs.\n\nPresentation: The paper is well-structured and many visualization analysis are provided to better assess the qualitative and quantitive analysis of the proposed model.\n\n", "weaknesses": "Assumption of Uniform Distribution: The main theoretical support for the approach assumes a uniform distribution of node degrees. However, in practice, node degree distributions frequently follow a power-law distribution that is non-uniform. Although the main results of this paper are obtained using real-world graphs with non-uniform node degree distributions, it is unclear how this affects the theoretical results. \n\nDependence on Pseudo Labels: It is mentioned that LRGNN’s performance is affected by the accuracy of the generated pseudo labels. Although the supplementary material provides an experiment that indicates LRGNN demonstrates a non-sensitive response to this impact, further exploration and discussion are needed to fully investigate the theoretical implications. Additionally, the motivation of using signed labels for edges is not strong enough becuase 1) only applies for homogenous graphs. 2) When the # of class labels is high, such strategy may lose a lot class-related information so it may not generalize.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's positive acknowledgment  on the clarity, novel, experiments, and presentation of our paper. For the weakness part, we have indeed discussed these limitations in the last section of our paper and devote much efforts to support the robustness of LRGNN by presenting extensive designated experiments in our experiment section as well as the Appendix.\n\nUniform Distribution:  The real-world datasets considered in our research exhibit non-uniform distributions, yet our experimental results validate the strong performance of our model on such datasets. In Appendix A, we have provided a detailed discussion and conducted an experiment to empirically demonstrate the effectiveness of low-rank matrix factorization (LRMF) in accurately predicting the label relationship matrix, despite the non-uniform distribution of observed entries.\n\nDependence on Pseudo Labels: We believe LRGNN does not rely on accurate pseudo labels. In fact, the weakest estimator used to generate pseudo labels is the one for the Squirrel, which has an accuracy of about 50%, while LRGNN achieves an impressive 74.38% accuracy on Squirrel, surpassing the runner-up score significantly. Thus, LRGNN demonstrates to be effective even when the generated pseudo labels are less reliable. Moreover, the experimental results in the Appendix indicate that the performance of LRGNN endures only a minor impact when the pseudo labels are corrupted by random noises.\n\nWe recognize the significance of the theoretical implications that arise from the shape of the distribution and the accuracy of pseudo labels.  We plan to dedicate our future work to explore the theoretical aspects. \n\nIn summary, we appreciate the reviewer for acknowledging the strengths of our paper include the clarity, novelty, experiments, and presentation. For the limitation mentioned in our paper, we will make further improvement upon our recent trials in the future work."}]

Author rebuttal:
Dear Reviewers and AC,

In response to the concerns raised by Reviewer jP2E, we have presented tables that juxtapose LRGNN with existing baselines across a spectrum of recent and large-scale datasets. This should help alleviate concerns regarding the scope of datasets used in our initial study. To elucidate on the distinctions, we delve deeper into the expressive constraints of FAGCN. One of the core tenets of our work is the novel integration of low-rank matrix completion within GNNs, particularly tailored for Heterophily graphs. Alongside this, our paper also sheds both theoretical and empirical light on the inherent limitations of the current crop of signed GNNs – an exploration that remains largely untouched in prior research. Addressing the queries posed by Reviewer mJPn, we have included a hyper-parameter sensitivity analysis. Furthermore, to offer a transparent view on our methodology, a table elucidating the learned weights has been incorporated. This should provide clarity on the amalgamation of terms in $c_{i,j}$ and any apprehensions regarding the volume of hyperparameters. For reviewer rmTT, who expressed concerns about the potential dependency on the size and quality of the observed entries, we direct attention to the plethora of figures and examples (both from real-world scenarios and generated datasets) in Appendix A and B of our initial submission, underscoring the resilience of our approach. Lastly, we have taken steps to clearly address the questions from Reviewer JZ4m, elucidating on the nature of $\tilde{A}$, diving deeper into matrix completion, and providing a clearer perspective on our optimization algorithm.

We want to express our gratitude to the reviewers for their valuable suggestions and would greatly appreciate any further questions they may have regarding our paper. If our responses have addressed your questions, we would kindly ask for your reconsideration of the scores.

Meta-review: **Summary:**

The paper proposes a low-rank graph neural network (LRGNN) that predicts the global label relationship matrix using a low-rank matrix completion technique. The predicted matrix is then used to aggregate node features in a GNN framework. The paper provides theoretical and empirical evidence for the effectiveness and robustness of LRGNN on various real-world and synthetic datasets.

**Strengths:**
- The paper presents a novel and elegant approach that combines low-rank matrix completion and GNNs to model the label relationships in heterophilous graphs.
- The paper is well-written, clear, and easy to follow.

**Weaknesses:**
- The novelty of LRGNN is somewhat limited, as it builds upon existing techniques such as compatibility matrices, low-rank matrix factorization, and signed GNNs.
- The number of hyperparameters in LRGNN is large, which may affect its scalability and generalization.

**Decision:**

After the rebuttal, all reviewers are generally positive towards this submission. An acceptance (poster) is suggested.
Decision: Accept (poster)