HarmonyGNNs: Harmonizing Heterophily and Homophily in GNNs via Self-Supervised Node Encoding
Authors: Rui Xue
Tianfu Wu
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Neural Networks
Heterophily and Homophily
Self Supervise Learning
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph Neural Networks (GNNs) have made significant advances in representation learning on various types of graph-structured data. However, GNNs struggle to simultaneously model heterophily and homophily, a challenge that is amplified under self-supervised learning (SSL) where no labels are available to guide the training process. This paper presents HarmonyGNNs, an end-to-end graph SSL framework designed to harmonize heterophily and homophily through two complementary innovative perspectives: (i) Representation Harmonization via Joint Structural Node Encoding. Nodes are embedded into a unified latent space that retains both node specificity and graph structural awareness for harmonizing heterophily and homophily. Node specificity is learned via linear and non-linear node feature projections. Graph structural awareness is learned via a proposed Weighted Graph Convolutional Network (WGCN). A self-attention module enables the model learning-to-adapt to varying levels of patterns. (ii) Objective Harmonization via Predictive Architecture with Node-Difficulty–Aware Masking. A teacher network processes the full graph. A student network receives a partially masked graph. The student is trained end-to-end, while the teacher is an exponential moving average of the student. The proxy task is to train the student to predict the teacher’s embeddings for all nodes (masked and unmasked). To keep the objective informative across the graph, two masking strategies that guide selection toward currently hard nodes while retaining exploration are proposed. Theoretical underpinnings of HarmonyGNNs are also analyzed in detail. Comprehensive evaluations on benchmarks demonstrate that HarmonyGNNs achieves state-of-the-art performance on heterophilic graphs (e.g., +7.1% on Texas, +9.6% on Roman-Empire over the prior art) while matching SOTA on homophilic graphs, and delivering strong computational efficiency.

Published as a conference paper at ICLR 2026
HARMONYGNNS: HARMONIZING HETEROPHILY AND HOMOPHILY IN GNNs VIA SELF-SUPERVISED NODE ENCODING
Rui Xue & Tianfu Wu
Department of Electrical and Computer Engineering (ECE) North Carolina State University, Raleigh, NC 27695, USA (rxue, twul9 @ncsu.ede.
ABSTRACT
Graph Neural Networks (GNNs) have made significant advances in representation learning on various types of graph-structured data. However, GNNs struggle to simultancously model heterophily and homophily, challenge that is amplified under self-supervised learning (SSL) where no labels are available to guide the training process. This paper presents HarmonyGNNs, an end-to-end graph SSL framework designed to harmonize heterophily and homophily through two com- plementary innovative perspectives: (i) Representation Harmonization via Joint Structural Node Encoding. Nodes are embedded into a unified latent space that retains both node specificity and graph structural awareness for harmonizing heterophily and homophily. Node specificity is learned via linear and non- linear node feature projections. Graph structural awareness learned via a proposed Weighted Graph Convolutional Network (WGCN). A self-attention module en- ables the model Searningtto-adap to varying levels of patterns. (ii) Objective Harmonization via Predictive Architecture with Node- Lodee-iitiiuult-Aaaan Mask- ing. A teacher network processes the full graph. student network receives a partially masked graph. The student is trained end-to-ens while the teacher is exponential moving average of the student. The proxy task to train the student predict the teacher's 's embeddings for all nodes (masked and unmasked). To keep the objective informative across the graph, two masking strategies that guide selection toward currently hard nodes while retaining exploration are proposed. Theoretical underpinnings of Harmony GNNS are also analyzed in detail. Com- prehensive evaluations on benchmarks demonstrate that HarmonyGNNy achieves state-of-th oh-the-rrt performance on heterophilic graphs (e.g.. +7.1 1.1% % on Texas, +9.6% on Roman-Eian Emprre over the prior art) while matching SOTA on homophilic graphs, and delivering strong computational efficiency. Code is released at this Github repository
INTRODUCTION
Representation learning on graph-structured data has emerged as a vibrant research area, serving as cornerstone for a wide range of graph learning tasks, including node classification, link prediction. and graph classification (Kipf & Welling 201 Gasteiger et al., 2019) Veličković et al. 2017 Wu al. 2019). These tasks are critical in diverse real-world domains such recommendation systems, molecular biology, and transportation (Tang et al.) 2020: [Sankar et al. 2021 Fout et al. 2017] Wu et al. 2022 Zhang et al.] 2024). Graph Neural Networks (GNNs) have become the dominant paradigm for learning expressive node and graph representations (Hamilton) 2020 Gasteiger et al.
2018 Veličković et al. 2017).
Traditional GNNs are typically trained in semi-supervised manner and have demonstrated impressive
performance across numerous benchmarks (Xu al. 2018 Li et al. 2021 Sun et al. 2021 Xue et al. 2023a| 2024). However, these supervise methods heavily rely the availability of labeled data, making them vulnerable to significant performance degradation when labeled data is scarce (Xue et al. 2023b). To overcome the limitations of label scarcity, supervisee Learning (SSL.)

---

Published as a conference paper at ICLR 2026
Loss. Ali-Noda
Raw Features
Input Braph
StepGrad
Prediction
Feature
Teacher Network
[Exponential Moving Avarage the Student Network)
Node Difffeutt--rivee Dynamic Masking warm random masking)
Student Network
(End-to-Erv End Trained from Scratch)
Y Node
Linear
HarmoryGNNs Embeddings
Mesked
MLP
Trandformrr
Hiararehical
input Biaaph
Fusion
H-Hop WGCN
K-Hop WGCN
reta/ shuuturee enarenssy
Joint Structural Node Encoding
Figure 1: Illustration of our proposed HarmonyGNNs:
Figure 2: T-SNE Wisconsin.
has emerged as a promising alternative. Various graph SSL methods (Velickovic et al. 2019 Zhu
et al. 2020b Hou et al. 2022 Chen et al. 2022 Xiao et al. 2024 lang al. 2022 Xiao et al. 2022
Yuan et al. 2023) have demonstrated strong performance under low-label regimes. However, current SSL paradigms- whether contrastive or generative-suffer from their own drawbacks. Contrastive methods often rely on complex training pipelines and carefully crafted data augmentations, while generative methods are prone to reconstruction-see -ppcc mismatches. A more comprehensive review of related work is provided in Appendix A
More importantly. real-world graphs exhibit complex mixed structural patterns, where homophily (the tendency of connected nodes to share similar labels) and heterophily (the presence of dissimilar labels among connected nodes) coexist both local and global scales. We provide a visualization dataset
in Fig. 2 And intensities are varying across datasets. For example, the Roman-Empin exhibits homophily ratio only 0.05, while Cora shows ratio 0.81 (see Table details). Many existing graph SSL models still perform poorly on heterophilic graphs, undermining their generalization capabilities. This is particularly troubling given SSL's fundamental reliance on raw graph structure and node features without explicit label guidance.
Recent efforts have attempted to address this challenge. Methods such as MUSE (Yuan et al. 2023 GREET (Liu et al. 2022), and GraphACL (Xiao et al.) 2024) have shown promise in improving SSL performance on heterophilic graphs. However, achieving robust performance across both homophilic and heterophilic patterns remains elusive. This persistent challenge stems from deeper issue: the inability of current graph SSL frameworks to harmonize the mixed structural patterns.
We propose that harmonizing homophily and heterophily within single graph SSL framework is key. Specifically, unified model should achieve both objective harmonization and representation harmonization when handling mixed structural patterns. Regarding objective harmonization. select- ing an appropriate proxy task is crucial. Contrastive approaches in SSL rely on relative objectives (e.g.. InfoNCE) without a stable global reference, making unclear which pattern should dominate in mixed graphs. This deeiondde ambiguity prevents convergence to unified latent space; Gen- erative methods that force raw feature reconstruction yield contradictory signals when neighbors have dissimilar attributes in heterophilic settings. In terms of representation harmonization, homophilic regions require smoothness to capture similarity, while heterophilic regions demand distinctiveness to preserve differences. Existing methods cannot adaptively balance these needs, and thus biased toward one structural pattern.
To this end, present HarmonyGNNs (Fig. T. end-to-end graph SSL framework that achieves both objective and representation harmonization. We summarize our contributions as follows:
Objective Harmonization via Predictive Architecture with Dynamic Masking: We exploit Tracher-Student framework which provides stable, holistic guidance Graph SSL. The teacher, with full view of the unmasked graph, produces holistic node representations node-encoding
2

---

Published as a conference paper at ICLR 2026
anchors, capturing both homophilic and heterophilic relations. The student is then guided to predict this stable target. Crucially, the teacher's ' EMA-updated parameters ensure the learning spaces are aligned and prevent the student from being misled by noisy, oscillating updates, which is critical for adapting to complex structures. Due to the interconnected nature of graphs, we compute the prediction loss for the entire graph (rather than only the masked nodes), thereby addressing the severer ambiguity inherent in graph data. Furthermore, instead of random node masking, we propose two dynamic masking strategies, which generate training tasks that are both challenging and informative. This design yields a learning objective that harmonizes easy and hard samples as well as homophilic and heterophilic signals.
Representation Harmonization via Joint Structural Node Encoding: To enhance representation learning, we combine linear and MI.P-based node feature transformations (emphasizing intrin- sic attributes) with K-hop structural projections via proposed Weighted GCN (which adaptively aggregates neighbor information). A vanilla Transformer block integrates these representations via self-attention, ensuring adaptability to homophily and heterophily while maintaining effi- ciency. A novel hierarchical fusion strategy is applied to integrate/calibrate the different types of representations. It gives the model the ability "see" and learn different patterns.
These two components are fundamentally intertwined, and each of them is essential. The predictive architecture provides the learning stability, the joint encoding module provides the expressive power to handle mixed signals (see an illustration in Fig. and the dynamic masking strategy provides a challenging yet meaningful learning objective. Extensive experiments on various mixed-structure graph benchmark datasets verify the strong performance of our HarmonyGNNy improved training effectiivnesss, efficiency, and generalization. The results show that a single, unitied framework can be designed to automatically navigate the full homophily heterophily spectrum without requiring any prior knowledge of the graph's 's properties.
demonstrating
PRELIMINARY
We present a preliminary analysis demonstrating the inability of baseline methods to effectively learn homophily and heterophily mixed patterns, which motivates our proposed HarmonyGNNs.
Notation 1. Denote by G = (V, E), a graph with the node set V of N nodes and the edge set E. Each node E V has d-dim feature vector f(v) Rd A subset V S V carries labels ((v) E y, these labels are not used during self-supervised training and used only for linear probing and k-means evaluation with self- self-supervieed node encoding frozen.
Homophily and Heterophily in Graphs. In graphs, ho- mophily means that adjacent nodes (u, v) tend have similar features, and heterophily means the opposite, which can be reflected in the graph normalized Laplacian
Performance Under Different Retio
74.8 71.7
Accuracy (%)
quadratic form, f Tayy
E(u,jEE Aut f(u) VT
37.1
f(0) where Tayym represents the symmetric normalized
33.1
vd.)
Laplacian, Laym = I D 3. A D 1 with the degree matrix D, adjacency matrix A, and identity matrix II. du and d, are the node degrees. f(u) Rs (()) for adjacent nodes, making ʃ Leym .S small. Conversely, in heterophilic graphs, the differences
homophilic graph,
h- 01 Mnmeppayy
0.7 (ilonaght))
Figure 3: Impacts of homophily ratios.
[(()
f(w) are larger. The coexistence of homophiliy Va.. Va..
and heterophily in real-world graph data challenges representation learning, especially via graph SSL.
Control Experiments using Synthetic Graphs. To illustrate the impacts of varying homophily ratios in graph data, we leverage synthetic graphs (Zhu et al. (020a) with controlled homophily ratios, h (h 0.1 indicates strong heterophily and h = 0.7 corresponds homophily) in training GNNs under supervised learning setting. We train classic GCN and GAT, and a simple baseline node-based MLP (with graph structure not used) which is found useful in (Chen al. (022)..
Fig.3 showws the results. As expected, GCN and GAT show much stronger performance on homophilic graphs than heterophilic ones. The baseline ML. significantly improves performance on heterophilic
3

---

Published as a conference paper at ICLR 2026
graphs, thanks to its capability of retaining node specificity, at the expense of degrading performance on homophilic graphs (due to lacking graph structural awareness). So. we can clearly see the advantage of adaptively harnessing the strength of node-specificity representation and graph structural awareness, which motivates our HarmonyGNNS.
3 METHOD
We first present details of Objective Harmonization and Representation Harmonization in our HNNmonyGNNNs in Sec. S.c.3.1 I 3.2 respectively, followed by theoretical underpinnings comparing our HarmonyGNNNs to existing methods to highlight the strengths of our HarmonyGGNNs in Sec. 3.4
3.1 OBJECTIVE HARMONIZATION
The choice of proxy task in SSL is critical. Inappropriate tasks can actually degrade performance (see details in Appendix A). In our HarmonyGNNs. motivated by JEPA and its demonstrated success in computer vision (Assran al. 2023), we employ a teacher-student predictive architecture to eliminate the need for complex negative sampling and to prevent representation collapsing, while ensuring both feature prediction in an aligned latent space and stable representation learning (see See 3.4). Moreover, we adopt masked node modeling as our primary proxy task and introduce two novel node-diffieully-driee dynamic masking strategies that encourage the model to learn more robust and generalizable representations.
Masked Node Modeling with Teacher-Student Predictive Architecture. For an input graph G -V, E') and a given node-wise mask M, let V' = { E V M(v) 1} be the subset of masked nodes, and V. = V \ Vn the subset of remaining unmasked nodes. For the masked nodes in Vn. replace their raw input features by learnable parameters with random initialization, e.g., from the white noise distribution. f(v) ~ NO, 1), Ve E Vn Let = (V, U Vn. E) denote the partially masked input graph, which is generated at each training iteration by sampling node-wise mask M. To facilitate learning a proper latent space, we leverage a teacher-student predictive architecture. Denote the student and the teacher network by S( 2) and T(- Vr), parameterized by 4 and V respectively. The student network sees the masked input graph G, while the teacher network sees the full graph G. The teacher network has the exactly same network configuration as the student, and is not trained, but uses the exponential moving average (EMA) of the student network to ensure the stability of training and the convergence of the same latent space (He et al. 2020 Assran et al. 2023 Bardes et al. 2024):
V. a VI + (1 a) P, i= 1,2,
All-Node Feature Prediction in the Latent Space. To estimate the student network's parameters ④b a proxy or pretext task is entailed. One common approach to consider masked nodes feature prediction in Vm only. However, graph nodes are inherently more ambiguous because their intercon- nections create strong dependencies, leading to interactions between masked and unmasked nodes to be captured. Predicting only masked nodes" features between the student and the teacher network is thus suboptimal for learning a more meaningful latent space. For a node v E V Vn, U Va. denote the outputs from the student and teacher network by S(1; Φ) E RD and ((;; v\ RR respectively. We propose to compute the prediction loss in the latent space based on the entire graph.
((Φ)=
1 - N ||S(;; 0) V)
Σ
Saat-Diffiiully-Driven Dynamic Node Masking. Masking strategies are critical for the success of SSL.. In general, random masking with sufficient high masking ratios (Devlin et al., 2019 He jet al. 2022) leads to hard proxy tasks to solved via learning meaningful representations. However, given the complex and often unknown topological properties of graphs, random masking alone is insufficient to guide effective SSL. Hence, we propose two novel dynamic masking strategies to compute the mask M; at each iteration. These strategies adaptively consider each node's 's learning difficulty based on the prediction loss in Eqn. P ensuring that the prediction task is sufficiently challenging learn robust representations with excellent generalization capabilities.
Denote by R be the overall node masking ratio hyperparameter (R E 10, We mask A = [N x R IV..l nodes in total. We warm up the training with purely random masking for
4

---

Published as a conference paper at ICLR 2026
predefined number of epochs. Afterwards, adopt the exploitation-exploraiii strategy, where exploit two mode-difficulty--riie drivve dynamic masking approaches, combined with the purely random exploration-basee masking. Let be the exploitation ratio (r E [0, 1),, we first select m [M r. nodes using the exploitation approach, and the remaining M m nodes are randomly sampled from the set of available N nodes (without replacement).
HarmonyGNNs +Diffi: Node Feature Prediction Loss Driven Masking, Based on Eqn. 2 we define the difficulty score of node after the current iteration by,
Diff(t) ||5(u) T(2)
(3)
which is used to compute the mask for the next iteration. We sort the nodes E V based on Dif in a decreasing order, and then select the first m nodes to mask. This approach ensures that the model focuses nodes where the student network's 's understanding is significantly lacking compared to the teacher network, thereby driving the student network to improve its representations where is most deficient. However, this approach does not entirely prevent the issue of over-focusing subset of high-difficulty nodes while neglecting the overall data diversity. To address this, we seek a probabilistic solution in the next approach.
small
HarmonyGNNs +Prob: Masking via Bernoulli Sampling with Node-Difficuly Informed Success Rate. Let pv be the success rate of the Bernoulli distribution used for selecting the node v E V to be masked, i.e., M(v) ~ Bernoullipp.). We have,
Diff(u)
Pe Po + 80, Po (1 r) x R, 5,
X x R,
(4)
Diffimax
where Po is the base success rate subject to the exploration approach, and it is the same for all nodes. d, is the node-difficulty based exploitation with Diffimax the maximum value of the node difficulty score among all nodes. This approach ensures that all nodes have base probability Po of being masked, while higher-difficulyy nodes are masked with greater chance, effectively guiding the model to focus more on learning from these challenging nodes. Since this approach is node-wise Bernoulli sampling, to prevent the worst cases in which either too few nodes or too many nodes (much greater than M) are actually masked, we do sanity check in the sampling process by either repeatedly sampling (if too few nodes have been masked) or early stopping.
3.2 REPRESENTATION HARMONIZATION
With the above architectural designs and loss function choices, we seek node encoding scheme towards the expressivity of node features in graph SSL in terms of inducing heterophily and homophily awareness and adaptivity in (t) against the raw input features f(v) for downstream tasks.
Learning Weighted GCN for Heterophily- Seieroophily-Prreseee Preserved Homophily Awareness. The traditional
GCN has been proven to act as simple and efficient smoothing operator (Kipf & Welling 2016a) making it good for homophilic graphs, but becoming less effective for heterophilic graphs (see Fig. 3 To address this, we introduce Weighted GCN (WGCN), which learns weights for edges and thus adaptively controls message passing- balancin smoothing and sharpening- handle diverse graph structures more effectively, avoid complex design choices and preserve high efficiency. Formally, a WGCN's layer is given by,
H(+1) o(A H H(O.W())
where Ay is learnable parameter that adjusts the edge weight dynamically, meaning the model learns how much influence each neighbor should have, instead of treating all edges equally. It is initialized from À = 5 ( + I)D 112 the normalized adjacency matrix with self- Then, the learned edge weight are passed through Sigmoid function a, (w,) as the edge weight for edge e. Bounding ag to (0, 1) regularizes the magnitude of edge weights, mitigating the trivial global-rescaling ambiguity that can otherwise arise in weighted message passing. (!)) < R XC is the node feature matrix at layer with the output dimension C is chosen to control model complexity. w(l) is the trainable weight matrix. In homophilic regions, WGCN retains high weights for similar neighbors; in heterophilic regions, it downweights dissimilar ones, preventing oversmoothing and capturing complex structures more effectively.
Projecting Node- Wise Features for Heterophily- Targeted Awareness. From Fig. 3 we can see the base MI.P can retain node specificity for achieving good performance on heterophilic graphs. So,
5

---

Published as a conference paper at ICLR 2026
introduce nonlinear projection f(Mip) (v) the node features. Additionally, the node features themselves play crucial roles, especially when neighborhoods exhibit high heterophily (Yuan et al.) 2023 Hence, we also apply a linear projection ((Linear) (v).
Learning Multi-Head Self-Attention for Heterophily and Homophily Adaptivity. To adaptively capture both homophily and heterophily, for a node v E V, we map it into a joint latent space. For example, we can simply combine the four types of features,
f(v) (())={(Linnerr) (v) @ ((Mip) (v) @ (v) + H (()) where f(v) E BAC
[(Linear)
(6)
where @ denotes stacking operation, l and l' denote WGCN layers, which can be tuned easily. To mix and re-calibrate the different types of features per node to induce heterophily and homophily awareness and adaptivity, treat the each projection output as "token" (e.g.. 4 tokens illustrated in Fig. [] and apply a vanilla Transformer block (Vaswani et al. 2017) with pre-norm settings. By doing SO, maintain the efficiency with novel feature level attention mechanism, which is different from existing graph transformer works that aim to capture node-wise attention and suffer from scalability caused by the quadratic complexity of the Transformer model w.r.t. the number of nodes N.
Fusing and Selecting Tokens Hierarchically as SSL Node Encoding. The four tokens in Eqn. 6 after passing through Transformer block, provide complementary representations of each node. Instead of flattening them all once, we fuse the most closely related encoded tokens first and propagate the result upward, which (i) keeps the parameter count low, (ii) eases gradient flow, and (iii) lets the model learn a coarse-to-fine weighting of homophilic and heterophilic patterns. We first fuse the two encoded tokens generated by WGCN; we then iteratively merge this result with each of the remaining two encoded projection tokens to produce the final output.
S(v) = a (Linear (Xo,cila (Linear (Xi,cllor (Linear (X2cclXa.c)))))
(7)
where Xio represents the output of f(Linear), f(M1p), H and ((') from the Transformer block for i = 0, 1, 2,3 respectively. Additionally, we also offer several strategies for deriving the final output, such taking the mean, the max, and simply selecting Xo,c. We provide an ablation study about the encoded token selection in Appendix M
3.3 COMPLEXITY ANALYSIS
Let denote the hidden (channel) dimension, the number of WGCN layers and the number of per-node tokens used in the harmonization module (e.g., = 4 in our implementation).
Computational complexity. The computation of HarmonyGNNY can be decomposed into three
parts:
MLP branch: Mapping raw node features to node-specific tokens via one or two linear/MLP layers costs O(N or O (N Nh²) (for 2-layer MLP).
WGCN branch: The [-hop structural embeddings are implemented with sparse WGCN layers, each with complexity O E h). Hence the cost is (1)E))).
Feature-level MHSA: For each node, we apply MHSA over its s feature tokens. Computing attention scores between tokens and the associated linear projections costs O + sh²), per node, and thus ONNs22, Nsh?) over all nodes. Note that the cost is not ON2)). This is exactly why we emphasize feature-token attention instead of node-wise attention.
Putting everything together, the overall complexity of the student encoder is O + [[E]h Ns2h + Nsh?). Since and are small constants (e.g.. < 2 and s = 4) our implementation, this simplifies to ONNdi + |E|h + Nh?). which on the same order as standard GNN encoders and strictly more efficient than node-wise graph transformers with (v)2h) attention.
Memory complexity. The memory footprint of the proposed method is dominated by:
Node activations: Each node stores s tokens of dimension h, leading to ONNsh) = O(N))
Graph structure: The sparse edge index and scalar weight per edge in WGCN require O O(E)) E
Model parameters: Input projections, WGCN weights, and token-level attention/MLPs take O (dh (dh- h²), which is independent of N and [P]]

---

Published as a conference paper at ICLR 2026
Under the sparse- sparse-graph assumption, the total memory complexity is therefore O [E]+ + dhh h?),
i.., it grows linearly in both N and [E] and does not require storing any ((N2) node-wise attention maps.
3.4 THEORETICAL UNDERPINNINGS
In this section, we provide theoretical underpinnings of graph SSL convergence analyses for our HarmonyGNNs and alternative encoder-decoder based graph SSL methods such as GraphMAE (Hou) et al. 2022 2023) (which aim to directly reconstruct raw input features of masked nodes).
The encoder-decoder SSL. architecture consists of an encoder network F(:; (ene) and a separate decoder network ddec). Let 0 = (Dene, deec) collects all parameters. Given a masked graph signal f from the input graph signal of N nodes using mask M, its objective is minimize,
(E N [ID(E(f: enn)): Qdec) f11..
(8)
The convergence rates of encoder-decoder methods and our HarmonyGNNss (Eqn. can be bounded in the main theorem as follows.
Theorem 1. Consider the optimization of encoder-decoder based graph SSL in Equ. S and our proposed HarmonyGNNs in Eqn. [ under the same encoder architecture and following assump- tions/conditions: i Smoothness & Lipschitz: The encoder E(:; encc) and decoder D(= Q are
3-smooth and I--Lipschitz; Boundedness: Gradients of the encoder | E(; E(;; gradients of the decoder < (EE:; O en Oodc) O |]. and reconstruction errors [I O (t) - fIl are bounded; ii Strong convexity: Both the encoder F(:; Oen) and decoder D(: Q are j-strongly convex in their parameters; (v) Approximation: With only unmasked inputs, the encoder-decomd (or stacher-student in HarmonyGNNs incurs approximation error EE-D (or eT es) See assumptions details in Appendix G Then, the following three results hold:
A. Linear Convergence Bounds Under Strong Convexity. For our HarmonyGNNs,
P
[| 1- < (1
-((((t)))
P
For the encoder-decoder models,
[[0(++1)_ - 1- S (1- min(pgg,1b)) 10(0) 1¹1
(10)
(B2, max (82, (B)
from which can our HarmonyGNNs converges to the optimal solution &" faster than the encoder-decoder counterpart to their optimal solutions O* due to a smaller contraction
factor (1- < (1-
min(ug . This implies that HarmonyGNNs can achieve a faster
max (B2 (61
convergence.
B. Proxy Task Loss Bounds under a Lipschitz-dependen assumption between the masked graph signal and the raw graph signal, [| [| < 5. For our HarrmonGNNNs
[[S(f: b)) (ff: V1ll < Lg 8 6T
(11)
For the encoder-decoder models,
[D(EF Dene); dec)) fll S LE LD 8 8+ CE-D-
(12)
W.L.O.G., assume EE-D = ET-S, our HarmonyGNNs has a smaller error upper bound, indicating that our seacher-student model is closer to the optimal solution 4 during training, which implies that its parameter updates are more stable and its convergence speed is faster (as shown in A).
C. Gradient-Differene Bounds in Dncoder- Models Showing Coupling Effects of Parame- ter Updating.
LV. (1(+)))) ((((1)) (LE=D(((()) enc) < 2B Reconst (BE BELLLE [10(tt2)) !!!) I|
2B B Be Bnll (++1)) - dec
(
4B Bp Breonsst Reconsts
(13)
doc
VLE-D( (1+1) VLE-D (1)))) < 2B 2B Reconet Le (I+1)
(tt)
||+
enc enc
2B Recoosst 3D
1
dec
6 (1) |l + Becomat::
deall
(14)
where the coupling effects in Encoder- Decoder models may lead to instability in learning. The proofs are provided in the Appendix G and
7

---

Published as a conference paper at ICLR 2026
Table 1: Results of node classification (in percent = standard deviation across 10 splits). The best and the runner-up results are highlighted in red and blue respectively in terms of the mean accuracy.
Methods/ Datasets
Heterophilic
Homophilic
Cornell
Texas
Wisconsin
Actor
Cora
CiteSeer
PubMed
Arxiv
Homo Ratio
0,30
0.11
0.21
0.22
0.81
0.74
0.80
0.66
DGI
63.3524.61
60,59
55.4115.96
29.82:0.69
02.29:10.56
71.49:1.14
77443-0.4
70.19:1073
GMI
54.76=5.06
50.49=2.21
45.98=2.76
10.11=1922
12
71.66:00.56
79.83+0.90
69.23-0079
MVGRL
64.30=5.43
62.3845.61
62.37=4.32
30.02=0.70
83.03-10.27
72.75:0.46
79.63+20.38
70.88=00551
BGRL
57.30=5.551
59.19
52.35:4.12
81 81.08:10.17 29.86::0.75
71.59:10:22
09.97:10.36
01.24110.35
GRACE
54.86=6.95
57.57=5.68
50.00=5.83
29.01-0.78
80.08:10.53
71.4110.38
80.1540.34
70.9610.31
GraphMAB
61.93:44.59
67.80:13.37
48.25
01.48:10.56
84.20:10.40
73.20:10.39
81.1010.34
71.75:1.17
DSSL
53.15=1..28
62. 62.11+1..55
4,.29-4.42
28.36+00.65
83.06-+-0.53
73.20+-0.51
81.25-+0.11
70.13++0.25
NWR-GAB
58.64:1566
69.62
69.62:16.6
6.123:1.11
30.17:0.17
83.62::1.11
71.45:12.11
83.4410.92
71.8:10.2
HGRI
77.62+3.25
4..01
36.66+00.55
80.66++0.43
68.56++1.10
80.35+0.58
68.55+00.8
GraphACL
59.33=1144
71.08:2..44
69.22.15.69
30.03:11.03
84.2011.311
73.63:10.22
82.02:40.15
71.72+10.26
S3GCL
81.27+3.67
3.49913
84.56+2..1
36.88-00.38
0..66+00.00
!MUSE
82.00=3.42
83.98+2.81
38.24++.11
16.15+1.211
82.22+-0.21
71.14+0.40
82,90+0.40
70.98+00.2
GREET
73.51=3.115
83.80:12.91
82.94:15.69
15.79:1.04
83.84410.71
73.25
1:144
80.29:11.00
71.09:00.43
HarmonyGNNs Diffi
85.41=1.79 93.2442.77
92. 92.7442.91
37.93-0.55
84. 74.00-5
73,36++0.33
83,42-40.26
71 51.56-0.228
HarmonyGNNs +Prob
85.68=2.11
92.45=3.78
93.13=3.42
15:0.1
84.82200233
73.12+0.28
83.25=0.16
71.97=0.12
reproducible based on the provided codes. And, no hyperperameters were provided for other datasets. We tried our best to tune its hyperparameters in comparisons. S3GCL's official repo is under construction with codes be factored and organized,
MUSE only provides hyperparameters for Cornell their official repo: however. their results
directly report its published performance all datasets excepi Cora, Citeseer, and Pubmed, for which different splits were used with higher label rates in linear probing.
4 EXPERIMENTS
Datasets. We evaluate our model on a suite of real-world benchmarks: four widely adopted homophilic graphs (Cora, CiteSeer, PubMed, and ArXiv) (Sen et al. 2008 Hu et al. 202T) and seven heterophilic graphs (including Cornell, Texas, Wisconsin, Actor, Chameleon, Squirrel and Roman Empure) (Pei et al., 2020, Platonov et al. 2023). These datasets encompass various aspects and span both small-scale and large-scale networks, ensuring our experiments are diverse and comprehensive. Note that, as original Chameleon and Squirrel are known to be problematic (Platonoy let al. 2023), We also provide the homo ratio in the table. Details of these datasets are summarized in Appendix [
their filtered versions to ensure an accurate assessment of model performance.
Baselines. To make fair comparisons with other baselines, we adopt the widely used node classifi- cation task as our main downstream evaluation. We also conduct the experiment of node clustering in Appendix [ Here, we primarily compare against two groups of SSL baselines (see Appendix C
for semi-super comparisons): (1) Traditional SSL methods: DGI (Velickovic et al.. 2019)
GMI (Peng et al.] 2020), MVGRL (Hassani & Khasahmadi] (020)) BGRL (Thakoor et al. 202
GRACE (Zhu et al. 2020b), and GraphMAE (Hou et al. 2022): (2) SSL methods tailored for
heterophilic graphs: DSSL (Xiao et al. 2022). NWR-GAE (Tang et al. (002)). HGRL (Chen et al.
2022), GraphACL (Xiao et al. 2024). S3GCL (Wan et al., 2024). GREET (Liu et al. 2022) and
MUSE Yuan et al. 2023) We also provide comparisons with additional baselines in Appendix
For evaluation, we follow the same protocol all other base- lines (Liu et al. 2022 Yuan et al. 2023) by freezing the trained SSL model and utilizing the gen- erated embeddings for down- stream linear classifier. Note that we reproduce the results of major baselines (Liu et al.] 2022 Hou ctt al.) 2022 Xiao et al.) 2024] Yuan et al. 2023 using the hy- perparameters provided in their official repositories, and
Table 2: Results of node classification three heterophilic graph datasets.
Methods
Chaneleon((ilereel)
Squirel((iltrred) Roman-Gmpire
Homo Ratio
0.24
0.21
0.05
DGI
32.61::2.92
38.78.12.34
0..16
BGRL GRACE
32.55:14.65
1..67
12.16=0.225
35.39+3.58
36.21=2.81
51.58=0.98
MUSE
46.48+t2.51
41.57=1.44
66.26=0.53
GREET
44.67++2.98
19.69+1.885
63.37 1.91
HarmonyGNy GNNs Diffi
47.50-13.27 48.9113.88
44,68 11.68
75.51 10.54
HarmonyGNM GNNs +Prob
45.49:22.13
75.86=0.44
sure that the data split is consistent across all models. However, for those models among them that do not provide dataset- specific hyperparameters, such MUSE, we conducted own fine-tuning. For
8

---

Published as a conference paper at ICLR 2026
other baselines, we derive the results from their original papers baseline papers Yuan et al. 2023
Xiao et al. 2024 Wan et al.) 2024). For hyperparameter settings, see Appendix P
4.1 LINEAR PROBING RESULTS OF OUR HARMONYGNNS
We present the performance comparisons of our HarmonyGNNs with state-of-the-as baseline meth- ods across benchmarks in T and Table The following observations can be made:
Our HarmonyGNNs achieves significant improvement on heterophilic graph datasets, while retaining overall on-par performance on homophilic graph datasets. On heterophilic graph datasets, compared to previous state-of-the-art graph SSL methods, our method outperforms all baselines for example, by 7.12% on the Texas dataset, by 9.6% the Roman dataset, and by 1.27% on Actor. Similar observations hold when compared with previous SL methods; see Appendix Cfoor detailed analysis. On four homophilic graph datasets, our HarmonyGNNs obtains better performance on Cora and Arxiv, on-par performance on CiteSeer and PubMed (with negligible performance drops that within the standard deviations). The overall strong performance shows that our HarmonyGNNs is effective for both types of graphs
The two node-difficulty driven masking strategies in our HarmonyGNNs perform similarly. The Bernoulli sampling based approach (i.e., Harmony +Prob) is slightly better, thanks to its balance between exploration and exploitation. As we shall show in ablation studies (see Table 5). our proposed node- onde-difficulty driven mask strategies are significantly better than the purely random masking strategy.
4.2
k MEAA CLUSTERING RESULTS OF OUR HARMONYGNNS
From the clustering results in the Appendix D our HarmonyGNNs achieves significantly better performance than all baselines, including the state-of-the-as model MUSE, by a large margin on the Texas and Cornell datasets, with improvements of 11.26% % and 12.51 % respectively, Moreover, HarmonyGNN4 slightly outperforms MUSE on Actor due to the complex mixed structural patterns, as introduced in Appendix N also attains comparable performance on Citeseer. These findings are consistent with those observed in linear probing based node classification tasks. Overall, our results demonstrate that HarmonyGNNs can generate high-quality embeddings regardless of the downstream tasks and effectively handle both heterophilic and homophilic patterns, highlighting its strong generalization capability in graph representation learning.
4.3 COMPUTE AND MEMORY COMPARISONS
To verify the efficiency of our proposed approach, we con- ducted an empirical analysis comparing our method to two major state-of-the-at SSL base- lines: GREET and MUSE. As shown in Table 3 we measured memory usage, training time per epoch and total training time until convergence on three large scale datasets, Actor, Roman-Empire and Ogbn-Arxiv, that exhibit a complex mixture of patterns and require substantial computational resources. We utilized the optimal hyperparameters for each respective model. The results show that our MarmonyGGNN, 's memory usage is on par with GREET (with only slight increase for Actor at GB) and remains lower than MUSE. Regarding running time, our HarmonyGNN: requires much less running time of the other two SOTA models while achieving much better performance, as shown in Table [ This efficiency improvement attributed to the fact that both GREET and MUSE employ alternating training strategy for contrastive learning, which clearly highlights the advantages of our HarmonyGNNs.
Table 3: Compute and Memory Comparisons
GPU MEMORY(MB)) |EPoC TIME(S/CPOCII)
TOTAL TIME(S)
Datasets
MUSE GREET OuRs MUSE
GREET
OURS
MUSE GREET OuRS
Actor
8786
4316
8608
0.43
0.56
0.23
53.64
64.32
28.98
Roman
34791
36425
29886
2.47
2,83
2.13
301 87
378,34
280.66
Arxiv
38791
35096
33486
5.31
6.71
4.03
627.32
738.86 476.16
Regarding the total training time until model convergence in the last column, our model is sig- nificantly faster than two baselines. By model convergence time, it means the time at which the best model is selected (out of the total number epochs that is the same for all models). This rapid convergence is attributable to the consistency in the latent space during reconstruction and end-to-end trining-advantee that the baselines do not achieve.
9

---

Published as a conference paper at ICLR 2026
Table 4: Results on Ablating Three Components.
Methods
Cornell
Texas
Wiscomsin
Actor
Roman
Cora
Citesver
Pubmed
Arxiv
Harmory (Full)
85.6882.111
92.45:3.78
93.13:3.42
38,15:0,71
75.86:10.47
84,70:0.56
73.36:0.33
83.42:0.26
71.56::0.25
w/o DynMsk
84.264:2.15
90,1643.51
90.0843.36
36 36.98
74.01
84,10=0.885
72:90-0:53
81,98:0633
71,0040.56
DynMak
81.7811366
85.5914.19
88.5611.56
35.86.1.877
72.87-11.78
83.10
7168-0060
$0.0811.66
70.0240.50
w/o T-S & DynMak & Amn
79.86+3382
82.46+5505
86.98+3.00
34.11+0.92
70.12+1899
78.36=0.80
69.60=0.56
78.05=0.60
08.65+0.58
4.4 ABLATION STUDIES
Ablating Three Components Our HarmonyGNNS has three key components: teacher-student predictive architecture (referred to 7-S), node-difficulty driven dynamic masking strategies (referred to DynMsk), and encoding self-attention (referred to Arm). To evaluate the contribution of each individual component, we conduct an ablation study by progressively removing one component at time. The results are shown in Table 4 and in Appendix E. we can observe,
DynMsk can lead to performance decreases by up to 3,05% across the datasets when removed, which shows the effectiveness of the proposed node-difficllyy driven masking strategies against purely random masking.
T-S predictive architecture also plays a significant role, as performance drops considerably (1% 4.57%) when directly reconstruct the features in the raw input space using latent space features, as done in the encoder-decoder models, leading to a learning space mismatch. This observation is consistent with the theorem proposed in Sec. 3.4
Substituting Arm with a simple MLP also leads to performance drops noticeably. This indicates that attention fusion also help adaptively assign weights to different components, allowing the model to effectively handle various patterns in graphs.
Exploitation Ratio r We also evaluate performance un- der different exploitation ratios across datasets (Table using the probabilistic masking scheme (Eqn. 4 Although the optimal masking ratio varies by dataset, dynamic mask-
Table 5: The effects of (Eqn.
Ratio
Cornell
Actor
Roman
84.56-+2.67
37.13+0.55
74.66-0.68
0.8
85.68+2.11 11
37.93-0.61
75.34=0.45
ing consistently outperforms pure random masking (r=0),
0.5
85,2442.75
38.15:0.71
75.86=0.47
0.3
84.40.1.60
37.7010.78
10.48
underscoring the need for our proposed dynamic masking and its integration with random masking.
0
84.26-42.15
36.98-0.88
74.01 +0.50
More Studies and Analysis More ablation studies covering WGCN impacts (App. the overall masking ratio (App. D) token-selection strategies (App. M are provided in the Appendices.
5 CONCLUSION
In this paper we have presented HarmonyGNNs, a self-supervised framework designed to harmonize heterophily and homophily in GNNs. Through our joint structural node encoding, which integrates lin- ear and non-linear feature transformations with K-hop structural embeddings, HarmonyGNNe adapts effectively to both homophilic and heterophilic graphs. Moreover, our teacher-student predictive paradigm, coupled with dynamic node-difficulty- diificully-bbsedd masking. further enhances robustness by providing progressively more challenging training signals. Comprehensive theoretical analysis and empirical results across benchmark datasets demonstrate that HarmonyGNNY consistently achieves state-of ohethe-rrt performance under heterophilic conditions using both linear probing and k-mean clustering evaluation protocols, while matching top methods on homophilic datasets. These findings underscore HarmonyGNN: 's capability to address the key challenges of capturing mixed structural properties, achieving superior performance without sacrificing efficiency.
ACKNOWLEDGMENTS
This research was partly supported by ARO Grant W911NFII81229 NSF IIS- 1909644, ARO Grant W91 19922 10010, NSF CMMI-2024688, NSF IUSE-201345) and NC State Goodnight Early Career Award. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies endorsements, either expressed or implied, of ARO, NSF or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes not withstanding any copyright annotation thereon.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference machine learning. pp. 21-29. PMLR, 2019.
Kristen M Altenburger and Johan Ugander. Monophily in social networks introduces similarity among friends-of-friends, Nature human behaviour, 2(4))284- 2018.
Mahmoud Assran, Quentin Duval, Ishan Misra, Piotr Bojanowski, Pascal Vincent, Michael Rabbat, Yann LeCun, and Nicolas Ballas. Self-supervised learning from images with a joint-embedding predictive architecture. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 15619-15629, 2023.
Adrien Bardes, Quentin Garrido, Jean Ponce. Michael Rabbat, Yann LeCun, Mahmoud Assran, and Nicolas Ballas. Revisiting feature prediction for learning visual representations from video. arXiv:2404.0847/ 2024.
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of the web conference 2020, pp. 1400-1410, 2020.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph con- volutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3950-3957, 2021.
Jingfan Chen, Guanghui Zhu, Yifan Qi, Chunfeng Yuan, and Yihua Huang. Towards self supe-sueeeeieed learning on graphs with heterophily. In Proceedings of the 31 ACM International Conference on Information & Knowledge Management, pp. 201-211, 2022.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07990 2020.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACI, pp. 4171-4186, 2019.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. Advances in neural information processing systems, 30, 2017.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05999, 2018.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference on Learning Representations, 2019, TtLlhttss///opeeeeviieee wwtprreewwweeeeeeeeeeeeeeee
wwt. snret/forum?iin mmee//oorumidddiigg/ 1-t-HHHL---2999mmmmm 2m9
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, al. Bootstrap your own latent: A new approach to self- celf-supervised learning. In NeurlPS, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 855-864, 864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
William Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159) 2020.
11

---

Published as a conference paper at ICLR 2026
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. In International conference on machine learning, pp. 1116-4126 PMLR, 2020.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In CVPR, 2020.
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. In CVPR, 2022.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. science, 31365786):504--57,, 2006..
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In KDD, 2022.
Zhenyu Hou, Yufei He, Yukuo Cen, Xiao Liu, Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. Graphmae2: A decoding--nhannce masked self-supervised graph learner. In Proceedings of the ACM web conference 2023, pp. 737-746, 2023.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Isc: A large-scale challenge for machine learning on graphs. arXiv preprini arXiv:2103.09433 2021.
Thomas Kipf and Max Welling. Semi-super classification with graph convolutional networks. arXiv preprint arXiv:1609.02900 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXi::1611.07308, 2016b.
Soo Yong Lee, Fanchen Bu, Jaemin Yoo, and Kijung Shin. Towards deep attention in graph neural networks: Problems and remedies. In International conference on machine learning, pp. 18774- 18795. PMLR, 2023.
Bingheng Li, Erlin Pan, and Zhao Kang, Pe-conv: Unifying homophily and heterophily with two- fold filtering. In Proceedings of the AAAI conference on artificial intelligence, volume 38, pp. 13437-13445, 2024.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. In International conference on machine learning, pp. 6437-6449. PMLR, 2021.
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Leurning, pp. 13242-13256. PMLR, 2022.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. IEEE transactions on pattern analysis and machine intelligence, 44(12):10770-00276 2021.
Yixin Liu, Yizhen Zheng, Daokun Zhang, Vincent Lee, and Shirui Pan. Beyond smoothing: Un- supervised graph representation learning with edge heterophily discriminating. arXiv preprint arXiv:2211. 2022.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao Xiao-Wen Chang, and Doina Precup. Is heterophily a real nightmare for graph neural networks to do node 2021.
classification? arXiv preprint
Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: fast and scalable system for fraud detection in online auction networks. In Proceedings of the 16th international conference on World Wide Web, pp. 201-210, 2007.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint
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 Proceed- ings of The Web Conference 2020, pp. 259-270, 2020.
12

---

Published as a conference paper at ICLR 2026
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova, A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv preprint ar arXiv:23022116400 2023.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang. Ming Ding, Kuansan Wang. and Jie Tang. Gec: Graph contrastive coding for graph neural network pre-training. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery data mining, pp. 1150--160, 2020.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 385-394, 2017.
Konstantin Rusch, Benjamin P Chamberlain, Michael W Mahoney, Michael M Bronstein, and Siddhartha Mishra. Gradient gating for deep multi-rate learning graphs. arXiv preprint arXiv:2210.005/1 2022.
Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. Graph neural networks for friend ranking in large-scale social platforms. In Proceedings of the Web Conference 2021, pp. 2535-2546, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Radd. Collective classification in network data. Al magazine, 29(3):93-93, 2008
Chuxiong Sun, Hongming Gu, and Jie Hu. Scalable and adaptive graph neural networks with self-label-enhanced training. arXiv preprint arXiv:2104.09376 2021.
Fan-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In ICLR 20, 2020.
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. arXiv preprint 1iXiv:2006.06588 2021.
Qiaoyu Tan, Ninghao Liu, Xiao Huang, Soo-Hyun Choi, Li Li, Rui Chen, and Xia Hu. S2gae: Self-supervised graph autoencoders are generalizable learners with graph masking. Proceedings of the sixteenth ACM international conference web search and data mining, pp. 787-795, 2023.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, pp. 1067-1077, 2015.
Mingyue Tang, Carl Yang, and Pan Li. Graph auto-encoder via neighborhood wasserstein reconstruc- tion. arXiv preprint 2XXx:2202.00022. 2022.
Xianfeng Tang. Yozen Liu, Neil Shah, Xiaolin Shi. Prasenjit Mitra, and Suhang Wang. Knowing your fate: Friendship, action and temporal explanations for user engagement prediction on social apps. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2269-2279, 2020.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva I. Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. arXiv preprint arXiv:2102.00 045141 2021.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning graphs via bootstrapping. In ICLR, 2022.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
13

---

Published as a conference paper at ICLR 2026
Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2018.
Petar Velickovic, William Fedus, William L Hamilton, Pictro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Guancheng Wan, Yijun Tian, Wenke Huang, Nitesh V Chawla, and Mang Ye. S3gel: Spectral, swift, spatial graph contrastive learning. In Forty-first International Conference on Machine Learning, 2024.
Chun Wang, Shirui Pan, Guodong Long, Xingquan Zhu, and Jing Jiang. Mgae: Marginalized graph autoencoder for graph clustering. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 889-898, 2017.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, Pp. 6861-6871. PMLR, 2019.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: survey, ACM Computing Surveys, 55(5):1-37, 2022.
Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self- supervised learning for graphs. Advances in Neural Information Processing Systems, 35:620-634, 2022.
Teng Xiao, Huaisheng Zhu, Zhengyu Chen, and Suhang Wang. Simple and asymmetric graph contrastive learning without augmentations. Advances in Neural Information Processing Systems, 36, 2024.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.008266, 2018.
Rui Xue, Haoyu Han, MohamadAli Torkamani, Jian Pei, and Xiaorui Liu. Lazygnn: Large-scale graph neural networks via lazy propagation. In International Conference on Machine Learning, pp. 38926-38937. PMLR, 2023a.
Rui Xue, Xipeng Shen, Ruozhou Yu, and Xiaorui Liu. Efficient large language models fine-tuning on graphs. arXiv preprint arXiv:2312.04777, 2023b.
Rui Xue, Tong Zhao, Neil Shah, and Xiaorui Liu. Haste makes waste: A simple approach for scaling graph neural networks. arXiv preprint 4rX1v:2410.05416, 2024.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462, 2021.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 33: 5812-5823, 2020.
Mengyi Yuan, Minjie Chen, and Xiang Li. Muse: Multi-view contrastive learning for heterophilic graphs. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 3094-3103, 2023.
Hengrui Zhang, Qitian WU, Junchi Yan, David Wipf, and Philip Yu. From canonical correlation analysis to self-supervised graph neural networks. NeurIPS, 2021.
Jiahao Zhang, Rui Xue, Wenqi Fan, Xin Xu, Qing Li, Jian Pei, and Xiaorui Liu. Linear-time graph neural networks for scalable recommendations. In Proceedings of the ACM on Web Conference 2024.
2024, pp.
Jiong Zhu. Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33.7793-7804, 2020a.
Yangiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.04133 2020b.
14

---

Published as a conference paper at ICLR 2026
A RELATED WORK
A.1 LEARNING ON HETEROPHILIC GRAPII
Heterophilic graphs are prevalent in various domains, such as online transaction networks (Pandit al. 2007), dating networks (Altenburger & Ugander 2018), and molecular networks (Zhu et al., 2020a). Recently, significant efforts have been made to design novel GNNs that effectively capture information in heterophilic settings, where connected nodes possess dissimilar features and belong to different classes.
Some studies propose capturing information from long-range neighbors from various distance (Li et al. [2222] Liu et al. [202T] [Abu-El Ha-Ha et al.) 2019; [Pi et al. (2020) [Suresh et al.] [202T). For
example, MixHop (Abu-EI-Haija et al. 2019) concatenates information from multi-hop neighbors at each GNN layer. Geom-GCN (Pei et al. (020) identifies potential neighbors in a continuous latent
space. WRGAT (Suresh et al. 2021) captures information from distant nodes by defining the type and weight of edges across the entire graph to reconstruct computation graph.
Other approaches focus on modifying traditional GNN architectures to achieve adaptive message
20200 passing from the neighborhood (Chen et | Chien et al. 2020 Yan et al.; 2021 Zhu et al.,
2020a). For instance, GPR-GNN (Chien et al., 2020) incorporates learnable weights into the
representations of each layer using the Generalized PageRank (GPR) technique, while H2GCN (Zhu
et al. 2020a) removes self-loop connections and employs a non-mixing operation in the GNN layer to emphasize the features of the ego node.
Additionally, some papers approach the problem from spectral graph theory (Luan et al. 2021 Bo ct al., 2021), claiming that high-pass filters can be beneficial in heterophilic graphs by sharpening the node features between neighbors and preserving high-frequency graph signals.
However, these methods still heavily rely on labeled data, which is impractical for real-world datasets due to the significant manual effort required and the necessity of ensuring label quality. Furthermore, they are limited in their ability to effectively learn from the data itself without extensive supervision.
A.2 GRAPH REPRESENTATION LEARNING VIA SSL
As discussed in Section D traditional supervised learning on graphs suffers from performance degra- dation when labeled data scarce. However, collecting and annotating manual labels in large-scale datasets (c.g., citation and social networks) is prohibitively expensive, or requires substantial domain expertise (e.g., chemistry and medicine). Additionally, these models are vulnerable to label-related noise, further undermining the robustness of graph semi-supervised learning. Self superviee learning (SSL) has achieved widespread adoption in the fields of natural language processing (NLP) (Devlin) et al. 2019) and computer vision (CV) (He et al., 2022 Assran et al. 2023). Unlike traditional supervised learning, which relies heavily on large amounts of labeled data, SSL leverages unlabeled data by creating proxy/pretext tasks that exploit intrinsic structures of raw data themselves as labels (such as the next word/token prediction, and masked word/image modeling). This approach not only addresses the dependency on the quantity of labeled data but also efficiently utilizes the inherent patterns and relationships within the data, enabling the development of richer representations with- out need for explicit annotations. Furthermore, they can also encourage the model to learn more robust representations, thereby reducing its sensitivity to noise and/or labeling bias. Building on these advantages, they have shown remarkable promise in various graph representation learning applications.
Because of the advantages mentioned above, self-supervised learning has also attracted significant attention in the field of graph representation learning. Graph SSL approaches are generally divided into two primary categories: graph contrastive learning and graph generative learning. (1) Contrastive Losses in Contrastive learning The model is encouraged to bring representations of similar nodes (or augmented views) closer while pushing apart those of dissimilar nodes; (2) Feature/edge Reconstruc- tion in generative learning: Given a masked input, the model is trained to reconstruct the original node features /predict the existence or weight of edges. However, both approaches become problematic under certain cireumstances. Contrastive learning's 's success hinges relatively complex training strategies, including the careful design of negative samples and a strong reliance on high-quality data augmentation (Grill et al. 2020). However, these requirements are often challenging to meet
15

---

Published as a conference paper at ICLR 2026
in graph settings (Hou et al. 2022), which limits the broader application of contrastive learning in this domain. They can also suffer from representation collapse, where the network converges to a state where all outputs become similar, rendering the learned features uninformative. On the other hand, generative learning methods aim to reconstruct graph data but often face challenges due to reconstruction space mismatch. This arises because the decoder demands intricate design choices and frequently struggles to fully recover the original feature space (Hou et al. 2022] 2023). The decoder can
also potentially inflate the model's parameter count and GPU memory footprint during training. Moreover, these methods are also prone to well-known issues such as training instability, overfitting, and mode collapse.
A.2.1 GRAPH GENERATIVE LEARNING
Generation based methods reconstruct graph data by focusing either the features and the structure of the graph or both. Classic generation- approaches include GAE (Kipf & Welling, 2016b), VGAE (Kipf & Welling 2016b), and MGAE (Wang al.. 2017), which primarily aim reconstruct the structural information of the graph, as well as S2GAE (Tan et al. 2023). In contrast, GraphMAE (Hou et al. 2022) and GraphMAE2 (Hou et al. 2023) utilize masked feature reconstruction as their primary objective, incorporating auxiliary designs to achieve performance that is comparable to or better than contrastive methods.
In the context of generative learning on heterophilic graphs, DSSL (Xiao et al. 2022 operates under
the assumption of graph generation process, decoupling diverse patterns to effectively capture high- order information. Similarly, NWR-GAE (Tang et al. (022) jointly predicts the node degree and the distribution of neighbor features. However, despite these innovative approaches, their performance on node classification benchmarks is often unsatisfactory (Hou et al. 2022).
A.2.2 GRAPH CONTRASTIVE LEARNING
Contrast-based methods generate representations from multiple views of a graph and aim to maximize their agreement, demonstrating effective practices in recent research. For example, DGI (Veličkovid et al. 2018) and InfoGraph (Sun et al.] (020) utilize node-graph mutual information maximization to capture both local and global information. MVGRL (Hassani & Khasahmadi] (2020) leverages graph diffusion to create an additional view of the graph and contrasts node- graph representations across these distinct views. GCC (Qiu et al., 2020) employs subgraph-based instance discrimination and adopts the InfoNCE loss as its pre-training objective. GRACE (Zhu et al. 2020b) and GraphCI. (You) cct al. 2020) learn node or graph representations by maximizing the agreement between different augmentations while treating other nodes graphs negative instances. BGRL (Thakoor et al., 2022) contrasts two augmented versions using inter-view representations without relying on negative samples. Additionally, CCA-SSG (Zhang et al.) (2221) adopts feature-level objective for graph SSL, aiming to reduce the correlation between different views. These contrast-based approaches effectively harness the structural and feature information inherent in graph data, contributing to the advancement of self-supervised learning on graphs.
However, most of these methods are based on the homophily assumption. Recent works have
demonstrated that SSL can also benefit heterophilic graphs. For instance, HGRL (Chen et al. 2022)
enhances node representations on heterophilic graphs by reconstructing similarity matrices to generate
two types of feature augmentations based on topology and features. GraphACL (Xiao et al.
2024
predicts the original neighborhood signal of each node using a predictor. MUSE Yuan al. 2023
constructs contrastive views by perturbing both the features and the graph topology, and it learns a graph heaph-structure-bassee
combiner. GREET (Liu et al. 2022) employs an edge discriminator to separate the graph into homophilic and heterophilic components, then applies low-pass and high-pass pass filters accordingly. However, these methods rely on the meticulous design of negative samples to provide effective contrastive signals. Moreover, although some approaches such GREET and MUSE achieve impressive results, they require alternative training. This significantly increases computational overhead and may lead to suboptimal performance.
Note that, the fundamental goal of contrastive learning is to shape an embedding space in which similar (positive) samples are pulled together while dissimilar (negative) samples are pushed apart.
16

---

Published as a conference paper at ICLR 2026
A.2.3 SELF SUPERVISED LEARNING IN HARMONYGNNS:
Recently, the JEPA paradigm has shown remarkable effectiveness in self- selersueee learning across diverse domains Assran et al. (2023). Motivated by its predictive objective principle, we design HarmonyGNNNs as graph-tailored framework that effectively tackles the challenges discussed above:
No Negative Sampling. Our method requires no negative samples or positive-negative pair construction. This is unique advantage of our model, as highlighted in Sec. [ The student network's ' objective is to predict the teacher's output representations for all nodes, rather than to contrast pairs. We explicitly mention that we eliminate negative sampling, a core component of contrastive learning.
No Contrastive Loss. We do not use contrastive loss functions (e.g.. InfoNCE or NT-Xent). Equ. definee predictive loss in an aligned latent space, NOT contrastive loss. We predict teacher network outputs for ALL nodes (both masked and unmasked), which completely different from contrastive learning's s paradigm of pulling positive pairs together and pushing negative pairs apart.
We also provide a comprehensive theoretical analysis of this predictive architecture.
Adaptive Node Masking. Our node masking is not mere data augmentation or random dropout. We introduce learnable parameters for masked nodes and adaptively select which nodes to mask based on prediction difficulty. This creates more challenging, informative training task compared to uniform random node dropping.
Teacher-Student All-Node Predictive Architecture. Only the student receives masked view; the teacher always observes the full graph. This setup constitutes an information- task, not a dual-random- view contrastive training.
B CHALLENGES OF HETEROPHILY AND HOMOPHILY FOR GRAPH REPRESENTATION LEARNING
In this section, we provide a preliminary analysis of the challenges involved in graph representation learning when handling mixture of both heterophily and homophily patterns (see Tables and in the Appendix (). We examine current methods, including both semi-supervised learning (SL) and self-supervised learning (SSL) approaches.
SL methods: GCN and GAT that focus on low- graph signals work well on the homophilic graph datasets, but suffer from significant performance drop on heterophilic graph datasets. WRGAT and H2GCN address these issues of GCN and GAT, leading to significant performance boost on heterophilic graph datasets, while retaining similar performance on homophilic graph datasets. To understand what the critical part is for performance improvement and to test if high-pass signals indeed play a significant role for them, we test a vanilla MLP which totally ignores the topology of graphs (see Table 6 and simply uses the raw input node features. We can see the simple MLP works reasonably well on heterophilic datasets in comparisons with WRGAT and H2GCN, which supports our earlier statement that traditional message passing produces smoothing operations on the graph, highly relying on the homophily assumption, and highlights that the raw node features play critical role in GNN learning on heterophilic graphs, whereas neighbor information is essential for learning on homophilic graphs. Overall, these observations motivate our joint structural node encoding (Eqn. 6). Mcanwhile, MLP suffers from drastic performance drop on homophilic graph datasets, as expected.
the heterophilic graphs,
Previous State-of-the-ar SSL methods. Those methods (DGI, GMI, MVGRI, BGRL, GRACE and GraphMAE) that are designed for homophilic graphs achieve significant progress in terms of bridging the SSL performance with the SL counterparts on homophilic graphs, but they inherit the drawbacks as GCN and GAT on heterophilic graphs. More recently, methods such as MUSE, GREET and S3GCL make promising improvement, but they do not show significant progress against the MLP SL baseline on heterophilic graphs, especially mixed patterns. Our HarmonyGNN's makes a step forward by significantly improving performance on heterophilic graphs, showing the great potential of graph SSL. (see Table and Table 2
Actor, which exhibits complex
17

---

Published as a conference paper at ICLR 2026
C PERFORMANCE COMPARISONS WITH SEMI-SUPERVISE LEARNING BASELINES
Similar as Table and Table in Section we present the performance comparison with several prominent semi -umi-iieee learning baselines in Tables 6 and Table 7 using the same datasets. The experimental secling--iclludng data splits and labeling ratios for Cora, Citeseer, and Pubmed-an are kept consistent across all experiments. For results of baselines, we use the results reported in (Platonov jet al. 2023 Yuan et al., 2023). For evaluation, we still follow the linear-probing protocol: we freeze each model, generate embeddings, and train downstream linear classifier for downstream node classification. We primarily compare against two groups of semi-supervised baselines:
Traditional supervised learning (SI.) methods: GCN (Kipf & Welling 2016a GAT (Veličkovic ct al., 2017) and simple MLP:
Supervised methods specifically designed for heterophilic graphs: WRGAT (Suresh al. H2GCN (Zhu et al., 20200a), GPR-GNN (Chien et al. (2220) and FAGCN (Bo et al. (021))
2021
Table 6: Results of node classification (in percent + standard deviation across ten splits). The best and the runner-up results are highlighted in red and blue respectively in terms of the mean accuracy.
Methods
Heterophilic
Hocnophllcc
Comell
Wisconsin
Actor
CiteSoer
PubMed
GCN Kipf Welline 60
57,03+:3330 30
60,00:24880 80
56.47=6.55
30.83:0.77
81,50:0.300
70.30:00.7
79.00:0.005
71.74-0.27
GAT Vellckovic & ML.P
59 4643363
61.62+3.78
54,71-6877
28 16-88+1448
83.02+0.19
72.51+0022
7987-003
71.92-0.17
$1.08+7938
81.6245.51
84.31=3.00
38.66+00.94
56.11+0.34
56.91+0.42
71,35+0.05
55.50-0.23
WRGAT Suresh et al. 2021
81,62+3.0
83.6245.50
86.98-3.78
36.53-0.77
81.97+1.50
70.85 188
80.86+00.55
H22CN (Zuu 2000
82.1614.80
84.86266.77
86.67=4.69
3,.86.11003
11.7611.55
70.53&2.01
80.26:10.56
SSL-OOus
HarmanyGNNN +Prob
HiNN +Dimi
8541+1.79 95:24422.77
85.6812.11 92/1523:78
93.13=3/12
92,74-2.91
37.93-40.56
15.1510.71
84,70+0.56
81.52210225
73.12:0.28
33.36-0333
83.42=00.6
83.25220.66
01.56-0.28
71.97-0.12
1 Neither WRGAT nor H2GCN have available hyperparameter configurations specifically tuned for the OGBN-Arxiv dataset their original paper baseline papers.
Table 7: Results of node classification (in percent + standard deviation across ten splits). The best and the rumner-up results are highlighted in red and blue respectively terms of the mean accuracy.
Methods
Chamelenn(fiterel
Squire(((]terred)
Roman- Empire
GCN (Kipf& & Welling 2016a
40.89:14.12
39.47-1147
73.69 74
GPR-GNN (Chin et 2020
39.93:1330
38.95=1.99
64.85:10.27
SL
FAGCN [Bo
41.9011..72
41,08-2.27
65 02:10.0
H2GCN Zhu et
7020a
26.751:3.64
35.10=1.115
60.11:0.52
HarmonyGNNs +Dith
47.50+:3.27
44.68 1.66
75.51 +0.54
SSL-Ours
HarmonyGNNs +Prob
48.91113.86
45.49-2.13
75.86:10.47
From the results, we draw the same conclusion as in our comparison with SSL baselines in the main text: our HarmonyGNNs consistently outperforms all SL baselines on heterophilic datasets latasets-including both classical GNNs and models specifically designed for heterophily- achieving comparable performance on homophilic datasets. For example, HarmonyGNNs surpasses the strongest baselines by 8.38% on Texas, 6. 6.15% Wisconsin 4.41% % filtered squirrel and by 7.01 % on filtered Chameleon, demonstrating its ability to learn complex mixed patterns in graphs. Moreover, when comparing the two masking strategies, probabilistic masking consistently outperforms difficulty-based masking. This suggests that applying a base masking probability to all nodes- rotherrathhr than focusing solely on difficult ones during training- more effectively balances exploration and exploitation. This observation is consistent with the conclusion drawn in the main text.
D PERFORMANCE COMPARISON FOR NODE CLUSTERING
In this section, we present a performance comparison for node clustering. We compare our model with four groups of baseline methods:
18

---

Published as a conference paper at ICLR 2026
Table 8: Clustering results (ACC in percent + standard deviation). The best and runner-up results are highlighted with red and blue, respectively.
Texas ACC
Actor ACC
Cornell ACC
CiteSeer
Methods
ACC
AE (Hinton & Salakhutdinov 2006
50.49:0.01
24.19=0.11
52.19:0.011
58.79:0.19
node2vec (Grover & Leskovec
2016
48.80
25.02=0.04
50.98+0.01
20.76=:0.27
struc2vec (Ribeiro et al.
2017)
49.73=0.01
22.49=0.34
32.68+0.01
21.22::0:45
LINE (Tang al. 20155)
49.40
22.70-0.08
34.10.1..77
28.42:10.88
GAE (Kipf Welling 2016b)
4..02++1.22
23.45- 0.04
43.72+1.25
48.37:10.37
VGAE (Kipf & Welling, 2016b)
50.77+1.87
23.30=0.22
43.39+0.99
55.67+00113
GraphSAGE (Hamilton al. 2017
56.8
23.08=0.29
44.70+2.00
49.28=1.18
SDCN Bo ct al.
2020)
04.04
23.67=0.29
36.9442.00
59.86=1.18
MVGRL Hassani & Khasahmadi 2020)
62.7912.33
28.58=1.03
43.77+3.03
45.67+9.08
GRACE Zhu et al. 20206)
56.99:1223
25.87=0.45
43.55
54.66=
BGRL
Taaooor al. 2021
58.68+1.80
28.20-0.27
55.08
64.27=1.68
DSSL
Xiao et al. 2022
57.43+3.51
26.15=0.46
44.70:2.44
54.32=3.69
HGRL
Chen al. 2022
61.97=3.10
29.79=1.11
60.56
61.14#1.9
MUSE Yuan et al.
2023)
4.379+44.36
31.05=0.72
62.35++2.38
66.03++2.33
HarmonyGNNs +Diffi
7.55
3.72
73.22+3345
65.80+:2.32
HarmonyGNNs +Prob
77.05+2.66
32.10=1.51
74.86+2..99
66.56+3.56
MUSE doesn't 't provide any hyperparameters for node clustering.
Traditional Unsupervised Clustering Methods: AE (Hinton & Salakhutdinoy 2006). node2vec
(Grover& & Leskovec 2016), struc2vec (Ribeiro et 2017). and LINE (Tang et al.] 2013).
Astributed Graph Clustering Methods: GAE (VGAE) (Kipf & Welling 2016b). GraphSAGE
(Hamilton et al. 2017), and SDCN (Bo et al. 2020).
Self Supervised Methods for Homophilic Graphs: MVGRL (Hasaani & Khasahmadi 2020 GRACE (Zhu et al., (2206)) and BGRL (Thakoor et al. 202I).
Self Supervised Methods for Heterophilic Graphs: DSSL. (Xiao al. 2022), HGRI. (Chen et 2022). and MUSE (Yuan et al.) 2023).
Following the same protocol as with other baselines, we freeze the model and use the generated embeddings for k-means clustering. We reproduce MUSE (Yuan al. (002)), it has been proven to be the state-of-the-art model for node clustering. However, the original paper does not provide any hyperparameters for node clustering on any dataset, we perform hyperparameter tuning ourselves. For the other baselines, we report the results from baseline papers (Chen et al.) 2022; Yuan et al.) 2023). The hyperparameters search space can be found in Appendix The results are shown in Table g
From the results, we can achieve the similar conclusions as node classification:
Our HarmonyGNNs achieves significantly better performance than all basclines, including the state- of-the-and model MUSE, by large margin on the Texas and Cornell datasets, with improvements of 1 11.26% and 12.51 %, respectively. Moreover, HarmonyGNNs slightly outperforms MUSE on Actor due to the complex mixed structural patterns, as introduced in Appendix N It also attains comparable performance on Citeseer. These findings are consistent with those observed in node classification tasks. Overall, our results demonstrate that HarmonyGNNg GNNs can generate high- quality embeddings regardless of the downstream tasks and effectively handle both heterophilic and homophilic patterns, highlighting its strong generalization capability in graph representation learning.
Regarding the two masking strategies, probabilistic masking consistently outperforms difficulty masking. This finding aligns with our observations in node classification and can attributed to a better balance between exploration and exploitation.
19

---

Published as a conference paper at ICLR 2026
Table 9: Ablation study on heterophilic datasets. Accuracy (%)
with mean + std.
Methods
Cornell
Texas
Wisconsin
Actor
Roman
Harmony GNNs (Full)
85.68:1..11
92.45=3.78
93.13:3.42
38.15:0.71
75.86:10.47
w/o DynMsk
84.26:2.15
90.16=3.51
90.08:1..6
36.98=0.87
74.01
w/o T-S
82.0942.85
87.96=3.87
89.02:13.12
73.11=1.12 36.08
w/o Attn
82.85+2.33
88.96=4.00
90.23::3.26
37.02=:0.62
73.53+1.36
w/o T-S & DynMsk
81.78:+3.66
85.59=4.19
88.56+3..5
35.86+0.87
72.87
w/o T-S & DynMsk & Attn
79.8641..82
82.46
86.98413600
34.11
10.12
E ABLATION STUDY ON PROPOSED TECHNIQUES
We perform an ablation to illustrate the interactions between our masking strategies and the other model components in Table
Results show that dynamic masking and the teacher-student predictive architecture usually interact: the performance drop from removing both is not simply the sum of their individual effects, under- scoring their interdependence. As noted in the Sec. 3.1 masking strategies are critical to SSL's success.
However, dynamic masking and attention usually operate orthogonally: dynamic masking informs SSL of complex, often unknown topological properties of graphs, while attention fuses multiple filters to capture complex structural patterns. The results in the table also align with our expectations.
F PERFORMANCE COMPARISON WITH RECENT BASELINES
In this section, we present performance comparison of node classification using recent and strong Matte-ofthhearr SL baselines, namely PCNet (Li et al. 2024). AEROGNN (Lee al. 2023). and G (Rusch et al., 2022). We report the results as provided in their respective original papers. Because prior works evaluate different datasets (e.g., G2 only heterophilic graphs, while PC-Conv adopts different splits on homophilic benchmarks), we restrict our comparisons to identical settings for fairness. Therefore, report results for all methods on heterophilic datasets and include AeroGNN on three homophilic datasets, as is the only method evaluated under the same experimental protocol as ours and presented in Table [ As shown in Table I0 and IT Our Harmony achieves state- of-the-art art performance on the Wisconsin, Texas, and Actor datasets, as well as on three homophilic benchmarks, while maintaining competitive results on Cornell. This indicates HarmonyGNin ability to handle complex mixed patterns in graphs.
Table 10: Results of node classification (in percent + standard deviation across ten splits). The best and the runner-up results are highlighted red and blue respectively terms of the mean accuracy.
Cornell ACC
Texas
Wisconsin ACC
Actor ACC
Methods
ACC
PCNet (Li al. 2024)
82.16: 2.70
88.1142.17
88.63= 2.75
37.80 0.64
AEROGNN (Lee et al.
2023
81.244+6.00
84.35+5.20
84.80+3.30
36.57+1.10
GP (Ruch et al. 2022)
86.22+44.90
87.5743.86
87.84+3.49
S3GCL (Wa
2024
81.27+3.67
86.1243.91
84.56+2..1
3..88-0034
HarmonyGNNy +Diffi
1..41+1.779
93.2442.77
92.74+22.91
07.93+
HarmonyGNNs +Prob
85.68+22.11
92.45+3.78
93.13++.42
38.15++0.71
G2 has no reported performance on the Actor dataset.
20

---

Published as a conference paper at ICLR 2026
Table 11:
Results of node classification (in percent + standard deviation across ten splits). The best and the runner-up results are highlighted in red and blue respectively in terms of the mean accuracy.
Methods
Cora
Citeseer
Pubmed
AEROGNN (Lee et al.
2023
83.90 + 0.50
73.20 = 0.60
80.59 + 0,50
Harmony + Dill
84.70 + 0.56
73.36 = 0.33
83.42 + 0.26
HarmonyGNNs + Prob
84.82 + 0.23
73.12 = 0.28
83.25 + 0.16
G PROOF OF GRADIENT-DIFFEREEE BOUNDS
Theorem 2. Consider the optimization of encoder-decoder based graph SSL in Eqn. g and our proposed HarmonyGNNs in Eqn. 2 under the same encoder architecture and following assump- tions/condition::
Gradient Smoothness and Lipschitz Contimuity for the encoder, the decoder. E.g. the encoder E(: Onnc) has gradient @g-smoothness (i.e., each gradient from iteration t to t + changes at most linearly with respect to parameter shifts in Oenc with a coefficient (r) and T.g-iipschizz
continuous with respect to its input and/or parameters (i.e., differences such as E|; (1t)))
El:; e eene)l can be bounded from the above as linear functions of [|0!!e") O with coefficient Lg). Similarly, we have (3p, LD) defined for the decoder.
Boundedness from the above for gradients of the encoder, gradients of the decoder, and reconstruc- tion errors of the combined encoder-decoder.
So, [V (1) < B5, (CDD((((F::) O dec S Bp, and (ID(ELU;)))); - fll S
B Reconst
Strong Convexity for the encoder, the decoder, and the student (and the teacher) in their parameters.
E.g. the encoder E(;; 2 enn) is ptr-slynggyy convex in their parameters Oenes i.e., (t+1) o.nell Similarly,
EVE olit!)) VE O O!t+!)) o(fi) pg -
||@!!t!)
have μ.D defined for the decoder.
Approximation Error. When only unmasked inputs are used, the composite functions, either the encoder-decoder the teacher-student in our HarmonyGNNs, achieve an approximation error CE-D (or cr-s).
Then, the following three results hold:
Linear Convergence Bounds Under Strong Convexity. For our HarmonyGNNs,
[1(((+1) 2
F
||((())
$0112
(15)
For the encoder-decoder models,
- - < (1- (1- min
(n2g, min
(...33333833 [[0(t) 10
(16)
from which can our HarmonyGNNs converges to the optimal solution xx faster than the encoder-decoder counterpart to their optimal solutions O* due to a smaller contraction Sactor (1- <
(1- 3 This implies that HarmonyGNNs can achieve a faster
max [8 (87
convergence.
Proxy Task Loss Bounds under Lipschitz-dependent assumption between the masked graph signal and the raw graph signal, || fll < 8. For our HarmonyGNNs.
||S(J; x) T(f; ()] < Lg 8 er-
(17)
For the eecoder-decoder models.
|| [ & Pene); a S L LD 8 CE-D-
(18)
21

---

Published as a conference paper at ICLR 2026
W.L.O.G., assume CE-D= cr-S, cr-s, our HarmonyGNNs has smaller enror upper bound, indicating that our teacher-student model closer to the optimal solution 8 during training, which in turn implies that its parameter updates more stable and its convergence speed is faster (as shown in the first result above).
Gradient-Difference Bounds in Encoder-Decoder Models Showing Coupling Effects of Purameter Updating,
IVLLEDD(O VLE-D(( s 2B Reconst (BEBD BELLDEE
|10 -
-0! enel
(19)
+ 2B B Reconst 3 3 doc
- -
doe 4B Reconsty
IVLL-D((AL)) VLE-D(O
dee)ll Il $ Reconst 3D Lg [[0 ( (halll
(20)
+ Reconst 3 @
(t+1)
@ + Reconatt
dec
where the coupling effects in In this section, we first provide the proof of the Gradient Difference Upper Bound:
models may lead to instability in learning.
G.1 ENCODER GRADIENT DIFFERENCE UPPER BOUND IN ENCODER- MODEL:
Consider the encoder-decoder model loss function
[ID(((]; LE LF-D(O) (II)B)))) (P((:: Qdte) -11
(21)
Assume the following:
1. Encoder Smoothness:
E(; O ()+ V (E; (1) )| S BE (10 (+++t)
( @thel-
(22)
enc
enc
2. Decoder Gradient Smoothness: For any fixed input (e.g. fa, (T)),
VD(++) (((+))))
V (F(( (0)) enc): @
S 3D |10 (t++1)
0 dec
(23)
+ LDLE [((ttt) ( enell
3. Encoder Gradient Bound:
VE( s Bg.
(24)
4. Decoder Gradient Bound:
V VD(F(; @ BD-
(25)
We use the simplified notation in our proof:
VD (1)
(E(; (1)
BB
(26)
5. Reconstruction Error Bound:
D(E(: ((0) (1)
dec - f < BReconst-
(27)
6. Encoder Lipschitz (with respect to parameters): There exists L > 0 such that
[[ ((++1)) E(: ( < LE [[@(++]] - (!) ll.
(28)
Then, the gradient difference with respect to the encoder parameters between two consecutive iterations is bounded by
VLB-D(O(tt))
VLE-D C1 ene
O en + C2 (t+1)) - (tt)
deall ll + Cs,
(29)
where
C1 = 2B Reconst
BBBDD BELDLE).
C2 = 2Bg 3p BReconst,
C3 = 4Bg Bp B Reconst
(30)
22

---

Published as a conference paper at ICLR 2026
Proof. We start with the expression for the gradient with respect to the encoder parameters at iteration
t
VLE (1) enc/ = 2 ( (E(; - / VE(: (D(:) enc))
(31)
Similarly, at iteration t 1+1
VL 2 (E(; enc Define the difference:
/ VB(; )) VD((+1) (B(; )) (32)
A
V CE (E- - VCE-D((
(33)
Thus,
D | 2 VV ( ( (E( ((tt)))))))))))))))))) ( (E(: (
(34)
[ (E(; f VE(: (lie) VD( [E: (0: ((2c)) ))
To handle this difference, we add and subtract the intermediate term
(E(: 2 V ((te)) VD(++) (B(; (E(t ((t=))))))))) - f|.
(35)
so that
A =
( ) (F ) VD(L+2) (F(;;
(F((; -
+ 2 22VE( (()) )
V [E( ( - (E(, ( (D (E(+: (E(: (((t)))) -5)
+ 2 VVE( ( )
(E(; ((1e)) ( (DI+)((((:0L*t)) ((ttt)) -f) - -(D (B(: - 1) })
(36)
Applying the triangle inequality yields:
A S Ti + T2 + T3,
(37)
with
Ti 2 VE(: Oft+!)) (((:)()t))
((( )
|D (E(: (E( ((t+)))) -
(E(:
(38)
and
Th = (E | |D (E(: )( (D (D(((E(:))))) (E(: ( (E(( (E(:)((tt)))) (
(E(::
s|| -
(39)
and
T3 = B[
VDW
(! ( (Di+D) (((t)))) -f) - (E(;)
- -1) f)} }
(40)
Bounding Ti: By the encoder smoothness assumption,
EE ((++1) (E ( Il s 3E ||0 O ll
(41)
and by the decoder gradient bound,
VD(++) [E(; (E((+)((((:)))) (((+1)))) enc < BD.
(42)
and the reconstruction error bound,
((++1)) E(:; (((+!)))) - f| $ B Reconet
(43)
23

---

Published as a conference paper at ICLR 2026
Thus,
Ti 2 Bn B Rocmsst
[10(he!) 0
(44)
Bounding T2: We now decompose the term
VD(++) (B(:
VD (E(: ((h))
(45)
enc
By adding and subtracting the term VD ((E(; we obtain:
D (B(;; (E(;;((tt)) ))) - VD (B(
(B(;(((;
VD (E(:)
end ((t+)))))))))
(nc))))
(46)
VD O )))
VD(' (B(::
By the decoder's Lipschitz continuity with respect to its input, we have:
(D( E(: (E(:; () - ((E(,O( |||
s LD |E(; (1t))) - E(: (ddd).
(47)
and by the encoder Lipschitz condition, [[ ((=")) E(: ( I LE enc
(48)
Thus, the first term is bounded by:
LpLE |0(tt)) - (
(49)
For the second term, the decoder gradient smoothness gives:
((E(;; (D( BD |1 -
(1
deel
(50)
Thus,
(E(: enc
-10--v/l - (E(:(E( s LDLE ([0(tt)) - @ + 3p 110 - |l-
doe
(51)
Now, using the encoder gradient bound, ( Offc)!l s Bg, and the reconstruction error bound [[D(++1) ( - -Ill < Beconstt we have:
(LOLE ( (((+1)) ( ll + 3D ||0 eddell
Th < 2 Bg B Reconst
(52)
Bounding T3:
T3 = 2 (t) ) (F(; (D -1) (F))((((;
1)
(53)
( (1 (VV 19 )1l - (E(: -f)
-s) -DD()EE (E(: ((!))
)) f
(54)
< 2Bg Bp 2B Reconst
(55)
= 4 Roconst
(56)
Combining Tı, T2 and Ts:
A $ Ti Tg Tss
< 23g BB Reconst
(t++)) (1) 22B B.Be:BReontttln Ln LE 10
(())
ene
2Bg Recomet p |10 (l+1) (1) deall + 4BBBBp B Reconst
[2BRooo Reconst
BBBD BELDLE )
(((tt!)) @ @thlll + 2B B Recomet [10(tt))
(()
dec
4Bg Bp B Reconst-
24

---

Published as a conference paper at ICLR 2026
Define
C₁ 2B Reconst (BEBD + BELDLE)
and C2 = B2
and C3 LBBBBBBRecnet
(57)
Then, the final bound is:
(LL-D(((!tt)) - VLE-D(O S C
[[+ ( + C2 [10 eme
0 ll dee
+ 4Bg BD B Reconst-
dee
(58)
This completes the proof for the encoder gradient difference bound.
G.2 DECODER GRADIENT DIFFERENCE UPPER BOUND
For decoder, assume that:
Decoder Lipschitz Continuity:
[|D(+))) s Ln ||0(t2))
deel
(59)
Decoder Gradient Smoothness:
V V s 3D [|0()t])
10 deell:
(60)
For simpility, also assume 3p-smooth with respect to its input which helps to keep the proof concise:
VD(ff: VD(22 dec))l s BDllfi fell-
(61)
3. Boundedness:
There exist constants BD and Reccost such that
[VD(++1] (F(:;
(F(: ((++)))) S BD,
(62)
ene
and
[ [E:: (E(:: - f S B Reconet.
(63)
enc
4. Encoder Influence:
The encoder is Lg- Lg-Lipschitz with respect to its parameters; that is,
|E( - E(: ( || - Lg [[O(+1]] O eeee |l.
(64)
Then the gradient difference with respect to the decoder parameters satisfies
[VLE-(( (++1)) VCE=D(O
doe) Il - 2B Reconst 3p LE |
(++1)
((()
(65)
ene
enc
2B Reconst.
( @
(t+1)
de + 4 4Bp B Reconst
Proof. We begin with the gradient with respect to the decoder parameters at iteration that
FLE-D(O% 2 (B(: - f v ( (E(::((tee))
(66)
Similarly, at iteration t +
(LE-D(O(tt))) (t+1)) dec
2 (E(; -f VD(++1) (E( ((t+
(67)
Define the difference:
A, VL (L (t((tt VL. (
(68)
Thus,
A (2(Diet1) (E(: (E(: (E(;; 11(+ - VD(++1) (E(; (E(;
(69)
2 ((()) (E(; f (D (B(:)(())
25

---

Published as a conference paper at ICLR 2026
To proceed, we add and subtract the intermediate term
2 (E(: (E(: f) (D(+
(70)
to obtain:
A 2 D(+tt) (E(;; - ( (VD(ct)) (BD: ()) VD(++ (B(:: (nc))
+2( (E(: (((:)))))))))) - -11
- VD (E(: cac
(F(;; +2 (2(1)()))) (B(; ((t)))) - (F(; 51) VD (Fl (F(:(FF(:))))))))) 1
(71)
Applying the triangle inequality, we have:
A TA Tn Te:
(72)
where
Ta 2 [((+)) (B(;;((tt)) - 1l (1((()) (VD (++1) (D(++)))
E((; ((ht"))) - -VD++ (B(; (mc))) )|| (73)
and
TB = (((((D)))( ((t))) - ( (E(::(((a)) (B) VD (E(: O
(74)
enc
and
Tc = (E( - - [[ (E(; - (B (m)))
(75)
Bounding TA: Using the decoder gradient bound, we have
v (B:; (E(+ s BD E(: 0(t:)) Ei: 0 (
(76)
By the encoder Lipschitz property,
E(; E(; S LE [10 -
@ctcll
(77)
Also, by the reconstruction error bound,
D (E(:) - -5| S B Reconst.
(78)
Therefore,
TA S 2B Reconst BD L [[0(tt)) - @
(79)
Bounding TB: For TB, we have
VD(++1) (E(:))
s BD @ - 8ec
(80)
Since:
(B(:)( - f < B Reconst
(81)
Thus, it follows that
TB S 2B Dp (t+1) dec
(82)
dec
Bounding To: We have:
|| (E(:)(((()))+)) (((:)((+)))e)))) - -fl (E(;)))) enc)) 22B
(83)
26

---

Published as a conference paper at ICLR 2026
and
(VD(+) (())))))))) enc
S BD,
(84)
Thus:
To S Recons!!
(85)
Combining TA, TB and Te: We then have:
gg S T + TB + Tc
S Reconst BD Lg |0 10(ttt) - - enell + 2B Reconst
(t+1) dec
+ ABDBBecona
(86)
This completes the proof for the decoder-side gradient difference bound.
H PROOF OF PROXY TASK LOSS BOUNDS
Theorem 3. Proxy Task Loss Bounds under Lipschitz-dependent assumption between the masked graph signal and the raw graph signal, I - fll S 8. For our HarmonyGNNs.
|S(F: 1) - [f; ; VIll S LE ETT-
(87)
For the encoder-decoder models,
[ID(E(F; T Penc): dee) fll LE Ln 6 + CE-D-
(88)
W.I.O.G., G.G assume D GT-S, our HarmonyGNNs has a smaller error upper bound, indicating that our teacher-studen model is closer to the optimal solution tp during training, which in turn implies that its parameter updates are more stable and convergence speed is faster (as shown in the first result above).
Proof.
(EFF: Odee) flll (de)
(89)
+ +II[(F.[J: omn)) Occc) (FF(F Penc); O
EE-D + LELDIlf fll
(90)
<EED + LE LD 8
(91)
||((A:0) -(::))())1)) ||S(]: - (15))))))-((()0)((((()0)))))) T(F:))I
(92)
< LE -
(93)
$ Lgd + 4T-
(94)
1 PROOF OF LINEAR CONVERGENCE BOUNDS
I.1 ENCODER-DECODER
Theorem 4. Linear Convergence Bounds Under Strong Convexity. For our HarmonyGNNs.
2
(++1)
+1112 <
E
|
2111
(95)
B
27

---

Published as a conference paper at ICLR 2026
For the encoder-decoder models,
[100+11) - 00 (1- min(ug..tr max 1 (B)B))
|10(0)-011 -011
(96)
HarmonyGNNs converges to the optimal solution & faster than the from which counterpart to their optimal solutions O' due to a smaller contraction factor min((e..1)))) This implies that HarmonyGNNs can achieve a faster convergence.
encoder-decoder
max (F
Proof. From above, We can get the smoothness assumptions:
VE ((tt!) VE(: S 8E ||0
O ll
ene
(97)
and
- S BB [|0(tt")
-0
dee
(98)
Besides, we also assume strong convexity:
1. pg-strong convexity of encoder:
(VE(J; TE((; ( - O encl 2 pr
10(
O(t)
ene 1I?
(99)
2. PD-strong convexity of decoder:
O VD O (ld)
(t) dee
2 HD
||0 - -
(100)
dec
When combining an encoder and decoder, the overall strong convexity constant is often at most min(uE, PD) in a conservative sense.
Then for the mocoder-dccoddr model, we define 0 (Dener Odee) for simplicity, where 0 is used as a generic parameter vector for the entire model. The gradient descent update is given by:
Oc+1 = 0, - LE
(101)
Following the gradient analysis:
110++1 1- [0 1/ LLVLED 11
(102)
||0 - 0" 1 (LL Or 00) + (VV
(103)
For (VL),(0)) 0*):
Since justtrongly convex, the following inequality holds:
L(O') 2 L(0) + VT.(O) (0' - 0) 11
2 1110 - 0
(104)
Let 0* denote the global optimum of L(0), i.e.,
0" = arg min L(0).
(105)
then:
VL(0") 0.
(106)
Substituting 0' - -0 into the strong convexity definition, we obtain:
L(O") 2 L(O.) - VL().) (0" 0.) 1 110 0.112.
(107)
28

---

Published as a conference paper at ICLR 2026
Rearranging the terms, have:
L(0") I(O.) 2 (I(())) (6" 0,) + 1
2 110 02l1
(108)
Since 8* is the global minimum, it follows that L(0*) - L(O)). Therefore:
L(0") L(0,) s 0.
(109)
Combining the two inequalities:
2 VI(()) (0" -0,) 1 "110" -2112.
(110)
VL(0)) 6*) 1 2 00 1-
(111)
In general, the encoder and decoder each st--tnongly convex and up-strongly convex with respect to their parameters, respectively, then the composition can only guarantee a smaller strong convexity coefficient min(Ne, in the worst case, then:
(VLED(O.),0, 0: 0*) (in(pE,DD)]00 0*1|²
Similarly, for [|VEE(())] since VLED((*) 0, then
VLLD (0) |VLED(() (LED(! I B 110 0-
(112)
[0)) 3² ||0 1
(113)
In Saccoer-Decoodee we have two sets of parameters (Denc: tdec) and we typically argue that
LED(O) is at most (3g-smooth) x (Bn-smooth),
(114)
For simplicity, let (0) is max(3g, smooth:
[V z (5)x833333110. - 0-11
Then we can get:
|10++1 - 111 s (1 2n mininnue (D) + 172 max (.xx)))))))))))))))))))))))))))) (3)) - 1-12
(115)
We want to find the minimum of (1 - min(n + n? m (2)):
2 min( + 2n max 0
(116)
min(HE MDD) max(33,
(117)
With optimal learning rate 17
min(we,ap) max()2.0p) we obtain:
min(u² uz)
| 1 (1
max (3) 010, - 1-
(118)
29

---

Published as a conference paper at ICLR 2026
1.2 HARMONYGNNS:
For our method, analyzing one step:
|| -0 = |1(0; iiV LTV().)) 11
(119)
Similarly above, with optimal learning rate ij = /E:
1 2-12 < (1
P. 11
(120)
B
Clearly, our proposed method achieves better convergence because:
min KD)
(121)
B
max (3% 8
This inequality holds because:
1. p 2 min ( (z))
2. 3 S max max (D)
Obviously, model yields faster convergence rate.
J PERFORMANCE PLOT
In this section. we present a radar plot to illustrate the advantages of our proposed HarmonyGiNNs compared to major baselines across all datasets as shown in Figure This fig- ure clearly demonstrates our model's effectiveness.
K WEIGHTED GCN VERSUS VANILLA GCN
In this section, we compare our proposed Weighted GCN (WGCN) against the standard GCN as low- pass filters for capturing homophilic patterns graphs. Specifically, we evaluate both models across different numbers of layers e, l" and hidden-dimension sizes on datasets of varying scale-Coreed Actor, and Coman-Empire and report the results in Table
From the results, we can see that when the dimension of the model is smaller, WGCN consistently outperforms vanilla GCN. This is because WGCN can adapt message passing flexibly, assigning higher weights to similar neighbors while downweighting dissimilar ones in heterophilic regions. However, when heavier models are used, GCN can achieve comparable and even better performance than WGCN, We conclude that this is because the deeper GCN has sufficient learning capacity, whereas the larger number of learnable parameters in WGCN potentially causing overfitting. Ad- ditionally, we observe that WGCN still provides advantages when the graph has complex mixed patterns, such as in the Actor and Roman -mmmire datasets.
In summary, when computational resources limited and graphs exhibit complex structures, WGCN can learn better representations. These findings prove the effectiveness of our proposed WGCN approach.
L OVERALL MASKING RATIO R
In this section, we provide an analysis of the overall masking ratio R, which determines the total percentage of nodes being masked for the student model during training. We present the results in Table 13 From the results, can observe that different datasets require different optimal masking ratios, which is consistent with our conclusions the main text. For datasets with more complicated patterns, such Actor and Roman Empire, smaller masking ratio proves beneficial. This prevents excessive node masking, which would otherwise prevent the student model from effectively capturing the teacher model's representations.
30

---

Published as a conference paper at ICLR 2026
Performance Comparison Across All Datasets
HarmonyGNN
Cornell
HGRL
GraphACL
MUSE
GREET
Texas
Rubmed
0.4
Wisconsin
Ctteseer
Actor
Cora
Figure 4: Performance comparison across all datasets
Table 12: The effects of WGCN over Vanilla GCN
Cornell
Actor
Roman-Empir
WGCN
GCN
WGCN
GCN
WGCN
GCN
(=1, h=32
84.8612.48
83.7842.71
37.00
36.6710.78
73.36=0.41
72.83-1033
[=2, (==3, h=32
85.03+2.00
84.32+2.31
36.95+00.5 37.23+0.77
74.02-0.38
73.85+0.57
8-2, h=256
85.68 15.40:11.79
37.83+0.75 37.8010.56
74.32-1.48
74.6410.56
(=2, 8'=3, h=256
85.21=1.889
85.2142.01
38.1510.71
38.10-0.53
75.86=0.47
75.60=0.57
M ENCODED TOKEN SELECTION STRATEGIES
In this section, present study on the token selection strategies mentioned in main text. Specifically, we evaluate four strategies:
Directly selecting the first token Xo,C
Taking the mean across all tokens
Taking the maximum across all tokens
Performing hierarchical token fusion described in Eqn. 7
Our results demonstrate that the proposed hierarchical token combination performs best among all strategies when dealing with large, complex graphs. This is because it can combine the similar encoded tokens first and dynamically learns their combination weights in coarse-to-fine manner, which demonstrates the effectiveness of this design. Simply selecting the first encoded token results in significant information loss and performs worse than basic aggregation methods like mean and
31

---

Published as a conference paper at ICLR 2026
Table 13: The effects of the overall masking ratio R (Eqn.
Ratio R
Cornell
Actor
Roman-Empire
1
84.9813.01
36,88-10,98
73.6520.47
0.8
85.6812.11
37.6
74.40=:.42
0.5
85.26+2.25
38.15:0.71
75.86+10.47
0.3
84.86+1.93
37.53+0.56
75.32++034
max pooling, as evidenced in the Roman Empire dataset. However, for smaller datasets, simpler selection methods are sufficient since hierarchical learning can potentially cause overfitting.
In our proposed method, the selection of these strategies is treated as hyperparameter that can be easily adjusted based on the specific properties of the dataset. This flexibility highlights the adaptability of our model design to different graph scenarios.
Table 14: The effects of different token selection strategies (Eqn.
Cornell
Actor
Roman-Empire
First Token
85.68
37.00=1..2
72.46=0.57 75.12-0.40
Mean
85.32++2.53
37.30+0.72
Max
85.26+-2.88
37.56+00.88
74.87-0.79
Hierarchical
84.98:22.22
38.15::0.71
75.86=0.47
N HETEROPHILY AND HOMOPHILY IN GRAPHS
N.1 DATASETS DESCRIPTIONS
We provide a basic introduction of heterophilic datasets used in our experiments (Pei et al. 2020 Platonov et al. 2023) and present T-SNE visualizations of four representative examples Cornell, Texas, Wisconsin, and Actor to illustrate their complex mixing patterns.
WebKB. The WebKB1 dataset is a collection of web pages. Cornell, Wisconsin and Texas are three sub-datasets of it. Nodes represent web pages and edges denote hyperlinks between them. The node features are bag-of-words representations of the web pages, which are manually categorized into five classes: student, project, course, staff, and faculty.
Actor Co-occurrence Network. This dataset is derived from the film-director catorracto--veeee writer network. In this network, each node corresponds actors co-occur on the same Wikipedia page. The node features consist of key keywords extracted from these Wikipedia pages, and the actors classified into five categories based the content of their pages.
actor, and edge between nodes indicates that the
Roman- Empire. The Roman-empire dataset built from the full text of the English Wikipedia article on the Roman Empire (=22.7K 7K words). Each word is a node, with edges connecting words that are adjacent in the text or linked by a dependency relation. Nodes are labeled by their ofrt-of-speech roles (17 most frequent plus "other"), and node features are 300-dimensional fastText embeddings. The resulting graph extremely sparse and chain-like (avg. degree =2.9, diameter =6,824) and exhibits strong heterophily, making it challenging benchmark for GNNs to capture long-range and syntactic dependencies.
Wikipedia Network. Chameleon and squirrel are two page-page networks specific topics in Wikipedia. Nodes represent web pages and edges represent mutual links between pages. Node features correspond to informative nouns appearing in the Wikipedia pages. These datasets used for node classification tasks, where pages are classified into five categories based on their average monthly traffic.
Upon closer examination, researchers (Platonov et al. 2023) identified a critical flaw in these widely- used benchmark datasets: substantial portion of nodes duplicates with identical regression
32

---

Published as a conference paper at ICLR 2026
targets and neighborhood structures. In the squirrel dataset, 57% of nodes (2,978 out of 5,201) duplicates, while in chameleon, duplicates account for 61% 31% of nodes (1,387 out of 2,277). These duplicates create problematic train-test data leakage, they appear across training, validation, and testing splits.
To remedy this issue, researchers developed filtered versions by removing nodes that had no incoming edges and shared both the same monthly traffic value and outgoing edge set with another node the graph. Testing on these filtered datasets revealed dramatically different results many models that performed exceptionally well on the original datasets showed significant performance degradation, and the relative rankings of different models changed substantially. This finding suggests that previous evaluations based on the original datasets were unreliable, as models may have been exploiting data leakage rather than learning meaningful graph patterns.
N.2 PATTERN ANALYSIS
These three datasets are relatively small and exhibit high heterophily. In the raw feature visualizations (left), nodes of different labels are highly mixed, with significant overlap between categories. After applying HarmonyGNNs, the right-side visualizations reveal a more distinct clustering structure, where nodes of the same label are more compactly grouped. For instance, in Texas and Cornell, purple nodes appear more concentrated, and red nodes are better distinguished from other categories, indicating that the model effectively captures the structural pat- terns. In Wisconsin, the node clusters become more distinguishable, with clearer boundaries between different categories. This demonstrates the model's 's ability to learn meaningful representations that enhance classification and clustering tasks.
Wisconsin, Texas and Cornell:
Actor: This dataset contains a large number of nodes with an imbalanced label distribution (with red nodes being dominant). In the raw feature space (left), although red nodes are mainly centered, other colored nodes remain scattered without clear boundaries. Notably, the outer ring of nodes effectively represents the mixed structural pattern, which accounts for the relatively low accuracy observed in both node classification and node clustering tasks across all models. In the HarmonyGNN GNNS embedding space (right), red nodes more tightly clustered, while nodes of other labels form relatively well-separated subclusters. This suggests that the model improves class separation and enhances discrimination among different node categories.
Overall, these visualizations demonstrate that in the HarmonyGNNs embedding space, nodes of different categories form more distinguishable clusters compared the raw feature space. This intuitively explains why our model achieves great performance in both node classification and node clustering tasks. Furthermore, highlights the model's strong representation learning capability across various graph structures, whether homophilic or heterophilic.
O DATASETS STATISTICS
We provide the deatils of datasets used in our experiment here. The homophily ratio, denoted as homo, represents the proportion of edges that connect two nodes within the same class out of all edges in the graph. Consequently, graphs with a strong homophily ratio close to 1, whereas those with ratio near 0 exhibit strong heterophily.
K(u, v) E E Vu yo
homo
(122)
[
P HYPERPARAMETERS
Our model's hyperparameters tuned from the following search space:
Learning rate for SSL model: {0.01, 0.005, 0.001}.
Learning rate for classifier: (0.01, 0.005, 0.001).
33

---

Published as a conference paper at ICLR 2026
HarmoryGNNs Embeddings
Raw Features
Figure T-SNE visualizations of Wisconsin datasets.
Raw Features
HarmonyGNNs Embeddings
Figure 6: T-SNE visualizations of Texas datasets.
Weight decay for SSL model: (0, x 10-3 5x 10-3 8x 10-3, 1 10-1,
5x 1 10 8x
10 10-1). ').
Weight decay for classifier: (0, 10-4 5x 10-5).
Dropout for Filters: {0.1, 0.3, 0.5, 0.7, 0.8).
Dropout for Attention: (0.1, 0.3, 0.5, 0.7, 0.8).
Dimension of tokens: {128, 256, 512, 1024, 2048, 4096).
Hidden units of filters: {16, 32, 64, 128, 256, 512).
Total masking ratio: {0.9, 0.8, 0.5, 0.3, 0.1, 0).
Dynamic masking ratio: (0.9, 0.8, 0.5, 0.3, 0.1, 0}.
34

---

Published as a conference paper at ICLR 2026
Raw Features
HarmonyGNNs Embeddings
Figure 7: T-SNE visualizations of Cornell datasets.
Raw Features
HarmoryGNNs Embeddings
Figure 8: T-SNE visualizations of Actor datascts.
Momentum: {0.9, 0.99, 0.999).
Q
THE USE OF LARGE LANGUAGE MODELS (LLMs)
We used Large Language Models (LLMs) solely to refine the writing.
35

---

Published as a conference paper at ICLR 2026
Table 15: Datasets statistics.
Datasets
Node
Edges
Feats
Classes
Homo
Cornell
183
295
1,703
0.30
Texas
183
309
1,703
0.11
Wisconsin
251
499
1,703
0.21
Actor
7,600
29.926
932
0.22
(Fittre)
890
17708
2325
0.24
(iiteee()
2223
93996
2089
0.21
Roman-Empire Empire
Roman
22662
32927
300
18
0.05
Cora
2708
10,556
1,433
0.81
CiteSeer
3,327
9,104
3,703
0.74
PubMed
19,717
88,648
500
0.80
Ogbn-Arxiv
169343
1166243
128
40
0.66
36


Reviews:
[{"review_id": "9Z8jBIBv3K", "reviewer": "Reviewer_VdwQ", "summary": "This paper proposes a unified SSL framework for both homophilic and heterophilic graph. The framework is built on a teacher-student predictive architecture, where the student network achieves representation harmonization via joint structural node encoding. The experimental results show the effectiveness of the proposed framework.", "questions": "see Weaknesses.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1.\tThe idea of : teacher–student predictive architecture is interesting, which eliminate the need for complex negative sampling.\n\n2.\tThe author provides theoretical analysis of the proposed method, although the analysis is really complicated and hard to understand.\n\n3.\tThe proposed method outperforms existing SSL methods on heterophilic graph datasets.", "weaknesses": "1. Besides the teacher-student predictive architecture, the overall novelty is limited and the design of the student network is somewhat engineering (e.g., Learning Multi-Head Self-Attention and Fusing and Selecting Tokens Hierarchically as SSL Node Encoding). The motivation of these strategies is unclear.\n\n2. The overall framework involves huge memory and computation overhead. It is suggested to analyze the memory complexity and computation complexity in detail. The authors perform computation and memory comparisons in Section 4.3. It would be better to perform similar experiments on more datasets (i.e., homophilic graphs and large-scale graphs).\n\n3. Many details are missing. For example, in Section 3.1, the authors claimed that the teacher network is not trained. It is not clear how to get the parameters of the teacher network. Moreover, the architecture of the teacher network is also not introduced.", "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": "8xtjjANisN", "reviewer": "Reviewer_6ntd", "summary": "The paper introduces a unified SSL framework addressing the challenge of learning on graphs with mixed structural patterns. It achieves this through Representation Harmonization (joint structural node encoding with WGCN and self-attention) and Objective Harmonization (a predictive teacher–student architecture with dynamic masking). The method effectively balances homophilic and heterophilic signals, showing strong performance across benchmarks. Overall, H3GNNs offers a significant advancement in adaptive, structure-aware graph self-supervised learning.", "questions": "See weakness", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The strength of this paper lies in its innovative unification of homophily and heterophily modeling within a self-supervised graph learning framework. The authors identify a key limitation in existing GNN and SSL methods—the inability to handle mixed structural patterns—and propose a comprehensive solution (H3GNNs) that achieves both representation harmonization and objective harmonization. It provides both stability and adaptability in learning from complex graph structures. Moreover, the paper is well-written, with extensive experiments showing state-of-the-art performance on heterophilic and mixed graphs, demonstrating strong generalization and interpretability.", "weaknesses": "The paper lacks experiments on large-scale graphs and comparisons with more recent or relevant algorithms, limiting its scalability claims. Efficiency analysis is narrow, involving few baselines without clear justification for their selection as representative methods. Broader comparisons and rationale would strengthen the empirical evaluation and conclusions.", "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": "woVktQuJ5J", "reviewer": "Reviewer_RngT", "summary": "The paper proposes H3GNNs, a self-supervised framework aimed at unifying the learning of homophilic and heterophilic graphs within a single model. It introduces a teacher–student predictive architecture with dynamic node-difficulty-based masking to create informative self-supervision signals, and a joint structural node encoding module that fuses linear, nonlinear, and structural features through a Weighted GCN and Transformer-based hierarchical fusion. Experiments on multiple benchmark datasets show that H3GNNs outperforms prior self-supervised GNN models.", "questions": "1.Could the authors provide a clearer explanation or visualization of how the WGCN, MLP, linear projection, and transformer fusion interact? It is not obvious which module primarily contributes to handling heterophily versus homophily.\n2.Why are exactly four “tokens” used in the joint encoding, and why is the fusion order fixed? Have the authors tried using different token numbers or fusion sequences, and how sensitive is performance to these choices?\n3.How are the learnable edge weights in WGCN regularized or constrained to prevent degenerate solutions (e.g., trivial scaling or sparsity collapse)? Are they shared across layers or trained independently?\n4.The dynamic masking variants show small numerical differences. Can the authors provide more analysis (e.g., convergence behavior, difficulty distribution, or qualitative examples) to demonstrate why dynamic masking is preferable to random masking?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The paper shows reasonable originality by combining teacher–student predictive learning, dynamic masking, and weighted structural encoding to address both homophily and heterophily in self-supervised GNNs.\n2.The technical quality is solid, with extensive experiments and consistent gains across benchmarks, though some design choices and analyses lack depth. \n3.The paper is clearly written overall.", "weaknesses": "1.The roles of WGCN, MLP, linear projection, and transformer fusion are not clearly separated or analyzed; it is unclear how each module contributes to handling homophily and heterophily individually.\n2.The dynamic masking update relies on previous loss values, yet the paper does not specify how frequently these scores are recomputed or how the warm-up and exploitation phases are scheduled.\n3.The efficiency comparison table does not include information about the hardware platform, GPU type, or framework version, so the claimed improvements in training time and memory cannot be verified.\n4.The paper lacks systematic sensitivity analysis for critical hyperparameters like the number of WGCN layers.\n5.On homophilic datasets, the reported improvements are minor and may fall within variance, yet no statistical tests or confidence intervals are presented to confirm significance.\n6.The theoretical analysis assumes strong convexity and smoothness for deep GNNs, which are unrealistic; hence the derived convergence results have limited practical meaning.", "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": "OuXdTFD4NF", "reviewer": "Reviewer_Gv2M", "summary": "This paper introduces HOD-GNN, an architecture that enhances GNN expressivity by computing derivatives of a base MPNN with respect to input node features and using these derivatives as additional structural information to input to the second GNN.  The paper proves that k-HOD-GNN can approximate k-OSAN subgraph GNNs, which is strictly more expressive than MPNNs with random walk structural encodings, and achieves favorable computational complexity for sparse graphs with shallow base MPNNs by exploiting an efficient message-passing-like derivative computation algorithm. Empirically, HOD-GNN consistently ranks in the top two tiers across seven benchmarks.", "questions": "See Weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The paper presents a fresh perspective on enhancing GNN expressivity through derivatives. The intuition is clearly explained through the connection to marking-based GNNs and Taylor expansion. I think the presented approach is conceptually elegant. \n\n2. The theoretical analysis provides a complete expressivity characterization by proving k-HOD-GNN approximates k-OSAN subgraph GNNs while offering constructive separation examples that precisely identify when the method is efficient.\n\n3. The three-component pipeline from base MPNN, intermediate derivative computation, and the downstream GNN is clear and easy to follow.", "weaknesses": "1. The claimed \"inductive bias toward derivative-aware representations\" is mentioned but never explained.\n\n2. The triangle counting example in the Motivation section is thin as a driver of the whole method. This motivating toy showing first-order derivatives recover triangle counts uses a very special linear stack, i.e., identity activations, and does not show whether derivatives remain informative for typical non-linear, normalized, or regularized MPNN on real tasks. Thus, it’s illustrative but not compelling evidence that derivatives are broadly the right signal. Also, in the theoretical analysis, the separation beyond k-WL depends on analytic activations that  iss fine for softplus/tanh, but not ReLU.\n\n3. Flattening $D^{out}$ could be large in practice. \n\n4. For $U^{node}$, a 2-IGN is powerful but can be heavy. The paper claims scalability via sparsity, but constants can bite (derivative channels $\\times$ feature dims $\\times$ orders). \n\n5. I didn’t see normalization for $D^{out}$ or $D^{(T)}$. Some stabilization may be necessary because  derivatives can vary wildly with feature scaling.\n\n6. I’m confused about the rationale for computing two derivative tensors that target different functions. Specifically, $D^{(T)}$ computes derivatives of the final node embeddings, while $D^{out}$ computes that based on the graph-level output. Why is it necessary to encode both, rather than using only node-level derivatives with an invariant head, or using only graph-level derivatives if the target is graph classification?", "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 (Poster)