Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
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.

In 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?

This 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].

Other small comments:

You report using V100 GPUs (16 or 32Gb?), how much memory did GCNMF take before ran out of memory.

It wasn't crystal clear how the approach works for vector node attributes, do you simply repeat the algorithm for each dimension separately?

"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?

How 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?

"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? 

Edits:
    A_u should be A_uu ?
    
    Zhu and Ghahramani reference is incomplete

    donwstream task -> downstream task


1. Rao, Nikhil, et al. "Collaborative Filtering with Graph Information: Consistency and Scalable Methods." NIPS. Vol. 2. No. 4. 2015.

2. 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.

3. 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.

4. Monti, Federico, Michael M. Bronstein, and Xavier Bresson. "Geometric matrix completion with recurrent multi-graph neural networks." arXiv preprint arXiv:1704.06803 (2017).


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.

After feedback:

I 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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
main_review: The strengths:

1. The paper is clearly written and easy to follow
2. The performance on missing 99% of the features is impressive
3. The speed improvement is promising

The weaknesses:

1. 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.
2. 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, 
DeepWalk 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.

[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).

[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_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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.

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)".

From 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_review: Under this perspective, I regard that the novelty in this paper is limited.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
main_review: Strengths:

The 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. 

Weaknesses:

It'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_review: 
Initial assessment : accept

The 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. 

I 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? 

Another 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. 

other comments:
P1 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?

Fig 3: Please make the text larger. The figures are hard to read. 

Fig 3: Also any intuition why Random is so much worse than Zero in all these datasets?
review_title: null

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