IRWE: Inductive Random Walk for Joint Inference of Identity and Position Network Embedding
Authors: Meng QIN
Dit-Yan Yeung
Venue: Accepted by TMLR ()

Abstract: Network embedding, which maps graphs to distributed representations, is a unified framework for various graph inference tasks. According to the topology properties (e.g., structural roles and community memberships of nodes) to be preserved, it can be categorized into the identity and position embedding. However, existing methods can only capture one type of property. Some approaches can support the inductive inference that generalizes the embedding model to new nodes or graphs but relies on the availability of attributes. Due to the complicated correlations between topology and attributes, it is unclear for some inductive methods which type of property they can capture. In this study, we explore a unified framework for the joint inductive inference of identity and position embeddings without attributes. An inductive random walk embedding (IRWE) method is proposed, which combines multiple attention units to handle the random walk on graph topology and simultaneously derives identity and position embeddings that are jointly optimized. In particular, we demonstrate that some random walk statistics can be informative features to characterize node identities and positions while supporting the inductive embedding inference. Experiments validate the superior performance of IRWE beyond various baselines for the transductive and inductive inference of identity and position embeddings.

Published in Transactions on Machine Learning Research (10/2024)
IRWE: Inductive Random Walk for Joint Inference of Iden- tity and Position Network Embedding
Meng Qin
menggin menggin__antoonnn azSformail com
Deportment of Computer Science Engineering, Hong Kong University of Science & Technology
Dit-Yan Yeung
dgyeung
Department of Computer Science & Engineering, Hong Kong Universiby of Science & Technology
Reviewed on OpenReview: Atips: // openreview. net/ pormfo id= bDse8Zagff
Abstract
Network embedding, which maps graphs to distributed representations, is a unified frame- work for various graph inference tasks. According the topology properties (e-g. structural roles and community memberships of nodes) be preserved, can be categorized into the identity and position embedding. Most existing methods can only capture one type of prop- erty. Some approaches
support the inductive inference that generalizes the embedding model to new nodes or graphs but relies on the availability of attributes. Due to the compli- cated correlations between topology and attributes, it is unclear for some inductive methods which type of property they can capture. In this study, we explore a unified framework for the joint inductive inference identity and position embeddings without attributes. An inductive random walk embodding (IRWE) method is proposed, which combines multiple attention units handle the random walk (RW) on graph topology and simultaneously derives identity and position embeddings that are jointly optimized. We demonstrate that some RW statistics can characterize node identities and positions while supporting the in- ductive inference. Experiments validate the superior performance of IRWE over varions baselines for the transductive and inductive inference of identity and position embeddings.
1 Introduction
For various graph inference techniques, network embedding (a.k.a. graph representation lcarning) is a com- monly used framework. maps each node of a graph to a low-dinensional vector representation (a.k.a.
embedding) with some key properties preserved. The derived representations are used to support several
downstream inference tasks, e.g., node classification (Kipf Welling) 2017 Veličković et al. 2018). node
clustering (Ye et al. 2022 Qin et al. 2023a. Gao et al. 2023) and link prediction (Lei et al. Qin & Yeung
2018
2019:
Qin et al. 2023b
2023
According to the topology properties to be preserved, existing network embedding techniques can be catego- rized into the identity and position embedding (Zhu et al.) 2021)) The identity embedding (a.k.a. structural embedding) preserves the structural role of each node characterized by rooted subgraph, which also embedding) captures the link-
defined as node identity. The position embodding (a.k.a. age similarity between nodes in terms of the overlap of local neighbors (i.e., community structures (Newmanj 2006)), which is also defined node position proximity. In Fig, [ (a), each color denotes structural role. For instance, red and yellow may indicate the opinion leader and hole spanner in a social network (Yang) et al. 2015). ). Moreover, there are two communities denoted by the two dotted circles in Fig. [ where nodes in the same community have dense linkages and thus are more likely to have similar positions.
The identity and position embedding should respectively force nodes with similar identities (e-g., {2) 8g and positions (c.g., {U1, U2, u6}) have close embeddings. As demonstration, we applied struc2uee (Ribeiro et al. 2017) and node2vec (Grover & Leskovec 2016 (with embedding dimensionality d 2), which

---

Published in Transactions on Machine Learning Research (10/2024)
16
-0.5
V
Vio
Communterr
10
V/
V11
-15
Community22
VG Community #1
Vi2
Community #2
0.5
0.5
1.5
-25
0.5
Example graph topology
(b) Embeddings of (ru22ec((d22)
(c) Embeddings rodk (c=2)
Figure 1: An example of identity and position embedding in terms of (b) struc2vec and (c) nodeLvec, where cach color denotes unique identity while nodes in the same community have similar positions.
typical identity and position embedding methods, to the example in Fig. (a) and visualize the derived embeddings. Note that two nodes may have the same identity even though they are far away from each other. In contrast, nodes with similar positions must be close to each other with dense linkage and short distances. Due to the contradiction, it challenging to simullannously capture the two types of properties in common embedding space. For instance, U) and Ey with the same identity have close identity embeddings
in Fig, D (b). However, their position embeddings are far away from each other in Fig, I (c). Since the two types of embeddings may be appropriate for different downstream tasks (c.g., structural role classification and community detection), we expect a unified embedding model.
Most conventional embedding methods (Wu et al., 2020 Grover & Leskovee 2016 Ribeiro et al.) 2017 Donnat ct al., 2018) follow the embodding lookup scheme and can only support transductive embedding inference. In this scheme, node embeddings are model parameters optimized only for the currently observed graph topology. When applying the model to new unseen nodes or graphs, one needs to re-train the model from scratch. Compared with transductive methods, some state-of-the-art techniques (Hamilton et al., 2017 Velickovic et al.) 2019) can support the advanced inductive inference, which directly generalizes the embedding model trained on observed topology to new unseen nodes or graphs without re-training.
Most existing inductive approaches (e-g.; those based on graph neural networks (GNNs) (Wu et al. 2020 rely on the availability of node attributes and an attribute aggregation mechanism. However, prior studies QQnn et al., 2018 Li et al. 2019; Wang et al. 2020; Qin & Lei, 2021) have demonstrated some complicated correlations between graph topology and attributes. For instance, attributes may provide (i) complemen- tary characteristics orthogonal to topology for better quality of downstteam lasks or (ii) inconsistent noise causing unexpected quality degradation. It is unclear for most inductive methods that their performance improvement is brought about by the incorporation of attributes or better exploration of topology. When attributes are unavailable, most inductive approaches require additional procedures to extract auxiliary at- tribute inputs from topology (e.g., one-hot node degree encodings). Our experiments demonstrate that some inductive baselines with these naive attribute extraction strategies may even fail outperform conventional transductive methods the inference of identity and position embeddings. It is also hard to determine which type of properties (i.e., node identities positions) that some inductive approaches can capture.
In this study, we consider the unsupervised network embedding and explore a unified framework for the joint inductive inference of identity and position embeddings. To clearly distinguish between the two types of embeddings, we consider the case where topology is the only available information source. This eliminates the unclcar influence from graph attributes due to the complicated correlations between the two sources. Different. from most existing inductive approaches relying on the availability of node attributes, we propose inductive random walk embedding (IRWE) method. It combines multiple attention units with different choices of key, query, and value to handle the random walk (RW) and induced statistics on graph topology.
RW is an effective technique to explore topology properties for network embedding. However, most RW- based methods (Grover & Leskoved 2016 Ribeiro et al., 2017) follow the transductive embedding lookup scheme, failing to support the advanced inductive inference. We demonstrate that anonymous walk (AW) [Ivanov & Burnaev 2018), the anonymization of RW, and its induced statistics can be informative features shared by all possible nodes and graphs and thus have the potential to support inductive inference.
2

---

Published in Transactions on Machine Learning Research (10/2024)
Although the identity and position embedding encodes properties that may contradict with one another, there remains a relation that nodes with different identities should have different contribulions in forming the local community structures. For the example in Fig. [ and 02 may correspond to an opinion leader and ordinary audience of a social network, where 81 is expected to contribute more in forming community## than 1/2- By incorporating this relation, IRWE jointly derives and optimizes two sets of embeddings w.r.t. node identities and positions. In particular, we demonstrate that some AW statistics can characterize node identities to derive identity embeddings, which can be further used to generate position embeddings. It is also expected that the joint learning of the two sets of embeddings can improve the quality of one another.
Our major contributions are summarized as follows. (i) In contrast to most existing inductive embedding methods relying on the availability of node attributes, we propose an alternative IRWE approach, whose inductiveness is only supported by the RW on graph topology. (ii) To the best of our knowledge, we are the first to explore a unífied framework for the joint inductive inference of identity and position embeddings using RW, AW, and induced statistics. (iii) Experiments on public datasets validate the superiority of IRWE over various baselines for the transductive and inductive inference of identity and position embeddings.
2 Related Work
2.1 Identity & Position Embedding
In the past several years, a series of network embedding techniques have been proposed. Rossi et al. (2020) gave an overview of existing methods covering the identity and position embedding. Most existing embedding approaches can only capture one type of topology propertics (i.c., node identitics or positions).
Perozii al. (2014) proposed Deep Walk: that applies skip-gram to learn node embeddings from RWs
graph topology. The ability of Deep Walk to capture node positions is further validated in (Pei et al 2020:
Rossi et al. 2020). Grover & Leskovee (2016) modified the RW in Deep Walk to a biased form and introduced node2vec that can derive richer position embeddings by adjusting the trade-off bet breadth- and depth- first sampling. Cao et al. (2015) reformulated the RW in Deep Walk: to matrix factorization objectives. Wang et al. (2017), Ye et al. (2022), and Chen et al. (2023) introduced commmnity--peesrrvinn embedding methods based on nonnegative matrix factorization, hyperbolic embedding, and graph contrastive learning.
Ríbeiro et al. (0177) proposed struc2vec, an identity embedding method, by applying RW to multi-
layer graph constructed via hierarchical similarities w.r.t. node degrees. Donnat et al. (2018) used graph
wavelets to develop Graph Wave and proved its ability to capture node identities, Pei et al. (2020) introduced struc2gauss, which encodes node identities in a space formulated by Gaussian distributions, and analyzed the effectiveness of different energy functions and similarity measures. Guo et al. (2020) enhanced the ability of GNNs to preserve node identities by reconstructing several manually-designned stalistios. Chen et al. (2022) enabled the graph transformer to capture node identities by incorporating the rooted subgraph of each node,
Hoff 2207)) demonstrated that the latent class and distance models can respectively capture node positions and identities but real networks may exhibit combinations of both properties. An eigen-model was proposed, which can generalize either the latent class model or distance model. However, the proposed eigen-model is a conventional probabilistic model and cannot simultaneously capture both properties in a unified framework. Zhu et al. (2021) proposed a PhUSION framework with three steps and showed which components can be usod for the identity or position embedding. Although PhUSION reveals the similarity and difference between the two types of embeddings, it can only derive one type of embedding under each unique setting, Rossi et al. (020) validated that some techniques (e.g., RW and attribute aggregation) of existing methods can only derive either identity or position embeddings. Srinivasan & Ribeiro (2020) proved that the relation between identity and position embeddings can be analogous to that of a probability distribution and its samples. Similarly, PaCEr (Yan el al.) 2024) is a concurrent transductive method that considers the relation between the two types of embeddings based on RW with restart. Although these methods (Srinivasan & Ribciro 2020 Yan et al.] (2024) can derive both identity and position embeddings, they only involve the optimization of one type of embedding and a simple transform to another type. In contrast, we focus on the joint learning and inductive inference of the two types of embeddings.
3

---

Published in Transactions on Machine Learning Research (10/2024)
2.2 Inductive Network Embedding
Some recent studies explore the inductive inference that directly derives embeddings for new unseen nodes or graphs by generalizing the model parameters optimized on known topology. Hamilton et al. (017)) introduced GraphSAGE, an inductive GNN framework, including the neighbor sampling and feature aggregation with different choices of aggregation functions. GAT (Veličković et al.) 2018) leverages self-attention into the attribute aggregation of GNN, which automatically determines the aggregation weights for the neighbors of each node. Velickovic et al. 2019) proposed DGI that maximizes the mutual information between patch embeddings and high-level graph summaries. Without using the feature aggregation of GNN, Nguyen et al. (2021) developed SANNE that applies self-attention to handle RWs sampled from graph topology. However, the inductiveness of the these methods relies on the availability of node attributes.
Some recent research analyzed the ability of several new GNN structures to capture node identities positions in specific cases about node attributes (e.g.. all the nodes have the same scalar attribute input (Xul ct al. 2019 ). Wu et al. (2019) and You et al. (2021) proposed DEMO-Net and ID-GNN that can capture node identities using the degree-specific multi-task graph convolution and heterogemeous message passing on
the rooted subgraph of each node, respectively. Jin et al.] 2020)) leveraged AW statistics into the feature aggregation to enhance the ability of GNN to preserve node identities. P-GNN (You et al.) 2019) can derive position-aware embeddings based on a distance -istance-weighted aggregation scheme over the sets of sampled anchor nodes. However, these GNN structures can only capture either node identities positions.
In contrast to the aforementioned methods, we explore unifted induclive frumework for the joint inference of identity and position embeddings without relying on the availability and aggregation of attributes.
3 Problem Statements & Preliminaries
We consider the unsupervised network embedding on undirected unweighted graphs A graph can be repre- sented as 9 = EV, with V = {111 "2,...,,NN ur and È = {(e,, 11),,, by E V} as the sets of nodes and edges. We also assume that graph topology is the only available information source and attributes are unavailable.
Definition (Node Identity). Node identity describes the structural role that a node e plays in graph topology (e.g., opinion leader and hole spanner w.r.t. red and yellow nodes in Fig. [ (a)), which can be characterized by its I-hop rooted subgraph (s( Given pre-set nodes (v, u) with similar subgraphs (G,(v, G,,, I)) (c.g., mcasured by the WL graph isomorphism test) are expected to play similar structural roles and have similar identilies.
Definition 2 (Node Position). Positions of nodes in graph topology can be encoded by their relative distances and can be further characterized by the linkage similarity in terms of the overlap of l-hop neighbors (i.e., community structures). Nodes with a high overlap of (-hop neighbors are more likely to (i) have short distance, (ii) belong to the same community, and thus (iii) have similar positions.
Definition 3 (Network Embedding). Given graph G, we consider the network embedding (a.k.a. graph representation learning) f V + R2 that maps each node to vector f(v) (a.k.a. embedding), with either node identities or positions preserved. We define f(v) := +(v) (or f(v) : 7()) as the identity (or position) embedding if {v(v)} (or (π(+)}) preserve node identities (or positions). Namely, nodes (v, u) with similar identities (or positions) should have close representations (N(v), v())) (or (v(v), (())). The learned embeddings are adopted as the inputs of some downstream modules to support concrete inference tasks.
The embedding inference includes the transductive and inductive settings. A transductive method focuses the optimization of f on the currently observed topology g (V,E) and can only support inference tasks on V. In contrast, an inductive approach can directly generalize its model parameters, which are first optimized on (V,E), to new unseen nodes V' or even a new graph G" (V", E") and support tasks on V or y" (i.e,, the inductive inference for new nodes or across graphs). A transductive method cannot support the inductive inference but an inductive approach can tackle both settings.
We focus on the joint inductive inference of identity and position embeddings. A novel IRWE method is proposed which combines multiple attention units to handle RWs and induced AWs.
4

---

Published in Transactions on Machine Learning Research (10/2024)
Position emb b(V}
Identity emmb (v(s))
Global position encoding (x)())
Position Embedding Module
Map
Decoder
AW
amb
Key Map
Identity Emb Decnder
Identity emb {m(v)}
AW Encoder
Queeyy Map
RW stat (rtv)}
Recon
Identity Embedding AW emb (o(w)
AW escoding {olmi)
A RWs (w)
Module
AW (shv)
Hiihh-rder degree feat (divd)
AWS (w)
Reduction
stat High-order [s(v]}
(w)
degree feat (o(v))
AW Embedding
2) Identity Embedding Encoder
Identity Embedding
Aulo-Encoder
Decoder
(a) Overall architecture
(b) Identity embodding module
Local position encoding {s())
w.t sampled
fw)
RW stat (r(v)
Value
Transformer
Map
Encoder
Context
emb (?(v))
Rand Proj
Key
Value Map
Map
Map
Contrastive
Identity
Q Qerr Map
Globbal pos (nd(1)
emb (p(v)>>
Query Map
Position
Attentive Reweightnng
Attentive Readont
emb ((()
1) Input Fusion Unit
Position Einhedding
Position Embedding
Encoder
Decoder
(c) Position embedding module
Figure 2: Model architecture of IRWE including modules of (b) identity and (c) position embeddings.
Definition 4 (Random Walk & Anonymous Walk). An RW with length I is node sequence (w((), w(1), ...., (9)), where w(f) E V is the j-th node and (wl)), w(+1)) E E. Assume that the index j starts from 0. For an RW one can map it to an AW w = (ww(w )..., I...,,((((())) where (w maps u() to its first occurrence index in w.
In Fig. I (a), (wi, u4, vs U1, v6) a valid RW with (0, 1, 2,3) as AW. In particular, two RWs (e.g.. (v), U4, 05, U1) and (ug, V10, 8g, ug)) can be mapped to common AW (i.e., (0, 2, 0)). In Section 4 we further demonstrate that AW and its induced statistics can be features shared by all possible topology and thus can support the inductive embedding inference without attributes.
4 Methodology
In this section, we elaborate on the model architecture as well the optimization and inference of IRWE. Fig. 2 (a) gives an overview of the model archilecture, including two jointly optimized modules that derive identity embeddings {vb()) and position embeddings {r(e)).
4.1 Identity Embedding Module
Fig. 2 (b) highlights details of the identity embedding module. It derives identity embeddings (w(()) based on auxiliary AW embeddings (P(w)), AW statistics (s(u)), and high-order degree feat ures {ō(v)). Fig. 3 gives running examples about the extraction of {y((w)) {s(v)} and {8(x)} based on the local topology of node i Fig. [ where we set RW length / = 3 and the number of sampled RWs ng = as a demonstration. The optimization and inference of this module includes the (1) AW embedding auto-encoder, (2) identity embedding encoder, and (3) identily embedding decoder.
5

---

Published in Transactions on Machine Learning Research (10/2024)
[1]
Table [c=((c)]
AW Lookup
0,0,0,00 0)
[0000 0000 0000 0000]
Encedings (ole))
One-hot AW
Sampled RWs 3o
(Starting from vi)
Mapped AWs
AW stat
0 000000022000
[2]
(0. 0,
[0000 0100 0000 0000)
M2
[5] (0, 1, 2,
[3]
(0, 0, 1,
[0000 0000 0100 0000]
[4]
1,
[0000 0100 0100 0000]
[5] (0, 1, 2,
[6] 0. 1)
[5]
(0. 1.
[0000 0000 0000 0100]
[0000 0100 0010 0000]
M
%
V
[+11 (0, 1, 0,
[7] (0, 0,
[0000 0100 0000 0100]
[10] (0, 1,
[8] 0.
[0000 0000 01000 0100)
[9] (0, 1. 1.
[0000 0100 0100 0100]
Vn
[15] (0. 1,
[10]
(0, 2, 1)
[0000 0100 0010 0100]
0,
[0000 0100 0000 0010]
[12] (0, 0.
[0000 0000 0100 0010)
Node Degrees
High- der Degree Feat (e=5) [v,))(00005 05000 03002 03002)
[13]
(0,
1. 21
[0000 0100 0100 0010]
deg(v, Vu vs, M. V., V. Via Mu Maa
2, 2)
[0000 01000 0010 0010]
= [5. 2, 2, 2, 2, 2,
2,
5,
2.
2
2. 2, 5]
2 3
[15]
3)
[0000 0100 0010 0001]
pos
fodex
AWS
Figure 3: Running examples about the derivation one-hot AW encodings {p(W)), AW statistics (s(t)), and high-order degree features {8(w) based on the local topology of node un Fig.
4.1.1 AW Embedding
As discussed in Section 3 it is possible to map RWs with different sets of nodes to a common AW. For instance, (0, 2, 0) is the common AW of RWs (v1, U2 Ug 01) and (vi, U4 U5 01) in Fig. 3 Given a fixed length 1, RWs on all possible lopology structures can only be mapped to finite set of AWS Qt Namely, Ω and its induced statistics are shared by all possible nodes and grophs, thus having the potential to support the inductive embedding inference. Based on this intuition, IRWE maintains an AW embedding p(w) E R for each AW w E Qz In this setting, {p(w)} can be used as a special embedding lookup table for the derivation of inductive features regarding graph topology.
We also consider an additional constraint on {((()), where two AWs with more common elements corre- sponding positions should have closer representations. For instance, (0, 1.2) and (0. 0,,10 should be closer in the AW embedding space than (0, 1, and (0, 1,0, 3). To apply this constraint, transform each AW w with length to a one-hot. encoding p(w) E {0, ((41)² where p(w))):(++y (i.e., subsequence from the ji-th to the (j + 1)h-th positions) is the one-hot encoding of the j-th element in w. For instance, we have p(w) = [0000 0100 0010 0001] for = (0, 1, 2, in Fig. 3 An auto-encoder is then introduced to derive and regularize ((p(w), including an encoder and decoder. Given an AW w, the encoder Enc,()) and decoder (.) are defined as
(ww)= (w) = MLP(p(()), ((w) = (ec,(w) MLP((p(w)),
(1)
which are both lulti-layer perceptrons (MLPs). The encoder takes p(w) as input and derives AW embedding v(w)). The decoder reconstructs p(w) with vd()) as input. Since similar AWs have similar one-hot encodings, similar AWs can have close embeddings by minimizing the reconstruction error between {p(w)} and {}(W))
4.1.2 Identity Embedding Encoder
IRWE derives identity embeddings (v(()) via the combination of AW embeddings {((w)} inspired by the following Theorem 1 (Micali & Zhu 2016).
Theorem 1. Let Ga(u,r) be the rooted subgraph induced by nodes with distance less than r from v. Let L) be the distribution of AWs w.r.t. RWs starting from v with length l. One can reconstruct Gs(v,)) in time Onn?) with O(n²) access to [q(v, 1),,., ,q(u, where I = O(m); and m are the numbers of nodes and edges in (v.
For a given length 4, let n be the number of AWs. q(v, I) can be represented as an n--dimensional vector, with the j-th clement as the occurrence probability of the j-th AW. Since AWs with length include sequences of those with length less than (e.g., 10, 3) provides information about 2,),, one can derive q(o, k) (k: < based on ( Therefore, q(v, can be used to characterize (. according to Theorem 1.
6

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 1: Derivation of AW Statistics
Input: target node RW length 4; sampled RWs wit" AW lookup table Ql; number of AWs Output: AW statistic s(u) w.r.t,
a(u) [0,0, 0, ... ,0 //Initialize s(v)
for each Win) do
map RW w to its AW w get the index of AW in lookup table Q
s(v); + s(b), + 1 //Update s(v)
As defined in Section 3 nodes with similar rooted subgraphs are expected to play similar structural roles and thus have similar identities. For instance, in Fig. ! G. 1) and (v 1) have the same topology structure, which is consistent with the same identity they have. Hence, q(v, I) can characterize the identity of node v.
To estimate ((,,),; we extract AW statistic s(v) for each node v using Algorithm 1 We first sample RWs with length starting from v via the standard unbiased strategy (Perozzi et al. 2014 (see Algorithm $ in Appendix A) Let Wit) be the set of sampled RWs starting from v. Each RW w E W(() is then mapped to its AW. Let 24 be an AW lookup table including all the AWs with length 4, which is fixed and shared by all possible topology. We define the AW statistic as s(v) = [e(w1), ,((,, E ZT, where c(w;) is the frequency of the j-th AW in Q as illustrated Fig.
20
600
Nodes
Table 1: Variation of the Number of AWs and its
60
400
Reduced Value w.r.t. Length I on Brazil
4
5
6
7
100
200
71
203
877
4,140
21,147
115,975
120
11
52
195
610
1,540
3,173
0
10
20
30
40
50
AWs
Figure 4: Visualization of AW statistics {s(u)} on Brazil.
Although т grows exponentially with the increase of length I, {s(u)) are usually sparse. Fig, visualizes the example AW statistics {s(b)} derived from RWs on the Brazil dataset (sec Section for details) with = and [ = 1, 000. The i-th row in Fig, 4 is the AW statistic s(vy of node Us. Dark blue indicates that the corresponding element is O. There exist many AWs (wj) not observed during the RW sampling (i.c., Ve V s.t. (v)) = 0). We then remove terms w.r.t. these unobserved AWs in Ωn and {s(u)). Let Q4 $(v), and vi be the reduced Q4 s(V), and mn. Table I shows the variation of and it on Brazil as increases from 4 to 9, where Yi significantly reduced.
In addition to {5())}, one can also characterize node identities from the view of node degrees RRbeiro et al. 2017 Wu al., 2019 based on the following Hypothesis 1.
Hypothosis 1. Nodes with the same degree expected to play the same structural role. This concept be exlended to high neighbors of nodes. Namely, nodes expected to have similaar identilies if they have simälar node degree statistics (e.g., distribution over all degree values) w.r.t. their high-order neighbors.
Based on this motivation, we extract high-order degree feature 8(v) for each node v using Algo- rithm 2 Given a node u, one can construct a bucket one-hot encoding Pa(u) E [0, w.r.t. its de- gree deg(u), where only the j-th element pa(u), set to 1 with the remaining elements set and == L(de((u) - deggma)e/ (dee(de degmin]]; degmin and degmax. are the minimum and maximum degrees. Since high-order neighbors of a node v can be explored by RWs W(0 starting from v, we define 5(v) Z(++)e (I -jeedimensional vector, where the subsequence (())ee((+1)) is the sum of bucket one-hot degree encodings w.r.t. nodes occurred the i-th position of RWs in Wil), Fig. gives a running example derive 8(01) (with 5) for node en in Fig.

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 2: Derivation of Degree Features
Input: target node RW length I; one-hot degree encoding dimensionality e; sampled RWs W minimum degree degmin' maximum degree degmax
Output: high-order degree feature 8(v) w.r.t. v
6(v) < [0,0.... ..00....00000+1.. 00]++)> //Initialize degree feature б(v)
for each w E W/) do
for from 0 to do
+ w( //i-th node in current RW w
4
5
pa(u) t 10.... Of E //Initialize degree encoding pa(u)
j [(deg(u) Delesmme////e (deggxxxx degmin)
pa(u); + //pplaee pa(u)
(1+)) + d(t))e(()1)e- + pa(l)/ 6(v)
Following the aforementioned discussions regarding Theorem 1 and Hypothesis IRWE derives identity embeddings {v/(v)} via the adaptive combination of AW embeddings (F(w) w.r.t. AW statistics {š(u)} and degree features {ō(e)}. The multi-head attention is applied to automatically determine the contribution of each AW embedding so(w) in the combination, where we treat (s((w) the key and value; the concatenated feature [}())]]((v)] is used as the query. Before feeding [á(v)][0(v]] E g(*++ee) to the multi-head attention, we introduce a fcature reduction unit (.), an MLP, to reduce its dimensionality to
g(v) Red, (v) (T)
(2)
The multi-head attention that derives identity embeddings {v(v)} is defined as
Z Att( Q, K. V) = Att((o(u)), (v(w)), (p(())),
(3)
where Att(-..s)) is the standard multi-head attention unit (see Appendix D for details), with Q, K, and as inputs of query, key, and value.
(3) we have Q = g(v)), K,,- Vj: p(w,)) and Z = (v:).
4.1.3 Identity Embedding Decoder
An identity embedding decoder (+c is introduce regularize identity embeddings (vb(v) using statistics ((())) It takes the (b()) of node v input and reconstruct corresponding [(())]](v)] via
((v) = (v) = ML)()()))
(4)
where ((v) is the reconstructed statistic. It can force {d(()} to capture node identities hidden in {((()) by minimizing the reconstruction error between {ū(n)} and ([5(v)](((v))). Note that we only apply Decp to optimize {v{{ and do not need this unit in the inference phase.
4.2 Position Embedding Module
Fig. (c) gives an overview of the position embedding module. It derives position embeddings {r(w)} basod on (i) identity embeddings (v(+) given by the previous module and (ii) auxiliary position encodings (v), m(]) extracted from the sampled RWs (Wie)). Instead of using the attribute aggregation mechanism of GNNs, convert the graph topology into a set of RWs and use the transformer encoder (Vaswani et al, 2017), sophisticated structure that can process sequential data, to handle RWs. Besides the sequential input, transformer also requires a 'position' encoding to describe the position of cach element in the sequence. As highlighted in Definition 3, the physical meaning of node position in non-Euclidean graphs is different from that in Euclidean sequences (e.g., sentences and RWs). To describe the (i) Euclidean position in RWs graph, we introduce the local and global position encodings (denoted as x)() and
and (ii) node position Ny(v)) for a sequence position with index j and each node v. The optimization and inference of this module includes the (1) input fusion unit, (2) position embedding encoder, and (3) position embedding decoder.
8

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 3: Derivation of Global Position Encoding
Input: target node sampled RWs W node set V; random matrix θ E l Output: global position encoding (,) w.r.t, V r(v) < 0, ..... .0 //Initialize RW statistic r(v)
for each Wir) do
3
for each V/y E w do
L r(v) + r(), //Update r(v)
(V) + r()) / Derive (v)))
4.2.1 Input Fusion Unit
The inpul fusion wnit extracts (i) (v)} and derives inputs of the transformer encoder combined with {ab())} Since the RW length is usually not very large (e.g., S 10 in our experiments), we define the local position encoding mi(s) E {0, 1 as the standard one-hot encoding of index j. Inspired by previous studies (Perozzi et al. 2014 Grover & Leskovec 2016 Zhu et al.) 2021I that validated the potential of RW for exploring local community structures, we extract the global position encoding {mg(w)) for each node e w.r.t.
RW statistic r(v) using Algorithm 3
Given a node v, maintain r(u) ZM,, with the j-th element r(v); the frequency that node vy occurs in RWs Wie starting from For instance, we have r(w)) [8, 2, 2, 2, 1, 0, 0, for the running example in Fig. 3 with 13 nodes. Since nodes in a community are densely connected, nodes within the same community are more likely to be reached vía RWs. Therefore, nodes (v, u) with similar positions are expected to have similar statistics (r(v), r()). We then derive Ty(v) by mapping r(v) to d-dimensional vector via the following Gaussian random projection, an efficient dimension reduction technique that can preserve the relative distance between input features with a rigorous guarantee (Arriaga & Vempala 2006
Tg (v) = r(v) with e E RRVIxd Oi ~ 1/01
(5)
In this setting, the non- Non-Euclidean node positions in a graph topology are encoded in terms the relative distance between (x,(w)) Hence, (v) has the initial ability to encode the position of node v. IRWE integrates the relation between node identities and positions based on the following Hypothesis 2.
Hypothesis 2. In community (t.e., node cluster with dense linkages), nodes with different structural roles may have different contributions in forming the community structure.
For instance, in a social network, an opinion leader (e.g., and in Fig. is expected to have more contributions in forming the community it belongs to than an ordinary audience (e.g., V2 and og in Fig. 1
Based on this intuition, we use identity embeddings {v(()) to reweight global position encodings {m (+)), with the reweighting contributions determined by a modified attention operation. Concretely, we set identity
embeddings {v{+)} as the query and let global position encodings (T)) as the key and value (i.e., Q (1;) and K,: V1, Tg (v:)). The modified attention operation is defined as
z = ReAtt Q, K, V) = (MLP(() + MLP(K)) o V.
(6)
where : QN), QN))),, K == (N), and V == BN(V): BN(.) and @ are the batch normalization and element- wisc multiplication. In 6 we apply two MLPs to derive nonlincar mappings of the normalized {Q, K} and use their sum to support the element-wise reweighling of the normalized V. For convenience, we denote the reweighted vector w.r.t. node v, as (x(x)) = Z,.. Given an RW w (w](9) w(1), (9),, IRWE concatenates the reweighted vector H (w)(W) and local position encoding ()) for the j-th node and feeds its linear mapping to the transformer encoder:
(w = [
(7)
where W, E (dd+++1)xd is trainable parameter.
9

---

Published in Transactions on Machine Learning Research (10/2024)
4.2.2 Position Embedding Encoder
IRWE uses the transformer encoder TransEne(-) to handle an RW w = (w(1)) ,,,,, wwl"):
(f(w("))....)) ( ... ()).
(8)
Tt takes the corresponding sequence of vectors (M(z)()), ..... {(w())) as input and derives another sequence of vectors (f(w(")) ... ()) with the same dimensionality. TransEnc(-) follows a multi-layer structure, with each layer including the sell-attention, skip connections, layer normalization, and feedforward mapping. Due to space limit, we omit details of TransEnc(.) that can be found in (Vaswani et al. 2017).
For an RW starting from node v, the first output vector t(w(O)) f(t) can be representation of As sample multiple RWs W(+ starting from each node v, one can obtain multiple such representations based on W( However, we only need one unique positon embedding 7(v) for v. Let H(v) == (f(w(()) w E W. A naive strategy to derive (()) is to average representations in t("), Instead, we develop the following attentive readout function to compute the weighted mean of ((0), with the weights determined by attention:
z = ROOut(t (y())) = Att(TT(U), Fle) ((o)), r(v) == zW, + by: and 7(0) == zW; - bb.
(9)
In 9 :t: :) is the standard multi-head attention unit (see Appendix D for details), where we let the global position encoding (y(u) be the query (i.c., Q = (y(() E R lxdd and g() be the koy and value (i.c., Kj j:: Vj:: z(0)). 7(0) and (()) are the (i) position embedding and (ii) auxiliary context embedding of node
v, with {W,, 7, by, W., b as trainable parameters.
4.2.3 Position Embedding Decoder
The position embedding decoder is introduced to optimize position embeddings (+(v) together with auxiliary context embeddings (f(v)). Some of existing embedding methods (Perozzi et al.) 2014 Tang al.) 20015 Hamilton et al. 2017) are optimized via the following contrastive loss with negative sampling:
min Leur
E (D.W))D (OwD))D [Pis (n)(s))))))) (1;)/r) hn(-
(10)
where D denotes the training set including positive and negative samples in terms of node pairs {(vs, 05)}: Piy is defined as the statistic of positive node pair (v,, Uj) (e.g., the frequency that (v,, vj) occurs in the RW sampling); Q is the number of negative samples; ny is usually set to be the probability that (u),2)) is selected as negative sample; (-)) (-) is the sigmoid function; 7 is a temperature parameter to be specified. We follow prior work (Tang et al. 2015) to let Pij := Azj/ /dg(())) (i.e., the probability that there is an edge from v; to By with A E (0, 1IIIITI as the adjacency matrix) and ny x (Eitva,yy)e Poç)0.75, In the next section, we demonstrate that the contrastive loss 110 can be converted to a reconstruction loss such that the joint optimization of IRWE only includes several reconst objectives.
4.3 Model Optimization & Inference
Given an RW length I, let Ô be the reduced AW lookup table w.r.t. the reduced AW statistics (š(x)) in The optimization objective of identity embeddings [v)()) can be described as
2
min Cup := freg-u aLreg-o:
(11)
freg-p = = welh Im(w) p(w)
(12)
Creg-v Σ VEV (((0)16()))//16))}) -(0)))
(13)
where Creg-p regularizes auxiliary AW embeddings (w())) by reconstructing the one-hot AW encodings {p(w)) via the auto-cncoder defined in [[]; Lreg-u regularizes the derived identity emboddings (v((1) by
minimizing the error between (i) features {[š(z) [[(v)]} normalized by the number of sampled RWs [W(1) and (ii) reconstructed values (0(r) given by 4 is tunable parameter.
10

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 4: Model Optimization of IRWE
Input: topology (V, E); RW settings (.sss,,)); local position encodings (mi() optimization settings M,, Mey, (at,,n).
Output: sampled RWs (Wi()), wff"); reduced AW lookup table fu & induced statistics (3(e), 6(v), (v)}
optimized model parameters (0%, 07)
get AW lookup table Q4 w.r.t. length I
get min degree degmin & max degree degmax of (V,8)
get contrastive statistic C for each node E V do
sample ns RWs W(l staring from via Algorithm 6
get AW statistic s()) w.r.t. Wiy via Algorithm get degree feature 6(v) w.r.t. (MD(") dmiig dmax) via Algoritim get global position encoding my (v) w.r.t. 1pte) via Algorithm 3 randomly select RWs w/a from Wio
10 get reduced AW statistic {8(u)} by deleting unobserved AWs
11 get reduced AW lookup table Q w.r.t. {5(e)}
initial model parameters 0,
13 for iier_ iter_count from to m do for county from 1 to my do get (f(w), )())) w.r.t. {Ωr, 8(v), 8(0)} get training loss Ey via 11] optimize identity embeddings (b(v)) via Opt(A Cp)
15
16
17
18
for county from to my do get identity embeddings (v(v) w.r.t ((),
19
get position embeddings [v)) w.r.t. (b(o). mf). w/
20
21
gel training loss C, via 14)
22
optimize position embeddings (7(1)) via Opt(Ar, 0,),
23
save model parameters 0+}
As described in Section 4.2.3 one optimize position embeddings {n(v)) via contrastive loss (10p. It can be converted to another reconstruction loss based on the following Proposition 1. In this setting, the optimization of { and {x(w)} only includes three simple reconstruction losses.
Let E xl and I E Rlvixd the matria forms of {t(,))} and {π(x;) with the i-th rous denoting the corresponding embeddings of node U/- We introduce the auriliary contrastive statistics C C | in terms of sparse matrir where Ci -n In(Qn,) (v,, E and C,₁ = 0 otherwise.
Proposition 1.
The contrastive loss 10 is equivalent to the following reconstruction loss:
min C, = ||
(14)
The key idea to prove Proposition 1 is to let the partial derivative aCeur (Olr// w...t. each edge (1s, 1y)) to O. We leave the proof of Propasition in Appendix C
Algorithmp summarizes the joint optimization procedure of IRWE. Before formally optimizing the model, we sampled ng RWs Wy(e starting from each node u and derive statistics (š(v), (( (T(}}} induced by (W(")). In partieular, we randomly select n, RWs w( from W((e (nı < ns) for each node, which are handled by the transformer encoder in the position embedding module. Namely, we use ratio of the sampled RWs to derive {y(w)} due to the high complexity of transformer. We only sample RWs and derive induced statistics once, which are shared by the following optimization iterations.
To jointly optimize {b(e)} and {v(1)), one can combine [1] and 14 to derive a single hybrid optimization objective. Our pre-oxperiments show that better embedding quality can be achieved if we separately optimize the two types of embeddings. One possible reason that the two modules have unbalanced scales of parameters. Let Og and 0, be the sets of model parameters of the identity and position modules. The scale
11

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 5: Inductive Inference within Graph
Input:
optimized model parameters (02, (; new topology (VUV,,") E"); RW settings {1, ns, nr); local position
encodings {mi(i)): (Ωu, degmu: degmaxo ((v), (V)) derived in model optimization on old topology (V,E)
Output: inductive emnbeddnngs (b(e)} & [T(1)) w.r.t. for each node E V do
2 sample ns RWs Wo(") from w.r.t. E' via Algorithm 6
get AW statistic ('(v) w.r.t. (Wil1), 5t via Algorithm 8
get degree feature 8' (e( w.r.t. (Wi(e) dlmm; dmax) via Algorithm get global position encoding (v) w.r.t. (MV1)) V3 via Algorithm 10 randomly select ny RWs W/ from Win) add (1)),, (v))) & (v( to {š(v)}, {8(m)), & (Fo(l))
get {vb(w)} based on (f1,,()).,(v)) w.r.t. YUV
get {7(1) based on (,)()), m(), w/ w.r.t. V
of 8, is larger than fg due to the application of transformer. As described in lines 14-17 and lines 19-22, we respectively update {vb()) and {π(0)} my and my 2 times based on (11 and (14) in each iteration, where we can balance the optimization of [vb(1) and {v(0) by adjusting my and my..
Note that {vb(v)} are inputs of the position embedding modulc, providing node identity information for the inference of (T(r)}. The optimization of {)(r}} also includes the update of tep via gradient descent, which also affect the inference of {vb())}- Therefore, the two types of embeddings are jointly optimized although we adopt a seporate updating strategy. The Adam optimizer is used to update {0p, 0y}, with Xy and Xy as the learning rates for {v(v)} and {r(1)). Finally, we save model parameters after m iterations.
During the model optimization, we save the sampled RWs (W(v)) w(")), reduced AW lookup table Q and induced statistics (5(w), ((0),,,(v) (v)) (i.e., lines 4-11 in Algorithm 4 and use them as inputs of the bransduclive inference of {e)()) and {r(w)). Then, the transductive inference only includes one feedforward propagation
through the model. We summarize this simple inference procodure in Algorithm 7 (sec Appendix A).
To support the inductive inference for new nodes within a graph, we adopt an incremental strategy to get the inductive statistics (š(v),ō()) [v)} via modified versions of Algorithms I and 3 that utilize some intermediate results derived during the training on old topology (V,E). Algorithm 5 summarizes the inductive inference within graph. Let V and E' be the set of new nodes and edge set induced by V.V. We sample RWs W(() for each new node v E V" and get the AW statistic 8(v) w.r.t. AWs in the lookup table 94 reduced on old topology EV,E) rather than all AWs. 6(v) is derived based on the one-hot degree encoding truncated by the minimum and maximum degrees of (V,E). In the derivation of (y)),, we compute truncated RW statistic r(v) only w.r.t. previously observed nodes V. We detail procedures to derive inductive {š(e), 5(v), (y(()) in Algorithms 8 and 10 (sce Appendix Ap. Similar to the transductive inference, given the derived (3(u), 8(v), Te (U)), we obtain the inductive [ and {π(#)} via one feedforward propagation.
For the inductive inference across graphs, we sample RWs (Mp(e), w/(1) on each new graph (V"".") Since there are no shared nodes between the training and inference topology, we only incrementally compute the reduced//runcaate statistics (ε()), using the procedures of lines 3-4 in Algorithm 5 We derive global position encodings {πg(w}} from scratch via Algorithm|
3 We summarize this inductive inference procedure 11 (see Appendix A). We also leave detailed complexity analysis of IRWE in Appendix
in Amgorithm
B
5 Experiments
In this section, we elaborate on our experiments. Section 5.1 introduces experiment setups. Evaluation results for the transductive and inductive embodding inference are described and analyzed in Sections 5.2 and 5.3] Ablation study and parameter analysis are introduced in Sections 5.4 and 5.5 Due to space limit, we leave detailed experiment settings and further experiment results in Appendix and
12

---

Published in Transactions on Machine Learning Research (10/2024)
5.1 Experiment Setups
Table 3: Details of Methods to be Evaluated
Methods
Trans
Ind
Pos
Ide
node2vec GGrover & Leskoved
2016
GraRep Caao el
struc2vec Ribeire et at 2017
struc2gauss Pei el
Table 2: Statistics of Datasets
PaCE: Yan ct at. 2022
A
PhUSION (4iu ct al.] 20021
Datasets
N
E
K
GraphSAGE (Hami
PPI
3,890
38,739
50
DG1 (Velickoyic et Bl. 2011
Wiki
4,777
92.517
40
BlogCatalog
10,312
333,983
39
GraphinAA. [Toi wil
GraphMAE2 Hou
USA
1,190
13,599
Europe
399
5,993
4
P-GNN You of al.
CSGCL Chen
2011
2023
Brosil
131
1,003
GraLSP Jin el su
2020
PPIs
1,021-3,180
4,5541-6,6888
10
SPINE (Guo s1.
GAS (Guo of al. 220g
SANNE [Nguyen nt. a..
202
UGFormer (Nguyyn et
2022
IRWE (ours)
Datasets. We used seven datasots commonly used by related research to validate the effectiveness of IRWE, with statistics shown in Table 2 where N, E, and K are the numbers of nodes, edges, and classes.
PPI, Wiki, and Bloglog are the first type of datasets (rrover & Leskovec 2016 Zhu et al. 2021 providing the ground-trth of node positions for multi-label classification. USA, Europe, and Brazil are the second type of datasets (Ribeiro al. 2017 Zhu et al., 2021) with node identity ground- truth for multi-class classification. In summary, PPI, Wiki, and BlogColalog are widely used to evaluate the quality of position embedding while USA, Europe, and Brazil are well-known datasets for the evaluation of identity embedding.
PPIs is widely used dataset for the inductive inference across graphs (Hamilton et al. 2017 Veličković et al. 2018), which includes a set of protein-protein interaction graphs (in terms of connected components). In addition to graph topology, PPIs also provides node features and ground-truth for node classification. As stated in Section 3 we do not consider graph attributes due to the complicated correlations between topology and attributes. is also unclear whether the classification ground ttuut dominated by topology attributes. Therefore, we only used the graph topology of PPIs.
Downstream Tasks. We adopted multi-label and multi-class node classification for the evaluation of position and identity embeddings on the first and second types of datasets, respectively. In particular, each node may belong to multiple classes in multi-label classification while cach node only belongs to one class in multi-class classification. We used Micro F1-score as the quality metric for the two classification tasks. To avoid the exception that some labels are not presented all training examples, we removed classes with very few numbers of members (i.e., less than 8) when conducting node classification.
We also adopted unsupervised node clustering to evaluate the quality of identity and position embeddings. Inspired by spectral clustering (Von Luxburg (007) and Hypothesis 1, we constructed an auxiliary (top-10) similarity graph Gp based on the high-order degree features (5'(c) E [R+)] derived via a procedure similar to Algorithm? 2 The only difference between (d)( (used for evaluation) and {f(u)} (used in IRWE) is that 8'(u) derived from the rooted subgraph (v I') but not the sampled RWs W((), To obtain (8(()), we set 1= (i.c., the order of neighbors) and e 500 (i.c., the dimensionality of the hot degree encoding) for the first type of dalasets while we let l and e 200 for PPIs. Namely, we applied a clustering algorithm to embeddings learned on the original graph & but evaluated the clustering result GD. We define this task as the node identity clustering and expect that it can measure the quality of identity embeddings becuase high-order degree features (v)) can capture node identities.
In addition, we treated the node clustering evaluated on the original graph & as community detection NNew man 2006), task commonly used for the evaluation of position emboddings. Normalized cut (NCut) (Von Luxburg. 2007) w.r.t. GD and modularity (Newman 2006) w.r.t. g were used as quality metries for mode identity clustering and community detection. We leave details of NCut and modularity in Appendix D
13

---

Published in Transactions on Machine Learning Research (10/2024)
Logistic regression and KMeans were used as downstream algorithms for node classification and clustering. Larger F1-score and modularity as well as smaller NCut implies better performance of downstream tasks, thus indicating better embedding quality.
In summary, we adopted (i) node identity clustering and (ii) multi-label node classification to respectively evaluate identity and position embeddings on the first type of datasets. For the second type of datasets, (i) malti-label node classifieation and (ii) community detection were used to evaluate identity and position embeddings. We only applied the unsupervised (i) node identity clustering and (ti) community detection to evaluate the two types of embeddings for PPIs, since we did not consider its ground-truth.
Baselines, We compared IRWE with 17 unsupervised baselines, covering identity and position embedding as well as transductive and inductive approaches. Table 3 summarizes all the methods to be evaluated, where '_' denotes that it is unclear for a baseline which type of property it can capture. PhUSION has multiple variants using different proximitics for different types of emboddings. We used variants with (i) positive point-wise mutual information and (ii) heat kernel, which are recommended proximities for position and identity embedding, as two baselines denoted as PhN-PPMI and PhN-HK. Each variant of PhUSION can only derive one type of embedding. Although PaCEr also considers the correlation between identity and position embeddings (denoted as PaCEr(I) and PaCEr(P)) and derives both types of embeddings, it only optimizes PaCEr(P) based on the observed graph topology and simply transform PaCEr(P) to PaCEr(I)-
For each transductive baseline, we can distinguish that it captures node identities or positions. For inductive basclines, GraLSP, SPINE, and GAS are claimed to be identity embedding methods while P-GNN and CSGCL can preserve node positions. Similar to our method, GraL.PP and SPINE use RWs and induced statistics to enhance the embodding quality. SANNE applics the transformer encoder to handle RWs. All the inductive baselines rely on the availability of node attribules. We used the bucket one-hot encodings of node degrees as their attribute inputs, widely-used strategy for inductive methods when attributes are unavailable. All the transductive methods learn their embeddings only based on graph topology. To validate the challenge of capturing node identities and positions in one embedding space, we introduced an additional baseline [n2v||s<2 by concatenating node2vec and struc2vec.
Most of the bascline can only generate one set of embeddings. We have to use this unique set of embeddings to support two different tasks on each dataset. Our IRWE method can support the inductive inference of identity and position embeddings, simultaneously generating two sets of embeddings. For convenience, we denote the derived identity and position embeddings as IRWE(s)) and IRWE(?).
As stated in Section we consider the unsuperoised network embedding. There exist supervised inductive methods (e.g., GAT Veličković et al. 2018), GIN (Xu et al. 2019), ID-GNN (You et al. 2021), DE-GNN (Li et al. 2020 , DEMO-Net (Wu et al. 2019). and SAT (Chen et al. 2022)) that do not provide unsupervised training objectives in their original designs. To ensure the fairness of comparison, these supervised baselines are not included in our experiments. Due to space limit, leave details of layer configuratioss, parameter settings, and experiment environment in Appendix D
5.2 Evaluation of Transductive Embedding Inference
We first evaluated the transductive embedding inference of all the methods on the first and second types of datasets. For the two classification tasks, we randomly sampled T E (20%, 40%, 60%, 80%} and 10% of the nodes to form the training and validation sets with the remaining nodes as the test set on each dataset. Similar to 10-fold cross-validation we repcated the data splitting 10 times, where we split the node set into 10 subsets with each one as the validation set in a round and used the average quality w.r.t. the validation set to tune parameters of all the methods. Evaluation results of the transductive embedding inference are shown in Tables 4 and 5 where metrics are in bold or underlined if they perform the best or within top-3.
For transductive baselines, identity embedding approaches (i.e., struc2vec, struc2gauss, and PhN-HK) and position embedding methods (i.e., node2vec, GraRep, PhN-PPMI) are in groups with top clustering perfor- mance (in terms of NCut and modularity) on the first and second types of datasets, respectively. Since prior studies have demonstrated the ability of these transductive baselines to capture node identities or positions, the evaluation results validate our motivation of using node identily clustering and commanily delection to
14

---

Published in Transactions on Machine Learning Research (10/2024)
Table 4: Transductive Embedding Inference w.r.t, Node Position Classification and Node Identity Clustering
PPI
Willi
BlogCabalog
F1-score"
(%)
Neut
F1-scoref (%)
Neut.
F
F1-scoret (%)
Neut|
20%
40%
60%
80%
20%
40%
60%
80%
20%
40%
60%
80%
node2vec
17.79
19.15
20.16
21.58
18.18
17.43
51.00
52.25
53.87
38.55 89
37.20
39.45
10.45
11.58
36.82
Graßtep
17.94
20.54
22.00
23. 49
39.92
49.87
53.33
54.18
55.09
37. 37.12
30.83
33.58
34.71
35.68
34.32
PaCEr(P)
15.94
17.30
19.70
45.42
43.80
46.32
47.76
36.93
06.06
37.98
38.89
39.76
34.10
PhN-PPMT
20.17
22.34
23.64
24.84
45.31
46.11
49.04
50.35
51.22
38.88
38.86
40.97
41.69
42.71
36.21
struc2vee
7.70
7.99
8.04
8.47
30.51
40.70
41.14
41.17
41.34
30.96
14.07
15.09
15.28
14.79
30.47
struc3gause
10.59
11.10
11.91
12.59
38.01
11.06
10.86
11.13
27 27.66
17.16
17.21
17.28
16.95
31.41
PaCEr(l)
9.93
10.38
10.70
10.86
40.40
41.70
41.70
41.22
42.06
24.93
16.26
16.44
16.55
16.36
32.89
PKN
9.60
9.57
9.44
9.95
31.52
41.54
41.58
41.35
41.77
29.47
17.28
17.33
17.32
17.04
34.45
B2v [
14.29
14.67
66
14.38
31.99
38.95
39. 75
41.85
44.37
32. 322.92
26.94
28.75
31.34
33.75
31.14
GraSAGE
6.59
6.29
7.12
6.58
36.00
41.14
4.1.0G
40.35 S2
40.89
30.71
16.79
16.77
16.70
16. 56
3-1.88
DGT
10.98
12.37
13.36
14.24
45.35
42.63
43.44
43.91
44.33
36.85
19.24
20.81
21.92
22.22
33.35
GraMAE
11.58
12.76
13.76
14.00
37.72
42.01
42.52
42.87
43.32
25. 14
19.29
20.38
20.57
21.02
28.35
GraMAE2
9.63
10.40
11.26
11.52
43.26
41.85
01
11.73
42.3-1
38 26
17.76
18.14
18.23
18. 29
35.56
P-GNN
11.70
12.71
13.71
13.75
39.74
43.16
44.38
44.92
45,88
37 .31
19.29
20.64
21.39
21.43
34.75
CSGCL
14.93
16.14
17.13
17.81
41.66
42.77
43.39
43.47
44.06
25.
18.91
19.25
19.30
19.42
30.58
GraLSP
9.08
9.35
9.37
9.95
29.76
41.05
41.00
40.62
41.40
11.00
16.65
17.50
17.44
17.58
23.46
SPINE
8.36
9.07
9.97
10.41
14.49
40.92
10.87
10.59
10.50
38
16.25
16.51
16,50
16.
37.17
GAS
9.25
9.88
10.59
11.15
39.47
41.29
41.40
41.44
42.24
34.50
18.07
18.47
18.76
18.94
34.11
SANNE
7.77
8.18
8.05
9.57
46.87
41,07
11.08
41.01
41.56
38.35
16.56
16.77
16.70
16.72
37.10
UGFormer
6.57
6.04
6.31
6.31
32.30
41.15
41.07
40.81
40.88
21.16
16.73
16.84
16.76
16.53
28.01
IRWE(S)
11.45
13.52
14.48
15.60
28.92
45.18
49.49
46.99
47.46
9.85
17.84
18.
19:05
19.20
24.58
IRWE (()
19.63
22.75
24.20
25.88
42.78
52.02
54.29
54.94
56.20
19.31
38.99
41.42
41.86
42.76
36.07
Table 5: Transductive Embedding Inference w.r.t. Node Identity Classification and Community Detection
USA
Europe
Bruzil
Fl-scoret
(%)
Mod
Fi-scoret (%)
Mod
F F1-scoret
(%)
Mod?
20%
40%
60%
80%
(%)
20%
40%
60%
80%
(%)
20%
40%
60%
80%
(%)
node2vec
47.02
50.42
53.16
53.36
25.88
36.15 19
39.65
41.98
41.46
7.43
32.50
32.12
39.75
37.
11.76
GraRop
52.52
57.80
61.93
62.01
27.54
80.18
44.32
48.09
44.87
11.48
34.89
40.45
43.50
42.14
19.76
PaCEr(P)
47.44
19.36
51.46
53.95
22.12
42.56
15.27
48.76
50.00
1.13
37.83
39.09
45.50
50.71
2.35
PhN-PPMT
50.28
54.31
37.45
57.05
25.03
36.58
40.54
44.21
43.17
7.26
32.60
36.51
39.00
40.00
9.12
Struc2vec
56.85
58.97
59.91
0.38
51.85
53.93
37.27
57.31
-5.61
65.43
71.66
75.25
74.29
-1.43
struc2ganss
60.88
61.80
62.32
64.36
3.27
49.50
53.38
55.53
56.34
-6.49
68.69
72.72
75.50
73.57
-3.31
(T)
59.80
60:47
60.42
01.40
-0.19
50.61
54.84
56.12
59.90
-3.60
63.91
67.86
68.18
73.75
-2.74
PGN-HK
58.64
60.97
62. 43
63.19
13.14
32
52.
5-1.79
56 09
-6.01
61.88 84
68. 78
74.75
69 29
-5.19
n2v [62]]
64.02
56.69
38.79 79
57.05
2.91
48.2 48.25
62, 23
34.79
52.43
-6.22
59.78
65.76
64.75
60.71
2.28
GraSAGE
15.49
50.06
3-1.70
55.37
1.55
31.22
16.31
45.70
16.35
-0.71
35.86 86
39.05 09.09
541.00
67.85
2.93
DGI
54.62
57.
38.85
59.49
3.45
44.23
48.05
52.39
49.02
-4.78
36.19
41.36
48.25
47.85
9.18
GraMAE
58.86
62.33
64.62
64.11
5.86
45. 19
49.
52.72
49.26
1.70
44.56
55.00
63.00
66.42
3.18
GraMAR2
55.91
56.90
57.67
59.07
18.73
35.97
40.09
43.96
42.92
7.03
36.63
38.93
39.00
37.85
5.95
P-GNN
58.55
61. 29
62.54
G1.34
21.48
33
47.06
51. 65
50.00
0.29
46. 16.08
50.15
49.75
52.85
1.78
CSGCL
59.49
59.41
61.79
21.14
46.87
56.36
52.68
-8.61
38
41.39
48.50
13.01
GraLSP
57.89
58.87
60.58
61.84
2.72
42.59
47.66
45.70
51.70
0.65
43.15
52.12
61.25
64.28
0.32
SPINE
35.07
37.12
40.64
10.25
2.16
25. 12
25.82
23.71
30.00
-0.08
23.36
21.51
19.25
23.37
0.05
GAS
60.46
62.97
64.48
64.45
22.45
51.56
52.18
55,12
58.04
5.20
67.06
69.09
72.75
74.28
1.51
SANNE
54.95
56.86
58.15
61.01
14.59
44.63
50.25
54.46
49.51
6.21
40.43
45.61
51.25
51.43
5.90
UCFormer
51.61
53.85
53.95
55.88
0.78
36.
43.83
45.79
48.29
1.35
35.22
39.70
47.00
46.42
2.65
IRW I)WE(() E(P)
58.02
63.58
66.
65.48
1.78
52.06
54.88
58.10
60.24
-0.52
70.22
74.09
72.25
75.00
1.17
IRWE())
55.25
58.60
60.64
61.68
31.24
43.67
47.41
50.25
49.27
17.74
36.85
40.15
44.25
41.43
21.26
evaluate the qualily of identäly and position embeeddings. Our node identity clustering results also validate Hypothesis 1 that the high-order degree features {Ō(v)} can encode node identity information.
On each dataset, most baselines can only achieve relatively high performance for one task w.r.t. identity or position embedding. It indicates that most existing embedding methods can only caplure either node identities or positions. In most cascs, [n2v|[s2v] outperforms neither (i) node2vee for tasks w.r.t. node positions nor (ii) struc2vec for those w.r.t. node identities. It implies that the simple integration of the two types of embeddings may even damage the quality of capturing node identities positions. Therefore, it is challenging to preserve both properties in a common embedding space.
For lasks w.r.t. each type of embedding, conventional transductive baselines can achieve much better per- formance than most of the advanced inductive baselines. One possible reason is that existing inductive embedding approaches rely on the availability of node attributes. However, there are complicated correla- tions between graph topology and attributes as discussed in Section I Our results imply that the embedding quality of some inductive baselines is largely affected by their altribute inpuls. Some slandard settings for the
15

---

Published in Transactions on Machine Learning Research (10/2024)
Table 6: Inductive Inference for New Nodes within a Graph and across Graphs
PPI
Wiki
BloyCalaloy
Europe
Bruzil
PPLs
FI1
Neut
FIt
Neut.
F11
Neut,
F11
Mod
FI1
Mod?
FI1
Mod"
Mod? Neut
(%)
(%)
(%)
(%)
(%)
(%)
[56]
(%)
(%)
(%)
GraSAGE
T.35
36.13
40.71
28 86
16.30
26.50
57.81
0.88
52.68
0.02
71.42
2.18
3.90
6.69
DGI
14.64
45.18
24.16
36,
22 76
33.71
65.54
3.90
52.19
0.69
58.57
3.65
3.52
8.31
GraMAE
38.58
20.94
27.78
1.62
64.29
3.42
2.82
GraMAF2
11.81
28.28
41.27
37.88
19.05
35.94
59.83
9.56
46.34
4.46
42.86
5.34
3.68
8.14
PGNN
14.29
42.91
43.74
37.57
22.00 06
35.33
59.49
16.15
51.70
1.36
61.42
3.93
7.83
7.95
CSGCL
16.13
41.46
43.96
25.54
19.30
31.14
63.36
18.17
56.59
-7.81
61.43
5,81
-0.26
5.88
GraLSP
6.39
47.24
40.62
31.78
16.51
37.39
25.21
-0.34
44.39
0.12
38.57
-0.80
0.88
8.48
SPINE
9.12
17.21
16.87
37.
0.76
37.14
0.38
8.
GAS
11.50
39.33
41.84
34.44
18.94
33.89
64.87
23.05
56.59
3.51
68.57
4.27
-2.10
7.15
SANNE
5.19
45.58
16.39
34.11
0.01
-0.01
25.13
-0.01
1.43
UGFormer
5.59
34.70
40.71
21.39
16.23
27.84
59.83
2.03
45.85
0.73
62.86
1,95
-0.83
5.43
IRWE(
10.53
32.95
11.05
15.93
16. 10
26.58
68.40
10.07
60.00
-1.12
72.80
-5.28
0.16
4.62
IR
18.29
45.54
47.32
25.54
11.41
case without. available altributes (e.g., using one-hot degree encodings as attribute inpuls) canmot help derive informative identity or position embeddiiggs.
Our IRWE method achieves the best quality for both identity and position embedding in most cases. It indicates that. IRWE can jointly derive informative identity and position embeddings in unified framework:
5.3 Evaluation of Inductive Embedding Inference
We further consider the inductive inference (i) for new unseen nodes within a graph and (ii) across graphs, which were evaluated on the (i) first two lypes of datasels (i.e., PPI, Wiki, BloyCatalog, USA, Europe, and Brazil) and (ii) PPIs, respectively. We could only evaluate the quality of inductive methods because transductive baselines cannot support the inductive inference.
For the inductive inference within graph, we randomly selected 80%, 10,, and 10% of nodes each single graph to form the training, validation, and test sets (denoted as Vern, Veat, and Vest), where Veat and Vest represent sets of new nodes not observed in Vern- The embedding model of each inductive method was optimized only on the topology induced by Vern- When validating and testing a method using the node classification task, embeddings w.r.t. Virn and Vern U Veat were used to train the downstream logistic regression. We repeated the data splitting 10 times following a strategy similar 10-fold cross validation and used the average quality w.r.l. the validation set to lune parameters of all the methods.
For the inductive inference across graphs, sampled 3 graphs from PPIs denoted as Girns Goet, and Gist. which were used for training, validation, and testing. We first optimized the embodding model on Ge To validate or test the model, we derived inductive embeddings w.r.l. Gval or Gest and obtained clustering results for evaluation by applying MMeans. This procedure was repeated 5 times, where 15 graphs were sampled. Finally, the average quality over the data splits was reportod.
Evaluation results of the inductive embedding inference depieted in Table G where metrics are in bold underlined if they perform the best or within top-3. IRWE achieves the best quality in most cases. In particular, the quality metrics of IRWE are significantly better than other inductive baselines, whose inductiveness relies on the availability of node attributes. Our results further demonstrate that IRWE can support the inductive inference of identäty and position embeddings, simulataneouslyy generating two sets of informative embeddings, without velying on the availability and aggregation of any graph attributes.
5.4 Ablation Study
In ablation study, we respectively removed some components from the IRWE model to explore their effec- tiveness for ensuring the high embedding quality of our method. For the identity embedding module, we considered the (i) AW embodding regularization loss Lreg-p 12), (ii) AW statistic inputs (š(v)), (ii) high- order degree feature inputs (ō(v)), and (iv) identity embedding regularization loss freg- In cases (i)
and (iv); identity embeddings were only optimized via loss (i.e., freg-v Lrog-p)-
16

---

Published in Transactions on Machine Learning Research (10/2024)
Table 7: Ablation Study wr... Node Position Classification and Node Identity Clustering on PPI as well
Node Identity Classification and Community Detection USA.
PPT
USA
FI1 (%)
Neut,
FIf (%6
Mod (%)
IRWE
25.88
28.94
67.31
31.24
(1) w/o loss Lreg-
26.43
30.14
66.55
30.82
(2) w/o imput {
21.76
29.68
65.21
29.31
(3) w/o input (6(m)
25.14
30.61
67.07
(4) w/o loss Lreg-ui
25.65
36.02
45.79
30.11
(5) w/o imput (+(())
24.95
29.28
65.79
30.44
(6) w/o input (t((1))
25.08
29.62
65.79
29.45
(7) w/o ROut(.)
13.39
29.39
66.47
-0.76
(8) w/o Ey
22.43
(9) base stat (5(e)
46.05
56.63
10) base stat [6(1)]
34.06
63.94
base [ (t)
17.52
21.85
12) based stat C (SVD)
22.60
12.15
0.15-
(a) PPI, F'l-score,
(b) PPI, Fl-scoref,
(c) PPL, Fl-scoref;
33
NC31
NO04
23
(d) PPI, NCut4,
(c) PPI, NCut,,
(f) PPI, NCut,, T
Figure 5: Parameter analysis w.r.t. 1, a, and on PPT in terms of F1-scoret (node position classification)
and NCut4 (node identity clustering).
For the position embedding module, we checked the effectiveness of the (v) identity embedding inputs {v(()), (vi) global position encoding inputs {u)), (vii) (viii) reconstruction loss Cy (14.. In case (v), the two modules of IRWE were independently optimized. For case (vii), we simply averaged the representations Z(e) to replace ROut(.). For case (viii,, we replaced the contrastive statistics C in [14] with adjacency matrix A.
attentive readout function ROut(-) described in (9). and
We also used some induced statistics baselines.
Concretely, evaluated the quality of (ix) AW statistics (ā(1)} and (x) degree features (ō(v) to capture node identities. In contrast, we checked the quality of (xi) global position encodings (v) and (xii) contrastive statistics C for node positions. In case (xii), we derived representations with the same dimensionality as other embedding methods by applying SVD to C.
As a demonstration, we report results of transductive embedding inference on PPI and USA (with 80% of nodes sampled as the training sot for classification) in Table 7 According to our results, freg-v is essential for idenlily embedding learning, since there significant. quality declines for node identity clustering and classification in case (iv). ROut(-) and C. are key components to capture node positions due to the significant quality declines for node position classification and community detection in cases (vii) and (viii). All the remaining components can further enhance the ability to capture node identities and positions. The joint optimization of identity and position embeddings can also improve the quality of one another.
5.5 Paramete Analysis
We lested the effects of (i) RW length 1, (ii) a in loss 11 and (iii) temperature parameter 7 in loss [4 Concretely, we set E (.... 9}, a E {0.1, 1,5, 10, 50, 100), and т E {1, 10, 50, 100, 500, 1000 Example parameter analysis results of the transductive embedding inference on PPT and USA (with 80% of nodes sampled as the training set for classification) are illustrated in Fig. 5 and 6 The quality of both types of embeddings is not sensitive to the settings of 1. Compared with position embeddings, the quality
17

---

Published in Transactions on Machine Learning Research (10/2024)
0.60
0/6
0.65
0.66
(a) USA, Fi-scoref,
(b) USA, P1-scoref,
(c) USA, Fl-scoref,
10.50
0.35
9.32
0:1
03-
0.06
0.28
0.4
(d) USA, modularityt, L
(e) USA, modularity a
(f) USA, modularity T
Figure 6: Parameter analysis w.r.t. 1, a, and on USA in terms of F1-scoref (node identity classification) and modularityt (community detection).
of identity embeddingg is more sensitive to a (e.g., in terms of Fl-score of node classification on USA and NCut of node identity clustering on PPT). The scttings of T would significantly affect the quality of the two types of embeddings. The recommended parameter settings of IRWE are given the Appendix D
6 Conclusion
In this paper, we considered unsupervised network embedding and explored a unified framework for the joint optimization and inductive inference of identity and position embeddings without relying on the availability and aggregation of graph attributes. An IRWE method was proposed, which combines multiple attention units with different designs to handle RWs graph topology. We demonstrrted that AW derived from RW and induced statistics can (i) be features shared by all possible nodes and graphs to support inductive inference and (ii) characterize node identities to derive identity embeddings. We also showed the intrinsic relation between the two types of embeddings. Based on this relation, the derived identity embeddings can be used for the inductive inference of position embeddings. Experiments on public datasets validated that IRWE can achieve superior quality compared with various baselines for the transductive and inductive inference of identity and position embeddings. We leave discussions of future directions in Appendix D
Acknowledgments
This research has been made possible by funding support provided Dit- Man Yeung by the Research Grants Council of Hong Kong under the Research Impact Fund project R6003-21.
References
Rosa I Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts and random projection. Machine learning, 63:161-182 2006.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM International on Conference on Information & Knowledge Management, pp. 891-900, 2015.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In Proceedings of the 2022 International Conference on Machine Learning, pp. 3469 3489, 2022.
Han Chen, Ziwen Zhao, Yuhua Li, Yixiong Zou, Ruixuan Li, and Rui Zhang. Cagel: Community-strength enhanced graph contrastive learning. In Proceedings of the 32nd International Joint Conference on Arti- ficial Intelligence, pp. 2059 2067, 2023.
Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node emboddings via diffusion wavelets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. -320-1329, 2018
18

---

Published in Transactions on Machine Learning Research (10/2024)
Yu Gao, Meng Qin, Yibin Ding, Li Zeng, Chaorui Zhang, Weixi Zhang, Wei Han, Rongqian Zhao, and Bo Bai. Raftgp: Random fast graph partitioning. In 2023 IEEE High Performance Extreme Compuling Conference, pp. 1 7, 2023.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 855 864, 2016.
Junliang Guo, Linli Xu, and Jingchang Liu. Spine: Structural identity preserved inductive network embed- ding. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pp. 2399-2405, 2019.
Xuan Guo, Wang Zhang, Wenjun Wang, Yang Yu, Yinghui Wang, and Pengfei Jiao. Role-oriented graph auto-encoder guided by structural information. In Proceedings of the 25th International Conference on Database Systems for Advanced Applications, pp. 466 481, 2020.
William Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Proceedings of the 2017 Advunces in Newral Information Processing Systems, pp. 1024 1034, 2017.
Peter Hoff. Modeling homophily and stochastic equivalence in symmetric relational data. Advances in Newral Information Processing Systems, 20, 2007.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang. Graphmac: Self-supervised masked graph autoencoders. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 594-604, 2022.
Zhenyu Hou, Yufei He, Yukuo Cen, Xiao Liu, Yuxiao Dong, Evgeny Kharlamov, and Jie Tang. Graphmae2: A secoding-enhanced masked self-supervised graph learner. In Proceedings of the 2023 ACM Web Conference, pp. 737-746, 2023.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In Proceedings of the 2018 International Conference on Machine Learning, pp. 2186-2195, 2018
Yilun Jin, Guojie Song, and Chuan Shi. Gralsp: Graph neural networks with local structural patterns. In Proceedings of the 2020 AAAT Conference on Artificial Intelligence, pp. 4361-4368, 2020.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Representations, 2017.
Kai Lei, Meng Qin, Bo Bai, and Gong Zhang. Adaptive multiple non-negative matrix factorization for temporal link prediction in dynamic networks. In Proceedings of the 2018 ACM SIGCOMM Workshop Network Meets AT & ML, pp. 28 34, 2018.
Kai Lei, Meng Qin, Bo Bai, Gong Zhang, and Min Yang. Gen-gan: A non-lincar temporal link predic- tion model for weighted dynamic networks. In Proceedings of the 2019 IEEE Conference on Computer Communications, pp. 388 396, 2019.
Pan Lí, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Proceedings of the 2020 Advances in Neural Information Processing Systems, 33:4465-4478, 2020.
Wei Li, Meng Qin, and Kai Lei. Identifying interpretable link communities with user interactions and messages in social networks. In Proceedings of the 2019 IEEE International Conference on Parallel & Distributed Processing with Applications, pp. 271-278, 2019.
Zirui Liu, Chen Shengyuan, Kaixiong Zhou, Daochen Zha, Xiao Huang, and Xia Hu. Rsc: accelerate graph neural networks training via randomized sparse computations. In International Conference on Machine Learning, pp. 21951 (1951-21968, 21968, 2023.
19

---

Published in Transactions on Machine Learning Research (10/2024)
Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 200:108-122 1020-22,- 2016.
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103723):8577-8582, 2006.
Dai Quoe Nguyen, Tu Dinh Nguyen, and Dinh Phung. A self-attention network based node embedding model. Proceedings of the 2021 Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 364-36440 377, 2021.
Dai Quoc Nguyen, Tu Dinh Nguyen, and Dinh Phung. Universal graph transformer self-attention networks. In Companion Proceedings of the Web Conference 2022, pp. 193-196, 2022.
Yulong Pei, Xin Du, Jianpeng Zhang, George Fletcher, and Mykola Pechenizkiy, struc2gauss: Structural role preserving network embodding via gaussian embedding. Data Mining & Knowledge Discovery, 34(4): 1072 1103, 2020.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery & data Mining, pp. 701 710, 2014.
Meng Qin and Kai Lei. Dual-channel hybrid community detection in attributed networks. Information Sciences, 551:146-167. 2021.
Meng Qin and Yan Yeung. Temporal link prediction: A unified framework, taxonomy, and review. ACM Computing Surveys, 56(4):1-40, 2023.
Meng Qin, Di Jin, Kai Lei, Bogdan Gabrys, and Katarzyna Musial. Adaptive communily detection incor- porating topology and content in social networks. Knowledge- -aasdd Based Systems, 161:342-356 2018.
Meng Qin, Chaorui Zhang, Bo Bai, Gong Zhang, and Dit-Yan Yeung. Towards a better trade-off between quality and efficiency of community detection: An inductive embedding method across graphs. ACM Transactions on Knowledge Discovery from Data, 2023a.
Meng Qin, Chaorui Zhang, Bo Bai, Gong Zhang, and Dit-Yar Yeung. High-quality temporal link prediction for weighted dynamic graphs via inductive embedding aggregation. IEEE Trunscctions on Knowledge and Data Engineering, 2023b.
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD Internationol Conference on Knowledge Discovery & Data Mining, pp. 385-330 394, 2017.
Ryan A Rossi, Di Jin, Sungehul Kim, Nesreen K Ahmed, Danai Koutra, and John Boaz Lee. On proximity and structural role-based embeddings in networks: Misconceptions, techniques, and applications. ACM Transactions on Knowledge Discovery from Data 14(5):1-37, 2020.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In Proceedings of the 8th International Conference on Learning Representations, 2020.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mci. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pp. 1067- 1077, 2015.
Ashish Vaswani, Noam Shazoer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Proceedings of the 2017 Advances in Neural Information Processing Systems, pp. 5998 6008, 2017.
20

---

Published in Transactions on Machine Learning Research (10/2024)
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Proceedings of the 6th International Conference Learning Representations. 2018.
Petar Velickovie, William Fedus, William L Hamilton, Pietro Lio, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In Proceedings of the 7thh International Conference on Learning Representations, 2019.
Uhrike Von Luxburg. A tutorial on spectral clustering. Statistics & Computing, 17(4):395-41, 2007.
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Community preserving network embedding, In Proceedings of the 2017 AAAI Conference on Artificial lintelligence, pp. 203-2033 403-209, 2017.
Xiao Wang, Meiqi Zhu, Deyu Bo, Peng Cui, Chuan Shi, and Jian Pei. Am-gen: Adaptive multi-channel graph convolutional networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1243 1253, 2020.
Jun Wu, Jingrui He, and Jiejun Xu. Demo-net: Degree-specific graph neural networks for node and graph classification. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 406 415, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks & Learning Systems, (1:4):4 ) 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, 2019.
Yuchen Yan, Yongyi Hu, Qinghai Zhou, Lihui Liu, Zhichen Zeng, Yuzhong Chen, Menghai Pan, Huiyuan Chen, Mahashweta Das, and Hanghang Tong. Pacer: Network embedding from positional to structural. In Proceedings of the ACM on Web Conference 2024, pp. 2485-2496 2024.
Yang Yang, Jie Tang, Cane Wing-ki Leung, Yizhou Sun, Qicong Chon, Juanzi Li, and Qiang Yang. RAIN: social role-aware information diffusion. In Proceedings of the 29th AAAI Conference on Artificial Intelli- gence, pp. 367-373, 2015.
Dongsheng Ye, Hao Jiang, Ying Jiang, Qiang Wang, and Yulin Hu. Community preserving mapping for network hyperbolic embedding. Knowledge-Baad Based Systems, 246:108699, 2022.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aw aware graph neural networks. In Proceedings of th 2019 International Conference on Machine Learning, pp. 7134-7143, 2019.
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural net- works. In Proceedings of the 2012 AAAI Conference on Artificial Intelligence, pp. 10737-107440 2021.
Wentao Zhang, Yu Shen, Zheyu Lin, Yang Li, Xiaosen Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. Pasca: A graph neural architecture scarch system under the scalable paradigm. In Proceedings of the 2022 ACM Web Conference, pp. 1817 1828, 2022.
Jing Zhu, Xingyu Lu, Mark Heimann, and Danai Koutra. Node proximity is all you need: Unified structural and positional node and graph embedding. In Proceedings of the 2021 SIAM International Conference on Data Mining, pp.
2021.
A Detailed Algorithms
The RW sampling procedure starting from node is summarized in Algorithm 6 which uniformly sample the next node v, from the neighbors of each source node Ug..
Algorithm 7 summarizes the transductive inference procedure of IRWE, where the RWs (Wi*), w(r)), }. AW lookup table Qg and statistics (8(1), (v)) derived the model optimization are used the inputs.
21

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 6: RW Sampling Starting from a. Node
Input: topology (V, E); larget node v; RW length & number of samples vss Output: set of sampled RWs Vo())
W 4- 0 / //nitiialize W(
from 1 to do 3 1y u and w < (#x) //Initialize current RW w
for sample_comme
while |w| (1 do
5 randomly sample a node is from v,'s 's neighbors
append to
7
Vx 4- U2
add w to Wi(e
Algorithm 7: Transductive Inference
Input: RWs (Wi()) W/")), AW lookup table it & statistics (8()),(()) [v)3 saved in model optimization; inference topology (V,E)
Output: transductive embddings {d(v)) & {r(e)) w.r.t V
get {vb())} based on (f4,,((),,(()) w.r.t. V
get {7(1) based on (t)) W( w.r.t. V
Therefore, the transudcitue inference of identity embeddings {v(()} and position embeddings {r(t)} only includes one feedforward propagation through the model.
Procedures to get inductive AW statistics {s(e)}, high-order degree features {ō(v)}, and global position encodings (v)), which support the inductive inference for new nodes wilhin graph (i.e., Algorithm 5 are described in Algorithms g g and respectively. When deriving {s(u)}, only compute the frequency of AWs in the lookup table 22 reduced on (V,E) rather than all AWs. Morcover, we get {ő(w)} based on the one-hot degree encoding truncated by the minimum and maximum degrees of the training topology (V,E) but not those of the inference topology (VUV, E²). For Ty (v), we compute truncated RW statistic r(v) only w.r.t. previously observed nodes V rather than V...
The inductive inference across graphs is summarized in Algorithm 11 We sample RWs (W(r) wf")) on each new graph (V", """). Since there are no shared nodes between the training topology (V,E) and infer- ence topology (V", 8"",, we only incrementally compute statistics (8(v),6(v) based on { degmin degmax) derived from EV,E) but compute global position encodings (T)( from scratch.
B Complexity Analysis
The complexity of the RW sampling starting from each node (i.c., Algorithm 6 is no more than O(ns)). The complexities to derive AW statistics s(u) (i.e., Algorithm Dh, high-order degree features 8(v) (i.e., Algorithm 2, and global position encoding (u) (i.e., Algorithm 3 w.r.t. a node are O(ns), O(ngl), and O k())d), with k(e) as the number of nodes observed in W The overall complexity to derive the RW-induced statistics (i.c., the feature inputs of IRWE) from graph (V,E) is no more than O(V]ngd + M/nss + W|ns! + (DVnss + kd)) O([Viss + kd), with Is = Eeev k(v).
As described in Algorithm 7 the transductive inference of IRWE only includes one feedforward propagation through the model. Its complexity is no more than Ofiii' [[](el+|V[ell + d V/n + (VVd + +|Vld) + [V[d+ l)d + [V|n + nyd)= = (T) + n,12)dh), where we assume that el = d, 12 & [V], and < in; the number of attention heads. According to Algorithm 5 the complexity of inductive inference for new nodes within graph is O(IV"|ngl k' k'd+ (VV" n ())),,,,, with k' Evey k(v). The complexity of inductive inference across graphs (i.e., Algorithm is [[V""ngs k'd I + nn))) with K" ;= Ev k(v).
Table summmarizes and compares the complexities of model parameters to be learned for all the methods in our experiments, where N is the number of nodes; d is the dinensionality of input feature embedding;
22

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 8: Inductive Derivation of AW Statistics
Input: new target node E V"; sampled RWs W AW lookup table Q reduced on old topology (V,8) Output: inductive AW statistic s(v) w.r.t.
fj [4]] //Get size of reduced AW lookup table
a(v) - [0, 0, ..... ,0 //Initialize s(Ø)
for each w Wir do
map RW to its correspouding AW
if w E f then
G
get the index j of AW w in reduced lookup table Q2 s(v); s()); /Uppatee s(v)
7
Algorithm 9: Inductive Derivation of Degree Feature
Input: new target node E V"; RW length I; one-hot degree encoding dimensionality e; sampled RWs Wi0);
desmin & degmax in old topology EV,
Output: inductive degree feature 6(v) w.r.t.
ō(v) - (0.0..... .00....0011))) for each wi do
" //Tnitialize degree feature 5(v)
3
for from 0 to do 4- w(()) //i-th node current RW w
4
if u V then
6
pa(u)= < [0,..., .0]" //nitiialiee one-hot degree encoding if deg(u) < degmin then
8
-+0
else deg(u)= > degmax then L j (e (e-1)
11
else
j (leg(u)-dezuiiu) (degmax desmin)
pa(u); + 1/Update pa(u) 8(v)ee(141)) < 6(V) + pa(u)
14
is the RW/AW length; y and fn denote the (i) number of AWs w.r.t. length and (fi) reduced value of mi L is the number of layers of GNN or transformer encoder; is the mumber of attention heads. Since most transductive embedding methods (e.g., node2vec and struc2vec) follow the embedding lookup scheme, their model parameters are with a complexity of at least. O(Nd). Most. inductive approaches rely on the attribute aggregation mechanism of GNNs. Their model parameters have a complexity of at least OLLd²). Methods based the multi-head attention transformer encoder (c.g., SANNE, UGFormer, and IRWE) should have at least O(Lhd) learnable model parameters. In addition, IRWE also includes the AW auto-encoder and MLPs in the identity embedding encoder and decoder. Therefore, the model parameters of IRWE have a complexity of ((2dd + (m + le)d + Lhdz) = 0(l2d + înd + Lhd"), where we assure that el R d.
C Proof of Proposition
For simplicity, we let Zij == ((u:))"((u)) (U;)/T. To minimize the contrastive loss Lenr 10 one can let its partial derivative 0Leur/21 Zij w.r.t. each edge (v, E E to O. Since axx) = 1/(1 + e and do dx)x//d [x) [x)], we have
ÖLen/ Piy(1 022r)) + Qm, (1 o(-2))))
(15)
which can be rearranged as
Pijo((zs)) Qujj(-=zz)) Pij Qn--
(16)
23

---

Published in Transactions on Machine Learning Research (10/2024)
Algorithm 10: Inductive Derivation of Global Position Encoding
Input: new target node E V"; sampled RWs Wlo) old training node set V; random matrix A E R Vixd Output: inductive global position encoding (e( w.r.t.
r(v) < [0,00... ...... .0"") //Initialize RW stat r(v)
for each E Win) do
for each node E w do if y then get index j of v in the training node set V r(u), r(v), //Update r(v)
5
[1) < ( /Deriee (2)
Algorithm 11: Inductive Inference across Graphs
Input: optimized model parameters (0%, 07] new topology E""; RW settings (1, ns, my): local position encodings (mi()); (f4, degmin: degmax] derived in model optimization on old topology (V,
Output: inductive embeddings (v(e)} & (7(1)) w.r.t. V"
for each node E y" do
sample RWs WDO from w.r.t. E" via Algorithm
get AW statistics s(e) w.r.t. (Mp()), 2i) via Algorithm
get degree feature 5(v) w.rtt (Wii), damn dmax) via A Algorithm get global position encoding (v) w.rtt. wi(e) via Algorithm randomly select RWs W from W(()
get {xb()}} based on 5(v), w.rtt V"
get {7(1) based on (1((0, (v)) mi (t), W/ w.r.t. V"
Table 8: Summary of the Complexilies of Model Parameters to be Learned.
mode@vec
Graltep
strucEvec
struc2gauss
PaCEr
PhN
GSAGE
DGI
GMAE
O(Nd)
O(Nd))
O(Nd)
O(Nd)
O(N(d N))
O(Nd)
O(L8")
O(La")
O(Ld")
GMAER
P.GNN
CSGCL
GraLSP
SPINE
GAS
SANNE
U.Former
O(Ld")
O(Ld")
O(Ld))
O md)
O(d")
O(Ld*)
O(Lhd*)
O(Lhd")
O('a + Fndd Lkd
By applying a(-x) =o(oo(x), we have
((jo(Zz)) - Qn, exp((=isto(1 = Pij Qn
Py Qn, exp(
Pij Qni
1texpt -15)
Po Q - Qm, (+exp(-2:1]
Pij Qni
1texpl -211)
(pij + Q2,))
= Pij
(17)
+ (23)) = Ptj/ (Pij + +Qn))
+ exp( -21y] (pi + Qn;)\Pp
(opp--z) Qn,/poj
By taking the logarithm of both sides, we further have
Fig In Pig - In(Qn)).
(18)
Let C E | be an auxiliary matrix with the same definition as that Proposition 1. From the perspective of matrix factorization, we can rewrite the aforementioned equation another matrix form rfT /r C, which is equivalent to the reconstruction loss L, 14
24

---

Published in Transactions on Machine Learning Research (10/2024)
Table 9: Parameter Settings for Transductive Inference.
c, ug. Br)
(Ap, A,)
[m, weg m,)
(1,
PPT
(256. 100, le3.
10)
(5e-4,1o-3)
(2c3. 1)
(7. 0.1, 5c2)
Wiss
(256, 100, le3, 10)
(1e-3.1e-3)
(le3, 5. 1)
(7, 10, le3)
Blog
(256,
1e3, 10)
(5e-1.5e-4)
(3e3, 20)
(9, 10, 10)
USA
[128, 100, 163,
20)
(1e-3,5e-1)
(500. 10, 1)
(9, 10, 10)
Europe
(64,
1e3,
20)
(5e-4,5e-4)
(200,
(9, 10, 10)
Braail
(64, 32,
163, 20)
(5o-4,50-4)
(200. 1, 1)
(9. 0.1, le2)
Table 10: Parameter Settings for Inductive Inference.
(Aw. A,)
me, my)
(1, a, r)
PPI
(256, 100, 1e3, 10)
(5e-1.1e-1)
(1e3, 20, 1)
(7, 10, Ge2)
Wiki
(256, 100, le3, 10)
(1e-3,56-4)
(1e3. 1)
(7, 10, 5e2)
Blog
(256, 100, 1e3, 10
(5e-4.5e-4)
(1e3, 20, 5]
(6, 10, 5)
USA
(128, 100, 1e3, 10)
(5e-1.5e-1)
(500, 10, 1)
(9, 10, 10)
Europe
(64, 100, 163,
(5e-4.5e-4)
(200, 1, 1)
(9. 10, 10)
Brazi
(64, 32, 1c3, 10)
(5e-4.5o-4)
(200. 1, 1)
(9, 0.1, 1c2)
PPIs
(256, 100, 163, 10)
(5e-4.5e-4)
(1000, 5, 1)
(9, 10, 50)
Table 11: Layer Configurations for Transductive Inference.
Identity Embedding Module
Foxition Embedding Module
Dataects
Emcpt)]
Deep()
Rad,
(e
MLP ReAST()
(Zeran
Prout
PPI
2.125...d.
2.128.1.12,
Rg 24,228... 11..244....12....222..1 102....12...dd.
64
d.612.4.lc.
d.dadadddd
(4. 64)
64
Wili
d.128.u:
64
d.G12.L.f..
(4. G4)
G4
12 12
d,128,t,13
r2+He,1024,,.51222 f..
d.812,t.fe.t
USA
4.100.1...a
10,40.00.. ..12.x...
82
d.d.daddddd
82)
Suroge
d.64,s,12
1024,1 die
16
d.256.1.512...8
dadia,d
(4. 1G)
Broad
12 12,64.165
a.64,6,1%.
1024,,1024,..01 2, 128,
16
d.128.t.fe.t
(4. 16)
Table 12: Layer Configurations for Inductive Inference.
Identity Embedding Module
Position Embeddiing Module ReAst))
Emcy())
De
(=
(Reran Peran)
Prout
PPJ
(3. (2,128.5.4.
d.128.1.12.
102.,........22......
64
d.fe.t
d.d.a.d......d
(4, 64)
64
(2,22,,....1
4.128,0.1.1
d.612.1.fo.
d.d.a.d.a.d...dd
G4
Bios
12,2,...d.
4.128.t.12.
ny+He.1106...b22...d
dit.b12.t.fe..t
d.d,a,d daa,da
(b.
USA
4.100.4.2.4
32
d.612:4.1e.
d.d.addad
(4, 16)
16
Suraee
d.64,1,12.
1o,1024...
16
d.d.vvda
(4. 16)
16
Bracd
d.84.1.12
d.d.a,da
128,3.d4
6.128.4.12.
4.612.4.e..
d.d.adaa
(0.
D Detailed Experiment Settings
Given a clustering result (C,. ............ ,Kk], NCut w.r.t. the auxiliary similarity graph Gn defined as
NCut(C:9p) = 0.5 Σx- [eut(C,, (M)(C,,C,)/vol(C..))
(19)
uyy (AD)y, with Ap as the adjacency matrix of GD- Given clustering result C, modularity w.r.t. the original graph is defined as
where C, : V V- Cr, Cut(C,,C,,)== Ev, EC, (AD).) and vol(C.) := Ev,
Σ K E U..,E [Aij - deg(v:) deg (eg();)/(2e),, Mod 9) = 2e r=1
(20)
where :: E, deg(r:)/2 is the number of edges.
The parameter settings of IRWF, for the transductive and inductive inference are depicted in Tables g and 10 where d is the embedding dimensionality; e is the dimensionality of one-hot degree encoding for the degree features (ō(r)}; ns [W(']| and nı := |w(") are the number of sampled RWs and number of RWs used to infer position embeddings for each node e; Xy and xy are learning rates to optimize identity and position embeddings; m is the number of training iterations; in each iteration, we update identity and position embeddings my and my times; I is the RW length; a and t are hyper-parameters in the training losses.
Tables and 12 give layer configurations for the transductive and inductive embedding inference, where Eac, and Dec. denote the AW encoder and decoder described in (1: Red,()) is the feature reduction
25

---

Published in Transactions on Machine Learning Research (10/2024)
Table 13: Evaluation Results on Attributed Graphs for the Validation of Inconsistency of Attributes.
Cornell
Texas
Washington
Wisconsin
Modf(%)
NCut,
(%)
NCut.
Mod1(%)
NCut,
(%)
NCut]
node2vee
56.93
3.18
45.99
3.10
44.94
3.59
54.73
2.97
struc2vec
-9.50
1.53
-11.37
1.17
-9.33
0.71
-8.94
1.34
att-emb
-0.09
3.76
-0.01
3.75
-2.30
3.84
-3.54
3.75
n2v jat
50.80
3.38
35.26
3.12
44.05
3.30
54.02
3.13
[2v (att)
-5.76
1.81
-12.77
-2.81
1.00
-9.58
unit (2); Deca(.) represents the identity embedding decoder (4) ReAtt(-) is the attentive reweighting function ( iu := [$2r] is the reduced number of AWs; hy, htran and Azout represent the numbers of attention heads in identity embedding encoder 8 transformer encoder 18 and attentive readout function (9); ITran is
the number of transformer encoder layers; 't', 's', and 'r' denote the activation functions of Tanh, Sigmoid, and ReLU. For our IRWE method, we recommend sctting 1 E f4,5, ,9), a E {0.1, 1, 5, 10), e {1,5, 10, 50, 100, 500, 1000), and mp. myy E (1,5,10,20; 20,.
We adopted the standard multi-head attention (Vaswani et al. 2017 to build the identity embedding encoder 3 and attentive readout unit (9) of IRWE. An allention unit includes the inpuls of key, query, and value described by K E Rmxdd Q E Raxd, and V E Rnxd, Assume that there are h attention heads. Let d = d/h. For the j-th head, we first derive linear mappings K() kW(), Q() - Qw((), and V() vw 8 with (w(() E Raxd, w(() R w!!) E Rdxd] as trainable parameters. The attention head is defined as
z = Att,(Q, == softmax QU) VVvvo.
(21)
We further concatenate the outputs of all the heads via Z Att K, V) = |0 |Z
All the experiments were conducted on server with AMD EPYC 7742 64-Core CPU, 512GB main memory, and one NVIDIA A100 GPU (80GB memory). We used the official code or public implementations of all the basclines and tuned parameters to report their best performance. On cach datasct, we set the same embedding dimensionality for all the methods.
E Further Experiment Results
To demonstrate the possible inconsistency of graph attributes for identity and position embedding dis- cussed in Section 1 we conducted additional experiments four attributed graphs (i.e., Cornell, Tezas, Washington, and Wisconsin) from WebKee For each graph, we extracted the largest connected component from its topology. After the pre-processing, we have (N, E, K) = (183, 227, 1703, 5), (183, 279, 1703, 5), (215, 365, 1703, 5), and (251, 450, 1703, 5) for Cornell, Teaas, Washington, and Wisconsin, where N, E, and K are numbers of nodes, edges, and clusters; M is the dimensionality of node attributes.
We then applied node2vec and struc2vec, which typical position and identity embedding basclines described in Table to the extracted topology of each graph, where we set embedding dimensionality d d= 64. Furthermore, we derived special attribute embeddings (denoted as att-emb) with the same dinensionality by applying SVD to node attributes. Namely, we have three baseline methods (e.g., node2vec, struc2vec, and att-emb). To simulate the incorporation of attributes, we concatenated att-emb with node2vec and struc2vec, forming another two additional baselines denoted as [n2v] [att] and [s2v|]att]. The unsupervised community dotection and node identity clustcring were adopted as the downstream tasks for position and identity embedding, respectively. The evaluation results depicted in Table where att-emb outperforms neither (i) node2vec for community detection nor (ii) struc2vee for node identity clustering: the concatenation of att-emb cannot further improve the embedding quality of node2vec and struc2vec. The results imply that (i) attributes may fail to capture both node positions and identities; (ii) the simple integration of aftributes may even damage the quality of position and identily embeddings.
httpp://www..cs.cmm..ttt
/data/
26

---

Published in Transactions on Machine Learning Research (10/2024)
F Discussions of Future Research Directions
Some possible future rescarch directions of this study are summarized as follows.
In this study, we focused on network embedding where topology is the only available information source without any attributes, due to the complicated correlations between the two sources (Qin et al, 2018 ct al. 2019; Wang ct al., 2020 Qin & Lei, 2021). We intend explore the adaptive incorporation of aftributes. Concretely, when attributes carry characteristies consistent with topology, one can fully utilize attribute information to enhance the embedding quality. In contrast, when there inconsistent noise in attributes, need to adaptively control the effect of attributes to avoid unexpected quality degradation.
In addition to mapping each node to a low-dimensional vector (a.k.a. node-level embedding), network embedding also includes the representation a graph (a.k.a. graph-level embedding). We plan to extend IRWE to the graph-level embedding and evaluate the embedding quality for some graph-level downstream tasks (e-g,, graph classification). To analyze the relations of graph-level embeckiings to identity and position embeddings also our next focus.
The optimization of IRWE adopts the standard full-batch setting, where we derive statistics or embeddings
w.r.t. all the nodes when computing the training losses. This setting may not. be scalable to graphs with large numbers of nodes. Inspired by recent studies of scalable GNNs (Zhang et al. 2022 Liu et al. 2023). we intend to explore a scalable optimization strategy based on mini-batch scttings.
27


Reviews:
[{"review_id": "G4HrBc3bRN", "reviewer": "Reviewer_a8jk", "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    * [S1] The method is clearly positioned wrt the state of the art\n    * [S2] The authors take care to motivate their technical decisions (using Theorem 1 and Hypotheses 1 and 2, among others), even if some decisions could be even further explained (cf below)\n* Weaknesses\n    * [W1] I have a major problem with the evaluation as it is now: it seems performance reported is based on hyper-parameter tuning, but there is no discussion in the text about how to select those hyper-parameters\n    * [W2] The overall architecture is rather complex. Though the authors try to break the whole architecture in smaller bits to better explain them (which is really appreciated), it is sometimes hard to follow and some of the illustrations can be misleading\n\nMore detailed comments regarding the above-mentioned weaknesses:\n\n* W1\n    * In cases where supervised information is available, it would be nice to provide performance for some supervised methods (GAT & co): even if one does not expect your unsupervised approach to compete with those, it is always interesting to have an idea of how large the gap is on downstream tasks\n    * You should use bold + underline for all methods in your tables for the reader to make her opinion\n    * It would be interesting to report performance for the IRWE method in case only one of the embeddings is used (position or identity) in all tables 5 to 7\n    * Performance reported in Tables 5 to 7 relies on hyper-parameter selection that seems to have been performed based on test set performance. Tables 10 to 13 report the hyper-parameters used, yet no hyper-parameter selection scheme is presented. If you compare your method to a bunch of baselines, you need to either use a fixed set of hyper-parameters that works well across a large number of datasets or provide a hyper-parameter selection method (e.g. rely on the validation set for selection)\n* W2\n    * In Fig. 3: the \"one-hot encoding\" is a bit strange: it seems the value 1 is sometimes encoded as 0100 and sometimes as 0001, depending on the index at which it occurs (eg compare [2] and [6]). Another reason why your one-hot encoding is not very intuitive is that the value 0 is encoded as \"0000\" whereas 1 is encoded as \"0100\": it seems the first bit is never used\n    * In practice, it seems you do not have $d << l^2$, hence Fig.4 is misleading as the AW Encoder is not really contracting information\n    * Fig. 4 is incomplete since the identity Embedding Regularization unit reconstructs $s(v)$ too, I think. Also, it is unclear why this is called a regularization unit and not a decoder, as for the AW decoder...\n    * Some points on which the paper does not provide sufficient intuition\n        * Why would information from AW statistics and degree information be complementary? The paper lacks intuition about many such questions that should be answered to motivate the chosen architecture\n        * Wouldn't it be better to resample RWs every few epochs, in order to better catch information from a node's neighbourhood?", "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 paper introduces a new model for unsupervised graph embedding. The model extracts both an identity embedding and a position embedding for each node of a graph. The method is inductive (i.e. a trained model can be used to extract embeddings for a new unseen graph).\nThe method relies on random walks and the related concept of anonymized walks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Related to the weaknesses pointed above, I am requesting two major changes:\n\n1. If my understanding of your evaluation (cf above) is correct, it is required that you either:\n    * report IRWE performance for a fixed set of hyper-parameters\n    * cross-validate hyper-parameters on the validation set for both IRWE and the baselines and report resulting performance\n2. Your illustrations should be revamped to better help the reader in their understanding of your notations", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6tJSPg3yjM", "reviewer": "Reviewer_D6v2", "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\n1) The paper proposes a novel and interesting approach for characterizing identity and position embeddings based on random walks over the graph.\n\n2) The model performs well in both inductive and transductive settings.\n\n3) The paper includes multiple experiments across various settings, often significantly outperforming the baselines.\n\nWeaknesses:\n\n1) The paper does not discuss existing literature that relates capturing identity and positional embeddings to modeling stochastic equivalence and homophily in networks, such as \"Modeling homophily and stochastic equivalence in symmetric relational data\" by Peter D. Hoff, 2008.\n\n2) The paper lacks any link prediction experiments, which is one of the most prominent downstream tasks.\n\n3) The analysis and description of the method are somewhat convoluted and can be difficult to follow at times.", "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": "This paper introduces a new embedding method acting as a unified framework for the joint inductive inference of identity and position embeddings where node attributes are not present. The paper introduces an inductive random walk embedding (IRWE) method that utilizes multiple attention mechanisms to create a random walk on graph topology defining jointly-optimized identity and position embeddings. Results based on multiple networks for in an inductive, as well as, transductive setting in the tasks of node classification and node identity clustering, showcase the superiority of the method against the considered baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) The paper should discuss connections to and compare its performance with classical studies, such as the work by Peter D. Hoff.\n\n2) The paper should include link prediction experiments, as this is a prominent downstream task.\n\n3) More recent transductive methods should also be considered, as most of the methods currently considered are not very recent.\n\n4) The paper should include a discussion on the number of parameters used by the proposed method and compare this with the considered baselines.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "FFCBCuRoWJ", "reviewer": "Reviewer_gxMC", "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: \n\nThe shown performance has a significant improvement over previous methods. \n\nWeakness:\n\n1. The methodology part of the work is very hard. The system is super complex, making it very hard to verify the correctness. If the model is engineered toward just improving performance over benchmark datasets, I am not sure what new knowledge I can learn from this work. Moreover, the main claimed contribution is the joint learning of identity embedding and positional embedding, but this has been considered by previous work such as PhUSION. The submission may need to be more specific about the motivation, aka, which problem is addressed by the proposed work. \n\n2. I am not sure whether the learned embeddings are inductive. When the position embedding is used, how does the model generalize to a new graph? In particular, how does the model align a node in the new graph to a corresponding node in the training graph such the two nodes have \"similar\" positions and get similar embeddings? \n\n3. The submission is too long because a lot of descriptions are redundant. Here I just give a few examples: \n1) the discussion of embeddings in Section 1 has a lot of overlap with the discussion in Section 2. \n2)Table 1 is not needed as long as they are clearly defined in the text. \n3) the first paragraph in Section 4 before 4.1 is only distracting. It should be integrated into the discussion of the method. \n4) Attention should not be a definition in the work because it is irrelevant to the work's main focus. \n\nOverall, I feel that the work should be compressed to 12 pages.  \n\n4. The \"formal\" definitions and hypotheses are not accurate. For example, in Definition 1, there are quite a few ambiguous terms such as \"some key properties\". In definition 2: \"the structural role\". In definition 3, \"the high-order linkage\". In my view, a definition should be mathematically accurate. \n\nFurthermore, theorem 1 from (Micali & Zhu, 2016) is interpreted incorrectly in this submission: $l = 2(m+1)$ is the complexity used only one induction step in the original work, not the complexity for the entire recovery algorithm.", "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": "The work proposes a new method of learning node representations from random walks. The results have shown significant performance improvement over previous methods in several node classification tasks.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please make the writing concise and highlight the main idea.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work presents a method for unsupervised graph embedding without attributes. The proposed method jointly learns positional and identity embeddings based on an inductive random walk embedding method.

The approach is novel and seems to perform well in practice, and the evaluation is thorough. The reviewers had a number of concerns about the experimental settings, the exposition, and the discussion of related work, but these have all been adequately addressed in the revision. We appreciate the thorough discussion of the points raised.

While we appreciate that you have addressed concerns about the paper length, we suggest returning the figures to their original size, rather than shrinking them.
Decision: Accept (poster)