On the Unreasonable Effectiveness of Feature Propagation in Learning on Graphs with Missing Node Features
Authors: Emanuele Rossi
Henry Kenlay
Maria I. Gorinova
Benjamin Paul Chamberlain
Xiaowen Dong
Michael M. Bronstein
Venue: ICLR 2022 Submitted (2022)
Keywords: graph neural networks
missing features
graphs
feature propagation

Abstract: While Graph Neural Networks (GNNs) have recently become the {\em de facto} standard for modeling relational data, they impose a strong assumption on the availability of the node or edge features of the graph. In many real-world applications, however, 
features are only partially available; for example, in social networks, age and gender are available only for a small subset of users. We present a general approach for handling missing features in graph machine learning applications that is based on minimizing the Dirichlet energy and leads to a diffusion-type differential equation on the graph. The discretization of this equation produces a simple, fast and scalable algorithm which we call Feature Propagation. We experimentally show that the proposed approach outperforms previous methods on six common node-classification benchmarks and can withstand surprisingly high rates of missing features: on average we observe only around 5% relative accuracy drop when 99% of the features are missing. Moreover, it takes only 10 seconds to run on a graph with ~2.5M nodes and ~123M edges on a single GPU.

Under review as a conference paper at ICLR 2022
ON THE UNREASONABLE EFFECTIVENESS OF FEATURE PROPAGATION IN LEARNING ON GRAPHS WITH MISSING NODE FEATURES
Anonymous authors Paper under double-biee blind review
ABSTRACT
While Graph Neural Networks (GNNs) have recently become the de facto stan- dard for modeling relational data, they impose strong assumption on the avail- ability the node or edge features of the graph. In many real-world applications, however, features are only partially available; for example, in social networks, age and gender are available only for a small subset of users. We present a general approach for handling missing features in graph machine learning applications that is based on minimization of the Dirichlet energy and leads to a diffusion-type differential equation on the graph. The discretization of this equation produces a simple, fast and scalable algorithm which we call Feature Propagation. We experimentally show that the proposed approach outperforms previous methods on seven common node-classee cldsslaassiiication benchmarks and can withstand surprisingly high rates of missing features: on average we observe only around 4% relative accuracy drop when 99% of the features are missing. Moreover, it takes only 10 seconds to run on a graph with 2.55 nodes and ~123M edges on single GPU.
INTRODUCTION
Graph Neural Networks (GNNs) (Gori et al., 2005; Scarselli et al., 2008; Kipf & Welling, 2017; Gilmer al., 2017a; Veličković al., 2018; Bronstein al., 2017) have been successful on broad range of problems and in variety of fields (Duvenaud et al., 2015; Ying et al., 2018; Zitnik et al., 2018; Gainza al., 2020; Sanchez-Gonzaler, al., 2020; Shlomi al., 2020; Derrow-Pinins Piniow-- al., 2021). GNNs typically operate by a message-passing mechanism (Battaglia et al., 2018; Gilmer et al., 2017b), where at each layer, nodes send their feature representations ("messages") to their neighbors. The feature representation of each node is initialized to their original features, and is updated by repeatedly aggregating incoming messages from neighbors. Being able to combine the topological information with feature information is what distinguishes GNNs from other purely topological learning approaches such as random walks (Perozzi et al., 2014; Grover & Leskovec, 2016) or label propagation (Zhu & Ghahramani, 2002), and arguably what leads to their success.
GNN models typically assume a fully observed feature matrix, where rows represent nodes and columns feature channels. However, in real-world scenarios, each feature is often only observed for a subset of the nodes. For example, demographic information can be available for only a small subset of social network users, while content features are generally only present for the most active users. In co- purchase network, not all products may have full description associated with them. With the rising awareness around digital privacy, data is increasingly available only upon explicit user consent. In all the above cases, the feature matrix contains missing values and most existing GNN models cannot be directly applied.
While classic imputation methods (Liu et al., 2020; Yoon et al., 2018; Kingma & Welling, 2014) can be used to fill the missing values of the feature matrix, they are unaware of the underlying graph structure. Graph Signal Processing, a field attempting to generalize classical Fourier analysis to graphs, offers several methods that reconstruct signals on graphs (Narang et al., 2013). How- ever, they do not scale beyond graphs with a few thousand nodes, making them infeasible for prac- tical applications. More recently, SAT (Chen et al., 2020), GCNMF (Taguchi et al., 2021) and PaGNN (Jiang & Zhang, 2021) have been proposed adapt GNNs to the case of missing features.

---

Under review as a conference paper at ICLR 2022
Feature Propagation
GNN
Prediction
Unknown Festure
Known Feature
Reconstructed Peature
Figure 1: A diagram illustrating Feature Propagation framework. On the left, graph with miss- ing node features. In the initial reconstruction step, Feature Propagation reconstructs the missing features by iteratively diffusing the known features in the graph. Subsequently, the graph and the constructed node features are fed into a downstream GNN model, which then produces a prediction.
However, they are not evaluated at high missing features rates (> 90%), which occur in many real- world scenarios, and where we find them to suffer. Moreover, they are unable to scale to graphs with more than few hundred thousand nodes. At the time of writing, PaGNN the state-of-the-an method for node classification with missing features.
Contributions We present general approach for handling missing node features in graph machine learning tasks. The framework consists of an initial diffusion-based feature reconstruction step followed by downstream GNN. The reconstruction step is based Dirichlet energy minimization, which leads to a diffusion-type differential equation on the graph. Discretization of this differential equation leads we call Feature Propagation (FP). FP outperforms state-of-the-art methods on six standard node- classification benchmarks and presents the following advantages:
very simple, fast, and scalable iterative algorithm which
Theoretically Motivated: FP emerges naturally as the gradient flow minimizing the Dirichlet energy and can be interpreted diffusion equation the graph with known features used as boundary conditions.
Robust to high rates of missing features: FP can withstand surprisingly high rates of missing features. our experiment, we observe on average around 4% relative accuracy drop when up to 99% of the features are missing. In comparison, GCNMF and PaGNN have an average drop of 53.33% and 21 25% respectively.
Generic: FP can be combined with any GNN model to solve the downstream task; in contrast, GCNMF and PaGNN specific GCN-type models.
Fast and Scalable: FP takes only around 10 seconds for the reconstruction step on OGBN- Products (a graph with ~.55 nodes and ~123 edges) on single GPU. GCNMF and PaGNN run out-of oft-of-memory on this dataset.
2 PRELIMINARIES
Let G GVVVV EV an undirected graph with n x n adjacency matrix A and node feature vector E _
The graph Laplacian is an n x n positive semi-definite matrix I- A, where Á D D the normalized adjacency matrix and D diag(E, aljs.... E, and) is the diagonal degree matrix.
For convenience, assume scalar node features. Our derivations apply straightforwardly to the case of d-dimensional features represented as x matrix X.
2

---

Under review as a conference paper at ICLR 2022
Denote by V& S V the set of nodes on which the features known, and by Vu VE
V \\ V the
unknown ones. We further assume the ordering of the nodes such that we can write
Xk X
A
Ak
A
A
! kk A
Iou
A
Auu
A
uu
uu
Because the graph is undirected, A is symmetric and thus A Auk and AT tacitly assume this in the following discussion.
km
uk- We will
Graph feature interpolation is the problem of reconstructing the unknown features x, given the graph structure G and the known features Xę. The interpolation task requires some prior the behavior of the features of the graph, which can be expressed in the form of an energy function f(x, G). The most common assumption is feature homophily (i.e., that the features of every node similar to those of the neighbours), quantified using a criterion of smoothness such as the Dirichlet energy. Since in many cases the behavior of the features is not known, the energy can possibly be learned from the data.
Learning on a graph with missing features is transductive learning problem (typically node- wise classification or regression using some GNN architecture) where the structure of the graph G is known while the labels and node features are only partially known on the subsets Vi and V of nodes, respectively (that might be different and even disjoint). Specifically, we try to learn function f(xi, G) such that Si Rs ye for i E Ví. Learning with missing features can be done by pre-processing step of graph signal interpolation (reconstructing the learning task, followed by the learning task f(x, G) on the
estimate X of the full feature
vector x from X₃.) independent inferred fully-featured graph. In some settings, are not interested in recovering the features per se, but rather ensuring that the output of the function f on these features is correct - arguably a more 'forgiving' setting.
FEATURE PROPAGATION
We assume to be given X₁. and attempt to find the missing node features x,, by means of interpolation that minimizes some energy ((x, G). In particular, we consider the Dirichlet energy E(x, G) ()====))))) x Ax Eij dzy (2; zy)² where āz the individual entries of the normalized adjacency A. The Dirichlet energy is widely used as smoothness criterion for functions defined on the nodes of the graph and thus promotes homophily. Functions minimizing the Dirichlet energy are called harmonic; without boundary conditions, it minimized by a constant function.
While the Dirichlet energy is convex and possible to derive minimizer in a closed-form, as shown below, the computational complexity makes it unfeasible for graphs with many nodes with missing features. Instead, we consider the associated gradient flow x(() = VV((((t) as differential equation with boundary condition xx(t) Xx whose solution the missing nodes, X, oo x,, (t), provides the desired interpolation.
Gradient flow.
For the Dirichlet energy, Vxl Ax and the gradient flow takes the form of the standard isotropic heat diffusion equation on the graph,
x(t) = Ax((t)
(IC) x x(0)
X x (0)
(BC)
(t) Xx
where IC and BC stand for initial conditions and boundary conditions respectively. By incorporating the boundary conditions, we can compactly express the diffusion equation as
Xx
A
x (1)
X + A x
uk
As expected, the gradient flow of the observed features O, given that they do not change during the diffusion.
The evolution of the missing features can be regarded as a heat diffusion equation with a constant heat source A wx Xx coming from the boundary (known) nodes. Since the graph Laplacian matrix is
3

---

Under review as a conference paper at ICLR 2022
positive semi-definite, the Dirichlet energy is convex. Its global minimizer is given by the solution to the closed-form equation Vx.. l = O and by rearranging the final [Vil rows of Equation we get the solution x, - Xx. This solution always exists as A is non-singular, by virtue of the following:
Proposition (The sub-Laplacian matrix of an undirected connected graph is invertible). Take any undirected, connected graph with adjacency matrix A E {0, 1]mx", and its Laplacian A I D-1/2AD--1- with D being the degree matrix of A. Then, for any principle sub-matrix L E b of the Laplacian, where 1 S < n. Lu is invertible.
See Appendix A. Also, while the proposition assumes that the graph is connected, our anal- ysis and method generalize straightforwardyy in the cases of disconnected graph as we can simply apply Feature Propagation each connected component independently.
Proof:
However, solving a system of linear equations is computationally expensive (incurring (( complexity for matrix inversion) and thus intractable for anything but only small graphs.
Iterative scheme. As an alternative, we can discretize the diffusion equation (1) and solve it by an iterative numerical scheme. Approximating the temporal derivative as forward difference with the time variable discretized using fixed step (t = hk for step size h > and = 1, ..). we obtain the explicit Euler scheme:
(l++1)
h
0
(k)
I
) x(()
I hA ak
(())
A
h h uk
h
I - hA
uuk
For the special case of h I, we can use the following observation
À A I 0
A
A kuu
A Rk
-
I
uk
A uu
to write the iteration formula as
I Auk
x (k+1)
(R)
(2)
unu
The Euler scheme is the gradient descent of the Dirichlet energy. Thus, applying the scheme de- creases the Dirichlet energy and results in the fea-
0.040
Spectral Coefficient
0.035
Original Feature
Reconstructed Feature (30% missing)
0.030
Reconstructed (60%, missing)
tures becoming increasingly smooth. Iteration (2)
0.025
Reconstructed Feature (99% missing)
can be interpreted as successive low-pass filtering.
Figure depicts the magnitude of the graph Fourier coefficients of the original and reconstructed fea-
0.015
0.010
tures on the Cora dataset, indicating that the higher the rate of missing features, the stronger the low- pass filtering effect.
0.005
0.000
500
1000
1500
2000
2500
Eigenvalue Index
The following results shows that the iterative scheme with h always converges and its steady state is equal to the closed form solution. Importantly, the solution does not depend on the initial values (0) given the unknown features.
Figure 2: Graph Fourier transform magni- tudes of the original Cora features (red) and those reconstructed by FP for varying rates of missing rates (we take the average over feature channels). Since FP minimizes the Dirichlet energy, it can be interpreted as a low-pass filter, which is stronger for higher rate of missing features.
Proposition Take any undirected and connected graph with adjacency matrix A E {0, 13mxn, and with D being the degree matrix of A. Let X E Rexd_
normalised Adjacency A D D-1/2AD
X E Rexd be a feature matrix and define the following recursive relation
((k)
I
(k-1)
Aak
Áuu
Then this recursion converges and the steady state is given to be
X
lim (x)
A
X
kk
Proof: See Appendix A.
4

---

Under review as a conference paper at ICLR 2022
Feature Propagation Algorithm. Equation 2 provides an extremely simple and scalable it- erative algorithm to reconstruct the missing fea- tures, which we refer to as Feature Propaga- fion (FP). While Xu can be initialized to any value, we initialize x, to zero and find 40 iter- ations to be enough to provide convergence for all datasets we experimented on. At each iter- ation, the diffusion occurs from the nodes with known features to the nodes with unknown fea- tures as well as among the nodes with unknown features.
Algorithm 1 Feature Propagation
1: y x
2:
while x has not converged do
3:
x Ax
> Propagate features
4:
X5: 6 Yk
b Reset known features
5: end while
It is worth noting that the proposed algorithm bears some similarity with Label Propagation (Zhu & Ghahramani, 2002) (LP),, which predicts class for each node by propagating the known labels in the graph. Differently from our setting of diffusion of continuous node features, they deal with discrete label classes directly, resulting in a different diffusion operator. However, the key difference between them lies in how they used. LP is used to directly perform node classification, taking into account only the graph structure and being unaware of node features. On the other hand, FP used to reconstruct missing features, which then fed into downstream GNN classifier. FP allows a GNN model to effectively combine features and graph structures, even when most of the features are missing. Our experiments show that FP+GNN always outperforms LP, even in cases of extremely high rates of missing features, suggesting the effectiveness of FP. Also, the derived scheme is special case of Neural Graph PDEs, and in turn it is also related the iterative scheme presented in Zhou & Schölkopf (2004).
Extension to Vector-Valued Features. The method extends to vector-valued features by simply replacing the feature vector x with n d feature matrix X in Algorithm 1, where d is the number of features. Multiplying the diffusion matrix A by the feature matrix X diffuses each feature channel independently.
Learning. One significant advantage of FP is that it can be easily combined with any graph learn- ing model to generate predictions for the downstream task. Moreover, FP is not aimed at merely reconstructing the node features, and instead by only reconstructing the lower frequency compo- nents of the signal, it is by design very well suited to be combined with GNNs, which are known to mainly leverage these lower frequency components (Wu et al., 2019). Our approach is generic and can be used for any graph-related task for missing features, such as node classification, link prediction and graph classification. In this paper, we focus on node classification.
RELATED WORK
Matrix completion. Several optimization-based approaches (Candès & Recht, 2009; Hu et al., 2008) as well as learning- caaning-based approaches (Liu et al., 2020; Yoon et al., 2018; Kingma Welling, 2014) have been proposed to solve the matrix completion problem. However, they are unaware of the underlying graph structure. Graph matrix completion (Kalofolias et al., 2014; van den Berg et al., 2017; Monti et al., 2017; Rao et al., 2015) extends the above approaches to make use of an underlying graph. Similarly, Graph Signal Processing offers several methods to interpolate signals on graphs. Narang et al. (2013) prove the necessary conditions for graph signal to be recovered perfectly, and provide a corresponding algorithm. However, due to the optimisation problems involved, most above approaches are too computationally intensive and cannot scale graphs with more than ~ ,0000 nodes. Moreover, the goal of all above approaches is to reconstruct the missing entries of the matrix, rather than solving a downstream task.
Extending GNNs to missing node features. SAT (Chen et al., 2020) consists of a Transformer- like model for feature reconstruction and a GNN model to solve the downstream task. GC- NMF (Taguchi al., 2021) adapts GCN (Kipf & Welling, 2017) to the case of missing node features by representing the missing data with a Gaussian mixture model. PaGNN (Jiang & Zhang, 2021) is a GCN-like model which uses partial passage-passing scheme to only propagate observed features.
5

---

Under review as a conference paper at ICLR 2022
While showing reasonable performance for low rates of missing features, these methods suffer in regimes of high rates of missing features, and do not scale to large graphs.
Other related GNN works. Several papers investigate how to augment GNNs when node features are available (Cui et al., 2021). as well as investigating the performance of GNNs with random features (Sato et al., 2021; Abboud et al., 2021). Dirichlet energy minimization has been widely used as a regularizer in several graph-related tasks (Zhu et al., 2003; Zhou & Schölkopf, 2004; Weston et al., 2008). Discretizion of continuous diffusion on graphs has already been explored in Chamberlain et al. (2021) and Xhonneux et al. (2020).
5 EXPERIMENTS AND DISCUSSION
Datasets. We evaluate on the task of node classification on several benchmark datasets: Cora. Citeseer and PubMed (Sen et al., 2008), Amazon-Computest and OGBN-Arxiv (Hu et al., 2020). To test the scalability of our method, we also test it on OGBN- Products (2, 449,029 nodes,
Amazon-Photo (Shchur et al., 2018)
edges). We report dataset statistics in table 3 (Appendix).
Baselines. We compare to Label Propagation (Zhu & Ghahramani, 2002), strong feature- agnostic baseline which only makes use of the graph structure by propagating labels on the graph. We additionally compare to feature-imputation methods that are graph-agnostic, such as setting the missing features to 0 (Zero), a random value from a standard Gaussian (Random), or the global mean of that feature over the graph (Global Mean) 2, We also compare baseline, which sets a missing feature to the mean (of that same feature) over the neighbors of a node (Neighbor Mean). We additionally experiment with MGCNN (Monti et al., 2017), a geometric graph completion method which learns how to reconstruct the missing features by making use of the observed features and the graph structure. For all the above imputation and matrix completion baselines, as well as for our Feature Propagation, we experiment with both GCN (Kipf & Welling, 2017) and GraphSage with mean aggregator (Hamilton et al., 2017) as downstream GNNs. We also compare to recently sfate-of-the-aat methods for learning in the missing features setting (GC- NMF (Taguchi et al., 2021) and PaGNN (Jiang & Zhang, 2021)). For GCNMF we use the publicly available code.? We could not find publicly available code for PaGNN so use our own implemen- tation for this comparison. We do not compare to other commonly used imputation based methods such VAE (Kingma & Welling, 2014) GAIN (Yoon et al., 2018), nor to the Transformer- based method SAT (Chen et al., 2020), as they have previously been shown to consistently underperform GCNMF and PaGNN (Taguchi al., 2021; Jiang & Zhang, 2021).
simple graph-based imputation
Experimental Setup. We report the mean and standard error of the test accuracy, computed over 10 runs, in all experiments. Each run has a different train/validationntess split (apart from OGBN datasets where we use the provided splits) and mask of missing features'. 'he splits are generated at random by assigning 20 nodes per class to the training set, 1500 nodes in total to the validation set and the rest to the test set, similar to Klicpera et al. (2019). For a fair comparison, we use the same standard hyperparameters for all methods across all experiments. We train using the Adam (Kingma & Ba, 2015) optimizer with a learning rate of 0.005 for a maximum of 10000 epochs, combined with early stopping with a patience of 200. Downstream GNN models (as well as GCNMF and PaGNN) use 2 layers with a hidden dimension of 64 and dropout rate of 0.5 for all datasets, apart from OGBN datasets where layers and hidden dimension of 256 are used. For OGBN- Arxiv we also employ the Jumping Knowledge scheme (Xu et al., 2018) with max aggregation. Feature Propagation uses 40 iterations to diffuse the features. We want to emphasize that we did not perform any hyperparameter tuning, and FP proved perform consistently with any reasonable choice of hyperparameters. We use neighbor sampling (Hamilton et al., 2017) when training on OGBN-Products. All experiments are conducted on an AWS 1xxlare machine with 8 NVIDIA V100 GPUS
"If a feature is not observed for any of the node's neighbors, we set it to zero. "ntts://gihuu..com///a htt.u//...oo//aabb////ntttttt
4 'Fach entry of the fcature matrix is independently missing with probability equal to the missing rate.
Fach V100 GPU has 16GB of memory.

---

Cora Under review as a conference paper at ICLR 2022
COAP
Moing Fudae
Box Moo Fareen
Computes
Fire Mising
Figure 3: Test accuracy for varying rate of missing features on six common node-classfficatinn benchmarks. For methods that require a downstream GNNs, a 2-layer GCN (Kipf & Welling, 2017) is used. On OGBN-Arxiv, GCNMF goes out-of-memory and is not reported.
Dataset
Full Features
50.0% Missing
90.0% Missing
99.0% Missing
80.39%
79.70%(-0.86%)
79.77%(-0.777%
(-.22%(-
CiteSeer
67.48%
65.74%(-2.57%%
(-.87%(-2
65.40%(-3.08%)
PubMed
77.36%
76.68%(-0.89%)
75.85%((11.96%)
74.29%((33.97%)
Photo
91.73%
(1.29%(-))48%))
(9.48%((22466%
87.73%(-4.36%)
Computers
85.65%
84.77%(-1.04%%)
82.71%((3.433%)
80.94%(-).51%)
OGBN-Arxiv 72.22%
(1.42%(-1.10%%
70.47%((2.433)
69.09%((44333%)
OGBN-Products 78.70%
77.16%(-1.96%))
7-.54%
74.94%((4478%%)
Average 79.08%
77.11%((2248%%)
(5.80%((4.110%)
Table 1: Performance of Feature Propagation (combined with GCN model) for 50%, 90% and 99% of missing features, and relative drop compared to the performance of the same model when all features present. On average, our method loses only 2.50% of relative accuracy with 90% of missing features, and 4. 12% with 99% of missing features.
Dataset
GCNMF
PaGNN
Label Propagation
FP (Ours)
Cora
34.54+2.07
58.0310.57
74.6
78.22:0.32
CiteSeer
3..65+1.112
46.02+0..8
64.60+t0.40
65.40-
PubMed
3..8
54.25+10.70
73.81
0..5
Photo
29.64
85,4110..28
83.45
87.73-10.27
Computers
3..74
17.33
74.48
80.94
OGBN-Arxiv
OOM
53.9810.08
67.56+10.00
69.09-0000
OGBN- -GoN-Products
00M
OOM
74.42=00.00
74.94+0.07
Table 2: Performance of GCNMF, PaGNN and FP(+GCN) with 99% of features missing, as well as Label Propagation (which is aeature-agnostiic. GCNME and PaGNN perform respectively 58.33% and 21.25% worse in terms of relative accuracy in this scenario compared to when all the features are present. In comparison, FP has only a 4. 4.% drop.
Node Classification Results. Figure 3 shows the results for different rates of missing features (x- axis), when using GCN as a downstream GNN (results with GraphSAGE are reported in Figure of the Appendix). FP matches or outperforms other methods in all scenarios. Both GCNMF and PaGNN are consistently outperformed by the simple Neighbor Mean baseline. This is not com- pletely unexpected, Neighbor Mean can be seen as first-order approximation of Feature Propa-

---

Under review as a conference paper at ICLR 2022
50% Missing Features
Missing Features
90% Missing Features
Tel. Acceoc
Tes:
42
Figure 5: Test accuracy on the synthetic datasets from Abu-El-Haija et al. (2019) with different levels of homophily. We use GraphSage as downstream model as it is preferable to GCN on low homophily data (Zhu al., 2020).
gation, where only one step of propagation is performed (and with a slightly different normalization of the diffusion operator). We elaborate on the relation between Neighbor Mean and Feature Propa- gation as well as on the results of the other baselines Section A.4 of the Appendix, Interestingly, most methods perform extremely well up to 50% of missing features, suggesting that in general node features are redundant, as replacing half of them with zeroa (Zero bascline) has little effect on the performance. The gap between methods opens up from around 60% of missing features, and is particularly large for extremely high rates missing features (90% or 99%): FP is the only feature-aware method which is robust to these high rates on all datasets (see Table 2). Moreover, FP outperforms Label Propagation on all datasets, even in the extreme case of 99% missing features. On some datasets, such as Cora, Photo, and Computers, the gap is especially significant. We con- clude that reconstructing the missing features using FP is indeed useful for the downstream task. We highlight the surprising results that, on average, FP with 99% missing features performs only 4. 4.12% worse (in relative accuracy terms) than the same GNN model used with no missing features, compared to 58.33% and 21.25% for GCNMF and PaGNN respectively.
Run-time analysis. Feature Propagation scales to extremely large graphs, as it only consists of repeated sparse-to-dense ma- trix multiplications. Moreover,
Camputess
DGBN-Anxi
Possing Tiee
Puesing The
can be regarded as a pre-
processing step, and performed only once, separately from training. In Figure 4 pare the run-time to complete the training of the model for FP, PaGNN and GCNMF. The time for FP includes both the feature propagation step to reconstruct the missing features, as well training of a downstream GCN model. FP is around 3x faster than PaGNN and GCNME The propagation step of FP takes only fraction of the total running time, and the vast majority of the time is spent training of the donwstream model. The feature propagation step takes only ~0.6s for Computers, ~0.8s for OGBN-Arxiv and 10.55 for using a single GPU. Both PaGNN and GCNMF go out-of-memory on OGBN-Products
Figure 4: Run-time (in seconds) of FP, PaGNN and GCNME. FP is faster than both other methods. GCNME goes out-of- memory (OOM) OGBN-Arxiv.
When does Feature Propagation work? Since FP can be interpreted a low-pass filter that smoothes the features on the graph, we expect to be suitable in the case of homophilic graph data (where neighbors tend to have similar attributes), and, conversely, to suffer in scenarios of low homophily. To verify this, we experiment on the synthetic dataset from Abu-El -b--El-Haija et al. (2019), hypothesis:
which consists of 10 graphs with different levels of homophily. Figure confirms when the homophily is high, Feature Propagation performs similarly to the case when all the features known. As the homophily decreases, the gap between the widens to become extremely large
8

---

Under review as a conference paper at ICLR 2022
in cases of zero homophily. In such scenarios, FP is only slightly better than setting the missing features to zero (Zero baseline). This observation calls for a different kind of non-homogeneous the features that can potentially be made learnable for low- low-homophily data.
diffusion dependent We leave this as future work.
CONCLUSION
We have introduced novel approach for handling missing node features in graph-learning tasks. Our Feature Propagation model can be directly derived from energy minimization, and can be im- plemented as an efficient iterative algorithm where the features are multiplied by a diffusion matrix, before resetting the known features to their original value. Experiments on number of datasets sug- gest that FP can reconstruct the missing features a way that is useful for the downstream task, even when 99% of the features are missing. FP outperforms recently proposed methods by significant margin on common benchmarks, while also being extremely scalable.
Limitations. While our method is designed for homophilic graphs, more general learnable diffu- sion could be adopted to perform well in low homophily scenarios, as discussed in Section Feature Propagation is designed for graphs with only one node and edge type, however it could be extended to heterogenous graphs by having separate diffusions for different types of edges and nodes. Finally, Feature Propagation treats feature channels independently. To account for dependencies, diffusion with channel mixing should be used.
Reproducibility Statement. The datasets used in this paper are publicly available and can be ob- tained from either the Pytorch-Geomend mark (Hu et al., 2020). In the supplementary material we provide our code, together with README file explaining in detail how to reproduce the results presented in the paper. All hy- perparameters and their values are listed in section
library (Fey & Lenssen, 2019) or Open Graph Bench-
Ethical Statement. Our work is aimed at improving the performance of Graph Neural Networks. While we believe that nothing in our work raises specific ethical concerns, the recent broad adop- tion of GNNs in industrial applications opens the possibility to the misuse of such methods with potentially detrimental societal impact.
REFERENCES
Ralph Abboud, ismail ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth Inter- national Joint Conference Artificial Intelligence, IJCAI-21, pp. 2112 2118, 2021.
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor. Hrayr Harutyunyan. Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolu- tion architectures via sparsified neighborhood mixing. In International Conference on Machine Learning (ICML), 2019.
Peter Battaglia, Jessica Blake Chandler Hamrick, Victor Bapst, Alvaro Sanchez, Vinicius Zambaldi. Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, Caglar Gulcehre. Francis Song. Andy Ballard, Justin Gilmer, George Dahl, Ashish Vaswani, Kelsey Allen, Charles Nash, Victoria Jayne Langston, Chris Dyer, Nicolas Heess, Daan Wierstra, Push- meet Kohli, Matt Botvinick, Oriol Vinyals. Yujia Li, and Razvan Pascanu. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1866.00 118806661666 2018.
Abraham Berman and Robert J. Plemmons. Nonnegative Matrices in the Mathematical Sciences. SIAM, 1994.
Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geo- metric deep learning: Going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4): 18 48-42, 2017.
Emmanuel J. Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foun- dations of Computational mathematics, 96):717-772, 2009.

---

Under review as a conference paper at ICLR 2022
Benjamin Paul Chamberlain, James R. Rowbottom, Maria L. Gorinova, Stefan Webb, Emanuele Rossi, and Michael M. Bronstein. GRAND: Graph neural diffusion. In International Conference on Machine Learning (ICML), 2021.
Xu Chen, Siheng Chen, Jiangehao Yao, Huangjie Zheng, Ya Zhang, and Ivor Tsang. Learning atribute-missing graphs. IEEE Transactions on Puttern Analysis and Machine Intelligence, PP, 2020.
Fan K. Chung. Spectral Graph Theory. Number 92. American Mathematical Soc., 1997.
Hejie Cui, Zijie Lu, Pan Li, and Carl Yang. On positional and structural node features for graph neural networks on non-attributed graphs. International Workshop on Deep Learning on Graphs (DLGGKDD), 2021.
Austin Derrow-Piniin Piniinn Jennifer She, David Wong, Oliver Lange, Todd Hester, Luis Perez, Mare Nunkesser, Seongjae Lee, Xueying Guo, Peter W Battaglia, Vishal Gupta, Ang Li, Zhongwen Xu, Alvaro Sanchez-Gonzalez, Yujia Li, and Petar Veličković. Traffic Prediction with Graph Neural Networks in Google Maps. 2021.
David Duvenaud, Dougal Maclaurin, Jorge Aguilera-Iparraguine Rafael Gómez-Bombarelli, Tim- othy Hirzel, Alán Eapuru-Guzike and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In Proceedings of the 28th International Conference on Neural Information Processing Systems, pp. 2224-2232, 2015.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Pablo Gainza, Freyr Sverrisson, Federico Monti, Emanuele Rodolà, Michael M. Bronstein, and Bruno E. Correia. Deciphering interaction fingerprints from protein molecular surfaces. Nature Methods, 17(2):184 192, 2020.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017a.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272, 2017b.
Marco Gori, Gabricle Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734. IEEE, 2005.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
William L. Hamilton, Rex Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035. 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00mm 00687, 2020.
Yifan Hu, Yehuda Koren, and Chris Volinsky. Collaborative filtering for implicit feedback datasets. In 2008 Eighth IEEE International Conference Data Mining, pp. 263-272, 2008
Bo Jiang and Ziyan Zhang. Incomplete graph representation and learning via partial graph neural networks. arXiv preprint arXiv:2003.101330 2021.
Vassilis Kalofolias, Xavier Bresson, Michael M. Bronstein, and Pierre Vandergheynst. Matrix com- pletion on graphs. ArXiv preprint urXiv:1408. /717, 2014.
10

---

Under review as a conference paper at ICLR 2022
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations, ICLR, 2015.
Diederik P. Kingma and Max Welling. Auto-encoding variational Bayes. In International Confer- ence on Learning Representations, ICLR, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, ICLR, 2017.
Johannes Klicpera, Stefan WeiBenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
Xinwang Liu, Xinzhong Zhu, Miaomiao Li, Lei Wang, En Zhu, Tongliang Liu, Marius Kloft, Ding- gang Shen, Jianping Yin, and Wen Gao. Multiple kemel k-means with incomplete kernels. IEEE Transactions on Puttern Analysis and Machine Intelligence, 42(5): 191-1204, 2020.
Federico Monti, Michael M. Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 7700-3710, 2017. ISBN
Sunil K. Narang, Akshay Gadde, and Antonio Ortega. Signal processing techniques for interpolation in graph structured data. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 5445-5449, 2013.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Nikhil Rao, Hsiang-Fu Yu, Pradeep K Ravikumar, and Inderjit S Dhillon. Collaborative filter- ing with graph information: Consistency and scalable methods. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garneu (eds.), Advances in Neural Information Processing Sys- tems, volume 28. Curran Associates, Inc., 2015. URL https: pttp///eeoccecccee/eeepeocccccsp neurips. pdf.
Alvaro Sanzhez-Gonzalez, Jonathan Godwin, Tobias Pfatf, Rex Ying, Jure Leskovec, and Peter Battaglia. Learning simulate complex physics with graph networks. In International Confer- ence on Machine Learning (ICML), 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 202/ SIAM International Conference Data Mining, SDM, pp- 333-341. SIAM, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. Al Magazine, 29(3):93-106, 2008
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS, 2018.
Jonathan Shlomi, Peter Battaglia, and Jean-Roch Vlimant. Graph neural networks in particle physics. Machine Learning: Science and Technology, 2(2):021001, 2020.
Hibiki Taguchi, Xin Liu, and Tsuyoshi Murata. Graph convolutional networks for graphs containing missing features. Future Generation Computer Systems, 117:155-168, 2021.
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprint 1782031706.02263, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, ICLR, 2018.
11

---

Under review as a conference paper at ICLR 2022
Jason Weston, Frédéric Ratle, and Ronan Collobert. Deep learning via semi-supervised embedding. In Proceedings of the 25th International Conference on Machine Learning, pp. 1168-1175, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 978 9781605582054,
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceed- ings of Machine Learning Research, pp. 6861-6871. PMLR, 09-15 Jun 2019.
Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In Interna- tional Conference on Machine Learning, pp. 10432-10441. PMLR, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453-5462. PMLR, 10-15 Jul 2018.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Pro- ceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974-983. Association for Computing Machinery, 2018. ISBN 9781450355520.
Jinsung Yoon, James Jordon, and Mihaela van der Schaar. GAIN: Missing data imputation using generative adversarial nets. In Proceedings of the 35th International Conference Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Reseurch, pp. 5689-5698. PMLR, 2018.
Dengyong Zhou and Bernhard Schölkopf. A regularization framework for learning from graph data. In Workshop Statistical Relational Learning (ICML), 2004.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propa- gation. In Technical Report CMU-CALD-002-107, Carnegie Mellon University, 2002.
Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings of the Twentieth International Conference on In- ternational Conference on Machine Learning, ICML'03, pp. 912-919. AAAI Press, 2003. ISBN 1577351894.
Marinka Zitnik, Monica Agrawal, and Jure Leskovee. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13)i457-i466, 2018.
A APPENDIX
A.1 CLOSED-FORM SOLUTION FOR HARMONIC INTERPOLATION
Given the Dirichlet energy f(x, G) f Ax, we want to solve for missing features X. argminx, leading to the optimality condition Vx.! 0. From Eq. 1 we find Vx. = 0 to be the solution of AuxX; + AuuX, = 0. The unique solution to this system of linear equations is x,, -A A..x.. We show this solution always exists by proving A is non non-singular (Propo- sition 1). The proof of this result follows from the following Lemma.
Lemma 1. Take any undirected and connected graph with adjacency matrix A E {0,1]"xx, and normalised Adjacency = 1/2 AD 112 with D being the degree matrix of A. Let A.n be the bottom right submatrix of À where 1 S b < n. Then pl p(A,w) < 1 where p(.) denotes spectral radius.
12

---

Under review as a conference paper at ICLR 2022
Proof. Define
Oi
Ouk
Aup up =
O
Aun
to be the matrix equal to Agu in the lower right b x b sub-matrix and padded with zero entries elsewhere. Clearly Aup I A elementwise and Aup * A. Furthermore, Aup + A represents an adjacency matrix of some strongly connected graph and therefore irreducible (Berman Plem- mons, 1994, Theorem 2.2.7). These observations allow us deduce that p(Aup) < p(A) (Berman & Plemmons, 1994, Corollary 2.1.5). Note that p(Aup) = p(Aau) as Aup and Aua share the same non-zero eigenvalues. Furthermore, p(A) S as we can write = I A and A is known to have eigenvalues in the range [0, 2] (Chung, 1997). Combining these inequalities gives the result p(A u(Aup) < p(A) 1
Proposition 1 (The sub-L -ablaapl matrix of a undirected connected graph is invertible), Take any undirected, connected graph with adjacency matrix A E {0, 1)=x,, and its Laplacian A I D D-1/2 A//2AD-1 with D being the degree matrix of A. Then, for any principle sub sub-matrix L,, Rbbb of the Laplacian, where <ubc < n, Lu is invertible.
Proof. To prove A.n is non-singular it is enough to show 0 is not an eigenvalue. Note that A un I Aux so O is not an eigenvalue if and only if A... does not have an eigenvalue equal to 1, which follows from Lemma
A.2 FLOSED-FORM. SOLUTION FOR THE EULER SCHEME
Proposition Take any undirected and connected graph with adjacency matrix A E {0, 1 and normalised Adjacency À AD 1/22, with being the degree matrix of A. Let Raxd X E Ruxd be a feature matrix and define the following recursive relation
(())
I
Oce A
x (1-1))
Auk
Then this recursion converges and the steady state is given to be
X A
lim
(
A
X
Ksk
Proof. The recursive relation can be written in the following form
(
(k-1) 1)
x (k-1) (k-1)) Amx (1-11)
Oku
X M)
Auk
Aua
x
1)
The first rows remain the same so we can write x(A) x convergence of the last rows
x(1-1) X and consider just
X 1k-1)=
A ()-
We can look at the stationary behaviour by unrolling this recursion and taking the limit to find stationary state
lim
x (n) lim
( (0) +
Σ (1-1) AutXa.
uu
Using Lemma we find 1om A A following limit
x
O and the geometric series converges giving us the
lim x(1)) [I, Ann)
A -A A
13

---

Under review as a conference paper at ICLR 2022
Dataset
Nodes
Edges
Features
Classes
Cora
2,485
5,069
1,433
CiteSeer
2,120
3,679
3,703
PubMed
19,717
44,324
500
Photo
7,487
119,043
745
Computers
13,381
245,778
767
10
OGBN-Arxiv
169,343
1,166,243
128
OGBN- Products
2,449.029
123,718,280
100
47
Table Dataset statisties.
CheSeer
Publiee
636
636
640
A10
Photo
Computen
OGBN-Ami
Bat
Cal Fiox Masing
Figure Test accuracy for varying rate of missing features on six common node-classificatin benchmarks. For methods that require a downstream GNNs, a 2-layer GraphSAGE (Hamilton et al., 2017) is used. On OGBN-Arxiv, GCNMF goes out-of-memory and is not reported.
14

---

Under review as a conference paper at ICLR 2022
A.3 BASELINES' IMPLEMENTATION AND TUNING
Label Propagation We use the label propagation implementation provided in Pytorch- Geometric (Fey & Lenssen, 2019). Since the method is quite sensitive the value of the hyperparameter, we perform a gridsearch separately on each dataset over the following values: (0.1,0.2,0.3 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.99].
MGCNN We re-implement MGCNN (Monti et al., 2017) in Pytorch by taking inspiration from the authors' public TensorFlow code 6, For simplicity, we use the version of the model with only graph convolutional layers and without an LSTM. For the matrix completion training process, split the observed features into 50% input data, 40% training targets and 10% validation data. Once the MGCNN model is trained, we feed it the matrix with all the observed features to predict the whole feature matrix. This reconstructed features matrix is then used as input for a downstream GNN (as for the feature-imputatioo baselines).
A.4 DISCUSSION OVER BASELINES' PERFORMANCE
Neighborhood Averaging As for some intuition to why Neighborhood Averaging works so well, let's assume to have a single feature channel for simplicity. The average of neighbors' features is a good estimator of the true feature of a given node when the feature is observed for enough neighbors (and is homophilous over the graph). However, as the rate of missing features increases, the feature may be present for only few neighbors (or none at all), causing the estimator to have much higher variance (and therefore less likely to be correct). On the other hand, Feature Propagation allows information to travel longer distances in the graph by repeatedly multiplying by the diffusion matrix. This means that even we do not observe the feature for any of a node's neighbors, we still estimate it from nodes further away in the graph. This be observed empirically: the gap between Neighborhood Averaging and Feature Propagation becomes increasingly significant for higher rates of missing features.
Zero vs Random We thank the Reviewer for bringing up this important point, and we will stress the revised version of our paper. Our intuition that models such as GCN and GraphSage, where node embeddings are computed as (weighted) average of neighbors embeddings, the effect of the Zero baseline is simply to reduce the norm the average embeddings of all nodes (since all nodes have the same expected proportion of neighbors with missing features). On the other hand, the Random baseline corrupts this weighted average. More generally, while for a GNN model could be relatively easy to learn to ignore features set to zero, and only focus known (non-zero) features, would be basically impossible for the model to do the same when setting the missing features random value.
However, we find Random to perform better than Zero when all features are missing. This is in line with findings in the literature (Sato al., 2021; Abboud et al., 2021), where Random features have been shown to work well in conjunction with GNNs as they act as signatures for the nodes, On the other hand, if all nodes have all zero vectors, it becomes basically impossible to distinguish them. After applying a GNN, all nodes will still have very similar embeddings and the task performance will be close to random guess.
hhan:://gtthhh.cm//mmmnngggg
15


Reviews:
[{"review_id": "OZD1uCkYuph", "reviewer": "Reviewer_U1iE", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe paper is well written, and easy to follow. The problem the authors address is interesting, and the solution provided is simple, yet elegant. The experimental results are thorough, both in terms of comparing performance and speed of the method. \n\nWeaknesses:\n\nIt's not completely clear how the proposed method extends to vector valued features. Is the process repeated independently for each feature? or is there some \"interdependencies\" between feature dimensions that can be made use of? How does that affect the computational complexity? ", "summary_of_the_paper": "The authors consider the case of training GNNs with missing features. The proposed framework consists of a diffusion based step prior to training the GNN. A discretization of the approach leads to what they term \"feature propagation\", a scalable method to impute features on the graph. The assumption is that the energy function that determines how related the features are to each other can be learnt from the data. The authors consider the gradient flow and it's solution to minimize the dirichlet energy, which is far more scalable than computing the closed form solution. Experiments on multiple datasets show that the proposed method outperforms several baselines. ", "summary_of_the_review": "\nInitial assessment : accept\n\nThe paper is well written, and easy to follow. The problem the authors address is interesting, and the solution provided is simple, yet elegant. The experimental results are thorough, both in terms of comparing performance and speed of the method. Missing value imputation is a problem that is often ill-addressed when it comes to ML research. In this paper, the authors specifically look at imputation in the context of training GNNs, and use the graph to perform the imputation. \n\nI feel the authors need to address the difference between the proposed method and label propagation a bit more. They claim it's different because of labels being discrete and the diffusion operator being different, but I'm not clear why that's a deal breaker. Won't the algorithm be the same but with a new operator? \n\nAnother point to address is the extension to vector valued features. They claim the extension is straightforward, but a note to this effect will be nice. \n\nother comments:\nP1 last paragraph : I’m not sure if being unaware to the task is a bad thing necessarily.  isn't it better to do imputation in a task agnostic fashion?\n\nFig 3: Please make the text larger. The figures are hard to read. \n\nFig 3: Also any intuition why Random is so much worse than Zero in all these datasets?\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NV-5ihUvpLK", "reviewer": "Reviewer_AjnH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper addresses a very interesting problem that is relevant to real-world applications; dealing with missing node features for graph neural networks (GNNs). The approach is based on minimising Dirichlet energy, which is a emthod previously used for graph regularisation and has relations with graph Laplcians, so is well suited to working with data on graph topology. The author(s) derive an efficient iterative algorithm which makes the approach scalable to large graphs which makes it more practical for real-world applications. Many public datasets were used for benchmarking that show very promising results.\n\nIn the experiments, it's surprising how well the nearest-neigbour averaging worked. In the comparison method's own papers SAT paper has a 'NeighAggre' baseline that seems to do something similar but gets worse scores than their method and GCNMF compares with kNN with k=5, and this also performs worse than their method. Do you have some insights into why neighbourhood averaging performs so well?\n\nThis method is a pre-processing step, not integrated into the GNN, as such many other methods for estimating the missing values could be used. One justification of this choice of approach is that is acts as a low-pass filter, and the GNN mainly learns from the lower frequency components.  This work is very close to matrix completion with graph side information.In this domain there are other methods that are highly scalable and are able to accurately estimate missing values when large amounts of the data (>99%) are missing [1, 2, 4]. Furthermore, one method uses a similar optimisation approach of iterative dense-sparse matrix mulitplication [1]. Worth note is that an extension to [1] will also remove edges in the graph that do not have high-homophily that could improve results for low-himopholy results. Also [3] is a kernel method for matrix completion that allows for a choice of covariance functions, including a diffusion kernel that is therefore similar to this approach. I think it is worth at mentioning this in comparison to this approach and even adding emprical evaluation against these methods, especially [1].\n\nOther small comments:\n\nYou report using V100 GPUs (16 or 32Gb?), how much memory did GCNMF take before ran out of memory.\n\nIt wasn't crystal clear how the approach works for vector node attributes, do you simply repeat the algorithm for each dimension separately?\n\n\"Proposition 1: inverse of Laplacian depends on a connected graph, as eigen values are 0 if graph has clusters.\" How true is this assumption in real graphs, and what can be done in the case where a graph is not connected?\n\nHow do you know 40 iterations is enough, is there a easy guide to this and what happens if you keep running the algorithm, will it eventually make all missing featues almost the same if run for a large number of iterations?\n\n\"For a fair comparison, we use the same standard hyperparameters for all methods across all experiments.\" Does this mean that the downstream 2-layer GCN model has the same hyperparameters? \n\nEdits:\n    A_u should be A_uu ?\n    \n    Zhu and Ghahramani reference is incomplete\n\n    donwstream task -> downstream task\n\n\n1. Rao, Nikhil, et al. \"Collaborative Filtering with Graph Information: Consistency and Scalable Methods.\" NIPS. Vol. 2. No. 4. 2015.\n\n2. Strahl, Jonathan, et al. \"Scalable probabilistic matrix factorization with graph-based priors.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.\n\n3. Zhou, Tinghui, et al. \"Kernelized probabilistic matrix factorization: Exploiting graphs and side information.\" Proceedings of the 2012 SIAM international Conference on Data mining. Society for Industrial and Applied Mathematics, 2012.\n\n4. Monti, Federico, Michael M. Bronstein, and Xavier Bresson. \"Geometric matrix completion with recurrent multi-graph neural networks.\" arXiv preprint arXiv:1704.06803 (2017).\n\n", "summary_of_the_paper": "A graph neural network (GNN) pre-processing step for completing missing node features is presented: feature propagation (FP). The method is based on minimisation of Dirichlet energy. A more efficient iterative update aproach is derived avoiding matrix inversion (cubic operation) to a series of sparse-to-dense matrix multiplications. The method acts similar to a low-pass filter for missing features, which complements the GNN learning algorithm. Relevant work is covered and similarities and differences mentioned in many cases. Experiments on seven publicly available datasets show that the method is effective and performs especially well when a large proportion of the feature values are missing (above 90%). A run-time analysis of wall-clock performance compares their method to two state-of-the-art methods for handling missing node features in GNNs and their method is 3 x faster in these comparison. A weakness of their method, FP, is analysed; FP assumes the graphs are homophlic, that nearby nodes have similar node features but if this is not the case then the method does not perform well. This is some interesting future work. ", "summary_of_the_review": "As this is a preprocessing step that essentially is similar to matrix completion with graph side information, then I believe that comparison with this literature is missing. Otherwise this is a very good paper. The approach they have for the problem, which could be seen as matrix completion with graph side information, is I believe novel in that domain, as well as in this framework for graph neural networks. Therefore, comparison with this domain is important here, as other methods in this domain could also be well justified as pre-processing steps. One such method that both scalable (using similar final equation, but dervied from a different approach, conjugate gradients), must be compared both in the paper and experiments in my opinion. Otherwise, it feels like the work is trying to avoid comparison with similar methods by claiming this work is related to GNN, while really it feels like this is a matrix completion with graph side information method, that is then used for GNNs.\n\nAfter feedback:\n\nI still feel that the motivation for using this particular method of estimating the missing values is not clearly better than other approaches. Also, the link to GNN seems weak as essentially this is a method for completing missing data and with this seems better suited to the domain for estimating missing values, where a stronger comparison with other missing values estimating methods can be compared - for example in comparison to recommender system approaches like collaborative filtering with graph side information. The link to GNN could be a small subsection in that style of paper. I don't see why running GNN is such a large part of this work when it's a stand alone preprocessing step. Therefore I've lowered my score from 6 to 5. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "EDgc12yzNZm", "reviewer": "Reviewer_JE1t", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The strengths:\n\n1. The paper is clearly written and easy to follow\n2. The performance on missing 99% of the features is impressive\n3. The speed improvement is promising\n\nThe weaknesses:\n\n1. FP is not a new idea/algorithm, it is essentially same as label propagation (LP) by Zhu et al. [1]. Although the authors argued that \"Differently from our setting of diffusion of continuous node features, they deal with discrete label classes directly, resulting in a different diffusion operator.\", from my understanding, there is not substantial difference. LP also propagate the label probability, which is continuous. The derivation, the update formula of FP are the same as LP, the only difference is to substitute the weight matrix in LP with Laplacian matrix. Interpreting label propagation via Dirchlet energy is also proposed in [2], where instead of using $x_i$, $x_j$, Solomon et al. were using $f_i$, $f_j$, which are label function of node $i$ and $j$. Consider $x_i$'s as the soft label with label function $f_i$, then they are essentially the same thing.\n2. The experiment part shows that simple averaging of the neighbors gives good result when the missing portion is $\\leq$ 50%. In that case, I think it is also important to show experimental results of algorithms that do not use node features, to see if there is really a gap on the performance. (Note that under strong assumption of homophily, it is not surprising that simple averaging of neighbors works well. FP or LP takes account the topology of the graph and changes simple averaging of neighbors to weighted average of the whole network. The global information of the graph is the key to a better performance in this case, and I doubt other algorithms using the global information can also get similar good performance.) For example, one can use simple label propagation on the node classes, or using LINE, \nDeepWalk or node2vec to get a embedding of each node and then classifying with the embeddings. If the performance is similar as what FP gives when there are 99% features missing, I would argue that in that case we can simply go with classical algorithms using only the network topology. We will only use GNN when we have enough features available, while in which case it seems simple averaging of neighbors is good enough. The paper is not so convincing at the current stage.\n\n[1] Xiaojin, Zhu, and Ghahramani Zoubin. \"Learning from labeled and unlabeled data with label propagation.\" Tech. Rep., Technical Report CMU-CALD-02–107, Carnegie Mellon University (2002).\n\n[2] Solomon, Justin, Raif Rustamov, Leonidas Guibas, and Adrian Butscher. \"Wasserstein propagation for semi-supervised learning.\" In International Conference on Machine Learning, pp. 306-314. PMLR, 2014.", "summary_of_the_paper": "The paper address the problem of  missing node features in graph by conducting feature propagation (FP). An iterative updated algorithm is presented. FP is a preprocessing step and can be used in multiple downstream tasks. Experiments on node classification shows the effectiveness of FP. The authors also provided comparison on running time and showed how homophily affects the performance of FP.", "summary_of_the_review": "In general I like the idea of using FP as a preprocessing step. However, I am not convinced that the idea is novel enough to be accepted in ICLR, details are referred to my main review.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7UFDDknA1-F", "reviewer": "Reviewer_bVRh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Through numerical experiments the authors illustrate the benefit of this simple approach. Nonetheless, my main concern has to do with the novelty of this. Using the quadratic form of the graph Laplacian (Dirichlet energy) for label propagation or graph signal interpolation has been used several times over the last decade (as referenced in this paper). Moreover, using a gradient descent approach instead of inverting the Laplacian has also been used quite often. E.g., see the tutorial \"Signal processing on higher-order networks: Livin’on the edge... and beyond\" where in Section 2.4.2 the authors review some typical formulations of signals on graphs before going into higher-order networks. Notice that Equation (4) contains (I-L)^k, which corresponds to several applications of the (normalized) adjacency matrix. In fact, it is mentioned that \"This may be interpreted in terms of k gradient descent steps of the cost function (Dirichlet energy)\".\n\nFrom the perspective of graph signal processing, the true solution with the inverse of the Laplacian can be seen as an IIR filter and this is an FIR approximation of the filter. This idea of graph filter design has also been studied quite a bit over the last 7 years.", "summary_of_the_paper": "This paper proposes a fast way to do node feature imputation in graph learning settings. In a nutshell, the idea is to consider the graph topology in the imputation by doing a feature by feature minimization of the Laplacian quadratic form. However, since the exact solution to this requires a matrix inversion, this quantity is minimized by a gradient descent procedure that relies on sparse matrix multiplications.\n", "summary_of_the_review": "Under this perspective, I regard that the novelty in this paper is limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a Feature Propagation (FP) method for dealing with missing features in graph learning tasks. The FP method is based on minimization of the Dirichlet energy and leads to a diffusion-type differential equation on the graph. Empirical results demonstrated the effectiveness. However, after rebuttal major concerns still remain on the novelty and siginificance, in particular, the connection with label propogation should be better elaborated, which is crucial to understand the contributions of this paper. Considering that, I can't recommend accept the current manuscript. The authors are encouraged to further improve for a more solid publication in the future.
Decision: Reject