Unsupervised Network Embedding Beyond Homophily
Authors: Zhiqiang Zhong
Guadalupe Gonzalez
Daniele Grattarola
Jun Pang
Venue: Accepted by TMLR ()

Abstract: Network embedding (NE) approaches have emerged as a predominant technique to represent complex networks and have benefited numerous tasks. However, most NE approaches rely on a homophily assumption to learn embeddings with the guidance of supervisory signals, leaving the unsupervised heterophilous scenario relatively unexplored. This problem becomes especially relevant in fields where a scarcity of labels exists. Here, we formulate the unsupervised NE task as an r-ego network discrimination problem and develop the SELENE framework for learning on networks with homophily and heterophily. Specifically, we design a dual-channel feature embedding pipeline to discriminate r-ego networks using node attributes and structural information separately. We employ heterophily adapted self-supervised learning objective functions to optimise the framework to learn intrinsic node embeddings. We show that SELENE's components improve the quality of node embeddings, facilitating the discrimination of connected heterophilous nodes. Comprehensive empirical evaluations on both synthetic and real-world datasets with varying homophily ratios validate the effectiveness of SELENE in homophilous and heterophilous settings showing an up to 12.52% clustering accuracy gain.

Published in Transactions on Machine Learning Research (12/2022)
Unsupervised Network Embedding Beyond Homophily
Zhiqiang Zhong University of Luzembourg
Guadalupe Gonzalez
99917@Nc.ac uk
Imperial College London
Danicle Grattarola
grattd@usi.c ch
Universitd della Svizzero italiana
Jun Pang
jun. Dang. paniguni..l.
University of Luzembourg
Reviewed on OpenReview: ht sp //s:
enrevi ew ew. net wwweev/
d= gu. pgg
Abstract
Network embedding (NE) approaches have emerged as a predominant technique to repre- sent. complex networks and have benefited numerous tasks. However, most. NE approaches rely on a homophily assumption learn embeddings with the guidance of supervisory sig- nals, leaving the unsuperoised helerophilous scenario relatively unexplored. This problem becomes especially relevant in fields where scarcity of labels exists. Here, we formulate the unsupervised NE task as an r-ego network discrimination problem and develop the SE- LENE framework for learning on networks with homophily and heterophily. Specifically, we design a dual-channel feature embedding pipeline to discriminate r-ego networks us- ing node attributes and structural information separately. We employ heterophily adapted self-supervised learning objective functions to optimise the framework learn intrinsic node embeddings. We show that. SELENE's components improve the quality of node embeddings, facilitating the discrimination of connected heterophilous nodes. Comprehensive empirical evaluations on both synthetic and real-world datasets with varying homophily ratios vali- date the effectiveness of SELENE in homophilous and heterophilous settings showing an up to 12.52% clustering accuracy gain.
1 Introduction
Network embedding (NE) has become a predominant approach to finding effective data representations of complex systems that take the form of networks (Cui et al.] 2019). NE approaches leveraging graph neural
networks (GNNs) Defferrard et al. 2016 Kipf & Welling 2017 Xu et al.) 2019b Zhong et al., 2022b) have proven effective in (semm))-superviie
settings and achieved remarkable success in various application 2020). However, recent works
areas, such as social, e-commerce, biology, and traffic networks (Zhang et al., demonstrated that classic supervised NE methods powered by GNNs, which typically follow a homophily assumption, have limited representation power on heterophilous networks (Bo al. 2021 Lim et al. 2021
Chien et al. 2021 Zhong et al. 2022a Zheng et al. 2022).
Whereas similar nodes are connected in homophilous networks, the opposite holds for heterophilous networks
in which connected nodes are likely from different classes (Figure (a(b))). For instance, people tend to connect with people of the opposite gender in dating networks (Zhu et. al. 2020) and fraudsters are more likely to connect with customers than other fraudsters in online transaction networks (Pandit et al. 2007).
Traditional GNNs typically fail in heterophilous scenarios because they obtain representations by aggre- gating information from neighbours, acting as low-frequency filter which generates indistinguishable node

---

Published in Transactions on Machine Learning Research (12/2022)
(a) Homophilous network (b) Heterophilous network
(c) Network embedding
ded
CS
Embeddding space
Math Biology
National airport
Selene
International airport
Figure 1: Example homophilous and heterophilous networks ((a): a citation network; (b): an airline transport network). (c) SELENE performs unsupervised network embedding capturing node attributes and structural information to address heterophily.
representations on heterophilous networks (Figure 2 (Bo et al. 2021 Recently, several GNN operators have been introduced to overcome the smoothing effect of traditional GNNs on heterophilous networks (Zheng et al. 2022), , however, they rely heavily on the (semii)-uperrvsse setting. Wei et al. (2022) conduct theo- retical analyses to find out the conditions that GNN models have performance difference synthetic homophiloous/teeeropphioooos datasets. Ma et al. (2022) empirically characterise different heterophily con- ditions and identify the specific conditions that lead to worse GNN model performance under supervised settings. In contrast, the elfectiveness of GNNs in unsupervised settings, iee. learning effective heterophilous representations without any supervision, is relatively unexplored (Xia et al. 2021]. In application areas such as biomedical problems, where scarcity of labels exists, the unsupervised sctting of high interest generate representations for various downstream tasks (Li al., 2022).
Current limitations. We address the task of node clustering under unsupervised heterophilous setting (Figure I (b-c)) (for convenience, we will refer to unsupervised network embedding as NE in the remainder of the text). In this scenario, the first unexplored question to investigate is RQ1: how do existing NE methods perform on heterophilous networks without supervision?
We conduct an empirical study on 10 synthetic networks with a variety of homophily ratios (h, Definition 3 investigate whether h influences the node clustering performance of representative NE methods. Our experimental results, summarised in Figure 3 show that (i) the performance of NE methods that utilise network structure, including heterophilous GNNs designed for supervised settings, decreases significantly when h - 0; (ii) the performance of NE method that only relies raw node altributes is not affected by changes of h, but it is outperformed by other NE methods when h + 1. These two findings directly answer RQ1 and mcanwhile raisc another interesting and challenging question RQ2: could we design a NE frumework that adapls well both homophily and heterophily selfings under no supervision!
Our approach. Motivated by the limitations mentioned above, we approach the NE task as an r-ego net- work discrimination problem and propose the SELf-supErvised Network Embedding (SELENE) framework. Our empirical study suggests that both node attributes and local structure should be leveraged to obtain node embeddings. Therefore, we summarise them into r-ego network and use self-supervised learning (SSL) objective functions to optimise the framework to compute distinguishable node embeddings. Such a design assumes nodes of the same class label share either similar node attributes or r-ego network structure. Specifically, we propose dual-channel embedding pipeline that encodes node attributes and network struc- ture information in parallel (Figure 4.. Next, after revisiting representative NE mechanisms, we introduce identity, and network structure features to enhance the framework's 's ability to capture structural information and distinguish different sampled r-ego networks. Lastly, since network sampling strategies often implicitly follow homophily assumptions, i.c., "positively sampling nearby nodes and negatively sampling the faraway nodes" Yang et al. 2020), we employ negative-sample-rree SSL objective functions, namely, reconstruction loss and Harlow-Twing loss, to optimise the framework.
Extensive evaluation. We empirically evaluate our model and competitive NE methods on both synthetic and real networks covering the full spectrum of low-to-high homophily and various topics, including node clustering, node classification and link prediction. We observe that SELENE achieves significant, performance
2

---

Published in Transactions on Machine Learning Research (12/2022)
gains in both homophily and heterophily in real networks, with an up to 12.52% clustering accuracy gain. Our detailed ablation study confirms the effectiveness of each design component. In synthetic networks h E [0, 1), we observe that SELENE shows better generalisation.
2 Related Work
Node clustering, one of the most fundamental graph analysis tasks, is to group similar nodes into the same category without supervision (Ng et al. 2001 Schaeffer 2007). Over the past decades, many clustering algorithms have been developed and successfully applied to various real-world applications (Belkin & Niyogi 2001). Recently, the breakthroughs in deep learning have lod to paradigm shift in the machine lcarning community, achieving great success on many important tasks, including node clustering. Therefore, deep node clustering has caught significant attention (Pouyanfar et al. 2019 Yang et al. 2017 The basic idea of deep node clustering is to integrate the objective of clustering into the powerful representation ability of deep learning. Hence learning an effective node representation is a prerequisite for deep node chustering. To date, network embedding (NE)-based node clustering methods have achieved state-of-the-a performance and become the de facto clustoring methods.
Network embedding before GNNs. NE techniques aim at embedding the node attributes and structure of complex networks into low-dimensional node representations (Cui al. 2019). Initially, NE was posed the optimisation of an embedding lookup table directly encoding each node a vector. Within this group, several meth based on skip-grams (Mikolov et al. 2013) have been proposed, such as DeepWalk (Perozzi et al. 2014). node2vec (Grover & Leskoved 2016), struc2vec (Ribeiro et al. 2017), etc (Tang et al., 2015; Qiu et al. 2018). Despite the relative success of these NE methods, they often ignore the richness of node attributes and only focus on the network structural information, which hugely limits their performance.
Network embedding with GNNs. Recently, GNNs have shown promising results modelling structural and relational data (Wu et al.) 2021). GNN models capture the structural similarity of nodes through recursive message-passing scheme, using neural networks to implement the message, aggregation, and update functions (Battaglia et al. 2018). The effectiveness of GNNs has been widely proven in (semi)-
supervised settings, and they have achieved remarkable success in various areas (Zhang et al. 2020 Several approaches such as ChebNet (Defferrard et al. 2016), GCN (Kipf & Welling 2017), GraphS AGE Hamilton et al. 2017), CayleyNets (Levie et al. (2017), GWNN (uu et al. 2019a), and GIN (Xu et al.
2019b have led
to remarkable breakthroughs numcrous fields in semii-)uupervsed scttings. However, their effectiveness for unsupervised NE is relatively unexplored. Recently, GNN-based methods for unsupervised NE such DGI Velickovic et al., 2019). GMI (Peng et al., 2020 SDCN (Bo et al.) 2020 and GBT (Bielak et al. 2021 have been proposed, although they were primarily designed for homophilous networks.
Heterophilous network embedding. Recent works have also focused on NE for heterophilous networks and have shown that the representation power of GNNs designed for (semi-)supervised settings is greatly limited on heterophilous networks (Zheng et al. 2022). Some efforts have been dedicated to generalising GNNs to heterophilous networks by introducing complex operations, such as coarsely aggregating higher- order interactions combining the intermediate representations (Zhu et al. 2020 Bo et al. 2021 Lim et al.)
2021 Wei ct al. 2022) conduct thcoretical analyses to determine the conditions that GNN models have
hoomophilous/heeerophhllll /heterpphilluu datasels. Ma et al. (202 empirically char- acterise different heterophily conditions and identify the specific conditions that lead to worse GNN model performance under supervisod settings. Nevertheless, these heterophilous GNNs heavily rely on supervisory information and hence cannot be applied to unsupervised settings (verified in Section and Section 6.3 Latterly, Tang et al. (2022) introduce Neighborhood Wasserstein Reconstruction loss and novel decoder to properly capture node attributes and graph structure to learn discriminate node representations.
performance dilference on synthetic homophilous
3 Notation and Preliminaries
An unweighted network can be formally represented as g = (V, X), where is the set of nodes and [V| = n is the number of nodes, & C V x V is the set of edges, and X E Raxe represents the r-dimensional node
3

---

Published in Transactions on Machine Learning Research (12/2022)
attributes. We let y {yo be set of class labels for all V. For simplicity, we summarise & with an adjacency matrix A E (0. 1
Problem setup. We setup the problem using the unsupervised node clustering task as an example. We first learn node representations Z, E (a)
Rd for all v E V, capturing both node attributes and local network structure. Then, the goal is to infer the unknown class labels yo for all V using a clustering algorithm
the learned node representation Zy (in this paper, we use the well-known K K-means algorithm (Hartigan & Wong 1979 Note that, for convenience, in the following we refer to unsupervised NE simply as NE.
h = 0.2
(b)
Definition 1 (r-hop Neighbourhood N We denole the r-hop neighbourhood of node v by Noo = to d(u, v) I rh. where d(u,v) is the shortest poth distance between u and v. For the network shown in Figure (a), No., = {vo, U1, U2 U1, 17}.
Definition 2 (r-ego Network) (v)) McAAley & Leskovec, 2012 Qiu et al. 2020) Let No S be the r-ego neighbours of node v in G. Their correspordingg r-ego network an induced sub-network of g defined as (v) (Ng, Ex,,) where E == ((N) x NE)
Definition 3 (Homophily Ratio h) The homophily ratio of g describes the relation belween node labels and network struc- ture. Recent works commonly use two measures of homophily, edge homophily (Medge) (Zhu et al, (2021) and node homophily hedge
Figure 2: (a) Network with h = 0.2: (b) the aggregation mechanism in traditional GNNs implicitly follows a homophily assumption as re- sult of duplicated aggregation trees for nearby nodes - as shown for trees rooted in nodes vo and di (du- plicates marked by samc-colourod square).
(Nnode) (Pei et al., 2020), which can be formellled (L.)))) Anode [V] Evev ((u.eEN) Specifically, WEll
181
where hedge evaluates the fraction of edges between nodes with the same class labels; hnode evaluates the overall fraction of neighbouring nodes that have the some class labels. In this poper, we focus only on edge homophily and denote it with h = hedge. Figure (a) shows an example network with h = 0.2.
4 An Experimental Investigation
In this section, we empirically analyse the performance of NE methods on 10 synthotic networks with different homophily ratios (h). The main goal is to investigate (RQ1): how ex- isting NE methods perform on heterophilous networks Specifi- cally, quantify their performance the node clustering task 10 synthetic networks with h 00, 0.9]. A detailed description of the synthetic datasets generation process can be
nodezvec
Clustering Accuracy
80
GAE
GraphSAGF
SDCN
GST
60
H2GEN"
found in Section 6.1 and we refer the reader to Section 6.2 for
40
details on the experimental settings.
Figure illustrates that the clustering accuracy of repre- sentative NE methods that utilise network structure, i.e., node2vec (rrover & Leskoved 2016), GAE (Kipf & Welling
20
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8 0.9
2016), GraphSAGE (Hamilton et al. 2017), SDCN (Bo et al.
2020 GBT (Biclak et al. 2021) and H2GCN (Zhu et al. p020p show outstanding performance when h + 1 but with the decrease of h, their performance decreases significantly. The reason why existing NE methods using network structure fail only when h function or aggregation mechanism designs. For instance, (i) objective functions of node2vec and Graph-
Figure 3: Node clustering accuracy of rep- resentative NE methods on synthetic net- works.
that most of them implicitly follow a homophily assumption, with specific objective
4

---

Published in Transactions on Machine Learning Research (12/2022)
SAGE guide nodes at close distance have similar representations and nodes far away to have different ones; (ūi) the inherent aggregation mechanism of GAF, GraphSAGE, SDCN and GBT naturally assumes local smoothing (Chen et al., 2020) (which is mainly caused by the duplicated aggregation tree for nearby nodes as shown in Figure (b)), which translates into neighbouring nodes having similar representations.
On the other hand, H2GCN", which is specifically designed for heterophilous networks, follows the same trend as the homophilous approaches due to the loss of supervisory signals in the network embedding task. The only method with stable performance across different values of h is AE (Hinton & Salakhutdinov 2006). which is attributable to its reliance raw node attributes only. AE exhibits an apparent advantage against all other models when h < 0.5. This highlights the importance of considering node attributes in the design of NE approaches for networks with heterophily.
5 Network Embedding via r-ego Network Discrimination
In this section, we formalise the main challenges of NE on heterophilous networks. To address these chal- lenges, we present the SELFsupErvised Network Embedding (SELENE) framework. Figure shows the overall view of SELENE.
Challenges. Motivated by the empirical results in Section g we realisc that a NE method for heterophilous networks should have the ability to distinguish nodes with different attributes or structural information. Each node's local structure be flexibly defined by its r-ego network. We further summarise each node's relevant node attribute and structural information into r-ego network and define the NE task as an r-ego network discrimination problem. Then, we address three main rescarch challenges to solve this problem: (RC1) How to leverage node altributes and network structure for NE? (RC2) How to break the inherent homophily assumptions of traditional NE mechanisms? (RC3) How to define an appropriate objective function to optimise the embedding learning process?
The following subsections discuss our solutions address these three challenges and introduce the SELENE framework. In Section [ we provide comprehensive empirical evaluation on both synthetic and real data with varying homophily ratios to validate the effectiveness of SELENE under homophilous and heterophilous settings. We also show that all components in our design are helpful in improving the quality of node embeddings.
5.1 Dual-channel Feature Embedding (RC1)
Motivated by the empirical observation in Section 4 that AE (only based on raw node attributes) has the only stable performance across h E [), and graph structure-based NE approaches show priority when / + 1. Therefore, to learn node embeddings that can discriminate r-ego networks of different nodes, we propose to deal with two important, perspectives, i.e., node attributes and graph structure, separately. We first extract the r-ego network (G)( of each node G. For example, in Figure 4 (2(v) represents 2-ego network instance of G. The empirical analysis of Section hiighlihhtth that node attributes and structural information play a major role in discriminating nodes over networks. Therefore, embedding pipeline to learn node representation from node attributes and network structure separately, as shown in Figure 4 That said, we split r-ego network of each node (v = & } into ego node attribute X, and network structure (v) [WT.ET] And in order to avoid dense ego networks, we adopt one widely adopted neighbour sampler (Hamilton et al., (017)) to restrict the number of sampled nodes of each hop is no more than 15. Appendix C will provide more description about the implementation. Such a design brings two main benefits: (i) both important sources of information can be well utilised without interfering with each other, and (ii) the inherent homophily assumptions of NE methods can be greatly alleviated, an issue we will address in the following subsection. We will empirically discuss the effectiveness
propose dual-channel feature
of the dual channel feature embedding pipeline in Section 6.4
5

---

Published in Transactions on Machine Learning Research (12/2022)
Input network
Node attributes
fo
fo
Distertion
fo
features
X
NN
fo
X
r-ego network
X
extraction
Network structure
Distortion
fo
Add structural features
Cartt
GNN
G2(M)
fo
Figure We propose a dual-channel feature embedding pipeline to learn node representations separately from node attributes and network structure. Node feature attribute embeddings are optimised using an autoencoder trained reconstruct the input data (X, X), and refined through the contrastive loss CBr(H(L) ) The network structure encoder is optimised using LBT U(2).. The final node repre- sentation obtained by applying COMBINE to the generated node attribute representation and network structure representation U.
5.2 r-ego Network Feature Extraction (RC2)
Node attribute encoder module. As previously mentioned, learning effective node attribute representa- tions is of great importance for NE. In this paper, employ the basic Autoencoder (Hinton & Salakhut- dinov 2006) to learn representations of raw node attributes, which can be replaced by more sophisticated encoders (Masci et al. 2011 Makhzani et al. 2015 Malhotra et al., 2016) to obtain higher performance. We
assume an L-layers Autoencoder (fo), with the formulation of the 6-th encoding layer being:
H 6(W(" + +b!
(1)
where is non-linear activation function such as ReLU Naii & Hinton 2010 or PReLU (He et al. 2015). (((11) E Raaxdr: the hidden node altribule representations layer f 1, with de- being the dimensionality of this layer's hidden representation. w! E Rddi and (2) E Rd are trainable weight matrix and bias of the b-th layer in the encoder. Node representations H. fe(X.) !!!) are obtained after successive application of L encoding layers.
Despite the significant. success of GNNs in a variety of network-related tasks, their representation power in network structural representation learning is limited (Xul et al. 2019b). In order to obtain invariant node structural ropresentations so that nodes with differont ego network structures are assigned different representations, we employ the identity feature You et al.) 2021 and structural features (Li al. 2020). In this paper, we adopt variant shortest path distance (SPD) as node structural features (Xstrue). After, we further inject the node identity features (Xia) as augment features, hence we have node feature matrix X = Xstruc + Xia for each ego-network.
Identity and network structure features.
Network structure encoder module. Over the past few years, numerous GNNs have been proposed to learn node representations from network-structured data, including spectral GNNs (i.e., ChebNet (Deffer- rard et al.] 22166). CayletNet (Levic al. (017)) and GWNN (Xu al.] (019a)) and spatial GNNs (i.c., GraphSAGE (Hamilton et al. 2017), GAT (Velickovic et al., 2018)), GIN (Xu et al. (019b)). For the sake of simplicity, adopt simple GNN variant, i.e., GCN (Kipf & Welling 2017). the building block of the

---

Published in Transactions on Machine Learning Research (12/2022)
network structure encoder (fe). The l-th layer of a GCN for v's r-ego network can be formally defined as:
U = A 11((e11)
(2)
with A = A I, where I is the identity matrix, and D is the diagonal node degree matrix of A. U(t-1) e Rnxde is the hidden representation of nodes in layer L - 1, with dz-1 being the dimensionality of this layer's representation, and U = X. w(() E Rdde- is trainable parameter matrix. o is non-lincar activation function such as ReLU or Sigmoid (Han & Moraga 1995) function. Structural representations U, (v) = ((2) are obtained after successive applications of L layers.
5.3 Heterophily Adapted Supervuue Learning (RC3)
The objective function plays a significant role in NE tasks. Several objective functions have been proposed for NE, such network reconstruction loss (Kipf & Welling 2016), distribution approximating loss (Perozzi jet al.) 2014) and node distance approximating loss (Hamilton et al., 2017). Nevertheless, none of them is suitable for NE optimisation on heterophilous networks because of the homophily assumptions used to determine (dis)similar pairs. In heterophilous networks, node distance on network alone does not determine (dis (iis)siiilrrit,, i.e, connected nodes are not necessarily similar, and nodes far apart are not necessarily dissimilar. This removes the need for connected nodes to be close in the embedding space and for disconnected nodes to be far apart in the embedding space.
Inspired by the latest success of negative-sample--res self-supervised learning (SSL), we adopt the Barlow- Twins (BT) [Zbontar et al. 2021 our overall optimisation objective. Consequently, the invariance term makes the representation invariant to the distortions applied; the redundancy reduction term lets the rep- resentation units contain non-redundant information about the target sample. More details about the BT method can be found Appendix F.
We discuss the feasibility of different objective functions Section 6.4
Distortion. To apply the BT method optimise our framework, we have first generate distorted samples for target r-ego network instances. Due to the dual-channel feature embedding pipeline, introduce fAug and fhug to generate distorted node attribute and network structure instances, respectively. Our data distortion method adopts a similar strategy as You et al. (2020); Bielak et al. (2021) that randomly masks node attributes and edges with probability Pr.Pe: Formally, y, this distortion process can be represented as:
(X.. P.) (x(), (())
Anng (C.( (1) (o),
Barlow-Twins loss function. Based the two pairs of distorted instances, two pairs of representations (U!!) U(2) and (H!"), H!?) can be computed by applying fo and f8, respectively. Then, BT method can be employed to evaluate the computed representations and guide the framework optimisation. Using reprosentations (H(), (2) as example, the loss value is formally computed as:
M
I M
LBT (HO) H = Σ C1)-
+
Σ
C
(4)
34
Σ, H
where Cij
A defines the trade-off between the invariance and redundancy V "E "
reduction terms, b is the batch indexes, and i, index the vector dimension of the input representation vectors. We adopt the default settings as Zbontar et al. (2021).
Node attribute reconstruction loss function. In addition to the general objective function, LAT, we adopt another objective function, i.e., node attribute reconstruction loss L to optimise the node attribute encoder specifically. Following the node attribute encoder (Eq the decoder reconstructs input node attributes from the computed node representations H. Typically, a decoder has the same structure the encoder by reversing the order of layers. Its f-th fully connected layer can be formally represented:
7

---

Published in Transactions on Machine Learning Research (12/2022)
2 - H ( + )) Reconstructed node attributes X H obtained after successive applications of L decoding layers. We optimise the autoencoder parameters by minimising the difference between raw node attributes X and reconstructed node attributes X with:
Roo ( X)
| 2/11 X
X
(5)
Empowered with Barlow-Twins and node attribute reconstruction loss, we can optimise the framework's s encoders under heterophilous settings. The node attribute encoder is optimised with CBr (Eq. 4 and Re (Eq. 5), and the network structure encoder is optimised with LeT (Eq. The overall loss function is C = Lnr(UU) U(2) + (ar(H() ,H())) + L X).
Final node representations. Representations capturing node attributes (H) and structural context (U) are combined to obtain expressive and powcrful representations as: Z COMBINE(H, U) where COM- BINE(.) be any commonly used operation in GNNs (Xu el al., 2019b), such mean, mas, sum and concat. We utilise concat in all our experiments, allowing for independent integration of representations learnt by the dual-channel architecture.
5.4 Summary
Algorithm 1: SELf-supErvssed Network Embedding (SELENE) Framework
Input:
Network g = (V,Ex))=
Node attribute encoder fe and decoder fer
Network structure encoder (GNN) fa
Node attribute distortion function ion lung and network distortion function S2
Output: node representations
Sample a set of r-ego networks (1) (2)... (m()) from 9;
Extract network structure of each r-ego network (v) and enhance each with identity features (Xa))
and network structure features (Xstrue) to obtain (v) = (Wr, 8 8)
Generate distorted node attribute matrix instances (1) and x
Generate two distorted instances (g. (v), repeat
g(2) (v)) for cach r-ego network (v)
Initialise loss L as zero:
for each node v E do
H. = fo(X.),
X = (H,);
H )) = fo(x''),
H = fo(x!))
9
U (s( (v)),
T = ls( (v));
10
C= (U.)) _!2) + CBT(H!" ! + Lee (X,, Xo)
11
12
end
13
Update 8 and 8 by descending the gradients Vo,LC;
14
until Converyence;
15 H H fo)o(
for each node v E V do
17 U, = fu)),
18 end
19 Z COMBINE U)
Here, we summarise SELENE Algorithm [ to provide a general overview of our framework. Given as input a graph and node attribute encoder fo and docoder før network structure encoder fa, node attributo distortion function fX Aug and network distortion function f Our algorithm is motivated by the empirical results in Section 4 which showed that NE method for heterophilous nerworks should have the ability to
8

---

Published in Transactions on Machine Learning Research (12/2022)
distinguish nodes with different attributes or structural information. Therefore, we summarise each node's relevant node attribute and structural information into an r-ego network and define the NE task as an r-ego network discrimination problem. We sample set of r-ego networks {9r (2))
from ç (Line 1). Next, we extract network structure of each r-ego network (r(v) and enhance each with identity features (Xia) and network structure features (Xstree to obtain (r) (Ny Eg. X} (Line 2). Then, we generate distorted node attribute matrix instances ( and X and two distorted instances (g. g. (v)) for each r-ego network (e) (Line 3-4). For cach node v E 9, we compute its node attribute embodding (H.) and distorted node attribute embeddings (H, H²²),, ), and network structure embeddings (U,) U!?) (Line 8-10). Then, Barlow-Twiin and network attribute reconstruction loss functions are employed to compute the final loss L (Line 11). We update SELENE's parameters (0, 6) by descending the gradient Ve.&. (Line 13) until convergence. After the model is trained, we compute node attribute embedding H. and network structure embedding U. to obtain the final node representations Z by combining H and U (Linc 15-19).
Discussion. The description above indicates that the design of SELENE assumes nodes of the same class label share either similar node attributes or r-ego network structure. Under this assumption, we can learn node representations (Z) to distinguish nodes of different class labels from the perspoctive of node attributes (H) r-ego net work structure (U). Nevertheless, if nodes of different class labels have similar node altribules and r-ego network structure, it is hard for SELENE to distinguish them. We address this limitation as a very interesting future work to explore.
6 Evaluation
6.1
Real-world and Synthetic Datasets
Real-world datasets. We use a total of 12 real-world datasets (Texas (Pei et al. 2020 Wisconsin (Pei
ct al.
2020), Actor (Pei ct al. 2020), Chameleon (Rozemberczki et al. 2021 ), USA-Airports (Ribeiro et al.
2017
Cornell (Pei et al. 20200) Europe-Airports (Ribeiro et al.) 2017). Brazil-Aine Airports (Ribeiro et al. 2017)
Deezer- Deezer-Furope (Rozembeezkki & Sarkar] (020)). Citeseer (Kipl & Welling 2017), DBLP (Fu et al.] 2020
Pubmed (Kipf & Welling (017]) in diverse domains (web-page, citation, co-author, flight transport and
online user relation). All real-world datascts are available onlind"] Statistics information is summarised in
Table 4 of Appendix|] A
Synthetic datasets. Moreover, we generate random synthetic networks with various homophily ratios h by adopting similar approach to Abu-El-Haija et al. (2019); Kim & Oh| (2021). Specifically, each synthetic network has 10 classes and 500 nodes per class. Nodes are assigned random features sampled from 2D Gaussians, and each datasct has 10 networks with h E 0., 0.9]. The detailed data generation process can be found in Appendix A
6.2 Experimental Setup
We compare our framework SELENE 2 with 12 competing NE methods terms of the different challenging
graph analysis tasks, including node clustering, node class prediction and link prediction. We adopt 2 different competing NE methods without NNs, including node2vec (N2V) &Grover & Leskoved 2016) and struc2vec (S2V) (Ribeiro et al.
2017). We adopt 10 additional competing NE methods using NNs, including
AE (Hinton & Salakhutdinov 2006), GAE (Kipf & Welling 2016), GraphSAGE (SAGE) (Hamilton et al.
2017), DGI (Velickovic et al.]
2019). SDCN (Bo et al. 2020), GMI (Peng et al.
2020). GBT (Bielak et al.
2021 H2GCN (Zhu et al.] 2020), FAGCN (Bo et al. 2021 and GPRGNN
Chien et al. 2021). Note 2021) strategy to network-
that GBT an SSL approach that applies the Barlow- Twins (Zbontar et al.
structured data. Albeit providing a new model training strategy, the basic GNN building blocks remain the same, hence still maintaining a homophily assumption. H2GCN, FAGCN and GPRGNN are state-of- the-art (SOTA) heterophilous GNN operators for supervised settings. Here, we train them using the same mechanism as GBT to adapt them to the unsupervised setting. We rename the unsupervised adaptations of
Ihttps:/ //ppttrc/pytocchee wewate-ggogeeeeeeeee
Code and data are available al:

---

Published in Transactions on Machine Learning Research (12/2022)
Table 1: Node clustering results on real-world datasets. The bold and underline numbers represent the top-2 results. OOM: out-of-memory
Datases
Motries
AF
N2V
S2V
GAF
SAGE
SDCN
DGT
GMI
GBT
H2GCN
FAGCN CPRGNN
Ouns
| (96)
Heterophilous dlstaseets
ACC
50.49
48.80
19.73
12.02
56.83
14.01
35. 35.74
35.19
55,46
58.80
57.92
57.50
65.23
10,94
Texas
NMI
16.63
2.58
18.61
8.40
16.97
14.24
8.73
7.72
10.17
22.49
23.35
22.83
25.40
8.78
h = 0.11
All
14.6
-1.62
20.97
10.83
23.50
10.65
8.25
2.96
12.10
25.04
22.54
23.51
34.21
36.62
Wisc.
MCC
58.61
41.39
43.03
37.81
46.29
25
44.58
36.97
48.01
64.18
61.91
61.84
71.69
11.70
NMI
30:92
4.23
11:23
9.19
10.16
8.46
10:12
11.08
7.55
20.64
27.35
20.54
39.51
27.78
k 0.20
ARI
28.53
-0.48
11.50
5.2
6.06
3.67
10.31
3.74
3.55
32.61
31.56
30.53
43.48
33.33
ACC
24.19
25.02
23.45
23.08
23.67
24.26
26.18
24.68
25.55
25.61
25.80
29.03
12.52
Actor
h-
NMI
0.97
0.00
0.04
0.18
0.58
0,08
1.38
0.201
0.74
33.21
3.222
3.21
4.72
46.13
ARI
0.50
0.06
-0.05
-0.01
0.22
-0.01
0.07
0.41
-0.57
0.31
0,31
0.31
1.81
268. 00
Chamel.
ACC
35.68
21.31
26.34
32,76
31.01
33.5
27.77
25.73
32:21
30.62
31.33
31.62
38.97
9:222
h = 0.23
NMI
10.38
0.31
3.55
11.60
10.55
9.57
4.42
2.5
10.56
14:62
11.71
10.31
20.63
-0.24
ARI
3.80
0..02
1.82
1.65
6,16
5.86
1.85
0.52
7.01
4.78
5.16
5.01
15.94
127.39
USA-Alr.
ACC
55.24
26. 29
27.58
30.84
32.96
353.52
33.36
28.69
34.96
39.01
38.82
39.63
58,90
6.63
NMI
30.13
0.25
0.44
2.67
5.52
0.6
5.27
12.43
12.
31.17
3.15
h - 0.25
ART
24.20
-0.05
0.09
2.67
2.52
1.93
4.95
0.29
3.42
9.48
9.33
9.02
25.53
5.44
Cornell
ACC
62. 19
50.96
32.68
43.72
44.7
36.94
44.1
33.55
52.19
64.97
56.23
55.33
57.96
3.08
h - 0.31
NMI
17.08
5.84
1.54
4.33
5.79
5.26
5.94
17.05
17.08
16.90
17.32
1.41
ARL
17.41
0.18
-2.20
6.51
5.64
3.38
4.87
3.05
10.63
19.50
19.88
19.21
23.03
15.85
ACC
55.55 36
30.75
36.88
31.81
31.75
37.37
35.59
35.31
39.73
37.27
42.
366 63
57.80
1.11
En.-Arr.
NMI
32
3.00
6.15
10.15
2.10
8.45
10.77
11.08
9.44
9.08
16.81
11.60
34.25
5.68
& = 0.31
ARI
24.24
0.883
4.49
7.37
1.16
5.31
8.44
8.18
7.87
5.3
11,98
9.41
25.69
5.98
Bra-Air.
ACC
21.68
30.338
38.93
36.64
37.02
38.7
37.1
38.93
40.92
43.97
44.2
46.42
79.12
10.38
A = 0.31
NMI
49:26
2.5
10.23
10.96
6,89
14.05
10.64
12.62
12.16
22.37
22.67
201.10
55,90
13.18
ARI
42.93
-0.22
5.45
6.56
4.18
7.27
7.02
9.11
8.31
13:99
15.06
53.21
23.95
ACC
55.88
52.97
00M
51.51
51.06
54.76
53.16
00M
00M
56.81
56.81
53.22
59.94
5.51
h = 0.53
Deezer.
NMI
0.28
0.0
0OM
0.13
0.16
0.17
0.05
0OM
OOM
0.27
0.27
0.01
0.34
21.43
ARI
0.81
0.02
OOM
-0.02
0.61
-0.23
OOM
OOM
1.22
0.77
1.33
9.02
Homophiions
datusets
ACC
58.79
200.76
21:22
48.37
49.28
54.86
58.94
59.01
57.21
47.33
47.42
45.83
60.02
0.27
Citesser
NMI
30.91
0.35
1.18
24.59
22.97
30.37
32.6
32.11
31.9
20.48
20.18
20.58
32.74
0.31
h - 0.74
ART
30.29
-0.01
0.17
19.50
19.21
29.7
33.
33.09
33.17
18.03
17.93
18.11
33.46
0.87
ACC
48.50
29.19
31.66
67.81
48.08
61.34
58.22
03.28
13.10
41.87
41.25
43.96
75.74
3.61
DBLP
h - 0.80
NMI
18.98
0.14
1.33
28.94
16.46
27.13
29.98
33.91
42.21
11.04
10.60
11.27
44.17
4.64
AR1
15.15
-0.04
13.38
27.77
26.88
28.77
42.57
4.67
4.92
46.35
8.88
Pubmed
ACC
05.31
32
37.39
12.08
67.08
61.9
65.47
OOM
00M
56.71
56.88
68.81
67,98
0.47
NMI
26.80
0.02
0.07
1.28
30.71
19.71
28.05
00M
00M
17.15
16.91
17.01
31.14
1.40
à = 0.80
ARI
25.98
0.09
0.15
29.10
27.25
0OM
00M
16.51
26.24
29.79
2.37
H2GCN, FAGCN and GPRGNN as H2GCN' FAGCN and GPRGNN", respectively. See Appendix B and
Appendix C for details of all compoting methods and implementation.
6.3 Experimental Results
Node clustering. Node clustering results on homophilous and heterophilous real-world datasets are sum- marised in Table [ where we see that SELENE is the perf-rerro method in all heterophilous datasets. In particular, compared to the best results of competing models, our framework achieves a significant im- provement of up to 12.52% on ACC, 46.13% on NMI and 268% on ARI. Such outstanding performance gain demonstrates that SELENE successfully integrates the important node attributes and network structure in- formation into node representations. An interesting case is the comparison of SELENE, H2GCN* FAGON and GBT, given that H2GCN*, FAGCN* and GET also utilise the Barlow-Twins objective function to opti- mise a GNN model, and the major difference between H2GCN* FAGCN" GBT and SELENE our designs to address RC1 and RC2. SELENE has a superior performance in all heterophilous datasets, indicating the effectiveness of designs and showing that simply porting supervised models to unsupervised scenarios is not appropriate. Results of node clustering on homophilous networks, contained in Table [ show that SELENE achieves new SOTA performance. This demonstrates SELENE's suitability for homophilous networks and proves the flexibility of our designs. For the Symthelic networks, we present SELENE vs SDCN (SOTA node clustering model) vs GBT (SOTA graph contrastive learning model) vs FAGCN* (SOTA heterophilous GNN model) clustering accuracy in Figure (a). SELENE achieves the best performance on the synthetic datasets, which shows SELENE adapts well to homophily homophily/heterrphiiy /htterophehll scenarios with(out) contextually raw node attributes. Moreover, FAGCN* performs worse on 10 synthetic networks, which indicates that the
10

---

Published in Transactions on Machine Learning Research (12/2022)
heterophilous GNN models designed for supervised settings do not adapt well to unsupervised settings be- cause they need supervision information to train the more complex aggregation mechanism. In addition, we observe that SELENE has no significant improvement with h S 0.4 because the network structure encoder's expressive power on extreme homophily is limited. Overall, SELENE still works significantly better for homophilous graphs, but deteriorates more gracefully compared to prior works while h 0.
Node classification and link prediction. Meanwhile, we acknowledge that some works adopt different experiment pipeline that utilises node labels to train classifier, after obtaining unsupervised node repre- sentations, to predict labels of test nodes (Velickovic et al., 2019 Peng et al.) 2020 Bielak et al. 2021 Hence, we provide results of a number of real-world datasots that follow this setting to show the generality of SELENE. Results in Table 2 show that SELENE achieves the best classification performance on all datasets with homophily and heterophily. Moreover, we also report another major graph analysis task, ie.. link prodiction, performances of number of real-world datasets in Table 3 From the experimental results, we can find that (i) the homophily ratio has a significant influence on the link prediction task, and (ti SELENE performs priority on this lask well. For more experimental settings and experimental results discussion, refer to Appendix D
Table 2: Node classification results on real-world datasets. 2op-2 results.
The bold and underline numbers represent the
Dataset
F1-score
N2v
S2V
GAE
SAGE
SDCN
DGI
GMI
GBT
H2GCN"
FAGCN
GPRGNN
Olrs
(%)
Heterophilons datasots
Miero
0.598
0.509
0.592
0.5
0.563
0.552
0.541
0.505
0.461
0.523
0.607
0.561
0.643
5.93
Texas
Marro
0.284
0.165
0.335
0.253
0.301
0.153
0.266
0.295
0.253
0.186
0.265
0.262
0.381
13.73
Miero
0.284
0.240
0.227
0.254
0.277
0.252
0.272
0.272
0.245
0,244
0.284
0.341
20.07
Actor
Macro
0.194
0.178
0.190
0.164
0.204
0.125
0.211
0.224
0.138
0.166
0.192
0.274
12.30
USA-Air.
Micro
0,5:11
0.2399
0:251
0.309
0.311
0.302
0.338
0.253
0.35
0.535
0.527
0.153
0.565
4.41
Macro
0.476
0.235
0.253
0.236
0.200
0.298
0.260
0.221
0.288
0.483
0.454
0.370
0.532
10.
Bra-Air.
Micro
0.611
0.247
0.301
0.331
0.312
0.301
0.321
0.329
0.371
0.465
0.507
0.167
0.715
17.02
Marro
0.538
0.203
0.284
0.244
0.295
0.281
0.244
0.249
0.319
0.415
0.420
0.426
0.692
28.62
Homophilous datsseta
DBLP
Micro
0.746
0.269
0.334
0.768
0.732
0.638
0.792
0.811
0.744
0.413
0.560
0.643 0.588
0.813
0.25
Macro
0.737
0.227
0.305
0.758
0.721
0.633
0.781
0.801
0.736
0.371
0.536
0.810
0.75
Table 3: Link prediction results on real-world datasets. The bold and underline numbers represent the top-2
results.
Dataset
Metric
AE
N2V
52V
GAE
SAGE
SDCN
DG1
GMI
GBT
H2GCN
FAGCN
GPRGNN
Ours
Heterophilous datasets
Texas
ROC-AUC
0.529
0.549
0.571
0.634
0.559
0.640
0.787
0.777
0.783
0.451
0.673
0.782
0.784
Actor
ROC-AUC
0.501
0.673
0.652
0.688
0.634
0.532
0.626
0.609
0.398
0.679
0.613
0.796
0.725
USA-Air.
ROC-AUC
0.518
0.714
0.685
0.842
0.595
0.528
0.857
0.854
0.867
0.667
0.612
0.925
0.871
Bra--Arr
ROC-AUC
0.665
0.592
0.637
0.787
0.615
0.677
0.855
0.791
0.786
0.702
0.686
0.538
Homophilous datasets
DBLP
ROC-AUC
0.872 0.758
0.717
0.870
0.841
0.628
0.939
0.884
0.892
0.736
0.764
0.890
0.908
6.4 Analysis
Model scalability. The network structure encoder module categorised as a local network algorithm Teng 2016), which only involves local exploration of the network structure. On the other hand, the node attribute encoder module naturally supports the mini-batch mechanism. Therefore, our design enables SELENE to scale to representation learning on large-scale networks and to be friendly to distributed computing settings (Qiu et al.] 2020). Table [ illustrates that three competing methods, i.c., struc2vec, GMI and GBT, have out-of-memory issues on large datasets, i.e., Pubmed and Deezer,, an issue which did not arise with SELENE. This shows SELENE's advantage in handling large-scale networks due to its local network algorithm characteristic.
Effectiveness of loss function. thus sought to test the effectiveness of each component. In particular, we ablate each component and evaluate
The objective loss function of SELENE contains three components, and we
11

---

Published in Transactions on Machine Learning Research (12/2022)
(a)
(b)
(c)
(d)
80
N447
11.01
72-34
05:24
60:07
76:66
Clusteing Accuracy
90
SDON GRT HOSCN
Clastering Accuracy
60
41.00
67.15
62
70
80
50.09
15.2
10:37
93
-9
47.55
46.73
03.77
54
08.00
30
10
47:35
69:44
02:00
53
0444
01.00
USA/Arparts
Chameloon Data
DSLP
OBT
Mardly sboc
0.0
6.1
02
03
04
09
Model
Figure 5: (a) Clustering accuracy comparison on synthetic networks. (b) Loss function ablation on real-world
networks. (c) Framework component exploration on real-world networks. (d) Hyperparameter influences exploration on synthetic-0.8.
the obtained node representations on two heterophilous datasets (USA-Air., Chamel.) and one homophilous dataset (DBLP). Results shown in Figure (b) indicate that the ablation of any component decreases the model's performance. Specifically, the ablation of Lnee (X. X) causes steeper performance degradation in heterophilous datasets, and the ablation of Lsr(UA) U(2)) causes steeper performance degradation in homophilous datasets, which indicates the importance of node attributes and network structure in information for heterophilous and homophilous networks, respectively (consistent with observations in Section g
Effectiveness of dual-channel feature embedding pipeline. SELENE contains novel dual-channel features embedding pipeline to integrate node attributes and network structure information, thus, we conduct an ablation study to explore the effectiveness of this pipeline. We first remove the pipeline and only use the Barlow-Twing loss function to train a vanilla GCN encoding module (such a structure is the same as GBT, hence we remark it as GBT). Next, we add the network structure channel, which includes r-ego network extraction, anonymisation and distortion. Lastly, we add the node attribute channel to form the complete SELENE framework. Experimental results are shown in Figure (c). Overall, we observe that the design of each channel is useful for learning better representation, with the node attribute channel playing a major role
in the embedding of heterophilous networks. Note that adding the node attribute channel slightly decreases
the clustering accuracy for the homophilous dataset, i.c., DBLP, but it is still competitive.
Influence of P3 and Pa. We present SELENE's clustering accuracy on synthetic-O.s with different Pa and Pe in Figure (d). The figure indicates that hyperparameters of distortion methods significantly influence representation quality.
Effectiveness of heterophily adopted self-supervised learning. We intuitively discussed the impor- tance of selecting proper objective function for heterophily NE' tasks in Section (.3om55333) 5.3 explained the reason for selecting reconstruction loss (Eq. 5 and BT loss (Eq. 4b. Experimental results demonstrate the effec- tiveness of heterophily adopted self-supervised learning objective functions. For instance, SELENE shows priority compared with the network reconstruction
model (GAE), distribution approximating loss-based model (N2V), node distance approximating based model (SAGE), negative-sampling based model (DGI) and mutual information-base model (GMI).
7 Conclusion and Future Directions
In this paper, we focused on the unsupervised network embedding task with challenging heterophily settings and tackled two main research questions. First, we showed through an empirical investigation that the performance of existing embedding methods that utilise network structure decreases significantly with the decrease of network homophily ratio. Second, to address the identified limitations, which effectively fuses node attributes and network structure information without additional supervision. Comprchensive experiments demonstrated the significant performance of SELENE, and additional ablation analysis confirms the elfectiveness of components of SELENE on real-world and synthetic networks. As future work, (i) we propose to explore the Information Bottleneck (Tishby & Zaslavsky 2015 Wu et al. 2020) of network embedding to thcoretically define the optimal representation of an arbitrary network (Zügner et al., 2018); (ii) designing more powerful unsupervised network structure encoder for extreme heterophilous networks is also a promising future work.
proposed SELENE,
12

---

Published in Transactions on Machine Learning Research (12/2022)
References
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 2019 International Conference on Machine Learning (ICML), volume 97, pp. 21-29. PMLR, 2019.
Peter W. Battaglia, Jessica B. Hamrick, Victor Bapst, Alvaro Gonzaez- Vinícius Flores Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Çaglar Gülçehre, H. Francis Song, Andrew J. Ballard, Justin Gilmer, George E. Dahl, Ashish Vaswani, Kelsey R. Allen, Charles Nash, Victoria Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Pushmeet Kohli, Matthew Botvinick, Oriol Vinyals, Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. CoRR, abs/1806.00 1////1006001266 2018.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clus- tering. In Proceedings of the 2001 Annual Conference on Neural Information Processing Systems (NIPS), pp. 585 591, 2001.
Piotr Bielak, Tomasz Kajdanowicz, and Nitesh V. Chawla. Graph barlow twins: A self-supervised represen- talion learning framework for graphs. CoRR,
2021.
Deyu Bo, Xiao Wang, Chuan Shi, Meiqi Zhu, Emiao Lu, and Peng Cui. Structural deep clustering network. In Proceedings of the 2020 International Conference on World Wide Web (WWW), pp. 1400-1410 ACM, 2020.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convo- lutional networks. In Proceedings of the 2021 AAAI Conference on Artificial Intelligence (AAAI), pp. 3950-3957, 2021.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring and relieving the over-smoothing problem for graph neural networks from the topologiaal view. In Proceedings of the 2020 AAAI Conference on Artificial Intelligence (AAAT), pp. 3438 3445, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In Proceedings of the 2021 International Conference on Learning Representations (ICLR), 2021.
Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. A survey on network embedding, IEEE Trunsactions on Knowledge and Data Engineering (TKDE), 31(5):833 852, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of the 2016 Annual Conference Neural Information Processing Systems (NIPS), pp. 3837 3845, 2016.
Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. MAGNN: metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of the 2020 International Conference on World Wide Web (WWW), pp. 2331-2341. ACM, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 2016 ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 855 864. ACM, 2016.
William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 2017 Annual Conference on Neural Information Processing Systems (NIPS), pp. 1035-1035, 2017.
Jun Han and Clandio Moraga. The influence of the sigmoid function paramcters on the speed of back- propagation learning. In Proceedings of the 1995 International Workshop on Artificial Neural Networks (TWANN), pp. 005-201.66 Springer, 1995.
13

---

Published in Transactions on Machine Learning Research (12/2022)
John A Hartigan and Manchek A Wong. Algorithm as 136: A k-means clustering algorithm. Journal of the Royal Stalistical Sociely. Series C (Applied Slatistics), (8(1):100-108, 1979.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. In Proceedingss of the 2015 IEEF International Conference on Computer Vision (ICCV), pp. 1026-1034, 2015.
Geoffrey E Hinton and Ruslan R Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313:504-507, 2006.
Dongkwan Kim and Alice Oh. How to find your friendly neighborhood: Graph attention design with self- supervision. In Proceedings of the 2021 International Conference Learning Representations (ICLR), 2021.
Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, abs/1611.07308, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the 2017 International Conference on Learning Representations (ICLR), 2017.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M. Bronstein. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Signal Processing Magazine, 67(1):97 109, 2017.
Michelle M. Li, Kexin Huang, and Marinka Zitnik. Graph representation learning in biomedicine and healtheare. Nalure Biomedical Engineering, 2022.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance encoding - design provably more powerful graph neural networks for structural representation learning. In Proceedings of the 2020 Annual Conference Newral Information Processing Systems (NeurPPS), pp. 4465-4478, 2020.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. In Proceedings of the 2021 Annual Conference Neural Information Processing Systems (NeurIPS), pp. 20887 20887-20902, 2021.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In Proceedings of the 2022 International Conference on Learning Representations (ICLR), 2022.
Alireza Makhzani, Jonathon Shlens, Navdeep Jaitly, and Ian J. Goodfellow. Lstm-based encoder-decoder for multi-sensor anomaly detection. CoRR, abs/1511.05644 2013.
Pankaj Malhotra, Anusha Ramakrishnan, Gaurangi Anand, Lovekesh Vig, Puncet Agarwal, and Gautam ShrofT. Lstm-based encoder-decoder for multi-sensor anomaly detection. CoRR, abs//100700015s 001448, 2016.
Jonathan Masci, Ueli Meier, Dan C. Ciresan, and Jürgen Schmidhuber. Stackod convolutional auto-encoders for hierarchical feature extraction. In Proceedings of the 2011 International Conference on Artificial Neural Networks (ICANN), pp. 59- Springer, 2011.
Julian McAuley and Jure Leskovec. Learning to discover social circles in ego networks. In Proceedings of the 2012 Annual Conference on Neural Information Processing Systems (NIPS), pp. 548-556, 2012.
Tomas Mikolov, Πya Sutskever, Kai Chen, Greg S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionally. In Proceedings of the 2013 Annual Conference on Neural Information Processing Systems (NIPS), pp. 3111-3119, 2013.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 2010 International Conference on Machine Learning (ICML), pp. 807 814, 2010.
Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Proceedings of the 2001 Annual Conference on Neural Information Processing Systems (NIPS), pp. 849 849-856, 2001.
14

---

Published in Transactions on Machine Learning Research (12/2022)
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 2007 International Conference on World Wide Web (WWW), pp. 201 210. ACM, 2007.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional nelworks. In Proceedings of the 2020 International Conference on Learning Representalions (ICLR), 2020.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proceedings of the 2020 International Conference on World Wide Web (WWW), pp. 259 270. ACM, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 2014 ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 701 710. ACM, 2014.
Samira Pouyanfar, Saad Sadiq, Yilin Yan, Haiman Tian, Yudong Tao, Maria F. Presa Reyes, Mei-Ling Shyu, Shu-Ching Chen, and S. S. lyengar. A survey deep learning: Algorithms, techniques, and applications. ACM Computing Surveys, 51(5) 92:11-93::9 2019.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as malrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the 2018 ACM International Conference on Web Search and Data Mining (WSDM), pp. 459-467. ACM, 2018
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. GCC: graph contrastive coding for graph neural network pre-training, In Proceedings of the 2020 ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 1150-1160, 2020.
Leonardo Filipe Rodrigues Ribeiro, Pedro H. P. Saverese, and Daniel R. Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 2017 ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 385-394, 2017.
Benedek Rozemberezki and Rik Sarkar. Characteristic functions on graphs: Birds of a feather, from sta- tistical descriptors to parametric models. In Proceedings of the 2020 ACM International Conference Information and Knowledge Management (CIKM), pp. 1334, 2020.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2), 2021.
Satu Elisa Schaeffer. Graph clustering. Computer science review, 1(1):27-64, 2007.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 2015 International Conference on World Wide Web (WWW), pp. 1067-1077. ACM, 2015.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Pro- ceedings of the 2009 ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. -176 2009.
Mingyue Tang, Pan Li, and Carl Yang. Graph auto-encoder via neighborhood wasserstein reconstruction. In Proceedings of the 2022 International Conference on Learning Representations (ICLR), 2022.
Shang-Hua Teng. Scalable algorithms for data and network analysis. Foundations and Trends in Theoretical Computer Science, 12(1-2):1 274, 2016.
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 IEEE Information Theory Workshop (ITW), pp. 1-5. IEFF, 2015.
15

---

Published in Transactions on Machine Learning Research (12/2022)
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proceedings of the 2018 International Conference on Learning Represenla- tions (ICLR), 2018.
Petar Velickovie, William Fodus, William L. Hamilton, Pictro Lió, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In Proceedings of the 2019 International Conference on Learning Representations (ICLR), 2019.
Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R. Benson, and Pan Li. Understanding non-linearily in graph neural networks from the bayesian- inference perspective. In Proceedings of the 2022 Annual Conference on Neural Information Processing Systems (NeurIPS), 2022.
Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. In Proceedings of the 2020 Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 20437-20444 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. comprehensive survey on graph neural networks. IEEE Transactions on Neurul Networks and Learning Systems, 32(1): 4 24, 2021.
Feng Xia, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, and Huan Liu. Graph learning: A survey. IEEE Transactions on Artificial Intelligncce (TAI), 2(2):109 127, 2021.
Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. Graph wavelet neural network. In Proceedings of the 2019 International Conference on Learning Represenlations (ICLR), 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the 2019 International Conference on Learning Representations (ICLR), 2019b.
Bo Yang, Xiao Fu, Nicholas D. Sidiropoulos, and Mingyi Hong. Towards k-means-friendly spaces: Simul- tancous deep learning and clustering. In Proceedings of the 2017 International Conference on Machine Learning (ICML), volume 70, pp. 3861 3870. PMLR, 2017.
Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jic Tang. Understanding negative sampling in graph representation learning. In Proceedings of the 2020 ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 1666 1676. ACM, 2020.
Jiaxuan You, Jonathan Michael Gomes Selman, Rex Ying, and Jure Leskovec. Tdentity-aware graph neural networks. In Proceedings of the 2021 AAAI Conference on Artificial Intelligence (AAAI), pp. 10737 10745, 2021.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Proceedings of the 2020 Annual Conference on Neural Information Pro- cessing Systems (NewrIPS), pp. 5812 5823, 2020.
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. In Proceedings of the 2021 International Conference on Machine Learning (ICML), volume 139, pp. 12310- 12320. PMLR, 2021.
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning graphs: A survey. IEFE Transactions Knowledge and Data Engineering (TKDE), 34(1):249 270, 2020.
Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Yu Philip Graph neural networks for graphs with heterophily: A survey. CoRR, abs/ /s02220.07788, 2022.
Zhiqiang Zhong, Sergei Ivanov, and Jun Pang. Simplifying node classification on heterophilous graphs with compatible label propagation. Transactions on Machine Learning Research, 2022a.
Zhiqiang Zhong, Cheng- Te Li, and Jun Pang. Hicrarchical messago-passing graph neural networks. Data Mining and Knowledge Discovery, pp. 1-28, 2022b.
16

---

Published in Transactions on Machine Learning Research (12/2022)
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Proceedings of the 2020 Annual Conference on Neural Information Processing Systems (NeurIPS), pp. 7793 7804, 2020.
Jiong Zhu, Ryan A. Rossi, Anup B. Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the 2021 AAAI Conference Artificial Intel- ligence (AAAT), pp. 11168 11176, 2021.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 2018 ACM Conference Knowledge Discovery and Dala Mining (KDD), pp. 2847-2856 2018.
17


Reviews:
[{"review_id": "vn5Jaooi8z", "reviewer": "Reviewer_5GF4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n--\n- The paper is well-written and easy to read, while it provides good background for the problem. The writing is very clear and pleasant to read. The authors also provide several examples that significantly contribute to the paper's clarity.\n\n- The proposed method achieves state-of-the-art performance in the node classification and link prediction tasks. It outperforms all baselines on all node classification datasets and on 3 out of 5 link prediction datasets. Thus, it seems to be a good addition to the set of unsupervised node embedding algorithms.\n\nWeaknesses\n--\n- While it is clear why methods that rely on the homophily assumption would fail in the heterophilous setting (because nodes in close proximity are mapped to similar vectors which is not necessarily the case in the heterophilous setting), it is not clearly explained in the paper why the proposed method can work well in such a setting. I suggest the authors go into more details such that the beneﬁts that the method brings are clear to the reader.\n\n- This point is related to the previous one. In my view, heterophily is not properly defined in the paper. There are two different definitions of homophily, but no definition of heterophily. Would the following definition make sense: $heterophily = 1 - h$. I suggest the authors provide such a definition such that it becomes clear what are the properties of networks the proposed method aims to capture.\n\n- Even though the paper focuses on the unsupervised heterophilous scenario, it is only evaluated in two downstream tasks, i.e., mainly in node classification and in link prediction. Since node classification is a supervised learning problem, and thus end-to-end models can be trained on the different datasets, I wonder whether the proposed method would be practically useful for such a task.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The main contribution of this paper is SELENE, an unsupervised algorithm that learns low-dimensional node representations which can capture homophily but also heterophily in networks. The proposed method discriminates nodes' ego networks using node attributes and structural information separately. SELENE is evaluated in the tasks of node classification and link predicition. In the first task, it outperforms all baselines on all datasets, while in the second task, it outperforms them on most datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Most requested changes are related to the weaknesses listed above.\n\n- As discussed above, there is a lack of clear intuition regarding the proposed method. In my opinion, more intuition on why the method is designed as it is and why it works in heterophilous settings is necessary. I strongly encourage the authors to provide more intuition. Furthermore, I would suggest the authors provide a formal definition of heterophily and potentially some measure of heterophily (similar to equation 1, but for heterophily). I think that this would significantly strengthen the paper.\n\n- The proposed method is mainly evaluated in the node classification task. I would expect methods that are evaluated in this task to belong to the family of supervised learning algorithms. I would thus suggest the authors whether experiment with a supervised variant of SELENE or evaluate the method in more downstream tasks. If no further downstream tasks exist, that would mean that unsupervised methods are not of any practical use.\n\n- The comparison against some baselines is not fair since not all baselines can handle node attributes. For instance, node2vec cannot handle such attributes. I suggest the authors make sure that the list of baselines consists of methods that take the same data as the proposed model as input.\n\n- It is well-known that $k$-means is sensitive to the initialization of the centroids. If I am not wrong, it is not reported in the paper how exactly the centroids were initialized. It is only mentioned that clustering was repeated 10 times. This is fairly important since different initialization schemes might lead to different results. Furthermore, it is mentioned in Appendix C that mean/std performance is reported, but I think only means are reported in the paper.\n\n- In Section 6.4, the authors report the performance of the different methods in the node classification task, but they provide no details about the employed classifier and its hyperparameters. No details are provided in the Appendix as well. I suggest the authors provide those details since they are very important for reproducing the reported results.\n\n- Typos:\npage 2: \"Out empirical study\" --> \"Our empirical study\"", "broader_impact_concerns": "There are no concerns on the ethical implications of the work that would require adding a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "boZmkaAAOb", "reviewer": "Reviewer_2EgB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. There are very few works considering the setting of unsupervised learning that can handle node classification tasks over heterophilic networks. This is a very challenging problem. Although this work over-claims that they are the first one to consider this (explained later), research effort on this problem deserves appreciation. \n\n2. The paper is generally written well. In particular, different parts of technical design get sufficiently motivated. In a high level, I think the way proposed to encode the network is intuitively good for node classification over heterophilic networks, while I think these are some technical issues which will be discussed later. \n\nWeaknesses: \n1. There are several points unclear to me. The paper says the experiments do not use any supervision signals in Appendix D. Then, my question is how the learned embeddings get mapped to node labels. Are there some pure unsupervised learning methods  adopted in the latent space such as k-means? If k-means-type of methods are used, have you tried different random seeds and how many time have you tried? We know that k-means is super sensitive to the initial seeds.  I believe this is super crucial to determine the performance of this method. \n\n2. I do not quite buy the reasons in this paper that argue against previous works who train a simple down-steaming classifier over the embedding vectors to predict a small amount of labels. This is a valid method to measure the embedding quality as long as the classifier is simple and the number of used labels is small. I believe the proposed method should follow this protocol to do further comparison. Otherwise, how the adopted method maps embeddings to labels is super crucial, which is unclear to me. As I mentioned, k-means types of methods could be very sensitive to their initial seeds. \n\n3. I do not quite believe the empirical results given that the authors claim that they are using purely unsupervised evaluation. The reason is that homophily and heterophily are two contradictory concepts. It is impossible that without any supervision, the learned embeddings are good for both simultaneously. Think about this. We have no knowledge about node labels and just compute network embedding. Also, we have no knowledge during the evaluation so we pick a kernel (entirely agnostic to node labels) to do final node clustering based on these embeddings. Okay, how can the proposed method simultaneously both cluster the nodes that are adjacent to each other in the network  (homophily) and also cluster the nodes that are not adjacent to each other in the network  (heterophily)? There must be a tradeoff.  Given this, I do not quite believe the current experiment results. Actually, a previous work [1], which also gets missed in the reference of this work, also considers unsupervised learning on heterophilic networks, where the results indeed show this tradeoff. I suggest the authors clarify the details of their experiments on how their tune hyper-parameters and how to select the final clustering steps. Also, I think experiments based on training a simple downsteaming classifier should be done to verify the embedding quality. \n\n4. This is not the first paper on unsupervised learning for attributed heterogeneous network embedding. Please check [1] and give sufficient discussion. \n\n5. The results on CSBM synthetic datasets also look weird because on these datasets heterophily is not an issue for GNNs, as one just needs to do substraction instead of addition when combining neighbor representations. Check arguments in empirical works [2][3] (consider using them as baselines also). Also, the theory in [4] on CSBM shows that GNN models with proper parameterization have no performance difference on homophilic and heterphilic CSBM. \n\n6. What are unsupervised variants of H2GCN and FAGCN? I think the unsupervised loss function used here is crucial to determine their performances. These are important details. \n\nOverall, I like the adopted technique and the paper writing. However, the experiments are unclear and contradictory. Also, there are a few overclaims and missing references. Once these weaknesses get addressed, I think this could be a good paper. \n\n[1] Graph Auto-Encoder via Neighborhood Wasserstein Reconstruction, Tang et al. ICLR 2022\n[2] Adaptive universal generalized pagerank graph neural network, Chien et al. ICLR 2021\n[3] Is homophily a necessity for graph neural networks? Ma et al., ICLR 2022\n[4] Understanding non-linearity in graph neural networks from the bayesian-inference perspective, Wei et al. NeurIPS 2022.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies unsupervised network embedding methods, where the embedding results can be used to identify node classes that could be either homophilic or heterophilic. The main idea is to not use the proximity-driven loss but to use self-supervised learning type of loss, Barlow-Twin loss on structural representations, and reconstruction loss on node features. Experiments show some superiority of the proposed method.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The authors should clarify the details of their experiments on how their tune hyper-parameters and how to select the final clustering steps to address the weakness 3. \n\n2. Experiments based on training a simple down-steam classifier should be done to verify the embedding quality to address the weakness 2.\n\n3.Discuss the reference [1] above. And tune down the overclaim. \n\n4. Check [2][3][4] above. And give proper explanation on the experiments over synthetic datasets. Compare with [2] and [3] in the experiments.  ", "broader_impact_concerns": "No concerns on this. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xa5x67hiU7", "reviewer": "Reviewer_b2WU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper studies an interesting problem that is largely unexplored before. \n\n2. The paper is clearly written and easy to follow with a clear logic.\n\n3. The proposed framework is mostly reasonable and valid. \n\n4. Extensive experiments on multiple datasets show significant performance improvements.\n\n\nWeaknesses:\n1. Although the paper studies a new setting (i.e., unsupervised network embedding with heterophily), the challenges of the problem are not clear. There is no detailed discussion about whether simple modification of existing approaches can not solve the problem. For instance, some simple combinations of GNN models with heterophily design trained by self-supervised learning loss as adopted in the paper.\n\n2. Overall, the novelty of the proposed approach is a bit limited. It is more like an incremental combination of existing techniques proposed in multiple papers. In fact, almost all of the techniques are proposed and adopted in existing works. Therefore, the contribution of this work seems a bit weak. \n\n3. Some claims in the paper might not be accurate. For instance, it is claimed that in the dual-channel feature embedding pipeline, node feature and network structure information are well utilized without interfering with each other. However, the node attributes are used as the input of the GNN model in the network structure encoder module. Therefore, at least the node attribute information will interfer the structure feature. \n\n4. It is unclear why the double-channel feature embedding approach can solve the heterophily problem since the GNN part still aggregates information following the homophily assumption. It is suggested to discuss and explain why the node attribute separation will be better than existing works where residual connections of features are commonly used such as APPNP, GCNII, H2GCN and etc.\n\n\nOther minor comments:\n1. In section 4, how are the (semi)-supervised baselines trained under the unsupervised setting?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies an interesting and timely problem, i.e., unsupervised network embedding on heterophilous graphs, while existing works mostly focus on either unsupervised network embedding with a homophily assumption or (semi)-supervised network embedding with heterophily. The proposed approach has multiple components, such as a dual-channel feature embedding pipeline, r-ego network feature extraction, and negative-sample free self-supervised learning objective. Extensive experiments demonstrate the performance improvements, and some ablation study is provided for further analysis. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It is better to have a detailed discussion of the challenges in the studied problem and why existing approaches (or combinations) can not solve the problem.\n\n2. It is suggested to thoroughly discuss the novelty, contributions, connections, and differences as compared with existing works.\n\n\n\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is well-written, with the ideas presented very clearly.  The proposed approach is simple and intuitive, and the results support that this approach works better than existing approaches.

On the other hand the novelty of the proposed approach is a bit limited, as it simply concatenates a node attribute embedding and a graph structural embedding, and uses distortions to encourage embeddings of the distorted versions to be similar rather than using proximity-based training objectives.  However, improvements in model performance do not always require significant novelty.  Simple ideas that really work could be even more useful.  So I don’t think this is necessarily a bad thing.

The paper still has some small issues, after the improvements the authors already made after feedback from the reviewers.  In particular:
1. Purely unsupervised clustering is fundamentally an ill-defined problem, without assumptions on the distribution of actual cluster labels nothing would work in the worst case.  The authors probably should make this point clear.  Even better, the paper could be revised to focus on this semi-supervised setting with a small amount of labels, which seems like a more natural setting for downstream tasks.
2. Related, reviewer 2EgB made a valid point that a purely unsupervised clustering method could not work simultaneously for graphs with homophilous and heterophilous labels, because they are fundamentally contradictory.  So it is worth discussing a bit further how to resolve this contradiction, probably (1) discuss the assumptions on the labeling distribution and (2) discuss that the proposed approach is not equally good for both homophilous and heterophilous graphs, it still works significantly better for homophilous graphs, but deteriorates more gracefully compared to prior works on heterophilous graphs.
Decision: Accept (poster)