#  Transitivity-Preserving Graph Representation Learning for Bridging Local
Connectivity and Role-based Similarity

Van Thuy Hoang and O-Joun Lee†
Department of Artificial Intelligence, The Catholic University of Korea
Bucheon-si, Gyeonggi-do 14662, Republic of Korea
<EMAIL_ADDRESS>

###### Abstract

Graph representation learning (GRL) methods, such as graph neural networks and
graph transformer models, have been successfully used to analyze graph-
structured data, mainly focusing on node classification and link prediction
tasks. However, the existing studies mostly only consider local connectivity
while ignoring long-range connectivity and the roles of nodes. In this paper,
we propose Unified Graph Transformer Networks (UGT) that effectively integrate
local and global structural information into fixed-length vector
representations. First, UGT learns local structure by identifying the local
substructures and aggregating features of the $k$-hop neighborhoods of each
node. Second, we construct virtual edges, bridging distant nodes with
structural similarity to capture the long-range dependencies. Third, UGT
learns unified representations through self-attention, encoding structural
distance and $p$-step transition probability between node pairs. Furthermore,
we propose a self-supervised learning task that effectively learns transition
probability to fuse local and global structural features, which could then be
transferred to other downstream tasks. Experimental results on real-world
benchmark datasets over various downstream tasks showed that UGT significantly
outperformed baselines that consist of state-of-the-art models. In addition,
UGT reaches the expressive power of the third-order Weisfeiler-Lehman
isomorphism test (3d-WL) in distinguishing non-isomorphic graph pairs. The
source code is available at https://github.com/NSLab-CUK/Unified-Graph-
Transformer.

††footnotetext: † Correspondence<EMAIL_ADDRESS>Tel.: +82-2-2164-5516

_K_ eywords Graph Transformer $\cdot$ Graph Representation Learning $\cdot$
Structure-Preserving Graph Transformer $\cdot$ Local Connectivity $\cdot$
Role-based Similarity

##  1 Introduction

Graph neural networks (GNNs) and graph transformers have effectively solved
graph analysis tasks, such as node classification and link prediction [1, 2,
3]. GNNs learn representations by iteratively aggregating features of
neighbouring nodes with uniform or attentional weights [1, 4]. Unlike GNNs,
graph transformer models learn node representations using self-attention,
encoding pair-wise connections between nodes, and have shown better
performance than variants of GNNs [2].

Figure 1:  The Laplacian positional encoding cannot guarantee capturing
similarity between surrounding structures of nodes. Two adjacent nodes, ‘1’
and ‘3’, have different positional encodings even though they are structurally
similar.

While the existing models have been applied to various domains, GNNs and graph
transformers still have three inherent limitations. First, graph transformer
models lack the power to capture similarity between local structures. Some
recent graph transformers (e.g., GT [2] and SAN [5]) use graph structural
features (e.g., Laplacian Eigenvectors) as positional encodings (PEs) to
distinguish isomorphic substructures. However, although the PEs can assign
distinguishable representations to substructures of individual nodes, they do
not always reflect structural similarity between the substructures. PEs that
account for substructure similarity are significant for the models to
understand connectivity between neighbours, rather than simply aggregating
their feature vectors. In Figure 1, we assign the PEs to two nodes, ‘1’ and
‘3’, with Laplacian Eigenvectors. Then, their vector representations are
dissimilar, although they have similar local structures. This impreciseness
can be a serious obstacle to learning representations of graph structures and
eventually affect the models’ performance.

Second, GNN aggregators and self-attention lack the power to learn global
structural features. GNN variants, like GCN [1], GAT [6], and GATv2 [7, 8, 9],
compose node embeddings based only on features of neighbours. Similarly, graph
transformer models learn node representations by encoding features of node
pairs and substructures within $k$-hop distance using self-attention [10, 11,
12]. Although graph transformers have larger aggregation ranges in a layer
than GNNs, neighbourhood aggregation is not powerful enough to reveal long-
range dependencies or role-based similarities of nodes.

Third, the existing models lack the ability to integrate local and global
structural features into a unified representation, which could benefit various
downstream tasks. For example, influential nodes in social networks will be
centres of different communities, and we consider both ‘influence (global)’
and ‘community (local)’ to analyse the nodes. Some GNNs and graph
transformers, such as LSPE [13] and GPS [14], try to capture higher-order
substructures surrounding nodes within $k$-hop distance and consider them in
messages or node features. However, we cannot increase the $k$-hop distance as
the graph diameter increases. Furthermore, global structural features (e.g.,
long-range dependencies) correlate with node roles (i.e., substructures rooted
in nodes). Similar roles of nodes do not always indicate their adjacency or
similar node features but rather the opposite. Therefore, the different views
of the features are a significant barrier to integrating these features into a
unified vector representation.

To overcome the limitations, we propose Unified Graph Transformer Networks
(UGT), which can represent both local and global structural features of graphs
with a unified vector representation. We first construct virtual edges
connecting the distant nodes with role-based similarity. By sampling $k$-hop
neighbourhoods with both virtual and actual edges, UGT can observe long-range
dependencies of nodes along with their local connectivities. We propose
structural identity, which is a substructure descriptor, and use it for
identity mapping in transformer layers to preserve information about roles of
nodes. Structural distances estimated based on the substructure descriptor are
also used to compute attention scores to consider role-based similarity.
Transition probabilities are used together to calculate the attention scores
to consider proximity and role jointly. Finally, to bridge the gap between
local and global structures, UGT is pre-trained to preserve $p$-step
transition probabilities, considering all the paths between two nodes and
reflecting proximity and surrounding structure in multiple scales. Our
contributions are as follows:

  * •

We propose Unified Graph Transformer Networks (UGT), which can learn local and
global structural features and integrate them into a unified representation.

  * •

Our novel sampling method constructs virtual edges between nodes with high
role-based similarity and samples $k$-hop neighbourhoods to observe long-range
dependencies and local connectivity together.

  * •

The pre-training task is proposed to bridge the conceptual gap between local
and global structures by preserving transition probabilities between nodes,
which reflect both connectivity and surrounding structures of the nodes from
all the paths connecting them, at multiple scales.

  * •

We experimentally validated that UGT achieves comparable expressive power to
the third-order Weisfeiler-Lehman isomorphism test (3d-WL) in distinguishing
non-isomorphic graph pairs.

##  2 Related Work

This section discusses how the existing studies attempted to overcome the
limitations discussed in the previous section. Several existing graph
transformers attempt to reveal similarity of local structures between
neighbouring nodes using PEs. SAN [5] uses learnable PEs combined with the
attention mechanism to learn the local structures. Graphformer [15] adds node
degree to node features and integrates edge features using shortest-path
distance attention bias. GPS [14] uses random walk positional encoding (RWPE)
to find similar substructures for each target node. SAT [10] extracts $k$-hop
subgraph representations for each target node and uses GNNs to update the
target node representations. The existing models try to consider similarity of
local structures using substructures or paths surrounding nodes without
preserving distances between target and context nodes, although close
neighbours usually have higher significance than distant ones [16, 17]. The
main difference between the existing studies and UGT is that we describe and
consider substructures while preserving the distances using the structural
identity and distance. By describing the distances, the structural identity
goes beyond local structure descriptors to cover global structures, including
the roles of nodes.

Several existing studies attempted to capture global structural features.
WRGAT [18] aims to break the limitations of GNNs by using multiple relations
between nodes. GeoGCNs [19] employ multiple embedding methods, such as
Poincare and Struc2vec, and choose an optimal latent space that can preserve
the global structural features. While the GNN variants show the capability to
capture global information, they mostly overlook substructure similarity.
Several graph transformers, such as SAT [10] and Graphformer [15], attempt to
capture higher-order structures within $k$-hop distance [20]. However, the
higher-order structures are extracted within $k$-hop distance and omit long-
range dependencies since the $k$-hop distance is difficult to be extended to
graph diameters. Otherwise, UGT constructs virtual edges to connect distant
nodes with substructure similarity. By observing occurrences of substructures
all over the graph with virtual edges and co-occurrences of substructures
within $k$-hop distance with actual edges, UGT can learn both local and global
structures. Then, the transition probabilities are the medium for fusing the
two features.

##  3 Unified Graph Transformer Networks

This section introduces a novel graph transformer model, UGT, which can learn
local and global structural features and integrate them into a unified vector
representation. We first introduce how to sample context nodes and then
describe the design of UGT in detail. Finally, we introduce self-supervised
learning and fine-tuning tasks. The overall architecture of UGT is described
in Figure 2.

Figure 2: The overall architecture of UGT. UGT is composed of main blocks,
including sampling context nodes, building modules $I$, $d$, and $m$, and pre-
training blocks. The learned representations then could be used for various
downstream tasks.

###  3.1 Sampling Context Nodes

Figure 3: An example of UGT sampling strategy. We sample context nodes within
$k$-hop neighbourhoods and virtual connections between distant nodes with
structural similarity.

Given a graph $G=(V,E)$ with node set $V$ and edge set $E$, we aim to sample
the context node $v_{j}$ of each target node $v_{i}\in V$. The context node
$v_{j}$ could be sampled if the distance from $v_{i}$ to $v_{j}$ within
$k$-hop, or both two nodes $v_{i}$ and $v_{j}$ are structurally similar.
Formally, for each target node $v_{i}$, the set of neighbours of $v_{i}$ can
be defined as:

$\displaystyle{N}_{{i}}$ $\displaystyle=$ $\displaystyle N^{(k)}_{{i}}\cup
N^{(st)}_{i},$ (1)

where $N^{(k)}_{{i}}$ indicates the set of neighbours of $v_{i}$ within
$k$-hop distance, and $N^{(st)}_{i}$ refers to the set of nodes that are
structurally similar to $v_{i}$. Figure 3 presents a simplified graph that
contains a target node ‘1’ and its context. For global sampling, we construct
virtual edges between any two nodes if they are structurally similar. For
example, nodes ‘1’ and ‘12’ are structurally similar with the same degree of
five and connected to two triangles. Note that we only consider similarity
based on the graph structure without using the node feature. Let
$I_{k}({v_{i}})$ denotes the set of an ordered degree sequence of $v_{i}$ in
$1$ to $k$-hop. Note that $I_{0}({v_{i}})$ is the degree of $v_{i}$. By
comparing the ordered degree sequences between $v_{i}$ and $v_{j}$, we can
impose a score to measure structural distance. Formally, the structural
distance and score between any two nodes $v_{i}$ and $v_{j}$ in a graph could
be defined as:

$\displaystyle s_{k}={{{f}_{k}}\left(I_{k}({v_{i}}),I_{k}({v_{j}})\right)},$
(2) $\displaystyle
S\left(v_{i},v_{j}\right)={\exp\left({-\sqrt{s_{k}}}\right)},$ (3)

where $f_{k}(\cdot,\cdot)$ is the structural distance between two sequences.
Similar to Struc2vec [21], we use dynamic time warping (DTW) to measure the
distance between two ordered degree sequences. In most real-world networks,
however, the degree distribution is highly asymmetric and shows a long tail
distribution. To boost the connections between nodes with high degrees, we
introduce another score:

$\displaystyle
S\left(v_{i},v_{j}\right)={\exp\left({-\sqrt{s_{k}}}\right)}+{\exp\left({-\frac{1}{{}^{\sqrt{\left({{d}_{v_{i}}}+{{d}_{v_{j}}}\right)}}}}\right)},$
(4)

where $d_{v_{i}}$ presents the degree of $v_{i}$. Accordingly, two nodes with
a high score are structurally similar, and if they have high degrees together,
they are closer in the latent space.

###  3.2 Learning Unified Representations of Graphs

####  3.2.1 Input representation

Given a graph $G$, the node feature $x_{i}\in R^{d_{0}\times 1}$ of node
$v_{i}$ is mapped via a linear projection to $d$-dimensional hidden feature
$\hat{x}_{i}^{0}$, as:

$\displaystyle\hat{x}_{i}^{0}$ $\displaystyle=$
$\displaystyle{{W}_{0}}{{x}_{i}}+{{b}_{0}},$ (5)

where ${W}_{0}\in R^{d\times d_{0}}$ and ${b}_{0}\in R^{d}$ are the parameters
of the linear projection, $d_{0}$ refers to the original feature of $v_{i}$.
Since we aim to make UGT can learn the global positional information context
for each node in the whole graph, we add a linearly transformed positional
embedding $\lambda_{i}$ of dim $k$ to node features, as:

$\displaystyle\hat{\lambda}_{i}$ $\displaystyle=$
$\displaystyle{{W}_{1}}{{\lambda}_{i}}+{{b}_{1}},$ (6)
$\displaystyle{h}_{i}^{0}$ $\displaystyle=$
$\displaystyle\hat{x}_{i}^{0}+\hat{\lambda}_{i},$ (7)

where ${W}_{1}\in R^{d\times k}$ and ${b}_{1}\in R^{d}$. Note that the
positional embeddings are pre-calculated and added only for the first time,
and we use Eigenvectors of the graph Laplacian matrix. Furthermore, we
randomly flip $\lambda$ during training to allow UGT to capture sign
invariance.

####  3.2.2 Global structural self-attention

We now propose a self-attention bias to encode local and global structural
information. Since we aim to capture context nodes within a $k$-hop distance
and distant nodes, the self-attention needs to understand the distance between
node pairs in terms of $k$-hop distance and the structural distance. Formally,
we define a self-attention between $v_{i}$ and $v_{j}$ for head $k$ at layer
$l$ as:

$\displaystyle\alpha_{ij}^{k,l}=\frac{\left({{Q}^{k,l}}h_{i}^{l}\right)\cdot\left({{K}^{k,l}}h_{j}^{l}\right)}{\sqrt{d_{k}}}+D_{ij}^{k,l}+M_{ij}^{k,l},$
(8)

where ${Q}^{k,l}$, ${K}^{k,l}$ $\in R^{d_{k}\times d}$, $k=1$ to $H$ refers to
the number of attention heads, $h_{i}$ and $h_{j}$ are the features of node
$v_{i}$ and $v_{j}$, respectively. $D_{ij}^{k,l}$ and $M_{ij}^{k,l}$ $\in
R^{d_{k}\times d}$ are linear transformed structural distance $d_{ij}$ and
transition probability $m_{ij}$ between two nodes $v_{i}$ and $v_{j}$,
respectively. We now introduce strategies to construct $d$ and $m$.

We define the structural identity of each target node based on hierarchical
role-based information, including minimum, maximum, mean, and standard
deviation degrees up to $k$-hop distance context of each node $v_{i}$.
Formally, the structural identity of node $v_{i}$ and the structural distance
could be defined as:

$\displaystyle{I}_{i}=\\{\ {{d}_{v_{i}}},T_{1},T_{2},\cdots,T_{k}\\},$ (9)
$\displaystyle{{d}_{ij}}=f\left(\left[{{\left\|I_{i}^{(q)}-I_{j}^{(q)}\right\|}_{2}}\right]^{-1}\right),$
(10)

where $d_{v_{i}}$ denotes the degree of node $v_{i}$,
$T_{k}=\\{{{\min}_{k}},{\max}_{k},{{\mu}_{k}},{{\delta}_{k}}\\}$ denotes the
set of minimum, maximum, mean, and standard deviation values of the node
degrees at $k$-th hop distance, $I_{i}^{(q)}$ refers to the $q$-th element of
$I_{i}$, and $f$ refers to a linearly transformed structural distance.

While structural distance can benefit the model by finding distant nodes with
structural similarity, it cannot capture paths between the two nodes. To fill
this gap, we present the transition probability-based distance $m$, which is
the awareness of connectivity between any two nodes from a probabilistic
perspective. In this way, UGT could capture both the local and global
structural information, leading to the power to capture any path between
nodes. We define the transition probability distance $m$ from $v_{i}$ to
$v_{j}$ as:

$\displaystyle
m_{ij}=f\left({A}_{ij}^{1},{A}_{ij}^{2},\cdots,{A}_{ij}^{p}\right),$ (11)

where ${A}_{ij}^{p}$ refers to the transition probability from $v_{i}$ to
$v_{j}$ at $p$-step, and $f$ refers to a linearly transformed transition
probability.

####  3.2.3 Graph transformer layers

The outputs of self-attention are then concatenated into one vector
representation followed by a linear transformation. The node features of
$v_{i}$ are updated at layer $l$ as:

$\hat{h}_{i}^{l+1}=O_{h}^{l}\underset{k=1}{\overset{H}{\mathop{\mathbin{\|}}}}\,\left(\sum\limits_{v_{j}\in
N({{v}_{i}})}{\tilde{\alpha}_{ij}^{k,l}{{V}^{k,l}}h_{j}^{l}}\right),$ (12)

where ${\tilde{\alpha}_{ij}^{k,l}}=\text{softmax}_{j}({{\alpha}_{ij}^{k,l}})$,
${Q}^{k,l}$, ${K}^{k,l}$,${V}^{k,l}$ $\in R^{d_{k}\times d}$, ${O}^{l}_{h}\in
R^{d\times d}$, and $\mathbin{\|}$ refers to concatenation. The outputs then
are passed to feed-forward networks (FFN) along with residual connections and
layer normalization:

$\displaystyle\hat{h}_{i}^{l+1}=\text{LN}\left(h_{i}^{l}+\hat{h}_{i}^{l+1}\right),$
(13)
$\displaystyle\hat{\hat{h}}_{i}^{l+1}=W_{2}^{l}\text{ReLU}\left(W_{1}^{l}\hat{h}_{i}^{l+1}\right),$
(14) $\displaystyle
h_{i}^{l+1}=\text{LN}\left(\hat{h}_{i}^{l+1}+\hat{\hat{h}}_{i}^{l+1}\right),$
(15)

where $W_{1}^{l}\in R^{2d\times d}$ and $W_{2}^{l}\in R^{d\times 2d}$ are
learnable parameters, and LN refers to layer normalization.

Since the structural identity of nodes could sufficiently extract information
around nodes based on degree information, it could benefit to distinguish non-
isomorphic substructures. Therefore, we add a linearly transformed structural
identity to each transformer layer, as given by Equation (12):

$\displaystyle\hat{h}_{i}^{l+1}=f\left(I_{i}^{l}\right)+\hat{h}_{i}^{l+1}.$
(16)

We believe that with a number of adequate transformer layers, UGT could map
different substructures into different representations.

###  3.3 Self-supervised Learning Tasks

We now present self-supervised learning tasks that could train UGT on pretext
tasks to extract graph structure without using any label information. Our
objective is to learn representations that could capture both local and global
structures between any nodes as long as they are structurally similar. As
mentioned earlier, we aim to preserve relational structure information in
$p$-step transition probability, combining local and global structures. The
learned representations could then be used for solving different downstream
tasks.

Given a connectivity between a target node $v_{i}$ and a context node $v_{j}$,
we aim to maximize the transition probability of paths connecting $v_{i}$ and
$v_{j}$ against the probability of other pairs not from the graph. Similar to
Grarep and Glove, we employ noise contrastive estimation, introduced by [22].
The loss function for the transition probability matrix of $v_{i}$ at $p$-step
could be defined as:

$\displaystyle{{L}^{p}_{1}}({{v}_{i}})=\left(\sum\limits_{{{v}_{j}}}{{P_{k}}\left({{v}_{j}}|{{v}_{i}}\right)\log\sigma\left({{z}_{i}}{{z}_{j}}\right)}\right)+\lambda\mathbb{E},$
(17)

where
$\mathbb{E}={{E}_{{{v}_{k}}\sim{P_{k}}(V)}}\left[\log\sigma\left(-{{z}_{i}}{{z}_{k}}\right)\right]$,
$v_{k}$ refers to nodes obtained from negative sampling. We then assume the
noise follows a uniform distribution, and this lead to a new transition matrix
on a log scale that represents precisely the global relation information
between any two nodes at step $p$:

$\displaystyle
A^{\prime(p)}=\log\left(\frac{A_{i,j}^{(p)}}{\sum\nolimits_{t}{A_{t,j}^{(p)}}}\right)-\log\left(\frac{\left|N_{s}\right|}{\left|V\right|}\right),$
(18)

where $A^{\prime(p)}$ is the log scale probability matrix at step $p$ that we
aim to preserve, and $N_{s}$ refers to the set of negative samples. Finally,
the loss function for structure preservation at step $p$ can be computed as:

$\displaystyle
L^{p}_{1}=\left\|{A^{{}^{\prime}(p)}-Z^{(p)}})\right\|_{F}^{2},$ (19)

where ${{{Z}}^{(p)}}$ is the score matrix that could be built by computing the
cosine similarity between vector embeddings.

Since node feature information could benefit several downstream tasks, UGT
should also learn a reconstruction of node feature information. We define the
node raw feature reconstruction-based loss term as:

$\displaystyle{L_{2}}=\frac{1}{\left|V\right|}\sum\nolimits_{{{v}_{i}}\in
V}{{{\left\|{{x}_{i}}-{{{\hat{x}}}_{i}}\right\|}_{2}}},$ (20)

where $x_{i}$ refers to the raw feature of node $v_{i}$, and
$\hat{x_{i}}=FFN(z_{i})$. We train the model in multi-task learning with the
two losses, and the losses are linearly combined as:

$\displaystyle L=\alpha\sum\limits_{p}{L^{p}_{1}}+\beta L_{2},$ (21)

where $\alpha$ and $\beta$ are hyper-parameters.

###  3.4 Fine-tuning Tasks

To apply UGT to downstream tasks, the learned representations are then passed
directly to solve downstream tasks. In this study, we present three downstream
tasks, including node clustering, node classification, and graph-level
classification. For the node clustering task, we used modularity as the loss
function as with [23]. For the node classification, a representation of node
$v_{i}$ from the transformer layers was passed to fully-connected (FC) layers
to get the classification output $y_{i}$ as:

$\displaystyle y_{i}=W_{1}\text{ ReLU}\left(W_{2}h^{l}_{i}\right),$ (22)

where $W_{1}\in R^{d\times C}$ and $W_{2}\in R^{d\times d}$ are weight
matrixes, and $C$ refers to the number of classes. In the graph-level
classification, we employed average pooling to obtain graph features and
likewise used FC layers to obtain the prediction output.

##  4 Experiments

We conducted experiments to evaluate UGT versus GNN variants and graph
transformer models for three tasks: node clustering, node classification, and
graph-level classification. We also analyzed the power of our model by
assessing UGT on isomorphism testing.

###  4.1 Experimental Settings

####  4.1.1 Datasets

For the node-level tasks, we used eleven publicly available datasets, which
are grouped into three different domains, including Air-traffic networks
(e.g., Brazil, Europe, and USA) [21], Webpage networks (e.g., Chameleon,
Squirrel, Actor, Cornell, Texas, and Wisconsin) [19], and Citation networks
(e.g., Cora and Citeseer) [24]. We used four publicly available datasets for
the graph classification task, including Enzymes, Proteins, NCI1, and NCI9
from TUDataset [25]. Furthermore, we used Graph8c and nine Strongly Regular
Graphs datasets (SRGs), which contain 1d-WL and 3d-WL equivalent graph pairs,
respectively, for isomorphism testing [26].

####  4.1.2 Baselines

The GNN variants included GCN [1], GCNII [27], GIN [28], GAT [6], GATv2 [7],
SAGE [29], Geom-S [19], WRGAT [18], and DeeperGCN [30]. Furthermore, we
compared UGT against recent transformers, including GT [2], SAN [5], SAT [10],
GPS [14], ANS-GT [31], and Graphormer [15]. For isomorphism testing, we
compare UGT against recent powerful models, i.e., ChebNet [32], and GNNML3
[26].

####  4.1.3 Implementation Details

We conducted each experiment ten times by randomly sampling training,
validation, and testing sets of size 80%, 10%, and 10%, respectively. The
results written in the tables were measured with means and standard deviation
on the testing set over the ten cases. The experiments were done in two
servers with four NVIDIA RTX A5000 GPUs (24GB RAM/GPU). The hyper-parameters
were tuned on the validation sets for each task and dataset. For fair
comparisons with the baselines, we conducted a search for the number of layers
and the hidden dimension size with ranges of {2, 4, 8} and {32, 64, 128} with
every model, respectively.

Brazil Europe USA Chameleon Squirrel Film Cornell Texas Wisconsin Cora
Citeseer C$\downarrow$ Q$\uparrow$ C$\downarrow$ Q$\uparrow$ C$\downarrow$
Q$\uparrow$ C$\downarrow$ Q$\uparrow$ C$\downarrow$ Q$\uparrow$ C$\downarrow$
Q$\uparrow$ C$\downarrow$ Q$\uparrow$ C$\downarrow$ Q$\uparrow$ C$\downarrow$
Q$\uparrow$ C$\downarrow$ Q$\uparrow$ C$\downarrow$ Q$\uparrow$ GCN 0.71 -0.01
0.71 -0.07 0.47 0.16 0.46 0.25 0.27 0.73 0.59 0.11 0.75 0.0 0.61 0.16 0.59
0.18 0.16 0.68 0.17 0.63 GCNII 0.74 -0.02 0.76 -0.03 0.59 0.11 0.56 0.2 0.72
0.27 0.66 0.06 0.78 -0.05 0.8 -0.03 0.64 0.09 0.42 0.33 0.32 0.37 GIN 0.73
-0.03 0.01 0.01 0.08 0.1 0.47 0.13 0.75 0.27 0.59 0.04 0.81 -0.1 0.9 -0.13
0.73 -0.02 0.2 0.63 0.24 0.56 GAT 0.68 -0.01 0.74 -0.05 0.69 0.03 0.66 0.09
0.77 0.25 0.71 0.02 0.85 -0.1 0.88 -0.18 0.82 -0.07 0.17 0.66 0.25 0.55 GATv2
0.54 -0.01 0.61 -0.06 0.22 0.17 0.72 0.06 0.77 0.2 0.7 0.06 0.8 -0.08 0.88
-0.13 0.72 -0.01 0.17 0.66 0.21 0.59 SAGE 0.55 -0.02 0.76 -0.06 0.68 0.04 0.77
0.03 0.75 0.25 0.72 0.0 0.9 -0.16 0.94 -0.15 0.83 -0.07 0.18 0.65 0.23 0.57
WRGAT 0.74 -0.01 0.78 -0.05 0.71 0.03 0.64 0.09 0.69 0.34 0.67 -0.0 0.86 -0.15
0.92 -0.17 0.83 -0.12 0.23 0.6 0.28 0.53 WRGCN 0.72 -0.0 0.79 -0.05 0.7 0.03
0.64 0.1 0.68 0.34 0.67 0.0 0.88 -0.16 0.92 -0.17 0.79 -0.07 0.24 0.59 0.27
0.53 DeeperGCN 0.46 0.0 0.55 -0.06 0.5 0.1 0.75 0.04 0.78 0.26 0.75 0.03 0.8
-0.07 0.88 -0.15 0.75 -0.05 0.18 0.65 0.23 0.57 GT 0.61 -0.01 0.6 -0.05 0.31
0.12 0.78 0.02 0.78 0.22 0.8 -0.01 0.87 -0.15 0.92 -0.19 0.81 -0.11 0.19 0.64
0.26 0.54 SAN 0.6 -0.04 0.66 -0.06 0.42 0.15 0.71 0.01 0.58 0.42 0.42 0.01
0.89 -0.15 0.88 -0.12 0.79 -0.04 0.23 0.61 0.25 0.55 GPS 0.7 0.03 0.7 -0.01
0.64 -0.0 0.7 0.08 0.81 0.2 0.65 0.0 0.8 -0.09 0.73 -0.05 0.78 -0.05 0.38 0.46
0.5 0.29 SAT 0.43 0.01 0.75 -0.06 0.72 -0.0 0.8 -0.08 0.64 0.35 0.73 -0.0 0.85
-0.07 0.7 0.02 0.81 -0.04 0.58 0.01 0.39 0.12 UGT(K-mean) 0.68 0.0 0.78 -0.05
0.13 0.22 0.11 0.66 0.24 0.74 0.44 0.32 0.52 0.1 0.8 -0.1 0.67 0.03 0.10 0.71
0.15 0.66 UGT 0.51 0.22 0.51 0.20 0.34 0.30 0.11 0.64 0.21 0.39 0.28 0.50 0.28
0.47 0.33 0.46 0.27 0.52 0.09 0.76 0.04 0.78

Table 1: The performance on node clustering task in terms of conductance (C)
and modularity (Q) measurements. The top three are emphasized by first,
second, and third.

###  4.2 Performance Analysis

####  4.2.1 Evaluation on node clustering

We first conducted an experiment on eleven benchmark datasets for the node
clustering task. For the baselines, we trained the models in a supervised
manner with a classification task. Then, we used learned representations as
inputs for the K-means clustering algorithm. For our UGT model, we conducted
clustering using both K-means and an end-to-end manner. Table 1 shows the
performance of node clustering in terms of conductance (C) and modularity (Q)
measurements [33]. (1) UGT outperformed all baselines that ignore either local
or global structures, e.g., GCN, WRGAT, and GT. Remarkably, the performance of
our learned representations combined with K-mean also showed significant
performance over the benchmark datasets. We suppose that as UGT could learn
local and global structure and graph density, the representations could
estimate the dense relations between nodes in communities. (2) Most of the
recent graph transformers, such as SAN, SAT, Graphormer, and GPS, did not
capture the density and connectivity information, only concerning higher-order
neighbourhoods. This indicates that learning higher-order substructures could
not help the model handle local relation density and graph partitioning.

Brazil Europe USA Chameleon Squirrel Film Cornell Texas Wisconsin Cora
Citeseer GCN 41.54$\pm$9.73 37.94$\pm$2.99 50.42$\pm$5.07 66.25 $\pm$1.77
50.92 $\pm$1.02 28.15$\pm$1.37 55.55$\pm$9.29 48.89$\pm$6.47 58.40$\pm$6.49
87.33$\pm$1.71 72.05$\pm$1.22 GCNII 24.35$\pm$3.62 22.78$\pm$5.37
28.29$\pm$4.19 60.07$\pm$2.44 28.30$\pm$1.63 26.03$\pm$0.77 50.92$\pm$6.54
75.00$\pm$2.26 60.67$\pm$2.49 84.22$\pm$0.74 70.22$\pm$2.25 GIN 50.76$\pm$7.84
42.56$\pm$9.67 50.75$\pm$9.77 66.87$\pm$2.72 40.53$\pm$1.16 23.21$\pm$1.13
36.66$\pm$7.53 34.44$\pm$13.78 44.00$\pm$12.64 77.25$\pm$3.35 64.09$\pm$1.95
GAT 58.46$\pm$7.84 54.35$\pm$3.40 46.38$\pm$11.41 67.84$\pm$0.8 64.76$\pm$0.72
26.21$\pm$1.44 57.77$\pm$6.66 68.88$\pm$9.02 60.00$\pm$11.02 84.29$\pm$2.02
73.43$\pm$1.21 GATv2 69.23$\pm$8.42 57.94$\pm$4.75 61.84$\pm$ 3.38
62.20$\pm$2.11 50.80$\pm$3.01 25.73$\pm$2.11 56.66$\pm$8.88 63.33$\pm$9.68
55.20$\pm$4.66 85.77$\pm$1.27 72.95$\pm$1.87 SAGE 66.15$\pm$7.84
60.16$\pm$4.59 60.00$\pm$6.60 67.92$\pm$3.83 47.42$\pm$1.07 32.57$\pm$0.91
77.77$\pm$6.08 82.22$\pm$10.18 81.60$\pm$6.49 87.77$\pm$1.49 74.69$\pm$1.89
Geom-S - - - 58.94$\pm$0.54 36.55$\pm$0.14 30.46$\pm$0.32 54.05$\pm$0.00
64.86$\pm$0.00 58.82$\pm$0.00 83.40$\pm$0.10 73.50$\pm$0.07 WRGAT
55.38$\pm$3.07 51.28$\pm$3.62 56.97$\pm$3.54 51.80$\pm$2.03 32.96$\pm$1.44
35.78$\pm$1.84 74.44$\pm$15.55 75.55$\pm$6.66 84.80$\pm$5.30 74.59$\pm$0.50
73.01$\pm$1.71 DeeperGCN 69.23$\pm$4.86 59.49$\pm$6.76 61.17$\pm$4.99
57.53$\pm$2.82 34.96$\pm$1.04 31.68$\pm$1.50 63.33$\pm$10.30 76.67$\pm$8.16
72.80$\pm$8.54 86.59$\pm$0.85 73.61$\pm$0.62 GT 63.07$\pm$11.30 62.56
$\pm$9.53 64.37 $\pm$ 2.67 65.55$\pm$2.83 49.50$\pm$ 1.59 34.55$\pm$ 1.90
70.37$\pm$ 5.24 84.44$\pm$ 7.37 82.40$\pm$5.98 86.17$\pm$ 1.96 71.58$\pm$ 2.38
SAN 61.53$\pm$10.87 63.24$\pm$5.26 35.29$\pm$3.43 64.02$\pm$2.60
46.28$\pm$2.09 32.14$\pm$0.27 79.62$\pm$2.61 85.18$\pm$9.44 82.66$\pm$1.88
84.81$\pm$1.98 73.99$\pm$2.69 GPS 52.31$\pm$8.97 46.00$\pm$5.15 42.52$\pm$3.85
42.54$\pm$3.87 34.42$\pm$2.14 35.37$\pm$2.20 45.05$\pm$7.75 30.63$\pm$1.27
62.00$\pm$9.09 62.12$\pm$1.00 51.18$\pm$3.35 SAT 66.15 $\pm$6.15
57.43$\pm$6.19 65.04$\pm$4.06 49.69$\pm$3.81 40.08$\pm$0.76 31.61$\pm$1.37
41.67$\pm$6.33 34.44$\pm$4.15 57.60$\pm$9.32 79.63$\pm$2.69 63.98$\pm$2.41
ANS-GT 46.80$\pm$5.30 31.00$\pm$3.89 46.20$\pm$3.31 54.60$\pm$1.02
35.80$\pm$1.17 39.80$\pm$0.75 59.80$\pm$2.71 63.80$\pm$5.04 85.20$\pm$2.71
88.00$\pm$0.63 75.00$\pm$0.89 Graphormer 42.00$\pm$3.2 29.80$\pm$1.17
45.80$\pm$3.66 53.80$\pm$1.17 34.60$\pm$0.80 39.20$\pm$0.75 66.20$\pm$1.47
74.00$\pm$4.86 84.00$\pm$1.26 86.40$\pm$0.49 74.60$\pm$0.80 UGT w/o PT
76.92$\pm$4.71 44.94 $\pm$4.86 64.71$\pm$3.19 60.33 $\pm$3.91 50.43 $\pm$0.81
23.63 $\pm$1.03 52.78 $\pm$6.51 63.89 $\pm$3.93 64.0 $\pm$7.21 74.63 $\pm$2.93
57.41 $\pm$1.25 UGT 80.00 $\pm$5.23 56.92 $\pm$6.36 66.22$\pm$4.55 69.78
$\pm$3.21 66.96 $\pm$2.49 36.84$\pm$0.62 70.0 $\pm$4.44 86.67 $\pm$8.31 81.6
$\pm$8.24 88.74$\pm$0.6 76.08$\pm$2.5

Table 2: The performance on node classification task (accuracy). The top three
are emphasized by first, second, and third.

####  4.2.2 Evaluation on node classification

We show the results of the baselines and UGT on the node classification task
in Table 2. (1) Our UGT model with pre-training outperformed baseline models
that overlook the long-term dependencies in most datasets, i.e., GCN, GAT,
GATv2, and GT. We assume that the virtual edges allowed UGT to capture the
long-term dependencies between structurally similar nodes, which have
analogous roles and are significant for analyzing heterophily graphs. (2) UGT
showed significant improvements in homophily graphs, i.e., Cora and Citeseer,
in which nodes with the same labels tend to be adjacent. This indicates that
UGT could not only capture local connectivity but also distinguish similar
substructures (roles).

Enzymes Proteins NCI1 NCI109 GCN 18.24$\pm$2.05 59.23$\pm$0.62 68.24$\pm$2.38
67.09 $\pm$ 3.43 SAGE 21.46$\pm$4.32 62.79$\pm$1.38 64.36$\pm$2.82
64.47$\pm$2.41 GCNII 31.46$\pm$5.31 62.53$\pm$2.41 63.27$\pm$1.38
68.12$\pm$0.54 GIN 33.64$\pm$3.52 64.14 $\pm$ 2.05 66.72$\pm$5.32
68.44$\pm$1.89 GATv2 25.17$\pm$4.42 66.85$\pm$ 2.43 61.58$\pm$1.43
64.51$\pm$2.36 DeeperGCN 25.36$\pm$4.79 61.24$\pm$3.59 55.32$\pm$3.28
55.1$\pm$2.18 GT 41.67$\pm$6.67 77.25$\pm$3.83 69.77$\pm$1.4 69.66$\pm$0.06
SAN 22.50$\pm$0.83 68.47$\pm$0.9 59.31$\pm$3.47 57.3$\pm$8.20 SAT
50.85$\pm$3.66 62.91$\pm$0.76 54.99$\pm$0.26 56.04$\pm$0.06 GPS 62.71$\pm$8.64
53.75$\pm$6.20 79.44$\pm$0.65 76.27$\pm$0.95 UGT 67.22$\pm$3.92 80.12
$\pm$0.32 77.55 $\pm$0.16 75.45$\pm$1.26

Table 3: The performance on graph classification task in terms of accuracy.
The top three are emphasized by first, second, and third.

####  4.2.3 Evaluation on graph-level classification

Table 3 shows the performance of the models on graph-level classification. For
fair comparisons, we did not use the pre-training in the graph-level tasks,
since graphs in the benchmarks have small scales. UGT exhibited competitive
results compared to GNN variants and graph transformers, showing the
effectiveness in capturing the global structure information in the whole
graphs. This indicates that UGT could capture the connectivity in each
individual substructure and then map unique substructures to different
representations.

Table 4:  The number of graph pairs that are undistinguished in Graph8c and
nine strongly regular graphs (SRGs). Since graphs in each benchmark dataset
are non-isomorphic, an ideal graph representation model should not find any
similar pairs. The top two are emphasized by first and second.

GRAPH8C SR16622 SR251256 SR261034 SR281264 SR291467 SR351668 SR351899 SR361446
SR401224 $\\#$ Graphs 11,117 2 15 10 4 41 3854 227 180 28 $\\#$ Comparisions
61.8M 1 105 45 6 820 7,424,731 25,651 16,110 378 Types 1-d WL 3-d WL GCN 4,196
1 105 45 6 820 7,424,731 25,651 16,110 378 GA 1,827 1 105 45 6 820 7,424,731
25,651 16,110 378 GIN 559 1 105 45 6 820 7,424,731 25,651 16,110 378 ChebNet
44 1 105 45 6 820 7,424,731 25,651 16,110 378 PPGN 0 1 105 45 6 820 7,424,731
25,651 16,110 378 GNNML3 0 1 105 45 6 820 7,424,731 25,651 16,110 378 GT 0 0 0
0 0 0 19 0 0 2 GT w/o $\lambda$ 6,157 1 105 45 6 820 7,424,731 25,651 16,110
378 SAN 5,819 1 105 45 6 820 7,424,731 25,651 16,110 378 SAT 286,360 0 91 36 3
742 6,973,038 23,899 15,066 351 GPS 0 1 105 45 6 820 7,424,731 25,651 16,110
378 GPS w/o RWPE 1,517 1 105 45 6 820 7,424,731 25,651 16,110 378 UGT w/o
$\lambda$ 355 1 105 45 6 820 7,424,731 25,651 16,110 378 UGT w/o I 36,857.0 1
105 45 6 820 7,424,731 25,651 16,110 378 UGT 0 0 0 0 0 0 0 0 0 0

####  4.2.4 Evaluation on the power of model

a Distinguishing non-isomorphic graphs with $\lambda$.

b Distinguishing non-isomorphic graphs with RWPE.

Figure 4: Distinguishing a Decalin graph (Left) and Bi-cyclopentyl graph
(Right).

We conducted experiments to evaluate UGT on isomorphism testing for 1d-WL and
3d-WL benchmark datasets. Table 4 shows the performance on Graph8c and nine
SRGs datasets. (1) UGT could perfectly distinguish non-isomorphic graph pairs
in Graph8c and SRGs. Most of the GNN variants could also distinguish graphs in
Graph8c. However, as GNNs’ capabilities are limited to the 1d-WL test, they
failed to distinguish the graph pairs in SRGs. (2) The structural identity was
effective to distinguish 1d-WL graph pairs in Graph8c, which is more powerful
than $\epsilon$ of GIN. Since UGT determines substructures rooted in each node
through structural identity ($I$), the learned representations thus could
capture the surrounding substructures of each node. (3) To investigate the
reasons why UGT is more powerful than baselines, we examined differences
between Laplacian Eigenvectors and RWPE. Figure 4a presents how Laplacian
Eigenvectors ($\lambda$) can distinguish a decalin and bi-cyclopentyl graph
pair by assigning initial PEs to nodes ‘1’ and ‘3’. At the first iteration,
the input representation of UGT can be represented as
${h}_{i}^{0}=\hat{x}_{i}^{0}+{{W}_{1}}{{\lambda}_{i}}+{{b}_{1}}$ and assigns
different representations from the first iteration. Thus, the output
embeddings with structural identity
($h_{i}^{l+1}=FFN\left(I_{i}^{l}\right)+O_{h}^{l}(\cdot)$) ensure
distinguishability to nodes. In contrast, RWPE needed a random walk with a
length of five to distinguish the non-isomorphic graph pairs in Figure 4b. We
suppose that in the SRGs, nodes are connected densely, which causes RWPE to
fail to capture the substructures and connectivity in such graphs.

###  4.3 Ablation studies

To verify different modules in our model contribute to the overall
performance, we conduct ablation studies on three benchmark datasets,
including Cora, Brazil, and Cornell. Table 5 shows the results of
contributions of the five models: virtual edges, I, $\lambda$, d, and m. We
have the following observations: 1)  Constructing virtual edges two components
I and $\lambda$ could bring better performance in terms of accuracy for node
classification tasks. We argue that as the Cora dataset is homophily graph,
our model could understand the local and global structural information, thanks
to the I and $\lambda$ components. Furthermore, UGT can also capture the long-
term dependencies in Brazil and Cornell as they are heterophily graphs. This
indicates that our model could effectively combine the virtual edges and two
components. 2)  Without virtual edges, our model can show good performance on
clustering tasks. We argue that constructing virtual edges may make UGT a bit
confusing the connectivity in graphs since it can affect actual edges. 4),
Considering the structural distance and transition probability could
contribute to the highest performance of the model in terms of accuracy for
the Cora dataset. This is because the model could learn the local structural
similarity and long-term dependencies even if we enable the virtual edges. For
understanding local connectivity, the transition probability (m) is beneficial
compared to structural distance (d). We argue that the transition probability
could distinguish different connectivity between pair nodes in graphs,
eventually helping the model to capture the density and the graph
partitioning.

Virtual Edges I $\lambda$ Cora Brazil Cornell D M Cora Brazil Cornell acc Q C
acc Q C acc Q C acc Q C acc Q C acc Q C $\checkmark$ - - 86.87 0.71 0.14 76.92
0.06 0.49 50.0 0.02 0.62 - - 85.00 0.70 0.15 76.92 0.03 0.30 50.0 0.45 0.31
$\checkmark$ - 87.06 0.73 0.12 76.92 0.09 0.52 66.67 0.21 0.43 $\checkmark$ -
86.87 0.68 0.18 84.62 0.07 0.51 55.56 0.09 0.42 - $\checkmark$ 86.50 0.72 0.13
69.23 -0.01 0.59 44.44 0.02 0.18 - $\checkmark$ 86.69 0.74 0.11 84.62 0.07
0.46 61.11 0.43 0.34 $\checkmark$ $\checkmark$ 87.80 0.70 0.15 84.62 0.03 0.20
55.56 0.24 0.29 $\checkmark$ $\checkmark$ 88.35 0.72 0.12 76.92 0.07 0.37 50.0
0.11 0.40 ✗ - - 86.32 0.70 0.15 69.23 -0.02 0.46 61.11 0.01 0.44 - - 87.61
0.73 0.12 76.92 0.02 0.13 55.56 0.55 0.23 $\checkmark$ - 87.24 0.72 0.13 84.62
0.07 0.37 66.67 0.19 0.29 $\checkmark$ - 86.50 0.73 0.12 84.62 0.03 0.20 50.0
0.17 0.45 - $\checkmark$ 87.43 0.75 0.10 76.92 0.00 0.65 50.0 0.49 0.26 -
$\checkmark$ 86.32 0.73 0.12 76.92 0 0 50.0 -0.16 0.66 $\checkmark$
$\checkmark$ 85.40 0.72 0.13 84.62 0.06 0.52 55.56 0.0 0.0 $\checkmark$
$\checkmark$ 87.25 0.74 0.11 76.92 0.03 0.16 55.56 0.44 0.25

Table 5: Study the effect of virtual edges, I, $\lambda$, D, and M while
keeping the other components in our model fixed. The different consequences
are marked and highlighted by colours.

###  4.4 Sensitivity Analysis

$k$-hop distance.

Virtual edges over actual edges.

Figure 5: The performance of node classification task according to the
sampling range of context nodes up to $k$-hop distance (Above) and the
percentage of virtual edges over actual edges (Below).

We performed sensitivity analyses on the range of $k$-hop neighbourhoods and
the ratio of virtual edges to real edges, as shown in Figure 5. (1) As $k$
(i.e., the range of neighbourhood sampling) increased, the performance of node
classification showed increasing tendencies across the three datasets.
However, the trends were different for homophily and heterophily graphs. For
homophily graphs (e.g., Cora), increasing $k$ up to the 3-hop range affected
model performance, but not beyond. In contrast, for heterophily and sparse
graphs, increasing the number of neighbourhoods provided more benefit. (2)
Adding virtual edges could benefit more than increasing the number of $k$-hop
neighbourhoods for the Cora dataset. We suppose that virtual edges could
assist UGT in finding more distant nodes with structural similarity, and long-
range dependencies could be effective for analyzing both homophily and
heterophily graphs.

##  5 Conclusion and future work

This study proposes a novel graph transformer model, UGT, to learn local and
global structural features and integrate them into a unified representation.
UGT captures long-range dependencies between nodes with similar roles using
structural similarity-based sampling, discovers local connectivity using
$k$-hop neighbourhoods and structural identity, and unifies them by learning
transition probabilities between nodes that imply both aspects. Experimental
results on various downstream tasks and datasets show that UGT outperforms or
is comparable to state-of-the-art GNNs and graph transformers. Since our
sampling technique uses the structural similarity between nodes in the whole
graph, it can cause computational complexity in large graphs. Our further
research aims to reduce the computational complexity of role-based sampling by
applying graph coarsening.

## Acknowledgments

This work was supported in part by the National Research Foundation of Korea
(NRF) grant funded by the Korea government (MSIT) (No. 2022R1F1A1065516 and
No. 2022K1A3A1A79089461) (O.-J.L.) and in part by the Research Fund, 2022 of
The Catholic University of Korea (M-2023-B0002-00088) (O.-J.L.).

## References

  * [1] Thomas N. Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In Proceedings of the 5th International Conference on Learning Representations (ICLR 2017), Toulon, France, Apr 2017. OpenReview.net.
  * [2] Vijay Prakash Dwivedi and Xavier Bresson.  A generalization of transformer networks to graphs.  In Proceedings of the AAAI Workshop on Deep Learning on Graphs (AAAI 2021), 8–9 Feb 2021.
  * [3] Van Thuy Hoang , Hyeon-Ju Jeon , Eun-Soon You , Yoewon Yoon , Sungyeop Jung , and O-Joun Lee .  Graph representation learning and its applications: A survey.  Sensors, 23(8), 2023.
  * [4] Hyeon-Ju Jeon, Min-Woo Choi, and O-Joun Lee.  Day-ahead hourly solar irradiance forecasting based on multi-attributed spatio-temporal graph convolutional network.  Sensors, 22(19):7179, 2022.
  * [5] Devin Kreuzer, Dominique Beaini, William L. Hamilton, Vincent Létourneau, and Prudencio Tossou.  Rethinking graph transformers with spectral attention.  In Proceedings of the 34th Annual Conference on Neural Information Processing Systems (NeurIPS 2021), pages 21618–21629, Virtual Event, Dec 2021.
  * [6] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph attention networks.  In Proceedings of the 6th International Conference on Learning Representations (ICLR 2018), Vancouver, BC, Canada, Apr 2018. OpenReview.net.
  * [7] Shaked Brody, Uri Alon, and Eran Yahav.  How attentive are graph attention networks?  In Proceedings of the 10th International Conference on Learning Representations (ICLR 2022), Virtual Event, Apr 2022. OpenReview.net.
  * [8] O-Joun Lee and Jason J. Jung.  Story embedding: Learning distributed representations of stories based on character networks (extended abstract).  In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), pages 5070–5074, Yokohama, Japan, Jan 2020. ijcai.org.
  * [9] O-Joun Lee, Jason J. Jung, and Jin-Taek Kim.  Learning hierarchical representations of stories by using multi-layered structures in narrative multimedia.  Sensors, 20(7):1978, 2020.
  * [10] Dexiong Chen, Leslie O’Bray, and Karsten M. Borgwardt.  Structure-aware transformer for graph representation learning.  In International Conference on Machine Learning (ICML 2022), volume 162 of Proceedings of Machine Learning Research, pages 3469–3489, Baltimore, Maryland, USA, 17–23 Jul 2022. PMLR.
  * [11] O-Joun Lee and Jason J. Jung.  Story embedding: Learning distributed representations of stories based on character networks.  Artificial Intelligence, 281:103235, 2020.
  * [12] Hyeon-Ju Jeon, Gyu-Sik Choi, Se-Young Cho, Hanbin Lee, Hee Yeon Ko, Jason J Jung, O-Joun Lee, and Myeong-Yeon Yi.  Learning contextual representations of citations via graph transformer.  In Proceedings of the 2nd International Conference on Human-centered Artificial Intelligence (Computing4Human 2021), Da Nang, Vietnam, Oct 2021.
  * [13] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson.  Graph neural networks with learnable structural and positional representations.  In Proceedings of the 10th International Conference on Learning Representations (ICLR 2022), Virtual Event, 25–29 Apr 2022. OpenReview.net.
  * [14] Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini.  Recipe for a general, powerful, scalable graph transformer.  In Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS 2022), 2022.
  * [15] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu.  Do transformers really perform badly for graph representation?  In Proceedings of the 35th Conference on Neural Information Processing Systems (NeurIPS 2021), pages 28877–28888, Virtual Event, Dec 2021\.
  * [16] O-Joun Lee, Seungha Hong, and Jin-Taek Kim.  Interinstitutional research team formation based on bibliographic network embedding.  Mobile Information Systems, 2021:6629520:1–6629520:12, 2021.
  * [17] O-Joun Lee, Hyeon-Ju Jeon, and Jason J. Jung.  Learning multi-resolution representations of research patterns in bibliographic networks.  Journal of Informetrics, 15(1):101126, 2021.
  * [18] Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma.  Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns.  In Proceedings of the 27th Conference on Knowledge Discovery and Data Mining (KDD 2021), pages 1541–1551, Virtual Event, Aug 2021. ACM.
  * [19] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang.  Geom-gcn: Geometric graph convolutional networks.  In Proceedings of the 8th International Conference on Learning Representation (ICLR 2020), Addis Ababa, Ethiopia, 26-30 Apr 2020. OpenReview.net.
  * [20] Thanh Sang Nguyen, Jooho Lee, Van Thuy Hoang, O Lee, et al.  Connector 0.5: A unified framework for graph representation learning.  arXiv preprint arXiv:2304.13195, 2023.
  * [21] Leonardo Filipe Rodrigues Ribeiro, Pedro H. P. Saverese, and Daniel R. Figueiredo.  _struc2vec_ : Learning node representations from structural identity.  In Proceedings of the 23rd International Conference on Knowledge Discovery and Data Mining (KDD 2017), pages 385–394, Halifax, NS, Canada, Aug 2017. ACM.
  * [22] Michael Gutmann and Aapo Hyvärinen.  Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics.  Journal of Machine Learning Research, 13:307–361, 2012.
  * [23] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller.  Graph clustering with graph neural networks.  Journal of Machine Learning Research, 24:127:1–127:21, 2023.
  * [24] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad.  Collective classification in network data.  AI Magazine, 29(3):93–106, 2008.
  * [25] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann.  Tudataset: A collection of benchmark datasets for learning with graphs.  In Proceedings of the ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020.
  * [26] Muhammet Balcilar, Pierre Héroux, Benoit Gaüzère, Pascal Vasseur, Sébastien Adam, and Paul Honeine.  Breaking the limits of message passing graph neural networks.  In Proceedings of the 38th International Conference on Machine Learning (ICML 2021), volume 139 of Proceedings of Machine Learning Research, pages 599–608, Virtual Event, 18–24 Jul 2021. PMLR.
  * [27] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li.  Simple and deep graph convolutional networks.  In Proceedings of the 37th International Conference on Machine Learning (ICML 2020), volume 119 of Proceedings of Machine Learning Research, pages 1725–1735, Virtual Event, 13-18 Jul 2020. PMLR.
  * [28] 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 (ICLR 2019), New Orleans, LA, USA, May 2019. OpenReview.net.
  * [29] William L. Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NeurIPS 2017), pages 1024–1034, Long Beach, CA, USA, Dec 2017.
  * [30] Guohao Li, Chenxin Xiong, Ali K. Thabet, and Bernard Ghanem.  Deepergcn: All you need to train deeper gcns.  CoRR, abs/2006.07739, 2020.
  * [31] Zaixi Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee.  Hierarchical graph transformer with adaptive node sampling.  In Proceedings of the 36th Annual Conference on Neural Information Processing Systems (NeurIPS 2022), New Orleans, Louisiana, 28th Nov- 9th Dec 2022.
  * [32] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  In Proceedings of the 29th Annual Conference on Neural Information Processing Systems (NeurIPS 2016), pages 3837–3845, Barcelona, Spain, 5–10 Dec 2016.
  * [33] Jaewon Yang and Jure Leskovec.  Defining and evaluating network communities based on ground-truth.  Knowledge and Information Systems, 42(1):181–213, 2015.


key

#  $\mathsf{FROG}$: Forward-Secure Post-Quantum Signature

Attila A. Yavuz  University of South Florida
Tampa, Florida, USA
<EMAIL_ADDRESS>Rouzbeh Behnia  University of South Florida
Sarasota, Florida, USA
<EMAIL_ADDRESS>
###### Abstract

Forward-secure signatures guarantee that the signatures generated before the
compromise of private key remain secure, and therefore offer an enhanced
compromise-resiliency for real-life applications such as digital forensics,
audit logs, and financial systems. However, the vast majority of state-of-the-
art forward-secure signatures rely on conventional intractability assumptions
and therefore are not secure against quantum computers. Hash-based signatures
(HBS) (e.g., XMSS) can offer forward-secure post-quantum security. However,
they are efficient only for a pre-defined number of messages to be signed and
incur high key generation overhead, highly expensive signing, and large
signature sizes for an increasing number of messages. It is an open-problem to
develop quantum-safe forward-secure signatures that are efficient and
practical with a signing capability scalable to their security parameters.

In this work, we propose a new series of post-quantum signatures that we call
$\mathsf{FROG}$ (Forward-secuRe pOst-quantum siGnature). Unlike HBS
alternatives, $\mathsf{FROG}$ can achieve highly computational efficient
signatures with sub-linear key/signature sizes and (practically) unbounded
signing capability. This is achieved by transforming suitable post-quantum
signatures into forward-secure setting via MMM generic constructions.
Specifically, we investigated the transformation of prominent post-quantum
secure signatures such as Dilithium, WOTS and BLISS with MMM variants. Our
experiments indicate that $\mathsf{FROG}$ outperforms XMSS for the vast
majority (if not all for large number of messages) performance metrics. We
also discuss one-time variants of these base signature schemes that can push
the performance of $\mathsf{FROG}$ to the edge. Overall, $\mathsf{FROG}$ shows
a better performance than the existing alternatives with forward-security, and
therefore is an ideal alternative for the standardization efforts for forward-
secure post-quantum signatures.

###### Index Terms:

Authentication, digital signatures, forward-security, post-quantum-security,
digital forensics.

##  I Introduction

Forward-security ensures that the past messages are protected even if the
current secret key is exposed. Forward-secure digital signature schemes (e.g.,
[1]) are key-evolving signatures that periodically update the private key and
delete the previous key. This prevents an adversary who compromises the system
from forging the previously computed digital signatures on past messages,
since their corresponding keys were erased. Forward-secure digital signatures
enhance the breach and compromise-resiliency of digital signatures. Hence,
they play a critical role in many real-life applications such as secure audit
logging, digital forensics, financial applications, public key certificate
infrastructures, and many others.

###  I-A The State of the Art and Its Limitations

Several forward-secure digital signatures have been proposed with different
performance trade-offs (e.g., [2, 3, 4]). There is generally a trade-off
between signature and public key sizes, update frequency and computational
efficiency, and number of items that can be signed for some variants. Forward-
secure signatures generally are computationally costly compared to standard
signatures, and have larger signature and/or key sizes. Some of the forward-
secure signatures offer extended properties such as aggregation [5, 6, 7, 8,
9], untrusted update [10, 11] , selective verification [12], and group
signatures [13]. These features might increase the efficiency of the schemes
in one front, while incurring other cost and constraints in an another (e.g.,
more compact signatures but larger public keys and/or more computational
overhead). There are also generic forward-security frameworks (e.g., [14, 15])
that can transform any standard signature into a forward-secure signature.
However, these generic transformations might lead inefficient results (e.g.
[14]), and specially tailored constructions might outperform them with careful
designs (e.g. [16]) for some performance metrics.

The vast majority of the existing forward secure signatures rely on
conventional intractability problems (e.g., factorization, discrete logarithm
problem (DLP), elliptic curve (ECDLP)). However, it is well-known that the
conventional signature schemes are vulnerable to the emerging quantum
computers, and therefore, NIST has initiated the second round of
standardizations for post-quantum
cryptography111https://csrc.nist.gov/projects/post-quantum-cryptography/. The
existing post-quantum digital signatures, compared to their conventional
counterparts, are known to be costly in terms of communication, computation
and energy consumption. Forward secure version of such constructions are
expected to be even costlier than the original schemes.

The forward-security for post-quantum signatures have been mainly investigated
for hash-based digital signatures (HBS) [17]. To our best knowledge, the other
NIST standardization candidates have not yet been explored extensively from
the forward-security perspective. For instance, it is clear that a generic
forward-secure transformation (e.g., [14, 15]) for many of these candidates
yield highly inefficient constructions due to their very large signature
and/or public key sizes. HBS (e.g., Lamporr [17]) are among the first
signature schemes with a post-quantum security. There are number of efficient
one-time HBS (e.g., [18, 19, 20, 21]) but they can only sign one or a few
messages per key pair. Recently, a NIST candidate (SPHINCS [22]) addressed
this limitation with a stateless design, albeit suffering from large signature
sizes (e.g., 41 KB).

Forward-secure signatures are by design stateful. Hence, to our knowledge, at
this point, the HBSs such as XMSS [23] and LMS [24, 25] are the most efficient
forward-secure post-quantum secure alternatives. These schemes are usually
efficient only for small to moderate number of messages to be signed. However,
once the total number of messages to be signed increases, the computational
overhead, and especially the cost of key generation, grows significantly. Both
of these schemes rely on hierarchical variants (e.g., HSS-LMS) to handle
signing capabilities over $t>2^{40}$. (we refer them as Hierarchical HBS
(HHBS)). In any cases, HHBSs generally require $t$ to be pre-defined, and
their key/signature generation overhead and signature sizes grow extremely
large for a big $t$ . There is a need for post-quantum forward-secure
signatures that are efficient, practical and can scale for large number of
messages to be signed.

###  I-B Objectives and Desirable Properties

The goal of this work is to create a series of post-quantum forward-secure
signatures that achieve highly efficient key and signature generation while
maintaining sub-linear signature, private key and constant public key sizes.
We aim that our schemes should be at least competitive or outperform existing
alternatives for small/moderate $t$ values (for some performance metrics),
while significantly outperform them when $t$ grows for the all performance
metrics. We outline some of the desirable properties of $\mathsf{FROG}$.

  * •

Efficient Key Generation : For $t=2^{64}$, the key generation of
$\mathsf{FROG}$, instantiated with the lattice-based signature in [26] is
almost $2200\times$ faster than the most efficient key generation instance of
XMSS-MT variant for key generation (with 12 layers) with the maximum of
$2^{60}$ signature generation capability. This difference significantly grows
for XMSS-MT variants with lower number of sub-trees (e.g., 3 or 6).

  * •

Efficient Signature Generation : The signature generation of $\mathsf{FROG}$
is two signature generation plus three key generation overhead of the
underlying signature scheme along with a constant number of hash calls. This
cost is again independent from both the total number of messages to be signed
or number of messages signed so far, making $\mathsf{FROG}$ signing magnitudes
of times more efficient than XMSS-MT. For example, for $t=2^{64}$, the
lattice-based instantiation of $\mathsf{FROG}$ based on [26] (with AVX
optimization) is $\approx 15\times$ faster than most efficient XMSS-MT variant
for signature generation (with 12 layers). The hash-based instantiation of
$\mathsf{FROG}$ based on [27] is $\approx 8\times$ faster than the most
efficient XMSS-MT variant (with 12 layers).

  * •

Efficient Signature Verification: The signature verification of
$\mathsf{FROG}$(with basic MMM instantiation) is two signature verification
plus a constant number of hash calls. For example, for $t=2^{64~}$, the
lattice-based instantiation of $\mathsf{FROG}$ based on [26] is $\approx
17\times$ faster than most efficient XMSS-MT variant for verification (with 3
layers). The hash-based instantiation of $\mathsf{FROG}$ based on [27] is
$\approx 8\times$ faster than the most efficient XMSS-MT variant (with 3
layers).

  * •

Compact Public Key: The public key of $\mathsf{FROG}$ is just a hash value (
half size of XMSS-MT variants), and therefore is optimal.

  * •

Competitive Signature Sizes: The signature sizes in some $\mathsf{FROG}$
variants (e.g., hash-based) could slightly larger than those variants in XMSS-
MT with lower number of layers (e.g. $t=2^{60}$ with three layers), however,
usually such variants of XMSS-MT have a very costly key generation and
signature generation algorithms. For example, for instantiation of
$\mathsf{FROG}$ with Dilithium [26], the signature size is $13,624$ bytes
where in XMSS-MT with $12$ layers, signature size is $27,688$ bytes. The
signature size becomes more favorable for XMSS-MT with lower layers. We
investigated another variant of $\mathsf{FROG}$, called
$\mathsf{FROG}^{*}$(iterative product composition of MMM) that enjoys shorter
signatures and private keys but with a more expensive key generation and
signature verification. Remark that in many cases, $\mathsf{FROG}^{*}$ is
still significantly more computationally efficient than XMSS-MT variants.

Limitations: As aforementioned, our constructions ($\mathsf{FROG}$ and
$\mathsf{FROG}^{*}$) outperform XMSS-MT variants in almost all the metrics.
However, our schemes suffer from larger private key sizes. For instance, for
the hash-based instantiations of $\mathsf{FROG}$, the private key size could
be as large as $715,840$ bytes, which is about $18\times$ larger than the
largest private key size for the instantiated XMSS-MT variants.
$\mathsf{FROG}^{*}$has a smaller private sizes but with more computational
overhead. However, we think that this is a very favorable trade-off since
unlike public key size, the private key size does not incur any (online)
communication overhead.

##  II Preliminaries

Operators $||$ and $|x|{=\log x}$ denote the concatenation and the bit length
of variable $x$, respectively and $\log$ denotes $\log_{2}$.

######  Definition 1.

A signature scheme consists of three algorithms
$\mathsf{SGN}{}=({\mathsf{Kg}{},\mathsf{Sig}{},\mathsf{Ver}{}})$ defined as
follows.

  * –

$(\mathit{sk}{},\mathit{PK}{})\leftarrow\mathsf{SGN.Kg}{}(1^{\kappa})$: Given
the security parameter $\kappa$, it outputs the private and public key pair
$(\mathit{sk}{},\mathit{PK}{})$.

  * –

$\sigma\leftarrow\mathsf{SGN.Sig}{}(m,\mathit{sk}{})$: Given the message $m$
and the signer’s private key $\mathit{sk}{}$, it outputs the signature
$\sigma$.

  * –

$b\leftarrow\mathsf{SGN.Ver}{}(m,\sigma,\mathit{PK}{})$: Given a message-
signature pair ($m,\sigma$), and public key $\mathit{PK}{}$, outputs
$b\leftarrow{}\\{0,1\\}$

In ordinary digital signatures, if the private key of the signer is
compromised, all the signatures that are generated by the signer (past and
future) become forgeable. In forward secure signatures, the previously
computed signatures remain unforgeable even if the current private key of the
signer is compromised.

###  II-A Malkin, Micciancio and Miner (MMM) Scheme

$\mathsf{MMM}$ [15] is a series of constructions to transform standard digital
signatures $\mathsf{SGN}{}$ to forward secure signature. $\mathsf{MMM}$ is
composed of the sum (referred to as $\bigoplus$) and product (referred to as
$\bigotimes$) composition algorithms. In the sum composition, given a digital
signature $\mathsf{SGN}{}$ with $t$ forward-secure signing capability, the sum
composition can generate $2t$ signatures in total. For instance, given a
standard one-time signature, by iteratively applying sum composition $\log t$
times, one can obtain a forward-secure signature with $t$ signing capability.
In the product composition, given a digital signature $\mathsf{SGN}{}$ with
$t$ forward-secure signing capability, the product composition can generate
$t^{2}$ signatures in total.

The main $\mathsf{MMM}$ construction has an upper tree and multiple lower
trees, which are created with the iterative execution of sum composition and
are linked with the upper tree with the product composition. Lower trees are
generated on the go with increasing levels of height. This minimizes the key
generation/update cost and makes the overhead of $\mathsf{MMM}$ depend on
"messages signed so far" but not the total number of time periods available.
Thus, the lower trees are created as needed on the go. $\mathsf{MMM}$
increases the levels in each iteration to sign more messages with a slight
increase in cost (generation of a higher tree). Overall, in $\mathsf{MMM}$,
the costs are either logarithmic or constant with respect to $t<T$ (i.e., $t$
is the total number of messages signed so far, and $T$ is the maximum number
of signatures) and the size of the $\mathit{PK}{}$ is a small-constant. We
refer curious reader to [15] for the details.

Another interesting composition in [15] is the iterated product composition.
In this construction, a new forward secure scheme is achieved by applying the
sum composition once and then iterate the product composition to this two-time
signature to get $2^{2^{\log\log t}}$ and get $t$ time signature scheme.

##  III The Proposed Scheme FROG

We instantiate the generic constructions given in [15] with the existing
efficient lattice-based [26, 28] and hash-based [27] post-quantum signatures
to create a series new post-quantum forward-secure signature we call
$\mathsf{FROG}$ (Forward-secuRe pOst-quantum siGnature) .

###  III-A Design Rationale

In our design, we aim to achieve high computation efficiency while keeping
sub-linear signature/key sizes, all with signing capabilities scalable to the
security parameter (e.g., $t=2^{\kappa}$). However, following NIST guidelines,
we set $t=2^{64}$ for $\mathsf{FROG}$.

(i) The sub-linear key sizes in forward-secure schemes are generally achieved
by a tree structure. For instance, in XMSS-MT, given a pre-determined (fixed)
$t=2^{h}$ ($h$ is the height of the tree) number of messages to be signed, $d$
XMSS sub-trees are computed during key generation, each of height $l$, such
that $h=l\cdot d$. A Merkle-tree is constructed on top these sub-trees to
compute the final public key that can verify the generated signatures, which
include the authentication path from leaves to the root. Note that the tree
structure in XMSS-MT is rigid and $t$ is pre-determined. The signature sizes,
signature generation and especially key generation overhead grow substantially
for larger $t$ values, and if it reaches $t$, the system must be re-
initialized. HSS-LMS also follows a similar strategy. In our design, we depart
from HHBS approaches, but instead rely on $\mathsf{MMM}$ [15] that generates
hierarchical trees as needed and on-the-fly. In particular, we harness the sum
composition iteratively and in conjunction with product composition to obtain
practical performance results. However, as mentioned before, $\mathsf{MMM}$
generic framework might lead to inefficient forward-secure schemes if the
underlying primitive and composition methods are not selected carefully.

(ii) We observe that on-the-fly tree construction requires generating a fresh
private/public key pair per update, and therefore, the key generation overhead
must be minimized. That is, the signing overhead of on-the-fly constructions
depend on the key generation of the underlying signature primitive as much its
signing overhead. We identified that Dilithium [26] and BLISS [28] offer
efficient key generation and signing, making them appropriate choices for the
iterated sum and product compositions. For the sake of providing a more
leveled comparison with HHBS schemes, we also instantiated schemes based on a
relatively recent one-time hash-based signature in [27]. In iterated sum and
product compositions, we create a new private/key pair for each item to be
used, and then another two pairs for the future tree elements in an amortized
manner.

(iii) New public keys must be relayed to the verifier for each update, and
therefore both the signature and public key sizes must be minimized. We
selected BLISS [28] due to its parameters sizes which offers a more compact
size than the existing post-quantum signature alternatives. Our approach also
shed a light of how existing NIST post-quantum signature candidates perform
under some generic forward-secure transformations. Our observation indicates
that only the candidates whose total signature plus public key size is
relatively small might yield efficient results. In this regard, the lattice-
based candidates such as Dilithium [29] and Falcon [30] seem only
alternatives. We will later discuss our future plan to devise a one-time
lattice based signature similar to [31] and with the optimizations proposed in
[26] and the potential performance gains from such construction.

###  III-B The Description of Main Instantiation

$\mathsf{FROG}$ is constructed by performing an iterative sum and product
composition of $\mathsf{SGN}$. Let $\bigoplus$ and $\bigotimes$ denote the
application of sum and product composition defined in Section II only once. We
denote composing two instantiations of $\mathsf{SGN}$ with the sum composition
as $\mathsf{SGN}{}\bigoplus\mathsf{SGN}{}$. Similarly,
$\mathsf{SGN}{}\bigotimes\mathsf{SGN}{}$ denotes two instantiations of a
signature scheme with the sum composition. $\mathsf{SGN}{}^{\bigoplus}_{K}$
means an iterative composition of $\mathsf{SGN}$ with itself $K$ times. Recall
that $1\leq t\leq 2^{\kappa}-1$ denotes the total number of signatures signed
so far. For example, in XMSS-MT, $1\leq t\leq K<<2^{\kappa}-1$, whereas in
$\mathsf{FROG}$ $t$ can approach to $2^{\kappa}$. We can express the
$\mathsf{FROG}$ as follows:

$\mathsf{SGN}{}_{\log
t}^{\bigoplus}\bigotimes\\{\mathsf{SGN}{}_{i}^{\bigoplus}\\}_{i=0}^{t}$

$\mathsf{MMM}$ has an upper-tree and multiple lower-trees, which are
constructed on-the-fly as needed:

(i) We first create a forward-secure signature scheme with $\log t$ signing
capability by iterating $\mathsf{SGN}{}_{\log t}^{\bigoplus}$ via sum
composition. These private/public key pairs are the leaves of the upper-tree,
and are used to certify the public keys of the signatures that will be used to
verify the data items in the lower-trees. (ii) There will be multiple lower-
trees that will be created as new data items to be signed arrive. Each lower-
tree $1\leq i\leq t$ will be a new forward-secure iterative sum composition
$\mathsf{\mathsf{SGN}{}}{}_{i}^{\bigoplus}$ that can sign $2^{i}$ data items.
(iii) The leaves of upper-tree and the lower-tree are connected with a product
composition. That is, once the leaves (i.e., key pairs) of
$\mathsf{\mathsf{SGN}{}}{}_{i-1}^{\bigoplus}$ are depleted, we create a new
lower-tree $\mathsf{\mathsf{SGN}{}}{}_{i}^{\bigoplus}$ and compose it with the
corresponding leave of the upper-tree by calling the product composition.
(iii) We adopt the amortized update strategy to ensure that transition from
one lower-tree to the next one does not incur heavy key generation overhead.
In each update operation for $\mathsf{\mathsf{SGN}{}}{}_{i}^{\bigoplus}$, we
also generate two key pairs (the leaves) for the next tree $i+1$. Hence, once
the key pairs for $i$’th lower-tree are depleted, the keys for new tree will
be ready, and heavy (bulk) key generation is not needed. This approach enables
a uniform update efficiency and is essential to handle large lower-tree sizes.
However, it requires storing initial keys for the next lower-tree, and
therefore increases the private key size. This overhead only grows with $t$ as
$O(\kappa\cdot\log t^{2})$, and therefore is space-efficient. For small-number
of messages to be signed, one can omit amortization and perform batch update
only for new lower-trees to be generated.

###  III-C Alternative Instantiations

(i) As aforementioned, one can use different signature schemes (either one-
time or polynomially bounded) to be used in the construction. However, careful
consideration needs to be taken in order to ensure that the resulting forward-
secure scheme will be efficient. For instance, one can imagine the use of
W-OTS variants [20, 21] to offer different performance trade-offs. In W-OTS,
the length of hash-chain $w$ poses a trade-off between the signature/public
key sizes and computational overhead. We have investigated different $w$
values and signature/public key sizes for W-OTS instantiated with
$\mathsf{MMM}$. In order to have comparable signature sizes with
$\mathsf{FROG}$, $w$ value must be relatively large (e.g. $>$400), and this
makes the key generation and signing of W-OTS rather expensive for
$\kappa=100-110$. It might be possible that W-OTS variants offer desirable
trade-offs for different $\kappa$ and some applications might prefer a hash-
based signature as a base scheme as opposed to a lattice-based constructs.
Hence, we capture the possibility of any future OTS that has smaller signature
and/or public key sizes that may rely on a different building blocks.

(ii-iii) We consider hybrid approaches, wherein the upper tree is replaced by
a (H)HBS and the lower-tree is generated with iterative constructions as
described in the main scheme. This may lead an efficient constructions as
(H)HBS (e.g., LMS [25]) is efficient for small-fixed number messages to be
signed, and the upper-tree harbors $\kappa$ key pairs at most. Another
alternative is to compute a hash-chain for any selected signature, and place
$\kappa$ public keys as a part of the master public key. This approach makes
the master public key large, but in return, it makes $\mathsf{MMM}$ signature
size much smaller as the hash chain elements replace the leaves of upper-tree,
and only the signature is transmitted but not the public keys.

TABLE I: Analytical performance of $\mathsf{FROG}$ and $\mathsf{FROG}^{*}$

Operation/Parameter |  | Computation/Storage Cost
---
MMM
$\mathsf{FROG.Kg}{}$ | $2\;\mathsf{SGN.Kg}{}$
$\mathsf{FROG.Sig}{}$ | $3\;\mathsf{SGN.Kg}{}+2\;\mathsf{SGN.Sig}{}+2H$
$\mathsf{FROG.Ver}{}$ | $2\;\mathsf{SGN.Ver}{}+(\log\kappa+\log t)H$
$\mathsf{FROG}{}_{\sigma}$ | $2|\sigma|+4|pk|+(\log\kappa+\log t+1)\cdot|H|$
$\mathsf{FROG}{}_{pk}$ | $|H|$
$\mathsf{FROG}{}_{sk}$ | $(2+\log\kappa)\cdot|sk|+6|pk|+4\cdot\log\kappa\cdot|H|+3\log t\cdot|H|+\kappa(\log t)^{2}$
Iterated Product Composition
$\mathsf{FROG}^{*}{}\mathsf{.Kg}{}$ | $\log\log t(5\;\mathsf{SGN.Kg}{}+\mathsf{SGN.Sig}{}+2\kappa\cdot H)$
$\mathsf{FROG}^{*}{}\mathsf{.Sig}{}$ | $3\;\mathsf{SGN.Kg}{}+2\;\mathsf{SGN.Sig}{}+(\kappa+1)\cdot H$
$\mathsf{FROG}^{*}{}\mathsf{.Ver}{}$ | $2(\log\log t\cdot\mathsf{SGN.Ver}{}+H)$
$\mathsf{FROG}^{*}{}_{\sigma}$ | $2|\sigma|+4|pk|+\kappa$
$\mathsf{FROG}^{*}{}_{pk}$ | $|H|$
$\mathsf{FROG}^{*}{}_{sk}$ | $\log\log t(2|sk|+6|pk|+4\kappa)+\kappa\cdot(\log t)^{2}+|sk|\cdot\log\kappa$

(iv) All of the above techniques receive significant computational benefit
from pre-computation methods with an expense of larger memory usage. For
example, in amortized update strategy, the generated keys are independent from
the messages, and therefore can be pre-computed and stored to be used later.
This accelerates signature generation as a small and constant number of key
update operations are performed beforehand. Parallel computing (e.g., GPUs,
FPGAs) can be used to accelerate the batch generation of pre-computed elements
and then fed into online computations.

###  III-D Security Argument from Base Scheme OTS and MMM

$\mathsf{FROG}$ is a transformation of efficient post-quantum one-time
signatures into multiple-time forward-secure signatures via MMM [15]. Hence,
the security of $\mathsf{FROG}$ directly follows from the sum and/or product
composition proofs of MMM in [15] provided that the base OTS schemes are
secure. We instantiate $\mathsf{FROG}$ with well-proven OTSs as outlined, and
therefore $\mathsf{FROG}$ schemes are as secure as MMM with its corresponding
base OTS schemes.

TABLE II: Experimental performance comparison of $\mathsf{FROG}$,
$\mathsf{FROG}^{*}$ and its counterparts on a commodity hardware

Scheme |  | Key Generation
---
Sign | Verify |  | Signature
---
(B)
| Public Key
---
(B)
| Private Key
---
(B)
XMSS-MT-SHA2_20/2_256 | $9,236,557,672$ | $24,554,349$ | $5,186,460$ | $4,963$ | $64$ | $5,998$
XMSS-MT-SHA2_20/4_256 | $729,631,517$ | $14,364,265$ | $10,188,082$ | $9,251$ | $64$ | $10,938$
XMSS-MT-SHA2_40/2_256 | $9,404,925,498,412$ | $26,628,986$ | $5,377,454$ | $5,605$ | $64$ | $9,600$
XMSS-MT-SHA2_60/3_256 | $14,234,635,667,761$ | $29,584,259$ | $7,619,770$ | $8,392$ | $64$ | $16,629$
XMSS-MT-SHA2_60/6_256 | $31,682,214,982$ | $31,391,553$ | $16,521,985$ | $14,824$ | $64$ | $24,507$
XMSS-MT-SHA2_60/12_256 | $1,946,231,536$ | $15,474,825$ | $33,375,298$ | $27,688$ | $64$ | $38,095$
MMM
$\mathsf{FROG}$-BLISS | $2,102,770$ | $12,517,153$ | $999,972$ | $7,054$ | $32$ | $80,076$
$\mathsf{FROG}$-Dilithium | $815,322$ | $5,544,419$ | $994,438$ | $13,624$ | $32$ | $634,176$
$\mathsf{FROG}$-Dilithium-AVX2 | $261,832$ | $1,369,462$ | $432,882$ | $13,624$ | $32$ | $634,176$
$\mathsf{FROG}$-WOTS+(SHA256) | $810,768$ | $2,031,100$ | $959,158$ | $27,872$ | $32$ | $715,840$
$\mathsf{FROG}$-WOTS+(SHAKE256) | $2,223,760$ | $5,559,400$ | $2,223,760$ | $27,872$ | $32$ | $715,840$
Iterated Product Composition
$\mathsf{FROG}^{*}$-BLISS | $62,828,244$ | $12,782,583$ | $5,113,672$ | $4,766$ | $32$ | $10,640$
$\mathsf{FROG}^{*}$-Dilithium | $28,642,638$ | $5,830,749$ | $5,080,468$ | $11,305$ | $32$ | $85,362$
$\mathsf{FROG}^{*}$-Dilithium-AVX2 | $10,306,122$ | $1,655,792$ | $1,711,132$ | $11,305$ | $32$ | $85,362$
$\mathsf{FROG}^{*}$-WOTS+(SHA256) | $17,804,064$ | $2,296,530$ | $4,868,788$ | $25,552$ | $32$ | $107,040$
$\mathsf{FROG}^{*}$-WOTS+(SHAKE256) | $40,027,680$ | $5,829,010$ | $13,346,740$ | $25,552$ | $32$ | $107,040$

  * •

All the above schemes, except for the instantiations of Dilithium, which
gives138-bits of security, provide 128-bit of security.

##  IV Performance Analysis

In this section, we compare the performance of different instantiations of
$\mathsf{FROG}$ with its counterparts. We also discuss the performance of some
of the selected alternative constructions described in Section III. As
mentioned, we also instantiated forward secure schemes using the iterated
product composition technique presented in [15]. For the sake of clarity we
denote instantions with this technique as $\mathsf{FROG}^{*}$.

###  IV-A Analytical Performance

We denote the signature, public key, and private key sizes of the base
signature scheme as $|\sigma|$, $|pk|$ and $|sk|$, respectively. We denote the
size of hash output as $|H|$. $\mathsf{FROG}{}_{\sigma}$,
$\mathsf{FROG}{}_{sk},\mathsf{FROG}{}_{pk}$ denote the signature, public key,
and private key sizes of $\mathsf{FROG}$. $H$ denotes a hash operation (also a
PRF call for the simplicity). $\mathsf{FROG.Sig}$ includes the amortized
update cost for a given composition. Following the guidelines given by
NIST222https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/faqs, we set
$t=2^{64}$. We present the analytical performance of our instantiations
($\mathsf{FROG}$ and $\mathsf{FROG}^{*}$) in Table I. As depicted,
$\mathsf{FROG}^{*}$ provides compact signature and private key sizes with the
cost of an increased computational overhead.

###  IV-B Experimental Performance Evaluation and Comparisons

We now elaborate the detail of our performance analysis and comparison with
XMSS-MT. We use the similar instantiations of XMSS-MT in [32]. We note that as
also highlighted in [32], the HSS-LMS is slightly more computationally
efficient than XMSS-MT, but we currently focus on XMSS-MT standard due to its
ease of test. We compare $\mathsf{FROG}$ and $\mathsf{FROG}^{*}$ and its
counterpart in terms of (i) private key, signature and public key sizes, and
(ii) key generation, signature generation, and signature verification. We run
our experiments on an i7 Kaby Lake equipped with a 2.9 GHz Quad-Core Intel
Core and 8 GB RAM.

We instantiated both $\mathsf{FROG}$ and $\mathsf{FROG}^{*}$with three
signature schemes: (i) Dilithium [26]: For this scheme we used the recommended
parameters set (see Table 2 in [26]) which provides 138-bits of security with
signature size and public key size of 2701 and 1472 bytes, respectively. We
used this scheme as it is one of the prominent lattice-based signature schemes
for NIST post-quantum standardization process. We use the reference
implementation and the AVX2 implementation (increases parallelism and
throughput in floating point SIMD calculations). (ii) BLISS [28]: For this
scheme we used BLISS-II parameters set (see Table 1 in [28]) which provides
128-bits of security. We note that we have selected BLISS due to its smaller
signature size. The signature and public key sizes in our selected variants
are $625$ and 875 bytes, respectively. BLISS using Gaussian Sampling to
produce a one-time masking term in the signature generation and therefore,
obtains a better signature size as compared to Dilithium [26], with a cost of
signature generation performance. Additionally we note that the Gaussian
Sampling technique is susceptible to side-channel attacks. We stress that each
BLISS private/public key pair is used only once (minimal side-channel attack
risk). We used the reference implementation for BLISS. (iii) WOTS+ [27]: We
used a variant with 128-bits of security with $w=4$ and $m=n=256$. We
instantiated it with both SHA256 and SHAKE256.

As depicted in Table II, we compared our instantiations with six different
instantiations of XMSS-MT-SHA256 with different parameters sizes, since, based
on our initial benchmark, XMSS-MT with SHA256 showed significantly better
performance than the one instantiated with SHAKE256. We adopted the
implementation from [33]. For XMSS-MT we considered $t=2^{20},2^{40},2^{60}$.
For $t=2^{20}$, we considered the number of subtrees to be $2$ and $4$. For
$t=2^{40}$, we considered the number of subtrees to be $2$. For $t=2^{60}$, we
considered the number of subtrees to be $3$ $6$, and $12$.

Following NIST’s recommendation, both $\mathsf{FROG}$ and $\mathsf{FROG}^{*}$
allow for up to $t=2^{64}$ signature generation. $\mathsf{FROG}$ performs
significantly better than all of XMSS-MT variants for key generation,
signature generation and signature verification. However, as a trade-off, it
has larger private key sizes and slightly larger signature sizes. However,
since private key is only stored on the signer’s machine, and does not affect
communication overhead. Our $\mathsf{FROG}^{*}$ variants provides better
signature and private key sizes, with the cost of added performance overhead
on all other algorithms. however, it is still shown to be more efficient than
all other XMSS-MT variants.

## Acknowledgment

The work of Attila A. Yavuz is supported by the NSF CAREER Award CNS-1917627
and an unrestricted gift via Cisco Research Award.

## References

  * [1] R. Anderson, “Two remarks on public-key cryptology, invited lecture,” Proceedings of the 4th ACM conference on Computer and Communications Security (CCS ’97), 1997.
  * [2] M. Bellare and S. Miner, “A forward-secure digital signature scheme,” in _Advances in Crpytology (CRYPTO ’99)_. Springer-Verlag, 1999, pp. 431–448.
  * [3] G. Itkis and L. Reyzin, “Forward-secure signatures with optimal signing and verifying,” in _Advances in Cryptology (CRYPTO ’01)_. Springer-Verlag, 2001, pp. 332–354.
  * [4] A. Kozlov and L. Reyzin, “Forward-secure signatures with fast key update,” in _Proc. of the 3rd International Conference on Security in Communication Networks (SCN ’02)_ , 2002.
  * [5] A. A. Yavuz and P. Ning, “BAF: An efficient publicly verifiable secure audit logging scheme for distributed systems,” in _Proceedings of 25th Annual Computer Security Applications Conference (ACSAC ’09)_ , 2009, pp. 219–228.
  * [6] A. A. Yavuz, P. Ning, and M. K. Reiter, “BAF and FI-BAF: Efficient and publicly verifiable cryptographic schemes for secure logging in resource-constrained systems,” _ACM Transaction on Information System Security_ , vol. 15, no. 2, 2012.
  * [7] D. Ma, “Practical forward secure sequential aggregate signatures,” in _Proceedings of the 3rd ACM symposium on Information, Computer and Communications Security (ASIACCS ’08)_. NY, USA: ACM, 2008, pp. 341–352.
  * [8] J. Kim and H. Oh, “Fas: Forward secure sequential aggregate signatures for secure logging,” _Information Sciences_ , vol. 471, pp. 115 – 131, 2019\.
  * [9] E. U. A. Seyitoglu, A. A. Yavuz, and M. O. Ozmen, “Compact and resilient cryptographic tools for digital forensics,” in _IEEE Conference on Communications and Network Security (CNS)_ , June 2020, pp. 1–9.
  * [10] X. Boyen, H. Shacham, E. Shen, and B. Waters, “Forward-secure signatures with untrusted update,” in _Proceedings of the 13th ACM conference on Computer and Communications Security (CCS ’06)_. New York, NY, USA: ACM, 2006, pp. 191–200.
  * [11] B. Libert, J. Quisquater, and M. Yung, “Forward-secure signatures in untrusted update environments: Efficient and generic constructions,” in _Proceedings of the 14th ACM conference on Computer and communications security (CCS ’07)_. ACM, pp. 266–275.
  * [12] G. Hartung, “Secure audit logs with verifiable excerpts,” in _Topics in Cryptology - CT-RSA 2016_ , K. Sako, Ed. Cham: Springer International Publishing, 2016, pp. 183–199.
  * [13] S. Ling, K. Nguyen, H. Wang, and Y. Xu, “Forward-secure group signatures from lattices,” in _Post-Quantum Cryptography_ , J. Ding and R. Steinwandt, Eds. Cham: Springer International Publishing, 2019, pp. 44–64.
  * [14] H. Krawczyk, “Simple forward-secure signatures from any signature scheme,” in _Proceedings of the 7th ACM conference on Computer and Communications Security, (CCS ’00)_. ACM, 2000, pp. 108–115.
  * [15] T. Malkin, D. Micciancio, and S. Miner, “Efficient generic forward-secure signatures with an unbounded number of time periods,” in _Advances in Cryptology - Eurocrypt 2002_ , ser. Lectture Notes in Computer Science, vol. 2332, IACR. Amsterdam, The Netherlands: Springer-Verlag, April 28-May 2 2002, pp. 400–417.
  * [16] M. Abdalla, F. Benhamouda, and D. Pointcheval, “On the tightness of forward-secure signature reductions,” _Journal of Cryptology_ , vol. 32, 02 2018.
  * [17] L. Lamport, “Constructing digital signatures from a one-way function,” Tech. Rep. CSL-98, October 1979.
  * [18] W. Neumann, “HORSE: An extension of an r-time signature scheme with fast signing and verification,” in _Information Technology: Coding and Computing, 2004. Proceedings. ITCC 2004. International Conference on_ , vol. 1, april 2004, pp. 129 – 134 Vol.1.
  * [19] L. Reyzin and N. Reyzin, “Better than BiBa: Short one-time signatures with fast signing and verifying,” in _Proceedings of the 7th Australian Conference on Information Security and Privacy (ACIPS ’02)_. Springer-Verlag, 2002, pp. 144–153.
  * [20] J. Buchmann, E. Dahmen, S. Ereth, A. Hülsing, and M. Rückert, “On the security of the winternitz one-time signature scheme,” in _Progress in Cryptology – AFRICACRYPT 2011_ , A. Nitaj and D. Pointcheval, Eds., 2011, pp. 363–378.
  * [21] A. Hülsing, “W-ots+ – shorter signatures for hash-based signature schemes,” in _Progress in Cryptology – AFRICACRYPT 2013_ , A. Youssef, A. Nitaj, and A. E. Hassanien, Eds., 2013, pp. 173–188.
  * [22] D. J. Bernstein, D. Hopwood, A. Hülsing, T. Lange, R. Niederhagen, L. Papachristodoulou, M. Schneider, P. Schwabe, and Z. Wilcox-O’Hearn, “SPHINCS: Practical stateless hash-based signatures,” in _Advances in Cryptology – EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer Berlin Heidelberg, April 2015, pp. 368–397.
  * [23] J. Buchmann, E. Dahmen, and A. Hülsing, “Xmss - a practical forward secure signature scheme based on minimal security assumptions,” in _Proceedings of the 4th International Conference on Post-Quantum Cryptography_ , ser. PQCrypto’11. Berlin, Heidelberg: Springer-Verlag, 2011, pp. 117–129.
  * [24] F. T. Leighton and S. Micali, “Large provably fast and secure digital signature schemes based on secure hash functions,” US Patent 5,432,852, 1195\. [Online]. Available: https://www.google.com/patents/US5432852
  * [25] D. McGrew, Curcio, and S. M., Fluhrer, “Hash-based signatures. internet-draft draft-mcgrew-hash-sigs-06,” RFC - Internet Engineering Task Force, 2017. [Online]. Available: https://datatracker.ietf.org/doc/html/draft-mcgrew-hash-sigs-06
  * [26] L. Ducas, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehle, “Crystals – dilithium: Digital signatures from module lattices,” Cryptology ePrint Archive, Report 2017/633, 2017, http://eprint.iacr.org/2017/633.
  * [27] A. Hülsing, “WOTS+ - shorter signatures for hash-based signature schemes,” _IACR Cryptol. ePrint Arch._ , vol. 2017, p. 965, 2017. [Online]. Available: http://eprint.iacr.org/2017/965
  * [28] L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky, “Lattice signatures and bimodal gaussians,” in _Advances in Cryptology – CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I_ , R. Canetti and J. A. Garay, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 40–56.
  * [29] L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé, “Crystals-dilithium: A lattice-based digital signature scheme,” _IACR Trans. Cryptogr. Hardw. Embed. Syst._ , vol. 2018, no. 1, pp. 238–268, 2018.
  * [30] P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang, “Falcon: Fast-fourier lattice-based compact signatures over ntru,” _Submission to the NIST’s post-quantum cryptography standardization process_ , 2018.
  * [31] V. Lyubashevsky and D. Micciancio, “Asymptotically efficient lattice-based digital signatures,” _J. Cryptology_ , vol. 31, no. 3, pp. 774–797, 2018\.
  * [32] P. Kampanakis and S. Fluhre, “Lms vs xmss: Comparion of two hash-based signature standards,” _IACR Cryptology ePrint Archive_ , vol. 349, 2017\. [Online]. Available: https://eprint.iacr.org/2017/349.pdf
  * [33] XMSS, “Xmss.” [Online]. Available: https://github.com/XMSS/xmss-reference.git