PolyGCL: GRAPH CONTRASTIVE LEARNING via Learnable Spectral Polynomial Filters
Authors: Jingyu Chen
Runlin Lei
Zhewei Wei
Venue: ICLR 2024 spotlight (2024)
Keywords: Graph Contrastive Learning
Spectral Graph Neural Networks
Polynomial Filter
Heterophilic Graph Representation Learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We introduce spectral polynomial filters into graph contrastive learning to model heterophilic graphs.

Abstract: Recently, Graph Contrastive Learning (GCL) has achieved significantly superior performance in self-supervised graph representation learning. 
However, the existing GCL technique has inherent smooth characteristics because of its low-pass GNN encoder and objective based on homophily assumption, which poses a challenge when applying it to heterophilic graphs.
In supervised learning tasks, spectral GNNs with polynomial approximation excel in both homophilic and heterophilic settings by adaptively fitting graph filters of arbitrary shapes. 
Yet, their applications in unsupervised learning are rarely explored.
Based on the above analysis, a natural question arises: Can we incorporate the excellent properties of spectral polynomial filters into graph contrastive learning?
In this paper, we address the question by studying the necessity of introducing high-pass information for heterophily from a spectral perspective.
We propose PolyGCL, a GCL pipeline that utilizes polynomial filters to achieve contrastive learning between the low-pass and high-pass views.
Specifically, PolyGCL utilizes polynomials with learnable filter functions to generate different spectral views and an objective that incorporates high-pass information through a linear combination. 
We theoretically prove that PolyGCL outperforms previous GCL paradigms when applied to graphs with varying levels of homophily.
We conduct extensive experiments on both synthetic and real-world datasets, which demonstrate the promising performance of PolyGCL on homophilic and heterophilic graphs.

Published as a conference paper at ICLR 2024
POLYGCL: GRAPH CONTRASTIVE LEARNING VIA LEARNABLE SPECTRAL POLYNOMIAL FILTERS
Jingyu Chen
Runlin Lei
Zhewei Wei
Renmin University of China jy chen@ ruc.edu.. cn
Renmin University of China runl runlin_ _e_leiie @ruc. weu...duuu............ .cn
Renmin University of China zhewei @ruc. edu. cn
ABSTRACT
Recently, Graph Contrastive Learning (GCL) has achieved significantly superior performance in self-supervised graph representation learning. However, the existing GCL technique has inherent smooth characteristics because of its low-pass GNN encoder and objective based on homophily assumption, which poses a challenge when applied to heterophilic graphs. In supervised learning tasks, spectral GNNs with polynomial approximation excel in both homophilic and heterophilic settings by adaptively fitting graph filters of arbitrary shapes. Yet, their applications unsupervised learning are rarely explored. Based on the above analysis, natural question arises: Can we incorporate the excellent properties of spectral polynomial filters into graph contrastive learning? In this paper, address the question by studying the necessity of introducing high-pass information for heterophily from a spectral perspective. We propose POLYGCI, GCL pipeline that utilizes polynomial filters to achieve contrastive learning between the low-pass and high- pass views. Specifically, POLYGCL utilizes polynomials with learnable filters to generate different spectral views and an objective that incorporates high-pass information through linear combination. We theoretically prove that POLY outperforms previous GCL paradigms when applied to graphs with varying levels of homophily. We conduct extensive experiments on both synthetic and real- world datasets, which demonstrate the promising performance of POLYGCL on homophilic and heterophilic graphs. Code is available at /https://github com/ Chhehhh-Coott/tooiyiiooe
INTRODUCTION
Self-supervised representation learning, which aims to learn informative representations without the demand of costly handcrafted labels, has achieved a wide range of applications in areas such as
computer vision, natural language processing, and multimodal (Chen et al. 2020 Grill et al. 2020 Devlin al. 2019 Radford et al./ [021] Gao et al., (023). On non-Euulidean graph data, Graph Contrastive Learning (GCL), has become mainstream research direction in self-supervised scenarios, namely learning representations by capturing consistency across different views and optimizing the objective function based on mutual information maximization to distinguish positive and negative examples (Veličković et al. 2019 Hassani & Khasahmadij 2020 Peng et al.) 2020 Zhu et al. 2020b). Generally, most existing GCL methods rely on the homophily assumption, which means nodes connected by edges tend to have similar node representations. These methods adopt a low-pass filter (such GCN) encoder and the objective which smooths the representations of neighboring nodes. Therefore, the existing GCL methods have shown excellent performance on homophilic graphs.
However, heterophilic graphs are also prevalent in reality because of the principle of opposites attracting, e.g. dating networks. To address heterophily, many efforts have been made in supervised domain (Pei et al.] 2020 Lim et al.] (02T). Among them, spectral graph neural networks with learnable polynomial filters adaptively learn appropriate graph filters from graph data in an end- to-end manner (Chien al. (202T] He et al. 202T 2022, Guo Wei 2023), achieving desirable performance on both homophilic and heterophilic graphs due to more powerful expressiveness. Yet, the applications of spectral GNNs with polynomial filters self-supervised scenarios are relatively
"Zhewei Wei is the corresponding author.

---

Published as a conference paper at ICLR 2024
Cora
Chameleon
80
60
75
70
DCI
Supervised
4b
DGI
Supervised
GRACE
GRAGE
35
CCN.
Monamial
Onibyiteev
+ D.GNN
Monomial
Chebyshev.
Encoder
Encoder
Figure 1: Mean accuracy comparison in the supervised setting (red line) and with 3 self-supervised methods while the encoders are directly substituted with monomial and Chebyshev polynomial filters.
limited, and the traditional paradigm of GCL fails be applied heterophilic graphs due to its low-pass nature, leaving self-supervised learning in heterophilic settings an unsolved task. Based on the above, natural question is: How can we effectively introduce the properties of spectral polynomial filters into GCL to ensure expressiveness in both homophilic and heterophilic settings?
To answer the above question, we first consider substituting the low-pass GCN encoder in classic GCL methods with two classic polynomial filters, that are the monomial basis in GPR-GN (Chien et al. 2021) and the Chebyshev basis ChebNetll (He al. [022). As shown in Figure T this simple idea results in performance degradation in self-supervised settings with three different optimization objectives (green, blue, and purple lines), which conflicts with the performance improvement in supervised learning tasks (red line). A similar phenomenon occurs in He et al. (2022) when the spectral polynomial filter is learned the semi-supervised learning task, demonstrating the difficulty of learning a proper filter without sufficient label information. To address the problem, in this paper, we propose POLYGCL, a novel Graph Contrastive Learning framework via learnable spectral polynomial filters to realize effective learning graphs with different homophily levels. Specifically, POLYGCL restricts the expressiveness of the polynomial filters from a spectral perspective to construct the low-pass and high-pass views and introduces simple linear combination strategy to construct the optimization objective, which can be theoretically proved to benefit POLY GCLY from achieving lower loss in the spectral domain and boosting the performance of downstream tasks. Our contributions can be summarized as follows:
We propose POLYGCI, which introduces the superior properties of polynomial filters into Graph Contrastive Learning. POLYGCL achieves effective learning on both homophilic and heterophilic graphs without the complex data augmentation or pre-processing in traditional GCL paradigms.
We theoretically prove the necessity of the high-pass information in heterophilic settings. We also verify that the learning objective constructed by simple linear combination strategy of the low-pass and high-pass information enjoys theoretical guarantees on downstream tasks.
Extensive experiments real-world and synthetic datasets across different homophily levels conducted to verify the superior performance of POLYGCL without introducing extra complexity. Additional ablation study further confirms theoretical results.
2 RELATED WORK
Graph Contrastive Learning (GCL). As a mainstream research topic in self-supervised learning. GCL can be divided into two categories: (1) Augmentation--asee methods adopt different types of
data augmentations to generate different views, and the optimization of the loss function is based
on maximizing mutual information between them (Hassani & Khasahmadi] [020; You et al.] 2020
Zhang et al. 202T Zhu al. 2020b 2021b Liu et al.) (023). We provide detailed comparison of
the augmentation techniques and the space complexity of these methods in Table 7f Appendix D
(2) Augmentation-
methods aim to remove the complex data augmentation or negative sampling
strategy but consider inputting the same graph into different encoders obtain different views and
push together the representations of the same node/class from different views (Peng et al. 2020
Mo et al.) 2022) Xiao et al. 2022). However, the works mentioned above utilize the low-pass GNN
encoders and optimization objectives that smooth neighbor representations inherently, resulting in their unsatisfactory performance heterophilic graphs.
2

---

Published as a conference paper at ICLR 2024
Spectral-based GNNs. From spectral domain perspective, GCN first-order approximation of ChebNet has been proven to be a typical low-pass filter and has been widely used in graph representation learning tasks. Existing works often consider using polynomials to approximate the filter function, which preserves strong fitting capabilities and avoids the O(N3) complexity of Laplacian eigendecomposition. There different polynomial choices while taking into account various excellent properties of the basis, such as the monotonic basis of GPR-GNN (Chien et al. 202T), the Chebyshev basis of ChebNet (Defferrard et al. 2016 He et al. 2022) and the non-negative Bernstein basis in BernNet (He et al., (021), etc. Although spectral polynomial filters have been proven to be capable of fitting arbitrary filter functions that work for both homophilic and heterophilic
graphs. there is still a lack of superviedd applications for them.
PRELIMINARY
Problem Formulation. Given an undirected graph 9 = (V, Let N = [V] and E = |8] be the number of nodes and edges of the graph, and F denote the feature dimension. We denote X E NNF A E {0. 1 1 NNNN as node features and adjacency matrix respectively. In supervupe node representation learning, the objective is to learn an encoder, & RRN x R IR xD such that E(X, A) 2 = {Z1, 22, ................. 2N } represents high-level representations x, E RD for each node v. The representations may then be used for downstream tasks, such as node classification ZZu
et al. 2020b and clustering (Bhattacharjee & Mitra 2021 Yuan al. 2024).
Homophily. Homophily describes the tendency of nodes in the graph to form edges with nodes with the same label. Recently series of evaluation metrics of graph homophily have been proposed from different perspectives (Lim et al. 2021 Pei et al.) 2020). We use the edge homophily degree
h
((.,,,)). JECA,, (Zhu et al. 2020a) as the evaluation metric in this work, where the
value range is [0, 1]. If h approaches I, the homophily degree of the graph is higher. Otherwise, h approaching 0 indicates a higher degree of heterophily. In Table 6 of Appendix C.2 we list the homophily degree of some real-world graph datasets involved in this work.
Spectrum and Graph Filtering. Define Graph Laplacian L D A and the normalized version L - D- AD 1/2, where D a diagonal matrix with D = Σ Aij. Decompose the normalized Laplacian as L = UAU", note that A = diag(>o. (o......... AN-1) is the so-called Laplacian spectrum with eigenvalue 0 A < X I ... < A < 2, and U is unitary matrix consisting of eigenvectors. Further, the graph filtering operation on X is defined as Ug(A J where g( (A) denotes the graph filter function. Recent studies (Chien al. 202T He et al., 2021 2022) suggest using polynomials to approximate g(A) by K Koorder truncation can fit (A)) of any shape and avoid O(N") complexity of eigendecompositiin.
4 PROPOSED METHOD: POLYGCL
In this section, we revisit the problem of graph filtering in a self-supervised manner. Existing GCL methods mainly focus the homophilic setting and generally fail when faced with heterophilic graphs. Spectral graph neural networks, designed to handle graphs of varying homophily levels, are primarily constrained supervised learning tasks. Therefore, we are looking for an approach that enjoys the desirable properties of spectral methods and handles heterophily as well in self-supervised graph representation learning tasks.
The key idea of current spectral methods lies in adaptively learning polynomial filters via supervised signals, e.g., labels. To transfer them into self self-supervised scenarios, a natural idea emerges: directly use the learnable graph filter as the encoder and switch the objective function with self-supervised one. In Figure [ we implement this idea by swapping the GNN encoder module in three classic self-supervised GCL methods (DGI (Veličković et al. 2019) with the binary cross-entropy loss, GRACE (Zhu et al.) 2020b) with the InfoNCE loss and CCA-SSG (Zhang et al., 202T with the CCA loss inspired from Canonical Correlation Analysis) with two polynomial filters (monomial and Chebyshev basis) on homophilic graph Cora a and heterophilic graph Chame loon Unfortunately, despite the exceptional performance of GPR-GN (Chien et al. 2021) (monomial basis) and Cheb- Netll (He et al. 2022) (Chebyshev basis) over GCN in supervised tasks, directly plugging them into self-supervised settings as the encoder causes performance degradation compared with the simple
3

---

Published as a conference paper at ICLR 2024
low-pass GCN. This phenomenon could be attributed to the inconsistency between the powerful fitting ability of polynomial filters and the lack of supervision signals in self-supervised learning scenarios, which further inspires to add constraints the shape of polynomial filters, thereby facilitating encoder learning in label-scarce scenarios. As the solution, we present POLYGGI, which learns the polynomial filter based on the fixed low-pass and high-pass channels construct corresponding views of different spectral properties, thus facilitating the construction of the optimization objective that captures important information in the spectral domain. The implementation of the encoder and the optimization objective are given in Section 4.1 and Section respectively.
4.1 ENCODER: INTRODUCE THE POLYNOMIAL FILTERS
While existing GCL methods focus on low-pass encoders for homophilic tasks. recent studies find that high-frequency information is essential for heterophilic graphs (He et al. 2022 Lei et al. 2022). To ease the learning process in the self-supervised setting, we decouple the low www-pass and high-pass channels of the polynomial filter and restrict it to fit only low-pass and high-pass filter functions. Following He et al. (2022), we adopt Chebyshev polynomials with interpolation as base polynomials, which can be formulated as Σk=O Wk Th (L)X, where = 2L/ 3L/Amar I, and wi is reparameterized equation
2
K
K +11 7)
W/k
where zj = cos
1+1/2
K+I π -j= o.... K denote the Chebyshev nodes for TK+1, and the filter value
h((x;) at the Chebyshev node Tj reparameterized as learnable parameter "/ for æ; [-1, 1] Gil
et al. 2007 He et al., 20022. Suppose the filter function is non-negative following He et al. (2021). we use the prefix sum make the non non-negative learnable parameter 7/ increment with j to model
the high-pass filter. Likewise, a low pass filter can be reparameterized with prefix difference so that
the filter value (²)) decreases in À E [-1, Formally, we have:
H
7 # = To- Σ Mo i L,...,K,
(2)
1=1
where 70' = 70 = 7- In this way, we have 7 S 14411:7 2 1441 (which denotes the filter value h(x,)) for i = 0. .... K - 1, thus guarantee the high pass/low-pars pass property for h(A). Based on the above analysis, the low-pass and high-pass polynomial filter encoders can be expressed as equation
Σ = ZH - So Σ
Sh TL
where w and w are obtained via substituting y in equation I with 71 and 7 in equation 2 fo(+) represents a shared MLP with parameter 0 for fixed D dimensional output.
4.2 OPTIMIZATION OBJECTIVE IN POLYGCL
In POLYGCI, the optimization objective serves as the self-supervision signal for model training. As shown in equation 3 the embedding output by the low-pass encoder Z, and the high-pass encoder Zh can be considered as tow-pass/high-pas spectral views respectively. Thus, an intuitive idea is to obtain the final embedding via linear combination Z aZ₁ + 3ZH. where a, B are linear coefficients which can also be set as learnable parameters.
We follow Veličković al. (2019) and Hassani & Khasahmadi (0200) to perform contrastive learning between local patches (node embeddings) and global summaries (graph embeddings), aiming to achieve mutual information maximization between the spectral views. Specifically, we randomly shuffle X to get the negative low www-pass/highhae pass pass embeddings Z and ZH, and the global summary can be obtained by mean pooling as g Mean(Z) + Σ Z., where Z, denotes the embedding vector for node U. To score the agreement between node and graph representations, the discriminator DD is defined as (Z,, g) = (Z, Wg E (0, 1). where W E RDx is the weight matrix and serves as the sigmoid activation function. Based on the above components, we derive the overall Binary Cross-Entre Entsooyy (BCE) loss as equation
CCBE 4N
EE log D DZZ log(1 - DD(2,, g)) + log D(Z g) + log(1 - -D(Zin ())) (4)
4

---

Published as a conference paper at ICLR 2024
Note that maximize equation 4 for optimization. The whole training paradigm of POLYGCL is presented in Algorithm| and Figure coupled with the polynomial encoders shown in equation
Algorithm 1: Training Algorithm for POLYGCL
Input: Node features X. input adjacency A. initialized encoders &, initialized coefficients a, 33, maximum iterations T, polynomial order K.
for epoch 0, 0,1,.... ..... do
X shuffle(X); corruption
% 70' To % initialize %o 70' with Yo in for i L, ...... K do
71t Ej= Re)U( % high-pass encoder
N 70 Ej=1 ReL.U())): low-pass encoder
Obtain 8d and &d via af and Tf respectively shown in equation
Zr + (²(X, A), Z
(X, A); % positive embeddings
Zr + 8 ZH + (X, A); % negative embeddings
Z = + (ZH; % linear combination
Compute loss via equation 4 and update parameters in & and E":
11
Output: _ and H with frozen parameters; learned coefficients o. B.
b(A)
+
Low-pass
Poly
N X
+ k(A)
Linear
(i(A)
Pooling 1 xx
Combination
x
(CA)
High-pass
*
Contrast
Figure 2: Illustration for the overall pipeline in POLYGCL which takes node features X and adjacency matrix as input. "Poly" and "Init" are short for "polynomial" and "initialization" respectively. There two components in POLYGCI. The first is the generation process of low-pass (blue) and high-pass (red) spectral views via polynomial filters. By lincar combination, POLYGCL can fit filters of complex shapes shown in green lines. The second one to perform contrastive learning between the aggregated embedding (green) with the low- www-pass/high-pes outputs via equation
4.3 REVISIT GCL FROM THE SPECTRAL VIEW
In this section, we suppose the downstream task in GCL is binary node classification and the input dimension F to revisit the existing GCL methods from the spectral view. For each node v, is attached with one-hot class label. We denote Y E Nx2 (yo. y1) the label matrix, where ys is the indicator vector of class C, = 0, 1. Let the difference node labels be Ay = Yo y1- Then define GCL from the spectral view where a serves as the activation function. Note that only stage (2) involves label y. However, as MLP can be considered all-pass filtering, the graph filtering operation in GCL can be simplified as Z Ug(A)U" X. Ideal filtering results in a distinguishable node representation associated with Ay to identify node labels. Let U Ay and U X, we introduce Assumption | about the basic correlation between them.
stages: (1) Z Ug(A) ( (2) (MLP((Z)
Assumption Assume that a and f are positively correlated in the spectral domain, that is. [[ w 0.
Note that cSBM (Chien et al.) 2021 graph generation process is in accord with Assumption I and further justification is discussed in (ppendix/C.11... We utilize the Spectral Regression Loss (SRL) in EvenNet (Lei et al. 2022) the evaluation metric of the spectral filter, which is formulated as
5

---

Published as a conference paper at ICLR 2024
N-1 L(9)=
E
Li=0
VN
g(A.)
2(
A graph filter that achieves lower SRL is of higher
performance the downstream task. Further, Corollary [ formally demonstrates that there are different filter monotonicity tendencies for homophilic and heterophilic graphs.
Corollary 1. In the task of binary node classification on k-regular graph 9. for the homophilic graph of + choose the low-pass g( ensures a lower SRL upper bound. Similarly, for the heterophilic graph of h + 0, the high-pass ( corresponds to a lower SRL upper bound.
Given the fact that the lowppass information benefits graphs with high homophily degree and high- pass frequency promotes the learning of graphs with heterophily, a natural idea is to linearly combine the low-pass and high-pass filtering together. Theorem | provides a special case to illustrate this.
Theorem 1.
For a binary node classification task a k-regular graph S. suppose AN-1 2 and we consider the linear bounded filter function, the low-pass filter Now = c _ E [0. c] and the high-pass filter Ghigh 2 E [0, c). then linear combination of the low-pass and high-pass filter Ijoint = ISlow + yghigh x 2 0, y 2 0, x + = achieves lower expected SRL upper bound than Slow in heterophilic settings, that is, E, joantt < E2 [Loow] for UO. h U(2,1) 1), where i,
denotes the upper bound for L.
Remark. Theorem [ reveals that in heterophilic graphs, the linear combination strategy of low-pass and high-pass information has a smaller expected SRL upper bound than utilizing the low-pass information only, which provides a theoretical advantage to introduce the high-pass information for modeling heterophilic graphs.
4.4 THEORETICAL ANALYSIS
In this section, explain the effectiveness of POLYGCL from the view of Mutual Information (MI) theory. We first present Proposition [ which builds a connection with DGI (Veličković et al. 2019): Proposition The upper bound of LBCE has the same form as the DGI loss, which indicates LBE can be considered as the lower bound of &DG--
Proposition claims that maximizing LBCE for optimization is equal to maximizing the lower bound of LDGI. Based on Proposition| we can derive Theorem 2
Theorem 2. Given two deterministic encoder functions ()))) and & (.), which are the low-pass polynomial filter and high-pass polynomial filter respectively. Let z (zi)jem(z000 be the neighborhood of the node in the k-th graph that collectively maps to its high-level features, e" c"(Z(()), where is the neighborhood function that returns the set of neighborhood indices of node i for graph (kk) Let he2d Linear(h h Assume that |Z. = IZ| = =gg h Then, h. that optimising equation / also maximizes MI(Z (k), h,ag).
hf _ (z()))
Note that in Theorem neighbor information (corresponding to polynomial filters of order K) through both the low-pass encoder and high-pass encoder. Maximizing MI(Z((), (k), ho99) implies that the final embedding h combining both the low-pass and high-pass information, preserves the maximum correlation with the node's original K K-hop representations.
denote he as our final embedding, which aggregates the K-hop
log 2, h. 1999), but also maximizes the Jensen-Shannon divergence between the positive and negative distributions in both the low-pass and high-pass views. Detailed discussion is deferred Appendix A.3 due to space limitation.
Remark. We can rewrite equation 4 = 2JS (P
Pree) 2JS (P ppos
which proves that maximizing ΣECE not only maximizes MI(Z,"
Connection with downstream tasks. In POLYGCL, we have two self-supervised signals: the low-pass information 2y and the high-pass information zH. Based on the mutual information maximization interpretation of equation 4 we essentially combine both low-pass and high-pass information as the self-supervised signal. This involves maximizing the mutual information between the representation h and the joint distribution (zL, z.). Furthermore, Corollary 2 demonstrates that our method provides a tighter upper bound on the downstream Bayes error Tsai et al. 2020 Xiao et al. 2022) compared to using only low-pass or high-pass information. This suggests that

---

Published as a conference paper at ICLR 2024
Table 1: Mean node classification accuracy (%) with a 95% confidence interval on cSBM graphs. Boldface letters indicate the best results and underlining letters denote the second best results.
Methods
p= -1
0 =
-0.75
0 =
-0.3
@ -0.25
0 ==0
0.25
0.5
d= 0.75
DGI
83.04 1.
93.24
85.75
68.41
1.591
59.95 1071
68.70 500
84.04
91.53 1.00
82. 68 1.07
MVGRL
68.80 1:0
84.35 007
78.81
1 6.8
64. 105
59.09
1:5
70.74 a/3
89.91 0.5
95.95
2:03)
89:
1:55
GGD
$2.90 0:333
92.76
85.56
66.63
56.00
67.06
84.23
91.75
83.84
GMI
54.47 2:344
54,38
-071
50.70 691
50.41 1:4
51.79 2.03
59:57 am
82.28 0.76
93.74 4:146
96.01 1/6
CCA-SSG
50.55
52.71
51.21
50.88
51.16=057
56.33
72.41
90.83
62.03
BGRL
49.86 +:30
:4:44
49.95 000
50.21 +:3
$4.58 0.99
60.80 #:6
70.79
2:039
GBT
57.41 1:0
64.99
58.84 0:00
51.80 1.7
57.95 0.s
72.62 1/
91.09
97.80 1:035
96.03 1.0%
GRACE
98.74 +:228
97.55 =0
90.06 6.90
68.74 +
56.85
1.12
66.70 #:1
89.50 0M9
97.41 2:0:5
98.78 1:2
GCA
76.50 a:3
85.56
78.96
62.32
239
58.01
65.
58.11 145
77.16
81.38
75.54 0:6
GriphCL.
58.82 1.1
57.89
52.91 0.20
50.18 1:359
51.25
62.54
65.57
1:337
71.31
GREET
50.82 0.57
58.79
59.91 Um
63.57 2.6
65.99
0.4
71.04 b00
80.17 0.30
83.11 0:333
75.93 1:10
POLYOCL
8:17
94.23 0.3
:: 6.50
75.43 8.08
0.99
69.43 + 6x8
88.22 0.72
: 0.29
99.29 +:255
downstream tasks can benefit from the learned representations obtained through our objective function. We attribute this advantage to our utilization of both low-pass and high-pass information as the self- supervised signal. All the detailed proofs are presented in Appendix A
Corollary 2. Suppose that downstream label y is a M-categorical random variable and the down- stream Bayes error on learned representation h as Pa = En [1 maxyey P(ý = -v/v], where ý is the estimation for label from downstream classifier. Then, we have an inequality on the ervor upper bound sup (P S min (sup(Pr...)) (PhhP) suu Sup (P where sup(PE) denotes the error upper bound for representation h. The error upper bound of the low-pass and high-pass representations, how and hnigh, are denoted as sup sup(Pe (PEn...) and sup (mngg))) respectively.
5 EXPERIMENTS
In this section, we conduct experiments about self-supervised node classification on both synthetic datasets and real-world datasets to evaluate the performance of POLYGCL and gain further insights.
5.1 BASELINES AND SETTINGS
We compare our method with three types of GCL baselines as follows based on their optimization
objectives. (1) BCE-based GCL methods: DGI (Veličković et al., 2019), MVGRL (Hassani &
Khasahmadi 2020). GMI (Peng et al.] (020) and GGD (Zheng et al. 2022).
(2) InfoNCE-basee
GCL methods: GraphCL (You et al. (020). GRACE (Zhu et al. 2020b), GCA (Zhu et al., (02
GREET (Liu et al. 2023). (3) Invariance-keeping GCL methods: BGRL (Thakoor et al [2022).
GBT (Bielak et al. 2022), CCA-SSG (Zhang et al. 2021) Details about the model architectures and
hyperparameters listed in Appendix
Evaluation Protocol. We follow the linear evaluation scheme as introduced in Veličković et al. (2119), which can be treated "two-stage" learning. For the first stage, node features and graph structure without any label information are inputted, and each model is trained in a self-supervised manner. Then stage (MLP stage), the representations output by the GNN encoder in stage 1 fixed and used to train, validate, and test via simple linear classifier. As for the train/valid/ten splits on all datasets, we follow Chien et al. (202T) to randomly split the nodes into 60%, 20%, and 20%, and all methods share the same 10 random splits, output embedding size D and hyper- syper-parameters in stage for fair comparison. See Appendix F3 to learn more about the detailed settings.
5.2 EVALUATION ON SYNTHETIC DATASETS
Datasets. To better validate our theoretical results, we adopt the cSBM model to generate graphs with arbitrary homophily degrees following Chien et al. (202I). Note that the homophily degree of cSBM graphs is determined by the parameter homophilic the graph is and vice versa. Details about the cSBM dataset are included in Appendix [C.I
1, where the closer & approaches 1, the more
The results are shown in Table T First, observe that in self self-supervised learning, most models reach their performance peak when (o] approaches 1, and the model performance is generally poor when (e) approaches 0, which aligns with the findings of supervised learning in
Results.
7

---

Published as a conference paper at ICLR 2024
Table 2: Mean node classification accuracy (%) on real-world graphs. Boldface letters indicate the best results and underlining letters denote the second best results.
Citeseez
Pubmed
Coznall
Texas
Wisconsin
Actoz
Chamsleon
Squiccel
DGI
85.88
76.44 am
$2.13
70.82 4:2
$1.48 179
75,00 100
32.09 L:s
$8,23
38.80
MVGRL
87.36 2:0
78.70
86.30
67.70
73.11
74.25
31.98
57.75
40.25
GGD
87:21 1M
79.25 2mm
85.38 1:035
80.33 128
82.62 1:
73.25 1:3
32.27
$7.64 1:1
40.87 1/6
GMI
85,09
76.18
83.06
62.79
68.03
62.13
32.37
62.47
39.82
CCA-SSG
4:1m
1:1
82.88 1:19
34.86 1:16
1:100
BGRL
$4.45
14.31 L.
$3.06 023
59.84 2:2
09.54 1:381
62.88 4:133
32.48 1:187
64.09 1:177
47.02
GBT
$4.89
76.59
86.10
59,18
72.79
62.38
34.34
68.77
48.86
$3:27 0:074
1:2
6.1
11:32
155
72.13 1:135
31.97 1:115
1:4
GCA
$1.09
75.23 1:5
$2.01 2031
53.11 1:13
81.97 1:3
73.50 1:100
31,13 1:171
65.51
1:177
47.13 0.0
GraphCL
$6.54
78.99
85.16
61.48
66.07
60.63
32.45
58.49
42.92
GREET
85.16
79.06
85.64
78.36
78.03
84.63
38.26
60.57
39.76 6:074
POIYGCI.
87.57 1.442
79.81
000
87.15 1:27
82.62
88.03
1.00
85.50 1MN
41.15 1.0
71.62 1.066
56.49 1.022
Table 3: Experimental results on heterophilic graphs. Accuracy is reported for Roman-empire and Ama zon-rat ngs, and ROC AUC is reported for Mi nesweeper, Tolokers, and Questions ions following Platonov et al. 2023 OOM denotes "out of memory".
Methods
Roman-cmping
Amazon-ratinga
Kineswcopor
Tolokers
Questions
DGI
58.57
42.72
68.36 6.0
76,29
74.44
MVGRL.
1um
0.2
90.07 6.3
GGD
58.04 1.t
43.15
78.15 1:0
76.43
74.63
GMI
32.33 2:22
40.98 0.30
72.38
79.89
OOM
CCA-SSG
42.82 024
72.42 + 0.00
75.46 0.5
14.64 + 0,7
BGRL
39.34
41.17
72.82
79.73
72.27
1nM
1.
72.39 1.4.
75.74 078
GRACE
59,57
43,79
68.10
76.31
74.34
GCA
59.77 +.40
42.57 0.17
68.11
77.26
75.09
GraphCL
a30
6.14
82.15 0.40
76.88 0.00
60.51 1445
GREET
72.68
41.19
82.71
80.60
OOM
POLYGCL
72,97
44.29
86.11
83.73
75.33
Chien et al. (2021) Specifically, POLYGCL achieves 7 optimal or sub-optimal results in all the settings, holding the best performance when meeting extreme homophily/heterrohilyy (oo) 1) or the structural information is useless (l6) 0). On other types of datasets, POLYGCL also has comparable performances. We attribute this to the generalization ability the www-pas/hhigh-pas
linear combination strategy across different levels of homophily.
5.3 PERFORMANCE ON REAL-WORLD DATASETS
Datasets. We conduct the downstream node classification tasks to evaluate the quality of em- beddings on 14 real-world benchmark datasets across different homophily degrees. Among them, Cora, Ci teseer, and Pubmed (Sen al. 2008 Yang et al. 2016) are considered homophilic graphs, while Chamelede loon, Squi rrel from Wikipedia (Rozemberczki et al. [022), the Actor co- occurrence graph and Cornell, Texas, Wisconsin from WebKB (Pei et al. (2220) are denoted as heterophilic graph datasets. We also conduct experiments on 5 larger heterophilic graphs with different structural properties, which are Roman. empire, Amazon rat ings, Minesweepen Tolckers and Questions (Platonov et al. 2023).
Results. We present the performance on real-world datasets in Table 2 and Table 3 Generally, POLYGCL outperforms all baselines in 12 out of 14 benchmarks and achieves the runner-u up per- formance on the other 2 datasets. Notably, POLYGCL slightly boosts the performance compared other baselines for homophilic graphs while exhibiting clear performance gain graphs of heterophily, especially the 15.6% and 7.6% relative improvement on Squirre grell and Actor re- spectively. POLYGCL's superior performance indicates the exploitation of low-pass and high-pass information can universally benefit representation learning, which is further consistent with our theoretical results.
5.4 ABLATION STUDY
To analyze the effectiveness of introducing spectral polynomial graph filters and the high-pass information, we develop regularized variant of POLYGCL by setting the linear combination
8

---

Published as a conference paper at ICLR 2024
coefficients a, B 3 1,a 0, 0 to satisfy the condition in Theorem In addition, considering that the generation process of cSBM naturally meets Assumption we repeat the experiments in Section 5.2 with the regularized variant.
We first examine the model's preference for www-pss/hiigh-Pee -aaghhppsssss information by checking the value of (0, 1], which controls the proportion of low-pass representation Zr in the final representation Z. In Figure 3 we observe that a shows an increasing trend as á increases in the range of [-1, 1], indicating that in heterophilic graphs (ø < 0), the low-pass information accounts for less of the overall, whereas we draw the opposite conclusion in homophilic cases (Ø > 0). In addition, we draw the learned filters (normalized [0. 1) of the cSBM datasets with different @ Figure 4 For Φ POLYGCL tends to learn increasing functions corresponding to high-pas, figh-pass filters, while low-pass filtering dominates homophilic settings. When & = O, which means no structural information is useful, a approaches 0.5, and the learned filter function is almost an unchangeable line with the all all-pass property. The above diseussions illustrate that POLYGCL can indeed learn filters different shapes graphs across homophily by introducing high-pass information via polynomial filters.
1.0
0.0
0.6
0.4
0.2
0.0
Figure 3:
The learned a on the cSBM datasets. The shaded region denotes 95% confidence interval.
Figure 4: The normalized learned filters of POLYGCL
with a + 3 1,a a 2 0, B on cSBM datasets.
5.5 COMPLEXITY ANALYSIS
The time complexity of POLYGCL consists of two components: the learning of polynomial filters and the loss computation. Suppose for the graph with N nodes and E edges. the coefficients of the polyno- mial encoders in POLYGCL can be precomputed in time linear to K, therefore the propagation process in K K-order polynomial filters can be finished in O(KF) time. Meanwhile, the computation of L BCE costs O(N) time. Thus the overall time complexity of POLYGCL O(KE + N). which is linear to K, E and N. Table 4 shows the results on a large heterophilic graph arXiv year (Lim et al. (02T) with over I million edges, where OOM denotes "out of memory and "_" means failing to finish preprocessing in 24h. POLYGCL still holds the SOTA performance with satisfactory efficiency.
Table 4: Mean classification accuracy on arXiv-yeaz.
arXiv-year
DGI
40.60 021
GGD
022
MVGRL
BGRL
OOM
GBT
41.90 036
CCA-S5G
40.76
GRACE
OOM
POLYGCL
43.07 0.3
6 CONCLUSION
This paper addresses the problem of dealing with heterophilic issues in self-supervised learning settings. Inspired by the remarkable success of spectral graph neural networks with polynomial approximation in handling heterophily, we seek to extend their desirable properties to the self- supervised domain. We propose POLYGCL, a GCL framework that leverages contrastive learning between the low-pass and high-pass views. Specifically, POLYGCL utilizes the polynomial filters as encoders and incorporates a linear combined objective between low and high frequencies in the spectral domain. Theoretical analysis provides solid evidence that POLYGCL consistently outperforms previous low-pass designs by achieving lower loss. Extensive experiments demonstrate the exceptional performance of POLYGCI. across both homophilic and heterophilic settings.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
The work was partially done at Gaoling School of Artificial Intelligence, Beijing Key Laboratory of Big Data Management and Analysis Methods, MOE Key Lab of Data Engineering and Knowledge Engineering, and Pazhou Laboratory (Huangpu), Guangzhou, Guangdong 510555, China. This research was supported in part by National Natural Science Foundation of China (No. U2241212, No. 61932001), by Beijing Natural Science Foundation (No. 4222028), by Beijing Outstanding Young Scientist Program No. BJJ.ZYJHH 2019 100020098, by Alibaba Group through Alibaba Innovative Research Program, and by Stuawei-Renmin University joint program on Information Retrieval. We also wish to acknowledge the support provided by the fund for building world-class universities (disciplines) of Renmin University of China, by Engineering Research Center of Wext-Generation Intelligent Search and Recommendation, Ministry of Education, Intelligent Social Governance Interdisciplinary Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double- First Class" Initiative, Public Policy and Decision Decision-making Research Lab, and Public Computing Cloud, Renmin University of China.
REFERENCES
Panthadeep Bhattacharjee and Pinaki Mitra. A survey of density based clustering algorithms. Frontiers Comput. Sci., 15(1)151308,, 2021. doi: 10.1007/811704-009900555 URL https
10. //doi.org/10.10000 
//doi
Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V. Chawla. Graph barlow twins: A self-supervised representation learning framework for graphs. Knowl, Based Syst., 256: 109631, 2022, doi:
/t//httss///ooo..r//111.. 00w.0..1166.... knosys 2022
109631
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In AAAI, pp. 3950-3957, 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton. A simple framework for contrastive learning of visual representations. In International Conference on Machine Learning. volume 119, pp. 1597-1607. PMLR, 2020.
Zhixian Chen, Tengfei Ma. and Yang Wang. When does A spectral graph neural network fail in node classification? CoRR, abs/2202.07902, 2022. URL httl:tttss//axiiii www.xxii.rrg/baa..... 07902
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurlPS, pp. 1844-3852, 2016.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic block models. In NeurIPS, 2018
Jacob Devlin, Ming-Wai Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In NAACL-HLT, pp. 4171-4186, 2019.
Chanakya Ekbote, Ajinkya Deshpande, Arun Iyer, Sundararajan Sellamanickam, and Ramakrishna B Bairi. FiGURe: Simple and efficient unsupervised node representations with filter augmentations. In NeurIPS, 2023.
Marco Federici, Anjan Dutta, Patrick Forré, Nate Kushman, and Zeynep Akata. Learning robust representations via multi-view information bottleneck. In International Conference on Learning Representations, 2019.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
10

---

Published as a conference paper at ICLR 2024
Yuan Gao, Xiang Wang, Xiangnan He, Huamin Feng, and Yong-Dong Zhang. Rumor detec- tion with self-super learning on texts and social graph. Frontiers Comput. Sci., 17(4): doi: 10. 10.1007/111744-22-15333 s 111704-02--555
174611, 2023.
URL https://aol.ozg///202
Amur Ghose, Yingxue Zhang, Jianye Hao, and Mark Coates. Spectral augmentations for graph contrastive learning. In International Conference Artificial Intelligence and Statistics, pp. 11213-11266. PMLR, 2023.
Amparo Gil, Javier Segura, and Nico M Temme. Numerical methods for special functions. SIAM, 2007.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NeurlPS, pp. 2672-2680, 2014.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a approach to self-supervised learning. In NeurlPS, 2020.
Yuhe Guo and Zhewei Wei. Graph neural networks with learnable and optimal polynomial bases. In International Conference on Machine Learning, pp. 12077-12097. PMLR, 2023.
Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. In NeurIPS, pp. 5000-5011, 1, 2021.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pp. 4116-4126. PMLR, 2020.
Mingguo He, Zhewei Wei, Zengfeng Huang, and Hongteng Xu. Bernne: Learning arbitrary graph
spectral filters via bernstein approximation. In NewrIPS, 2021.
Mingguo He, Zhewei Wei, and Ji-Rong Wen. Convolutional neural networks graphs with chebyshev approximation, revisited. In NeurlPS, 2022.
R Devon Hjelm, Alex Fedorov, Samuel
Karan Grewal, Phil Bachman, Adam
Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurIPS, 2020.
Runlin Lei, Zhen Wang. Yaliang Li, Bolin Ding, and Zhewei Wei. Evennet: Ignoring odd-hop neighbors improves robustness of graph neural networks. In NeurlPS, 2022.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In NeurIPS, pp. 20887-20902, 2021.
Nian Liu, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei. Revisiting graph contrastive learning from the perspective of graph spectrum. NeurlPS, 2022.
Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent Lee, and Shirui Pan. Beyond smoothing: Unsuper- vised graph representation learning with edge heterophily discriminating. In AAAI, 2023.
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao-Wer Chang, Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification? investigating the homophily principle on node distinguishability.. In NeurIPS, 2023.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In International Conference on Learning Representations, 2022.
Yujie Mo, Liang Peng, Jie Xu, Xiaoshuang Shi, and Xiaofeng Zhu. Simple unsupervised graph representation learning. In AAAI, pp. 7797-7805, 2022.

---

Published as a conference paper at ICLR 2024
Hongbin Pei, Bingzhe Wei, Kevin Chen Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph Representation Learning via Graphical Mutual Information Maximization. In Proceedings of The Web Conference, 2020.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look evaluation of gnns under heterophily: Are really making progress? In International Conference on Learning Representations, 2023.
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. PMLR, 2021.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9())cnabb014 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. International Conference on Learning Representations, 2022.
MTCAJ Thomas and A Thomas Joy. Elements of information theory. Wiley-Interscience, 2006.
Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. Demystifying self-supervised learning: An information-thhorrticc. framework. CoRR, abs/2006.05576, 2020.
URL http:/ttt://// http:::://axxive org/ abs/ 2006. 05576
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep Graph Infomax. In International Conference on Learning Representations, 2019.
Haonan Wang. Jieyu Zhang, Qi Zhu, and Wei Huang. Can single-pass contrastive learning work for both homophilic and heterophilic graph? CORR, abs/2211.10890, 2022. URL https
//doi. www.4450/xx...22111111
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centric, highly- nighly-performant package for graph neural networks. arXiv preprint
2019.
Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self- supervised learning for graphs. In NewrlPS, 2022.
Xuanting Xie, Wenyu Chen, Zhao Kang, and Chong Peng. Contrastive graph clustering with adaptive filter. Expert Systems with Applications, 219: 119:11960 19645, 2023.
Wenhan Yang and Baharan Mirzasoleiman. Contrastive learning under heterophily. CoRR, htt.:ps::/dol..rg/////.. www.448555axxi1 2303. 06344
abs/2303.06344, 2023.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, pp. 40-48. PMLR, 2016.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In NeurlPS, 2020.
Zhe Yuan, Zhewei Wei, Fangrui Lv, and Ji-Rong Wen. Index-free triangle-based graph local clustering. Frontiers Comput. Sei., 18(3):183004 183404, 2024. doi: 10.1007/5111044-2222777 URL
httpp:://dot http:::://ooo.o//10...
1 1011100000017740-22-5--555
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and S Yu Philip. From canonical correlation analysis to self-supervised graph neural networks. In NewrlPS, 2021.
12

---

Published as a conference paper at ICLR 2024
Hengrui Zhang, Qitian Wu, Yu Wang, Shaofeng Zhang, Junchi Yan, and Philip S. Yu. Localized contrastive learning on graphs. CoRR, abs/2212.046044 2022. URL Inttp:::t//s/tt /
48550/arXiv. 2212. 04604
Yizhen Zheng, Shirui Pan, Vincent C. S. Lee, Yu Zheng, and Philip S. Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. In NeurIPS, 2022.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In NeurIPS, 2020a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020b. htt/http://axxx..ooo org abs 2006. 04131
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. In NeurIPS Datasets and Benchmarks, 202
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. Proceedings of the Web Conference 2021, pp. 2069-2080, 2021b.
13

---

Published as a conference paper at ICLR 2024
A ADDITIONAL PROOFS
A.1 PROOF OF COROLLARY
We first introduce Lemma 1 in Lei et al. (2022).
Lemma 1. Lei et al. 2022) For binary node classification task on a k-regular graph 9, let h be edge homophily and X be the i-th smallest eigenvalue of L, then
Σ N -1 a?
-
(5)
The above equaation can be extended to general graphs by replacing the normalized Laplacian L with the unnormalized L.
Based Lemma and Assumption 1
we present the proof of Corollary T
Proof of Corollary
Proof. Denote a (0ro ON aN-1) B 1.0....,BN-1.. On graph 9, note that L(9)
NN
g(A.88
Based on Assumption we suppose each entry of and [
E ((A))
positively correlated in the spectral domain, that is, ag wB; for each i. Thus, for the low-pass filter Flow and the high-pass filter ghigh the SRLs between the normalized a and g are:
N-1
Liow (9)= =2
1 Tiow
Σ
(N)(oo)
(6)
Lhigh (9) = T Thigh
where Tippe 2
EN- Itype (A.) Observing equation and equation
we first give
the upper bound T type as inequality
VN
N
Itupe (A:) cVN VN
cN
T type
(8)
2
2
==0
Note that "<" in inequality 8 comes from the bounded restriction g(A) E [0. c). Therefore, there is an upper bound of Loow(W) as shown inequality 9
Ltgpe (9) 2 Teype
Σ af (Ni)eee
N
2
< 2
cN
=2 Lr.
(9)
Consider minimizing the upper bound of Leypes that is. just maximizing L,, Below we will explain that it is necessary use corresponding low-pac www-pas/hhigh-gg pass filtering functions for graphs with ho- mophily/heteroohilly Note that for L,, V (ΣNY of (d)(()))pp)) iggnorin the constant coefficient, it is essentially a convex combination of g(A))cypes where Σ of N (See Lemma 4 in Lei et al. (222)))
. Case h + 0. This case corresponds to the strong heterophily situation. According to Lemma and EN-1 X, tr(ī)= N, have equation 10
a 2N h).
(10)
2=0
14

---

Published as a conference paper at ICLR 2024
Also coupled with Av-1 I 2, we have inequality 11
N-1
N-1
Σ
AN-
i=0
i=U
N-1 Σ
AN-1
S 2N.
(11)
Therefore Ex- a²A, has an upper bound 2N, When + O, the value close to the upper bound. At this time, the corresponding situation is exactly that the larger A allocated more a², that is, X; and a? have the same monotonicity (both are non non-decreasing)
The above proves that at has a non-decreasing monotonicity in the case of heterophily. In order to maximize Le (the convex combination of (AA)ttyp)) a larger g(A:) value should be assigned to larger af, so it is reasonable for the filter function g to be a high-pass. filter g(A:)
Case h + 1. The idea is similar to Case / + O, but the process is opposite (note that Eiso of A; - 0 at this time). It can be deduced that for homophily graphs, the filter function g is expected be a low-pass filter g(Ai)tow-
Based on the analysis the above two cases, we complete the proof.
A.2 PROOF OF THEOREM I
Proof. Below we consider proving that the linear combination low-pass filtering and high-pass filtering helps to achieve lower SRL..
First, consider the linear combination of low-pass and high-pass filter functions as equation 12
g(Ai)joina zg(Ax)low + vg
(12)
where x > y, > 0, + y = 1 are linear weighting coefficients. Then the corresponding SRL is
defined as equation 13
Ljoine (S) =2 (
1
Σ afg(>)) (e)(())joone)
T Troint
2
Σ a (zg(Ai)low + vo(A))igh)))
(13)
Toint
where Tjoint
J/N 2
N Σ ==
(xg (X:)ow + (g())))nna))) )²² aa
According to equation the upper bound of SRL. I(()) is i(() 2- L.,, so the expectation of the upper bound SRL is determined by [[L,], ignoring the constant coefficients in Lt, and for the random variable (Ax,, consider the expectation form of equation [4] the linear combination filter function gjoint (where the variable æ obeys uniform distribution, L.c., x (O, 1)):
Eg [a² (A)) = Ez (xzg()) (A) + (A))nn)))))
E, (2x 1)lE(a" (a0l(""((0 Aoow + c(1 -x)]
(2.r 1)TE(a 2 g 2oom +c(1 -x)dx
(14)
2
15

---

Published as a conference paper at ICLR 2024
In addition, for the low-pass filter Flow, consider its expected form equation 15
Ela g(A)o())
Elaa(c
2 X)]
c
= c "a[a">] X]
C
2
2 2(1 - h)
2
ch.
(15)
Note that the second "=" to the third "=" in equation 15 applies the conclusion of Lemma namely B|a²>] = 2(1 h). For the heterophilic graph with h ~ U ( 1), that is, h is uniformly distributed
I
on 1 1], we have inequality 16 as follows:
Ex [a² ((²)(A)) joiine
2
edh
h=
chdh
h=
E2 [hc]
En (a (A)iow).
(16)
Since the expected upper bound of SRL EJi} heterophilic settings where ~ ( 1), the linear combination of low-pass and high-pass filters guarantees a lower expected SRL. upper bound compared with utilizing the low-pass information only, that is, Eg [Ljoine]] < EE, [Loow], (0, 1), U 1). the proof is completed.
E[L.] - [aaa"g())], Therefore in
Additional results: Above consider the expected SRL upper bound for the heterophilic graphs, which calculates E[L] when (O, U 1). Generally, we assume the homophily degree h is uniformly distributed in [0, 1]. Similar to equation 15 the expectation form of high- pass filter
ghigh can be derived as equation 17
Ela² Bl("g(A))a gA)hnigh)
El(2 [
C B[aa>>] A]
2
2(1 h)
c(1 h))
(17)
In order to minimize the expected upper bound of SRL L, we only need to maximize E, [()]]
Based on equation] 17 we can easily draw the following conclusions:
1. For low-pass filtering, max,, E, ja (A) max, he, when h - 1, the expected upper bound of SRL will be minimized, which exactly reveals that low-pass filtering corresponds to homophilic graph; Likewise, for high-pass filtering max;, Ea " gA))sigh) max, (1 h)c, when - 0, the expected upper bound of SRL f. will be minimized, verifying that high-pass filtering corresponds to the heterophilic graphs.
2. Considering that E,, graph itself. In addition, consider the weighting coefficient x the linear combination can be set to learnable parameter during model training. Both of them reflect that linearly combining tow-pass and high- pass filtering enjoys better generalization across different homophily levels with a theoretical guarantee.
joine] = S. it is irrelevant to the homophily degree of the
(0, 1) in the above derivation. However, in fact,
16

---

Published as a conference paper at ICLR 2024
A.3 PROOF OF PROPOSITION
!
In this section, before the proof of Proposition 1 we first present Lemma which is used in DGI (Veličković al. 2019);
[2] 1== be a set of node representations drawn from an empirical probability distribution of graphs, p(Z), with finite number of elements, [Z], such that p(Z(k) (k) vk, K. Let R(.)) be a deterministic readout function on graphs and g(
Lemma 2. Vellčkoviić et al. 2019 Let [
(k) be the summary vector of the k-th graph, with marginal distribution p(g). The optimal classifier between the joint distribution p(Z, g) and the product of marginals p(Z)p(g), assuming class balance, has an error rate upper bounded by Err" = ΣE p(g(t))2 This upper bound is achieved if R is injective.
Then we claim that although our objective considers the high-pass and low-pass components simulta- neously, the DGI loss still serves upper bound for objective maximization.
Proof of Proposition
1
Proof. Formally, we rewrite our BCE loss as follows:
LECE
1
Σ log D (Z),g) g) log (1 - ()-())))))) +log D (Zir.g) log (1 11-D( DD
( (Z 8)
4N
1
Σ
N
log D (Z) g) D (Z + log ( (i)(()))))
D (Z (1- 8))
4N
log D (Zz, Zzz g) + log (1 (1 (1- 2in 8)
= LDGL
2N
where D (Z f1 8)
V D (Z g) D (Zz, B) E (0, and the above inequality can be de-
duced from the basic inequality.
Considering that the final embeddings Z aZ, 3Z as linear combination of Z, and Zμ, know that can represent Zμ and Zμ (a = 1,, = 0 or a = 0, = 1, respectively), then rewrite D (Z), Z g) as D g), where g = R (Z).
Thus we obtain that the upper bound for LBCE has the form of:
log D [Z. g) log (1-1(Z.g))
2N
which is the same as the objective in DGI. As we want maximize LECE for optimization, it is quite effective to maximize the DGI lower bound; thus, our objective also follows Lemma
A.4 PROOF OF THEOREM 2
We first introduce Corollary 1 and Theorem 3 Veličković et al. (2019):
Corollary 1. (Veličković et al. 2019) From now on, assume that the readout function used, R, is injective. Assume the number of allowable states in the space g. ig), greater than or equal to [Z]. Then, for g", the optimal summary under the classification error an optimal classifier between the joint and the product of marginals, it holds that Ig"l |Z].
Theorem 3. (Veličković et al. 2019) Define g* as the optimal summary vector under the classifica- tion error of an optimal classifer between p(Z.g, g) and pl p(Z))(().. g" arg max MI(Z: g). where MI stands for mutual information.
Based on Theorem in DGI, they claim that for finite input sets and appropriate deterministic functions, minimizing the classification error in the discriminator (()) can be used to maximize the MI between the input and output of R(.). Further, based on Corollary we obtain Theorem
17

---

Published as a conference paper at ICLR 2024
Proof of Theorem 2
Proof. Given our assumption of |Z| = g) there exists an inverse 2, (g) and therefore h (R) g h and (&g a RR-1 mapping g to h!"
EØ (R (g)), i.. there exists deterministic functions (E cJ oR- mapping
Considering that h Linear(h , based on the fact that the linear combina- tion is an invertible function, it is easy to derive that there exists deterministic function Linear o , 2) mapping g to h
The optimal classifier between the joint distribution p(h; .g) and the product of marginals ((h,"))((g then, by Lemma 2 has an error rate upper bound of Err* Σ p(h,00)2 There- fore, as stated Corollary 1 for the optimal h. | Zd|- This result, following the same arguments in Theorem maximizes the mutual information between the neighborhood and high-level features, MI(Z) h(99).
A.5 CONNECTING EQUATION WITH JS DIVERGENCE
In this section, we further prove that maximize ΛECE not only maximize MI (8) ho99) shown in Theorem 2 but also maximize the censen-Shannon divergence between the positive and negative distributions in both low pass and high pass views. The following proof inspired by the theoretical proof in Goodfellow et al. (2014) and Zheng et al. (2022).
Proof. Note that for the summary vector, we have:
g E(Z) (Z( + (B((2)) = 0Z2 + 82H,
which implies that g is fixed when considering the deterministic encoders in terms of the expectations of certain distributions, namely PL and Ри- Therefore, we disregard to streamline the subsequent derivation.
During training, we maximize optimize the following objective in equation 18
BBE = Bu. log (D (zz)) + E Pr log (1 - D (zz))
pgo log (D (z=)) E Pgee paey log
(zz))
(zr.) ph (Zt. log (D (zr.) dzr. + / (z1) log (1 D (zz.) dzr.
(18)
22,
[ PRos (Z4) log (D (ZH)) dz
parg (z log (1 D (211) dzz:
where phee and phe are the distributions of positive embeddings for the low-pass and high- nigh-pass encoder respectively, pheg and paeg are the distributions of negative embeddings. As our objective
here is to maximize LECE. and Poss (z) > 0; Pneg (z) > O, we can obtain the optimal solution for
D (z) is
(2)+ [z) This is because for any (a, TR2 ( 0), the maximum of the function = a log(( (r) + log(1 x) is achieved at o+3 (Goodfellow et al. 2014). By replacing D (z) with Ppne(e) (z)
(2)
Poo (x) in equation 18 we obtain equation
ppos
(ZL)
phce (zL)
LBCE = E2, ~ pena log
+ E Pgoo log
pppe
(zt,)
Peeg (ZL)
Ppos (zz.) + Paeg (ZL.
ppos
(ZH)
p (ZH)
Bay ~ pron log
+ Eng log
poos
(zH)
Pang
(ZH)
ppos
(7
pang (2
(19)
From equation 19 distributions P, and Pz, defined as equation 20)
can it looks similar to the Jensen-Shannon divergence between two
Ps P.+P5
JS(P: || Pa)
1 Ep log(
PIPPs
En loog(
(20)
2
2
2
18

---

Published as a conference paper at ICLR 2024
Thus, can plug in equation 20 into equation 19 to obtain equation 21
P. (3g
(zg (
PL (81. (81)) + PL. (2L.
Pl. (2t. 1-1)-Pp Pi. (8t)
LBCE P log
Ppes log
2 log 2
2
2
P (2H
P (xx)
(xH M+ PRes (xx (
P1 (xH 1+ PRE (2x) (xH)
+ Exn ~ppo pgra log
E Paep log
log 2,
2JS (Pim
P) + 2JS (PM || PH 4 log
(21)
where we can see maximizing LEE is the same as maximizing JS (PL e JS ( [PHr* (H at the same time. Thus, by optimizing LBC, Poos and Pney tend to be pulled apart and separated in terms of the low-pass view PL and high-pass view Pи.
PT and
A.6 PROOF OF COROLLARY
In this section, we first present the connection between the proposed objective and the mutual information maximization, then show that the learned representations by our objective provably enjoy good downstream performance.
We denote the random variable the input graph as 9 and the downstream label as y. For elarity, we omit subscript in what follows. In POLYGCI, we have two self-superviser signals: the low-pass information inferred by zı and the high-pass information zи. We can formulate zy. z from the local structural perspective, which is captured by the representations of the neighbors zr, = {z- by (v)), 2н = {x. lu; [()) of node v. Then we interpret our objective in equation $ from the information maximization perspective (Tsai et al. 2020) shown in Theorem
Theorem 4. Optimizing local and global terms in equation 4 is equivalent maximizing the mutual information between the representation and the joint distribution of low-pass and high-pass representations, denoted (zz, (z),ZH)). Let I(::-) be the mutual information. Formally, we have:
max = max I (h; 28.
(22)
Proof. As z Linear (ZL, zH), according to Theorem 2 and the data processing inequality (Thomas & Joy 2006), we have:
I(h; 1h; ZL) [(h; Linear(Zn 21)) I(h; z).
Thus maximize ΣBCE is equivalent to maximize the lower bound of / [h: zH. zt), which proves max &BCE + maxp / (h; ZH, Z1).
To prove Corollary 2. we first introduce Lemma 3 and Theorem 5
Lemma 3. For representation h that is obtained with deterministic encoder fo of input graph 9 with enough capacity, we have the data processing Markov chain: (z,,, Zn) y 9 +hh.
Proof. Since h f9( is deterministic function of input graph we have the following condi- tional independence: (Zz, Z 1 h and y 1 h/S (Federici et al. 2019), which leads to the data processing Markov chain (Zz, ZH) + y + 9 - h. Thus, the proof is completed.
Based on Lemma B 5 why the downstream tasks can benefit from the representations learned by our objective function.
Theorem 5. Let hags arg max [h; ZL, ZH), hlow arg maxp I [h; zi), and hnigh arg max, (h: 2.). Formally, we have the following inequalities about the task-relevant infor- mation:
I(9:)) max ((hy)) 2 I(bagg:y) y) maxo]( v), (hiighy))
(23)
19

---

B GENERALIZATION OF THEOREM Published as a conference paper at ICLR 2024
Proof. We have the data processing inequality (Thomas & Joy 2006) as inequality 24
(( 2 (h, [zz, zH: 9) 2 [(Z zH; h), 1 [ZL, zH: 9: z Z
zHi h
(24)
Since hagg
arg maxK / (zz, Zz: h), TizL ZH; Y) = I(ZL. Zz; y) In addition, as hagg is deterministic given æ, zHz we also have, 0 S haggg y L zz H bagg LL, 2n) O, where H()) denotes the entropy. Given the
have: [(2L, ZH bagg)
[ Z 9) and
above, we have equation 25
T(hagzi y) (( 2 T(haggi i Viz,, 21r)
-[9;y;2t, Z1r) + [haagi y (1,, kH)
I(S:y; 2H) +
-[(S:y) - y |L. 2,1)
max / (h; y) )) [(;; (2,, (1) (haupiy) I(:: 2r, zn).
(25)
Thus, the mutual information gap between self-supervised representation hags and supervised representation houp is 7(9: y zz, 7n)) 2 0. Based on the property of mutual information, we further have inequality 26
I(:
19: ZH kr. + yZz zH) 2 (9: 2L, zH)
(26)
Similarly, we have ( 2H) I(9: 1zz, 2.). Coupled with equation 25 and equation 26
have I y 2 [hhoww y) and I (hagg' 2 I y(aighh) which completes the proof.
Based on Theorem we further prove Corollary 2
Proof of Corollary
Proof. Suppose the Bayes error S Pr S 1 Ma which means classification on the learned embedding is better than random guessing. We utilize inequalities 27 borrowed from Thomas & Joy (2006) and Tsai al. (2020):
P Bags
I log(11 - P S (y hagg). Hyyhhuup) I log + P log M.
(27)
For H (y) hagg) and H (ssp) we have equation 28:
Hy (yyy)agg) H (haggi y)
(y) - I (hsupi y) [(:: ZH)
(y/hsup)) + y ZH)
(28)
where we use equation 25 in the second equality. Combining inequality 27 and equation 28 we have the error upper bound for hagg as sup(P% in inequality 29
D S log 2 Ph -log M T(9: 2L, 2n) - sup Phinee
(29)
Further using 19:y
LL, ZH) < I(S:y/zL) and I(:: [(: y/zz, zH) S I(9: shown in equa-
tion 26 we have sup ( min suu Pr Ph sup P (hisiih) )). which completes the proof.
As for the generalized version of Theorem we first introduce the generalized version of Lemmal borrowed from Lei et al. (2022).
2022) Given the unnormalized graph Laplacian L U and its eigenvalues {X2 denote the number of edges on the graph is m, and label difference as Ay = yo y1 E RNx1, For the unnormalized spectrum of label difference on L, denoted as a'
Lemma 4. Lei
U, Ay (06, a4 oh....,, d have:
N-1
Σ (a/)2X)
Σ
X 2m, 1 - h
(30)
N-1 X1
20

---

Published as a conference paper at ICLR 2024
Based Lemma following the proof sketch of Theorem it can be easily proved that Theorem still holds for the unnormalized graph Laplacian L as generalized version, shown in Theorem 6
Theorem 6. (generalized version of Theorem on unnormalized Laplacian L ) For binary node classification task on graph S with n nodes and m edges, we consider the linear bounded filter function and the unnormalized Laplacian L with X 0, 0. the low-pass filter Doo c- 3mm the high-puss filter as fhigh. = nc X, then a linear combination of the low-pass and high-pass filter 3m
nc X and
achieves lower expected SRL upper bound than Nlow in heterophilic settings, that is, Eg joind I E, [Low for x ~ U),,1), U(2, 1), where L denotes the upper bound for L.
Ijoint zglow + y9high. x 2 0, 0, x +
Proof of Theorem
Proof. According to equation 9 the upper bound of SRL L(9) is L(9) 2 Lt, so the expectation
of the upper bound of SRL determined by E[ igmoring the constant coefficients in Lt, and for the consider the expectation form of equation for the linear combination
random variable (X)( filter function gjoint (where the variable x obeys uniform distribution, i.e., x ~ UO, 1)):
Ex [ax(((())) joint))
[a² (rg( X
X))oww Now ug( (9(X')nigh)
Ex (2x 1)1E(a g )ow! I + c(1-x))
(2x 1)EEa (egla"g(X1 (Xm) +c(1 -x)xx
x=
(31)
In addition, for the low-pass filter Nlow, consider its expected form as equation 32
E Eia²g( (2X = E[a²
nc X)]
4m
nc BB(221 X
4m
nc 4m
c 4m n
(1 h)
ch.
(32)
Note that the second "=" to the third "=" in equation 32 applies the conclusion of Lemma namely E[a²X]] 4m (1 h). For the heterophilic graph with h U(2 1), that is, h is uniformly distributed n
on [2 1), we have inequality 33 as follows:
Eg [a (() joine] c
odh
h=}
chdh
h=
EA [hc]
E, |a gXX))
(33)
Since the expected upper bound of SRI. B(i] = 2 B[L.)] = 2 2- 2 Therefore in heterophilic settings where h ~ U$, 1). the linear combination of low-pass and high-pass filters guarantees a lower expected SRL upper bound compared with utilizing the low-pass information only, that is, E2 [[joine]] < E. [[oow) ~ U(0, 1), ~ U 1), the proof is completed.
Note that the slight difference between Theorem T and Theorem 6 lies in the constant coefficients of ne respectively. addition, Theorem the low-passe www-paas//hhhhppae passsppssssss linear functions, which are 2 and 4y gets rid of the k-regular restriction in Theorem by introducing the unnormalized graph Laplacian
As for the binary classification task in Theorem there is series works based on spectral analysis of heterophily that adopt the two-class setting( (eaiingggeeiii al. 2022 Chen al. 2022 Ma et al. 2022
21

---

Published as a conference paper at ICLR 2024
Luan et al. 2023). Besides, the theoretical analysis in Chen et al. (2022) states that the analysis of multi-class cases can be simplified via the "One vs Others" reduction, that is, for C' class classification
task, denoting yá = and v = > thus we can transform the multi-class cases into binary classification.
Based on the above discussion, Theorem I makes reasonable simplifications and has the potential to be extended to general form of graph Laplacian multi-class classification cases, which demonstrate the necessity of introducing high-pass information in heterophilic settings.
C DETAILS OF EXPERIMENTS
C.1 SYNTHETIC DATASETS
C.1.1 GENERATION PROCESS OF CSBM
In order to generate a graph with varying degrees of homophily, we follow Chien et al. 2022 1 to generate cSBM datasets. Denote a cSBM graph 9 as 9 ~ cSBM(n, A, p), where n is the number of nodes, f is the dimension of features, and À and Jı are hyperparameters controlling the proportion of contributions from the graph structure and node features respectively. We partition nodes into two classes of equal size 2) and assign each node f-dimensional feature vector which is randomly sampled from a class-specific Gaussian distribution as:
Z
Vf where ys {-1,+11 denotes the label of node Us N(0,, I/f) and Z is random noise term.
I;
you +
(34)
Assume the average degree of the generated graph is d, and the adjacency matrix of the generated cSBM graph is defined
d+Ava
if ffeg > 0
F|Aij =
(35)
Avdd 72
otherwise.
To control the homophily degree h of the generated graphs, the parameter T is introduced in the form AvE where & is control factor defined as & = 7. The degree of homophily in the graph is determined by the parameter & E [-11, 1). where a larger |사] value indicates that the graph provides stronger topological information. On the other hand, when are informative for prediction. It is noteworthy that the closer é approaches 1, the more homophilic the graph is, and conversely, if O, the graph tends exhibit heterophily.
of Φ 2 ā arctan
0, only node features
To generate informative cSBM graphs, we need to satisfy the condition X + -² 11+e where e >> 0 (Dehpaanee et al.) 2018). In practice, we choose n 5000, f = 2000, d = 5, c 3.25 for all graphs. The choices and μ and the resulting homophily ratio and number of edges |E] are listed in Table 5
Table 5: Statistics of cSBM datasets.
-1
-0.75
-0.50
-0.25
0
0.25
0.50
0.75
1
X -2.06
-1.90
-1.46
-0.79
0.00
0.79
1.46
1.90
2.06
p
2.00
1.25
2.30
3.01
3.26
3.01
2.30
1.25
2.00
E''
25,058
25.134
25,390
25,140
24,872
25,024
24,866
25,382
25,038
h 0.036
0.072
0.171
0.322
0.503
0.677
0.825
0.925
0.960
C.1.2
JUSTIFICATION FOR ASSUMPTION
Justification. The widely used graph generative model, contextual stochastic block model (cSBM) naturally adheres Assumption [ while generating graphs with different homophily levels. Specif-
22

---

Published as a conference paper at ICLR 2024
ically, cSBM generates node features and edges independently via equation 34 and equation 35 respectively. As shown in equation 34] it is exactly a linear correlation between node label y/ and feature 24, which also can be extended to the spectral domain by left multiplying U While taking
expectations at the same time, we demonstrate that the generation mechanism of cSBM is consistent with Assumption and further reflect the rationality of Assumption T
C.2 WORLD DATASETS
We introduce the details of the real-world datasets as follows. and the statistics of them are shown in T
Cora, Citeseer and Pubmed (Sen et al. 2008 are three citation networks that are considered classic homophilic graphs. In these graphs, nodes represent papers and edges represent citation relationships between two papers. The features consist of bag-of-word representations of the papers, while the labels indicate the research topic of each paper.
Cornell, Texas and viscosin (Pei et al. 2020) are three heterophilic networks originating from the Webjeeprroecct, where nodes are web pages of the computer science departments of different universities and edges are hyperlinks between them. The features of
each page are represented as lag-of-words. and the labels indicate the types of web pages.
Chameleon and Squirrel (Pei et al.) (020) are two heterophilic networks based on Wikipedia. The nodes denote web pages in Wikipedia and edges denote links between them. The features consist of informative nouns the Wikipedia pages, and labels indicate the average traffic of the web pages.
Actor (Pei et al. 2020) is an actor co-occurrence network where nodes denote actors and edges indicate two actors have co-occurrence in the same movie. The features indicate the keywords in the Wikipedia pages, and the labels are the words of corresponding actors. It is a typical heterophilic graph.
Roman empi re, Anazon rat ragings, Kinesweepex Tolokers and Questions (Platonov et al. (023) are 5 large heterophilic graphs with different structural properties and from different fields. They are proposed to ease the problem of existing heterophilic graphs e.g., there are a large number of duplicate nodes in Chame leon and Squirrel, leading to training and test data leakage.
arXiv-year (Lim al. 2021 is the ogbn-arXiv (Hu et al. 2020 network with different labels, that is, set the class labels to be the year that the paper is posted instead of the paper subject area and balance the class ratios approximately. considered as typical large heterophilic graph.
D BASELINES
We summarize the baseline methods based on their optimization objectives as follows.
Binary Cross Cross-Entropp Entropy (BCE) loss. Inspired by Deep Infomax (Hjelm et al. 2019) in computer vision, DGI (Veličković et al. 2019) contrasts the node embeddings with the global summary with JSD estimator and BCE loss. To extend the idea of DGI, MVGRL (Hassani & Khasahmadi 2020) introduces multi-view contrastiveness with diffusion augmentation, and GMI (Peng et al. 2020) focuses on local scope with the first-order neighborhood. Further, GGD (Zheng et al. 2022) simplifies the discriminator in DGI and proposes the group discrimination objective based on BCE loss achieve effective and efficient learning.
InfoNCE loss. GRACE (Zhu et al. 2020b) performs contrastive learning on two augmented views including the feature masking and edge dropout with an InfoNCE objective. GCA (Zhu et al., al.]| (221b) improves the performance of GRACE by introducing adaptive augmentation techniques to capture the important features and structural information. GraphCL (You et al. 2020) considers the combination of multiple augmentations to diversify the augmented views.
GREET (Liu et al. 2023) proposes an edge heterophily discriminating mechanism based
http: cmu
cmu. http:///ww.eeeeooooeee////////e/
11 www/wwwb.
23

---

Published as a conference paper at ICLR 2024
Table 6: Statistics of real-world datasets.
Dataset
Num. of nodes
Num. of edges
Features
Classes
Homophily
Cora
2,708
5,278
1,433
7
0.810
Citeseer
3,327
4,552
3,703
6
0.736
Pubmed
19,717
44,324
500
3
0,802
Cornell
183
298
1,703
5
0.305
Texas
183
325
1,703
0.108 5
Wisconsin
251
515
1,703
0.196 5
Chameleon
2,277
36,101
2,277
0.235 5
Squirrel
5.201
217,073
2,089
5
0,224
Actor
7,600
30,019
932
0,219 5
Roman-empire
22.622
65,854
300
18
0,047
Amazon-ratings
24,492
186,100
300
5
0.380
Minesweeper
10,000
78,804
0.683 2
Tolokers
11,758
1,038,000
10
0,595 2
Questions
48,921
307,080
301
2
0.840
arXiv-year
169,343
1,166,243
128
5
0.222
on the InfoNCE objective to achieve effective Graph Contrastive Learning on heterophilic graphs.
Invariance-keeping loss. BGRL (Takkoor et al. 2022) adopts a bootstrapping scheme inspired by BYOL (Grill al. 2020). which only contrasts node embeddings between the output of the online network and the corresponding target network, thus achieving begative-sample free. GBT (Bielak et al. 2022) utilizes tross-correlation-bie based on the redundancy connudancy-reucttion principle to build contrastiveness between embedding dimensions. CCA-SSG (Zhang al. 2021) further considers optimizing feature-level objective inspired by classical Canonical Correlation Analysis to capture the invariance between augmented views effectively.
loss
Besides, also summarize the existing GCL methods from the augmentation techniques and the space complexity Table
Table 7: Technical comparison of the representative GCL methods regarding data augmentation and space complexity, where N, E, and D denote the number of nodes, edges, and the size of the output embeddings, respectively. Diffusion denotes graph diffusion Personalized PageRank or heat kernel. Multiple denotes multiple augmentation methods, including edge removing, edge adding, node dropping, and subgraph induced by random walks. "/" indicates that no such augmentation exists. (Here we consider the node shuffling strategy the corruption technique but not for data augmentation.)
Method
Topology Aug.
Feature Aug.
Space. O(N)
DGI (Veličković et al. 2019
MVGRL (Hassami Khasahmadi
2020
Diffusson
O(N)
GMI (Peng et al. 2020)
O(N + F
GGD (Zeng al.
2022
O(N)
GRACE (Zhu et al.
2020b
Edge Removing
Feature Masking
(
GCA (Zhu al.
2021b
Edge Removing
Feature Masking
O(N2)
GraphCI. You et al.
2020)
Multiple
Feature Dropout
O(N2)
GREET (Liu
al. 2023
Edge Removing
Feature Masking
O(N2)
BGRL (hakoor et al.
2022
Edge Removing
Feature Masking
O(N)
GBT (iclak al. 2022
Edge Removing
Feature Masking
O(N)
(Zhang ct al. 2021
Edge Removing
Feature Masking
O(D*)
24

---

Published as a conference paper at ICLR 2024
E SUPPLEMENT RELATED WORK
There is series of works on Graph Contrastive Learning with heterophily. HLCL (Yang & Mirza solciman 2023) employs fixed set of polynomials (i.e., A and L represent the low-pass/high pass filters respectively) to generate spectral views for further contrast, while similar ideas are also used in graph clustering (Xie et al. 2023) and supervised settings (Bo et al. 202T]. Furthermore, FiGURe (Ek) bote et al. 2023). which focuses self-supervised learning tasks on heterophilic graphs and involves filter augmentations, performs contrastive learning in different spectral views generated by filter banks. Motivated by the spectral contrastive loss proposed by HaoChen et al. (202T). SP-GCL (Wang) et al.; 2022) conducts contrastive learning based on the transformed graphs constructed by the output embeddings instead of the original graphs, thus achieving effective learning graphs of different homophily levels. Additionally, Local-GCI. (Zhang et al. 2022) devises kernelized contrastive loss with linear complexity for GCL,, which also shows effectiveness in heterophilic graphs.
There are also GCL methods using spectral augmentations. Ghose et al. (2023) proposes a set of well-motivated graph transformation operations derived via graph spectral analysis, which are spectral graph cropping and graph frequency components reordering. SpCo (Liu et al. (2022) studies the necessity of high- fighffreuenccy information GCL and learns the optimal augmentation from the spectral view.
Compared with the above, POLYGCL does require specially designed or complex preprocessing steps for spectrum augmentations but achieves the contrast between low-pass and high-pass infor- mation by directly optimizing the corresponding decoupled filters. In this way, POLYGCL has the ability to learn filters of any shape in self-supervised learning, which ensures its expressiveness to address GCL with heterophily. Besides, these works related to the graph spectrum mainly focused on the analysis of eigenvalues while POLYGCL cares more about the learning of filter functions adapt to homoophilc/heetrophiiic settings.
In summary, to the best of our knowledge, POLYGCL is the first to achieve efficient learning of low-pass and high-pass filters via polynomial approximation a self-supervised setting.
F IMPLEMENTATION DETAILS
F. EXPERIMENTAL DEVICE
We conduct all the experiments on machine with an NVIDIA A100 80GB PCIe, Intel Xeon CPU (2.20 GHz) with 40 cores, and 512 GB RAM.
F.2 MODEL ARCUITECTURES
refer to official code to implement the baseline models with the help of PyTorch Geomet-
Fic & Lenssen 2019), DGL (Wang et al. 2019) and PyGCL (Zhu et al. 2021a) libraries. The
URL and commit number are presented Table g
Table Codes & commit numbers.
URL
Commit
DGI
sttps: /gbthub www/Petate/eeeeooooooooeeeeeeeee arV
/DGI
61baf67
MVGRL
/mvrr
628ed2b
GMI
hctpa:/ //ttt///ttttbb com/ spang /GM
3491e8c
GGD
https:/ http::////ttub... com/
2V215est peyres Liharolyhhaaaga craph wre.pph---ruuppaee www.p-discciminntiioo
7cf72db
GRACE
https: http::///qooo thu.guutuuu..... com RRC- 070SACE
51h4496
GCA
https::/qithn
CRTPAC- hTC/CA
GraphCL
htEps://g www.tggtttouo..o. Con. Shen Laby arane
a0c8c97
GREET
GELDS 3003:///sshue com/ com.yyxx.... 1023 37GG2
8bcc940
BGRL
ht:
60PF11
GBT
hELps: githab. com/ aobeeak// qraph bar aarlew twins
ec62580
CCA-SSC
https::/gittn com/ wtt.:/ennnnuaaggguuuur
cea6e73
25

---

Published as a conference paper at ICLR 2024
Table Details of the hyper-parameters tuned by grid search on cSBM datasets.
Ø
Ir
wd
Irl
wdl
Ir alpha
activation
initial low value
initial high value
range
le-2
0.0
5e-3
le-6
le-2
ReLU
2
0.75
le-2
0.0
le-3
0.0
le-2
ReLU
2
0.5
le-2
0.0
le-3
0.0
le-2
ReLU
2
4
-0.5
le-2
0.0
le-3
0.0
le-2
ReLU
2
4
le-2
0.0
le-4
0.0
5e-3
PReLUU
4
0.25
le-4
0.0
Se-3
ReLU
4
0.5
lc-2
0.0
le-3
0.0
lc-2
ReLU
2
0.75
1e-2
0.0
le-3
0.0
le-2
ReLU
2
2
1e-2
0.0
le-3
0.0
le-2
ReLU
2
2
Table 10: Details of the hyper-parameters tuned by grid search on real-world datasets.
Dataset
wdl
epochs
patience
dprate
dropout
activation
batch norm
Cora
5e-4
le-3
2e-3
0.0
500
20
0.3
0.3
ReLUU
False
Citeseer
le.4
0.0
Se-4
0.0
1,000
20
0.2
0.3
ReLU
False
Pubmed
1c-4
lc-3
lc-3
1,000
20
0.0
PReLU
Truc
Cornell
lc-4
0.0
le-3
0.0
500
20
0.8
0.5
ReLU
False
5e-3
le-3
0.0
500
20
0.4
0.5
ReLU
False
Wisconsin
lc-4
0.0
le-3
0.0
500
20
0.1
0.7
PReLU
Truc
Chameleon
le-3
0.0
le-3
0.0
1,000
50
0.3
0.2
PReLU
True
Squirrel
le-3
0.0
le-3
0.0
500
20
0.2
0.0
PReLU
True
Actor
le-2
0.0
le-3
0.0
500
20
0.2
0.3
ReLU
False
Romaz-empire
le.4
0.0
500
20
0.5
ReLU
False
Amazon-ratings
5e-3
0.0
500
20
0.4
ReLU
False
Mi Minesweaper
le.4
0.0
le-3
0.0
500
20
0.4
0.1
ReLU
False
Tolokers
le-2
0.0
lo-3
0.0
500
20
0.6
0.4
PRcLU
True
Questions
le-3 0.0
le-3
0.0
500
20
0.1
0.2
ReLU
False
Table 11: Details of the hyper-parameters tuned by grid search on arXiv-year.
Dataset
Irl
wd1
epochs
patience
dprate
dropout
activation
batch norm
srXiv-year
le-3
le-3
0.0
1,000
20
0.5
0.5
ReLU
False
F.3 HYPERPARAMETER SETTINGS.
Note that for the downstream node classification tasks based on the learned embeddings, we set embedding size for all models as the same and fix the learning rate l2 0.01 and weight decay W2 0.0 at the second MLP stage for fair comparison.
Experiments on the synthetic datasets. On the cSBM datasets, we test the performance of the regularized variant of POLYGCL to satisfy the condition in Theorem [ with the constraint + 3 1, a 2 0, 3 2 In our experiments, we utilize the sigmoid activation function to satisfy the above constraint. In addition, for fixed parameters, we set the order of polynomials K 10, the output embedding size D 512, and the early stopping patience the training process as 20. The other hyperparameters listed in Table where parameters "initial low value". "initial high value". and "range" are utilized for the initialization the low www.paassshhppaeeee filters.
Experiments on the real-world datasets. On real-world datasets, we choose the order of polynomials K 10 and the output embedding size D = 512. Table [0ble shows the other parameters tuned by grid search, and it is noted that for sinesw, Tolokers, and Questions, we adopt ROC AUC as the evaluation metric following Platonov et al. (2023). Furthermore, in Table [I] we conduct the self-supervised node classification task on arXiv arXiv-year with 5 fixed 50/25/25 train/val/test splits as introduced in Lim et al. (2021). We choose D 256 for POLYGCL and other baselines in arXiv-year to address the OOM issue that arises with most baselines when D is set 512.
26

---

Published as a conference paper at ICLR 2024
G ADDITIONAL EXPERIMENTAL RESULTS
G.1 ADDITIONAL BASELINES: GCL WITH HETEROPHILY
We include two new baselines, namely SP-GCL (Wang et al. 2022) and HLCL (Yang & Mirza soleiman, 2023) for further comparison, which are GCLs that address heterophily. We conduct experiments on both synthetic and real-world datasets. The results are summarized in Table [2 Table 13, and Table [4] Specifically, shown in Table [2]] although claimed to tackle heterophily, these two methods still suffer from performance drop in extreme heterophilic cSBM settings when ø approaches -1. In contrast, POLYGC! consistently holds superior performance over the two new baselines on both synthetic and real-world datasets.
Table 12: Mean node classification accuracy (%) with 95% confidence interval on cSBM graphs compared with additional baselines.
Methods
0.75
0.5
4
0.25
0 0
@ - 0.25
@ 0.5
0.75
SP-OCL
21.0
73.19
+0.00
20.20
to
59.36 +0.0e
73.01 iect
94.13 20.00
40.40
HLCL
66.03 20:45
67.66
10.0
70.62
2044
60.80
10
38
20.77
65.80
79.25 10.99
97. 10.50
93.07
10:40
POLYGCL
20.17
:a.1
20.00
2:.
88.22 20:2
98.09 24.29
99.29 =033
Table 13: Mean node classification accuracy (%) on real-world graphs compared with additional baselines.
Methods
Coza
Citeseer
Pubmed
Cozneil
Misconsin
Chams
Equirzel
SP-GCL
82.99 18
75.54 20:00
85.74 gam
69.41 41
69.76 2:
69.34 2
35.92 2007
69.23 21:08
53.05 11
HLCLL
85.53
76.79
83.13
64.00
78 38
79,50
40.56
63.86
24,49
POLYGCL
eas
$7.15 amr
131
11000
o5s
672
Table 14: Experimental results on 6 heterophilic graphs compared with additional baselines.
Methods
Roman empire
Amazon saazzon-zatigg zatings
Xineaweepes
Tolokers
Questions
arxiv year
SP-GCL
63. 27
43. 11 20.32
81.76 20.61
80.73 20.02
75.08 20.49
42,56 =0
67.75 +0.10
43,92 +0.26
79.34 #0.50
78.99
74.92 =0.65
0OM 43,07
POLYGCI.
72.97 1.3
44,29 y
86.11 8.4
83.73 e.s
75.33 1 am
G.2 ABLATION STUDY: LINEAR COEFFICIENTS
We include experiments where a and B are set to zero separately as the ablation study of linear coefficients. Specifically, a = 0, 3 0 means only the high-pass/low-pant filter is reserved respectively. The results are given in Table 15
We observe that the results of POLYGCL (a 0) remain comparable in heterophilic datasets, while POLYGCL (3 = 0) shows better adaptability to homophilic settings. The results reveal that the high-pass information is indispensable for graphs with large heterophily, and so is the low-pass information for homophilic graphs. The results of this ablation study are further consistent with the low-pass/high-pes preference for homophilichheeerophiiii settings in Figure B Section 5.4 Note that POLYGCI. achieves better performance when optimized over both the parameters o, 3 in most datasets.
G.3 SUBSTITUTING EQUATION WITH THE NT-XENT LOSS
We consider directly substituting our optimization loss in equation 4 with the NT-Xent loss used in GraphCL You al. 2020 Besides, the augmentation strategies and other settings aligned with GraphCL. The results are listed in Table [6
We observe that the results of POLYGCL (NT-Xent) are slightly lower than POLYGCL. This phe- nomenon can be attributed to the introduction of structural augmentations (e.g., edge-dropping or subgraph-sampling) that destroy the spectral properties of the original graph, which is not conducive
27

---

Published as a conference paper at ICLR 2024
Table 15; Mean node classification accuracy (%) on real-world graphs compared with two variants of POLYGCL.
Methods
Cors
Citescez
Pubncd
Cocncll
T=x05
Wisconcin
Actor
Ch-amelccn
Squazrel
PoLYGCL
$7.57
79.81
$7.15
82.62
88,03
85,50
41.15
71.62
56,49
io
20.45
20:5
20.30
+2.02
61.07
c0.
POLYGCL (3 0y 87.65 sup
78.16 83.75
86.64 10.17
76.25 15:43
$2.50 :2.35
08.38 2,50
$7.26 20.00
05088
$1.27
48.52 ...7
Table 16: Mean node classification accuracy (%) on real-world graphs as for different losses.
Methods
Coza
Cilwaser
Fulased
Dozne1l
Texas
Risconain
Actiox
Chane Loon
Squiscel
PoLYGELL
am
88.08
41.15 38.95 g0
56.49
POLYGCT (NT-Xem))
76.83 g0
2030
81 g7
27.3
81.75 23
69.17 gM
gm:00
to the learning of spectral filters POLYGCI. However, POLYGCL (NT-Xent) still holds competi- tiveness with other baselines across different homophilic and heterophilic datasets in Table 2 which reflects the universality and effectiveness of the POLYGCL framework.
G.4 DISCUSSIONS ON THE REPARAMETERIZATION IN EQUATION
2
We utilize the reparameterization techniques in equation
2 ensure the low-pass and high-pass properties of the learned filters during the learning process, which correspond to the filter functions with incremental and decremental values, respectively.
To verify its effectiveness, we list the comparison between the results of POLYGCL and POLYGCL (wo-RP) in Table 17] where POLYGCL (wo-RP) denotes POLYGCL without ReParameterization By -lsss information via simple reparameterization, POLY benefits
decoupling the low-pass and high-pass from a more stable model training process and improves the performance on homophilichheterohiiiic datasets.
Table 17: Mean node classification accuracy (%) on real-world graphs: Reparameterization Analysis.
Cora
Citasoar
Pubmed
Coznell
Toxas
Wisconsin
Actoz
Chanslean
Scuizrel
POLYGCL
87.57 10.22
79.81 1o.s
87.15 10.27
$2.02 a3.31
88.03 11.00
83.50 a1.55
41.15 ac.ss
71.02 10.6
56.49 =0.72
POLYGCL (wo RP) 85.09
76.74
84.39
78.26
84.11
79,50
38.14 20.06
65.98
50.06
In addition, the reparameterization technique based non-negativity and prefix sum/difference can be easily extended to other polynomial bases, which further verifies the robustness of this technique. In detail, as for the Bernstein polynomial (He et al. 2021), which also learn arbitrary filters, directly utilize this reparameterization on the coefficients 02 which proves to be equivalent to the filter value (A).. Besides, for the Monomial polynomial in GPR-GNN (Chien al., 2021), can also consider non -egativee coefficients to ensure the low- www-pas//high-pae shlighhpasssss property, for instance, =i (21-- and 2 im L for low-pass/high-pas filters respectively, where the non-negativity of ys is all we need.
G.5 DISCUSSIONS ON OTHER POLYNOMIAL BASES
The analysis in Section G.4 reflects the generality and flexibility of our proposed reparameterization technique, and we consider utilizing the simple reparameterization to conduct experiments on Bernstein and Monomial bases. The results are listed POLYGCL (Ber) and POLYGCL (Mono) in Table We conclude that the results of POLYGCL (Bern) and POLYGCL (Mono) are comparable with POLYGCL on certain datasets, which reflects the generality of our framework. practice, we employ Chebyshev polynomials in POLYGCL due to comprehensive considerations of efficiency and effectiveness. This choice supported by Table 19 which presents the average running time per epoch (ms) of POLYGCI using different bases.
G.6 OTHER CORRUPTION METHODS
In our implementation of generating negative embeddings in POLYGCL, we simply shuffle the node features randomly. Further, conduct experiments on real-world datasets explore the impact
28

---

Published as a conference paper at ICLR 2024
Table 18: Mean node classification accuracy (%) on real-world graphs for different bases.
Methads
Cora
Cornell
Charel
POLYGCL
87.57 2642
79.81 6.5
87.15
022
82.62 48.1
88.03 1100
85,50 cUe
41.15 1.as
71,62 oow
56.49 w72
PoLYGCL (Bera)
85.51
77.45
83,90
83.13
S0.23
82.40
58.08
09.35
51.76
PoLYGCL (Meno)
$4.94
78.52
79,87
12.3
83.27
81.42
$2.00
66.41
Table 19: Average running time per epoch (ms) as for different bases.
Methods
Coza
Citeseer
Pubmed
Cornel:
Texas
Wisconsin
Actor
Chame
Squirrel
POLYGCI,
82,32
136.21
242.92
45.91
49.77
166.17
221.73
824,76
POLYGCL. (Bem)
208.53
322.73
815.07
97.61
90.83
104,38
383.9
589.41
2284.05
POLYGCL (Mono)
167.95
180.48
38.63
of other data augmentation methods in POLYGCL. We denote edge-dropping as "ED", feature- masking as "FM", and uubgraph-samplin as "SS" for short. Note that we follow the settings in CCA-SSG (Zhang al. (02T) and GRACE (Zhu al. (220bb) to perform edge-dropping and feature- masking at the same time, which is denoted as "ED&FM", and we perform the subgraph-sampling (SS) perturbation following GraphCL You et al. 2020).
Table 20: Mean node classification accuracy (%) on real-world graphs for different corruption methods.
Mothods
Cora
Citeseer
Pubmed
Carnel
"Texe
30 Riaconsiin
Act or
Chame lear
Sigu mrwl
PoLYGCI
87.57
79.11
87.15
82.62
88.03
85.50
41.15
71662
$6.49
POLYGCL (ED&FMM POLYGCI. (85)
23m
40.00
43.00
4..02
20
79
80.33
23:11
76.55 g0
23
observe that the ED&FM perturbation slightly deteriorates the performance of POLYGCIE but still seems comparable. However, the SS perturbation causes significant damage to the effectiveness of POLYGCL. We attribute this phenomenon excessive perturbations in the graph topology and the loss of important spectrum information while conducting the operation.
In Table 20
G.7 THE IMPORTANCE OF DECOUPLING MECHANISM
To demonstrate the effectiveness of the decoupling mechanism in POLYGCL, report the mean accuracy results the cSBM datasets in Table as a comparison between POLYGCL and POLYGCL (Cheb). Note that in POLYGCL (Cheb), directly apply GCL to the Chebyshev polynomial filters without decoupling the low-pass and high-pass information. POLYGCL generally outperforms POLYGCL (Cheb) different homophily levels, especially in extreme homophilichheterophiiic settings ([o) + 1).
Further, visualize the normalized learned filters of POLYGCL (Cheb) on the cSBM datasets in Figure Compared with Figure POLYGCL (Cheb) learns complex filters with a high degree of oscillation across homophily, while the filter curve learned by POLYGCL is smoother. From the spectral perspective, this observation supports our preference for the training paradigm in POLYGCL over learning spectral filters directly via GCL
29

---

Published as a conference paper at ICLR 2024
Table 21: Mean node classification accuracy (%) with a 95% confidence interval on cSBM graphs: Decoupling Analysis.
6-
0.75
6
9
0-
POLY GCL
98.84
94.23
90.82
75.43
66.51
69.43
88.22
98.09
99.29
GCL (Cheb)
79.28 00.45
85.35
20.92
81.04
60.57
77.27
66.00
65,90 00.53
70.34
84.63
92.97
89.72
1.0
6-
0-5.
0.8
--2255
0m0.5
Response
007.5
dm1
0.2
0.0
Figure The normalized learned filters of POLYGCL (Cheb) on cSBM datasets.
30


Reviews:
[{"review_id": "WrhKZGOkS5", "reviewer": "Reviewer_Q45Y", "summary": "The paper proposes a spectral domain self-supervised method for graphs based on a linear combination of low-pass and high-pass information while keeping the graph structure intact. Although the idea of the paper is interesting and novel, the evaluation lacks comparison with recent works along the similar direction. Moreover, the paper is missing some key references such as FAGCN (not a self-supervised method but considers high pass and low pass information in a supervised manner)[1], [2] [3]. It lacks explanations concerned with the intuition behind low-pass and high-pass information in the learning process. \n\n\nTheorem 1 is only for regular graphs for binary classification, how can it be a basis of a much stronger claim of having the high pass information in heterophilic datasets?\n\nHave you considered high-pass encoders for the graphs with large heterophily? What is the performance in such a case of alpha = 0? What about when beta = 0?\n\nWhat about using NT-Xent loss as used in GraphCL as compared to the one used in this paper? What is the intuition of low and high frequency information in the context of the global embedding $g$? \n\nWhile reporting the results for graphCL, what exact method did you use? node/edge-drop or a combination of other methods?\n\n[1] Deyu Bo et al. , \"Beyond Low-frequency Information in Graph Convolutional Networks\", AAAI 2021.\n[2] Amur Ghosh et al. , \"Spectral Augmentations for Graph Contrastive Learning,\" AISTATS 2023.\n[3] W Yang, B Mirzasoleiman, \"Graph Contrastive Learning under Heterophily,\" 2023 Arxiv.\n\n\nAfter response:\n\nI appreciate the efforts authors put to clarify my concerns. Thanks. The authors comment on \"k-regular graph\" restricting the eigenvalues of the normalized Laplacian to [0,2] was unsatisfactory. In fact, it is true for all type of graphs. Such loose statements are not good. Moreover, I was looking for for more intuitions about low pass and high pass questions and comparing against the mean representation, just putting some numbers in order to validate the usefulness of the proposed work seems a bit naive. It would help the paper if frequency domain examples are exploited in simple settings, not just in terms of accuracy numbers after putting a classification head. This paper had a great idea, but could have been much better..", "questions": "Theorem 1 is only for regular graphs for binary classification, how can it be a basis of a much stronger claim of having the high pass information in heterophilic datasets?\n\nHave you considered high-pass encoders for the graphs with large heterophily? What is the performance in such a case of alpha = 0? What about when beta = 0?\n\nWhat about using NT-Xent loss as used in GraphCL as compared to the one used in this paper? What is the intuition of low and high frequency information in the context of the global embedding $g$? \n\nWhile reporting the results for graphCL, what exact method did you use? node/edge-drop or a combination of other methods?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "please see summary.", "weaknesses": "please see summary.", "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": "", "extra_scores": {}}, {"review_id": "gKubVWhiwQ", "reviewer": "Reviewer_aFan", "summary": "This paper addresses graph contrastive learning with learnable spectral filters, allowing to tackle homophilic and Heterophilic graphs.", "questions": "Please position this work and its contributions with respect to the aforementioned papers", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Graph contrastive learning is of great interest, including the challenging goal of addressing heterophilic graphs.\nThe proposed idea is interesting and the paper providing theoretical and relevant experimental results is well written.", "weaknesses": "The main issue is that this paper is not well positioned within the literature of graph contrastive learning (GCL), including several missing work on GCL with spectral filters and/or adaptive/learnable filters, such as\n* Liu, Nian, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei. \"Revisiting graph contrastive learning from the perspective of graph spectrum.\" Advances in Neural Information Processing Systems 35 (2022): 2972-2983.\n* Xie, Xuanting, Wenyu Chen, Zhao Kang, and Chong Peng. \"Contrastive graph clustering with adaptive filter.\" Expert Systems with Applications 219 (2023): 119645.\n* Zhang, Hengrui, Qitian Wu, Yu Wang, Shaofeng Zhang, Junchi Yan, and Philip S. Yu. \"Localized Contrastive Learning on Graphs.\" arXiv preprint arXiv:2212.04604 (2022).\nThe latter also provide some results on heterophilic graphs. Another paper on GCL with homophilic and heterophilic graphs is\n* Wang, Haonan, Jieyu Zhang, Qi Zhu, and Wei Huang. \"Can Single-Pass Contrastive Learning Work for Both Homophilic and Heterophilic Graph?.\" arXiv preprint arXiv:2211.10890 (2022).\nand some theoretical results in this paper can be related to works conducted by other researchers  \n* HaoChen, Jeff Z., Colin Wei, Adrien Gaidon, and Tengyu Ma. \"Provable guarantees for self-supervised deep learning with spectral contrastive loss.\" Advances in Neural Information Processing Systems 34 (2021): 5000-5011.\n\nThere are some spelling and grammatical errors, such as “in an self-supervised manner”, “with an self-supervised one”, “Trainging Algorithm”, “We denote Y … be the”, “ further justification are discussed”, “claims that maximize”, “optimising … also maximize”, “proves that maximize”, “Shannon diverge”", "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": "", "extra_scores": {}}, {"review_id": "v59FyXm7lY", "reviewer": "Reviewer_2heL", "summary": "The paper introduces a novel approach to Graph Contrastive Learning (GCL) named POLYGCL, designed to address the challenges of applying GCL to both homophilic and heterophilic graphs. The primary limitation addressed is the inherent smoothness introduced by traditional low-pass GNN encoders. POLYGCL employs learnable spectral polynomial filters to balance between low-pass and high-pass views, providing better representation learning for both graph types. Theoretical proofs underscore the effectiveness of this combined filter approach, and empirical evaluations on synthetic and real-world datasets validate the method's superiority over existing GCL paradigms. The research fills a crucial gap in the realm of graph representation learning, particularly concerning heterophilic graphs.", "questions": "1. **Motivation behind Chebyshev Polynomials**: Can the authors provide more insight into why Chebyshev polynomials were specifically chosen as the base polynomials? How do they compare to other potential polynomial bases in terms of efficacy and computational efficiency in the context of Graph Contrastive Learning?\n\n2. **Filter Decoupling Challenges**: Are there potential challenges or scenarios where the decoupling of low-pass and high-pass information might be less advantageous? How does the method account for such scenarios?\n\n3. **Limitations of the Model**: Every model has its limitations. What would the authors identify as the key limitations of the PolyGCL method? Are there specific types of graph structures or data distributions where PolyGCL might not be the best choice?\n\n4. **Future Work**: Given the current findings and the proposed method, what do the authors see as the next steps or future directions in this line of research? Are there plans to extend PolyGCL or integrate it with other techniques to address more complex graph learning scenarios?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "1. **Originality**:\n    - The work presents a novel approach in the form of **PolyGCL** that combines both low-pass and high-pass filters in graph-based learning.\n    - The theoretical foundations are robust, and the introduction of a combined filter in graph learning is a commendable initiative.\n    - The work extends beyond existing literature by addressing both Graph Contrastive Learning (GCL) methods and spectral-based GNNs, which is an original contribution to the domain.\n\n2. **Quality**:\n    - The paper is backed by rigorous theoretical formulations, evidenced by multiple theorems, remarks, propositions, and corollaries.\n    - The empirical validations, including both synthetic and real-world datasets, provide strong support for the paper's claims. A diverse set of baselines have been chosen for comparisons, ensuring a comprehensive evaluation.\n\n3. **Significance**:\n    - The paper addresses challenges in existing GCL methods and spectral-based GNNs, a pressing need in the domain of graph representation learning.\n    - The proposed method's prowess on heterophilic graphs is especially significant given the inherent challenges of these graph types.\n    - The complexity analysis suggests the scalability of the method, highlighting its potential applicability to large-scale problems in the future.\n\n---\n\nIn conclusion, the paper stands out in its originality, depth of analysis, and significance to the graph learning community. It is a valuable contribution to the literature and holds promise for further explorations in this direction.", "weaknesses": "1. **Lack of Intuitive Explanation for Choice of Chebyshev Polynomials:** The paper introduces the use of Chebyshev polynomials without providing a deep intuitive rationale behind this choice. For readers unfamiliar with Chebyshev polynomials or their relevance in graph-based learning, this can be a point of confusion. A discussion on why Chebyshev polynomials were chosen over other potential polynomial bases could add depth to the work.\n\n2. **Decoupling of Low-Pass and High-Pass Information**: While the paper emphasizes the importance of decoupling low-pass and high-pass filter functions, it doesn't thoroughly discuss the potential pitfalls or challenges of this approach. It would be beneficial to discuss under which conditions this decoupling might not be advantageous or how it compares to methods that don't employ this decoupling.\n\n3. **Reparameterization and Assumptions**: The paper introduces reparameterization techniques, such as using the prefix sum and prefix difference, to ensure non-negativity and a decremental filter value. However, there's a lack of clarity on the implications of these assumptions and reparameterizations on the model's performance and generality. It would be beneficial to delve deeper into why these particular reparameterization techniques were chosen and their impact on the robustness and flexibility of the approach.", "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": "", "extra_scores": {}}, {"review_id": "KRlGUvakbG", "reviewer": "Reviewer_LQgR", "summary": "This paper focuses on self-supervised learning applied to spectral GNNs. It addresses the limitation of existing contrastive learning techniques when dealing with high-pass heterophilic graphs. The authors tackle this challenge by introducing high-pass information in graph contrastive learning (GCL) and propose PolyGCL, a GCL pipeline that leverages polynomial graph basis to generate different spectral views for contrastive learning. Experimental results on synthetic and realworld datasets validate the effectiveness of the proposed PolyGCL.", "questions": "1. Please provide a more detailed explanation of how $\\alpha$ and $\\beta$ are optimized in Equation (4). Are there any supervising signals to optimize these two parameters? If so, the model seems to be equivalant to directaly optimizing a polynomial filter since all of the coefficients are learnable.\n2. Please give the rationale for randomly shuffling node features as a pertubation method. Would the model performance be influenced if the random shuffle were replaced with other methods like edge-dropping or subgraph-sampling?\n3. Please provide more explanations on PolyGCL's advantage over directaly applying GCL on spectral GNNs?\n4. How would the model performance when there is only one filter left or $\\alpha$ and $\\beta$ are fixed?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The introduction of polynomial spectral GNNs into graph contrastive learning is a novel and interesting idea.\n+ PolyGCL is well-motivated, and the authors provide empirical evidence to support the necessity of designing specific polynomial filter structures.\n+ There are some decent theoretical analyses of the proposed method.\n+ Experimental results demonstrate the effectiveness of PolyGCL.", "weaknesses": "- Certain part of the introduced model need further clarrification. The authors propose to optimize a high-pass and a low-pass filter with polynomial spectral filters respectively, but ultimately arrive at a linear combination of the outputs of these two filter results. However, the optimization target in Equation (4) doesn't involve $\\alpha$ and $\\beta$ at all . \n- The rationale behind randomly shuffling the node feature to obtain the contrastive view needs to be explained, since is not a common practice to pertub graph representation.\n- In section 4.4, authors conclude that the aggregation of low-pass and high-pass representations achieves better error upper bound compared with just one aspect of representation. However, it still doesn't explain PolyGCL's advantage over directaly applying GCL on normal spectral GNNs like ChebNet.\n- The paper lacks sufficient ablation studies on the two separate filters, such as how the model's performance is affected when there is only one filter left or when $\\alpha$ and $\\beta$ are fixed.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)