Self-supervised Graph Neural Networks via Low-Rank Decomposition
Authors: Liang Yang
Runjie Shi
Qiuliang Zhang
Bingxin Niu
Zhen Wang
Xiaochun Cao
Chuan Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph neural network
Self-supervised learning
Low-Rank recovery

Abstract: Self-supervised learning is introduced to train graph neural networks (GNNs) by employing propagation-based GNNs designed for semi-supervised learning tasks. Unfortunately, this common choice tends to cause two serious issues. Firstly, global parameters cause the model lack the ability to capture the local property. Secondly, it is difficult to handle networks beyond homophily without label information.
This paper tends to break through the common choice of employing propagation-based GNNs, which aggregate representations of nodes belonging to different classes and tend to lose discriminative information. If the propagation in each ego-network is just between the nodes from the same class, the obtained representation matrix should follow the low-rank characteristic. To meet this requirement, this paper proposes the Low-Rank Decomposition-based GNNs (LRD-GNN-Matrix) by employing Low-Rank Decomposition to the attribute matrix. 
Furthermore, to incorporate long-distance information, Low-Rank Tensor Decomposition-based GNN (LRD-GNN-Tensor) is proposed by constructing the node attribute tensor from selected similar ego-networks and performing Low-Rank Tensor Decomposition. The employed tensor nuclear norm facilitates the capture of the long-distance relationship between original and selected similar ego-networks. Extensive experiments demonstrate the superior performance and the robustness  of  LRD-GNNs.

Self-supervised Graph Neural Networks via Low-Rank Decomposition
Liang Yang Runjie Shi ', Qiuliang Zhang Bingxin Niu Zhen Wang 3, Xiaochun Cao Chuan Wang 4x
School of Artificial Intelligence, Hebei University of Technology. Tianjin, China
Schooo of Artificial Intelligence, OPtics and ElectroNies (iOPEN),
School of Cybersecurity, Northwestern Polytechnical University, Xi'an, China
"School of Cyber Science and Technology,
Shenzhen Campus of Sun Yat-sen University, Shenzhen, China
Institute of Information Engineering, CAS, Beijing, China
yangliang@vi qq com, shirumj1e20200163 com, 34631947848qq com
niubingxin6666166 com, w w-zhen@nvpu. edu. cn, mocoiaaccummmalll sysu edu, en, wangchuan@iie ac.
Abstract
Self-supervised learning is introduced to train graph neural networks (GNNs) by employing propagation- GNNs designed for semi-supervised learning tasks. Unfortunately, this common choice tends to cause two serious issues. Firstly, global parameters cause the model lack the ability to capture the local property. Secondly, it is difficult to handle networks beyond homophily without label information. This paper tends to break through the common choice of employing propagation-bant GNNs, which aggregate representations of nodes belonging to different classes and tend to lose discriminative information. the propagation in each ego-network is just between the nodes from the same class, the obtained representation ma- trix should follow the low-rank characteristic. To meet this requirement, this paper proposes the Low-Rank Decomposition- based GNNs (LDD-GNN-Matrix by employing Low-Rank Decomposition to the attribute matrix. Furthermore, to incorporate long-distance information, Low-Rand Tensor Decomposition- -based GNN (LRD-GNN-Tensol is proposed by constructing the node attribute tensor from selected similar ego-networks and performing Low-Rank Tensor Decomposi- tion. The employed tensor nuclear norm facilitates the capture of the long-distance relationship between original and selected similar ego-networks. Extensive experi- ments demonstrate the superior performance and the robustness of LRD-GNNs.
1 Introduction
Graph Neural Networks (GNNs) have been successfully employed by many fields including computer vision (CV), natural language processing (NLP), information retrieval (IR), etc 222 3
Vanilla
GNNs, such as Graph Convolutional Network (GCN) 4 and Graph Attention Network (GAT) [5]. are designed for semi-supervised node classification task, where part of nodes are labeled. To make models adaptive networks beyond hompohily, flexible GNNs with more trainable parameters are proposed, such as JKNet (6). GCNII 77. H2GCN [. FAGCN 99 and GPRGNN 10] label information more critical for these flexible GNNs.
The role of
Inspired by the superior performance in CV and NLP, self-supervised learning, especially contrastive learning, is introduced training GNNs. While large number of methods are proposed, they can
"Corresponinng author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

be divided into two categories, i.e., contrastive and predictive models. The predictive models, such as Graph AutoEncoder (GAB) and its variational version (VAGE), MGAE (T.) GALA [[2] and GROVER, require data-label pairs, where the labels are self-generated from the data and significantly different for different tasks. Without the sensitive generated labels, contrastive models, which only require data-data pairs, attract more attention. The representative graph contrastive learning methods
include DGI (13), GMI [14), MVGRL [5]. GRACE (16), GCA [17] and BGRL [18].
Most existing graph self-supervised learning models employ vanilla GNNs designed for semi- supervised learning with global parameters as encoders. Especially, GCN with one or two layers, where only the feature mappings are trainable. is the most familiar choice. Unfortunately, this common choice tends to cause two serious issues. Firstly, global parameters cause the model lack the ability to capture the local property. For example, the mapping functions in GCN are shared by all nodes. Without the supervision from labels, the reliability of global parameters weaker than that of the local ones. Secondly, it is difficult to handle networks beyond homophily. Most universal GNNs for networks beyond homophily introduce additional trainable parameters distinguish neighbourhoods from different classes with the help of labels, such as GPRGNN and FAGNN. Without the label information, this process becomes complicated and fallible.
This paper tends to break through the common choice of employing propagation-based GNNs in self-supervised graph learning. Propagation- based GNNs seek node representation by averaging the representations of nodes, which may belong to different classes, from neighbourhoods, and thus tends to lose discriminative information. To overcome this issue, an intuitive and ideal way is to make the propagation in each ego-network just between the nodes from the same class. By this way, the obtained representation matrix for ego-network should follow the low-rank characteristic. To meet this requirement, this paper proposes the Low-Rank Decomposition-basee GNNs (LRD-GNN) by employing Low-Rank Decomposition to the attribute matrix. By directly applying Low-Rank Matrix Decomposition to the attribute matrix of the ego-network, Low-Rank Matrix Decomposition-basse GNN (LRD-GNN-Matri)
given.
Furthermore, to incorporate long distanit information, Low-Rank Tensor Decomposition- -based GNN (LRD-GNN- (ENNoTenoo)) is proposed by extending LRD-GNN-Matti to tensor version. LRD- GNN-Tenso constructs the node attribute tensor by selecting similar ego-networks and splicing the attribute matrices of similar ego-networks into 3-way tensor. Motivated by the Tensor RPCA, tensor nuclear norm is defined as the average of the nuclear norm of all the frontal slices of discrete Fourier transformation of tensor along the 3-rd dimension. This tensor nuclear norm is equivalent to the matrix nuclear norm of the block circulant matrix of the tensor, which facilitates the capture of the long-distance relationship between original ego-network and selected similar ego-networks.
The main contributions of this paper are summarized as follows:
We point the necessity of designing specific encoder for self-supervised graph learning.
We theoretically analyze the low-rank property of the representation matrix in ego-network.
We proposed Low-Rank Decomposition- based GNNs (LRD-GNN) and its two instances, LRD-GNN-Matii and LRD-GNN-Tensor.
We experimentally evaluate the superior performance and the robustness of LRD-GNN.
2
Notations and Preliminaries
Notations: In this paper, boldface Euler script letters, e.g., A, are utilized to denote tensors. Matrices denoted by boldface capital letters, e.g., A; vectors are denoted by boldface lowercase letters, e.g., a, and scalars are denoted by lowercase letters, e.g., a. For a 3-way tensor A, its (i. k))th entry is represented Aijk aijk and use A(i,;,:) A(: i,:) and A(:, to denote respectively the i-th horizontal, lateral and frontal slice. The frontal slice A(;;;, i) is denoted compactly as (6)
Let G = =V,E) denote graph with node set = [11 ........ uN and edge set E, where N is the number of nodes. The topology of graph g can be represented by its adjacency matrix A = [ay] E {0, N where dij- = if and only if there exists an edge Eij = (v,, v2) between nodes ;; and ti.. The degree matrix D is diagonal matrix with diagonal element d; = EN dij as the degree of node U,. .V,,)) = {vyl 1y) E E) stands for the neighbourhoods of node G. Let G. (V,, Es) represents the ego-network around node Us where V, N(c:)) U U,, and E, denotes
...

---

Weigntd
Nade Reprovsaaion
Averag
Mara
Rgeaceake
(a) Ego-network
(b) Existing Propagation- based GNNs
(c) Low-Rank Matrix Decomposition-assee GNN
holk
Similar Ego-networks Selection
Festure Matriccs
Extraction
Low Kank Tensor Decompostion
(d) Low-Rank Tensor Decomposition-bssce GNN
Figure I: Framework of the proposed Low-Rank Decomposition-basee GNNs (LRD-GNNs) and comparison with existing GNNs. (a) One ego-network example. Colors of nodes stand for categories, while center node, i.c. node 1, is highlight with purple dashed border. (b) Existing propagation- based GNNs are equivalent to weighted averaging of neighbourhood nodes. (c) Low-Rank Matrix Decomposition- based GNN WED-GNN-Matriie tend to make the embedding matrix of node is the ego-network be low-rank. To this end, low-rank matrix decomposition is applied to the feature matrix of nodes in the ego-network. (d) Low-Rank Tensor Decomposition baaed GNN LLRD-GNN -ENsorenso.. LRRD-GNN-Tensse firstly selects ego- networks, which are similar to the ego-network example. Then, the low-rank tensor decomposition is applied to the tensor, which consists of the feature matrices from above selected ego-networks.
The propagations between nodes in the same class
edges between nodes in V₁ E NxP and H E IR NF denote the collections of node attributes and representations with the jth rows, i.e., E R² and h, E R .coresponndng to node U, where F and J stand for the dimensions of attribute and representation. For convenience, X; E IR (d)++))xx and H; E IR xd denote collections of attributes and representations of ego-network around v;-
Graph Neural Networks: Most of the Graph Neural Networks (GNNs) follow aggregation- combination strategy [3. where each node representation is iteratively updated by aggregating node representations in the local neighbourhoods and combining the aggregated representations with the node representation itself as
h AGGREGATE" ((h M (()))) h = COMBINATE" (h. h
(1)
where h stands for the aggregated representation from local neighbourhoods. Besides of the concatenation based implementation, such as GraphSAGE [19 and H2GCN [8] averaging (or
summation) has been widely adopted to implement COMBINATE'S such as GCN 4. GAT (5),
GIN 20), etc. Except for the MAX and I.STM implementations in GraphSAGE 19] most of the GNNs utilize averaging function implement AGGREGATE" Therefore, they can be unified as
he ===
Σ
dk Lh W
(EA(()
where W represents the learnable parameters and (-) denotes the nonlinear mapping function.
3 Low-Rank Decomposition-based GNN
3.1 Motivations
Existing propagation-based based GNNs tend to lose discriminative information. As shown in Figure [b) and Eq. 2). propagation-based GNNs seek node representation by averaging the representations of nodes from neighbourhoods. Unfortunately, neighbourhoods may belong different classes from the center node. Thus, averaging representations of neighbourhood nodes may mix the representation of center node with representations of nodes from other classes. Especially, this issue is serious on networks with heterophily. The performance degradation of existing GNNs on networks with heterophily demonstrates the loss of discriminative information in propagation.
To alleviate this issue, an intuitive and ideal way is to make the propagation in each ego-network just between the nodes from the same class shown in Figure Tc). This can be formulated
H X.P
(3)
3

---

where X; R((+1))F and H, E R((++))F denote the collections of node attributes and repre- sentations of ego-network around node us, i.c. G. P; ((..-))xdd.+1))) is the propagation matrix. If the propagation is only between the nodes from the same classes, P, should be block diagonal matrix, whose rank is the same as the number of class in this ego-network, However, it is difficult to known the propagation matrix P, since the classes of nodes are unknown in self-supervised learning task. Fortunately, it can be obtain that the rank of H; is no more than the number of class in this ego-network, since the rank of P, the same as the number of class in this ego-network. Therefore, the matrix H; should be low-rank.
3.2 Low-Rank Matrix Decomposition--asee GNN
Based on the analysis in pervious subsection, this section proposes the Low-Rank Matrix Decomposition-basee GNN (LRD-GNNN-atrix) Motivated by the Robust PCA (RPCA) [21] LRD--GNN-Marix decomposes the attribute matrix X; into low-rank H; and sparse S;, i.e.,
argmin rank + A||S/|lo H.S.
s.t. X, H S.
(4)
where ran is the rank of the matrix H. ||||o is the number of non-zero elements in S, i.e., fo norm, and À is a parameter for tradeoff between the two terms. Since the rank function and Eo norm nonconvex, alternatively minimize its convex surrogate as
argmin H.S.
|| |H||- + X||S|| s.l. X; SS
(5)
where || |- is the trace norm of H, i.e., the of the singular values of H. ||S||| I is the & norm, iee the sum of the absolute value of all elements in S. By applying the Augmented Lagrangian
Methods (ALM) 22], the constrained optimization problem in Eqs. (5) can be converted to
F(H,, S. Y,, H.ll- + X|SS < Y.,
H S.
>
X - H. -
(6)
2
where Y, is the Lagrange multipliers for the constraint X; H S. < Y.X >= ta((tr(())) stands for the inner- mrnerrtrouuct of matrix and X. This objective function can be optimized via Alternating Direction Methods of Multipliers (ADMM) (3). ADMM alternatively updates H, S, and Y; by fixing others. The algorithm details are shown in Appendix. After the low-rank matrix H; is obtained, the row in H corresponding to the node v; is extracted as h as the final representation of node U,.
The proposed L.RD-GNN-Matre possesses two attractive characteristics: (1) Parameter-free: The above low-rank matrix decomposition is parameter-free free. Thus, this procedure does not need the supervision label, and can be performed under self-supervised learning. (2) Parallelization: The proposed Low-rank GNNs only need the information of ego-network to obtain representation, and thus are easy to be parallelized. Thus, it is potential to be applied on large graphs.
3.3 Low-Rank Tensor Decomposition-basee GNN
The proposed LRD-GNN-Matin can partly alleviate the issue of discriminative information loss in propagation-based GNNs by low-rank representation pursuit. Unfortunately, it is also difficult to obtain robust and accurate node representations only using information in the ego-netword since the small number of nodes, which belong to the same class center node, in the ego-network. Taking Figure [c) as an example, there are only 3 nodes in the ego-network, which belong to the same class center node. This issue may be serious on networks with heterophily.
Many recent studies demonstrate that nodes with long distances from the center node can also provide additional information for center node representation. These distant nodes possess very different attributes from the center node, even they belong to the same class. Therefore, propagations with these distant nodes may benefit the robust representation of center node. To this end, this subsection by proposing Low-Rank Tensor Decomposition-Dass
enhances the LRD-GNN-Matre GNN-Tensor) shown in T d). LRD- Tensor constructs the node attribute tensor by selecting similar ego-networks and splicing the attribute matrices of similar ego-networks into 3-way tensor. Analogous to the matrix case in Section 3.2 X, E ([dd++1)xFxMMM and H. E [(d++1)x FX(M)
GNN (LRD-
denote the constructed node attribute tensor and representations tensor for ego-network around node

---

2, where M is the number of selected similar net-neeworks. To obtain robust node representation with the help of selected similar ego-networks, low-rank tensor decomposition is performed on A;
argmin H...
Hilll S||S
s.t.
= = + S:
H4
The & norm 11, which is the of the absolute value of all elements, be directly extend from matrix to tensor.
Unfortunately, it is difficult to directly extend nuclear norm from matrix tensor. Motivated by the Tensor RPCA (TRPCA) [24 25]. the tenor nuclear norm of a tensor A Rn X denoted as || is defined as the average of the nuclear norm of all the frontal slices of discrete Fourier
transformation of A along the 3-rd dimension Ā fit [ 3), |.c.||||)
ny Σ ||)
where A (+) denotes the frontal slice A(:,:,)) There exist an important property that the block circulant matrix can be mapped to block diagonal matrix in the Fourier domain, i.e.,
(F & I, (c)) (F-1
Ing) A
(8)
where F ng denotes discrete Fourier Transform matrix stands for Kronecker product, and
(
A (1)
(ma)
(2)
(2)
A (2)
A
A (3)
Á (A)
boire(A)
(ma)
A (ma)
A (ma-1)
A
According to this key property, the tensor nuclear norm is essentially equivalent to the matrix nuclear norm of the block circulant matrix, i.e..
1 ng
22 Σ
1 - - f1
1 II(F bblrr(()))( (F @ In2)ll+ -|bbiicc()]lll Tig
1
|||||
|
n2
If the selected M similar ego-networks are the ego-networks around nodes Viy Waar X; is constructed by splicing X; and X.,..... ......... Xiars and H. constructed by splicing H, and H ...... Hime then the tensor nuclear norm of H. is
H,
H
H
H.
H
71/11
bci re bccir ro.i)ll M +1
M +
[
H
H
H.
which can capture the long-distance relationship between original ego-networ G; and selected similar ego-networks ..,.... Pi.. Therefore, compared ARD-GNNN-attn LRD-GNN DAD-GNN-Tensoe Tensor can exploit ling-distance information, and thus obtain robust and accurate node representation. The detailed algorithm to optimize Eq. (7 is given in Appendix.
Experiments
Datasets. Our experiments are conducted on 12 commonly used benchmark datasets, including 6 homophilic graph datasets (i.e., Cora, CiteSeer, PubMed, Wiki-CS, Amazon Computers and Amazon Photo 26 27 28 and 6 heterophilic graph datasets (i.e., Chameleon, Squirrel, Actor, Cornell, Texas,
and Wisconsin (29]) The statistics datasets are summarized in Table !
Cora, CiteSeer and PubMed (26) are three citation network datasets, where nodes indicate a paper and each edge indicates a citation relationship between two papers. The labels are the research topic of papers. Wiki-CS [27] is reference network constructed based on Wikipedia. The nodes correspond articles about computer science and edges are hyperlinks between the articles. Nodes are labeled with ten classes each representing branch of the field. Amazon Computers and Amazon Photo 28 are two co-purchase networks from Amazon.
these networks, each node indicates good, and each edge indicates that two goods are frequently bought together. The labels are the category goods. Cornell, Texas and Wisconsin [29] are three web page networks from computer science departments of diverse universities, where nodes are web pages and edges are hyperlinks
5

---

Table 1: Statistics of datasets
Dataset
Cora
CiteSeer
PubMed
Wiki CS
Compulers
Photo
Chameleon
Squirel
Actor
Comell
Texas
Wisconsin
# Nodes
2.708
3.327
19,717
11,701
13,752
7,650
2.277
5,201
7,600
183
183
251
# Edges
5,429
4.732
44,338
216.123
245,861
119,081
36.101
217.073
33,544
295
# Features
1,433
3,703
500
300
767
745
2,325
2,089
932
1,703
1,703
1,703
# Classes
7
3
10
5
5
Table 2: Results in terms of classification accuracies (in percent # standard deviation) on homophilic benchmarks. The best and runner-up results are highlighted with bold and underline, respectively.
Methods
Cora
CitcSeer
PubMed
Wiki-CS
Computers
Photo
GCN
81,50+1..3
70.30+0.28
78.80+2.90
76.89=0.37
86.34+0.48
92.35=0.25
GAT
82.80=1.30
71.50=0,49
78.50=0.27
77.42=0.19
87.06+0.35
92.64=0.42
MLP
56,11
56.91+0,42
71.35+0.05
72.02+0.21
73,88+0.
78.54=0.05
JKNet
81,10=0.00
69. 69.80=0.36
10.1020.24
79.52+0.21
85.28+0.72
92.68+0.13
H2GCN
80.23+0.20
69.97=0.66
78.79=0.30
79.73+0.13
84.32=0.52
91.8620.27
FAGCN
77.80=0.66
69.81=0.80
76.74=0.66
74.34=0.53
83.51#1.04
92.72=0.22
GPR-GNN
80,55#1.05
68,57=1.22
77.02+2.59
79.82=0.35
1.22
92.93=0.26
DeepWalk
69.47+0.55
58.82=0.61
1.287
74.35+0.06
85.68+0.06
89.44=0.11
node2vec
71.24+0.80
47.6420.77
66.47=1.00
71.79=0.05
84.39+0.08
89.67=0.12
GAE
71.07=0.39
65.22+0.43
71.7310.92
70.15=0.01
85.27+0.19
91. 91.6240.113
VGAE
79.81=0.87
66.75=0.37
77.16#0.31
76.63=0.19
86.37=0.21
92. 92.20=0.11
DGI
82.29+0.56
71.4940.14 14
87.43+0.84
75.73+0.13
84.09+0.39
91. 91.49+0.25
GMI
82.51=1.47
71.562..56
79.83+0.90
75.06=0.13
90.72=0.33 81.76++0.52
MVGRL
83.03+0.27
72.75+0.46
79.63=0.38
77.97=0.18
87.09
92.01=0.13
GRACE
80.08+0.53
71.41=0.38
80.15+0034
16.062
87.21
92.65=0.32
GCA
80.39=0.42
71.21=0.24
80.37+0.75
79.35=0.12
87. 04
92.78=0.17
BGRL
81.08#0.17
71.59=0.42
79.97=0.36
78.74=0.22
88, 88.92+0.33
93.24=0.29
LRD-GNN-Matri,
82.10=0.24
71.91=0.56
78.50+1.20
80.19=0.18
87. 87.15#0.19
92.31=0.17
LRD-GNN-Temme
83.7420.61
72.05+0.69
79.71
81.43+0.13
89.60.0.18
93.26:2015
between two web pages. The labels are types of web pages. Chameleon and Squirrel 29 are two Wikipedia networks where nodes denote web pages in Wikipedia and edges denote links between two pages. The labels stand for the average traffic of the web page.
For Cora, CiteSeer, and PubMed datasets, we adopt the public splits with 20 labeled nodes per class for training, 500 nodes for validation and 1000 nodes for testing. For Wiki-CS, Computers and Photo datasets, we randomly split all nodes into three parts, i.e., 10% nodes for training. 10% nodes for validation and the remaining 80% nodes for testing. The performance on heterophilic datasets is evaluated on the commonly used 48 48%/32%/20% training/vaiidationnesstgg
Baselines. To verify the superiority of the proposed LRD-GNN, We compare it with four groups of baseline methods: (1) The multiple layer perception (MLP) and classic GNN models for node classification task including vanilla GCN and GAT 5 (2) GNN models designed for alleviating over-smoothing issue networks with heterophily including JKNet (6) GPR-GNN [10, FAGCN 9 and H2GCN 88: (3) Conventional self-supervised graph representation learning methods including
DeepWalk (30 node2vec (31) GAE and VGAE II; (4) Contrastive self-supervised baselines
including DGI 13 GMI 14, MVGRL 15) GRACE 16, GCA [17]
and BGRL [8.
Experimental details. All methods were implemented in Pytorch with Adam Optimizer. We run 10 times of experiments and report the averaged test accuracy with standard deviation. All the parameters of baselines are tuned to get preferable performance in most situations or the same as authors' original implementations. The in (0.2, 0.3, 0.4). Besides, early stopping with a patience of 200 epochs and L. regularization with coefficient in ( (IE-2, 5E-3, 1E-3) are employed to prevent overfitting.
search space is: learning rate 10.1, 0.05, 0.01). dropout
4.1 Experimental Results
4.1.1 Evaluation on node classitication task
Performance Comparison. The mean classification accuracy with the standard deviation on homophilic datasets and 6 heterophilic datasets presented in Table 2 Table 3 respectively. We

---

Table 3: Results in terms of classification accuracies (in percent + standard deviation) on heterophilic benchmarks. The best and runner-up results are highlighted with bold and underline, respectively.
Methods
Chameleon
Squirel
Actor
Cornell
Texas
Wisconsin
GCN
59.6342.32
36.28
30.83+0,77
57.0343..8 30
60.00+4,80
56.47+6.55
GAT
56.38+2.19
32.09+3.27
28.06#1.46
59.46+3.63
61. 61.62+3.78
64.71+6.87
MLP
46.91+2.15
29.28=1.33
35.66#0.94
81.08+7.95
81.6245.55
84.31+3.40
JKNe
58.3142.76
42.2442.11
36.47+0.51
56.4943.22
65.35:4.66
$1.37+3.21
H2GCN
59.39=1.98
37.90+2.02
35.86+
82.16+44.8
84.8626.77
86,67+4.66 69
FAGCN
63.44+2.05
41.17 .94
36.81+0.26
81.35+5.05
84.32=6.02
83,33+2.01
GPR-GNN
61.58+2.24
46.65=1.81
35.27=1.04
81.8945.93
83,24=4.95
84.12+3.45
DeepWalk
47.7442.05
32.93+1.58
22.78+0.64
39. 18:5.77
46,4926,49
33.53+4.92
node2vec
41.93+3.29
22.84=0.72
28.28
42.94+7.46 46
41.92+7.76
37.45+7.09
GAE
33.8422.77
28.03=1.61
28.03+1.18
58. 38.8213.21
58, 38.6424.53
52.55+3.80
VGAE
35.2242.71
19.48
26.99+ 1.56
59.1944.09
59.20s4.26
56.67+5.51
DGI
39.95+1.75
31.80=0.77
22,0000
63.35:4.6 61
60.59=7.56
55.4145.96
GMT
46.97+3.43
30.1
27.82+0.90
54.76+5.06
50.49+2.21
45.98+2.76
MVGRL
51,07+2.68
35.47=1.29
30.02=0.70
64.30+5.43
62.38+5.61
62.37+4.32
GRACE
48.05#1.81
31.33+1.22
29.01+0.78
$4.86.6695
57.57=5.68
50.00+5.83
GRACE-FA
52.68+2.14
35.97+1.20
32.55+ 1,28
67.57+4.98
64.05=7.46
63.73+6.81
GCA
49.80+1811
35.50=0.91
29.65+1.47
55.41+4.56
59, 59.4626.16
50,7824.06
BGRL
47.46+2.74
32.6420.78
29.86+0.75
57.30+5.51
59.19=5.8 .85
52.35+4.12
LRD-GNN-AN Mattixx
60.71+2.21
47 1.161
37.22+0.83
08.46
86.1222.86
83,13#1.90
L.RD-GNN-Tenee
66,27&1.27
55.91#0.91
37.07+0.83
84.73+2.83
87.03+3.97
86.86133.04
Cora
CiteSecr
PubMed
80
65
Jecuracy (%)
Accuracy(Po
75
75
Restrran
LRD-ENN
LRD-GIN
LRD-GNN
GAT
70
GCN
GCN
70
GCN
GRACE
10
40
50
20
30
40
50
10
20
30
40
50
Perturbation Rate(*))
Perturbation Rate(%)
Perturbation Rate(%)
Figure 2: Node classification performance graphs with randomly adding noisy edges.
compare the proposed LRD-GNN- GNN-Matrix and its tensor version LRD-GNN- Gen-Tersor with baselines. First of all, we observe that LRD--NNY MoN-Teesorr outperforms all baseline methods in 10 out of 12 benchmarks and achieves competitive results the rest 2 benchmarks.
The superior performance indicates the tensor low-rank decomposition can universally benefit representation learning, since low-rank structure widely exists in diverse real- woal-wrrdd graph data. And the construction of tensors effectively captures the connections among similar nodes. Note that LRD-GNN outperforms state-of-the-ar deep model JKNet both homophilic and heterophilic datasets. This demonstrates that shallow-layer information is actually quite abundant for extracting node representation for LRD-GNN Additionally, compared with GPR-GNN, FAGNN and H2GCN which are all the GNNs designed for processing datasets with heterophily, we observe that LRD-GNN achieves the low-rank structure remains the heterophilic information from the ego-networks instead of the impairing heterophilic information processing by averaging operation.
state-of-iie of-the--rtttttt results on all heterophilic datasets. This verifies that
In Table we find that LRD-GNN significantly outperforms conventional and contrastive self- supervised methods. The main reason is that these self-supervised methods constantly smooth the representations along heterophilic edges, which destroys the low-rank structure and makes the representations indistinguishable. In contrast, our method overcomes these issues via low-rank tensor decomposition, and learns more expressive representations. Besides, it can be observed that LRD- GNN-Tensor outperforms information from distant nodes with the local is necessary. These results suggest that by adopting the low-rank decomposition in GNNs, our proposed LRD-GNN is more effective and universal than the previous models on processing datasets with both homophily and heterophily for node classification.
in most cases, which indicates that combining global
The following experiments are all based on LRD-GNN-Tensor. which is abbreviated as LRD-GNN.
7

---

Cora
CiteSeer
PubMed
75
60
Accuracy (%)
So (%)
Accuracy (%)
65
50
55
LRD-GNN
LRD-GNN
50
LRD-GGN
30
GAT
GCN
GCN
GEN
45
GRACE
GRACE
GRACE
50
20
30
Perturbation Rate(%)
Perturbation Rate(%))
Perturbation Rate(%))
Figure 3: Node classification performance on graphs with randomly adding noisy attributes.
Table 4: Performance of LRD-GNN under different tensor construction methods
Similar Nodes
Data Variants
Cora
CiteSeer
Chamelcon
Cornell
Texas
A.A. A
83.74:0.61 83.55+0.27
72.05+0.69
65.92
88.95=3.11 11
88.42+1.22
X
71.59s0.91
56.29=0.67
88.15+2.94
87.82+
Attribute
AX AX
83.62+0.54
71.67+0.60
53.46+1.68
87.89=2.11
87.3643.68
AX
82.66640.71
71.30=0.74
47.32+2.66
1.85
72.78+2.37
AX, X
80.32+0.49
70.06+0.65
63.07=1.09
73.05#2.36
73.68
X
81.25=0.42
71.65=0.68
16.2611.29
84.73=1.97
85.78+1.22
Structure
A, AX
80.73+0.41
71.03+0.75
15.68
84.21=1.66
83.68
AX A
78.2020.65
69.2110.64
64.2721.39
83.15+2.68
84.7343.06
Visualization. To provide intuitive interpretation, apply t-SNE to visualize the node embed- dings obtained by GCN, GAT and LRD-GNN on four datasets. As shown in Figure the clusters of embeddings of nodes from different classes marked with various colors. By visually analyzing the clusters and distribution of the node classification results, we can find the characteristics of the corresponding models. The clusters of embeddings of different classes processed by GCN are overlapped, which demonstrates that GCN tends to be under-fitting. The clusters of embeddings obtained by GAT are also irregular and sharp, especially the poor performance on Chameleon which indicates that simply aggregating information does not work on homophilic graphs. While the clusters of embedding obtained by LRD-GNN are more regular and the nodes with the same label exhibit spatial clustering, which shows the power of LRD-GNN.
4.1.2 Robustness Analysis
In this experiment, we investigate the robustness of LRD-GNN on graph data. We perturb graph structure and input node attributes by randomly adding noisy edges and attributes respectively, and test the node classification accuracy on the representations learned from perturbed graphs. We compare the performance of LRD-GNN with GCN, GAT and GRACE on Cora, CiteSeer and Pubmed datasets. The classification results under different perturbation rates are shown in Figure and Figure 3 From Figure we can see that LRD-GNN consistently outperforms the other three methods under different perturbation rates. Specifically, the proposed LRD-GNN obtains node representations without propagation and the graph topology is only used to form the ego-network. However, other methods need to propagate the information based on topology, which indicates that they are more likely to be affected by corrupted topology information. Therefore, LRD-GNN tends be more robust to topology noises than the existing GNNs. Figure 3 reports that LRD-GNN is also superior other baselines under attributes perturbation, which can be attributed to the denoising ability of low-rank decomposition and recovery in LRD-GNN These experimental results demonstrate the strong robustness of LRD-GNN against random attacks on graph topology and node attributes.
4.1.3 Ablation Study
To analyze the effectiveness of different tensor construction methods in LRD-GNN, we conduct experiments on several variants of tensor. We compare the performance of LRD-GNN under different tensor construction methods, and node classification results with several variants are shown in Table 4 We mainly investigate methods of constructing tensors from topology and attribute two perspectives: (I) select nodes with similar attributes; (2) select nodes with similar local structures, and then use

---

Chameleon
CiteSecr
Photo
Computers
GON
GAT
LRD-GNN
Figure 4: The visualization for node representations obtained by GCN, GAT and LRD-GNN
Com
CiteSeer
Wiki-CS
Ascurucy
Accunicy
70
LRD-ONN
LRD-TNN
63
LAD-GNN
GCN
GCN
GCN
50-
55
GAT
DGI
DGI
DGI
30
MVGEL
MVGRL
MVGRL
5
9
10
10
8
10
Number of Layers
Number of Layers
Number of Layers
Figure 5: Node classification results with various model depths on Cora, Citeseer and Wiki-CS.
these nodes' ego-network matrix in different orders (i.e., X, AX, X2X) construct tensors, where each ego-network matrix forms slice of the target tensor.
From Table we can find that under the same configuration, node embeddings obtained from tensors constructed by nodes with similar attributes are more expressive than tensors constructed by nodes with similar local structures, both on the homophilic graphs (Cora and CiteSeer) and heterophilic graphs (Chameleon, Cornell and Texas). When higher-order information (i.e., X²X) is utilized, the performance heterophilic datasets is significantly improved. However, the variant of tensor which contains AX is not competitive enough compared to other variants on heterophilic graphs, which indicates that higher-order information is important for representation learning heterophilic graphs. In addition, we can observe that tensors that preserve the original node attributes outperform tensors formed only by node representations obtained by propagation, which indicates that original node attributes play a prominent role.
4.1.4 Over-smoothing Problem Analysis
To validate whether LRD-GNN can alleviate the over-smoothing problem, we compare the perfor- mance of LRD-GNN with several representative self-supervised and semi-supervised GNNs under different model depth. We regard the process of obtaining node representations via TensorRPCA as a layer of LRD-GNN framework. The node classification results on Cora, CiteSeer and Wiki-CS are shown in Figure 5 It can be seen that GCN achieves competitive performance at two layers. As the number of layers increases, the performance of GCN drops rapidly, which indicates that GCN suffers from over-smoothing seriously. GAT alleviates the over-smoothing issue by introducing irrelevant malti-channel propagations. Unfortunately, also becomes DGI and MVGRL, which adopt GCN layer as encoder, also tend to be over- over- seoeshitt as depth increases. Instead, results of LRD-GNN are stable and higher than other methods on different types of networks. The reasons are two-folds: one is that the proposed LRD-GNN obtains node representations without propagation and the graph topology only used to form the ego-network, which can prevent node representations from being too similar. Another is that the low-rank decom-
smoohhing after few layers.

---

position in LRD-GNE reduces the impact of noise, which further keeps node representations from becoming indistinguishable. Through these two designs, when the model goes deep. the performance of LRD-GNN is significantly better than the above self- supe-sueee and semi-supervised methods, which indicates that LRD-GNN has a good capability alleviate over-smoothing.
Conclusions
This paper breaks through the common choice of employing propagation-based GNNs, which aggregate representations of nodes belonging to different classes and tend to lose discriminative information. Firstly, this paper theoretically shows that the obtained representation matrix should follow the low-rank characteristic. Then, to meet this requirement, this paper proposes the Low-Rank Decomposition-Daasee GNNs (LRD-GNN) by employing Low-Rank Decomposition to the attribute matrix. Furthermore, to incorporate long-distance information, Low-Rank Tensor Decomposition- based GNN LLRD-GNN-Tensse proposed by constructing the node attribute tensor from selected similar ego-networks and performing Low-Rank Tensor Decomposition. Extensive experiments demonstrate the superior performance and the robustness to noises of the proposed LRD-GNNs.
Acknowledgment
This work supported in part by the National Natural Science Foundation of China (No. U22B2036. 62376088, 61972442, 62102413, U1936210, U1936208, 11931915), in part by the National Science Fund for Distinguished Young Scholarship of China (No. 62025602), in part by the Natural Science Foundation of Hebei Province of China under Grant F2020202040, in part by the Fok Ying- Tong Education Foundation China (No. 171105), and in part by the Tencent Foundation and XPLORER PRIZE.
References
[1] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey graph neural networks. TNNLS, 22(1):4-22 24, 2021.
[2] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AI Open, 1:57-81, 2020.
[3] Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In ICML, pages 1263-1272, 2017. 2017.
[4] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[5] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. ICLR, 2018
[6] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In ICML, pages 5449-5458, 2018.
[7] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, pages 1725-1735 2020.
[8] 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.
[9] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks, pages 3950-3957, 2021.
[10] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR, 2021.
10

---

[11] Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/161 2016.
[12] Jiwoong Park, Minsik Lee, Hyung Jin Chang, Kyuewang Lee, and Jin Young Choi. Symmetric graph convolutional autoencoder for unsupervised graph representation learning. In ICCV, pages 6518-6527. IEEE, 2019.
[13] Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR. OpenReview.net, 2019.
[14] Zhen Peng. Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong. Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In wwW, pages 259-270. ACM / IW3C2, 2020.
[15] Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In ICML, volume 119, pages 41 1 16-416.. PMLR, 2020.
[16] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. CoRR, abs/2006. 02000600133 131,,, 2020.
[17] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In WWW. ACM, Apr 2021.
[18] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Velick- ovic, and Michal Valko. Bootstrapped representation learning on graphs. CoRR, abs/2102.06514, 2021.
[19] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NIPS, pages 1024-1034, 2017.
[20] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[21] Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? J. ACM, 58(3):11:1-11:33 2011.
[22] Stephen P. Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 3(1):1-122 2011.
[23] Stephen P. Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2014.
[24] Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan. Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization. In CVPR, pages 5249-5257, 2016
[25] Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan. Tensor robust principal component analysis with new tensor nuclear norm. IEEE Trans. Pattern Anal. Mach. Intell., 42(4):925-938, 2020.
[26] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. AI magazine, 29(3):93- 93, 2008
[27] P Mernyei and C Wiki-CS Cangea. A wikipedia- benchmark for graph neural networks. arxiv 2020. arXiv preprint arXiv:2007.022 029011, 2007.
[28] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation, 2019.
[29] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
[30] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social repre- sentations. In SIGKDD, pages 701-710, 2014.
[31] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In SIGKDD, pages 855-864, 2016.

---

A Algorithm Description of ADMM
We Alternating Direction Methods of Multipliers (ADMM) solve convex optimization problem in RPCA and TensorRPCA, and the details are shown in Algorithml and Algorithm2 which are named Matrix ADMM and Tensor ADMM, respectively.
Algorithm I: Matrix ADMM
Input: matrix data X, parameter X. Initialization: Ho So = Yo p= 1.1, 140 le 3, le 8.
while not converged do
Singular Value Thresholding %;
1. Update H&+1 by Ha+1 = arg min |||, + 2 1 + Sk X + #i 11::
H
% Noft-Thresholdin %;
Update Sk+1 by Sk+1 arg min A||S||a + ML HK+1 + + X
Yx Fx
P.:
5
Yx+1 = Hy + [u((H++ - Sk+1 - X)
4. Update #k+1 by 14++1 = pPv :
Check the convergence conditions
|H++1 - Hx S 6, || Sklloo S ||x++1 - Sk+1 X1100 S
end
Algorithm 2: Tensor ADMM
Input: tensor data X. parameter Initialization: Hg Sn 3b = 0, p0 1.1, le 2, le -- 5.
while not converged do
Singular Value Thresholding %;
1. Update H4+1 by Ha+1 = arg min |||||= + Uh 1 S₁ - X + 12:
H
% Soft- Soft-Thresholding %;
Update Sk+1 by Sk+1 arg min A||S||2 + 1y 2
|7++1 + X' Vi 2
Ve+1 = H4 + pa [M+++++11 Sx+1 X):
4. Update #4+11 by pu++1 = min(p Mmax))
Check the convergence conditions
[iHe+1 - Hellon S S1 Skllo0 S 117641 - Sk+1 X1 S
end
B Select Similar Ego-networks
In section 3.3, we enhance LRD-GNNN-atrix to tensor version LRD-GNN-Tensor.. The ego-networks around nodes which similar with target node selected construct tensor. We evaluate similarity from two perspectives.
(1) We select nodes which have similar attributes with target node. For instance, the Cosine Similarity is used measure the similarity of attributes between nodes. (2) We select nodes which have similar local structures with target node. We use the Shannon entropy value of eet-network to measure local structure similarity. For the ego-network G. = (V,, around U; the Shannon entropy value H (G,) is defined as
H(G,)
= Σ P(v) log P(u) "EV;
(10)
where P(v) is the probability of the random walking visiting in ego-network. Then, we choose several nodes" ego-networks that are close to the Shannon entropy value of the central node to construct tensor.
12

---

Besides, to combine information from different orders, we also utilize the selected nodes' ego- networks after propagation(i.e. AX, X) as part of the tensor. The specific methods for constructing tenosr and the performance have been presented in section 4.1.3 Ablation Study.
13


Reviews:
[{"review_id": "KyvcgW8QWE", "reviewer": "Reviewer_Efzd", "summary": "This paper studies the self-supervised graph learning for node classification tasks.\nThe authors make an observation that traditional propagation based GNNs loose discriminative information\nvia node property averaging. To address this issue, the authors propose a novel LRD-GNN method that\nencourages low rank property of the representation matrix. The extended version, LRD-GNN-Tensor, allows\nnode feature propagation between long distance nodes and improve the method's ability to capture long\ndistance relationships. Empirical results show the proposed method outperforms baseline methods and improves\nthe model robustness towards noisy edges.", "questions": "* Justification for selecting exactly M similar ego-networks for every node?\n\n* How are the similar ego-networks selected in practice?\n\n* Computation complexity and overall method scalability w.r.t. graph size?", "limitations": "The limitation of this work is not discussed in the paper. \n\nI don't see any potential negative societal impact of this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors make an interesting observation that in order to propagate only among same class nodes, the\nproperty matrix needs to be low rank. However, instead of enforcing a low rank decomposition of the\nnode property matrix, the method adopts the Robust PCA relaxation of the rank function/L0 norm and therefore\ndoes not need heuristic hyper-parameters or label supervision.\n\n* Empirical results show the proposed method has better performance than various baseline methods in both homophilic\nand heterophilic settings. Ablation study also shows the proposed method can alleviate the over-smoothing issue.\n\n", "weaknesses": "* LRD-GNN-Tensor considers long distance correlations in the graph by grouping similar ego-networks together. However, it is not clear from the paper how are these similar ego-networks selected.\n\n* It is claimed in the paper that the proposed method is scalable yet only small datasets are used in empirical studies.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1. Justification for selecting exactly M similar ego-networks for every node?***\n\nR1. Thanks for your insightful question. Selecting exactly M similar ego-network is the compromise of the model’s expressive power and generalization ability. It is natural that different nodes should select different numbers of similar ego-networks, since different nodes possess different topology structures. Unfortunately, it requires additional components and parameters to determine it for every node. Although different M for different nodes can improve the model’s expressive power, it may induce an overfitting issue and reduce the generalization ability, especially in self-supervised learning tasks. Besides, we don’t find a practical relationship between the number of similar ego-networks and the node’s topology structure. This provides difficulty in modeling the number of similar ego-networks. From these perspectives, the strategy of exactly M similar ego-networks for every node is employed in our model. \n\n---\n\n***Q2. How are the similar ego-networks selected in practice?***\n\nR2. In practice, the cosine similarity of the center nodes’ attributes is utilized to select the similar ego-network. In the supplemental material, two similar ego-networks selection strategies, i.e., attribute-based strategy and topology-based one, are provided. The attribute-based strategy employs the cosine similarity of center nodes’ attributes as measurement, while the topology-based strategy uses the Shannon entropy value as measurement. The ablation study on the strategies is given in Section 4.1.3 and Table 4. It shows that the attribute-based strategy consistently outperforms the topology-based one. Therefore,  the cosine similarity of the center nodes’ attributes can be employed in practice. \n\n---\n\n***Q3. Computation complexity and overall method scalability w.r.t. graph size?***\n\nR3. The overall complexity is linear with the graph size, thus the model is scalable. The main component of the proposed LDR-GNN is the low-rank matrix/tensor decompositions, which are implemented via RPCA and tensor RPCA. The complexity of RPCA on a matrix of $n_1 \\times n_2$, where $n_1 > n_2$, is $O(n_1 n_2^2)$, while that of tensor RPCA on a tensor of of $n_1 \\times n_2 \\times n_3$, where $n_1 > n_2$ and $n_3$ is the third dimension is $O(n_1 n_2^2 n_3 + n_1 n_2 n_3 log(n_3) )$. In the case of LDR-GNN, $n_3 = M$ is the number of selected similar ego-networks. Since the dimension of node attribute $F$ is often larger than the size of ego-network $d_i$, we set $n_1 = F$ and $n_2 = \\bar{d}$, where $\\bar{d}$ is the average node degree. Therefore, the complexities of LRD-GNN-Matrix and LRD-GNN-Tensor for each node are $O(F \\bar{d}^2)$ and $O(F  \\bar{d}^2  M + F  \\bar{d}  M log(M) )$, respectively.  Since every node separately performs LRD-GNN-Matrix or LRD-GNN-Tensor, the overall complexities are $O(N F \\bar{d}^2)$ and $O(N F  \\bar{d}^2  M + N F  \\bar{d}  M log(M) )$, where $N$ is the number of node in the graph, respectively. Therefore, the overall complexity is linear with the graph size, and the model is scalable."}, {"review_id": "tAQPngH2kK", "reviewer": "Reviewer_7YeZ", "summary": "This paper proposes to alleviate the issues in propagation-based self-supervised GNN using the low-rank matrix/tensor decompositions. Firstly, it points out existing self-supervised GNNs can not capture local information and handle networks with heterophily due to the global learnable parameters and the lack of supervision information.  Secondly, it investigates the low-rank property of the local representation matrix. Thirdly, to meet these requirements, it presents low-rank matrix/tensor decomposition, which possesses attractive characteristics. Experiments on real networks verify the superior performance and robustness to noises.", "questions": "- What are the differences between unsupervised learning and self-supervised learning.  Although I like the idea of seeking representation using low-rank decomposition, I think it is an unsupervised learning. It may be different from self-supervised one. Could you explain their differences.\n\n- The procedure of tensor construction is not clear. How the similar ego-networks are selected. Besides, it is not clear why the similar ego-networks are concatenated into a tensor instead of a larger matrix.\n\n- It is not clear why the proposed methods are robust to topology and attribute noises. Although the experiments verify this characteristic, the formal explanation should be given.\n\n- What do the white boxes mean in Fig 1(d)?\n\n===\n\nI have read the rebuttal and would like to keep my rating.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The motivation makes sense. It is interesting and meaningful to reveal the issues in existing self-supervised GNNs. Due the shared global parameter and lack of label information, propagation-based encoders tend to have some drawbacks. It seems the first attempt to seek specific encoder for self-supervised GNNs.\n\n- The technology is solid and novel. The observation that local representation matrix should be low-rank is insightful and interesting. The employed low-rank matrix/tensor decomposition are novel to the field of graph neural network. Especially, the tensor decomposition seems technically solid. Besides, the proposed methods have some attractive properties.\n\n- The evaluations are sufficient. Both the employed datasets and the baselines are representative and adequate. The performance improvements are acceptable. The visualization and ablation study are convincing.", "weaknesses": "- Some descriptions are not clear. For example, it is confusing to put the overflows of both matrix decomposition and tensor one in the same figure. Besides, Figure is too small and compact. See questions bellow.\n\n-\tIt is difficult to understand why the proposed methods is better than propagation-based ones for reviewers who are not familiar with low-rank decomposition. It is not as intuitive as in computer vision. Therefore, some preliminaries should be given.\n\n-\tA section on related work should be given to make the readers to judge the contributions of this paper.\n\n-\tThe presentation and writing should be carefully check.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1. What are the differences between unsupervised learning and self-supervised learning. Although I like the idea of seeking representation using low-rank decomposition, I think it is an unsupervised learning. It may be different from self-supervised one. Could you explain their differences.***\n\nR1. In my opinion, self-supervised learning belongs to unsupervised learning. Unsupervised learning is a broad class of tasks where the supervision information, such as node labels in the graph, is unavailable. It includes many tasks, such as clustering, dimension reduction, Probabilistic Density Estimation, etc. Self-supervised learning often employs to denote the unsupervised representation task with neural networks. Thus, self-supervised learning is a specific class of unsupervised learning. From this perspective, although low-rank decomposition is an unsupervised learning method, the proposed LRD-GNN is a self-supervised method for graph representation learning. \n\n---\n\n***Q2. The procedure of tensor construction is not clear. How the similar ego-networks are selected. Besides, it is not clear why the similar ego-networks are concatenated into a tensor instead of a larger matrix.***\n\nR2. Due to the limited space, the details on similar ego-networks selection are elaborated in the supplement material as follows. We construct the attribute tensor by selecting similar ego-networks and splicing the attribute matrices of similar ego-networks into a 3-way tensor. We evaluate similarity from two perspectives. (1) We select nodes that have similar attributes to the target node.  For instance, Cosine Similarity is used to measure the similarity of attributes between nodes. Then, the ego-networks from these nodes are selected to construct a tensor. (2) We select nodes that have similar local structures to the target node. The Shannon entropy value of ego-network is used to measure local structure similarity. For the ego-network $G_i = (V_i,E_i) $   around $v_i$ , the Shannon entropy value $H(G_i)$ is defined as $ H( G_i ) = -\\sum_{v \\in {V}_i} P(v)\\log P(v) $, where $P(v)$ is the probability of the random walking visiting $v$ in ego-network.  Then, we choose several nodes' ego-networks that are close to the Shannon entropy value of the central node to construct a tensor.\n\nThe reason for employing a tensor instead of a large matrix is because that tensor can preserve more structure information compared to the matrix. According to the construction of the tensor, nodes belonging to the same ego-network are on the same slice of the tensor, while nodes in different ego-networks are on different slices. On the contrary, the large matrix can not distinguish whether nodes are from the same ego-network, since all nodes are concatenated in the same dimension.  Therefore, the tensor is superior to the matrix.\n\n***Q3. It is not clear why the proposed methods are robust to topology and attribute noises. Although the experiments verify this characteristic, the formal explanation should be given.***\n\nR3. The robustness to topology and attribute noises can be ascribed to the employed low-rank decomposition. On one hand, low-rank decomposition avoids the propagation over the topology, which is sensitive to the topology noises. Existing propagation-based GNNs perform the message passing according to the links in the topology. Therefore, the noisy links inevitably introduce noises in representation. On the contrary, the representation learning in LRD-GNN does not strictly rely the topology. The topology is only utilized to construct the local information matrix in the LRD-GNN, while the low-rank decomposition does not use topology. Therefore, even though the noisy topology introduces noises in the local information matrix, the following low-rank decomposition possesses the ability to denoise.  On another hand, the attribute noises can be removed via low-rank decomposition. The low-rank decomposition, which decomposes the attribute matrix into a low-rank matrix and a noisy one, has significant robustness to noises. Therefore, the low-rank decomposition contributes to the robustness to topology and attribute noises.\n\n---\n\n***Q4. What do the white boxes mean in Fig 1(d)?***\n\nR4. The white boxes stand for elements with zero values. In the Noise part, the discrete white boxes denote the elements without noises compared to the gray boxes, which represent the noises. In other parts, including Feature Matrices Extraction, Node Attribute, and Low-rank Matrix Representation, the row-wise white boxes stand for the padding vectors in the slices with fewer nodes. Specifically, the selected similar ego-networks contain different numbers of nodes, thus the constructed matrices possess different sizes. To concatenate these matrices into a tensor, matrices with fewer rows, i.e., ego-networks with fewer nodes, should be padded with zero rows. We will add this explanation to the caption of the figure in the final version.\n\n---\n\n***Weakness: 1) Figure is too small and compact. 2) Some preliminaries on low-rank should be given. 3) A section on related work should be given. 4) The presentation and writing should be carefully check.***\n\nR5.  Thanks for your suggestion on improving the paper. We will add the preliminaries on the low-rank problem and a related work section, fully polish the paper, and separate Figure 1 into the LRD-GNN-Martix Figure and the LRD-GNN-Tensor one in the appendix for better illustration."}, {"review_id": "UZ7SNjHepD", "reviewer": "Reviewer_EJvt", "summary": "The encoder for self-supervised graph neural networks is investigated.  The authors identify the weaknesses of capturing local property and handling heterophilic networks in existing propagation-based encoder. They observe that the obtained node representations possess low-rank characteristics and tend to meet it using the low-rank matrix factorization. Besides, to extend to incorporate global information, attribute tensor is constructed and low-rank tensor factorization is applied. Experiments shows its effectiveness and robustness to noises, especially on networks with heterophily.", "questions": "Refer to Weaknesses.", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "•\tThe investigated encoder issues are significant to self-supervised graph neural network. Especially, the global parameter and the lack of supervision information are critical for encoder choice. \n\n•\tThe employed low-rank decomposition algorithms are novel to GNNs. The decomposition to local attribute matrix facilitates the local structure capture and the requirements to label.\n\n•\tThe performance enhancement on heterophilic networks is remarkable. Experiments on robustness and preventing oversmoothing are convincing. \n\n•\tThe presentation is clear. The figure of the proposed framework is elaborate to show the process. The figure of visualization demonstrates the discriminability of node representations.\n", "weaknesses": "•\tThe relationship between the proposed method and existing self-supervised GNN is not clear. Existing self-supervised learning relays on encoder for supervised learning and an objective function. However, the proposed method does not need objective function. Therefore, it is important to find their connections. \n\n•\tIt is difficult for readers, who are not familiar with low-rank, to get the key points in motivations and details of the proposed methods. It is better to review the concepts of low-rank and self-supervised in preliminaries section or appendix.\n\n•\tThere are some typos. For example, the is a nuclear norm missing in the formula between lines 162 and 163.\n\n•\tThe performance on preventing over-smoothing issue is compared against semi-supervised GNNs, i.e., GCN and GAT. The self-supervised GNNs should be compared with.\n\n•\tThe proposed LRD-GNN is a non-parameter model, which may benefit the task of self-supervised learning. However, how can it be improved if the labels are available.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***Q1.  The relationship between the proposed method and existing self-supervised GNN is not clear. Existing self-supervised learning relays on encoder for supervised learning and an objective function. However, the proposed method does not need objective function. Therefore, it is important to find their connections.***\n\nR1. Thanks for your advice. Unfortunately, it is difficult to point out their detailed connections, since they are very different from design principal. Existing self-supervised GNNs focus on global characteristics, thus they employ encoders with global parameters and global objective functions. On the contrary, the proposed LRD-GNN pays much attention to local properties, and thus local encoder with a local objective function (low-rank decomposition) is utilized. The local encoder and objective function are essentially different from the global ones, and thus it is hard to point out their connections. Extensive experiments demonstrate the effectiveness and superiority of the local encoder and objective function. We want to conduct in-depth research on their theoretical connections in the future. \n\n---\n\n***Q2. It is difficult for readers, who are not familiar with low-rank, to get the key points in motivations and details of the proposed methods. It is better to review the concepts of low-rank and self-supervised in preliminaries section or appendix.***\n\nR2. Thanks for your suggestion. We will provide the basic concepts of low-rank and self-supervised GNNs in the appendix to improve the readability and completeness of the paper.\n\n---\n\n***Q3. There are some typos. For example, the is a nuclear norm missing in the formula between lines 162 and 163.***\n\nR3. Thanks for your suggestion. We will fully polish this paper. The formula between lines 162 and 163 can be corrected as \n$ \\frac{1}{n_3} \\sum_{i=1}^{n_3}  ||\\bar{A}^{(i)}||_*$.\n\n---\n\n***Q4. The performance on preventing over-smoothing issue is compared against semi-supervised GNNs, i.e., GCN and GAT. The self-supervised GNNs should be compared with.***\n\nR4. According to your suggestion, the ability of our proposed LRD-GNN on preventing the over-smoothing issue is compared with DGI and MVGRL, which are representative self-supervised GNNs. The node classification results with various model depths on Cora, Citeseer, and Wiki-CS are as follows, as well as the visualization in Fig 1 in the global response PDF.  Therefore, compared to both semi-supervised and self-supervised GNNs, the proposed LRD-GNN can prevent over-smoothing issue.\n\n***Table 1. The results on Cora.***\n | Model   | 2-layers | 4-layers | 6-layers | 8-layers | 10-layers |\n|---------|----------|----------|----------|----------|-----------|\n | DGI     | 82.15    | 74.47    | 54.25    | 31.22    | 27.63     |\n | MVGRL   | 83.11    | 80.09    | 61.26    | 39.89    | 36.62     |\n| LRD-GNN | 84.74    | 81.77    | 81.62    | 80.53    | 80.42     |\n\n***Table 2. The results on Citeseer.***\n | Model   | 2-layers | 4-layers | 6-layers | 8-layers | 10-layers |\n|---------|----------|----------|----------|----------|-----------|\n | DGI     | 70.72    | 64.02    | 44.78    | 25.47    | 24.16     |\n| MVGRL   | 71.51    | 65.43    | 62.24    | 57.7     | 47.59     |\n | LRD-GNN | 71.94    | 71.82    | 70.8     | 69.32    | 68.36     |\n\n***Table 2. The results on Wiki-CS.***\n| Model   | 2-layers | 4-layers | 6-layers | 8-layers | 10-layers |\n|---------|----------|----------|----------|----------|-----------|\n | DGI     | 73.62    | 68.07    | 64.37    | 55.36    | 51.64     |\n | MVGRL   | 76.53    | 72.66    | 68.27    | 60.36    | 52.54     |\n | LRD-GNN | 81.55    | 81.17    | 80.62    | 79.53    | 79.42     |\n\n---\n\n***Q5.  The proposed LRD-GNN is a non-parameter model, which may benefit the task of self-supervised learning. However, how can it be improved if the labels are available?***\n\nR5. The proposed model can be improved by constructing the matrix and tensor with the help of node labels. The current self-supervised model constructs the matrix and tensor, which will be decomposed, using the ego-network and similar ego-networks without any supervision. When the node labels are available, the matrix and tensor constructions can be improved according to the predicted node labels. Specifically, the labels of nodes, which are unlabelled, can be predicted using the existing GNNs. Then, the matrix can be constructed using the nodes in the ego-network, which share the same predicted labels as center nodes. And the tensor can be constructed using the ego-networks, whose center nodes’ labels are the same. By employing the predicted node label, the nodes in the constructed matrix and tensor may belong to the same classes with higher probability, thus their ranks tend to be much lower. This facilitates the following decomposition. Therefore, the model can be improved with the help of node labels."}, {"review_id": "GGn5KH6SVM", "reviewer": "Reviewer_KVoZ", "summary": "The paper argues that when dealing with self-supervised learning tasks, utilizing propagation-based GNNs as encoder inevitably encounters two serious issues, i.e., failing to capture local property due to global parameters and lacking the ability on handling homogenous networks without label information. To this end, the authors introduce a different perspective by replacing the propagation-based GNNs with low-rank decomposition-based GNNs. The authors formulate the low-rank decomposition-based GNNs by employing low-rank decomposition to the attribute matrix. Besides, considering that networks require long-distance information for representation, the authors introduce the tensor-based formulation and construct the node attribute tensor from selected similar ego-networks. ", "questions": "see Weaknesses.", "limitations": "n/a", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides a novel perspective to tackle GNNs encoder for self-supervised learning. \n- The proposed low-rank decomposition-based GNNs effectively solve the serious issues introduced by employing propagation-based GNNs. \n- The consideration of incorporating long-distance information successfully captures the long-distance relationships between original and selected similar ego-networks.\n- The experiments show the superiority and generalization of the proposed low-rank tensor decomposition-based GNNs. The ablation study and experimental analysis illustrate the success in a complete view.\n", "weaknesses": "- The reason why the low-rank decomposition-based GNNs preserve local information is not presented clearly. \n- Can the authors clarify the differences between networks beyond homophily and network with heterophily?\n- How can the proposed model be enhanced in semi-supervised tasks by using the node labels.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1. The reason why the low-rank decomposition-based GNNs preserve local information is not presented clearly.**\n\nR1. The characteristic of local information preservation is from both the matrix/tensor construction and low-rank decomposition. Firstly, both the matrix and the slice of the tensor, which will be decomposed, are constructed from the attributes of nodes in the local ego network. This leads the obtained representation to learn from local information. Secondly, the low-rank property is the requirement of the local propagation between nodes with the same labels. Thus, the low-rank decomposition, which seeks low-rank representation, essentially performs local propagation. Therefore, the low-rank decomposition-based GNNs possess the potential of preserving local information.\n\n---\n\n**Q2. Can the authors clarify the differences between networks beyond homophily and network with heterophily?**\n\nR2. The homophily rate is a measurement to describe the proportion of linked nodes belonging to the same classes. Vanilla GNNs perform well on networks with high homophily rates, i.e. homophilic networks. The network with heterophily are the networks with low homophily rates, while the networks beyond homophily are the networks, whose homophily rates are not high. Therefore, networks with heterophily belong to networks beyond homophily. \n\n---\n\n**Q3. How can the proposed model be enhanced in semi-supervised tasks by using the node labels?**\n\nR3. The proposed model can be enhanced by constructing the matrix and tensor with the help of node labels. The current self-supervised model constructs the matrix and tensor, which will be decomposed, using the ego-network and similar ego-networks without any supervision. When the node labels are available, the matrix and tensor constructions can be improved according to the predicted node labels. Specifically, the labels of nodes, which are unlabelled, can be predicted using the existing GNNs. Then, the matrix can be constructed using the nodes in the ego-network, which share the same predicted labels as center nodes. And the tensor can be constructed using the ego-networks, whose center nodes’ labels are the same. By employing the predicted node label, the nodes in the constructed matrix and tensor may belong to the same classes with higher probability, thus their ranks tend to be much lower. This facilitates the following decomposition. Therefore, the model can be enhanced with the help of node labels."}]

Author rebuttal:
We would like to express our sincere appreciations to the reviewers for their insightful comments and compliments to our paper. The PDF contains the figure of results on preventing over-smoothing issue.

Meta-review: All the reviewers agree that this is a well-written paper with novel approaches to encourage low-rank property for GNN in the semi-supervised setting. Empirical results also demonstrated superior performance compared to other methods. I recommend to accept this paper.
Decision: Accept (poster)