Masked Graph Autoencoder with Non-discrete Bandwidths

Ziwen Zhao

School of Computer Science and Technology
Huazhong University of Science and Technology

Yuhua Li
Corresponding author.

Yixiong Zou

School of Computer Science and Technology
Huazhong University of Science and Technology

Jiliang Tang

Michigan State University
East Lansing

Ruixuan Li

School of Computer Science and Technology
Huazhong University of Science and Technology

Masked graph autoencoders have emerged as a powerful graph self-supervised learning method that has yet to be fully explored. In this paper, we unveil that the existing discrete edge masking and binary link reconstruction strategies are insufficient to learn topologically informative representations, from the perspective of message propagation on graph neural networks. These limitations include blocking message flows, vulnerability to over-smoothness, and suboptimal neighborhood discriminability. Inspired by these understandings, we explore non-discrete edge masks, which are sampled from a continuous and dispersive probability distribution instead of the discrete Bernoulli distribution. These masks restrict the amount of output messages for each edge, referred to as “bandwidths”. We propose a novel, informative, and effective topological masked graph autoencoder using bandwidth masking and a layer-wise bandwidth prediction objective. We demonstrate its powerful graph topological learning ability both theoretically and empirically. Our proposed framework outperforms representative baselines in both self-supervised link prediction (improving the discrete edge reconstructors by at most 20%) and node classification on numerous datasets, solely with a structure-learning pretext. Our implementation is available at <https://github.com/Newiz430/Bandana>.

<concept_desc>Computing methodologies Unsupervised learning</concept_desc>
<concept_desc>Information systems Data mining</concept_desc>

[500]Computing methodologies Unsupervised learning
[500]Information systems Data mining

§ INTRODUCTION

Today, the demand for massive amounts of data in pre-training large models has reached an unprecedented level.
Self-supervised learning (SSL) has emerged as a powerful approach to uncovering underlying patterns in unannotated data by pre-training on some tailor-made tasks called pretexts <cit.>.
Graphs, unlike text and images,
possess non-Euclidean structures that are hard for humans to intuitively understand and lack well-annotated graph benchmark datasets due to the diversity of graph data and tasks.
Thus, SSL also plays a pivotal role in learning graph representations, especially in various web applications such as social recommendation <cit.>.

Contemporary graph SSL studies are mainly contrastive methods <cit.> that leverage metric learning between augmented data pairs.
In spite of this, they suffer from
the thorny problem of dimensional collapse. On the other hand, autoencoding methods
learn by reconstructing the input data from encoded representations. However, traditional graph autoencoders <cit.> fall short of modeling high-dimensional representation spaces, while variational autoencoders <cit.> require additional assumptions on data distributions.
In contrast, masked graph autoencoders, a novel framework for data reconstruction, enable the learning of high-dimensional representations without extra assumptions and show remarkable adaptability to graph data.
One type of masked graph autoencoder aims to reconstruct node features, referred to as FeatRecs <cit.>.
Another type, on which our work focuses, aims to reconstruct randomly masked links to learn graph topology, referred to as TopoRecs <cit.>.

In this work, we focus on the topological informativeness of traditional TopoRecs' representations, i.e. how well they embed graph topology into the latent representation space.
As illustrated in Figure <ref>(a), traditional TopoRecs rely on two key components:
(1) discrete edge masking, where binary edge masks are sampled from a discrete distribution, and (2) binary link reconstruction, which distinguishes the masked positive edges from negative ones.
Despite some prominent results <cit.> derive from these two strategies,
we argue that discrete random masking and binary link reconstruction lead to limited informativeness, both globally and locally (in Section <ref>).
(1) Globally, pathways for long-range information are likely to be stretched or blocked by indiscriminate masking,
leading to the vulnerability to over-smoothing.
(2) Locally,
discrete masking cannot provide fine-grained neighborhood discriminability, leading to suboptimal topological learning performance.

Discrete masks vs. the proposed bandwidths.

Present work.
To tackle the problems, a topologically informative non-discrete masking strategy is desired. We introduce a new perspective by considering the message propagation of a GNN analogously as the (transient) transmission between nodes in a telecommunication network. By randomly setting a limit for each connection link (edge) on the amount of messages transferred in one single propagation step, named the “bandwidth”, we manage to mask a portion of information through each edge, as shown in Figure <ref>(b). Bandwidths provide topological informativeness both globally and locally:
(1) the graph topology is kept intact during the training (Figure <ref>(c)), and long-range information can reach its destination unimpeded, which provides global informativeness.
(2) By sampling bandwidth values from a dispersive Boltzmann-Gibbs distribution, each node learns its neighborhood in a more fine-grained and discriminative way, which provides local informativeness. Accordingly, we propose a novel masked graph autoencoder with bandwidth prediction instead of link reconstruction. It is termed “Graph autoencoder aided by Bandwidths”,  in reverse. We showcase 's great topological informativeness both theoretically (Section <ref>) and empirically (Section <ref>) by conducting extensive experiments on numerous datasets.

We present the following main contributions:

* We unveil that discrete TopoRecs are insufficient to learn topologically informative representations. Globally, blocked message flows make the TopoRec vulnerable to the over-smoothing problem of deeper GNNs; locally, uniformized weight distribution results in the indiscriminative neighborhood.

* We explore a non-discrete masking mechanism in masked autoencoders, named “bandwidths”. We establish a theoretical relationship between our bandwidth mechanism and regularized denoising autoencoders to prove its informativeness.

* We propose , a novel graph self-supervised learning framework that learns topologically informative representations. It outperforms representative baselines in both link prediction and node classification solely with a structure-learning pretext.

§ RELATED WORK

In this section, we briefly review prior work on graph self-supervised learning and compare their advantages and disadvantages.

Contrastive Learning <cit.> was born initially for the visual domain <cit.>. The most popular contrastive learning framework <cit.> feeds augmented data pairs into two shared-weight neural networks. Then it
computes pairwise similarities between positive and negative samples
by InfoNCE contrastive loss <cit.>.
A flood of prominent work has appeared since contrastive learning was introduced to the graph domain <cit.>.

However, they must face the serious problem of representation collapse
, that is, the output of the encoder will degenerate to a scalar independent of the input.
In addition, InfoNCE itself does not provide the power of learning graph structures, because it only measures the distance in the feature space. Therefore, contrastive learning methods rarely discuss the generalizability to structural tasks like link prediction unless they are specifically designed <cit.>.

Autoencoding, another line of work,
encodes the graph into a latent space via GNNs and then decodes the representations to reconstruct the original features or structure. The pioneering work of GAE <cit.> stimulated the research of traditional graph autoencoders <cit.>. However, an overcomplete autoencoder, whose dimension of the representation space is no less than that of the data space, may degenerate into an identity map,
severely limiting its expressive power.
Graph variational autoencoders <cit.> learn prior variational distributions of latent representations to obtain better latent spaces and generate new representations from them.
Nevertheless, they still induce a suboptimal latent space because of the simplistic prior assumption <cit.>.

Mask Modeling. The “mask-then-reconstruct” scheme has already been adopted to model natural language, computer vision, etc., and has achieved great success <cit.>.
Masked autoencoders (MAEs) have been introduced into the graph domain just recently <cit.>. For FeatRecs, the most well-known of which is the  series <cit.> that leverages the re-mask mechanism and the scaled cosine error loss.
Yet, they are not suitable for link prediction due to the neglect of graph topology.
On the other hand, TopoRecs learn by discrete random edge masks and link reconstruction, the most well-known of which are  (formerly ) <cit.> and  <cit.>.
resorts to a cross-correlation decoder to capture the information lost by perturbation, and  employs path masks and another degree regression decoder.
Despite being empirically beneficial to performance improvement, there are no theoretical guarantees that these strategies can induce a better topological learner.

Our work aims to bridge this gap.

§ PRELIMINARIES

In this section, we illustrate the principle of message propagation (Section <ref>) and TopoRecs (Section <ref>). Then, we discuss the problems of discrete masking and link reconstruction (Section <ref>).

§.§ Notations and Concepts

We use different types of one specific symbol $S$ to denote different forms of one mathematical object. A bold symbol $\mathbf{S}$ denotes a matrix, with its $j$th column in bold italics $\boldsymbol{S}_j = \mathbf{S}_{:,j}$. The element at the $i$th row and $j$th column is in italics with subscripts $S_{ij}$.

Let $\mathcal{G} = (\mathbf{X}, \mathbf{A})$ be an undirected graph with $n$ nodes, where $\mathbf{X} \in \mathbb{R}^{n \times d}$ is the node feature matrix and $\mathbf{A} \in \{0, 1\}^{n \times n}$ is the adjacency matrix. We also denote by $\mathcal{E}$ the edge set and $\mathcal{V}$ the node set.
$\text{deg}(i)$ is the degree of node $i$. We call any 1-hop subgraph $\mathcal{G}_i = (\mathbf{X}^{\mathcal{G}_{i}}, \mathbf{A}^{\mathcal{G}_{i}}) \subset \mathcal{G}$ of node $i$ an ego-graph, where $\mathbf{X}^{\mathcal{G}_{i}} = [\boldsymbol{X}_j]_{j\in\mathcal{N}_i \cup \{i\}}$, and $\mathbf{A}^{\mathcal{G}_{i}} \in \{0,1\}^{n_i\times n_i}$ is a principal submatrix of $\mathbf{A}$
Here $n_i=|\mathcal{N}_i \cup \{i\}|$ with $\mathcal{N}_i$ the 1-hop neighborhood set of node $i$.

Message-passing GNNs (MPNNs) <cit.> learn by exchanging information between neighboring nodes. To begin with, every node receives messages from its neighbors and processes them with non-linear neurons. Then, messages are aggregated as the new representation of that node. This iterative updating mechanism can be formalized as $\mathbf{Z}^{(k)} \leftarrow \mathbf{G}\mathbf{Z}^{(k-1)}\mathbf{W}^{(k-1)}$, where $\mathbf{W}^{(k)}$ is a learnable weight matrix of the $k$th layer. For notational convenience, we integrate message aggregation and activation into one message propagation matrix $\mathbf{G}$, with the general form $\mathbf{G}=\Sigma\mathbf{A}$ where $\Sigma$ is an activation operator such as Sigmoid $\sigma(\cdot)$ and ReLU. $\mathbf{G}$ varies with GNN types, such as
$\mathbf{G} = \Sigma\hat{\mathbf{D}}^{-1/2}\hat{\mathbf{A}}\hat{\mathbf{D}}^{-1/2}$
for a Graph Convolutional Network (GCN) <cit.>. Here $\hat{\mathbf{A}}$ represents the graph with self-loops: $\hat{\mathbf{A}}=\mathbf{A}+\mathbf{I}_n$ and $diag(\hat{\mathbf{D}})=\mathbf{1}_n^\top\hat{\mathbf{A}}$, where $\mathbf{I}_n\in\{0, 1\}^{n \times n}$ and $\mathbf{1}_n \in \{1\}^n$ are respectively the identity matrix and the all-ones vector. To sum up, we can denote the output of the $K$th MPNN layer as $\mathbf{Z}^{(K)} = \mathbf{\Gamma}\mathbf{X}\mathbf\Theta$, where $\mathbf{\Gamma}=\mathbf{G}^K$ and $\mathbf\Theta=\prod_{i=0}^{K-1}{\mathbf{W}^{(i)}}$.

Blocked message flows.

§.§ TopoRec

mask a subset of edges $\mathcal{E}_m \subset \mathcal{E}$ and use the unmasked set $\bar{\mathcal{E}}_m = \mathcal{E} - \mathcal{E}_m$ along with the entire node set to train an encoder. $\bar{\mathcal{E}}_m$ (resp. $\mathcal{E}_m$) induces a subgraph with adjacency matrix $\bar{\mathbf{A}}_{m}$ (resp. $\mathbf{A}_{m} = \mathbf{A} - \bar{\mathbf{A}}_{m}$). The masking process is defined as

\begin{equation}\label{eq:mask}
\bar{\mathbf{A}}_{m}=\mathbf{A} \circ \mathbf{M}, \quad \mathbf{M} := [\mathbb{1}_{[(i,j)\in \bar{\mathcal{E}}_m]}]^{n \times n} \in \{0, 1\}^{n \times n}
\end{equation}

with $\circ$ the Hadamard product. For discrete TopoRecs, every entry of the masking matrix $\mathbf{M}$ is an indicator $\mathbb{1}_{[(i,j)\in \bar{\mathcal{E}}_m]}$ that determines if the edge $(i,j)$ is retained. It follows an i.i.d. Bernoulli distribution $M_{ij} \sim Bernoulli(1-p), \forall i, j$ where $p$ controls the mask ratio.

Formally, A TopoRec is a parameterized binary map $r(\mathbf{X}, \bar{\mathbf{A}}_{m}): \mathbb{R}^{n \times d} \times \{0, 1\}^{n \times n} \rightarrow (0, 1)^{n \times n}$ implemented by two head-to-tail networks, the so-called encoder-decoder. Encoder, the GNN to be pre-trained, encodes the input features as latent representations, with the $k$th-layer weights $\mathbf{W}_{e}^{(k)}$. Decoder plays an auxiliary role in recovering the representations, with the $k$th-layer weights $\mathbf{W}_{d}^{(k)}$.
A TopoRec with a single-layer MLP decoder is formalized as

\begin{equation}\small
r(\mathbf{X}, \bar{\mathbf{A}}_{m}) := \underbracket[0.8pt][3pt]{\Sigma_d(\boldsymbol{b}_d+\mathbf{W}_d}_{\text{decoder}}\underbracket[0.8pt][3pt]{(\mathbf{\Gamma}\mathbf{X}\mathbf\Theta)}_{\text{encoder}}), \ \mathbf{\Gamma}= (\Sigma_e\bar{\mathbf{A}}_{m})^K, \mathbf\Theta=\prod_{i=0}^{K-1}{\mathbf{W}_{e}^{(i)}}
\end{equation}

where $\Sigma_e$ (resp. $\Sigma_d$) is the activation operator of the encoder (resp. decoder).
Finally, the reconstruction loss $\mathcal{L} = \mathcal{L}(r(\mathbf{X}, \bar{\mathbf{A}}_{m}), \mathbf{A}_{m} )$ minimizes the error between the output and the masked data. The cross-entropy is widely adopted to reconstruct links:

\begin{equation}\small
\label{eq:toporecce}\hspace*{-0.05in}
\mathcal{L}(r(\mathbf{X},\bar{\mathbf{A}}_{m}),\mathbf{A}_{m}):=\boldsymbol{1}_n^\top\left(\frac{\delta_{\mathcal{E}_m}}{|\mathcal{E}_m|} + \frac{\delta_{\mathcal{E}^-}}{|\mathcal{E}^-|}\right)(-\mathbf{A}_{m}\circ\log r(\mathbf{X},\bar{\mathbf{A}}_{m}))\boldsymbol{1}_n
\end{equation}

Here $\scriptsize \delta_{\mathcal{E}} = \delta_{(i,j)}(\mathcal{E}):=\begin{cases}
1, (i,j) \in \mathcal{E} \\
0, (i,j) \notin \mathcal{E}
\end{cases}$
is the Dirac measure: the term $\scriptsize \frac{\delta_{\mathcal{E}_m}}{|\mathcal{E}_m|}$ in <ref> filters and averages every masked edge from the cross-entropy matrix $(-\mathbf{A}_{m}\circ\log r(\mathbf{X},\bar{\mathbf{A}}_{m}))$, while $\scriptsize \frac{\delta_{\mathcal{E}^-}}{|\mathcal{E}^-|}$ indicates the sampled negative edge set $\mathcal{E}^- \subset \mathcal{V}\times\mathcal{V} - \mathcal{E}$.

§.§ A Message Propagation View of TopoRecs

In this subsection, we revisit the message propagation to answer the question “why are discrete TopoRecs topologically uninformative?”.

§.§.§ Global uninformativeness: blocked message flows.
A message flow is the directed message pathway from a source node to a sink (target) node <cit.>.

Let us analyze the message flows of a discrete TopoRec.
For an ego-graph $\mathcal{G}_i$, the central node $i$ randomly selects a subset of nodes from its neighborhood $\mathcal{N}_i$ and aggregates messages from them only.
This indiscriminate selection obstructs the message flows that may be crucial to the sink nodes:
source nodes of these message flows are not able to transmit their messages directly to the sink nodes, resulting in a large amount of stretched or even blocked flows, which are very likely to disrupt the connectivity of the original graph (as the mask ratios of these masked autoencoders are usually very high <cit.>), as shown in Figure <ref>(a).

Entropy histograms of the edge weight distribution in ego-graphs on Cora.

Moreover, we reveal that discrete masking makes the encoder vulnerable to the over-smoothing problem.
To formalize, we introduce a commonly used metric, the Dirichlet energy <cit.>, to evaluate the over-smoothness of a discretely masked graph.
The lower the energy, the severer the over-smoothness. Our conclusion is summarized by the following theorem.

[breakable, pad at break=2.5mm, before skip=1mm, after skip=1mm, width=1.0, boxsep=0mm, arc=1.5mm, left=1.5mm, right=1.5mm, top=1.5mm, bottom=1mm]

Let $\mathcal{G}_i=(\mathbf{X}^{\mathcal{G}_{i}}, \mathbf{A}^{\mathcal{G}_{i}})$ be an ego-graph with $n_i\ge2$. Assume $\boldsymbol{X}_j^{\mathcal{G}_{i}} = \boldsymbol{X}_k^{\mathcal{G}_{i}}$ for $\forall j,k \in \mathcal{N}_i$. Define the ego Dirichlet Energy of $\mathcal{G}_i$ as

\begin{equation}
E_D(\mathcal{G}_i) := \frac{1}{n_i}\sum_{j \in \mathcal{N}_i}\|\boldsymbol{X}_i^{\mathcal{G}_{i}}-\boldsymbol{X}_j^{\mathcal{G}_{i}}\|^2
\end{equation}

If a connected component $\mathcal{G}_{i,m}$ of $\mathcal{G}_i$ is induced by imposing masks following the i.i.d. $Bernoulli(1-p), 0<p \le 1$ to $\mathbf{A}^{\mathcal{G}_{i}}$, then we have $E_D(\mathcal{G}_{i,m}) \le E_D(\mathcal{G}_i)$. This inequality is an equality iff $p=1$.

Please refer to Appendix <ref>.

Note that the Dirichlet energy of the entire graph is exactly the sum of ego Dirichlet energies over all ego-graphs. So
Theorem <ref> remarks that a discretely masked graph is more likely to be over-smoothed. As such, discrete TopoRecs obtain relatively trivial expressive power with deeper GNN layers. We have also conducted an experiment to verify this on 5 graph benchmark datasets. It is shown in Figure <ref>(b) that the performance of  goes into a nosedive with a 5-or-more-layer GCN.

§.§.§ Local uninformativeness: indiscriminative neighborhood.
A GCN or Graph Attention Network (GAT) <cit.> is usually chosen as the encoder of a TopoRec. However, both of them are not capable of distinguishing the messages among different neighbors effectively. We quantify the discriminability of each neighbor $j$'s message in an ego-graph $\mathcal{G}_i$ as the dispersion of edge weights assigned by node $i$. In GCN, such assignment is realized only by a function of node degrees $w_{ij}=1/\sqrt{(\deg(i)+1)(\deg(j)+1)}$.
This does not work well due to the power-law tendency of networks <cit.>.
GAT, by contrast, explicitly models the neighborhood by introducing learnable self-attention matrices: $w_{ij}=\text{softmax}_j({\text{LeakyReLU}(\mathbf{a}^\top[\mathbf{W}_{att}\boldsymbol{Z}_i||\mathbf{W}_{att}\boldsymbol{Z}_j])})$, but its discriminability is limited either, as previous research <cit.> indicates that the attention weights assigned by GAT are roughly the same for different neighbors.
Unfortunately, the discrete masking strategy will not provide such neighbor discriminability, because their only concern is the existence of links to some neighbors.

We have conducted another experiment on Cora for demonstration. Edge weights assigned by GCN and GAT pre-trained by  are first computed. Then, entropies of the weights in every ego-graph $H_i = -\sum_{j \in \mathcal{N}_i}w_{ij} \log {w_{ij}}$ are calculated. The smaller the entropy value, the more discriminative the edge weights. We visualize the entropies in Figure <ref> (left, center) and observe that
for both GCN and GAT, the entropy distribution peaks shift towards the larger area, since  is not able to provide discriminative power of neighbor messages for them.

To sum up, a new masking scheme is desired instead of discrete edge masking for better topological informativeness.

§ BANDANA

In this section, we aim to answer the questions “what is ?” in Section <ref> and “why does  learn informative representations?” in Section <ref>.  is a novel topological masked graph autoencoder that encompasses two main mechanisms: continuous bandwidth masks and layer-wise bandwidth prediction.

§.§ Bandwidth Masking and Prediction Pipeline

§.§.§ Continuous bandwidth masks.

According to Section <ref>, a discrete TopoRec samples edge masks from a Bernoulli distribution. As bandwidths are non-discrete, each entry of the masking matrix $\mathbf{M}$ should be randomly sampled from a continuous distribution instead, with the following requirements:

Probabilistic: $M_{ij} \in [0, 1]$ (0 for non-existent edges).

Simplicial: $\sum_{j\in\mathcal{N}_i}{M_{ij}} = 1, \sum_{j\notin\mathcal{N}_i}{M_{ij}} = 0$.

Dispersive: bandwidths of neighbors should be discriminative.

For (1) and (2), every column of $\mathbf{M}$, i.e., bandwidths of neighbors in an ego-graph, should form a probabilistic simplex to stabilize the message passing process.
For (3), we want bandwidths to provide the discriminative power of neighbors. In light of these conditions, we choose the bandwidth distribution as follows.

[breakable, pad at break=2.5mm, before skip=1mm, after skip=1mm, width=1.0, boxsep=0mm, arc=1.5mm, left=1.5mm, right=1.5mm, top=1.5mm, bottom=1mm]

For the rest of the paper, $\mathbf{M}\in [0, 1]^{n \times n}$ is a continuous matrix consisting of i.i.d. probabilistic simplicial column vectors, of which each nonzero entry follows a Boltzmann-Gibbs distribution:

\begin{equation}\label{eq:bandwidth}
M_{ij} = \text{softmax}_j\left(\frac{m_{ij}}{\tau}\right) = \displaystyle\frac{\exp(m_{ij}/\tau)}{\sum_{k \in \mathcal{N}_j \cup \{j\}}{\exp(m_{kj}/\tau)}}
\end{equation}

where $m_{ij} \sim \mathcal{N}(0, 1)$ and $\tau$ denotes the temperature.

Intuitively, a “bandwidth” on an edge is the maximum proportion of the output messages to the input messages through that edge per message passing step. The softmax in <ref> plays a dual role of normalization and amplification: (1) normalization guarantees a probabilistic simplex; (2) exponential softmax amplifies the weight dispersion in an ego-graph, which has already been discovered and utilized by some attention-based studies <cit.>.
Though both are edge weights, bandwidths are fundamentally different from attention weights, which is further discussed in Appendix <ref>.

Instead of the discrete masking matrix, we use bandwidths to perturb the adjacency matrix: $\tilde{\mathbf{A}}=\mathbf{A} \circ \mathbf{M}$. This converts the initial discrete adjacency matrix with $A_{ij} \in \{0, 1\}$ into a continuous matrix with $\tilde{A}_{ij} \in [0, 1]$. Unlike the discrete case, both $\mathbf{M}$ and $\tilde{\mathbf{A}}$ are no longer symmetric, because there are two different bandwidth values on every edge for the bidirectional message propagation.

Note that we also adopt the temperature $\tau$ to control the bandwidth distribution. Specifically, it controls the continuity of the mask: when $\tau\rightarrow0$, the Boltzmann-Gibbs distribution degenerates to the superposition of Dirac $\delta$ functions at 0 and 1, that is, the discrete Bernoulli mask; when $\tau\rightarrow\infty$, it degenerates to Uniform.

§.§.§ Encoding.
's encoder network propagates bandwidth-restricted messages. To be more specific, the perturbed adjacency matrix $\tilde{\mathbf{A}}$ represents an undirected graph with bidirectional edge weights, on which  performs message propagation instead of $\bar{\mathbf{A}}_{m}$. Propagation on the $k$th layer can be formalized as

\begin{equation}\label{eq:bandanaprop}
\mathbf{Z}^{(k)} \leftarrow \tilde{\mathbf{G}}\mathbf{Z}^{(k-1)}\mathbf{W}_{e}^{(k-1)}, \quad \tilde{\mathbf{G}}=\Sigma_e\tilde{\mathbf{A}}
\end{equation}

The entire encoder-decoder is defined as

\begin{equation}
r(\mathbf{X}, \mathbf{A}) := \underbracket[0.8pt][3pt]{\Sigma_d(\boldsymbol{b}_d+\mathbf{W}_d}_{\text{decoder}}\underbracket[0.8pt][3pt]{(\tilde{\mathbf{\Gamma}}\mathbf{X}\mathbf\Theta)}_{\text{encoder}}), \quad \tilde{\mathbf{\Gamma}} = \tilde{\mathbf{G}}^{K}
\end{equation}

where $\Sigma_d$ refers to the softmax function. It now models the representation space in a way that every node receives and aggregates different ratios of messages from different neighbors.

§.§.§ Bandwidth prediction.

Following the asymmetric encoder-decoder architecture <cit.>,  employs a lightweight MLP as its decoder. What the bandwidth decoder “reconstructs” is the bandwidth value of every edge, i.e. it predicts how much every edge is masked during training.
This is a logistic regression problem
that can still be optimized by the cross-entropy objective:

\begin{equation}\label{eq:bandce}
\mathcal{L}(r(\mathbf{X}, \mathbf{A}), \tilde{\mathbf{A}} ):=\boldsymbol{1}_n^\top\left(\frac{\delta_{\mathcal{E}}}{|\mathcal{E}|}+ \frac{\delta_{\mathcal{E}^-}}{|\mathcal{E}^-|}\right)(-\tilde{\mathbf{A}}\circ\log r(\mathbf{X}, \mathbf{A}))\boldsymbol{1}_n
\end{equation}

The difference is that all positive edges ($\delta_{\mathcal{E}}$) are now participating in training. We still keep blocked edges $\delta_{\mathcal{E}^-}$ as zero samples.

§.§.§ Layer-wise masking and prediction.
It has become common knowledge that different network layers capture different granularities of information: shallower layers capture more general information, while deeper layers capture information more specific to the pretext task
We propose a layer-wise masking scheme to explicitly capture different granularities. We generate different bandwidth masks for every layer of GNN, with the $k$th-layer perturbed adjacency matrix $\tilde{\mathbf{A}}^{(k)}$ and the corresponding message propagation matrix $\tilde{\mathbf{G}}^{(k)}$. On the backend, we share one MLP decoder for every layer.
We calculate the reconstruction loss for each layer and the final loss is the average of all layer losses:

\begin{equation}\small
\mathcal{L} = \frac{1}{K}\sum_{k=0}^{K-1}{\mathcal{L}^{(k)}} = \frac{1}{K}\sum_{k=0}^{K-1}{\mathcal{L}( \Sigma_d(\boldsymbol{b}_d+\mathbf{W}_d(\tilde{\mathbf{\Gamma}}^{(k)}\mathbf{X}\mathbf\Theta^{(k)})), \tilde{\mathbf{A}}^{(k)})}
\end{equation}

where $\tilde{\mathbf{\Gamma}}^{(i)} = \prod_{i=0}^{k-1}{\tilde{\mathbf{G}}^{(k)}}, \mathbf\Theta^{(k)}=\prod_{i=0}^{k-1}{\mathbf{W}_{e}^{(i)}}$.

§.§ Why Are Bandwidths Informative?

In this subsection, we give empirical and theoretical support for our bandwidth schemes.

§.§.§ A fine-grained strategy for informative topology.

The advantages of bandwidth masking and prediction are threefold.

* Compared with binary link reconstruction, predicting a continuous bandwidth value is a more fine-grained and challenging task which is more meaningful to the mask modeling <cit.>.

* Global informativeness, as non-discrete bandwidth masks guarantee a complete graph topology and unimpeded message flows so that deeper GNNs can be pre-trained more effectively. As shown in Figure <ref>(b),  greatly outperforms  on GNN pre-training with 5 or more layers.

* Local informativeness, as  can provide the discriminative power of neighbor messages by bandwidth prediction.
As shown in Figure <ref> (right),  has the most discriminative neighborhood weights.

Such informativeness is further validated by an embedding visualization study on Karate Club <cit.> in Appendix <ref>.

§.§.§ Implicit optimization on the topological manifold.

's excellent topological learning ability is theoretically guaranteed. We elucidate that  can be interpreted as a regularized denoising autoencoder <cit.> in an implicit graph topological space, while a discrete TopoRec cannot. Furthermore, bandwidth prediction is mathematically equivalent to optimizing a “score” in that space.
To this end, we first assign each column of the adjacency matrix $\mathbf{A}$ to the corresponding node in the graph as its new “feature”.

[breakable, pad at break=2.5mm, before skip=1mm, after skip=1mm, width=1.0, boxsep=0mm, arc=1.5mm, left=1.5mm, right=1.5mm, top=1.5mm, bottom=1mm]

A topological encoding matrix is defined as $\mathbf{T}:=\mathbf{A} - \boldsymbol{1}_n\boldsymbol{1}_n^\top \in \mathbb{R}^{n \times n}$, where $\boldsymbol{1}_n$ is the all-ones vector. Denote $\boldsymbol{T}_j$ as the topological encoding of node $j$.

One advantage of the topological encoding is that it allows us to write the bandwidth masking as adding random noises on it:

\begin{equation}
\tilde{\mathbf{T}} = \delta_{\mathcal{E}}(\mathbf{T} + \boldsymbol{\epsilon})=\mathbf{T} + \boldsymbol{\epsilon}, \ \boldsymbol{\epsilon}_i \sim \text{softmax}(\mathcal{N}(0, \mathbf{I}_n))
\end{equation}

Assume $\boldsymbol{T}_j$ and the perturbed $\tilde{\boldsymbol{T}}_j$ follow the probability distributions $p(\boldsymbol{T}_j)$ and $p(\tilde{\boldsymbol{T}_j})$ respectively.
From the topological encoding perspective, $\mathbf{X}$ and $\mathbf{\Theta}$ are conversely the non-linear transformations on $\tilde{\mathbf{A}}$, in which case we denote our bandwidth reconstructor by $r_{\mathbf{X}}$. Under this premise, the following Proposition gives that $r_{\mathbf{X}}$ can be viewed as a regularized denoising autoencoder.

[breakable, pad at break=2.5mm, before skip=1mm, after skip=1mm, width=1.0, boxsep=0mm, arc=1.5mm, left=1.5mm, right=1.5mm, top=1.5mm, bottom=1mm]

Suppose a TopoRec on vectors $r_{\mathbf{X}}: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$ is at least first-order differentiable (to $\boldsymbol{T}_{j}$ for the rest of the paper). If the perturbed topological encoding $\tilde{\boldsymbol{T}}_j$ on a connected graph follows a continuous distribution $p(\tilde{\boldsymbol{T}_j})$ and satisfies

$n \ll 2|\mathcal{E}|$, and

all elements in $\{\tilde{\boldsymbol{T}}_{j}\}_{j=1}^{n}$ follow an i.i.d. isotropic multivariate Gaussian $\mathcal{N}(\boldsymbol{\mu}_{\tilde{\boldsymbol{T}}_{j}},\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}})$, i.e. the covariance matrix satisfies $\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}}=c\mathbf{I}$ where $c$ is an arbitrary constant.

Then, $\mathcal{L}$ in <ref> defines a regularized denoising autoencoder:

\begin{equation}\small
\label{eq:rdae}\hspace*{-0.05in}
\mathcal{L} = \underbracket[0.8pt][2pt]{\mathbb{E}_{j\in\mathcal{V}}[\| r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_{j} \|^2]}_\text{reconstruction} + \underbracket[0.8pt][2pt]{\sigma_{\epsilon}^2 \mathbb{E}_{j\in\mathcal{V}}[\| \nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})\|^2_F]}_\text{regularization} +o(\sigma_{\epsilon}^2)
\end{equation}

where $\sigma_{\epsilon}^2$ is the noise variance.

Please refer to Appendix <ref>. We also discuss the mildness of the assumptions in Appendix <ref>.

Proposition <ref> is consistent with previous studies that the masked autoencoder is a kind of denoising autoencoder <cit.>, but the noise should technically be non-discrete for TopoRecs.
According to the existing analysis of the denoising autoencoder <cit.>, we have the following theorem.

[breakable, pad at break=2.5mm, before skip=1mm, after skip=1mm, width=1.0, boxsep=0mm, arc=1.5mm, left=1.5mm, right=1.5mm, top=1.5mm, bottom=1mm]

Suppose $r_{\mathbf{X}}$ fulfills the condition in Proposition <ref>. Then for $\sigma_{\epsilon}^2 \rightarrow 0$, the optimal TopoRec $r_{\mathbf{X}}^* = \arg\min_{r_{\mathbf{X}}}{\mathcal{L}}$ is asymptotically equivalent to an implicit gradient optimizer of $\log p(\boldsymbol{T}_{j})$:

\begin{equation}
r^*_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_{j}  \propto \nabla \log{p(\boldsymbol{T}_{j})}
\end{equation}

Please refer to Appendix <ref>.

By Theorem <ref>, the optimal bandwidth predictor ($r_{\mathbf{X}}=r_{\mathbf{X}}^*$) optimizes the gradient of log probabilities of the topological encoding, indicating that the bandwidth masking and prediction scheme are theoretically learning graph topology.
Based on our conclusions,  can be further expanded to some theoretically grounded frameworks, such as score-based models <cit.> and energy-based models <cit.>. We have further discussions in Appendix <ref>.

§ EXPERIMENT ANALYSES

In this section, we first introduce experimental configurations in Section <ref>. More detailed settings can be found in Appendix <ref>. Then, we showcase the experiment results of  to answer the following research questions:

* RQ1. Is  able to learn more informative topology than discrete TopoRecs in practice?

* RQ2. How does  perform on node classification?

* RQ3. How does  perform on link prediction?

* RQ4. How effective are Boltzmann-Gibbs bandwidths and the layer-wise strategy?

More experiment results can be found in Appendix <ref>, including time and space consumptions (<ref>), more large-scale datasets (<ref>), parameter analyses (<ref>), the semi-supervised setting (<ref>), etc.

§.§ Experimental Settings

Datasets. Apart from the two synthetic datasets in Section <ref>, we conduct experiments on 12 well-known undirected and unweighted graph benchmark datasets, including (1) citation networks: Cora, CiteSeer, PubMed <cit.>; (2) co-purchase networks: Photo, Computers <cit.>; (3) co-author networks: CS, Physics <cit.>; (4) OGB networks: ogbn-arxiv, ogbn-mag, ogbl-collab, ogbl-ppa <cit.>; (5) hyperlink networks: Wiki-CS <cit.>.
Detailed statistics can be found in Appendix <ref>, and experiment results of the last 4 datasets can be found in Appendix <ref> and <ref>.

We report all quantitative results as “mean ± standard deviation” by running 10 times under the same setup. Hardware, training setups, and hyperparameters can be found in Appendix <ref> and <ref>.

Baselines. As self-supervised methods are being studied, only self-supervised algorithms are considered as baselines.
They are divided into the following categories:
(1) traditional graph autoencoders:  <cit.>,  <cit.>; (2) variational graph autoencoders:  <cit.>,  <cit.>,  <cit.>,  <cit.>[ fuses mask modeling with the variational autoencoder. We still count it as variational-based in light of its generative characteristic and learning objective.]; (3) contrastive and non-contrastive (with no negative sampling) methods:  <cit.>,  <cit.>,  <cit.>,  <cit.>,  <cit.>; (4) FeatRecs:  <cit.>,  <cit.>; (5) TopoRecs:  <cit.>, -edge, -path <cit.> (with edge masking and path masking separately).
We use “$\dagger$” to mark baselines that are implemented by us for the current task because they are not officially implemented.

Manifold learning visualizations.

Micro-F1(%) and Macro-F1(%) of node classification.

max width=1.0

Micro-F1     2*Year     2*
Model     2*Cora     2*CiteSeer     2*PubMed    2*Photo     2*Computers     2*CS     2*Physics     2*ogbn-arxiv     2*Avg. Rank

Autoencoder     2*2016     2*   $^\dagger$ <cit.>    80.15 ± 0.34     69.79 ± 0.36     80.51 ± 0.53     91.07 ± 0.09     87.92 ± 0.12     90.46 ± 0.29     93.04 ± 0.03     69.58 ± 0.32     2*10.3
78.44 ± 0.90     62.64 ± 0.58     79.62 ± 0.38     89.83 ± 0.13     86.02 ± 0.25     89.75 ± 0.32     91.02 ± 0.04     48.25 ± 0.53
[RGB]180, 180, 180()2-12[RGB]0, 0, 0
2*2018    2*$^\dagger$ <cit.>     77.93 ± 0.59     68.55 ± 0.34     77.78 ± 0.63     92.77 ± 0.26     88.11 ± 0.08     92.46 ± 0.14     94.32 ± 0.04     69.81 ± 0.27     2*9.3

76.89 ± 0.51     63.33 ± 0.68     76.54 ± 0.82     91.60 ± 0.10     86.34 ± 0.15     90.61 ± 0.19     92.58 ± 0.07     47.89 ± 0.45

Autoencoder     2*2016    2*$^\dagger$ <cit.>     76.30 ± 0.49     58.85 ± 0.79     75.73 ± 0.22     89.58 ± 0.20     84.99 ± 0.19     92.33 ± 0.07     94.40 ± 0.07     69.94 ± 0.30     2*12.3

74.70 ± 0.60     52.80 ± 0.91     75.39 ± 0.24     86.61 ± 0.40     82.26 ± 0.30     89.09 ± 0.16     92.28 ± 0.11     47.05 ± 0.79

[RGB]180, 180, 180()2-12[RGB]0, 0, 0
2*2018    2*$^\dagger$ <cit.>     76.85 ± 0.88     54.73 ± 0.46     73.06 ± 0.42     89.51 ± 0.23     85.03 ± 0.15     92.56 ± 0.09     93.64 ± 0.08     69.39 ± 0.36      2*12.5

75.15 ± 0.95     48.71 ± 1.27     73.49 ± 0.44     86.88 ± 0.40     81.54 ± 0.36     89.67 ± 0.23     91.08 ± 0.15     47.34 ± 0.59

[RGB]180, 180, 180()2-12[RGB]0, 0, 0
2*2023    2* <cit.>     83.95 ± 0.55     72.11 ± 1.26     79.55 ± 0.29     90.13 ± 0.57     88.39 ± 0.26*     88.79 ± 0.93     2*OOM     2*OOM     2*9.6

82.88 ± 0.66     68.48 ± 0.86     78.36 ± 0.44     87.76 ± 1.01         85.38 ± 1.62

8*Contrastive &
2*2020    2* <cit.>     80.95 ± 0.29     70.39 ± 0.46     83.55 ± 0.44     92.12 ± 0.14     87.68 ± 0.15     91.90 ± 0.01     2*OOM     2*OOM     2*8.3

79.20 ± 0.44     68.15 ± 0.32     83.29 ± 0.20     90.99 ± 0.36     85.82 ± 0.27     89.09 ± 0.01

[RGB]180, 180, 180()2-12
2*2021     2* <cit.>     81.92 ± 0.17     71.60 ± 0.27     84.08 ± 0.16     92.39 ± 0.20     87.14 ± 0.15     92.61 ± 0.06     2*OOM     2*OOM     2*6.4

80.76 ± 0.35     68.79 ± 0.37     83.70 ± 0.29     91.17 ± 0.30     85.10 ± 0.31     90.64 ± 0.16

[RGB]180, 180, 180()2-12[RGB]0, 0, 0
2*2022    2* <cit.>     84.60 ± 0.20     72.57 ± 0.31     83.76 ± 0.03     90.98 ± 0.00     87.35 ± 0.08     92.48 ± 0.05     95.31 ± 0.04     2*OOM     2*6.4

82.50 ± 0.21     66.11 ± 0.29     83.16 ± 0.02     88.22 ± 0.00     85.99 ± 0.13     89.32 ± 0.08     93.90 ± 0.05

[RGB]180, 180, 180()2-12[RGB]0, 0, 0
2*2021    2* <cit.>     83.96 ± 0.38     73.45 ± 0.44     81.81 ± 0.53     92.87 ± 0.36     88.61 ± 0.29     93.01 ± 0.29     95.31 ± 0.07     69.52 ± 0.09     2*5.1

83.01 ± 0.48     68.75 ± 0.51     81.31 ± 0.51     91.69 ± 0.49     87.24 ± 0.52     90.73 ± 0.51     93.76 ± 0.10     47.39 ± 0.51

2*2022    2* <cit.>     84.05 ± 0.59     73.06 ± 0.37     80.98 ± 0.47     92.92 ± 0.40     89.24 ± 0.45     93.09 ± 0.14     95.65 ± 0.07     71.30 ± 0.24     2*3.6

83.07 ± 0.53     67.78 ± 0.85     80.26 ± 0.48     91.93 ± 0.47     88.12 ± 0.78     91.42 ± 0.15     94.19 ± 0.09     51.15 ± 0.15

[RGB]180, 180, 180()2-12[RGB]0, 0, 0
2*2023    2* <cit.>     83.84 ± 0.54     73.48 ± 0.34     81.34 ± 0.44     93.30 ± 0.20     89.01 ± 1.53     91.31 ± 0.07     95.25 ± 0.05     71.82 ± 0.00     2*5.2

82.80 ± 0.46     68.70 ± 0.42     80.68 ± 0.43     92.19 ± 0.24     87.63 ± 1.79     88.89 ± 0.13     93.78 ± 0.07     50.42 ± 0.00

2*2023    2* <cit.>     78.34 ± 0.96     65.31 ± 0.64     80.11 ± 0.52     91.43 ± 0.07     85.31 ± 0.07     90.47 ± 0.07     93.98 ± 0.06     67.77 ± 0.36     2*11.8

77.44 ± 0.86     62.54 ± 0.64     79.04 ± 0.47     90.47 ± 0.15     81.48 ± 0.18     87.69 ± 0.11     91.95 ± 0.08     36.41 ± 0.24

[RGB]180, 180, 180()2-12[RGB]0, 0, 0
2*2023    2*-edge <cit.>     83.33 ± 0.15     72.02 ± 0.46     82.33 ± 0.39     93.28 ± 0.08     89.42 ± 0.15     92.29 ± 0.25     95.10 ± 0.04     70.95 ± 0.29     2*5.9

82.60 ± 0.24     66.36 ± 0.63     81.63 ± 0.41     92.04 ± 0.08     88.00 ± 0.14     90.17 ± 0.34     93.48 ± 0.04     49.37 ± 0.45

[RGB]180, 180, 180()2-12[RGB]0, 0, 0
2*2023    2*-path <cit.>     82.54 ± 0.16     72.32 ± 0.39     82.80 ± 0.22     93.29 ± 0.10     89.40 ± 0.10     92.54 ± 0.21     95.15 ± 0.11     71.22 ± 0.40     2*5.4

81.84 ± 0.26     65.77 ± 0.40     82.23 ± 0.23     92.16 ± 0.17     87.69 ± 0.15     90.25 ± 0.31     93.51 ± 0.03     49.99 ± 0.54

[RGB]180, 180, 180()2-12[RGB]0, 0, 0
white            84.62 ± 0.37     73.60 ± 0.16     83.53 ± 0.51     93.44 ± 0.11     89.62 ± 0.09     93.10 ± 0.05     95.57 ± 0.04     71.09 ± 0.24

white     -2*2024    -2*     82.97 ± 0.92     68.11 ± 0.48     82.99 ± 0.40     92.26 ± 0.04     87.79 ± 0.20     91.02 ± 0.13     94.20 ± 0.05     49.66 ± 0.50      -2*2.4

12l*We obtain a much lower score for  on Computers than the official one. We report the Micro-F1 from the original paper <cit.> instead.

§.§ Learning Topological Manifolds (RQ1)

We verify 's informative representation learning ability by performing manifold learning on two undirected synthetic datasets with structures: Swiss Roll, a curved surface on $\mathbb{R}^3$; and Two-moon, two interleaved crescent-shaped clusters on $\mathbb{R}^2$. We assign a column of the identity matrix $\mathbf{I}_n$ to each node as features with no topological information.
The latent representation spaces are learned by  and  respectively (each model is trained till the early stopping) and visualized by t-SNE <cit.>.
It is obvious in Figure <ref> that  is more topologically informative than .

AUC(%) and AP(%) of link prediction.

max width=1.0

Year     Model     Cora     CiteSeer     PubMed     Photo     Computers     CS     Physics
Avg. Rank

Autoencoder     2*2016     2* <cit.>     94.66 ± 0.26     95.19 ± 0.45     94.58 ± 1.12     71.45 ± 0.95     70.99 ± 1.03     93.78 ± 0.36     88.88 ± 1.11

94.22 ± 0.39     95.70 ± 0.31     94.26 ± 1.65     65.99 ± 0.96     67.88 ± 0.82     89.87 ± 0.59     82.45 ± 1.59

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2018     2* <cit.>     94.76 ± 0.18     95.68 ± 0.35     94.12 ± 0.08     85.42 ± 0.79     67.09 ± 3.93     95.49 ± 0.17     90.70 ± 1.08

94.93 ± 0.20     96.34 ± 0.25     94.19 ± 0.08     80.58 ± 1.40     62.53 ± 3.17     92.56 ± 0.33     89.37 ± 1.16

Autoencoder     2*2016     2* <cit.>     91.24 ± 0.48     94.55 ± 0.48     95.46 ± 0.04     95.61 ± 0.05     92.69 ± 0.03     87.34 ± 0.43     89.27 ± 0.83

92.27 ± 0.43     95.34 ± 0.37     94.29 ± 0.07     94.63 ± 0.06     88.27 ± 0.08     80.24 ± 0.55     82.79 ± 1.14

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2018     2* <cit.>     91.35 ± 0.87     94.47 ± 0.33     96.17 ± 0.21     95.44 ± 0.14     92.38 ± 0.15     87.39 ± 0.37     88.96 ± 0.96

91.98 ± 0.85     95.21 ± 0.33     94.81 ± 0.41     94.49 ± 0.12     88.49 ± 0.33     80.31 ± 0.49     82.38 ± 1.31

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2019     2* <cit.>     90.36 ± 1.34     88.85 ± 0.69     2*OOM     2*OOM     2*OOM     2*OOM     2*OOM

91.36 ± 1.16     90.27 ± 0.73

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2023     2* <cit.>     95.49 ± 0.70     94.61 ± 1.05     95.19 ± 3.94     95.25 ± 1.19     96.53 ± 0.16     95.73 ± 0.70     2*OOM

95.90 ± 0.64     96.40 ± 0.89     94.60 ± 4.17     94.04 ± 1.18     96.33 ± 0.16     93.17 ± 0.53

8*Contrastive &
2*2020     2*$^\dagger$ <cit.>     81.80 ± 0.45     84.78 ± 0.38     93.11 ± 0.37     88.64 ± 1.17     89.97 ± 0.25     87.67 ± 0.10     2*OOM

82.02 ± 0.50     82.85 ± 0.36     92.88 ± 0.30     83.85 ± 4.15     92.15 ± 0.43     94.87 ± 0.02

[RGB]180, 180, 180()2-11
2*2021     2*$^\dagger$ <cit.>     81.91 ± 0.76     84.72 ± 0.28     94.33 ± 0.67     89.61 ± 1.46     90.67 ± 0.30     88.05 ± 0.00     2*OOM

80.51 ± 0.71     81.57 ± 0.22     93.13 ± 0.62     86.53 ± 3.00     90.50 ± 0.63     94.94 ± 0.37

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2021     2*$^\dagger$ <cit.>     67.54 ± 1.30     78.88 ± 2.73     74.97 ± 0.28     91.04 ± 2.98     83.85 ± 1.35     83.54 ± 0.98     77.40 ± 0.08

72.74 ± 1.18     77.42 ± 4.56     77.11 ± 0.26     89.68 ± 3.85     84.04 ± 1.74     78.66 ± 1.06     73.33 ± 0.10

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2023     2* <cit.>     73.18 ± 0.54     78.11 ± 0.48     76.21 ± 0.18     80.80 ± 0.04     84.60 ± 0.05     70.08 ± 0.12     89.18 ± 0.04

76.81 ± 0.73     83.15 ± 0.47     80.99 ± 0.13     84.34 ± 0.06     86.85 ± 0.05     79.50 ± 0.09     84.30 ± 0.05

2*2022     2*$^\dagger$ <cit.>     93.02 ± 0.53     95.21 ± 0.47     87.54 ± 1.06     75.08 ± 1.24     71.27 ± 0.89     92.45 ± 4.18     85.03 ± 7.16     2*10.3

91.40 ± 0.59     94.42 ± 0.67     86.93 ± 1.01     70.04 ± 1.12     66.84 ± 1.10     91.67 ± 4.17     82.46 ± 9.33

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2023     2*$^\dagger$ <cit.>     93.26 ± 1.00     95.26 ± 0.14     90.85 ± 0.91     73.03 ± 2.24     72.20 ± 2.09     94.57 ± 0.32     94.56 ± 0.81

91.65 ± 0.98     94.36 ± 0.20     90.37 ± 0.92     68.77 ± 1.50     67.97 ± 1.52     92.76 ± 0.54     93.86 ± 1.09

2*2023     2* <cit.>     89.27 ± 0.33     86.35 ± 0.42     89.53 ± 0.23     86.80 ± 2.85     84.16 ± 4.82     86.60 ± 1.06     88.92 ± 1.24

89.78 ± 0.22     87.38 ± 0.29     88.68 ± 0.33     80.56 ± 3.74     78.13 ± 6.58     82.93 ± 1.63     88.20 ± 1.34

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2023     2*-edge <cit.>     95.66 ± 0.16     97.02 ± 0.27     96.51 ± 0.82     81.12 ± 0.45     76.23 ± 3.13     92.41 ± 0.44     91.94 ± 0.37     2*5.9

94.65 ± 0.24     96.89 ± 0.45     96.08 ± 0.68     77.11 ± 0.40     71.71 ± 2.90     87.16 ± 0.69     86.33 ± 0.55

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
2*2023     2*-path <cit.>     95.47 ± 0.25     97.21 ± 0.17     97.19 ± 0.18     80.46 ± 0.34     73.24 ± 1.26     87.96 ± 0.44     86.19 ± 0.36

94.64 ± 0.25     97.02 ± 0.32     96.69 ± 0.19     76.56 ± 0.55     70.94 ± 1.26     80.84 ± 0.58     78.55 ± 0.45

[RGB]180, 180, 180()2-11[RGB]0, 0, 0
white            95.71 ± 0.12     96.89 ± 0.21     97.26 ± 0.16     97.24 ± 0.11     97.33 ± 0.06     97.42 ± 0.08     97.02 ± 0.04

white     -2*2024     -2*     95.25 ± 0.16     97.16 ± 0.17     96.74 ± 0.38     96.79 ± 0.15     96.91 ± 0.09     97.09 ± 0.15     96.67 ± 0.05

§.§ Comparison on Node Classification (RQ2)

Similar to other self-supervised models <cit.>,  follows the linear probing setup to evaluate. That is, we use the pre-trained encoder's output representations to train a Xavier-initialized <cit.> linear layer.

We report two classic metrics, Micro-F1 and Macro-F1, in Table <ref>. It is evident that  achieves competitive performance with state-of-the-art contrastive methods and FeatRecs, but only with a structure-learning pretext. As indicated by the Avg. Rank, the performance of discrete TopoRecs (, ) in node classification tasks is difficult to emulate the dominant FeatRecs (, ). However,
surpasses both settings of  on 7/8 datasets, surpasses  (one of the most advanced contrastive frameworks) on 6/7 datasets, and outperforms  and  by 1.2 and 2.8 ranks, respectively.
Our work, perhaps surprisingly, shows that fine-grained topological learning can uncover the close relationship between the graph structure and the intrinsic characteristics of node features.

Effect of the masking strategies on the average node classification accuracy (%).

max width=0.48

Variants     Cora     CiteSeer     PubMed

Bernoulli     79.16 ± 0.15     68.60 ± 0.90     82.67 ± 0.40

Uniform     81.36 ± 0.20     70.25 ± 0.55     81.84 ± 0.47

Truncated Gaussian     79.34 ± 0.46     69.95 ± 0.25     82.00 ± 0.56

Boltzmann-Gibbs     84.02 ± 0.09     72.45 ± 0.42     83.31 ± 0.38

Boltzmann-Gibbs, LWM     82.38 ± 0.19     70.75 ± 0.55     81.70 ± 0.57

(Boltzmann-Gibbs, LWP)     84.62 ± 0.37     73.60 ± 0.16     83.53 ± 0.51

§.§ Comparison on Link Prediction (RQ3)

Unlike node classification, our evaluation of link prediction is different from the old routine. Previous TopoRecs directly performed link prediction in an end-to-end manner without probing or fine-tuning since they do the exact same thing for pre-training. However, it is not a self-supervised case and hence not suitable for evaluating self-supervised models. Thus, we utilize a fairer evaluation scheme called dot-product probing, which replaces the original MLP decoder with a dot-product operator $\mathbf{A}_\text{recon}=\sigma(\mathbf{Z}\mathbf{Z}^\top)$, as  does <cit.>. We

employ the dot-product probing instead of the end-to-end training for  as well as all baselines
(note that this may lead to some discordance between our results and those officially reported).
Further analyses of the dot-product probing can be found in Appendix <ref>.

We report Area Under the ROC curve (AUC) and Average Precision (AP) in Table <ref>.
We have several observations. (1) Despite no longer using link prediction for pre-training,  still achieves the best link prediction results. In particular, it
greatly outperforms the performance of  by 20% on Computers.
(2)  gains over 3%-10% improvement compared to the best contrastive results. From the Avg. Rank, the performance of contrastive methods under dot-product probing is less than satisfactory, even for the advanced link prediction model , because they do not explicitly learn graph structures while pre-training.
(3) FeatRecs (, ) do not perform as well as TopoRecs and even traditional autoencoders (, ), since they only pay attention to node features. (4) Some contrastive methods and variational autoencoders
require more memory for large graphs. This highlights the lightweight property of s.

§.§ Ablation Study of Masking Strategies (RQ4)

We have analyzed the strengths of Boltzmann-Gibbs bandwidths and the layer-wise strategy in Section <ref>. To validate these strengths, we experiment with different distributions, including the discrete Bernoulli distribution $M_{ij} \sim Bernoulli(1-p)$, uniform distribution $M_{ij} \sim U(0, 2-2p) (p>0.5)$, truncated Gaussian distribution $\scriptsize M_{ij} \sim \psi(1-p,1,0,2-2p) (p>0.5)$[$\psi(\mu,\sigma^2,a,b)$ denotes a Gaussian distribution $\mathcal{N}(\mu,\sigma^2)$ truncated within the interval $[a,b]$ where $-\infty<a<b<+\infty$.], and the Boltzmann-Gibbs distribution in <ref>
(we ensure that masks sampled from these distributions have the same mask ratio $p$).
These variants only feed the output-layer representations into the decoder. The model employing layer-wise masking only (each layer uses an independent mask set but only the last layer performs the prediction) is referred to as LWM, while the one with both layer-wise masking and prediction is referred to as LWP.
It is obvious from Table <ref> that the model with Boltzmann-Gibbs bandwidths outperforms all models with different mask distributions. Furthermore, 's setting obtains the best node classification performance on all three datasets. Note that the model with LWM only learns suboptimal representations because it only attempts to predict one set of masks while multiple different sets are used.

§ CONCLUSION

This work firstly discusses two limitations in the message propagation of existing discrete TopoRecs, which induce the insufficiency of learning topologically informative representations. To address the issues, we explore non-discrete masking by a novel bandwidth masking and reconstruction scheme. We present our masked graph autoencoder  via the specialized Boltzmann-Gibbs masking and layer-wise prediction, and thoroughly explore its empirical and theoretical superiority. We demonstrate that  can learn more precise graph manifolds and outperform other baselines, including the state-of-the-art contrastive methods and FeatRecs, on link prediction and the feature-related node classification, solely by pre-training on a structure-learning pretext.
While  may not represent the optimal solution, it is the first attempt to explore a new paradigm for masked graph autoencoders that diverges from the discrete mask-then-reconstruct stereotype.

This work is supported by National Natural Science Foundation of China under grants 62376103, 62302184, 62206102, U1936108 and Science and Technology Support Program of Hubei Province under grant 2022BAA046.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Alain and Bengio(2013)]
authorpersonGuillaume Alain and personYoshua Bengio. year2013.
What regularized auto-encoders learn from the data-generating distribution. In booktitleProceedings of the 1st International Conference on Learning Representations.

[Battiston et al(1999)]
authorpersonFederico Battiston, personGiulia Cencetti, personIacopo Iacopini, personVito Latora, personMaxime Lucas, personAlice Patania, personJean-Gabriel Young, and personGiovanni Petri. year1999.
Networks beyond pairwise interactions: Structure and dynamics.
journalScience volume874, number5439 (year1999), pages509–512.

[Becker and Hinton(1992)]
authorpersonSuzanna Becker and personGeoffrey E Hinton. year1992.
Self-organizing neural network that discovers surfaces in random-dot stereograms.
journalNature volume355, number6356 (year1992), pages161–163.

[Chen et al(2020)]
authorpersonTing Chen, personSimon Kornblith, personMohammad Norouzi, and personGeoffrey Hinton. year2020.
A simple framework for contrastive learning of visual representations. In booktitleProceedings of the 37th International Conference on Machine Learning. pages1597–1607.

[Clevert et al(2016)]
authorpersonDjork-Arné Clevert, personThomas Unterthiner, and personSepp Hochreiter. year2016.
Fast and accurate deep network learning by exponential linear units (elus). In booktitleProceedings of the 4th International Conference on Learning Representations.

[Defferrard et al(2017)]
authorpersonMichaël Defferrard, personLionel Martin, personRodrigo Pena, and personNathanaël Perraudin. year2017.
PyGSP: Graph signal processing in Python.

[Devlin et al(2019)]
authorpersonJacob Devlin, personMing-Wei Chang, personKenton Lee, and personKristina Toutanova. year2019.
BERT: Pre-training of deep bidirectional transformers for language understanding. In booktitleProceedings of the 2019 Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pages4171–4186.

[Fey and Lenssen(2019)]
authorpersonMatthias Fey and personJan Eric Lenssen. year2019.
Fast graph representation learning with PyTorch Geometric. In booktitleICLR Workshop on Representation Learning on Graphs and Manifolds.

[Fountoulakis et al(2023)]
authorpersonKimon Fountoulakis, personAmit Levi, personShenghao Yang, personAseem Baranwal, and personAukosh Jagannath. year2023.
Graph attention retrospective.
journalJournal of Machine Learning Research volume24, number246 (year2023), pages1–52.

[Glorot and Bengio(2010)]
authorpersonXavier Glorot and personYoshua Bengio. year2010.
Understanding the difficulty of training deep feedforward neural networks. In booktitleProceedings of the 13th International Conference on Artificial Intelligence and Statistics. pages249–256.

[Gui et al(2022)]
authorpersonShurui Gui, personHao Yuan, personJie Wang, personQicheng Lao, personKang Li, and personShuiwang Ji. year2022.
titleFlowX: Towards explainable graph neural networks via message flows.

[Hasanzadeh et al(2019)]
authorpersonArman Hasanzadeh, personEhsan Hajiramezanali, personKrishna Narayanan, personNick Duffield, personMingyuan Zhou, and personXiaoning Qian. year2019.
Semi-implicit graph variational auto-encoders. In booktitleProceedings of the 33rd Conference on Neural Information Processing Systems.

[He et al(2022)]
authorpersonKaiming He, personXinlei Chen, personSaining Xie, personYanghao Li, personPiotr Dollár, and personRoss Girshick. year2022.
Masked autoencoders are scalable vision learners. In booktitleProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pages16000–16009.

[He et al(2020)]
authorpersonKaiming He, personHaoqi Fan, personYuxin Wu, personSaining Xie, and personRoss Girshick. year2020.
Momentum contrast for unsupervised visual representation learning. In booktitleProceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. pages9729–9738.

[Hjelm et al(2019)]
authorpersonR Devon Hjelm, personAlex Fedorov, personSamuel Lavoie-Marchildon, personKaran Grewal, personPhil Bachman, personAdam Trischler, and personYoshua Bengio. year2019.
Learning deep representations by mutual information estimation and maximization. In booktitleProceedings of the 7th International Conference on Learning Representations.

[Hou et al(2023)]
authorpersonZhenyu Hou, personYufei He, personYukuo Cen, personXiao Liu, personYuxiao Dong, personEvgeny Kharlamov, and personJie Tang. year2023.
GraphMAE2: A decoding-enhanced masked self-supervised graph learner. In booktitleProceedings of the 32nd ACM Web Conference. pages737–746.

[Hou et al(2022)]
authorpersonZhenyu Hou, personXiao Liu, personYukuo Cen, personYuxiao Dong, personHongxia Yang, personChunjie Wang, and personJie Tang. year2022.
GraphMAE: Self-supervised masked graph autoencoders. In booktitleProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pages594–604.

[Hu et al(2020)]
authorpersonWeihua Hu, personMatthias Fey, personMarinka Zitnik, personYuxiao Dong, personHongyu Ren, personBowen Liu, personMichele Catasta, and personJure Leskovec. year2020.
Open graph benchmark: Datasets for machine learning on graphs. In booktitleProceedings of the 34th Conference on Neural Information Processing Systems. pages5812–5823.

[Hyvärinen and Dayan(2005)]
authorpersonAapo Hyvärinen and personPeter Dayan. year2005.
Estimation of non-normalized statistical models by score matching.
journalJournal of Machine Learning Research volume6, number4 (year2005).

[Ioffe and Szegedy(2015)]
authorpersonSergey Ioffe and personChristian Szegedy. year2015.
Batch normalization: Accelerating deep network training by reducing internal covariate shift. In booktitleProceedings of the 32nd International Conference on Machine Learning. pages448–456.

[Jaiswal et al(2020)]
authorpersonAshish Jaiswal, personAshwin Ramesh Babu, personMohammad Zaki Zadeh, personDebapriya Banerjee, and personFillia Makedon. year2020.
A survey on contrastive self-supervised learning.
journalTechnologies volume9, number1 (year2020).

[Kamyshanska and Memisevic(2013)]
authorpersonHanna Kamyshanska and personRoland Memisevic. year2013.
On autoencoder scoring. In booktitleProceedings of the 30th International Conference on Machine Learning. pages720–728.

[Kim and Oh(2021)]
authorpersonDongkwan Kim and personAlice Oh. year2021.
How to find your friendly neighborhood: Graph attention design with self-supervision. In booktitleProceedings of the 9th International Conference on Learning Representations.

[Kingma and Ba(2015)]
authorpersonDiederik P Kingma and personJimmy Ba. year2015.
Adam: A method for stochastic optimization. In booktitleProceedings of the 3rd International Conference on Learning Representations.

[Kipf and Welling(2016)]
authorpersonThomas N Kipf and personMax Welling. year2016.
Variational graph auto-encoders. In booktitleNIPS Workshop on Bayesian Deep Learning.

[Kipf and Welling(2017)]
authorpersonThomas N Kipf and personMax Welling. year2017.
Semi-supervised classification with graph convolutional networks. In booktitleProceedings of the 5th International Conference on Learning Representations.

[LeCun et al(2006)]
authorpersonYann LeCun, personSumit Chopra, personRaia Hadsell, personM Ranzato, and personFujie Huang. year2006.
A tutorial on energy-based learning.
journalPredicting Structured Data volume1, number0 (year2006).

[Li et al(2023a)]
authorpersonJuanhui Li, personHarry Shomer, personHaitao Mao, personShenglai Zeng, personYao Ma, personNeil Shah, personJiliang Tang, and personDawei Yin. year2023a.
Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. In booktitleProceedings of the 37th Conference on Neural Information Processing Systems.

[Li et al(2023b)]
authorpersonJintang Li, personRuofan Wu, personWangbin Sun, personLiang Chen, personSheng Tian, personLiang Zhu, personChanghua Meng, personZibin Zheng, and personWeiqiang Wang. year2023b.
What's behind the mask: Understanding masked graph modeling for graph autoencoders. In booktitleProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pages1268–1279.

[Li et al(2019)]
authorpersonMufei Li, personHao Zhang, personXingjian Shi, personMinjie Wang, and personZheng Zhang. year2019.
A statistical characterization of attentions in graph neural networks. In booktitleICLR Workshop on Representation Learning on Graphs and Manifolds.

[Li et al(2023c)]
authorpersonXiang Li, personTiandi Ye, personCaihua Shan, personDongsheng Li, and personMing Gao. year2023c.
SeeGera: Self-supervised semi-implicit graph variational auto-encoders with masking. In booktitleProceedings of the 32nd ACM Web Conference. pages143–153.

[Liu et al(2022)]
authorpersonYixin Liu, personMing Jin, personShirui Pan, personChuan Zhou, personYu Zheng, personFeng Xia, and personPhilip S. Yu. year2022.
Graph self-supervised learning: A survey.
journalIEEE Transactions on Knowledge and Data Engineering volume35, number6 (year2022), pages5879–5900.

[Mernyei and Cangea(2020)]
authorpersonPéter Mernyei and personCătălina Cangea. year2020.
Wiki-CS: A wikipedia-based benchmark for graph neural networks. In booktitleICML Workshop on Graph Representation Learning and Beyond.

[Oord et al(2018)]
authorpersonAaron van den Oord, personYazhe Li, and personOriol Vinyals. year2018.
titleRepresentation learning with contrastive predictive coding.

[Pan et al(2018)]
authorpersonS Pan, personR Hu, personG Long, personJ Jiang, personL Yao, and personC Zhang. year2018.
Adversarially regularized graph autoencoder for graph embedding. In booktitleProceedings of the 27th International Joint Conference on Artificial Intelligence. pages2609–2615.

[Paszke et al(2019)]
authorpersonAdam Paszke, personSam Gross, personFrancisco Massa, personAdam Lerer, personJames Bradbury, personGregory Chanan, personTrevor Killeen, personZeming Lin, personNatalia Gimelshein, personLuca Antiga, et al year2019.
PyTorch: An imperative style, high-performance deep learning library. In booktitleProceedings of the 33rd Conference on Neural Information Processing Systems.

[Qin et al(2022)]
authorpersonZhen Qin, personWeixuan Sun, personHui Deng, personDongxu Li, personYunshen Wei, personBaohong Lv, personJunjie Yan, personLingpeng Kong, and personYiran Zhong. year2022.
cosFormer: Rethinking softmax in attention. In booktitleProceedings of the 10th International Conference on Learning Representations.

[Rusch et al(2023)]
authorpersonT Konstantin Rusch, personMichael M Bronstein, and personSiddhartha Mishra. year2023.
titleA survey on oversmoothing in graph neural networks.

[Sen et al(2008)]
authorpersonPrithviraj Sen, personGalileo Namata, personMustafa Bilgic, personLise Getoor, personBrian Galligher, and personTina Eliassi-Rad. year2008.
Collective classification in network data.
journalAI Magazine volume29, number3 (year2008), pages93–106.

[Shchur et al(2018)]
authorpersonOleksandr Shchur, personMaximilian Mumme, personAleksandar Bojchevski, and personStephan Günnemann. year2018.
Pitfalls of graph neural network evaluation. In booktitleNIPS Workshop on Relational Representation Learning.

[Shiao et al(2023)]
authorpersonWilliam Shiao, personZhichun Guo, personTong Zhao, personEvangelos E Papalexakis, personYozen Liu, and personNeil Shah. year2023.
Link prediction with non-contrastive learning. In booktitleProceedings of the 11th International Conference on Learning Representations.

[Song and Ermon(2019)]
authorpersonYang Song and personStefano Ermon. year2019.
Generative modeling by estimating gradients of the data distribution. In booktitleProceedings of the 33rd Conference on Neural Information Processing Systems.

[Swersky et al(2011)]
authorpersonKevin Swersky, personMarc'Aurelio Ranzato, personDavid Buchman, personNando D Freitas, and personBenjamin M Marlin. year2011.
On autoencoders and score matching for energy based models. In booktitleProceedings of the 28th International Conference on Machine Learning. pages1201–1208.

[Tan et al(2023)]
authorpersonQiaoyu Tan, personNinghao Liu, personXiao Huang, personSoo-Hyun Choi, personLi Li, personRui Chen, and personXia Hu. year2023.
S2GAE: Self-supervised graph autoencoders are generalizable learners with graph masking. In booktitleProceedings of the Sixteenth ACM International Conference on Web Search and Data Mining. pages787–795.

[Van der Maaten and Hinton(2008)]
authorpersonLaurens Van der Maaten and personGeoffrey Hinton. year2008.
Visualizing data using t-SNE.
journalJournal of Machine Learning Research volume9, number86 (year2008), pages2579–2605.

[Veličković et al(2018)]
authorpersonPetar Veličković, personGuillem Cucurull, personArantxa Casanova, personAdriana Romero, personPietro Lio, and personYoshua Bengio. year2018.
Graph attention networks. In booktitleProceedings of the 6th International Conference on Learning Representations.

[Veličković et al(2019)]
authorpersonPetar Veličković, personWilliam Fedus, personWilliam L Hamilton, personPietro Liò, personYoshua Bengio, and personR Devon Hjelm. year2019.
Deep graph infomax. In booktitleProceedings of the 7th International Conference on Learning Representations.

[Vincent et al(2008)]
authorpersonPascal Vincent, personHugo Larochelle, personYoshua Bengio, and personPierre-Antoine Manzagol. year2008.
Extracting and composing robust features with denoising autoencoders. In booktitleProceedings of the 25th International Conference on Machine Learning. pages1096–1103.

[Wei et al(2022)]
authorpersonChunyu Wei, personJian Liang, personDi Liu, and personFei Wang. year2022.
Contrastive graph structure learning via information bottleneck for recommendation. In booktitleProceedings of the 36th Conference on Neural Information Processing Systems. pages20407–20420.

[Yosinski et al(2014)]
authorpersonJason Yosinski, personJeff Clune, personYoshua Bengio, and personHod Lipson. year2014.
How transferable are features in deep neural networks?. In booktitleProceedings of the 28th Conference on Neural Information Processing Systems.

authorpersonWayne W Zachary. year1977.
An information flow model for conflict and fission in small groups.
journalJournal of Anthropological Research volume33, number4 (year1977), pages452–473.

[Zhang et al(2021)]
authorpersonHengrui Zhang, personQitian Wu, personJunchi Yan, personDavid Wipf, and personPhilip S Yu. year2021.
From canonical correlation analysis to self-supervised graph neural networks. In booktitleProceedings of the 35th Conference on Neural Information Processing Systems. pages76–89.

[Zhang et al(2022a)]
authorpersonSixiao Zhang, personHongxu Chen, personHaoran Yang, personXiangguo Sun, personPhilip S Yu, and personGuandong Xu. year2022a.
titleGraph masked autoencoders with transformers.

[Zhang et al(2022b)]
authorpersonYifei Zhang, personHao Zhu, personZixing Song, personPiotr Koniusz, and personIrwin King. year2022b.
COSTA: Covariance-preserving feature augmentation for graph contrastive learning. In booktitleProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pages2524–2534.

[Zhou et al(2021)]
authorpersonKaixiong Zhou, personXiao Huang, personDaochen Zha, personRui Chen, personLi Li, personSoo-Hyun Choi, and personXia Hu. year2021.
Dirichlet energy constrained learning for deep graph neural networks. In booktitleProceedings of the 35th Conference on Neural Information Processing Systems. pages21834–21846.

[Zhu et al(2020)]
authorpersonYanqiao Zhu, personYichen Xu, personFeng Yu, personQiang Liu, personShu Wu, and personLiang Wang. year2020.
Deep graph contrastive representation learning. In booktitleICML Workshop on Graph Representation Learning and Beyond.

[Zhu et al(2021)]
authorpersonYanqiao Zhu, personYichen Xu, personFeng Yu, personQiang Liu, personShu Wu, and personLiang Wang. year2021.
Graph contrastive learning with adaptive augmentation. In booktitleProceedings of the 30th ACM Web Conference 2021. pages2069–2080.

§ MORE THEORETICAL DETAILS

This section gives the detailed proofs of propositions and theorems.

§.§ Proof of Theorem <ref>

It is obvious that the unmasked ego-graph $\mathcal{G}_{i,m}$ has $p(n_i - 1) + 1$ nodes. So

\begin{align}
& E_D(\mathcal{G}_{i}) - E_D(\mathcal{G}_{i,m}) \notag\\
&= \frac{n_i-1}{n_i}\|\boldsymbol{X}_i^{\mathcal{G}_{i}}-\boldsymbol{X}_j^{\mathcal{G}_{i}}\|^2 - \frac{p(n_i-1)}{p(n_i-1)+1}\|\boldsymbol{X}_i^{\mathcal{G}_{i}}-\boldsymbol{X}_j^{\mathcal{G}_{i}}\|^2 \notag\\
&= \frac{(n_i-1)(p(n_i-1)+1)-pn_i(n_i-1)}{pn_i(n_i-1)+n_i}\|\boldsymbol{X}_i^{\mathcal{G}_{i}}-\boldsymbol{X}_j^{\mathcal{G}_{i}}\|^2 \notag\\
&= \frac{(n_i-1)(1-p)}{pn_i(n_i-1)+n_i}\|\boldsymbol{X}_i^{\mathcal{G}_{i}}-\boldsymbol{X}_j^{\mathcal{G}_{i}}\|^2 \notag\\
&\ge 0
\end{align}

and $E_D(\mathcal{G}_{i}) - E_D(\mathcal{G}_{i,m}) = 0$ iff $p=1$.

§.§ Proof of Proposition <ref>

Under the assumption of $\tilde{\boldsymbol{T}}_{j}\sim\mathcal{N}(\boldsymbol{\mu}_{\tilde{\boldsymbol{T}}_{j}},\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}})$ and $\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}}=c\mathbf{I}$, $r_{\mathbf{X}}(\tilde{\boldsymbol{T}}_{j})$ is a predictor of the Gaussian mean $\boldsymbol{\mu}_{\tilde{\boldsymbol{T}}_{j}}$. As such, the negative log likelihood in <ref> can be rewritten as an $\ell_2$ error of topological encoding:

\begin{align}
\mathcal{L} &= -\mathbb{E}_{j\in\mathcal{V}}[\log r_{\mathbf{X}}(\tilde{\boldsymbol{T}}_{j})] \notag\\
&= -\mathbb{E}_{j\in\mathcal{V}}\left[\log \frac{\exp\left(-\frac{1}{2}(r_{\mathbf{X}}(\tilde{\boldsymbol{T}}_{j})-\tilde{\boldsymbol{T}}_{j})^\top\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}}^{-1}(r_{\mathbf{X}}(\tilde{\boldsymbol{T}}_{j})-\tilde{\boldsymbol{T}}_{j})\right)  }{(2\pi)^\frac{n}{2}\det(\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}})^\frac{1}{2}}
\right] \notag\\
&=\frac{1}{2c}\mathbb{E}_{j\in\mathcal{V}}\left[(r_{\mathbf{X}}(\tilde{\boldsymbol{T}}_{j})-\tilde{\boldsymbol{T}}_{j})^\top(r_{\mathbf{X}}(\tilde{\boldsymbol{T}}_{j})-\tilde{\boldsymbol{T}}_{j}) \right] \notag\\
& \quad\quad + \underbracket[0.8pt][3pt]{\log ((2\pi)^\frac{n}{2}\det(\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}})^\frac{1}{2})}_{\boldsymbol{const}} \notag\\
&\propto \mathbb{E}_{j\in\mathcal{V}}[\| r_{\mathbf{X}}(\tilde{\boldsymbol{T}}_{j}) - \tilde{\boldsymbol{T}}_{j} \|^2]
\end{align}

expanding $r_{\mathbf{X}}(\cdot)$ with the first-order Taylor series yields

\begin{equation}
r_{\mathbf{X}}(\tilde{\boldsymbol{T}}_{j}) = r_{\mathbf{X}}(\boldsymbol{T}_{j} + \epsilon) = r_{\mathbf{X}}(\boldsymbol{T}_{j}) + \nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})\epsilon + o(\epsilon^\top\epsilon)
\end{equation}

and we have

\begin{align}
\mathcal{L} &= \mathbb{E}_{j\in\mathcal{V}}[\| r_{\mathbf{X}}(\boldsymbol{T}_{j}) + \nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})\epsilon - (\boldsymbol{T}_{j} + \epsilon) + o(\epsilon^\top\epsilon) \|^2] \notag\\
&= \mathbb{E}_{j\in\mathcal{V}}[\| (r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_{j}) + (\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})\epsilon - \epsilon)\|^2] + o(\sigma_{\epsilon}^2) \notag\\
&= \mathbb{E}_{j\in\mathcal{V}}[\| r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_{j} \|^2] \notag\\
& \quad + 2 \mathbb{E}_{j\in\mathcal{V}}[\epsilon]^\top\mathbb{E}_{j\in\mathcal{V}}[(\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \mathbf{I})^\top(r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_{j})] \notag\\
& \quad + \left(\mathbb{E}_{j\in\mathcal{V}}[\| \nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})\epsilon \|^2] + \mathbb{E}_{j\in\mathcal{V}}[\epsilon^\top\epsilon] \right. \notag\\
& \left. \quad - 2 \mathbb{E}_{j\in\mathcal{V}}[\epsilon]^\top\mathbb{E}_{j\in\mathcal{V}}[\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})]
\vphantom{\mathbb{E}_{j\in\mathcal{V}}[\| \nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})\epsilon \|^2] + \mathbb{E}_{j\in\mathcal{V}}[\epsilon^\top\epsilon]}\right) + o(\sigma_{\epsilon}^2) \notag\\
&= \mathbb{E}_{j\in\mathcal{V}}[\| r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_{j} \|^2] \notag\\
&\quad+ \text{tr}(\mathbb{E}_{j\in\mathcal{V}}[\epsilon\epsilon^\top]\mathbb{E}_{j\in\mathcal{V}}[\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})^\top\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})]) \notag\\
& \quad + 2\mu_{\epsilon}^\top\mathbb{E}_{j\in\mathcal{V}}[(\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \mathbf{I})^\top(r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_{j})] \notag\\
& \quad - 2\mu_{\epsilon}^\top\mathbb{E}_{j\in\mathcal{V}}[\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})]
+ o(\sigma_{\epsilon}^2)
\end{align}

As the noise vector of each ego-graph $\mathcal{G}_i$ is a probabilistic simplex, the mean of noises over every edge in $\mathcal{G}_i$ is $1/\text{deg}(i)$. This derives the statistical mean of bandwidths on the entire graph $\mu_{\boldsymbol{\epsilon}}$ as

\begin{equation}\label{eq:noisemean}
\mu_{\boldsymbol{\epsilon}} = \frac{1}{2|\mathcal{E}|}\sum_{i\in\mathcal{V}}{\text{deg}(i)\cdot\frac{1}{\text{deg}(i)}} = \frac{n}{2|\mathcal{E}|}
\end{equation}

Therefore, $\mu_{\epsilon}\rightarrow 0$ when $n \ll 2|\mathcal{E}|$. In that case,

\begin{align}
\mathcal{L} &= \mathbb{E}_{j\in\mathcal{V}}[\| r_{\mathbf{X}}(\boldsymbol{T}_{j})\!-\!\boldsymbol{T}_{j} \|^2] + \sigma_{\epsilon}^2\text{tr}(\mathbb{E}_{j\in\mathcal{V}}[\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})^\top\nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})]) + o(\sigma_{\epsilon}^2) \notag\\
&= \mathbb{E}_{j\in\mathcal{V}}[\| r_{\mathbf{X}}(\boldsymbol{T}_{j})\!-\!\boldsymbol{T}_{j} \|^2] + \sigma_{\epsilon}^2 \mathbb{E}_{j\in\mathcal{V}}[\| \nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})\|^2_F] + o(\sigma_{\epsilon}^2)
\end{align}

§.§ Proof of Theorem <ref>

We follow <cit.> to complete the proof. From a generative perspective, one may consider the edge set of $\mathcal{G}_j$ as a sampled subset from $p(\boldsymbol{T}_j)$. Let

\begin{align}\label{eq:functionaldef}
f(\boldsymbol{T}_{j},r_{\mathbf{X}},\nabla r_{\mathbf{X}}) &:= p(\boldsymbol{T}_j)(\mathbb{E}_{j\in\mathcal{V}}[\| r_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_{j} \|^2] \notag\\
&\quad\quad + \sigma_{\epsilon}^2 \mathbb{E}_{j\in\mathcal{V}}[\| \nabla r_{\mathbf{X}}(\boldsymbol{T}_{j})\|^2_F])
\end{align}

Then the bandwidth prediction in <ref> can be transformed into finding the extremum of an integral functional $\mathcal{L}(r_{\mathbf{X}})$:

\begin{equation}
r^* = \arg \min \mathcal{L}(r_{\mathbf{X}}) , \\
s.t. \ \mathcal{L}(r_{\mathbf{X}}) = \int_{\mathbb{R}^n}{f(\boldsymbol{T}_{j},r_{\mathbf{X}},\nabla r_{\mathbf{X}})\text{d}\boldsymbol{T}_j}
\end{equation}

Despite a multivariate functional, it can be split into individual components:

\begin{equation}\small
\mathcal{L}(r_{\mathbf{X}}) = \sum_{i=1}^{n}\int_{\mathbb{R}^n}{p(\boldsymbol{T}_j)\left(( r_{\mathbf{X},i}(\boldsymbol{T}_{j}) - T_{ij})^2 + \sigma_{\epsilon}^2 \sum_{k=1}^{n}{\left(\displaystyle\frac{\partial r_{\mathbf{X},i}(\boldsymbol{T}_{j})}{\partial T_{kj}} \right)^2}\right)\text{d}\boldsymbol{T}_j} \\
\end{equation}

We know by the Euler-Langrage equation that the optimal $r^*$ satisfies

\begin{equation}\label{eq:euler-langrage}
\frac{\partial f}{\partial r_{\mathbf{X}}} \bigg|_{r^*} - \frac{\text{d}}{\text{d}\boldsymbol{T}_j}\frac{\partial f}{\partial \nabla r_{\mathbf{X}}} \bigg|_{r^*} = 0
\end{equation}

By <ref>, we have

\begin{equation}\label{eq:el-leftderivative}
\displaystyle\frac{\partial f}{\partial r_{\mathbf{X}}} = 2(r_{\mathbf{X},i}(\boldsymbol{T}_{j}) - T_{ij})p(\boldsymbol{T}_j),
\end{equation}

\begin{align}
\displaystyle\frac{\partial f}{\partial (\nabla r_{\mathbf{X}})_i} &= 2\sigma_{\epsilon}^2 p(\boldsymbol{T}_j) \left[\displaystyle\frac{\partial r_{\mathbf{X},k}(\boldsymbol{T}_{j})}{\partial T_{ij}} \right]_{k}^\top  \\\label{eq:el-rightderivative}
\Rightarrow \displaystyle\frac{\partial}{\partial T_{ij}}\displaystyle\frac{\partial f}{\partial (\nabla r_{\mathbf{X}})_i} &= 2\sigma_{\epsilon}^2 \left(\textstyle\frac{\partial p(\boldsymbol{T}_j)}{\partial T_{ij}} \left[\textstyle\frac{\partial r_{\mathbf{X},k}(\boldsymbol{T}_{j})}{\partial T_{ij}}\right]_{k}^\top
+ p(\boldsymbol{T}_j) \left[\textstyle\frac{\partial^2 r_{\mathbf{X},k}(\boldsymbol{T}_{j})}{\partial T_{ij}^2}\right]_{k}^\top \right)
\end{align}

Putting <ref> and <ref> into <ref> yields

\begin{align}\label{eq:tobesolved}
r_{\mathbf{X},k}(\boldsymbol{T}_{j}) - T_{kj} &= \frac{\sigma_{\epsilon}^2}{p(\boldsymbol{T}_{j})}\sum_{i=1}^{n}{\left(\displaystyle\frac{\partial p(\boldsymbol{T}_{j})}{\partial T_{ij}} \displaystyle\frac{\partial r_{\mathbf{X},k}(\boldsymbol{T}_{j})}{\partial T_{ij}} + p(\boldsymbol{T}_{j})\displaystyle\frac{\partial^2 r_{\mathbf{X},k}(\boldsymbol{T}_{j})}{\partial T_{ij}^2} \right)} \notag\\
&= \sigma_{\epsilon}^2 \sum_{i=1}^{n}{\left(\displaystyle\frac{\partial \log{p(\boldsymbol{T}_{j})}}{\partial T_{ij}} \displaystyle\frac{\partial r_{\mathbf{X},k}(\boldsymbol{T}_{j})}{\partial T_{ij}} + \displaystyle\frac{\partial^2 r_{\mathbf{X},k}(\boldsymbol{T}_{j})}{\partial T_{ij}^2} \right)}
\end{align}

<cit.> gives an analytical solution of <ref> when $\sigma_{\epsilon}^2 \rightarrow 0$:

\begin{equation}
r^*_{\mathbf{X},k}(\boldsymbol{T}_{j})\bigg|_{\sigma_{\epsilon}^2 \rightarrow 0} = T_{kj} + \sigma_{\epsilon}^2\displaystyle\frac{\partial \log{p(\boldsymbol{T}_{j})}}{\partial T_{ij}}+o(\sigma_{\epsilon}^2)
\end{equation}

so the proof concludes:

\begin{equation}
r^*_{\mathbf{X}}(\boldsymbol{T}_{j}) - \boldsymbol{T}_j \propto \nabla \log{p(\boldsymbol{T}_{j})}
\end{equation}

This indicates that the perturbed topological encoding manifold $p(\tilde{\mathbf{T}})$ is approximately equal to the original manifold $p(\mathbf{T})$ when $\boldsymbol{\epsilon}$ is small enough. Hence, despite the changing bandwidths, the optimizing objective remains invariant as the topological manifold of the original graph data.

§.§ Mildness of Assumptions

§.§.§ The noise mean $\mu_{\boldsymbol{\epsilon}}$.

Proposition <ref> and Theorem <ref> hold under $n \ll 2|\mathcal{E}|$, that is, the mean of bandwidths over every edge needs to be small enough (in other words, the mask ratio needs to be close to 1). According to <ref>, 's mask ratio is fixed as $p=1-\mu_{\boldsymbol{\epsilon}}=1-n/2|\mathcal{E}_{train}|$, which is very large in large-scale networks (and even larger in practice because the graph data is not always connected), thus the assumption can be easily satisfied. For discrete TopoRecs, this also implies that little information is available during training. Yet,  keeps the global topology intact, which is conducive to mitigating the impact of the extremely high mask ratio. The mask ratios of  throughout our experiments are listed in Table <ref>, where “Calculated” represents the mask ratios calculated by $p =1-n/2|\mathcal{E}_{train}|$, and “Measured” represents the actual mask ratios measured during training.

Mask ratios of  on various datasets.

max width=0.48

Dataset     1cCalculated     1cMeasured

Cora     0.6983     0.7077

CiteSeer     0.5702     0.6048

PubMed     0.7383     0.7571

Photo     0.9622     0.9630

Computers     0.9671     0.9679

CS     0.8683     0.8697

Physics     0.9182     0.9185

ogbn-arxiv     0.9140     0.9158

ogbl-collab     0.8840     0.8995

§.§.§ The covariance $\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}}$.

Another prerequisite of Proposition <ref> and Theorem <ref> is that the covariance of $\{\tilde{\boldsymbol{T}}_{j}\}_{j=1}^{n}$ should satisfy $\mathbf{\Sigma}_{\tilde{\boldsymbol{T}}_{j}}=c\mathbf{I}$ with an arbitrary constant $c$. It is obvious that $c$ is the variance of noise $\sigma_\epsilon$, so we mainly focus on the diagonal covariance matrix, which implies the independence between every two different entries of $\tilde{\boldsymbol{T}}_{j}$. As

\begin{align}
\mathbb{E}[\tilde{T}_{ij}\tilde{T}_{kj}] &= \mathbb{E}[(T_{ij} + \epsilon_{ij})(T_{kj} + \epsilon_{kj})] \notag\\
&= \mathbb{E}[T_{ij}T_{kj} + T_{ij}\epsilon_{kj} + T_{kj}\epsilon_{ij} + \epsilon_{ij}\epsilon_{kj}] \notag\\
&= \mathbb{E}[T_{ij}T_{kj}] + \mathbb{E}[T_{ij}]\mathbb{E}[\epsilon_{kj}] + \mathbb{E}[T_{kj}]\mathbb{E}[\epsilon_{ij}] + \mathbb{E}[\epsilon_{ij}]\mathbb{E}[\epsilon_{kj}] \notag\\
&= \mathbb{E}[T_{ij}T_{kj}] + \mathbb{E}[T_{ij} + \epsilon_{ij}]\mathbb{E}[T_{kj} + \epsilon_{kj}] - \mathbb{E}[T_{ij}]\mathbb{E}[T_{kj}] \notag\\
&= \mathbb{E}[\tilde{T}_{ij}]\mathbb{E}[\tilde{T}_{kj}] + \mathbb{E}[T_{ij}T_{kj}] - \mathbb{E}[T_{ij}]\mathbb{E}[T_{kj}]
\end{align}

for any $i, k \in \mathcal{N}_j, i \ne k$, it is equivalent to the independence of the local topology $\{T_{ij}\}_{i \in \mathcal{N}_j}$ of every node $j$, i.e. every two incoming edges of $j$ should be independent.
While node relationships in real-world networks are more likely to be correlated, this assumption is introduced for the brevity of the mathematical derivation of Proposition <ref> and Theorem <ref>. Whether they still hold without this assumption necessitates further mathematical analysis.

Node embedding visualization of different masking strategies.

§ MORE VISUALIZATIONS

In this section, we illustrate our embedding visualization study in Figure <ref> to support the global and local informativeness of  in Subsection <ref>.
We conduct the experiment on Karate Club <cit.>, a widely used real-world network dataset containing 34 nodes (numbered 0–33 in in Figure <ref>(a)) and 156 undirected edges. Each node is assigned by a column of the identity matrix $\mathbf{I}_n$ as features.
is trained on Karate Club with three masking setups: discrete masking (left column), uniformized masking (center column), and bandwidth masking (right column). Configurations of these setups are the same as those used in our ablation studies (Subsection <ref>). Afterwards, we visualize the node embeddings in a 2-dimensional embedding space by t-SNE <cit.>, as in Figure <ref>(h-j).
We mainly focus on three types of node groups, as shown in Figure <ref>(a):

* Community group, a conspicuous cluster adjacent to node 0. Members include 4, 5, 6, 10, and 16.

* Between-community group, consisting of nodes located between both two clubs founded by the hub node 0 (Mr. Hi) and 33 (John A). They form two main clusters by influencing their neighboring nodes. However, between-community group members like 8, 9, 27, and 28 are similarly affected by both clubs.

* Topological equivalence group, consisting of nodes that share their neighborhood: every member (14, 15, 18, 20, 22) is connected and only connected to node 32 and 33.

Result analysis. According to the left column (Figure <ref>(b), (e), (h)), discrete masking firstly undermines the graph topology by creating isolated nodes. For example, node 16 and 18 behave abnormally in the latent graph: as the message flows from 16 are blocked, it is detached from the community group, and finally drifts away from the community group cluster in the embedding space. On the other hand, the topological equivalence of 18 is not preserved due to the masking, causing it to be far away from other topological equivalence group members in the embedding space. These observations indicate that discrete edge masking obstructs the message flows that may be crucial to the sink nodes.

According to the center column (Figure <ref>(c), (f), (i)), uniformized masking has partially resolved the isolation issues above, with 16 and 18 joined clusters they belong to. This verifies the global informativeness of non-discrete masking. However, masks sampled from a uniform distribution do not provide local informativeness. With no effort in distinguishing neighbors, node 2 is overlooked by its neighboring node 27 and is pulled towards the club of node 33, resulting in the deviation from the between-community group.

Finally, the right column (Figure <ref>(d), (g), (j)) tells that bandwidth masking preserves the node relations of all three groups, so we have verified both the global informativeness and the local informativeness of bandwidth masking.

§ MORE DISCUSSIONS

This section discusses connections between  and other deep learning models, including graph attention models, score-based models, and energy-based models. Our discussions shed light on the reliability of  from different perspectives, and we hope they will lead to deeper insights in the future.

§.§ Graph Attention Models

The way we use bandwidth to do weighted message propagation is inspired by the graph self-attention mechanism <cit.>.
Existing studies have pointed out that attention weights should be able to distinguish different edges <cit.>, and softmax-based attention can amplify the dispersion of attention weights to be more discriminative <cit.>. Therefore, we hold that it is beneficial to generate bandwidth values from a softmax-amplified distribution, i.e. the Boltzmann-Gibbs distribution. Yet, our bandwidth masking and graph attention mechanisms are fundamentally different. Graph attention models empirically fit a locally optimal weight distribution of neighborhood, in which the parameter matrices converge as training goes on. Our bandwidth masking strategy does not learn the weights, but randomly generates them parameter-free. For every iteration, each edge is randomly assigned a different bandwidth, so that different neighbors will be noticed every time to help the encoder distinguish their messages. Plus, the layer-wise masking is inspired by  <cit.> which, however, does not give any explanations, discussions, or even empirical results in terms of the layer-wise approach. Our work also bridges this gap.

is currently not able to directly pre-train GAT and Graph Transformers as it also assigns weights to every edge in message propagation. It needs to be adjusted to accommodate bandwidths and attention weights. How to improve the topological learning performance of graph attention-based networks in self-supervision now remains an interesting future work.

§.§ Score-based & Energy-based Models

By Theorem <ref>, bandwidth prediction is equivalent to optimizing the gradient of a log probability $\nabla\log{p(\boldsymbol{T}_{j})}$. This is also called a “score” in the field of generation, which can be directly estimated by Score Matching <cit.>
to generate samples that match the original data distribution. Therefore,  can be seen as an implicit score-based model that adds Gaussian noise to the graph topology and learns its score.

Energy-based models (EBMs) <cit.> perform an alternate optimization process: (1) optimizing the output, and (ii) optimizing the energy. (i) The forward pass (or inference) of the model $f(x; \Theta):x \mapsto y$ is viewed as finding the local minimum point $y^*$ on a manifold $E_\Theta \in \mathcal{F}$. Here $E_\Theta:\mathcal{X}\times\mathcal{Y}\rightarrow\mathbb{R}$ is a scoring function of the input-output pair $(x,y)$, judging whether the output $y$ matches $x$ the best. $\mathcal{F}$ is the function space of $E_\Theta$. $E_\Theta(x,y)$ is smaller if $y$ better matches $x$. As the learning process goes on, $y$ has an increasing tendency for minimizing $E_\Theta(x,y)$, and $y=y^*$ when the model converges. Analogous to the principle of minimum energy in thermodynamics, $E_\Theta$ is called an energy function. (2) The backward pass of $f(x, \Theta)$ searchs on $\mathcal{F}$ for the optimal $E_\Theta$ that meets the above conditions. As the learning process goes on, $E_\Theta(x,y)$ has an increasing tendency to assign lower energy values to more compatible $(x,y)$ pairs and vice versa.

Probabilistic discriminative models $f(\boldsymbol{x}; \Theta):\boldsymbol{x} \mapsto \hat{\boldsymbol{y}}$ based on maximum likelihood estimation can directly define the energy as its negative output logit (i.e. the unnormalized probability) because it indicates which $\hat{\boldsymbol{y}}$ matches $x$ the best. However, as a non-probabilistic model, an autoencoder cannot define the energy in this way. This issue has been solved by <cit.> who state that the reconstruction of denoising autoencoders is equivalent to performing regularized score matching, and the energy function can be derived using the antiderivative of the score (for any output $\hat{y}$):

\begin{equation}\label{eq:aeenergy}
E_\Theta(\boldsymbol{X}) = \log{p(\boldsymbol{X})} = \int (r(\boldsymbol{X};\Theta) - \boldsymbol{X})\text{d}\boldsymbol{X}
\end{equation}

By Proposition <ref>, discrete TopoRecs are not denoising autoencoders and hence not EBMs in this way. On the contrary,  can be viewed as an EBM. It can be inferred from Theorem <ref> that the manifold of $r_{\mathbf{X}}(\mathbf{T}) - \mathbf{T}$ is a gradient vector field $\mathcal{T}$, on which inference is allowed to perform gradient descent on $\mathcal{T}$ to find the output $r_{\mathbf{X}}(\mathbf{T})$ that is closest to the input $\mathbf{T}$. Hence, the following corollary holds:

[breakable, pad at break=2.5mm, before skip=1mm, after skip=1mm, width=1.0, boxsep=0mm, arc=1.5mm, left=1.5mm, right=1.5mm, top=1.5mm, bottom=1mm]

Let $\mathcal{T} = E_{\mathbf{X},\Theta}(\mathbf{T})$ be an energy landscape similarly defined by <ref>. Then 's forward and backward passes are equivalent to implicitly performing the following optimization tasks on $\mathcal{T}$:

\begin{align}
\text{Forward pass: } r_{\mathbf{X}}(\tilde{\mathbf{T}}) &= \arg \min_{\tilde{\mathbf{T}}} E_{\mathbf{X},\Theta}(\tilde{\mathbf{T}}) \notag\\
\text{Backward pass: } E^*_{\mathbf{X},\Theta} &= \arg \min_{E \in \mathcal{F}} \mathcal{L} \notag
\end{align}

Such correlation between  and EBM provides another perspective of the reliability and flexibility of bandwidth mechanisms. We see this as a good foundation for future insights.

§ MORE CONFIGURATIONS

This section details our experimental configurations for reproducibility.

§.§ Data Statistics

We use a total of 12 real-world datasets:

* Citation networks: Cora, CiteSeer, PubMed <cit.>;

* Co-purchase networks: (Amazon-)Photo, (Amazon-)Computers <cit.>;

* Co-author networks: CS, Physics <cit.>;

* OGB networks for node classification: ogbn-arxiv, ogbn-mag <cit.>;

* OGB networks for link prediction: ogbl-collab, ogbl-ppa <cit.>;

* Hyperlink networks (directed): Wiki-CS <cit.>.

Please refer to the corresponding papers for a detailed introduction. Statistics of all datasets are listed in Table <ref>, where “density” stands for the percentage of all potential connections in a network that are actually positive edges, formally $\rho=\frac{|\mathcal{E}|}{n(n-1)}$.

Dataset statistics.

max width=0.5

Dataset     1c#nodes     1c#edges     1c#features     1c#classes     1cDensity (‰)

Swiss Roll$^\dagger$     500     6,712     –     –     26.9

Two-moon$^\dagger$     2,000     12,264     –     –     3.07

Cora     2,708     10,556    1,433     7    1.44

CiteSeer   3,327   9,104   3,703   6   0.82

PubMed   19,717   88,648   500   3   0.23

Photo   7,487   119,043   745   8   4.07

Computers   13,381   245,778   767   10   2.60

CS   18,333   81,894   6,805   15   0.24

Physics   34,493   247,962   8,415   5   0.21

Wiki-CS   11,701   216,123   300   10   1.58

ogbn-arxiv   169,343   2,315,598   128   40   0.08

ogbn-mag   736,389   10,792,672   128   349   0.02

ogbl-collab   235,868   2,570,930   128    –    0.05

ogbl-ppa   576,289   30,326,273   58    –    0.09

§.§ Hardware & Environments

is built upon PyTorch <cit.> 1.12.1 and PyTorch Geometric (PyG) <cit.> 2.3.1. The latter provides all 7 datasets used throughout the quantitative experiments except ogbn-arxiv and ogbl-collab, which are from the OGB 1.3.5 package <cit.>. Two synthetic datasets used in Section <ref> come from the PyGSP package <cit.>. All experiments are conducted on a 24GB NVIDIA GeForce GTX 3090 GPU with CUDA 11.3.

Detailed hyperparameters of .

Dataset     Cora     CiteSeer     PubMed     Photo      Computers     CS       Physics     ogbn-arxiv

No. of layers      3     5     2     2     3     2     2     4

Learning rate $\gamma$     1e-2     2e-2         1e-3       2e-3     1e-3      1e-2     2e-3      5e-4

Bandwidth temperature $\tau$     0.9      0.2        0.2        1      0.4           1e-6     0.4         0.4

Intermediate feature dim.             256      256          64         256     256           64       256         256

Output feature dim.     256      256          32         64     64            32       128         256

Encoder dropout     0.8      0.8          0.6        0.8     0.5           0.8      0.8         0.2

Decoder dropout     0      0            0.7        0.2       0.2           0.2      0.2         0

Weight decay (for encoder)            5e-5     5e-5         5e-5       5e-5     0             5e-5     5e-5        5e-5

Weight decay (for linear probing)     5e-3     1e-1         5e-5       5e-4     5e-4          1e-3     1e-3        1e-4

§.§ Model Setup & Hyperparameters

Training setup.
We follow the train/validation/test split of previous work <cit.>. To be specific, we use all existing official splits. For all datasets, edge sets are divided into $\mathcal{E}_\text{train}\!:\!\mathcal{E}_\text{val}\!:\!\mathcal{E}_\text{test} = 85\%\!:\!5\%\!:\!10\%$ for training and the downstream link prediction. As for node classification, the official split of Planetoid and ogbn-arxiv is adopted and node sets of other datasets are divided into $\mathcal{V}_\text{train}\!:\!\mathcal{V}_\text{val}\!:\!\mathcal{V}_\text{test} = 10\%\!:\!10\%\!:\!80\% $.

employs a GCN encoder ($\tilde{\mathbf{G}}=\boldsymbol{\Sigma}_e\hat{\tilde{\mathbf{D}}}^{-1/2}\hat{\tilde{\mathbf{A}}}\hat{\tilde{\mathbf{D}}}^{-1/2}$ in <ref>) with 1 to 5 layers and a fixed 2-layer MLP decoder with dropout. For brevity,  does not resort to extra techniques such as path masking, degree regression <cit.>, cross-correlation decoding <cit.>, re-masking, and random feature substitution <cit.>. All non-linear layers (of the encoder, decoder, and learnable downstream branches) are Xavier-initialized with biases 0. Every layer of the encoder is equipped with batch normalization <cit.>, dropout, and an ELU activation function <cit.>.
We perform grid search for the learning rate $\gamma$ and temperature $\tau$ over the searching space {5e-4, 1e-3, 2e-3, 5e-3, 1e-2, 2e-2} and {1e-6, 0.1, 0.2, 0.3, ..., 1} respectively. Adam <cit.> is used as the model optimizer. For all datasets except ogbn-arxiv, we use a fixed training strategy of 1000 epochs with early stopping, the patience of which is set to 30. For ogbn-arxiv, 100 epochs with batch size $2^{16}$. As with previous work, both grid search and early stopping are carried out on the validation set, and the best validation models are saved for testing.

Linear probing for node classification. The so-called linear probing <cit.> first performs unsupervised pre-training on both the encoder and decoder. Then, the decoder is substituted with a Xavier-initialized linear layer. It is trained (with the encoder frozen) for another 100 epochs with a fixed learning rate of 1e-2 to obtain the classification logits.

All model hyperparameters for node classification are given in Table <ref>. Please refer to the configuration in our source code for link prediction. They are selected manually on the validation set among several candidate values, except the grid-searched parameters.

§ MORE EXPERIMENT ANALYSES

This section showcases the rest of our experimental results to answer some additional research questions:

* ARQ1. What is the time and space consumption of ?

* ARQ2. Why is the dot-product probing setup fairer for evaluating self-supervised models?

* ARQ3. What is the performance of  on more larger-scale datasets except ogbn-arxiv?

* ARQ4. Is  able to be generalized to different graph types, e.g. directed graphs?

* ARQ5. How do certain parameters affect 's performance?

* ARQ6. How does  perform with limited training data?

§.§ Time and Space Consumptions (ARQ1)

In this subsection, we provide the time and space complexity of  as well as the representative baselines.

Complexity analysis.
The time and space complexity of each component of  is listed in Table <ref>.
The total time and space complexity tells that  scales linearly w.r.t. the number of nodes and edges. Despite that  requires extra time for continuous masking and layer-wise decoding, the overall time complexity of  is at the same level as . Beyond that, the lightweight decoder architecture reduces the difference in time consumption to a relatively small extent in practice.

Quantitative comparison. We have further measured the wall-clock pre-training time and peak GPU memory consumption for  as well as the baselines above. All self-supervised models are used to pre-train a 2-layer GCN for fixed 500 epochs (100 for ogbn-arxiv).
As shown in Table <ref>,  is not as efficient as  because it utilizes the whole training graph for message propagation and the layer-wise prediction multiplies the decoding time complexity by $K$. However, the lightweight decoder architecture makes the overall time gap much smaller than $K$ times (1.7$\times$ at most), making the time-effectiveness tradeoff more justifiable. In terms of GPU memory consumption,  is overall on par with . The reason is that
discrete edge masking actually does not offer remarkable memory savings, as $\mathcal{O}(\vert\mathcal{E}\vert)$ is nearly negligible in the total memory cost. Therefore,  still maintains the lightweight advantage of masked graph autoencoders.

Time & space complexity of 's components.

max width=

Component     Time     Space

Bandwidth masking     $\mathcal{O}(\vert\mathcal{E}\vert)$     $\mathcal{O}(\vert\mathcal{E}\vert)$

Encoding     $\mathcal{O}(Kd\vert\mathcal{E}\vert+Kd^2\vert\mathcal{V}\vert)$     $\mathcal{O}(Kd^2+\vert\mathcal{E}\vert+Kd\vert\mathcal{V}\vert)$

Decoding     $\mathcal{O}(Kd^2\vert\mathcal{E}\vert)$     $\mathcal{O}(d\vert\mathcal{E}\vert)$

Bandwidth prediction     $\mathcal{O}(K\vert\mathcal{E}\vert)$     $\mathcal{O}(\vert\mathcal{E}\vert)$

Total     $\mathcal{O}(Kd^2\vert\mathcal{E}\vert+Kd^2\vert\mathcal{V}\vert)$     $\mathcal{O}(Kd^2+d\vert\mathcal{E}\vert+Kd\vert\mathcal{V}\vert)$

Comparison of pre-training time (seconds) and memory consumption (MB).

max width=

Dataset     1c     1c     1c     1c     1c

6cPre-training time (s)

Cora     1.96e01     4.19e01     1.25e02     1.16e01     1.95e01

CiteSeer     2.44e01     4.53e01     4.59e02     1.40e01     2.08e01

PubMed     4.06e01     2.29e02     9.01e02     5.68e01     7.62e01

ogbn-arxiv     4.79e02     OOM     OOM     2.47e02     4.07e02

ogbl-collab     1.25e03     OOM     OOM     6.39e02     9.47e02

6cPeak GPU memory (MB)

Cora     1,169     1,431     2,045     1,171     1,459

CiteSeer     1,235     1,687     2,959     1,243     1,677

PubMed      1,409     12,267     20,781     1,345     1,523

ogbn-arxiv     8,941     >24,576     >24,576     6,149     4,925

ogbl-collab     7,289     >24,576     >24,576     5,283     6,269

Average AUC (%) of link prediction under the end-to-end training/fine-tuning (ETE/FT) and the dot-product probing (DPP).

max width=

Model     Setup     1cCora     1cCiteSeer     1cPubMed     1cPhoto     1cComputers     1cCS     1cPhysics

2* <cit.>     FT     91.34     95.70     95.70     98.22     97.76     95.91     96.42
DPP     73.18 ($\downarrow$18.2)     78.11 ($\downarrow$17.6)     76.21 ($\downarrow$19.5)     80.80 ($\downarrow$17.9)     84.60 ($\downarrow$13.2)     70.08 ($\downarrow$25.8)     89.18 ($\downarrow$7.24)
[RGB]180, 180, 180()2-9[RGB]0, 0, 0
2* <cit.>     ETE     93.41     93.14     98.34     96.97     95.49     94.13     97.02
DPP     89.27 ($\downarrow$4.14)     86.35 ($\downarrow$6.79)     89.53 ($\downarrow$8.81)     86.80 ($\downarrow$10.2)     84.16 ($\downarrow$11.3)     86.60 ($\downarrow$7.53)     88.92 ($\downarrow$8.10)
[RGB]180, 180, 180()2-9[RGB]0, 0, 0
2*-edge <cit.>     ETE     96.46     97.91     98.84     98.73     98.72     98.92     95.10
DPP     95.66 ($\downarrow$0.80)     97.02 ($\downarrow$0.89)     96.51 ($\downarrow$2.33)     81.12 ($\downarrow$17.6)     76.23 ($\downarrow$22.5)     96.50 ($\downarrow$2.42)     93.09 ($\downarrow$2.01)
[RGB]180, 180, 180()2-9[RGB]0, 0, 0
2*-path <cit.>     ETE     96.43     97.92     98.74     98.56     98.73     98.72     98.76
DPP     95.47 ($\downarrow$0.96)     97.21 ($\downarrow$0.71)     97.19 ($\downarrow$1.55)     80.46 ($\downarrow$18.1)     73.24 ($\downarrow$25.5)     92.26 ($\downarrow$6.46)     94.00 ($\downarrow$4.76)
[RGB]180, 180, 180()2-9[RGB]0, 0, 0
ETE     95.84     97.49     97.32     97.61     96.38     98.50     98.53
-2*     DPP     95.71 ($\downarrow$0.13)     96.89
($\downarrow$1.08)     97.26 ($\downarrow$0.06)     97.24 ($\downarrow$0.37)     97.33 ($\uparrow$0.95)     97.42 ($\downarrow$1.08)     97.02 ($\downarrow$1.51)

§.§ The Dot-Product Probing (ARQ2)

The workflow of end-to-end training (ETE) and dot-product probing (DPP).

In this subsection, we reiterate the necessity of dot-product probing in self-supervised link prediction.
We first reveal three shortcomings of the traditional end-to-end evaluation scheme. Firstly, ETE has become more like a fully supervised case than self-supervised, which is not effective enough to evaluate the generalization ability of self-supervised methods. Secondly, ETE relies on the trained decoder parameters in downstream training, leading to the over-optimistic evaluation results and saturation of the link prediction accuracy on many datasets <cit.>. Lastly, it is unfair to methods that do not learn by link prediction, as downstream information is inappropriately provided in the pre-training phase. In contrast, the dot-product probing simply replaces the decoder with a dot-product decoder during the evaluation, illustrated in Figure <ref>. DPP solely takes the latent representations provided by the encoder and directly gets the link prediction results, without any additional downstream training process, which decouples the pre-training and downstream adaptation and thus provides a fairer evaluation of self-supervised methods.

We consider several baselines specifically designed for link prediction, namely
, , and . Their link prediction performance is compared by two evaluation strategies: end-to-end training or fine-tuning (ETE/FT), and dot-product probing (DPP). For ETE/FT,  fine-tunes with a 1-layer Hadamard-product MLP decoder, while the others are trained end-to-end with a 2-layer MLP decoder. Table <ref> shows that, under the DPP setting, the link prediction accuracies of all baselines on a vast majority of datasets show a noticeable decrease compared to those under the ETE/FT setup. As a contrastive method,  is more dependent on the fine-tuning process for link prediction, so its performance is the most vulnerable out of all baselines. However, the same phenomenon is observed on the TopoRecs as well. The performance of  even decreases by more than 17% and 22% on Photo and Computers, respectively.
The clear sensitivity to the DPP setting suggests that decoders of the baseline models play a major role in their excellent performance. , however, is relatively immune to DPP, indicating that its effectiveness is provided by the encoder and thus more generalizable.

Additional performance on OGB datasets.

Hits@k(%) of link prediction on ogbl-collab.

max width=1

Model     Hits@20     Hits@50

-edge     58.59 ± 1.19     65.58 ± 0.43

-path     58.43 ± 1.06     65.58 ± 0.58

60.42 ± 0.84     67.77 ± 0.72

Hits@k(%) of link prediction on ogbl-ppa (by running 3 times).

max width=1

Model     Hits@50     Hits@100

-edge     13.16 ± 0.27     26.78 ± 2.44

-path     10.72 ± 0.73     24.32 ± 1.78

30.24 ± 0.90     42.05 ± 0.97

Micro-F1(%) and macro-F1(%) of node classification on ogbn-mag.

max width=1

Model     Micro-F1     Macro-F1

-edge     32.87 ± 0.36     13.94 ± 0.16

-path     32.86 ± 0.34     14.13 ± 0.29

33.08 ± 0.46     14.49 ± 0.36

§.§ Experiments on OGB Datasets (ARQ3)

Here we provide the additional link prediction results on ogbl-collab[We only keep the papers published in 2010 and beyond for training.] and ogbl-ppa, as well as node classification on ogbn-mag[We only keep the “paper-cites-paper” relation for training.]. We keep the end-to-end training on ogbl-collab and ogbl-ppa (on which we observe that almost all models fail with dot-product probing, as it may be too hard to achieve on large-scale datasets).
We report results of ogbl-collab, ogbl-ppa, and ogbn-mag in Table <ref>(a-c) respectively.  is observed to consistently outperform both configurations of  on all of the OGB datasets, indicating its advantage of topological learning on large-scale networks.

Micro-F1(%) and Macro-F1(%) of node classification on Wiki-CS.

Model     Micro-F1     Macro-F1

78.19 ± 0.05     75.30 ± 0.08

78.85 ± 0.25     75.47 ± 0.35

Node classification accuracy(%) under semi-supervised setting.

max width=1

2*Dataset     2*Model     3cTraining data ratio

[RGB]180, 180, 180()3-5[RGB]0, 0, 0
10% (original)     5%     1%

-edge     92.29 ± 0.25     92.04 ± 0.11     88.61 ± 0.36

93.10 ± 0.05     92.85 ± 0.05     90.40 ± 0.24

[RGB]180, 180, 180()2-5[RGB]0, 0, 0
-edge     95.10 ± 0.04     94.92 ± 0.03     93.56 ± 0.18

white-2*Physics          95.57 ± 0.04     95.41 ± 0.04     94.34 ± 0.03

§.§ Experiments on Wiki-CS (ARQ4)

Our bandwidth strategy has great potentiality in handling problems on a wide range of graph types, because bandwidth is a special kind of edge weight which is generally applicable. For example,  is naturally compatible with directed graphs like Wiki-CS. We conduct an experiment on Wiki-CS directly on the model architecture (with 10%:10%:80% data split) and show node classification results in Table <ref>.  performs better than , a contrastive framework providing native support for Wiki-CS, owing much to the local informativeness of bidirected and dispersive edge weights.

§.§ Parameter Analyses (ARQ5)

§.§.§ Effect of the temperature.
As discussed in Section <ref>, the temperature $\tau$ of the Boltzmann-Gibbs distribution controls the continuity of the mask.

Figure <ref> illustrates the node classification performance with different values of $\tau$, set as 1e-6, 0.1, 0.2, ..., 0.9, 1, 2, and 5. The extent of performance fluctuation w.r.t. temperature varies across datasets, as does the temperature range for the best accuracy, such as [0.8, 0.9] for Cora and [0.2, 1] for PubMed. However, it can be observed on the vast majority of datasets that the model performance declines if $\tau$ is too small (i.e. the discretized mask) or too large (i.e. the uniformized mask).

Node classification accuracy w.r.t. the temperature.

Average node classification accuracy w.r.t. the embedding size.

§.§.§ Effect of embedding size.

We also analyze the effect of input and output embedding size of the decoder layers. Figure <ref> shows that  does not necessarily benefit from a large embedding dimension, even if the dataset is relatively large, as the best input and output embedding size on PubMed is 64 and 32 respectively. On the other hand, CiteSeer prefers a larger embedding size because it benefits from a deeper encoder in our case, but setting a deeper encoder in a discrete  will instead lead to over-smoothing and a decrease in performance.

§.§ The Semi-Supervised Setting (ARQ6)

We further investigate the performance of  under the semi-supervised setting with scarce-labeled training data. We limit the node label ratio of CS and Physics (two datasets without official data splits) to 5% and 1% for downstream training and showcase the node classification accuracy in Table <ref>.
It's noteworthy that the performance of both  and  drops as the ratio of labeled training data decreases. However,  still outperforms  with scarce downstream supervision signals.