Graph Neural Networks can Recover the Hidden Features Solely from the
  Graph Structure
Graph Neural Networks (GNNs) are popular models for graph learning problems.
GNNs show strong empirical performance in many practical tasks. However, the
theoretical properties have not been completely elucidated. In this paper, we
investigate whether GNNs can exploit the graph structure from the perspective
of the expressive power of GNNs. In our analysis, we consider graph generation
processes that are controlled by hidden (or latent) node features, which
contain all information about the graph structure. A typical example of this
framework is kNN graphs constructed from the hidden features. In our main
results, we show that GNNs can recover the hidden node features from the input
graph alone, even when all node features, including the hidden features
themselves and any indirect hints, are unavailable. GNNs can further use the
recovered node features for downstream tasks. These results show that GNNs can
fully exploit the graph structure by themselves, and in effect, GNNs can use
both the hidden and explicit node features for downstream tasks. In the
experiments, we confirm the validity of our results by showing that GNNs can
accurately recover the hidden features using a GNN architecture built based on
our theoretical analysis.
Ryoma Sato
# Graph Neural Networks can Recover the Hidden Features

###### Abstract

Graph Neural Networks (GNNs) are popular models for graph learning problems. GNNs show strong empirical performance in many practical tasks. However, the theoretical properties have not been completely elucidated. In this paper, we investigate whether GNNs can exploit the graph structure from the perspective of the expressive power of GNNs. In our analysis, we consider graph generation processes that are controlled by hidden node features, which contain all information about the graph structure. A typical example of this framework is kNN graphs constructed from the hidden features. In our main results, we show that GNNs can recover the hidden node features from the input graph alone, even when all node features, including the hidden features themselves and any indirect hints, are unavailable. GNNs can further use the recovered node features for downstream tasks. These results show that GNNs can fully exploit the graph structure by themselves, and in effect, GNNs can use both the hidden and explicit node features for downstream tasks. In the experiments, we confirm the validity of our results by showing that GNNs can accurately recover the hidden features using a GNN architecture built based on our theoretical analysis.

Graph Neural Networks, Graph Neural Networks, Graph Structure

## 1 Introduction

Graph Neural Networks (GNNs) (Gori et al., 2005; Scarselli et al., 2009) are popular machine learning models for processing graph data. GNNs take a graph with node features as input and output embeddings of nodes. At each node, GNNs send the node features to neighboring nodes, aggregate the received features, and output the new node features (Gilmer et al., 2017). In this way, GNNs produce valuable node embeddings that take neighboring nodes into account. GNNs show strong empirical performance in machine learning and data mining tasks (Zhang and Chen, 2018; Fan et al., 2019; He et al., 2020; Han et al., 2022).

Roughly speaking, GNNs smooth out the node features on the input graph by recursively mixing the node features of neighboring nodes, and GNNs thereby transform noisy features into clean ones. This smoothing effect has been observed empirically (Chen et al., 2020; NT and Maehara, 2019) and shown theoretically (Li et al., 2018; Oono and Suzuki, 2020). There are several GNN architectures that are inspired by the smoothing process (Klicpera et al., 2019; NT and Maehara, 2019; Wu et al., 2019). It has also been pointed out that stacking too many layers harms the performance of GNNs due to the over-smoothing effect (Li et al., 2018; Chen et al., 2020), which is caused by too much mixing of the node features.

In this perspective, node features are the primary actors in GNNs, and graphs are secondary. If node features are uninformative at all, GNNs should fail to obtain meaningful node embeddings no matter how they mix node features. This is in contrast to the opposite scenario: Even if the graphs are uninformative at all, if the node features are informative for downstream tasks, GNNs can obtain meaningful node embeddings just by ignoring edges or not mixing node features at all. Therefore, node features are the first requirement of GNNs, and the graph only provides some boost to the quality of node features (NT and Maehara, 2019). It indicates that GNNs cannot utilize the graph information without the aid of good node features.

The central research question of this paper is as follows:

_Can GNNs utilize the graph information_

_without the aid of node features?_

We positively answer this question through our theoretical analysis. We show that GNNs can recover the hidden node features that control the generation of the graph structure even without the help of informative node features. The recovered features contain all the information of the graph structure. The recovered node features can be further used for downstream tasks. These results show that GNNs can essentially use both given node features and graph-based features extracted from the graph structure. Our theoretical results provide a different perspective from the existing
beliefs (Wang et al., 2020; NT & Maehara, 2019) based on empirical observations that GNNs only mix and smooth out node features. In the experiments, we show that existing GNN architectures do not necessarily extract the hidden node features well, and special architectures are required to learn the recovery in empirical situations.

The contributions of this paper are summarized as follows:

* We establish the theory of the feature recovery problem by GNNs for the first time. Our analysis provides a new perspective on the expressive power of GNNs.
* We prove that GNNs can recover the hidden features solely from the graph structure (Theorem 4.4). These results show that GNNs have an inherent ability to extract information from the input graph.
* We validate the theoretical results in the experiments by showing that GNNs can accurately recover the hidden features. We also show that existing GNN architectures are mediocre in this task. These results highlight the importance of inductive biases for GNNs.

## 2 Related Work

### Graph Neural Networks and Its Theory

Graph Neural Networks (GNNs) (Gori et al., 2005; Scarselli et al., 2009) are now de facto standard models for graph learning problems (Kipf & Welling, 2017; Velickovic et al., 2018; Zhang & Chen, 2018). There are many applications of GNNs, including bioinformatics (Li et al., 2021), physics (Cranmer et al., 2020; Pfaff et al., 2021), recommender systems (Fan et al., 2019; He et al., 2020), and transportation (Wang et al., 2020). There are several formulations of GNNs, including spectral (Defferrard et al., 2016), spatial (Gilmer et al., 2017), and equivariant (Maron et al., 2019) ones. We use the message-passing formulation introduced by Gilmer et al. (2017) in this paper.

The theory of GNNs has been studied extensively in the literature, including generalization GNNs (Scarselli et al., 2018; Garg et al., 2020; Xu et al., 2020) and computational complexity (Hamilton et al., 2017; Chen et al., 2018; Zou et al., 2019; Sato et al., 2022). The most relevant topic to this paper is the expressive power of GNNs, which we will review in the following.

**Expressive Power** (or Representation Power) means what kind of functional classes GNNs can realize. Originally, Morris et al. (2019) and Xu et al. (2019) showed that message-passing GNNs are at most as powerful as the 1-WL test, and they proposed GNNs that are as powerful as the 1-WL and \(k\)-(set)WL tests. Sato et al. (2019, 2021) and Loukas (2020) also showed that message-passing GNNs are as powerful as a computational model of distributed local algorithms, and they proposed GNNs that are as powerful as port-numbering and randomized local algorithms. Loukas (2020) showed that GNNs are Turing-complete under certain conditions (i.e., with unique node ids and infinitely increasing depths). There are various efforts to improve the expressive power of GNNs by non-message-passing architectures (Maron et al., 2019; Ma et al., 2019; Murphy et al., 2019). We refer the readers to survey papers (Sato, 2020; Jegelka, 2022) for more details on the expressive power of GNNs.

The main difference between our analysis and existing ones is that the existing analyses focus on combinatorial characteristics of the expressive power of GNNs, e.g., the WL test, which are not necessarily aligned with the interests of realistic machine learning applications. By contrast, we consider the continuous task of recovering the hidden features from the input graph, which is an important topic in machine learning in its own right (Tenenbaum et al., 2000; Belkin & Niyogi, 2003; Sussman et al., 2014; Sato, 2022). To the best of our knowledge, this is the first paper that reveals the expressive power of GNNs in the context of feature recovery. Furthermore, the existing analysis of expressive power does not take into account the complexity of the models. The existing analyses show that GNNs can solve certain problems, but they may be too complex to be learned by GNNs. By contrast, we show that the feature recovery problem can be solved with low complexity.

### Feature Recovery

Estimation of hidden variables that control the generation process of observed data has been extensively studied in the machine learning literature (Tenenbaum et al., 2000; Sussman et al., 2014; Kingma & Welling, 2014). These methods are sometimes used for dimensionality reduction, and the estimated features are fed to downstream models. In this paper, we consider the estimation of hidden embeddings from a graph observation (Alamgir & von Luxburg, 2012; von Luxburg & Alamgir, 2013; Terada & von Luxburg, 2014; Hashimoto et al., 2015). The critical difference between our analysis and the existing ones is that we investigate whether GNNs can represent a recovery algorithm, while the existing works propose general (non-GNN) algorithms that recover features. To the best of our knowledge, we are the first to establish the theory of feature recovery based on GNNs.

Many empirical works propose feature learning methods for GNNs (Hamilton et al., 2017; Velickovic et al., 2019; You et al., 2020; Hu et al., 2020; Qiu et al., 2020). The differences between these papers and ours are twofold. First, these methods are not proven to converge to the true features, while we consider a feature learning method that converges to the true features. Second, the existing methods rely heavily on the input node features while we do not assume any input node features. The latter point is important
because how GNNs exploit the input graph structure is a central topic in the GNN literature, and sometimes GNNs are shown to NOT benefit from the graph structure (Errica et al., 2020). By contrast, our results show that GNNs can extract meaningful information from the input graph from a different perspective than existing work.

## 3 Background and Problem Formulation

In this paper, we assume that each node \(v\) has hidden features \(\mathbf{z}_{v}\), and the graph is generated by connecting nodes with similar hidden features. For example, (i) \(\mathbf{z}_{v}\in\mathbb{R}^{d}\) represents the preference of person \(v\) in social networks, (ii) \(\mathbf{z}_{v}\) represents the topic of paper \(v\) in citation networks, and (iii) \(\mathbf{z}_{v}\) represents the geographic location of point \(v\) in spatial networks. The critical assumption of our problem setting is that the features \(\{\mathbf{z}_{v}\mid v\in V\}\), such as the true preference of people and the true topic of papers, are not observed, but only the resulting graph \(G\) is observed. Somewhat surprisingly, we will show that GNNs that take the vanilla graph \(G\) with only simple synthetic node features such as degree features \(d_{v}\) and graph size \(n=|V|\) can consistently estimate the hidden features \(\{\mathbf{z}_{v}\mid v\in V\}\) (Fig. 1). In the following, we describe the assumptions on data and models in detail.

### Assumptions

In this paper, we deal with directed graphs. Directed graphs are general, and undirected graphs can be converted to directed graphs by duplicating every edge in both directions. We assume that there is an arc from \(u\) to \(v\) if and only if \(\|\mathbf{z}_{v}-\mathbf{z}_{u}\|<s(\mathbf{z}_{v})\) for a threshold function \(s\colon\mathbb{R}^{d}\to\mathbb{R}\), i.e., nodes with similar hidden features are connected. It is also assumed that the hidden features \(\{\mathbf{z}_{v}\}\) are sampled from an unknown distribution \(p(\mathbf{z})\) in an i.i.d. manner. As we consider the consistency of estimators or the behavior of estimators in a limit of infinite samples (nodes), we assume that a node \(v_{i}\) and its features \(\mathbf{z}_{v_{i}}\sim p(\mathbf{z})\) are generated one by one, and we consider a series of graphs \(G_{1}=(V_{1}=\{v_{1}\},E_{1}),G_{2}=(V_{2}=\{v_{1},v_{2}\},E_{2}),\ldots,G_{n}= (V_{n},E_{n}),\ldots\) with an increasing number of nodes. Formally, the data generation process and the assumptions are summarized as follows.

**Assumption 1** (Domain): The domain \(\mathcal{Z}\) of the hidden features is a convex compact domain in \(\mathbb{R}^{d}\) with smooth boundary \(\partial\mathcal{Z}\).
**Assumption 2** (Graph Generation): For each \(i\in\mathbb{Z}_{+}\), \(\mathbf{z}_{v_{i}}\) is sampled from \(p(\mathbf{v})\) in an i.i.d. manner. There is a directed edge from \(v\) to \(u\) in \(G_{n}\) if and only if \(\|\mathbf{z}_{v}-\mathbf{z}_{u}\|<s_{n}(\mathbf{z}_{v})\).
**Assumption 3** (Density): The density \(p(\mathbf{z})\) is positive and differentiable with bounded \(\nabla\log(p(\mathbf{z}))\) on \(\mathcal{Z}\).
**Assumption 4** (Threshold Function): There exists a deterministic continuous function \(\bar{s}(x)>0\) on \(\bar{\mathcal{Z}}\) such that \(g_{n}^{-1}s_{n}(x)\) converges uniformly to \(\bar{s}(x)\) for some \(g_{n}\in\mathbb{R}\) with \(g_{n}\xrightarrow{n\to\infty}0\) and \(g_{n}n^{\frac{1}{n+1}}\log^{-\frac{1}{d+2}}n\xrightarrow{n\to\infty}\infty\) almost surely.
**Assumption 5** (Stationary Distribution): \(n\pi_{G_{n}}(v)\) is uniformly equicontinuous almost surely, where \(\pi_{G_{n}}(v)\) is the stationary distribution of random walks on \(G_{n}\).

Note that these assumptions are common to (Hashimoto et al., 2015). It should be noted that the threshold functions \(s_{n}\) can be stochastic and/or dependent on the data as long as Assumption 4 holds. For example, \(k\)-NN graphs can be realized in this framework by setting \(s(\mathbf{z}_{v})\) to be the distance to the \(k\)-th nearest neighbor from \(\mathbf{z}_{v}\).

**Remark (One by One Generation).** The assumption of adding nodes one at a time may seem tricky. New users

Figure 1: **Illustrations of the Problem Setting. (a) Nodes have hidden features from which the input graph is generated. (b) The input to GNNs is a vanilla graph without any additional features. The coordinates of nodes are computed by the spring layout for visualization in this panel, but these coordinates are neither fed to GNNs. (c) GNNs try to recover the hidden features.**
are indeed inserted into social networks one by one in some scenarios, but some other graphs do not necessarily follow this process. This assumption is introduced for technical convenience to consider the limit of \(n\rightarrow\infty\) and to prove the consistency. In practice, the generation process of datasets does not need to follow this assumption. We use a single fixed graph in the experiments. GNNs succeed in recovering the hidden features only if the graph is sufficiently large.

### Graph Neural Networks

We consider message-passing GNNs (Gilmer et al., 2017) in this paper. Formally, \(L\)-layer GNNs can be formulated as follows. Let \(\mathbf{X}=[\mathbf{x}_{1},\ldots,\mathbf{x}_{n}]^{\top}\in\mathbb{R}^{n\times\text{d}_{ \text{an}}}\) be the explicit (i.e., given, observed) node features, and

\[\mathbf{h}_{v}^{(0)} =\mathbf{x}_{v} (\forall v\in V),\] \[\mathbf{a}_{v}^{(l)} =f_{\text{agg}}^{(l)}(\llbracket\mathbf{h}_{u}^{(l-1)}\mid u\in \mathcal{N}^{-}(v)\rrbracket) (\forall l\in[L],v\in V),\] \[\mathbf{h}_{v}^{(l)} =f_{\text{upd}}^{(l)}(\mathbf{h}_{v}^{(l-1)},\mathbf{a}_{v}^{(l)}) (\forall l\in[L],v\in V),\]

where \(\llbracket\cdot\rrbracket\) denotes a multiset, and \(\mathcal{N}^{-}(v)\) is the set of the neighbors with outgoing edges to node \(v\). We call \(f_{\text{agg}}^{(l)}\) an aggregation function and \(f_{\text{upd}}^{(l)}\) a update function. Let \(\theta=[L,f_{\text{agg}}^{(1)},f_{\text{upd}}^{(1)},\ldots,f_{\text{agg}}^{ (L)},f_{\text{upd}}^{(L)}]\) denote a list of all aggregation and update functions, i.e., \(\theta\) specifies a model. Let \(f(v,G,\mathbf{X};\theta)=\mathbf{h}_{v}^{(L)}\) be the output of the GNN \(\theta\) for node \(v\) and input graph \(G\). For notational convenience, \(L_{\theta}\), \(f_{\text{agg},\theta}^{(l)}\), and \(f_{\text{upd},\theta}^{(l)}\) denote the number of layers, \(l\)-th aggregation function, and \(l\)-th aggregation function of model \(\theta\), respectively.

Typical applications of GNNs assume that each node has rich explicit features \(\mathbf{x}_{v}\). However, this is not the case in many applications, and only the graph structure \(G\) is available. In such a case, synthetic features that can be computed solely from the input graph, such as degree features and the number of nodes, are used as explicit node features \(\mathbf{x}_{v}\)(Errica et al., 2020; Hamilton et al., 2017; Xu et al., 2019). In this paper, we tackle this general and challenging setting to show how GNNs exploit the graph structure. Specifically, we do not assume any external node features but set

\[\mathbf{x}_{v}=[d_{v},n]^{\top}\in\mathbb{R}^{2}, \tag{1}\]

where \(d_{v}\) is the degree of node \(v\), and \(n=|V|\) is the number of nodes in \(G\). The goal of this paper is that GNNs can recover the hidden features \(\mathbf{z}_{v}\) even if the node features are as scarce as the simple synthetic features. In words, we show that there exists GNN \(\theta\) that uses the explicit node features \(\mathbf{X}\) defined by Eq. (1)1 and outputs \(f(v,G,\mathbf{X};\theta)\approx\mathbf{z}_{v}\). This result is surprising because GNNs have been considered to simply smooth out the input features along the input graph (Li et al., 2018; NT & Maheara, 2019). Our results show that GNNs can imagine new features \(\mathbf{z}_{v}\) that are not included in the explicit features \(\mathbf{X}\) from scratch.

Footnote 1: Precisely, we will add additional random features as Eq. (3).

**Remark (Expressive Power and Optimization).** We note that the goal of this paper is to show the expressive power of GNNs, i.e., the existence of the parameters \(\theta\) or the model specification that realizes some function, and how to find them from the data, i.e., optimization, is out of the scope of this paper. The separation of the studies of expressive power and optimization is a convention in the literature (Sato et al., 2019; Loukas, 2020; Abboud et al., 2021). This paper is in line with them. In the experiments, we briefly show the empirical results of optimization.

### Why Is Recovery Challenging?

A straightforward approach to estimating the hidden features \(\mathbf{z}_{v}\) is to estimate the distance matrix \(D_{ij}=\|\mathbf{z}_{i}-\mathbf{z}_{j}\|\) first and recover the features by, e.g., multidimensional scaling. As GNNs can simulate the Bellman-Ford algorithm (Xu et al., 2020), the estimation of the distance matrix \(D\) looks easy at first glance. However, this is not the case as the edge lengths are not included in the input, and therefore the shortest path distance on the graph is not a consistent estimator for the distance of nodes in the feature space. Figure 2 illustrates this fact. One hop on the graph in a sparse region is longer in the feature space than that in a dense region. A hop count does not necessarily reflect the distance in the feature space. One might think that the density around a node could be estimated e.g., by the degree of the node, but this is not the case. Indeed, as the graph shown in Figure 2 is a \(k\)-NN graph, the degrees of all nodes are the same, and therefore the degree does not provide any information about the density. In general, the density cannot be estimated from a local structure, as von Luxburg

Figure 2: **Illustrations of the Difficulty of Recovery.** The input graph is \(10\)-NN graph of the hidden features. The shortest path distance between points A and B is \(21\) hops, and the shortest path distance between points A and C is \(18\) hops. These distances indicate that point C is closer to point A than point B, but this is not the case in the true feature space. This disagreement is caused by the different scales of edges in sparse and dense regions. The difficulty lies in the fact that these scales are not directly available in the input information.
& Alamgir (2013) noted that "It is impossible to estimate the density in an unweighted \(k\)-NN graph by local quantities alone."

If the edge lengths in the feature space are taken into account, the shortest-path distance on the graph is a consistent estimator for the distance of nodes in the feature space. However, the problem is that the edge length, such as the quantitative intimacy between people in social networks and the distance between the true topics of two papers in citation networks, is not available, and what we observe is only the vanilla graph \(G\) in many applications. The first insight to this challenge is that the threshold function \(s(\mathbf{z})\), which represents a typical scale of edges around \(\mathbf{z}\) can be used as a surrogate value for the edge length. In the following, we first focus on estimating the threshold function \(s(\mathbf{z})\) by GNNs, and then, we show that GNNs can recover the hidden features \(\mathbf{z}_{v}\) by leveraging the threshold function.

## 4 Main Results

We present our main results and their proofs in this section. At a high level, our results are summarized as follows:

* We show in Section 4.1 that GNNs can estimate the threshold function \(s(\mathbf{z})\) with the aid of the metric recovery theory of unweighted graphs (Hashimoto et al., 2015; Alamgir & von Luxburg, 2012).
* We show in Section 4.2 that GNNs can recover the hidden features up to rigid transformation with the aid of the theory of multidimensional scaling (Sibson, 1979; 1978) and random node features (Sato et al., 2021; Abboud et al., 2021).
* We show in Theorems 4.2 and 4.5 that the number of the functions to be learned is finite regardless of the number of nodes, which is important for learning and generalization (Xu et al., 2020).

### Graph Neural Networks can Recover the Threshold Function

First, we show that GNNs can consistently estimate the threshold function \(s\). As we mentioned in the previous section, the density and threshold function cannot be estimated solely from the local structure. As we will show (and as is known in the classical context), they can be estimated by a PageRank-like global quantity of the input graph.

**Theorem 4.1**.: _For any \(s\) and \(g\) that satisfy Assumptions 1-5, there exist \(\theta_{1},\theta_{2},\ldots\) such that with the explicit node features \(\mathbf{X}\) defined by Eq. (1),_

\[\text{Pr}\left[f(v,G_{n},\mathbf{X};\theta_{n})\xrightarrow{n\to\infty}s(\mathbf{z}_ {v})\right]=1,\]

_where the probability is with respect to the draw of samples \(\mathbf{z}_{1},\mathbf{z}_{2},\ldots\)._

Proof Sketch.: We prove this theorem by construction. The key idea is that GNNs can simulate random walks on graphs (Dehmamy et al., 2019). Once the stationary distribution of random walks is estimated, we can recover the scale from it (Hashimoto et al., 2015). The full proof can be found in Appendix A. 

This theorem states that GNNs can represent a consistent estimator of \(s(\mathbf{z}_{v})\).

However, this theorem does not bound the number of layers, and the number of layers may grow infinitely as the number of nodes increases. This means that if the size of the graphs is not bounded, the number of functions to be learned grows infinitely. This is undesirable for learning. The following theorem resolves this issue.

**Theorem 4.2**.: _There exist \(h^{(1)}_{\text{agg}},h^{(1)}_{\text{upd}},h^{(2)}_{\text{agg}},h^{(2)}_{ \text{upd}}\) such that for any \(s\) and \(g\), there exist \(h^{(3)}_{\text{upd}}\) such that Theorem 4.1 holds with_

\[f^{(1)}_{\text{agg},\theta_{n}}=h^{(1)}_{\text{agg}},\quad f^{(1)}_{\text{ upd},\theta_{n}}=h^{(1)}_{\text{upd}}\]

\[f^{(l)}_{\text{agg},\theta_{n}}=h^{(2)}_{\text{agg}},\quad f^{(l)}_{\text{ upd},\theta_{n}}=h^{(2)}_{\text{upd}}\quad(l=2,\ldots,L_{\theta_{n}}-1)\]

\[f^{(L_{\theta_{n}})}_{\text{agg},\theta_{n}}=h^{(2)}_{\text{agg}},\quad f^{ (L_{\theta_{n}})}_{\text{upd},\theta_{n}}=h^{(3)}_{\text{upd}}.\]

Proof Sketch.: From the proof of Theorem 4.1, most of the layers in \(\theta_{i}\) are used for estimating the stationary distribution, which can be realized by a repetition of the same layer. 

This theorem shows that the number of functions we need to learn is essentially five. This result indicates that learning the scale function has a good algorithmic alignment (Xu et al., 2020, Definition 3.4). Moreover, these functions are the same regardless of the graph size. Therefore, in theory, one can fit these functions using small graphs and apply the resulting model to large graphs as long as the underlying law for the generation process, namely \(s\) and \(g\), is fixed. Note that the order of the logical quantification matters. As \(h^{(1)}_{\text{agg}},h^{(1)}_{\text{upd}},h^{(2)}_{\text{agg}},h^{(2)}_{ \text{upd}}\) are universal and are independent with the generation process, they can be learned using other graphs and can be transferred to other types of graphs. The construction of these layers (i.e., the computation of the stationary distribution) can also be used for introducing indicative biases to GNN architectures.

### Graph Neural Networks can Recover the Hidden Features

As we have estimated the scale function, it seems easy to recover the features by applying the Bellman-Ford algorithm with edge lengths, as we mentioned in Section 3.3, but this does not work well. The first obstacle is that there is a freedom of rigid transformation. As rotating and shifting
the true hidden features does not change the observed graph, we cannot distinguish hidden features that are transformed by rotation solely from the graph. To absorb the degree of freedom, we introduce the following measure of discrepancy of features.

**Definition 4.3**.: We define the distance between two feature matrices \(\mathbf{X},\mathbf{Y}\in\mathbb{R}^{n\times d}\) as

\[d_{G}(\mathbf{X},\mathbf{Y})\stackrel{{\text{def}}}{{=}}\min_{\begin{subarray} {c}\mathbf{P}\in\mathbb{R}^{d\times d}\\ \mathbf{P}^{\top}\mathbf{P}=I_{d}\end{subarray}}\frac{1}{n}\|\mathbf{C}_{n}\mathbf{X}-\mathbf{C}_{ n}\mathbf{Y}\mathbf{P}\|_{F}^{2}, \tag{2}\]

where \(\mathbf{C}_{n}\stackrel{{\text{def}}}{{=}}(\mathbf{I}_{n}-\frac{1}{n} \mathbbm{1}_{n}\mathbbm{1}_{n}^{\top})\in\mathbb{R}^{n\times n}\) is the centering matrix, \(\mathbf{I}_{n}\in\mathbb{R}^{n\times n}\) is the identity matrix, and \(\mathbbm{1}_{n}\in\mathbb{R}^{n}\) is the vector of ones. We say that we recover the hidden features \(\mathbf{X}\) if we obtain features \(\mathbf{Y}\) such that \(d_{G}(\mathbf{X},\mathbf{Y})<\varepsilon\) for sufficiently small \(\varepsilon>0\).

In other words, the distance is the minimum average distance between two features after rigid transformation. This distance is sometimes referred to as the orthogonal Procrustes distance (Hurley and Cattell, 1962; Schonemann, 1966; Sibson, 1978), and can be computed efficiently by SVD (Schonemann, 1966). Note that if one further wants to recover the rigid transformation factor, one can recover it in a semi-supervised manner by the Procrustes analysis.

The second obstacle is that GNNs cannot distinguish nodes. A naive solution is to include unique node ids in the node features. However, this leads the number of dimensions of node features to infinity as the number of nodes tends to infinity. This is not desirable for learning and generalization of the size of graphs. Our solution is to randomly select a constant number \(m\) of nodes and assign unique node ids only to the selected nodes2. Specifically, let \(m\in\mathbb{Z}_{+}\) be a constant hyperparameter, and we first select \(m\) nodes \(\mathcal{U}=[u_{1},\ldots,u_{m}]\subset V\) uniformly and randomly and set the input node features \(\mathbf{x}_{v}\in\mathbb{R}^{2+m}\) as

Footnote 2: From a technical point of view, this is a critical difference from existing analyses (Loukas, 2020; Sato et al., 2021; Abboud et al., 2021), which assume unique node ids. Our analysis strikes an excellent trade-off between a small complexity (a constant dimension) and a strong expressive power (precise recovery).

\[\mathbf{x}_{v}^{\text{syn}}=\begin{cases}[d_{v},n,\mathbf{e}_{i}^{\top}]^{\top}&(v=u_{ i})\\ [d_{v},n,\mathbf{0}_{m}^{\top}]^{\top}&(v\not\in\mathcal{U})\end{cases}, \tag{3}\]

where \(\mathbf{e}_{i}\in\mathbb{R}^{m}\) is the \(i\)-th standard basis, and \(\mathbf{0}_{m}\) is the vector of zeros. Importantly, this approach does not increase the number of dimensions even if the number of nodes tends to infinity because \(m\) is a constant with respect to \(n\). We show that we can accurately estimate the distance structure and the hidden features by setting an appropriate number of the selected nodes.

**Theorem 4.4**.: _For any \(s\) and \(g\) that satisfy Assumptions 1-5, for any \(\varepsilon,\delta>0\), there exist \(m\) and \(\theta_{1},\theta_{2},\ldots\) such that with the explicit node features \(\mathbf{X}\) defined by Eq. (3),_

\[\text{Pr}\left[\limsup_{n\rightarrow\infty}d_{G}(\hat{\mathbf{Z}}_{\theta_{n}}, \mathbf{Z})<\varepsilon\right]>1-\delta,\]

_where \(\hat{\mathbf{Z}}_{\theta_{n}}=[f(v_{1},G_{n},\mathbf{X};\theta_{n}),\ldots,f(v_{n},G_ {n},\mathbf{X};\theta_{n})]\in\mathbb{R}^{n\times d}\) is the estimated hidden features by GNN \(\theta_{i}\), and \(\mathbf{Z}=[\mathbf{z}_{1},\ldots,\mathbf{z}_{n}]\in\mathbb{R}^{n\times d}\) is the true hidden features. The probability is with respect to the draw of samples \(\mathbf{z}_{1},\mathbf{z}_{2},\ldots\) and the draw of a random selection of \(\mathcal{U}\)._

Proof Sketch.: We prove this theorem by construction. We estimate the threshold function \(s\) by Theorem 4.1 and compute the shortest path distances from each selected node in \(\mathcal{U}\) with the estimated edge lengths. The computation of shortest path distances can be done by GNNs (Xu et al., 2020). After this process, each node has the information of the (approximate) distance matrix among the selected nodes, which consists of \(m^{2}\) dimensions. We then run multidimensional scaling in each node independently and recover the coordinates of the selected nodes. Lastly, the selected nodes announce their coordinates, and the non-selected nodes output the coordinates of the closest nodes in \(\mathcal{U}\). With sufficiently large \(m\), the selected nodes \(\mathcal{U}\) form an \(\varepsilon^{\prime}\)-covering of \(\mathcal{D}\) with high probability, and therefore, the mismatch of the non-selected nodes is negligibly small. The full proof can be found in Appendix B. 

As in Theorem 4.1, the statement of Theorem 4.4 does not bound the number of layers. However, as in Theorem 4.2, Theorem 4.4 can also be realized with a fixed number of functions.

**Theorem 4.5**.: _For any \(s\) and \(g\), there exist \(h^{(1)}_{\text{agg}}\), \(h^{(1)}_{\text{qupl}}\)\(\ldots\), \(h^{(8)}_{\text{agg}}\), \(h^{(8)}_{\text{upd}}\) such that Theorem 4.4 holds with these functions._

Therefore, the number of functions we need to learn is essentially a constant. This fact indicates that learning the hidden features has a good algorithmic alignment (Xu et al., 2020, Definition 3.4). Besides, the components of these functions, i.e., computation of the stationary distribution, shortest-path distances, and multidimensional scaling, are differentiable almost everywhere. Here, we mean by almost everywhere the existence of non-differentiable points due to the min-operator of the shortest-path algorithm. Strictly speaking, this is no more differentiable than the ReLU function is, but can be optimized in an end-to-end manner by backpropagation using auto-differential frameworks such as PyTorch.

**Remark (GNNs with Input Node Features).** Many of graph-related tasks provide node features \(\{\mathbf{x}_{v}^{\text{given}}\mid v\in V\}\) as input. Theorem 4.4 shows that GNNs with \(\mathbf{x}_{v}^{\text{syn}}\) as explicit node features can recover \(\mathbf{z}_{v}\), where \(\mathbf{x}_{v}^{\text{syn}}\) is defined by Eq. (3). Thus, if we feed \(\mathbf{x}_{v}=[\mathbf{x}_{v}^{\text{given}\top},\mathbf{x}_{v}^{\text{syn}\top}]^{\top}\) to GNNs as
explicit node features, GNN can implicitly use both of \(\mathbf{x}_{v}^{\text{given}}\) and \(\mathbf{z}_{v}\).

The most straightforward method for node classification is to apply a feed-forward network to each node independently,

\[\hat{y}_{v}^{\text{MLP}}=h_{\theta}(\mathbf{x}_{v}^{\text{given}}). \tag{4}\]

This approach is fairly strong when \(\mathbf{x}_{v}^{\text{given}}\) is rich (NT & Maehara, 2019) but ignores the graph. Our analysis shows that GNNs can classify nodes using both \(\mathbf{x}_{v}^{\text{given}}\) and \(\mathbf{z}_{v}\), i.e.,

\[\hat{y}_{v}^{\text{GNN}}=h_{\theta}(\mathbf{x}_{v}^{\text{given}},\mathbf{z}_{v}). \tag{5}\]

Comparison of Eqs. (4) and (5) highlights a strength of GNNs compared to feed-forward networks.

## 5 Experiments

In the experiments, we will validate the theorems by empirically showing that GNNs can recover hidden features solely from the input graph.

**Datasets.**: We use the following synthetic and real datasets.

**Two-Moon**: is a synthetic dataset with a two-moon shape. We construct a \(k\)-nearest neighbor graph with \(k=\text{floor}(\frac{1}{10}n^{1/2}\log n)\), which satisfies Assumption 4. As we know the ground-truth generation process and can generate different graphs with the same law of data generation, we use this dataset for validating the theorems and showing generalization ability in an inductive setting.
**Adult**: is a real consensus dataset. We use age and the logarithm of capital gain as the hidden features and construct a \(k\)-nearest neighbor graph, i.e., people with similar ages and incomes become friends.
**Settings.**: We use two different problem settings.
**Transductive**: setting uses a single graph. We are given the true hidden features for some training nodes, and estimate the hidden features of other nodes. We use \(70\) percent of the nodes for training and the reset nodes for testing.

Figure 3: **Results for the Transductive Setting.** Overall, the proposed method succeeded in recovering the ground truth hidden features while tSNE to \(\mathbf{X}\) (Eq. (3)) fails, and GNNs and GATs are mediocre. (Top Left) The ground truth hidden embeddings. The node ids are numbered based on the x-coordinate and shown in the node colors. These node ids are for visualization purposes only and are NOT shown to GNNs and downstream algorithms. (Top Mid) The input graph constructed from the hidden features. The positions of the visualization are NOT shown to GNNs. (Top Right) tSNE plot on the synthetic node features, i.e., Eq. (3). These results indicate that the node features are not informative for feature recovery, which introduces challenges to the task. (Bottom Left) The recovered features by the proposed method. They resemble the ground truth not only with respect to the cluster structure but also the x-coordinates (shown in the node colors), the curved moon shapes in the two-moon dataset, and the striped pattern in the Adult dataset. The \(d_{G}\) value (Eq. (2)) is small, which indicates the success of the recovery and validates the theory. (Bottom Mid) The recovered features by GNNs. They do not resemble the true hidden features. The \(d_{G}\) value is mediocre. (Bottom Right) The recovered features by GATs. They do not resemble hidden features, but some clusters are detected (shown in the node colors). The \(d_{G}\) value is mediocre. These results show that existing GNNs can extract some information from the graph structure, but they do not fully recover the hidden features.
**Inductive**: setting uses multiple graphs. In the training phase, we are given two-moon datasets with \(n=1000\) to \(5000\) nodes and their true hidden features. In the test phase, we are given a new two-moon dataset with \(n=10000\) nodes and estimate the hidden features of the test graph. This setting is challenging because (i) we do not know any hidden features of the test graphs, and (ii) models need to generalize to extrapolation in the size of the input graphs.

**Methods.** As we prove the theorems by construction and know the configuration of GNNs that recover the hidden features except for the unknown parameters about the ground truth data (i.e., the scale \(g_{n}\) and the constant \(c\) that depends on \(p\) and \(\bar{s}\)), we use the model architecture that we constructed in our proof and model the unknown parameters, i.e., scaling factor \(g_{n}\), using \(3\)-layer perceptron with hidden \(128\) neurons that takes \(n\) as input and output \(g_{n}\). This model can be regarded as the GNNs with the maximum inductive bias for recovering the hidden features. We fix the number of the selected nodes \(m=500\) throughout the experiments.

**Baselines.** We use \(3\)-layer Graph Attention Networks (GATs) (Velickovic et al., 2018) and Graph Isomorphism Networks (GINs) (Xu et al., 2019) as baselines. We feed the same explicit node features as in our method, i.e., Eq. (3), and use the hidden features as the target of the regression.

**Details.** We optimize all the methods with Adam (Kingma & Ba, 2015) with a learning rate of \(0.001\) for \(100\) epochs. The loss function is \(d_{G}(\mathbf{\hat{Z}}_{\theta}[\text{train-mask}],\mathbf{Z}[\text{train-mask}])\), where \(\mathbf{\hat{Z}}_{\theta}\in\mathbb{R}^{n\times d}\) is the output of GNNs, \(\mathbf{Z}\) is the ground truth hidden embeddings, and train-mask extracts the coordinates of the training nodes.

**Results.** Figures 3 and 4 show the results. As the rigid transformation factor cannot be determined, we align the recovered features using the orthogonal Procrustes analysis in the postprocessing. We make the following observations.

**Observation 1**.: **Recovery Succeeded.** As the lower left panels show, the proposed method succeeds in recovering the hidden features solely from the input graphs. Notably, not only coarse structures such as connected components are recovered but also details such as the curved moon shape in the two-moon dataset and the striped pattern in the Adult dataset are recovered.

**Observation 2**.: **Existing GNNs are mediocre.** As the lower right panels show, GINs and GATs extract some information from the graph structure, e.g., they map nearby nodes to similar embeddings as shown by the node colors, but they fail to recover the hidden features accurately regardless of their strong expressive powers. This is primarily because the input node features contain little information, which makes recovery difficult. These results highlight the importance of inductive biases of GNNs to exploit the hidden features.

**Observation 3**.: **tSNE fails.** The upper right panels show that tSNE on the explicit node features \(\mathbf{X}\) failed to extract meaningful structures. These results indicate that the synthetic node features (Eq. (3)) do not tell anything about the hidden features, and GNNs recover the hidden features solely from the graph.

**Observation 4**.: **Recovery Succeeded in the Inductive Setting.** Figure 4 shows that the proposed method succeeded in the inductive setting as well. This shows that the ability of recovery can be transferred to other graph sizes as long as the law of data generation is the same.

## 6 Conclusion

In this paper, we showed that GNNs can recover the hidden node features, which contain all information about the graph structure, solely from the graph input. These results provide a different perspective from the existing results, which indicate that GNNs simply mix and smooth out the given node features. In the experiments, GNNs accurately recover the hidden features in both transductive and inductive settings.
