Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper introduces an all-pair message passing scheme based on a kernelized Gumbel-Softmax operator to reduce the complexity of message passing from quadratic (in number of nodes N) to linear time at the cost of some approximation error. The authors provide an analysis of the incurred error and present empirical comparisons with state-of-the-art methods.
strengths_and_weaknesses: ## Strengths
* The paper is very well-written and organized
* The problem of efficient graph learning is highly relevant to the ML community 
* Sound theoretical results are provided that bound the approximation error of the proposed scheme (Sec. 3.2)
* The presented method combines existing techniques (random features, reparameterization trick, Gumbel distribution sampling) in a novel way
* Empirical results and comparisons (Sec. 4) on common graph datasets support the improved effectiveness of the proposed approach
* Visualizations and sensitivity analysis of relevant variables (\tau) are provided in the appendix

## Weaknesses
* The method requires a parameter \tau to be tuned in advance. Is there any way to learn or automatically set \tau based on the theoretical analysis (e.g., mathematically balance the tradeoff mentioned in Line 178) so that ablation studies are not needed on an application specific basis?

questions: Please see Weaknesses section above.


### Post Rebuttal
Thank you for your response. This addresses my concern and my decision remains the same (Accept).
limitations: Yes (in the Appendix)
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors proposed a GNN framework named ALIGNS that can simultaneously learn the latent topology and missing labels of nodes. They came up with a two steps approximation to first kernelize the softmax function used in latent node structures, then a continues relaxation of the categorical distribution over all pairs of edges to enable end-to-end back propagation. In the experimentation section they tested on various datasets with up to 2M nodes, in both transductive and inductive setting, given clean, noisy, and even no graph information. Results show not only ALIGNS has a performance gain against SOTA models, but also it scales with increasing number of nodes. 
strengths_and_weaknesses: Pros: 
- The paper is well-written and easy to read. 
- Method has potential for used in much wider range without constraining on graph-structured input. 
- Scalability of model is very impressive. The kernelization and continues relaxation seems to hold up pretty well in real world task. 
- Performance in transductive setting with standard benchmarks in homophily and heterophily graphs are on par or outperform SOTA. 
- In inductive setting even after adding noise to edges, the model still performs very stable. 

Cons: 
- Typo in line 331, ELBO, not EBLO.
- Eq (8) is not the same as in Algorithm 1. Shouldn't it be \z_u^{(l)} on the right side?  
- I don't get why all datasets have a fix \tau = 0.25. Shouldn't it based on the feature size/graph structures? 
- From my personal perspective, I would like to see the learned latent structure in main text, and have a comparison to the original graphs. 
questions: - I feel like the same approximation can be applied to GAT or other attention based methods. What is the benefits on doing it for all pair-wise then using existing structures? Are we missing out on informations we already have in this case?
- Why is k-NN still needed in Graph-enhanced applications? Is observed adjacency strictly needed or we can use the current layer's latent structure as adjacency? 
- Again in Eq(8) on the right side, is \z and \v of the same dimension? Is there no dimension changes during feature transformation? 
limitations: I didn't see a negative societal impact of this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper considers to overcome the deficiencies of over-squashing, heterophily, long-range dependencies, edge incompleteness etc. by proposing a new structure to learn the topology of the input graphs. Specifically, it proposes to incorporate the learned topology into the attention matrix through the Softmax Gumbel operator. To reduce the runtime complexity, a kernelized version of attention computation is developed using random feature decomposition. Also, convergence properties of the approximation are derived. Extensive experiments are conducted on different types of node classification tasks.
strengths_and_weaknesses: Strengths:

1. Theoretical analysis is comprehensive. Convergence results are developed to study the quality of the fast computation of the Softmax Gumbel operator. 
2. The variational perspective of the proposed method is motivating. 
3. Numerical experiments are comprehensive as well, which includes testing on small graphs, large graphs, transductive and inductive task, and graph-enhanced applications etc. 

Weaknesses:

1. The paper mentions that the new method is proposed to tackle problems like over-squashing, heterophily, long-range dependencies etc. However, in the main body of the paper, it is hard to realize how the development of the new structure helps to resolve these issues accordingly. It would be great if the authors could point this out more clearly.
2. Since the method is proposed for scalable GNN, the authors are encouraged to review and discuss more about SOTA scalable GNNs and compare with the proposed model in the related works section, such as subgraph-wise sampling: GraphSAINT [1]; Kernelized masked attention: GKAT [2]; Linearized GNN: [3][4] etc. Also, those models could be reasonable baselines in the Section 4.2, Experiments on Larger Graph Datasets, where currently only MLP and GCN are compared.

[1] Zeng, Hanqing, et al. "Graphsaint: Graph sampling based inductive learning method." arXiv preprint arXiv:1907.04931 (2019).

[2] Choromanski, Krzysztof, et al. "Graph kernel attention transformers." arXiv preprint arXiv:2107.07999 (2021).

[3] Wu, Felix, et al. "Simplifying graph convolutional networks." International conference on machine learning. PMLR, 2019.

[4] Bojchevski, Aleksandar, et al. "Scaling graph neural networks with approximate pagerank." Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020.

questions: 1. In Section 3.4, there is a comment stating that Eqn. (12) can be computed in $\mathcal{O}(1)$ because the summation term is computed in Eqn. (7). However, it seems that the summation terms are 
\begin{equation}
\sum_{v=1}^{N} e^{g_v / \tau} \phi( \mathbf{k}_v / \sqrt{\tau})  \cdot  \mathbf{v}_v, \text{and} 
\end{equation}

\begin{equation}
\sum_{w=1}^{N} e^{g_w / \tau} \phi( \mathbf{k}_w / \sqrt{\tau})
\end{equation}

instead of  $\sum_{w = 1}^{N} \phi(\mathbf{k}_w)$ . Could the authors elaborate more about this?


2. According to the error bound for Softmax Gumbel RF decomposition in theorem 1, the bound grows exponentially in terms of the length of embedded vector $q_u$ and $k_v$, but shrinks polynomially in terms of the number of random features. Have the authors measured the gap between the approximation and the truth value when working on the experiments? As the norm grows, is a large number of random features required?

limitations: The limitations and negative social impacts are not addressed in the paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work performs message passing over any pairs of nodes in the graph, while avoiding the N^2 time complexity by using kernelized operator. The key technique is to use random feature to estimate the kernel function. The authors conduct experiments on various node-level tasks to evaluate the method.
strengths_and_weaknesses: #### Pros ####
(1) Using random feature technique to approximate the kernel function is impressive and reduces the complexity significantly.

(2) The presentation flow of this paper is clear and easy to follow.

#### Cons ####
(1) More convincing benchmark comparison should be considered. Actually, I was surprised by the effectiveness of the random feature approximation. I think more rigorous benchmark comparison should be used to evaluate the empirical performance. In the current experiments, except ogb-proteins, other experiments are mainly using the setting defined by this paper, which might be less convincing to me. For example, for the citation networks, we have well-established benchmark setup in the community. The setup used in this paper is different, and the results of the baselines are not consistent with prior works. For example, on Citeseer, the accuracy of JKNet (~72) is much lower than GCN (~76), which indicates that the reproduced results of baselines might not be convincing.




+++++++++ Post-rebuttal +++++++++

After reading the response from authors, my original concerns are addressed. 
questions: (1) For the edge loss (Eq. (10)), can we consider both observed edges and non-observed relationships. If we only consider existing edges, the loss could lead to all \pi_{uv} to be large.
limitations: Not applicable.
review_title: null

Meta-review: metareview: The paper presents an approximate way to perform all-pair message passing within the context of GNNs. The paper's main contribution is a series of extensive empirical results and at the same time theoretical justification for the approach. All the reviewers liked the paper and noted the impressive scalability of the approach. Some technical questions/concerns were also addressed post rebuttal. This paper is recommended for acceptance.
confidence: Certain
Decision: Accept