Decoupled Self-supervised Learning for Graphs
Authors: Teng Xiao
Zhengyu Chen
Zhimeng Guo
Zeyang Zhuang
Suhang Wang
Venue: NeurIPS 2022 Accept (2022)

Abstract: This paper studies the problem of conducting self-supervised learning for node representation learning on  graphs. Most existing self-supervised learning methods assume the graph is homophilous, where linked nodes often belong to the same class or have similar features. However, such assumptions of homophily do not always hold in real-world graphs. We address this problem by developing a decoupled self-supervised learning (DSSL) framework for graph neural networks. DSSL imitates a generative process of nodes and links from latent variable modeling of the semantic structure, which decouples different underlying semantics between different neighborhoods into the self-supervised learning process. Our DSSL framework is agnostic to the encoders and does not need prefabricated augmentations, thus is flexible to different graphs. To effectively optimize the framework,  we derive the evidence lower bound of the self-supervised objective and develop a scalable training algorithm with variational inference. We provide a theoretical analysis to justify that DSSL enjoys the better downstream performance. Extensive experiments on various types of graph benchmarks demonstrate that our proposed framework can  achieve better performance compared with competitive  baselines.

Decoupled Self-supervised Learning for Graphs
Teng Xiao', Zhengyu Chen', Zhimeng Guo', Zeyang Zhuang', Sauaang Wang' The Pennsylvania State University, *Zhejiang University, TTogji University (tengxiao, zhimeng, szw494) @psu edu, chenzhengyu@zju. edu. cn zeyangzhuagg03156gma. com
Abstract
This paper studies the problem of conducting self-supervised learning for node representation learning on graphs. Most existing self-supervised learning methods assume the graph is homophilous, where linked nodes often belong to the same class have similar features. However, such assumptions of homophily do not always hold in real-world graphs. We address this problem by developing a decou- pled supervupereieed learning (DSSL) framework for graph neural networks. DSSL imitates a generative process of nodes and links from latent variable modeling of the semantic structure, which decouples different underlying semantics between different neighborhoods into the self self-supervised learning process. Our DSSL frame- work agnostic the encoders and does not need prefabricated augmentations, thus is flexible to different graphs. To effectively optimize the framework, we derive the evidence lower bound of the celf-superviee objective and develop a scalable training algorithm with variational inference. We provide theoretical analysis to justify that DSSL enjoys the better downstream performance. Extensive experiments on various types of graph benchmarks demonstrate that our proposed framework can achieve better performance compared with competitive baselines.
Introduction
Graph-structured data is ubiquitous in the real world, such as social networks, knowledge graphs, and molecular structures, In recent years, graph neural networks (GNNs) [16, 27, 52, 7, 60] have been proven to be powerful in node representation learning over graph-structured data. Typically. GNNs are trained with annotated labeled data supervised manner. However, collecting labeled data expensive and impractical in many applications. especially for those requiring domain knowledge, such as medicine and chemistry [71, 20). Moreover, supervised learning may suffer from problems of ues-transferraale, over-fitting and poor generalization when the task labels scarce [10, 64).
Recently, self-supervised learning (SSL.) provides promising learning paradigm that reduces the dependence manual labels in the image domain [5, 12, 13, 6). Compared to image data, there are unique challenges in designing sule-super learning schemes for graph-structured data since nodes in the graph are correlated with each other rather than completely independent, and geometric structures are essential and heavily impact the performance in downstream tasks [27]. A number of recent works [53, 18, 64, 69, 48, 65, 45] have studied graph self-supervised learning and confirm that it can learn transferrable and generalizable node representations without any labels. Typically, there two main self suff-superi schemes to capture structure information in graphs [53, 64, 45]. The first scheme is reconstructing the vertex adjacency following traditional
methods [26, 14, 17, 16, 46), which learns encoder that imposes the topological closeness of nodes in the graph structure on latent representations. The key assumption behind this scheme is that neighboring nodes have similar representations [53, 46]. However, this assumption over-emphasizes proximity [53, 64, 47] and does not always hold true for heterophilic and non-homophilous (mixing) graphs. In comparison, contrastive learning methods [53, 18. 64, 69, 48, 65] construet two graph
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(a) homophilous pattern.
(b) heterophilic pattern.
(c) mixing pattern.
Figure I: An illustration examples of different types graphs. Nodes with similar labels typically have similar neighborhood patterns in all types of graph. This assumption is general than the standard homophily assumption where nodes with similar semantic label typically be linked with each other.
views via the stochastic augmentation and then learns representations by contrasting views with infor- mation maximization principle. While these contrastive methods can capture structure information without directly emphasizing proximity, their performance relies on topology augmentation [70, 50]. Importantly, conducting augmentation for non-homophilous graphs is relatively difficult since linked nodes may be dissimilar, and nodes with high similarities might be farther away from each other. Hence, the above problems pose an important and challenging research question: How to design an effective self-supervised scheme for node representation learning in non-homophilous graphs?
We approach this question by taking advantage of neighborhood strategies of nodes for the self- supervised learning on non-homophilous graphs. Our key motivation is that nodes with similar neighborhood patterns should have similar representations. In other words, we expect that the neighborhood distributions can be exploited to distinguish node representations. Our assumption is more general than the standard homophily assumption as shown in Figure 1. For instance, while the gender prediction in common dating networks lacks homophily [1], neighborhood distribution is very informative to the node gender labels, i.c., nodes with similar neighborhoods are likely to be similar.
While the motivation is straightforward, we are faced with two main challenges. The first challenge capturing the local neighborhood distribution borhood distributions typically follow heterogeneous and diverse patterns. For instance, node usually connects with others due to the complex interaction of different latent factors and therefore possesses distribution consisting of local mixing patterns wherein certain parts of the neighborhood are homophilous while others are non-homophilous. The lack of supervision obstructs us from mod- eling the distribution of neighborhoods. The second challenge is capturing the long-range semantic dependencies. As shown in Figure 1, in con-homophilous graphs, nodes with high semantic and local structural similarities might be farther away from each other. For this reason, global semantic information is the objective that we would incorporate for self-supervised learning.
self- superviee learning manner. The neigh-
This paper presents new self- sup-suueee framework, decoupled self- supervud learning (DSSL), to achieve a good balance between these two challenges. At the core of DSSL is the latent variables, which empower the model with the flexibility to decouple the heterogeneous and diverse patterns local neighborhood distributions and capture the global semantic dependencies a coherent and synergistic framework. Our contributions can be summarized as follows: (1) We propose a DSSL for performing self-supervised learning on non-homophilous graphs, which can leverage both useful local structure and global semantic information. (2) We develop an efficient training algorithm based on variational inference to simultancously infer the latent variables and learn encoder parameters. (3) We analyze the properties of DSSL and theoretically show that the learned representations can achieve better downstream performance. (4) We conduct experiments on real-world non- non-hooophilous graphs, and the results demonstrate the effectiveness of our self self-supervised learning framework.
2 Related Work
Non-homophilous Graphs. Non-hooophiloos is known in many settings such as online transaction
networks [36], dating networks [1] and molecular networks [68]. Recently, various GNNs [37, 68, 59, 29, 69, 8, 44, 62] have been proposed to deal with non-homophilous graphs with different methods such as potential neighbor discovery [37, 23, 22], adaptive message propagation [8, 59], exploring high-frequency signals [2) and higher-order message passing [68, 5]. Despite their success, they typically consider the semi-super setting and are trained with spsc-sp labeled data, while in

---

k
7j
Figure 2: An illustration of (a) a graphical model for DSSL. The discrete latent variable & is used to instantiate latent Grauure-ff-Gaussians Vi. which is then decoded 2j and (b) a toy subgraph example of non-homophilous graphs where color denotes the class of the node. (c) Our model encodes the semantic shift by decoupling structure since different each node has different latent factors to make connections to its different neighbor, and (d) captures global semantic structure via the semantic clusters, which seeks push the representations of V1 and 12 their closest prototypes.
practice, labels are often limited, expensive, and even inaccessible. In contrast, in this paper, we study the problem of supe-sue learning: learning node representations without relying on labels.
Self-supervised Learning on Graphs. Self-supervised learning holds great promise for improving representations when labeled data are scarce [5, 12, 13, 19]. Earlier combinations of GNNs and self-supervised learning involve GraphSAGE [16]. VGAE [26], and Graphite [15], which typically follow the traditional network-embeddiig methods [38, 46, 14] and adopt the link reconstruction random walk principle. Since these methods over-emphasize node proximity at the cost of structural information [53, 45, 64], various graph contrastive learning methods have been proposed [53, 18, 64, 69, 48, 35], which aim to learn representations by contrasting representation under differently augmented views and have achieved promising performance. However, they heavily rely complex data- or task-specific augmentations, which are prohibitively difficult for non-how non-homophilous graphs. Our work differs from the above methods and aims to answer the question of how design effective self-supervised learning scheme for non-homophilous graphs.
Disentangled graph learning. Our work is also related to but different from existing disentangled graph learning that aims to decouple latent factors in the graph. vGraph [43] considers a mixture process to define the conditional probability on each edge. vGraph is classical shallow network embedding algorithm. However, we instead tackle the problem self-supervised learning with GNNs. There are couple of works that explore the disentangled factors in the node-level [33, 32], edge-level [67] and graph-level [63]. Whereas these methods require task-specific labels that can be extremely scarce. By contrast, address the problem of learning node representations homophilous graphs without labels. Disentangled contrastive learning [28] learns disentangled graph representations without labeled graphs. [61] proposes the self-supervised graph-level representation learning with disentangled local and global structure [61]. Nevertheless, their goal is to conduct graph-level classification tasks, but we tackle node-level representation problem. [66, 9, 555 consider adding a clustering layer or a prototype clustering component to capture the global information. However, they are still based on contrastive learning [66, 9] supervised learning [55]. By contrast, our framework is an unsupervised generative model and does not rely on graph augmentations and downstream labels. Moreover, we focus on non-homophilous graphs where connected nodes may not be similar to each other by decoupling the local diverse neighborhood context.
3 Decoupled Self-supervised Learning
In this section, we describe our problem setting with respect to self-supervised learning and demon- strate our approach. An illustration of generative and inference processes is depicted in Figure 2 (a).
3.1 Problem Formulation
We consider a graph G = (V,E), where a set of [V] N nodes and & C V x V a set []] edges between nodes. A N is the adjacency matrix of G. The (i,j)-th element Aij = if there exists an edge (v;, U)) between node U; and vj, otherwise A.; = 0. The matrix X E D describes node features. The i-th row of X, i.e., x;, is the feature of node e, Given the graph G = (X, A), the objective of self-supervised node representation learning is to learn encoder
3

---

function A)) RNXN X RNND - R NNDD where & denotes its parameters, such that the representation of node ey AX]i can be used for downstream tasks such as node classification.
3.2 The Probabilistic Framework
In this section, we introduce our framework, decoupled self-supervised learning, which can learn meaningful node representations non-homophilous graphs by capturing the intrinsic graph structure. The core idea of DSSL is to model the distributions of node neighbors via a mixture of generative processes in the representation space. Specifically, we model the generation of neighbors by assuming each node has latent heterogeneous factors which are utilized to make connections to its different neighbors. Intuitively, the factor denotes various reasons behind why two nodes are connected in non-homophilous graphs. For instance, two nodes in a school network will be connected depending on some factors such as colleagues, friends, classmates; in protein networks, even if they do not have similar features, different amino acid types are likely to be connected due to various interactions.
Formally, let fo (X, ( A]]] = v; and fo A] = 2j be the representations of nodes vi and Vi- respectively. Here we utilize different notations, i.c.. v and z to distinguish between central and neighbor nodes since each node plays two roles: the node itself and specific neighbor of other nodes. Our goal is find the encoder parameter which maximizes the likelihood of distribution p(z,) V;: 0) on central node and its neighbor. To model the unobserved factors, we associate every node V, with a discrete latent variable k to indicate to which factor v, has. Assume that there are K factors in total, the log-likelihood of node neighbors Vi can be written by marginalizing out the latent variables:
LDSSL(0)
Σ JEN(E)
log|po [v.] IN(I
Σ log
Σ
po(zs|v, k) (klvi)) k=1
(1)
[N(1)
SEN(E)
where N(t) is the set of out-neighbors of us the distribution pa (k)lv. indicates the assignment of latent semantics over central node representation v;. and po(2) vi, k)) is the probability that node iy and its neighbor Uj are connected under factor k. Unlike previous works [46, 14, 26], which directly encourage nearby nodes to have similar representations, we provide an alternative way to model node neighbors and seek to decouple their latent relationship without any prior on neighbor partitions. The similar high-level ideas of modcling latent variables between two nodes has also been explored in local augmentation in graphs (LA-GCN) [31] and vGraph [43]. Different from them, we consider modeling discrete relations in the learned representation space for self-supervised learning on non-homophilous graphs. In Eq. (1), probabilities po (kllv) and po (z, v,, ke) are not specified, and involve discrete latent variables. To make solvable, we introduce the following generative process.
Let [4g and Σs be the mean and variance of the latent mixture component k; and T. be its correspond- ing mixture probability. The generation of node and its neighbor shown in Figure 2 (a) typically involves three steps: (1) draw a latent variable k from a categorical distribution p(k: on all mixture components, where p(k) usually defined as uniform distribution p(k) = 1 for unknown graphs and better generalization, (2) draw the central node representation V; from the Gaussian distribution pe(v: [k) = NV p,,, Ex), and (3) draw the neighbor representation z, from Gaussian distribution Po(z, Vs. k) N (22; May. Σÿ) where the mean depends both on central representation and latent variable: 12 = v, + Byo(k). Here the projector (o(+) denotes another network that embeds latent variable h to the representation space, and ,3 is the parameter that controls the strength of interpolation. In practice, to reduce complexity, we consider using isotropic Gaussian, i.c., Vk: : Σn = Lof and Vj: Σn = lož where I is the identity matrix, 0 and 02 are hyperparameters. In alignment with this generative process, the joint distribution of the edge and latent variable can be written as:
(2) Intuitively, pa (v(vkk can be viewed as the probability for node representation under the k-th mixture component. Regarding po po(z,lv,, k) = -N(z; ut,, Σ,), this formulation inspired by knowledge graph embedding [3], where two entities should be closed to each other under a certain relation operation. However, unlike knowledge graph embedding, the relational context is a latent variable and not observed in our setting. Intuitively, instead of enforcing the exact representation alignment of two linked nodes [26, 14, 17, 16, 46), our design can relax this strong homophily assumption and account for the semantic shift of representations between the central node and its neighbors.
Pe PV zj, k) = pe (z, V., (v)((v))))(()))
Now, the posterior probability pe (kl/vs) in Eq. (I) can be derived by using Bayesian rules as follows: pe (va k) k))((k)
.V M4g (ok)
(klv)))) = EK Pa (v
(3)
Σm= NV Pg. Ly (oF)

---

where = {ug] can be treated as a set of trainable prototype representations, which are the additional distribution parameters. This posterior probability represents the soft semantic assignment of the learned representation to the prototypes, which makes the node with similar semantic properties be close to pro and encode both the inter- and intra-cluster variation. Substituting po po(k vv)) and po (2)2/11 v., k) in Eq. (1) with the specified probabilities, we get final objective D (0, p.).
3.3 Evidence Lower Bound
Given the framework above, we are interested in: (i) learning the model parameters 0 and μ by maximizing the log-likelihood psst 14); and (ii) inferring the posterior of latent variable k for directly solve these two problems
each observed links. However, is computationally intractable due to the latent variables. To solve this, we resort to amortized variational inference methods [25], and maximize the evidence lower-bound (ELBO) of Eq. (1), i.e., LDSsl (0, μ 2 LDssL o, p)::
LDssL O, (4)
Σ JEN()
(l (2, vv, k) log ((qa((k)v (4)
[N())
is the introduced variational distribution parameterized by & and H(-) is the entropy operator. z, is included in this variational posterior, so the inference is also conditioned on the neighborhood information. We derive this ELBO in Appendix A.1. Maximizing this ELBO w.r.t {8, o, je} is equivalent to (i) maximizing (D μu) and to (ii) make variational 4s (k|V,, Zj) be close to true posterior. Plugging the parameterized probabilities into this ELBO, we obtain the following loss to minimize. See Appendix A.2 for corresponding derivations.
where da (klv;; 2,)
log exp(v, -LL/of)
c=
(Ro [lvv (k) 2, -2 JEN())
Σ
(HIv;)
[N(1)
MK= explv. mw//o7)
(lgo 2,)),
where 4o (A|v;) ()) EjeNO 4s (klv,, 2,) is the posterior probability of semantic assignment for central node u; by aggregating all its neighbors. Thus, the first term (denoted as Liocal) in the loss encourages the model to reconstruct the local neighbors while considering different semantic shifts captured by latent variable I (see Figure 2 (b)). The second term (denoted Liglabal) encourages the model to perform clustering with learned representation where possible, i.e., seeking to push the representation V; to its closest prototype cluster (see Figure 2 (c)). The final entropy term makes the model choose to have high entropy over go (klvi:: 2;) such that all of the K K-channel losses must be low. Overall, this loss derived from ELBO can capture global semantic similarities over neighborhoods and learn to decouple different latent patterns in the local neighbors.
Regarding the variaitonal distribution go (k) Zj). we model it as categorical distribution since k is a discrete multinomial variable. Specifically, the representations and zj are encoded to combined representation and then go (klv,, 2,) is determined by an output softmax inference head as follows:
exp(ho((v::2)) 2, (A))
q (klv,,, Σ exp(ho (v:; 2, ()])()))))
(6)
where h denotes the inference network parameterized by & and [ can be the element-wise product or concatenation operation. ([v;; [Kj] indicates the htth element, i.e., the logit corresponding the latent context k. Instead of introducing variational parameters individually, we consider the amortization inference [25, 58), which fits a shared network to calculate each local parameter.
For the expectation terms in Eq. (5), back-propagation through the discrete variable k is not di- rectly feasible. We alleviate this by adopting the Straight-Throur Gumbel-Softmax estimator [21], which provides a continuous differentiable approximation for drawing samples from categorical distribution. Specifically. for each sample, latent cluster vector с E 1), 1)x is drawn from:
exp((ho ( [v: 2, 1) k <(k))>>)
c[k]
(
Σk= (ha (Iv []] {((1))>))
where <[k] is i.i.d drawn from the Gumbel(O, 1) distribution and 7 is a temperature. With this reparameterization trick, we can obtain the surrogate (klv..,,, [llv; + (3) 2, 2 E.lllv; (c) 2, [ and the gradients are estimated with Monte Carlo. The expectation term over (k v.) can be similarly estimated. Then, {0, o, u1) in Eq. (5) can be efficiently solved by gradient descent.
5

---

3.4 Algorithm Optimization
The overall optimization involves simultaneously training (1) the encoder fe. (2) the projector go, (3) the inference predictor he and (4) the prototypes μ.. The most canonical way to update the parameters stochastic gradient descent. However, we observe that stochastically updating all parameters suffers from two problems: (1) The objective admits trivial solutions, e.g., outputting the same representation for all nodes in the optimization process. (2) Updating prototypes without any constraints will lead to a degenerate solution, i.e., all nodes are assigned to a single cluster.
To address the issue of trivial solutions, inspired by the recent works [19, 13], we consider an asymmetric encoder architecture that includes online and target encoders. Specifically, for each node pair (b,, ) the online encoder fo produces the representation of the central node v;; while the target encoder f&g is used to produce the representation of its neighbor 2,. Importantly, the gradient of loss is only used to update the online encoder fe while being blocked in the target encoder. The weights of the target encoder & are updated via the exponential moving average (EMA) of the online encoder 0:
(0. < (0, pr] r (Vo,o.n)
< 7 +1-
(8)
where r(-) indicates a stochastic optimizer and T E [0, 1] is the target decay rate. This update introduces an asymmetry between two encoders that prevents collapse to trivial solutions [13, 48]. To alleviate the second issue, besides the stochastic update, also apply global update for the prototype vectors μ
{
K at the end of each training epoch to avoid a degenerate solution:
ΣN (k) V IE (k) vallE
where (k) = 1/(N(() ESENOO (k 2,).
(9)
The derivation is provided in Appendix A.3. Intuitively, T. (A) reflects the degree of relevance of node v/ to the htth prototype. Instead of only updating the prototypes in a mini-batch, we also aggregate all the representations as the prototype based on the soft assignment probability at the end of the epoch. After the training is finished, we only keep the online encoder fe for the downstream task. Our full algorithm and network are provided in Appendix B. The details about time complexity of DSSL is given in Appendix C.1, which scales linearly in the size of edges.
3.5 Theoretical Analysis
In this section, we provide an analysis of the proposed framework. We first present the connection between the proposed objective and the mutual information maximization, then show that the learned representations by our objective provably enjoy good downstream performance. Due to the space limitation, all proofs of theorems and corollaries are provided in Appendix D.
We denote the random variable of the input graph as G and the downstream label as y. For clarity, omit subscript i in what follows. From an information-theoreiic learning perspective, a desirable way maximize the mutual information I(v,y) y) between the representation v and downstream label y. However, due to the lack of the downstream label, self-supervised learning resorts to maximizing (v,,s) where s is different designed sulf-super signal [51, 4, 56, 65, 11]. In our method, we have two self-supervised signals: the global semantic cluster information inferred by k and the local structural roles captured by the representations of the neighbors z {z, E (x)) of node v.
Then, we can interpret our objective in Eq. (5) from the information maximization perspective:
Theorem 1. Optimizing local and global terms in Eq. (5) is equivalent to maximizing the mutual information between the representation v and global signal i and maximizing the conditional mutual information between and the local signal z, conditioned on global signal k. Formally, have:
min L + max (v; k) + (Vv: = [v;; z). 0.0-1
(10)
This theorem suggests that we essentially combine both local structure and global semantic informa- tion as the supe-suue signal and maximize the mutual information between the representation v and their joint distribution (k, z). Next, we discuss how the learned representation affects the downstream task y based on the information bottleneck principle [51, 11, 56, 4]. The rationality of self-supervin learning is that the task-relevan information lies mostly in the shared information be-
tween the input and the supe-supe signals [51, 11, 4]. Specifically, we formulate our lightweight and reasonable assumption below, which serves as a foundation for our analysis.
Assumption 1. Nodes with similar labels should have similar "local structural roles" and "global semantic clusters." In this work, we equate "local structure" with the 1-hop neighborhood and "global

---

semantic" with the clustering membership of a node. Formally, we have the task-relevant information y left in except that in joint ceff-suervviee signal (z, k) is relatively small: y k) S
Intuitively, this assumption indicates that most of the task-relevant information in the graph is contained in the self-supervised signal (local neighborhood and global semantic patterns), Based on this assumption, we have the following theorem, which reveals why the downstream tasks can benefit from the learned representations learned by our objective function.
Theorem 2. Let Vjoint =
arg max, I(v; z, k), Vlocal arg max, I(v; and Vglobal = arg maxy T() Formally, we have the following inequalities about the task-relevant information:
y): = max [ yv:y)= 2 (Vjoiit;y) 2 max{ (Vioc((Viaaai)))) (Vgioball y)) 2 (): -. (11)
Theorem 2 shows that the gap of task-relevant information between supervised representation V sau = arg maxy [(v,y) and self-supervised representation Vjoint is e. Thus, we can guarantee a good downstream performance long as the Assumption is satisfied. It is noteworthy that jointly utilizing local structure and global semantics as the self-supervised signal is expected to contain more task information. As further enlightenment, we can relate Eq. (36) with the Bayes error rate [51]:
Corollary 1. Suppose that downstream label y is M-categorical random variable. Then have the upper bound for the downstream Bayes errors P = Ev [1- maXyey P(ý = y|v)] on learned representation v, where y is the estimation for label from our downstream classifier:
Th(Ps (oome ) S log + P
Youp llog M I(::ylz,k) & RHS yoames
(12)
where Th(2) = min famfmaxf2: fz. 0}, 1/|MM] is a thresholded operation [51]. Similarly, we can obtain the error upper bound of other representations Vincal and V Yglnhal
RHS yitobl
Then, we have inequalities on error upper bounds RHS S CimmmnHHs (RHSv RHSS giohat)
This corollary says that our self-supervised signal has a tighter upper bound on the downstream Bayes error. Thus, both local structure and global semantic information, has superior performance on downstream tasks.
expect that the representation learned by our objective function, which utilizes
4
Experiments
In this section, we empirically evaluate the proposed self-supervised learning method on several real-world graph datasets and analyze its behavior on graphs to gain further insights.
4.1 Experimental Setup
Datasets. We perform experiments on widely-used homophilic graph datasets: Cora, Citeseer, and Pubmed [42], as well as non-homophilic datasets: Texas, Cornell, Wisconsin [37], Penn94 and Twitch. Penn94 and Twitch are two relatively large non-homophilous graph datasets proposed by [41, 29]. We provide the detailed descriptions, statistics, and homophily measures of datasets in Appendix E.
Baselines. To evaluate the effectiveness of DSSL, we consider the following representative unsuper- vised and self-supervised learning methods for the node representation task, including Deepwalk (38), LINE [46], Struc2vee [40], GAE [26], VGAE [26]. DGI [53], GraphCL [64], MVGRL [18] and BGRL [48]. The detailed description of baselines and implementations are given in Appendix E.2.
We consider two types of downstream tasks: node classification and node clustering. For node classification, we follow the standard linear-evaluation protocol on graphs [53, 48), where a linear classifier is trained on top of the frozen representation, and test accuracy (ACC) is used as a proxy for representation quality. For datasets, we adopt the similar random split with ctin//alidaaioon/estt split ratio of 48/32/20% for the training of downstream linear classifier following [37]. Note that [37] claims that the ratios are 60/20/20%, which is different from the actual shared data splits as shown by [68. 34, 29]. For the node clustering task, we perform K -mmens clustering on the obtained representations and set the number of clusters to the number of classes We utilize the normalized mutual information (NMI) [54] as the evaluation metric for clustering.
Evaluation Protocol.
Setup. For all self-supervised methods on graph neural networks, we consider a two-layer GCN [27] as the encoder unless otherwise stated, and randomly initialize parameters. We run experiments with 10 random splits and report the average performance. We select the best configuration of hyper- parameters based on accuracy on the validation. The detailed settings given in Appendix E.2.
7

---

Table 1: Experimental results (%) with standard deviations the node classification task. The best and second best performance under each dataset are marked with boldface and underline, respectively.
Method
Cora
Citeseer
Pubmed
Texas
Cornell
Squirrel
Penn94
Twitch
Deepwalk
17.14.0.82
67.85_o.7
79.38
42231
11.5511.12
37.54
66.37 16.13.10.6
LINE
68. -847
80.5620.92
48.69=11.9
43.68+2.17
57.59=a177 18.92+
67.23
Struc2vee
30.26
53.38=002
40.83+1185
49.31
30.22+5.7
36,49+1.15
=0.29
63.52.0..5
GAE
78.33=00.7
66.39-024
78.28
53,98=332
44,18
30,53++1.3
58. +
67. 07.98+022
VGAE
80.59 69.90
81.33
50.27:12.1
48.73
29. 11.11
58. a822
65.09
DGI
14.17
1.38
81.65:20.71
28.53
15.33
26.44
53.6820.19
66.97:10.5
GraphCL
84.28
72,46
81.96.10.7
48.67.14.37
47. 44.22.14.50
22.53
18.4
68.3710.15
MVGRL
81.2
72.13 13.11311104
82.33-+0.8
51,26=:0.5
51.16+16.7
38, +8.43
57.22+a17
66.03-+0.26
BGRL
83.29
71.56=0087
81.34
52.77:
50,33+2229
a8.9 36,22
67, a..23
DSSL
83.06
73.51 0.64
82.98
62.11=1155
53.15
40.51 +0.35
60.38=aaz
69.81 +0.17
Squiral
Twitch
Squirel
Twitch
Aoc Resunions (8)
Loss
300
Accuricy feoo global Mpdoone)
Accurscy Iwl global updano)
Accutlty E1
Accuracy -0000
Accuraty
Figure 3: (Left) Performance w/ and w/o global update. (Right) Performance with varying T.
4.2 Overall Performance Comparison
In this section, we conduct experiments on real-world graphs compared to state-of-the-ar methods.
Table I reports the average classification accuracy with the standard deviation on node classification after ten runs. Since node clustering results have a similar tendency, we provide them in Appendix F.1. From Table we have the following observations: (1) Generally, our DSSL achieves the best performance on both node clustering and classification tasks over the best baseline, demonstrating the effectiveness of DSSL on both homophilous and non-homophilous graphs and the robustness to different downstream tasks and graphs. Especially, DSSL achieves a relative improvement of over 6% and 4% on Texas and Squirrel compared to the best baselines (2) Our DSSL cannot achieve the best performance on Cora. This is reasonable since Cora is highly homophilous (see Appendix 1. and the core design of augmentation in contrastive learning methods such as MVGRL and GraphCL enables them to be effective on homophilous graphs but failed on low-homophily settings. This supports our motivation augmentation on non-homophilous graphs due to their heterogeneous and diverse patterns. (3) When compared with GAE, VGAE, and DGI, DSSL consistently and significantly outperforms them. We deem that this improvement is mainly from the joint local semantic shift and global semantic clustering in DSSL, which not included in existing methods.
the introduction that it is relatively difficult to design effective graph
0.9
0.9
0.5
Accuracy
Accuracy
Accuracy
2.8
0.8
0.7
0.7
0.7
0.7
Twith
0.6
0.0
0.82
0.
0.8
0.4
0.6
0.8
1.0
0.5
32
of
A
Figure 4: Hlyper-paramee analysis on PubMed, Twitch and Texas datasets.
4.3
Ablation Study and Parameter Analysis
In this section, we conduct an ablation study and investigate the sensitivity of hyper-parameters.
Ablation Study. We consider the following ablations: (A1) We remove the key component of DSSL: the local reconstruction loss (w/o Llocat). (A2) We remove global clustering loss to see if Liocal alone is still effective (w/o Lgtobal). (A3) We remove the entropy term in Eq. (5) (и/o entropy). (A4) We remove the semantic shift term go (k) in Liocal (w/o semantic shift). (AS) We set posterior qo (kc v., ) 1/ K as uniform distribution for each link (w/ uniform posterior). We show the ablation study results in Table 2. Lgtobal alone does not provide much discriminative information, and it does not perform very well. Llocat as a key component of DSSL alone produces better results
8

---

Table 3: Experimental results (%) on the node classification task with GAT. The best and second best performances under each dataset are marked with boldface and underline, respectively.
Method
Cora
Citeseer
Pubmed
Texas
Cornell
Squirrel
Penn94
Twitch
MVGRL.
84.52
71,52+041
81.05+0.6
53.42=00.9
37.58+0095 +0.2
-7.21
07.11
BGRL 83.91
72.15+0.22
80. 80.12+0.52
51.02=1130
48.97
35.33
56,52
66.21 +0.35
DSSL
82.54.10.1
73.67.14.88
81.6910.37
19.73.1128
53.631116
39,42.1.4
58.97 0.26
69.55.10.4
1.0
0.0
0.2
0.0
0.0
(9) Naighorhood similaitt on Taxas
(b) Latent factor simiarity on Texas (c) Visuilization of subggraph (Texes 58)
(6) Visualization su sulggraph (Twitch in B)
Figure 5: The visualization and case study results (best viewed on a computer screen and note that the latent distribution of each link need to be zoomed in to be better visible).
than the DGI baseline. We can also observe that considering semantic shift and personalized posterior further improve the performance lot which demonstrates our key motivations. The full model (last row) achieves the best performance, which illustrates that different components in the proposed DSSL are complementary to each other.
Effect of Global Update on Prototypes. We conduct ab- lation studies to gain insights into the global updating of prototypes. As shown in Figure 3, we can observe that without Eq. (9), the performance is not very good, and we are stuck in bad local optima. As discussed above, a possible reason is that we will experience strong degener- acy if we only update prototype vectors with mini-batch training. This figure also demonstrates that DSSL can converge within a few hundred steps, which is efficient.
Table Node classification accuracy (%) on the Texas dataset.
Ablation
Accuracy
A1 w/o local loss Liocal
25.18
A2 w/o global loss Cytobal
29.34=2.76
A3 w/o entropy loss
60.57=1.27
w/o semantic shift
56.19=1.25
w/ uniform posterior
50,27
A2+A3
57.61=1.72
A2+A4
50.52_2.01
Effect of Asymmetric Architecture. We then explore the effect of target decay rate т on the performance. Figure shows the learning curves of DSSL on Squirrel and Twitch. We can observe that the best result achieved at t = 0.9. When = 1.0, i.e., the target network is never updated, DSSL obtains a competitive result but is lower than 7
A2+A5
48.59=1.87
DGI
58.53=2.98
DSSL
62.11 1.53
0.9. This confirms that slowly updating the target network is crucial in obtaining superior performance. At the other extreme value T = 0, the target network is the same as the online network, and DSSL demonstrates a degenerated performance.
Hyper-parameters Analysis. We investigate the hyper-paramesn most essential our framework design, i.e., the standard deviation σ₁ and d2, the temperature of the Gumbel Softmax 7, and the total number of factors K. The corresponding results are shown in Figure 4. of resembles the temperature scaling in Eq. (5). We observe of is better to be selected from 0.6 to 1.0, and too small (e.g.. 0.2) value may degenerate the performance
all three datasets. of balances the local and global loss in Eq. (5). We can find that having large values of of does not improve the performance, as the local loss plays an essential role in the proposed model. Further, we observe that DSSL is not very sensitive to the Gumbel softmax temperature X, while a moderate hardness of the Softmax gives the best results. We also find that as K increases from to 8, the performance of DGCL improves, which suggests the importance of decoupling latent factors. However, training with large K will lead to performance slightly drop. We provide results on other datasets in Appendix F.3.
Encoders Analysis. To further evaluate the effectiveness of the proposed DSSL, we consider the case where the self-supervised learning methods are implemented using another GNN encoder. Table shows the results of the selected baseline with GAT as the encoder. As shown in Table 3, our DSSL performs better than all the compared methods in most cases, which once again proves the effectiveness of DSSL, and also shows that DSSL is broadly applicable to various GNN encoders.

---

135
(8) Example graph from Pubmedi
(b) Corresponding corretation map
[6] Example graph from Comell
(0) Correspondngg correlation map
Figure 6: Example graphs and correlation maps. The graphs are randomly sampled from Pubmed and Cornell. The correlation maps are obtained based on the pair-wise similarities of learned posteriors.
4.4 Visualization and Case Study
Local neighborhood Patterns. We provide the visualization and case study results to understand how DSSL uncovers the latent patterns in local neighborhoods. More results can be found in Appendix F.4. In Figure 5 (a), we calculate the cross-class neighborhood similarity (see Appendix E.3 for definition), which serves as the ground truth. nodes with the same label share the same neighborhood distributions, the intra-class similarity should be high. In Figure 5 (b), we calculate average posterior distribution go (k),)) over nodes on each class and provide cosine similarity of them. We can observe that our learned distribution shares similar pattern with the cross-class neighborhood similarity, which shows that learned latent factors can capture the latent semantic information related to neighborhood patterns. In Figures 5 (c) and (d), plot the subgraph of randomly selected node, and the distribution qo (klv,,, 2,). We use different colors to indicate different labels. We find that similar neighbors over class generally have similar distribution, while different types of links exhibit different latent distributions. This observation matches our motivation that DSSL can decouple the diverse semantics in the local neighborhoods.
Global Semantic Patterns. We investigate how our learned semantic clusters perform on the long- range nodes. To show this, study the learned cluster distribution go (A[vv) for each node. To facilitate visualization, we randomly sample a sub-graph that contains high-hop neighborhoods from each dataset and use different colors to indicate different node labels. We then calculate the pair-wise similarity of the posteriors qu (klv;) between nodes as shown in Figure 6. We can observe that our learned semantic clusters exhibit similar patterns for the nodes in the same class. Some nodes exhibit similar semantic clusters regardless of the distance between them. For instance, node ID exhibits a very similar posterior distribution to the same class node ID 19 in Pubmed, and node ID exhibits similar posterior distribution to node ID 12 in Cornell, despite these nodes being ID 4 hops away. Since DSSL seeks to pull the node representation to the inferred semantic clusters, can learn the global node-node relationships in representations instead favoring nearby nodes.
5 Conclusions
In this paper, we study the problem of conducting self-supervised learning on non-homophilous graphs data. We present novel decoupled self-supervised learning (DSSL. framework decouple the diverse neighborhood context of node in an unsupervised manner. Specifically, DSSL imitates the generative process of neighbors and explicitly models unobserved factors by latent variables. We show that DSSL can simultancously capture the global clustering information and the local structure roles with the semantic shift. We theoretically show that DSSL enjoys a good downstream performance. Extensive experiments on several graph datasets validated the superiority of DSSL and showed that DSSL could learn meaningful class flas--iisrimmintiiv representations.
Acknowledgments
This work was partially supported by the National Science Foundation (NSF) under grants number IIS-1909702 and IIS- Army Research Office (ARO) under grant number W911NF-21- 1-0198 and Department of Homeland Security under grant number E205949ID. The findings and conclusions in this paper do not necessarily reflect the view of the funding agency.
10

---

References
[1] Kristen M Altenburger and Johan Ugander. Monophily social networks introduces similarity among friends-of of-dd--o--rieddd Nature human behaviour, pages 284-290, 2018.
[2] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequeney information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 3950-3957, 2021.
[3] Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. Advances in neural information processing systems, 2013.
[4] Manh-Ha Bui, Toan Tran, Anh Tran, and Dinh Phung. Exploiting domain-speciftr features to enhance domain generalization. Advances in Neural Information Processing Systems, 2021.
[5] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pages 1597-1607, 2020.
[6] Zhengyu Chen, Jixie Ge, Heshen Zhan, Siteng Huang, and Donglin Wang. Pareto self-supervised training for few-shot learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 16663-13672, 2021.
[7] Zhengyu Chen, Teng Xiao, and Kun Kuang. Ba-gnn: On learning bias-aware graph neural network. In 2022 IEEE 38th International Conference on Data Engineering, pages 3012-3024, 2022.
[8] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2020.
[9] Kaize Ding, Yancheng Wang, Yingzhen Yang, and Huan Liu. Structural and semantic contrastive learning for self-supervised node representation learning. arXiv preprint arXiv:2202.088 084880 2022.
[10] Linus Eriesson, Henry Gouk, and Timothy M Hospedales. How well do self-supervised models transfer? In Proceedings of the IEEF/CVE Conference on Computer Vision and Pattern Recognition, pages 5414-5423, 2021.
[11] Marco Federici, Anjan Dutta, Patrick Forré, Nate Kushman, and Zeynep Akata. Learning robust representations via multi-view information bottleneck. In International Conference Learning Representations, 2019.
[12] Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. In International Conference Learning Representations, 2018.
[13] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, al. Bootstrap your own latent-a new approach self-supervised learning. Advances Neural Information Processing Systems, pages 21271 111271221284 2020.
[14] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and dutu mining, pages 855-864, 2016.
[15] Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International conference on machine learning, pages 2434-2444, 2019.
[16] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
[17] William I. Hamilton, Rex Ying, and Jure Leskovee. Representation learning on graphs: Methods and applications. arXiv preprint ArXiv:1709.05560 2017.

---

[18] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pages 4116-4126, 2020.
[19] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729-9738, 2020.
[20] W Hu, B Liu, J Gomes, M Zitmik, P Liang, V Pande, and Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
[21] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint 16Xiv:161 144, 2016.
[22] Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. Universal graph convolutional networks. Advances in Neural Information Processing Systems, 2021.
[23] Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 148-156 2021.
[24] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
[25] Diederik P. Kingma and Max Welling. Auto-encoding variational bayes. In International Conference on Learning Representations, 2014.
[26] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint drXiv:1611.07308, 2016.
[27] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. ICLR, 2017.
[28] Haoyang Li, Xin Wang, Ziwei Zhang, Zehuan Yuan, Hang Li, and Wenwu Zhu. Disentangled contrastive learning on graphs. Advances Neural Information Processing Systems, 2021.
(29] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 2021.
[30] Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning non-homophilous graphs. arXiv preprint arXiv:2104.01404, 2021.
[31] Songtao Liu, Rex Ying. Hanze Dong, I Laning Li, Tingyang Xu, Yu Rong, Peilin Zhao, Junzhou Huang, and Dinghao Wu. Local augmentation for graph neural networks. In International Conference Machine Learning, pages 14054-14072, 2022.
[32] Yanbei Liu, Xiao Wang. Shu Wu, and Zhitao Xiao. Independence promoted graph disentangled networks. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4916-4923, 2020.
[33] Jianxin Ma, Peng Cui, Kun Kuang, Xin Wang, and Wenwu Zhu. Disentangled graph con- volutional networks. In International conference on machine learning, pages 4212-4221, 2019.
[34] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In International Conference on Learning Representations, 2021.
[35] Yujie Mo, Liang Peng. Jie Xu, Xiaoshuang Shi, and Xiaofeng Zhu. Simple unsupervised graph representation learning. In AAAI, 2022.
[36] Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: fast and scalable system for fraud detection online auction networks. In Proceedings of the 16th international conference World Wide Web, pages 201-210, 2007.
12

---

[37] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuar Chang, Yu Lei, and Bo Yang. Geom-gen gen: Geo- metric graph convolutional networks. In International Conference on Learning Representations. 2019.
[38] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710, 2014.
[39] Ben Poole, Sherjil Ozair, Aaron Van Den Oord, Alex Alemi, and George Tucker. On variational bounds of mutual information. In International Conference Machine Learning, pages 5171-5180, 2019.
[40] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pages 385-394, 2017.
[41] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, page cnab014, 2021.
[42] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, pages 93-93, 2008.
[43] Fan- Yun Sun, Meng Qu, Jordan Hoffmann, Chin-Wei Huang, and Jian Tang. vgraph: A generative model for joint community detection and node representation learning. Advances in Neural Information Processing Systems, 32, 2019.
[44] Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In KDD, 2021.
[45] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances in Neural Information Processing Systems, 2021.
[46] 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 world wide web, pages 1067-1077, 2015.
[47] Mingyue Tang, Pan Li, and Carl Yang. Graph auto-encoder via neighborhood wasserstein reconstruction. In International Conference on Learning Representations, 2021.
[48] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scabe representation learning on graphs via bootstrapping In International Conference on Learning Representations, 2021.
[49] MTCAJ Thomas and A Thomas Joy. Elements of information theory. Wiley-Interscience, 2006.
[50] Puja Trivedi, Ekdeep Singh Lubana, Yujun Yan, Yaoqing Yang. and Danai Koutra. Augmenta- tions in graph contrastive learning: Current methodological flaws & towards better practices. arXiv preprint arXiv:2111.0322 2021.
[51] Yao-Hung Hubert Tsai, Yue Wu, Ruslan Salakhutdinov, and Louis-Philippe Morency. De- mystifying self-super learning: An information-tthorrtiie.. framework. arXiv preprint arXiv:2006.05576, 2020.
[52] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[53] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2018.
[54] Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for cluster- ings comparison: Variants, properties, normalization and correction for chance. The Journal of Machine Learning Research, pages 2837-2854, 2010.
13

---

[55] Yanling Wang, Jing Zhang, Haoyang Li, Yuxiao Dong, Hongzhi Yin, Cuiping Li, and Hong Chen. Clustersel: Cluster-aware supervised contrastive learning on graphs. In Proceedings of the ACM Web Conference 2022, pages 161 1-1621, 2022.
[56] Yifei Wang, Zhengyang Geng. Feng Jiang. Chuming Li, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Residual relaxation for multi-view representation learning. Advances in Neural 2021.
Information Processing Systems,
[57] Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non parameettiic instance discrimination. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733-3742, 2018.
[58] Teng Xiao and Donglin Wang. A general offiin reinforcement learning framework for interac- tive recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4512-4520, 2021.
[59] Teng Xiao, Zhengyu Chen, Donglin Wang. and Suhang Wang. Learning how to propagate messages in graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2021.
[60] Keyulu Xu. Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
[61] Minghao Xu, Hang Wang, Bingbing Ni, Hongyu Guo, and Jian Tang. Self-supervised graph- level representation learning with local and global structure. In International Conference Machine Learning, pages 11548-11558, 2021.
[62] Liang Yang. Mengzhe Li, Liyang Liu, Chuan Wang, Xiaochun Cao, Yuanfang Guo, et al. Diverse message passing for attribute with heterophily. Advances in Neural Information Processing Systems, 2021.
[63] Yiding Yang. Zunlei Feng, Mingli Song. and Xinchao Wang. Factorizable graph convolutional networks. Advances in Neural Information Processing Systems, pages 20286-20296, 2020.
[64] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, pages 5823,, 2020.
[65] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-supervised graph neural networks. Advances in Neural Information Processing Systems, 2021.
[66] Han Zhao, Xu Yang, Zhenru Wang, Erkun Yang, and Cheng Deng. Graph debiased contrastive learning with joint representation clustering. In IJCAI, pages 3434-3440, 2021.
[67] Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Exploring edge disentanglement for node classification. arXiv preprint arXiv:2202.11225. 2022.
[68] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, pages 7793-7804, 2020.
[69] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 11 1166-111176 2021.
[70] Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. arXiv preprint arXiv:2 109.0/ /6, 2021.
[71] Marinka Zitikk Rok Sosič, and Jure Leskovec. Prioritizing network communities. Nature communications, pages 1-9, 2018.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you descrihe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "xUEz4n6gVu8", "reviewer": "Reviewer_mEXA", "summary": "This paper proposes a new method, called decoupled self-supervised learning (DSSL), for self-supervised learning of node representation on non-homophilous graphs. Experiments on reals datasets are used to verify the effectiveness of the proposed method. ", "questions": "1. What is the time complexity of the proposed method? Is the proposed method slower than existing methods? Why not perform experiments on larger datasets? \n2. How to explain the phenomenon that existing methods based on homopilous assumption also achieve comparable accuracy with the proposed method?\n3. Can we generate some synthetic datasets with only homophilous structure or non-homophilous structure to verify the property of the proposed method and existing methods?\n", "limitations": "The authors have adequately addressed the limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. It is interesting to study the self-supervised learning problem about node representation learning on non-homophilous graphs, because most existing graph self-supervised learning methods assume homophily in graphs. \n2. The proposed method seems to be reasonable.\n3. Theoretical analysis is provided.\n4. Better accuracy is achieved by the proposed method, compared with existing methods.\n5. The paper is well written with good organization.\n\nWeaknesses:\n1. Time complexity analysis is not provided. The datasets adopted for evaluation are relatively small. Is it due to high time complexity of the proposed method? As we know, most self-supervised learning methods are proposed for large-scale datasets.\n2. On some datasets with non-homophilous structure, like Twitch, existing methods based on homopilous assumption also achieve comparable accuracy with the proposed method, which seems to contradict with the motivation of this paper. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "p5TlLPR_1q-", "reviewer": "Reviewer_7ey5", "summary": "This work studies the new problem of self-supervised learning for node representations on non-homophilous graphs, with the novel latent variable modeling to capture local and global semantics of graphs by decoupling latent factors, which is supported by theoretical and empirical results. In particular,\n* The authors first point out that self-supervised learning on non-homophilous graphs is undiscovered, yet it should be differently handled unlike in the existing self-supervised learning methods for homophilous graphs, due to a unique structure of non-homophilous graphs that connected nodes do not share similar properties. \n* To tackle this problem, the authors model the latent variable based on the motivation that nodes with similar neighborhood distributions should have similar representations, on which the model can capture the local semantics and global cluster structures by decoupling the neighborhood context. \n* The authors make the proposed latent variable model learnable in an end-to-end fashion with the famous amortized variational inference scheme.\n* To alleviate the issue that all node representations are collapsed into one representation and are assigned to one cluster, the authors leverage two tricks: 1) use the asymmetric encoding scheme for node representations (i.e., updating central and neighboring nodes differently); 2) use the outputs of node representations with their mixture probabilities to obtain prototype vectors for node clustering. \n* The authors theoretically show that their proposed method maximizes the mutual information between the node representation and the joint distribution of suggested local and global latent variables, which is further analyzed in terms of the generalization bound to downstream tasks.\n* The authors empirically verify that the proposed DSSL largely outperforms existing baselines, especially on non-homophilous graphs, and several analyses support their model designs as well as their claims.", "questions": "### Major Questions and Suggestions\n* Regarding the first weakness in the above, the authors can address it by discussing the relevant work [1].\n* Regarding the second weakness in the above, the authors can address it by showing results of capturing long-range dependencies, perhaps in a similar manner in Figure 5 of the case study but based on nodes far away from each other.\n\n### Minor Questions and Suggestions\n* Does the color in Figure 1 denote the class of nodes? It seems more explanations are needed for the illustration of Figure 1.\n* The meaning of encoding intra-cluster variation in Line 172 is unclear. How does the proposed formulation in equation (3) capture the intra-cluster variation?\n* A lack of explanation on the projector g_\\theta in Line 209. It is better to explain the projector, for readers who are not familiar with self-supervised learning.\n* The contents on page 14 should be removed.\n\n### Typos\n* In Line 293, we. \n* In Line 346, case.\n* In Line 361, (b) and (c) should be (c) and (d).\n", "limitations": "The authors provide the limitations and potential negative societal impact of their work in Section F of the supplementary file. I am satisfied with them.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n* This work discovers a new task of self-supervised learning for nodes on non-homophilous graphs, with enough explanations on its inherent challenges. \n* This work is technically and mathematically sound. Specifically, this work tackles the proposed task with the novel and interesting latent variable formulation that models distributions of node's neighbors with decoupled latent factors, which can capture local distributions with reconstruction loss but also global cluster semantics with cluster centroids. Also, the authors theoretically show the effectiveness of the proposed DSSL in the view of information maximization.\n* The empirical results of the proposed DSSL are significant, compared against relevant baselines.\n* The authors comprehensively conduct the ablation study and sensitivity analysis.\n* This paper is extremely well written and easy to follow.\n\n### Weaknesses\nNote that the below points are not the major weaknesses of this paper, but it would improve the paper if the authors address them adequately.\n* There is a relevant work that, in graph self-supervised learning, [1] considers both local and global semantic structures, where the global context is captured by class prototypes which could be considered similar to the authors' method in the motivational perspective.\n* The authors claim in the introduction section that, one challenge of graph self-supervised learning is to capture the long-range semantic dependency described in Line 66. However, I cannot find empirical results that the proposed DSSL framework can alleviate this issue. The case study in Figure 5 only shows the local dependencies between nearby nodes, not the long-range dependencies.\n\n---\n\n[1] Xu et al. Self-supervised Graph-level Representation Learning with Local and Global Structure. ICML 2021.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZLJDxQ0loRL", "reviewer": "Reviewer_ANod", "summary": "The paper proposes a novel self-supervised learning approach for node representation learning on non-homophilous graphs. The proposed approach model the neighbors of a central node via a generative process. In addition to learning the patterns of local neighbors in the graph, the proposed approach also learns global semantic information in the node representations with parameterized prototypes. On top of that, the proposed method seeks to find different underlying semantics in different patterns of local neighbors in the graph.", "questions": "1. Any reasons of using 60% 20% 20% data splits rather than standard splits as used in other papers? \n2. It would be great if the author could compare the proposed method against works with similar efforts, as stated in Weakness 1. \n3. Could the authors provide more details on the complexity analysis?\n\n", "limitations": "N/A", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths \n\n1. This paper presents a framework for self-supervised learning on non-homophilous graphs, which is meaningful and well-motivated.\n2. The paper shows a reasonable amount of experimental results on data of different homophily levels.\n3. The paper performs thorough ablation studies on different components of the model. \n\nWeaknesses\n1. Compared graph self-supervised learning methods are not comprehensive. For self-supervise graph learning methods, the performance of included baselines such as MVGRL and BGRL are not SOTA. It is better to include methods such as [1][2][3] which has much better performance. Also, the proposed method aims to learn the local structure and the global semantic information with self-supervised learning. Works with similar motivations have been proposed in the community. For example, [3] also proposes jointly considering structural and neighbor information for self-supervised learning. [4] also proposes a clustering objective. [5] also uses the idea of prototypes to capture the global semantic knowledge\n\n2. For the experiments, the authors didn't use standard data split protocol (20-shot per class). Using 60% training data is somehow contradict with the goal of self-supervised learning and it is hard to fairly compare with the reported results in our papers. Meanwhile, considering that the proposed method consists of multiple components, ablation studies are vital to validate the power of semantic shift and personalized posterior. It would be great if the author can perform the ablation studies on multiple non-homophilous graph datasets and even on homophilous graph datasets.\n\n3. Minor issues\nLine 39 constructs -> construct\n\nLine 96 have achieve -> have achieved\n\nLine 182 equivalent to maximize -> equivalent to maximizing\n\nLine 164 relation context -> relational context\n\nLine 220 undated -> updated\n\nLine 250 affect -> affects\n\nLine 303 an relative improvement -> a relative improvement\n\n[1] Jiao et al. \"Sub-graph Contrast for Scalable Self-Supervised Graph Representation Learning\", ICDM 2020\n\n[2] Jin et al. \"Multi-Scale Contrastive Siamese Networks for Self-Supervised Graph Representation Learning\", IJCAI 2021\n\n[3] Mo et al. \"Simple unsupervised graph representation learning\", AAAI, 2022\n\n[4] Zhao, Han, et al. \"Graph Debiased Contrastive Learning with Joint Representation Clustering\" IJCAI 2021\n\n[5] Ding et al. \"Structural and Semantic Contrastive Learning for Unsupervised Node Representation Learning\", arXiv 2022", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DdfvPxszxm0", "reviewer": "Reviewer_4zvQ", "summary": "This paper focuses on self-supervised learning for node representation learning on non-homophilous graphs. The authors propose a framework called DSSL. DSSL leverages a probabilistic formalization of the problem, and it introduces a latent variable for modeling the semantic structure of graphs. Experiments on a few graph benchmarks show promising results of DSSL.", "questions": "See the weaknesses above.", "limitations": "N/A", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "----- Strengths:\n\n(1) The problem is important.\nNode representation learning is a fundamental problem in the graph machine learning area for its wide downstream applications. Many recent works propose to use graph neural networks for node representation learning, but these methods require a large amount of labeled nodes for training. Different from these works, this paper focuses on self-supervised learning for node representation learning, which is an important problem.\n\n(2) The proposed DSSL framework is principled.\nA framework called DSSL is proposed. The framework uses a probabilistic formalization of the problem, and a mixture model is used to characterize graph structures, where a discrete latent variable is introduced. During training, gumbel-softmax is used to deal with the discrete latent variable. As discussed in the paper, DSSL can be theoretically viewed as to maximize the mutual information between node representations and global semantics. Overall, the DSSL framework is principled with good theoretical results, and I quite like this approach.\n\n(3) The results are encouraging.\nIn the experiment, the authors use a few graph benchmarks for comparison, and DSSL outperforms many competitive baselines.\n\n----- Weaknesses:\n\n(1) Similar ideas of self-supervised learning have been explored in literature.\nIn terms of methodology, the major idea of DSSL is to maximize the conditional probability for each edge. Although this is an intuitive idea, the idea has been widely explored by existing studies. For example, classical graph embedding algorithms (e.g., DeepWalk, LINE, node2vec) also try to maximize the conditional probability for model training. Some more recent works (e.g., GraphSAGE) leverages similar ideas. The major difference between DSSL and these works is that DSSL uses a mixture-model formalization to define the conditional probability on each edge, which is able to approximate true conditional probabilities more precisely, but this idea has also been touched by existing works (e.g., vGraph: A Generative Model for Joint Community Detection and Node Representation Learning). Given all these works, the idea of DSSL is not very new. Also, vGraph is not discussed in the paper, making it hard to judge the contribution of DSSL over vGraph. Thus, it would be helpful if the authors could discuss the advantage of DSSL over vGraph in the revised draft.\n\n(2) Whether non-homophilous graphs are worth studying?\nThe major focus of the paper is on non-homophilous graphs. However, I feel like non-homophilous graphs are not so popular in practice, and homophily exists in most real graphs. Besides, in terms of modeling, I feel like homophilous graphs and non-homophilous graphs are not so different. For example, if we look at the results in the experiment, we can see GraphCL and BGRL achieve competitive results on most homophilous graphs, although they are not specifically designed for non-homophilous graphs. Furthermore, from my understanding, DSSL can be applied to both non-homophilous and homophilous graphs, and I don't see special designs targeting at dealing with non-homophilous graphs. Therefore, I think what DSSL does is not so consistent with the major claim of the paper, and I wonder why the authors position DSSL as modeling non-homophilous graphs rather than general graphs (i.e., both non-homophilous and homophilous graphs)?\n\n(3) The experiment can be further improved.\nIn the experiment, the authors compare DSSL against several competitive baseline methods. Overall, DSSL outperforms all the methods on non-homophilous graphs. However, the experiment mainly presents quantitative results, showing DSSL is a better model for non-homophilous graphs, but the underlying reason is not well explained and validated. Therefore, it might be more convincing if the authors could do some ablations studies or case studies to show the intuition why DSSL has better performance on non-homophilous graphs.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept