Low-Rank Graph Neural Networks Inspired by the Weak-balance Theory in Social Networks
Authors: Langzhang Liang
Xiangjing Hu
Zenglin Xu
Zixing Song
Irwin King
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph neural networks
heterophily
social theory
low rank

Abstract: Graph Neural Networks (GNNs) have achieved state-of-the-art performance on node classification tasks by exploiting both the graph structures and node features. Generally, most existing GNNs depend on the implicit homophily assumption that nodes belonging to the same class are more likely to be connected. However, GNNs may fail to model heterophilious graphs where nodes with different labels tend to be linked, as shown in recent studies.  To address this issue, we propose a generic GNN applicable to both homophilious and heterophilious graphs, namely Low-Rank Graph Neural Network (LRGNN). In detail, we aim at computing a coefficient matrix such that the sign of each coefficient reveals whether the corresponding two nodes belong to the same class, which is similar to the sign inference problem. In Signed Social Networks (SSNs), the sign inference problem can be modeled as a low-rank matrix factorization (LRMF) problem due to the global low-rank structure described by the weak balance theory. In this paper, we show that signed graphs are naturally generalized weakly-balanced when considering node classification tasks. Motivated by this observation, we propose to leverage LRMF to recover a coefficient matrix from a partially observed signed adjacency matrix. To effectively capture the node similarity, we further incorporate the low-rank representation (LRR) method. Our theoretical result shows that under our update rule of node representations, LRR obtained by solving a subspace clustering problem can recover the subspace structure of node representations. To solve the corresponding optimization problem, we utilize an iterative optimization algorithm with a convergence guarantee and develop a neural-style initialization manner that enables fast convergence. Finally, extensive experimental evaluation on both real-world and synthetic graphs has validated the superior performance of LRGNN over various state-of-the-art GNNs. In particular, LRGNN can offer clear performance gains in a scenario when the node features are not informative enough.

Under review as a conference paper at ICLR 2023
NETWORKS INSPIRED BY THE WEAK-BALANCE THEORY IN SOCIAL NETWORKS
LOW-RANK
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) have achieved state-of-the-art performance on node classification tasks by exploiting both the graph structures and node features. Generally, most existing GNNs depend on the implicit homophily assumption that nodes belonging to the same class are more likely to be connected. However, GNNs may fail to model heterophilious graphs where nodes with different labels tend to be linked, as shown in recent studies. To address this issue, we propose a generic GNN applicable to both homophilious and heterophilious graphs, namely Low-Rank Graph Neural Network (LRGNN). In detail, we aim at computing a coefficient matrix such that the sign of each coefficient reveals whether the corre- sponding two nodes belong to the same class, which is similar the sign inference problem in Signed Social Networks. In this paper, we show that signed graphs are naturally generalized beakkl-bbllanee for node classification tasks. Motivated by this observation, we propose to leverage low-rank matrix factorization (LRMF) to recover a coefficient matrix from partially observed signed adjacency matrix. To effectively capture the node similarity, we further incorporate the low-rank repre- sentation (LRR) method. Our theoretical result shows that under the update rule of node representations, LRR obtained by solving a subspace clustering problem can recover the subspace structure node representations, To solve the corresponding optimization problem, we utilize iterative optimization algorithm with conver- gence guarantee and develop a neural-style initialization manner that enables fast convergence. Finally, extensive experimental evaluation both weal-world and synthetic graphs has validated the superior performance of LRRNN over various state-of-the-art GNNs. In particular, LRGNN can offer clear performance gains in scenario when the node features are not informative enough. Our code is available https: / anonymoossos..s... waroooussspppeeee 4open. wwwwsceeeieeeeeieeeeeeeee 4551/.
INTRODUCTION
Graphs (or networks) are ubiquitous in variety of fields, such as social networks, biology, and chemistry. Many real-world networks follow the Homophily assumption, í.e., linked nodes tend share the same label have similar features; while for graphs with heterophily, nodes with different labels are more likely to form a link. For example, many people tend to connect with people of the opposite sex in dating graphs. For graphs with homophily, Graph Neural Networks (GNNs) variants (Kipf& & Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018 8) have achieved remarkable successes on various graph mining tasks. Among them, Graph Convolutional Network (GCN) (Kipf & Welling, 2017) and Graph Attention Networks (GATs) (Velickovic et al., 2018) are representative methods. However, the performance of GNNs deteriorates when learning on graphs with heterophily, in that the smoothing operation used in traditional GNNs tends to make representations of neighhoring nodes similar, even though they have different labels.
Some designs (Zhu et al., 2020; Chien et al., 2021; Lim et al., 2021) have been proposed to enhance the representational power GNNs under heterophilous scenarios (see Zheng et al. (2022) for survey). Among them, high-pass filters are the most frequently used components since they can push away a node from its neighbors in the embedding space, which conforms to the characteristic of heterophily that nodes generally dissimilar their neighbors. High-pass filters are usually realized by negating the normalized adjacency matrix. In the spatial graph convolution domain, signed message passing (Yan al., 2021; Bo al., 2021) allows negative aggregation coefficients

---

Under review as a conference paper at ICLR 2023
so to push away those neighboring heterophilious nodes. However, most existing methods have weaknesses that restrict their representational power. Spectral- based methods (Chien et al.. 2021; Luan et al., 2)21) combine high-pass filters with low-pass ones by linearly combining the outputs of intermediate layers. These methods fail to capture the node-level homophily ratio as they utilizes only one type of convolutional filters in each layer. Additionally, spatial- methods (Bo al,, 2021; Yang et al., 2021) update the representation of each node by computing learnable weighted combination of the representations of its neighbors and updating the aggregation coefficients based on the attention function used in Graph Attention Network (GAT) (Velickovic et al., 2018). As GAT computes form of static attention and the ranking of the attention scores is unconditioned on the query node (Brody et al., 2022), this attention function is prone to produce uniform attention scores and cannot distinguish nodes of different classes when their distributions of features are of small difference (Fountoulakis et al., 2022).
In this paper, we address the challenges of generalizing GNNs to heterophilious graphs with the help of social theory developed from signed social networks (SSNs) whose positive links represent the friendship between two users while whose negative links represent enmity. Similarly, we call the graphs with negative edges as signed graphs. In SSNs, a practical theory called the weak balance theory (Davis, 1967) modifies the structural balance theory (Cartwright & Harary, 1956) by elimi- nating the patter "an enemy of my enemy is my friend", and keeping the following patterns of "an enemy of my friend is my enemy", "a friend of my friend is my friend", and "a friend of my enemy my enemy". In the context of node classification task, we can view homophily and heterophily as friendship and enmity, respectively. It is easy to verify that signed graphs are weakly balanced when considering node classification tasks, e.g., homophilious neighbor of my homophilious neighbor is also a homophilious node to me but a heterophilious neighbor of my heterophilious neighbor is not necessarily& homophilious node. The weak balance naturally leads to a global low-rank structure for the network, based on which the sign inference problem can be formulated as a low-rank matrix completion problem (I (LRMC) (Hsieh et al., 2012).
The weak-balance theory motivates us to apply low-rank approximation approaches to node classi- fication on heterophilious graphs. Specifically, given a partially observed signed adjacency matrix (where negative edges are allowed), we aim to recover coefficient matrix Z via low-rank approx- imation methods, such that a positive Z,,, implies node U; and vj have the same label and the magnitude of Zi,j represents the importance of node Uy U/- Then we use Z to update node representations by performing feature propagation in GŇNs. Due to the polynomial time complexity of solving LRMC which is practically infeasible for large networks, we resort to the low-rank ma- trix factorization (LRMF) technique that is scalable to large graphs. The low-rank approximation of signed networks can achieve satisfactory or even exact recovery under certain assumptions as stated in Davenport& & Romberg (2016). Furthermore, to better capture the similarity between node repre- sentations, we leverage the low-rank representation((RN) (Liu al., 2010) learning for recovering the underlying subspace structure on heterophilious graphs. Thus, we name the new derived GNN as Low Rank Graph Neural Network (LRGNN). It is important to note that the low-rank assumption was used to improve the defense over adversarial examples (Jin et al., 2020), it is not designed for heterophilious graph modeling and not implemented for signed graphs. To solve the corresponding non-convex optimization problem, utilize the softImpute which minimizes the objective function by minimizing a surrogate function. Though LRGNN char- acterizes a node's representation using the linear combination of all the node representations, reduce the time complexity to linear by leveraging some tricks of matrix multiplication. Extensive experimental results on both real-world and synthetic datasets showed the superior performance and efficiency of LRGNN over tate-of-the-aae methods. We put all proofs and the discussion of related work in Appendix due to the space limitation.
algorithm (Hastie et al.. 2015)
can
2 PRELIMINARIES
Notations. Denote by G = (V, E) a undirected graph, where V and E denote the node set and edge set, respectively. The nodes are described by a node feature matrix X E Raxs, where n and f are the number of nodes and number of features per node, respectively. Y E Raae is the node label matrix. The neighbor set of node v; is denoted by Mr. We denote the node representation matrix in the [-th layer by H(), We let A denote the adjacency matrix that generally Ar,; = 1 if (i. E E and O otherwise; while in signed graphs (networks), we extend the values of adjacency matrix to
2

---

Under review as a conference paper at ICLR 2023
(-1,0, 0, 1), where 1 corresponds to homophily (e.g., friendship). -1 corresponds to heterophily (e.g., enmity ), and 0 stands for unknown relationship. We call this generalized adjacency matrix as the signed adjacency matrix and denote it by A. The Frobenius norm of a matrix is given by || [l.- A.;: represents the i-th row of matrix A.
We define the underlying complete graph and generalized k-weakly balanced graph as follows.
Definition 1. For a signed graph, its underlying complete graph is given by adding all the missing edges to the graph, with appropriate signs, so that the resulting complete graph contains no positive links that connect two enemies (heterophilious nodes).
Definition 2. A signed graph is said to be generalized e-weakly balanced if the nodes can be divided into e groups such that in its underlying complete graph, all the within- group edges are positive and all the between- group edges are negative.
Signed graphs are naturally generalized c-weakly balanced when considering node classification tasks with classes. Figure I shows an example of a 3-weakly balanced graph. The following theorem reveals the low-rank structures of generalized weakly balanced graphs.
Theorem 1, (Hsieh et al., 2012) The signed adjacency matrix of the underlying complete graph of generalized c-weakly balanced graph is exactly of rank if >> 2, and rank if S 2.
Considering low-rank structures, it is natural to model the edge sign inference problem an LRMC problem since LRMC can provide theoretical guarantees for exact re- covery under some conditions. Given a partially observed signed matrix adjacency A, the task of LRMC to find the lowest-rank solution among all the feasible solutions:
-1
-1
-1
-3
min rank s.t. Pn(Z) = (A), (1)
Figure 1: An illustrative example of
3 3-weakly balanced signed graph and its adjacency matrix of rank 3. Color cor- responds to label.
where Pn(-) is an element-wise function defined Pa (M,,. M.j if (i,j) E & and 0 otherwise, for
an arbitrary matrix M E RT Unfortunately, (1) a
NP-hard problem. An approximate optimization problem of (1) can be obtained using the convex relaxation
min
|Z||, s.t. PZ = PA))),
where |Z||- denotes the nuclear norm of Z, which is the tightest convex relaxation of rank. Note that the values of entries of Z can be continuous. This optimization problem be solved to yield the global optimal solution in polynomial time in many cases (Candès & Recht, 2012) 2). We next discuss the conditions of perfect recovery. Let T be the class imbalance defined T mar {n/n:), where is the number of nodes, n; the number of nodes of the i-th class. A surprising result involving LRMC that by solving (2), perfect recovery from the observations possible if certain assumptions hold.
Theorem 2. (Hsieh et al., 2012) (Recovery Condition for Signed Networks) Suppose we observe edges As.j. (i.j) E Ω, from a k-weakly balanced signed network A". Also, suppose that the following assumptions hold: (1) k is bounded (k O(1)), (2) the set of observed entries Ω is uniformly sampled, and (3) number of samples is sufficiently large, iee, | 2 C+ Cr'nlog2n, n, where G is constant.
Then A, can be perfectly recovered by solving (2) with probability at least n -3
Although LRMC can conditionally provide exact recovery, solving (2) requires performing singular value decomposition on potentially large matrix, which is computationally expensive. In practice, real-world graphs may have large number of nodes. To make this idea practical, fast algorithm is needed. To this end, we further relax the objective as
min [Z
rank < 4. A)1 s.t.
where e 5 q & n is parameter. The constraint on the rank of Z can be guaranteed by decomposing Z into the product of two low-rank matrices. This gives an LRMF problem.
min U. Ug
PP(UUTT
AII + AO(U, V),
(4)
3

---

Under review as a conference paper at ICLR 2023
where À is parameter and ((:--) regularizer that encourages some desired properties in U, V. such as sparsity, non-negative, and orthogonality. Though (4) is a difficult non-convex problem with adopt alternating minimization based algorithms to obtain approximate yet good solutions. We note that matrix factorization (MF) algorithms predict the sign and magnitude of aggregation coefficient (UV"),, ). only using the information from the observed entries in Å.
no known globally convergent algorithm,
Low RANK GRAPH NEURAL NETWORKS
In this section, we present the overall framework of Low Rank Graph Neural Networks and the corresponding optimization algorithm.
3.1 OVERALL FRAMEWORK
Here, we detail our model design. Inspired by Lim et al. (2021), we first apply MLPs to fuse feature matrix and adjacency matrix into lower-dimensions. matrix H E R=
H (0) = - p)) (MLP)(AA),
(5)
where 0 < μ < 1 is the balance term. We here use adjacency matrix A to exploit the information of graph topology MF-based methods will recover complete graph from observations, where information of the original graph topology is lost.
For the updating of deeper layers, we introduce hyper- papper-rrrmeter 3 as motivated from APPNP (Klicpera et al., 2019) by keeping the term (H) which is known to especially useful for learning on heterophilous graphs since not restricted by the homophily assumption. Once
have coefficient matrix v(!)!!" for the 1-th layer, the node representations for the (1 + 1)-th layer are updated as
H++ (1 B)U!
H
(6)
where 0 < <1,, 1 v Rxg are derived by minimizing the following objective function
F(U v(0)= = ( (1 vV H +
-A)
(7)
where ς weights the importance of the MF term. The first term the propagation term which enables the aggregation coefficients to capture the similarity of node representations via involving matrix ( and ()) It is important to note that the first term can be derived from the low-rank representation learning of the coefficient matrix (as will described in Section 4). This term is also closely related to GloGNN (Li et al., 2022) and the difference will be discussed in Section 4. The second term is the MF term that aims to recover the missing edges from observed ones. Therefore, method captures node correlations and derives aggregation coefficients considering both the observed edges and node representations.
There are still several problems we need to address. First, the signed adjacency matrix is not available. Second, optimizing (7) is not trivial due to the element-wise function Pn(-) and the propagation term. Finally, is important to find a good starting point for and V so as to converge within small number of iterations.
To address the first problem, we can use any off-the-shelf neural network classifier to generate pseudo labels. We also exploit the known node labels in training set Ty and the label matrix Y. Similar to Zhu et al. (2021), we generate the pseudo labels as follows,
Y 7=0oY+ O) Ý, Ý = Softmax(P),, P SNN(((X),
where f.N(.) denotes a trained neural network, @ the Hadamard product, and O i Ty. otherwise. The signed adjacency matrix is defined as A,, (Y Y,.) - 5 (i.j) E and 0 otherwise. Here, 0 5 < is parameter to control the ratio of negative edge weights. (:)) denotes the inner product of two vectors. We note that one can use stored pseudo labels generated by any model. In experiments, use simple models including GCN and MI. for faimesss.
4

---

Under review as a conference paper at ICLR 2023
3.2 SOFTIMPUTE ALTERNATING LEAST SQUARES ALGORITHM
Practical solutions to LRMF fall into two main camps, i.e, Alternating Least Squares algorithm (ALS) (Wiberg, 1976; Shum et al., 1995; Huynh al., 2003) and Newton methods (Buchanan & Fitzgibbon, 2005; Okatani & Deguchi, 2007; Chen, 2008). We refer the interested reader to Daven- port & Romberg (2016) for survey. Unfortunately, both these methods are difficult handle additional constraints. The propagation term hinders us to optimize (7) by ALS or Newton methods. To tackle this issue, we make use of the softImute-AALS algorithm (Hastie al., 2015). Consider that we have current estimates ( and ViO, and we now wish derive a new U that minimize the objective. We first introduce the following surrogate function for deriving UO)
Su (Zul (()) = ( (1 B) VOT H
3H (0)
O 11
(Z V A) + (Z V() -W
where (-) is element-wis wise function and defined (M,)) M.j if (i,j) & & and otherwise. Then ( can be obtained by minimizing the surrogate function over Zo, i.e. Ú(!) argmin Zu eRoxg
Sy Sz V The closed-form solution is (see Appendix A.1).
T = (AV + - H " ( 3(1 3)
H) HO voJ.
I/ V + (1 B) HOH V011
(10)
where Ā Pa(A) (TW Similarly, define surrogate function for deriving (
Sy (Zv ( V() = | (1 -1-33) () (H
P/ ( zz Á) + Po (Ū TW'"" )}>
(11)
We obtain ( by minimizing the above surrogate function over Zy The closed-form solution is
Vi = h- + (1 H
hATOO (1 B) HOO T B(1 3) H O)
TO (T 1(11
(12)
Here À (A) (U"))))) We establish the following result justify the design of the surrogate functions.
Theorem 3. (Correctness) The functiion (7) is non-increasing under the update rules (10)
and (12),
F(U(O) V() S F( S F(D(, (
(13)
One calculate (++1) in time complexity linear to the number of edges using some tricks of matrix multiplication. See appendix A.3 for a detailed discussion.
Remark 1.
Most traditional approaches randomly initialize U and V. In this paper, we employ a more neural- style initialization manner.
U (1) init argiin U
| - (1) init 11
(Āv!)
(
(V (D) intt ini init) -1
v!
v!)) inst finit (H)
(14)
Here (imie.) denotes fully-connected layer graph convolution layer, depending on the ho- mophily ratio. We empirically found that this initialization can provide better results within a few iterations for updates. The pseudocode of LRGNN can be found in Appendix A.2.
4 PLACING LRGNN IN THE CONTEXT OF SUBSPACE CLUSTERING
In this section, we show that the propagation term can be derived by performing subspace clustering using low-rank representation (LRR) (Liu et al., 2010). We consider the subspace clustering prob- lem. Given a set of data samples (each sample is associated with vector) drawn from union of linear subspaces, the goal of subspace clustering is to group the samples into their respective sub- spaces. Spectral-type methods first learn coefficient matrix from the given data, then the clustering
5

---

Under review as a conference paper at ICLR 2023
results can be obtained by applying spectral clustering methods the coefficient matrix. Suppose we have data matrix X E Ia at hand, we want to find a coefficient matrix such that each of data samples can be represented by the linear combination of the basis in "dictionary" D E Rxxd as X ZD, where 2 describes the affinity between the i-th sample and j-th sample and e; the representation of the i-th sample. LRR aims finding the lowest-rank representation among all the candidates.
LRR is robust noise and outliers in the subspace clustering problem (Liu et al., 2010). Latent Low-Rank Representation (LatLRR) (Liu & Yan, 2011) further improves LRR with hidden data. We consider a variant LatLRR,
min
|||| + A||Z|| s.t. X [ B)X | (1 8)2x + 8X,, (15)
where X E RRa the hidden data matrix and a parameter to weight the importance hidden data. Back to our problem, now we wish to perform subspace clustering on H When we consider the graphs with heterophily, it is advisable use the initial node representations H hidden data
since it is not restricted by the homophily assumption. By appropriately replacing the symbols, we obtain our final optimization problem
min
||||-- + ? 8.1. H (1 - 3y2H + HH
(16)
The low-rank structure induced by the nuclear norm regularization on Z is of great significance. We have the following result.
Theorem 4, Assume that the row vectors (node representations) of ( are drawn from a union of independent subspaces {S:) Also Assume that the update rule of node representation matrix
( = (1 3)z H + (0)
(17)
where ( is an optimal solution (assume it exists) to the following optimization problem
min
Z + A|Z
s.l. H = (1 (0-3)211 ZH (H)
(18)
where B 0. Then for any node-pair (denoted by u, and 0U) that belong to different subspaces, we have Z = 0, vl 2 0.
When the number of clusters is known (e.g., c) and the number of columns in U (i.e., 2) is sufficiently larger than c, the nuclear norm minimization problem can be equivalently replaced by the low-rank decomposition (Cabral et al., 2013). We therefore have the following optimization problem
min ( E
| - (1 ()
( XX VO"""00" ||:
s.l. 2 e (19)
The first term is exactly the propagation term in (7). Our numerical simulation experiments show that LRR obtained by solving (19) can reveal the membership of the samples: within-subspace elements dense, and the between-subspace elements are sparse. We here in- clude X|I (00 1| for theoretical completeness. In our simulations, as X' increases, within-subspace ele- ments get closer to zeros, shown in Figure 2. There- fore, our objective function excludes this regularization term. The detailed settings and more simulation results are provided Appendix A.6. In summary, our objective function contains two parts. The propagation term is mo- tivated by the LRR method for subspace clustering. The second MF term inspired by the low-rank structures of the
k=10.iinomdoon-0, #cusstorse 5.tw
willr silquro
0.030
0,520
Aceraged
0.25
0.935
0.0031 0.002
Figure 2: Numerical simulation result. The low-rank representation is obtained by solving (19). The shaded region in- dicates 95% confidence interval.
graphs.
Discussion. A closely related work is the GloGNN (Li et al., 2022), which defines the coefficient matrix
z argmin ( (1 H
3H
(0) + 7
-AGNN 1 (20)
z

---

Under review as a conference paper at ICLR 2023
Texas
Wiscon,
Cornell
Actor
Squirrel
Chamel.
Cora
Citeseer
Pubmed
MLP
80.81 85.29
49 36,53+0:70 28.77+1.56 46,21+2.99 75.6942.00 74.02=1 1.90 87.16=
GCN
55.1445.16 51.76+3.06
60.54+5.30 27.32=1.10 53.43+2.01 64.82+2.24 16.98+1.27 76.50=1.M 88.42+0.50
GAT
52.16+6.3 49.41+4.09
61. .9.8.995
27.44+0.89
40.72+1.55
60.26+2.50
87.30=1.10 10 76.55+1.25
86,33+0.48
MixHlop
77.8427.73 75.88a4.90
73.51e6.34
32.22a2.34
43.80a1.48
60.50a2.53 87.61 76.26=1.35
25.31
H,GCN
84.8627.23 87.65s4.98
82.70&5.28
35.70a1.00
36,4821.86
60.1 1a2.15 87.87a1.20 17.1 89,4920.38
GPR-GNN
78.3844.36
82.94x4.21
80.27a8.11
34.63a1.22
31.61 46.58s1.71
87,95a1.18
77.13=1.67 87. 27.54
WRGAT
83.62:5.50
86.98+3.78
$1.62+3.90 90 36.53=0.77
48.85=0.77
65.24+0877
88.20=2.26
76.81=1.8 89 88.52=0.92
GloGNN+ 84, 00. 88.0443.22
85.95+5.10 10 37.70=1.40
57.88=1.76
71.21+1.84
88.33=1.09
77.22=1.78 89.24=0.39
GGCN 84, 86+4.55 86.86+3.29 29 85.6826.63
17.54
55,17=1.55
71.14+1.84
87.95=1.05
77.14=1.45 45 89,15=0.37
ACM-GCN
$7.84+4.40 88.4333.22
85, 14..07
36.28s1.09
54.40=1.88
66.93a1.85
87.91
77.32+1.70
90,00=0.52
LINKX 74.60
75.49 77.84+5.81
36.10 15.155
+1.8
68.42+1.38
84.64=1.13
73.19=0.99
87. 37.8670.77
LRGNN 89.1924.49 88.2343.04 86.22+6.10 37.10+2.12 74.51 78.93+1.23 88.23+1.03 77.46=131 89.60=0.54
Table 1: Node classification results on 9 real-world benchmark datasets. The results we report the averages associated with standard deviations over 10 trials. We highlight the best results in bold and the runner-up results with underlines.
Notice that although the first term in Problem (19) has a similar form as the first term in Equa- tion (20), they are derived from different perspectives. We here point out several major differences between our IRGNN and GloGNN. First and most importantly, the coefficient matrix in LRGNN explicitly modeled as low-rank matrix. The propagation term in GloGNN is only the vanilla subspace clustering augmented with hidden data, neither sparse nor low-rank is ensured. However, LRR is shown to offer both theoretical and empirical benefits subspace clustering. Moreover, the weak balance theory developed from signed social networks reveals the low-rank structures of the underlying complete graphs. Second, LRGNN aims recovering the missing edge weights via matrix factorization while GloGNN encourages the missing edges to be near zeros by including term (Z AGCN| f.p. On the contrary, the MF term in LRGNN does not impose restrictions on the unobserved entries due to the element-wise function (a((). Third, the adjacency matrix AGEN used in GloGNN is the symmetric normalized adjacency matrix (or its powers) used in vanilla GCN, whose edge weights are uniform and positive. In contrast, we use the pseudo labels to generate a similarity matrix that allows negative weights.
5 EXPERIMENT
In this section, we evaluate the performance of LRGNN. We put the experimental results w.r.t. the convergence rate of the softImpute-ALe ALS algorithm, ablation study, robustness to random noise added to the signed adjacency matrix, and large-scale graph in Appendix A.9 due to space limitation.
Datasets. We use three homophilious datasets including Cora, Citeseer and Pubmed (Yang et al., 2016). We also use 6 heterophilious datasets released in (Pei et al., 2020) and (Rozemberezki al., splits used in this paper are the same as (Pei et al., 2020).
2021). The raining/validation/tess The datasets and splits are all available from the Pytorch Geometric library (Fey & Lenssen, 2019). Details of these datasets are provided in Appendix A.5.
Baselines. We compare LRGNN with 11 baselines, including (1) classic GNN models: vanilla GCN (Kipf & Welling, 2017), GAT (Velickovic et al., 2018) and MixHop (Abu-El-Haija et al., 2019). (2) GNN models dedicated to tackling heterophily: H,GCN (Zhu 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), and GloGNN++ (Li et al., 2022). (3) 2-layer MLP. We choose GloGNN++ and ACM-GCN as they generally perform better than other variants proposed in the corresponding papers.
Node classification results. Table I summarizes the test accuracy of the methods the node classification task over datasets with diverse homophily ratios. We may make several observations from the table. (1) MLP is strong baseline for heterophilous datasets. It significantly outperforms GCN, GAT, and MixHop on Texas, Wisconsin, and Comell datasets. For example, the average classification accuracy of MIP on Texas is 80.81% while that of GCN is 55.14%. (2) We observe
7

---

Under review as a conference paper at ICLR 2023
Comell
Texas
Wisconsin
0.44
0.375
0.22
0.48
0.350
0.325
0.40
041
0.300
0:38
0.40
0.275
32 1213
15-15-1
Operating rank
Operating rank
Operating rank
Figure 3: Recovery enror of matrix factorization three datasets. The lowest point is associated with a vertical line. The shaded region corresponds to a 95% confidence interval.
Texas
Wisconsin
Cornell
Actor
Squirrel
Chamelcon
Cora
Citeseer
Pubmed
HGGCN
5,4/22.4
6.8/22.7
4.5/26.6
52.9/14.7
22.3/7.2
7.0/3.3
5.9/2.7
9.6/4,9
210/201.5
GGCN
6,8/2.5
17.5/7.7
24.4/8.2
200/54.5
1/38/2
30.2/14.3
237/69.6
123/20.8
ACM-GCN
15.9/6.7
20.2/4.2
18.6/6.3
18.7/4.9
21.8/11.5
20.8/9.2
20.8/17.3
21.3/9.5
17.7/14.5
GlaGNN++
10.1/18.8
27.2/62.9
15.1/5.8
37.9/4.8
21.8/5.6
19.1/4.9
32.8/5.1
25.3/11.5
19.5/6.6
LRGNN
11.3/6.0
21,2/7.3
20.2/4.8
17.1/1.5
24.9/5.1
22.2/4.5
17.5/1.9
26.3/2.4
32.2/8.8
Table 2: Empirical running time comparison. Average running time per epoch(in ms)/average total running time(in s). indicates that the algorithm fails to converge within 10 minutes.
two different patterns among the heterophilious datasets. GCN, GAT, MixHop, and LINKX perform worse than MLP on Texas, Wisconsin, and Cornell. However, they outperform MLP on Squirrel and Chameleon datasets. (3) Generally, methods dedicated to heterophilous graphs perform better than MLP and traditional GNNs. GPR-GNN is the exception. (4) H₂GCN (6.22), WRGAT (5.78), GGCN (4.00), ACM-GCN (3.56), GloGNN+ (2.67), and LRGNN (1.56) are the top-performers (the num- ber in parentheses corresponds to the average rank across all datasets). LRGNN performs the best in terms of average rank. This shows that LRGNN can consistently offer superior performance on both homophilious and heterophilious graphs. Notably, LRGNN achieves the best result on Squirrel with around 20.5% improvement over the runner-up score achieved by LINKX. It is worth noting that the superior performance of LRGNN on Squirrel and Chameleon may be attributed to the relatively large average node degrees of these two datasets (38.16 16 and 13.8, respectively), which indicates that we have more observations to recover the underlying complete graph.
Choice of operating rank q. We investigate how the operating rank q affects the performance. Specifically, we are interested in the recovery loss of MF: err = 2n En, |sign((U!!)))))) v(("") )(s))
(ign(AA,),, where L denotes the last layer. From Figure 3 we can observe that q increases, the error gradually decreases at first, then the error gradually rises after the lowest point (associated with vertical line). For these three datasets, the lowest points are 6, 4, and 5, respectively. Note that these datasets all have 5 classes while for Texas, there is one class that only contains one node. This result empirically verifies the low-rank structures of real-world graphs. We can conclude that the best choice of operating rank q should be exactly the number of classes or slightly larger than it. This also explains the effectiveness of low-rank modeling: we can explicitly choose a proper rank for the coefficient matrix according to the number of classes since in most cases, the factors U and V are full rank matrices, so the rank of the coefficient matrix is exactly q. In general LRMF problem, we have no exact information about the rank of the matrix we want to recover. However, we do know the rank when considering node classification tasks, which makes choosing a proper g easier.
Results on synthetic graphs. To comprehensively evaluate the performance of LRGNN, we use random partition graphs (Kim & Oh, 2021) generated by stochastic block model. The node features are sampled from Gaussian distributions where the centers of clusters are vertices of hypercube. Note that the distance between the means of Gaussian distributions is small compared to the stan- dard deviation. As result, node features of different classes are hard to distinguish, which can be verified by the poor performance of MLP on these synthetic graphs. We use 15 synthetic random graphs with varying node-level homophily ratios and average degrees. More details be found in Appendix A.5. We can make the following observations from Figure 4. When homophily ra- tio or degree is low, i.e, average degree 0.5, homophily ratio 0. and homophily ratio 0.3,
8

---

Under review as a conference paper at ICLR 2023
Synthelic Grepha
Weal-Worrdd Graph Toan
0.
Deprer 300
1:20 Levall brrghly Tado
hodeLavll cropply Rato
NoceLarn lianoph Paato
Figure 4: 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.
LRGNN is the only one that can achieve higher accuracy than MLP. Besides, LRGNN outperforms other methods by a large margin when the homophily ratio and average degree are not too high. We note that LRGNN also significantly outperforms all the baselines on Squirrel and Chameleon. These graphs have a common characteristic, i.e, the quality of node features is not good enough for MLPs to achieve an acceptable result. We conjecture that LRGNN performs particularly well on these kinds of graphs, that is, LRGNN can offer superior performance even the node features are not so informative. We next validate our conjecture using real-world dataset. Specifically, we degrade the quality of features of Texas dataset and then test the performance of models trained on this corrupted dataset. We add Gaussian variables to the features and obtain degraded feature X + Cj. with çj i..dd. sampled from a Gaussian distribution [(0 )²). Note that
matrix by X و the original features will be overwhelmed by the Gaussian random variables if large is applied, and thus the features are less informative. We take GloGNN++ H₂GCN, and MLP as representative models for comparison. We can observe from Table that, as the features get less informative, the performance of these three methods deteriorates dramatically. For example, when o = 0.8, their accuracies are around 60%, while the accuracy LRGNN is above 80%. In addition to that, large a also makes their training process erratic, which is accompanied by significant error bars. These results empirically confirm our previous analysis that LRGNN particularly effective in the scenario that node features are not that informative. This may explain the effectiveness of LRGNN, namely deriving the coefficient matrix by leveraging both the node representations and observed signed edges.
Efficiency study, We also evaluate the efficiency of LRGNN compared to other baseline models. We select GGCN, ACM-GCN, H,GCN, and GloGNN+ for comparison as they are the top perform- ers in Table 1. We exclude WRGAT since it takes long time to precompute the multi-relational graphs. For GGCN, Glo-GNN++, and H,GCN, we use the codes and hyper-parameters provided by their authors. Since there is no available code for ACM-GCN, we implement it using Pytorch Library and tune the prree-pprameters based on validation set. We can observe from Table 2 that LRGNN has the shortest rumning time on 6 out of 9 datasets. Especially, LRGNN converges within 10 seconds over all the datasets. As a comparison, GGCN fails to converge within minutes on Pubmed. Besides, LRGNN achieves around 8.5x and 4.8x speedups compared with GloGNN+ on Texas and Citeseer, respectively. In conclusion, LRGNN is efficient and converges very fast. It is worth noting that to achieve the reported results of LRGNN in Table 1, the number of layers and the update iterations for poftlmpute-AL. algorithm are nearly always 1. This explains the superior efficiency of LRGNN and confirms the fast convergence rate of softImpute-ALS algorithm over the neural-style initialization.
6 CONCLUSION
In this paper, we address the challenge of generalizing GNNs to heterophilious graphs with the help of the weak balance theory. Inspired by the low-rank structures of the weakly-balanced graphs, we propose to explicitly model the coefficient matrix as a low-rank matrix. The coefficient matrix is derived by solving difficult non-convex optimization problem whose objective function consists of an LRR and an LRMF term. Extensive experimental results have demonstrated the effectiveness of the proposed LRGNN, especially when the node features are not informative enough.


Reviews:
[{"review_id": "vMSZMlV-hTI", "reviewer": "Reviewer_aB3d", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes a new GNN architecture inspired by a model of homophily and heterophily in social networks. Nodes with similar features are modeled with a positive edge, while nodes with different features are modeled with a negative edge. The paper notices that the weak balance theory for networks naturally applies in the setting of GNNs, since the nodes can be grouped according to which class they belong to. Using existing theory of weakly balanced networks being of low rank, the paper uses a GNN model which explicitly tries to compute a low-rank signed coefficient matrix for node aggregation. This architecture is evaluated for several node classification tasks and compared to existing GNNs.", "summary_of_the_review": "I believe that the contributions of the paper are significant and are able to handle heterophily well, which other GNNs have struggled with.", "strength_and_weaknesses": "Strengths\n-\n\n- The paper draws from well-established theory on low-rank matrix factorizations and signed networks. It is able to adapt an existing ALS algorithm to a new case using a surrogate loss term, which it justifies using a bound. There is a nice discussion of computational complexity and methods to speed up the optimization.\n- LRGNNs significantly outperform other types of GNNs empirically on the heterophilic datasets, especially Squirrel.\n- The experiments are comprehensive and provide good intuition as to why LRGNNs are able to perform well. Adding node-wise independent noise to each of the feature vectors hurts most GNNs, but LRGNNs are robust to this.\n\nWeaknesses\n-\n\n- All of the datasets used seem to rely only on short-range interactions; this is evidenced by each GNN only using one layer for each of the datasets. This brings up the question of how much the graph structure is actually being used. How would LRGNNs compare in the cases where deeper GNNs are necessary?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ZQ-GpT89sy", "reviewer": "Reviewer_Yww3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a low-rank matrix to approximate the coefficient matrix which describes the aggregations of neighborhood information globally. The paper designed a new coefficient matrix with the form of a low rank matrix $UV^t$ which is the solution of the minimization problem inspired by the subspace clustering problem. Furthermore, author proposes a semi-supervised pseudo label generation process as well as matrix initialization step using classic neural approaches on graphs. To solve this matrix, author proposes a novel alternating update algorithms based on softimpute and proves its correctness. The proposed solution achieves results on real-world datasets comparable to other state of the art models and consistently outperforms other methods on synthetic datasets.", "summary_of_the_review": "This paper proposed a novel solution using low-rank matrix to the problem of GNN learning on graph with heterophily. This paper is in general well written and provide a new perspective. However, the experimentation results are not very strong and the scalability of the solution is not verified. Besides, although the author mentions the connection between signed networks and the heterophilous graphs, it is not clear to me whether there is non-trivial connection. Considering this is the core concept and motivation, I am currently giving a reject but I am willing to raise my score if the authors could provide additional explanations.", "strength_and_weaknesses": "Strength:\n1) The paper connects the representation learning on the graph with heterophily and the signed networks. This connection has not been explored by previous literatures and might provide more insights of the learned representations.\n2) The motivations and designs of the algorithms are articulated clearly with both theoretical derivations and numerical simulations.\n3) The authors conduct extensive experiments to verify the effectiveness of the algorithm and provides ablation study and diagnostic plots to verify their modeling assumptions.\n\nWeaknesses:\n1) Although novel, the connection between signed networks and the modeling target is not clear. And thus, the motivation of assuming low-rank approximation needs further elaborations. \n2) The graphs used in the experiments are not large. Does this proposed solution scale to graphs with hundreds of thousands of nodes?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IqTX-bBJCO", "reviewer": "Reviewer_TShN", "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 provides a post-processing to the LINKX with the low-rank constraint on the adjacency matrix. Then, it employs softimpute alternating least square to reduce the complexity. Finally, it bridges the connection between the proposed methods and subspace clustering based on low-rank recovery. Experimental evaluations verify its superiority.\n", "summary_of_the_review": "My main concern is the limited novelty as shown in weakness.\f", "strength_and_weaknesses": "Strength\n- The motivation of low-rank on adjacency matrix makes sense.\n- The experimental evaluations are sufficient.\n- The connection between subspace learning based on LRR and the proposed method is interesting.\n\nWeaknesses\n- The novelty of this paper is limited.  The low-rank constraint on adjacency matrix is not novel, such as [1]. This paper just employs the softimpute alternating least square to speedup the computation. The construction of \\tilde{A} at the beginning of page 5 is not novel yet. This strategy has been proposed in dealing networks with heterophily, such as [2].\n- The organization is redundant.\n\n[1] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, Jiliang Tang: Graph Structure Learning for Robust Graph Neural Networks. KDD 2020: 66-74\n\n[2] Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, Danai Koutra: Graph Neural Networks with Heterophily. AAAI 2021: 11168-11176", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "5jvvaXbILeZ", "reviewer": "Reviewer_4e9z", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 proposes Low-Rank Graph Neural Network (LWGNN), which enhances GNNs by utilizing low-rank approximation to recover the underlying fully-connected matrix Z. In the matrix Z, a positive Z[i,j] means that node j and node i belong to the same class, and a larger value of Z[i,j] means that node j has more influence on node i and vice versa. By using Z as the propagation matrix, LWGNN achieves good performance on node classification tasks of heterophilic graphs. \n\nThe motivation for the low-rank representation comes from the weak balance theory in Signed Social Networks, which leads to a low-rank property of the underlying fully connected signed graph obtained from the classes of each node. Thus, the authors represent Z as the product of two low-rank matrices U and V. For each layer, the authors obtain U, V by (1). reasonable optimization objectives (Equation 7) with closed-form solutions (Equation 9-12), i.e. softImpute-ALS algorithm; (2). carefully designed initialization (Equation 14); and (3). pseudo-labeling (Equation 8) to fulfill the objective function.\n\nThis paper is an extension to GloGNN [1] in that they both require solving the propagation matrix Z in each layer, and using it for propagation. The main differences between LWGNN and GloGNN are: 1) LWGNN makes explicit use of low-rank matrix and low-rank approximation, while GloGNN only implicitly uses low-rank matrices for computing acceleration; 2) LWGNN draws the Z close to the signed adjacency matrix A, while GloGNN does not utilize the signs. \n", "summary_of_the_review": "The work is novel in motivation and good in performance. However, it is largely built on existing work, and it’s not very clear which components its power gains from. ", "strength_and_weaknesses": "Strengths:\n\nS1: The paper has a clear motivation for explicitly exploiting the low-rank property of the signed social graph. \n\nS2: This paper achieves good performance on node classification tasks of heterophilic graphs.\n\nS3: Figure 3 shows that, as the operating rank of U and V increases, the recovery error for signed matrix first decreases, and then increases, which is consistent with the weak balance theory.\n\nS4: LWGNN inherits the satisfactory time complexity from GloGNN. The authors prove that the time complexity of the forward propagation process is linear to the edge number, which is commendable considering that the process of finding the closed-form solution involves the computation of dense matrix multiplication and inversion. \n\nWeaknesses:\n\nW1: The model largely inherits GloGNN in each component, which limits the contribution of this work. \n\nW2: Many practices in this paper are borrowed elsewhere without a clear claim, e.g.,\n- Equation (5), MLP(A) in H^{(0)} is similar to the approach in LINKX;\n- Equation (6), the initial residual connection is similar to APPNP;\n- The first term (propagation term) in Equation (7) is from GloGNN.\nThese are all powerful submodules. The paper should indicate the source of the design ideas. Also, ablation experiments for these modules are encouraged.\n\nW3: Due to the integration of several modules, it is not clear if the utility of signs is crucial for performance gain. The \\tilde{A} in Equation 7 (i.e., the set of edge signs with pseudo labels) should be replaced by the vanilla adjacency matrix A to verify that the supervision of edge sign plays a role. Note that the ablation model is not the same as GloGNN.\n\nW4: Still, due to the integration of several modules, the model has more hyperparameters. For example, \\mu from the use of MLP(A), \\delta from the use of pseudo-labeling, which may lead to a decrease in the usefulness of the model. \n\nW5: The proof in Appendix 1 seems to be incomplete.\n\nW6: Despite S4, the paper is only experimental on smaller (N<20,000). Thus, experiments on the arxiv-ogbn dataset or some LINKX datasets to highlight S3 might be beneficial. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject