Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes Dual-Encoding Transformer (DET), which aggregates information from both local neighbors and semantically close neighbors to address the scalability issue of existing Transformer architectures for graphs. Also, the authors design self-supervised semantic neighbor fetching loss, which is jointly optimized with the main task loss.
strength_and_weaknesses: **Strengths**

(1) This paper addresses the limitation of Transformer-based models for graphs, which is one of important topics to generalize Transformer to the graph domain.

(2) The proposed DET shows the best performance on KG completion task.

**Weakness**

(1) I think that the novelty of this paper is limited. 

- The combination of structurally and semantically close neighbors has been already discussed in various works (Geom-GCN [1], Non-local GNNs [2]).
- Also, semantic neighbor fetching loss seems similar to self-supervised loss of SuperGAT [3].

(2) The accuracy of GCN and GraphSAGE on ogbn-arxiv is very low. From the leaderboard of ogbn-arxiv, the accuracy of GCN and GraphSAGE are 71.74 and 71.49, respectively. What makes deteriorating performance?

(3) From Table 7, DET requires more average training time compared to Graphormer on PCQM4M-LSCv1 and ZINC datasets although DET uses less neighborhoods compared to Graphormer.

(4) In Section 5.2, the paper discussed the correlation between semantic encoding and graph homophily. So, it would be better if the paper compare the performance on heterophilic graph datasets with baselines such as H2GCN [4].

---

[1] Pei, Hongbin, et al. "Geom-gcn: Geometric graph convolutional networks." ICLR 2020.

[2] Liu, Meng, Zhengyang Wang, and Shuiwang Ji. "Non-local graph neural networks." TPAMI 2021.

[3] Kim, Dongkwan, and Alice Oh. "How to find your friendly neighborhood: Graph attention design with self-supervision." ICLR 2021.

[4] Zhu, Jiong, et al. "Beyond homophily in graph neural networks: Current limitations and effective designs." NeurIPS 2020.
clarity,_quality,_novelty_and_reproducibility: **************Clarity**************

The paper is clearly written to understand overall method.

**************Quality**************

Some experiments for baselines are not properly conducted. Also, it would be better to conduct more experiments to validate the effectiveness of proposed models.

**********Novelty**********

The proposed method has a limited novelty. 

******************************Reproducibility******************************

The authors share their source code in the supplement. The paper has good reproducibility.
summary_of_the_review: Overall, I am leaning towards rejection. My major concern is the novelty and experimental results. If you address my concerns, I will raise my score.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes DET, a transformer architecture for handling large graphs.

DET relies on two attention mechanisms:
- A structural attention mechanisms, i.e. for a given node, attention applied between a virtual global node and the neighboring nodes only. Moreover, a learnable position encoding is added (including centrality, distance to other neighbors and edge type).
- A semantic attention mechanism, i.e. attention applied to semantic neighbors. More precisely, and for a given node, the other nodes are ranked depending on a learned embedding similarity score which is then used as an attention weight. This score can be learned via a self-supervised objective.
Although computing the similarity score for each node has quadratic complexity in the number of nodes., the ranking step is done every few epochs only, providing an efficient attention mechanism in practice.

The authors then proceed to demonstrate the effectiveness of graph and node level tasks, with strong results for PCQM4M, ZINC, ogbn arxiv and knowledge graph completion. Finally, further studies of DET are provided: an ablation is done to understand the role of structural attention, semantic attention, and the semantic attention loss, a study on the usefulness of semantic encoding w.r.t. graph homophily, and an example of learned relations by the different mechanisms.

strength_and_weaknesses: Strength:
- This work offers a potential solution, DET, to an important problem, scaling transformers to large graphs.
- The method is simple and motivated: a local attention scheme is augmented by an attention scheme that is able to fetch remote useful nodes. An SSL loss allows to learn the score used for ranking and attention weighting. Ranking only every few epochs seems to provide an efficient attention scheme in practice.
- DET demonstrates strong results on various and important benchmark such as PMQC4M and ZINC.
- This work studies in detail the proposed attention scheme and in particular the semantic attention: we see that the nodes fetched by the semantic encoder make sense, and that the semantic encoder is as expected useful when considering low homophily graphs.

Weaknesses:
- One novelty of this work, and what makes it scalable, is applying a custom attention to top ranked nodes, with an updated ranking every few epochs. In light of this, a natural baseline would be to apply linear attention instead of the proposed $f_s$: it would be more convincing to demonstrate the usefulness of $f_s$ compared to linear attention.
- The other novelty is the use of a virtual node for a local attention mechanism. I am not sure to understand the motivation of this mechanism compared to a purely local attention scheme (attention between the node of interest and its neighbors): clarification and/or ablation could be useful to better understand the interest of the proposed scheme.
clarity,_quality,_novelty_and_reproducibility: Clarity:
The paper is generally well-written with a few caveats:
- The motivation for the SSL loss is not clear: why enforcing high similarity between neighboring nodes? At first sight it seems redundant with the structural attention scheme which only applies attention to neighbors.
- If I understand correctly, for a given graph, DET has to sort $n$ times $n$ scores and store $n^2$ scores in memory?

Quality:
- The methods is clearly described, correctly motivated and simple.
- Experimental protocol seems thorough: varied tasks (graph and node level) as well as baselines are used. Moreover, sensible ablations are conducted although one seems to be missing in my opinion (see weakness).

Novelty:
- DET relies on two attention mechanisms: a local one, aimed at reflecting the structure, and a sparse, global one, aimed at gathering semantically similar remote nodes. Both mechanisms seem at least partially novel to me. Encoding the structure by considering substructures such as neighboring nodes has already been proposed [1][2] without involving a virtual node, and could potentially be discussed to better delineate the contribution of this work.

[1] GraphiT: Encoding Graph Structure in Transformers (Mialon et al. (2021))

[2] Structure-Aware Transformer for Graph Representation Learning (Chen et al. (2022))

Reproducibility: the code is provided along with experimental details in the appendix.

summary_of_the_review: This work offers a sensible solution to an important problem, with strong results. Although some elements could be clarified in the writing (novelty, more motivation for the virtual node in local attention and the SSL loss) and some ablation may be in my opinion missing, the pros outweight the cons and I tend to recommend acceptance.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new Graph Transformer architecture, named dual-encoding Transformer (DET), which has a structural encoder to aggregate information from near neighbors and a semantic encoder to focus on useful semantically close neighbors. The empirical results demonstrate that the proposed DET achieves superior performance compared to the respective state-of-the-art attention-based methods.
strength_and_weaknesses: strength:
- The idea of disentangle and combine structural neighbors and semantic neighbors looks interesting to me.
- The authors conducted thorough experiments on various datasets.

weaknesses:
- Some writing is a bit confusing. How to understand and interpret Figure 2? How do the authors define the semantic set $\mathcal{N}^{\text{se}}$? "In our implementation, it is sampled from the top candidate" what are the pool to select top candidates then? Is it all the other nodes?
- What's the runtime analysis of the proposed method? How to understand Table 7? Why sometimes there's a nontrivial overhead and sometimes not?
- The empirical performance of the proposed method is no longer the state-of-the-art performance. Please check [1]'s results on ZINC, for example. The authors should include and compare with this paper.

[1] Dwivedi, Vijay Prakash, et al. "Graph Neural Networks with Learnable Structural and Positional Representations." International Conference on Learning Representations. 2022.
clarity,_quality,_novelty_and_reproducibility: The clarity of the paper is not satisfactory, certain modules are not very clear to me.
The authors provide source code that looks well documented so I guess there's no concern on reproducibility.
I feel there's quite limited novelty in the proposed approach. The dual module idea is similar to model ensemble.
summary_of_the_review: The submission has thorough empirical results, but the empirical results do not look very competitive and the proposed method has only limited novelty
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel graph transformer architecture that jointly aggregates structural neighbors and semantically related neighbors to encode each node. The proposed method is evaluated on various levels of graph learning tasks and confirmed to be effective.
strength_and_weaknesses: strengths:
1. This paper studies a critical problem, that is to say, how to preserve the advantage of transformer to enjoy a large receptive field and, at the same time, efficiently aggregate discriminative information. In this regard, the contribution is likely to make a significant impact to the community.
2. The proposed neural architecture is novel to me, which, instead of considering sparsity trick or hierarchical structure, directly defines neighborhood in the latent semantic space.
3. The experiments are solid in terms of their comprehensiveness. Besides, the ablation studies confirm the effectiveness of introduced components. The case study of semantic neighbors also implies that the semantic encoder works with meaningful neighbors.

weaknesses:
1. It seems that there is a lack of theoretical analysis about the proposed architecture. I am really curious about what semantic similarities would be learned eventually. Meanwhile, what is the negative distribution should be adopted deserves a more detailed discussion, especially considering the number of examples increases along with the number of hops exponentially.
clarity,_quality,_novelty_and_reproducibility: Clarity: Generally, this paper is well-written. One suggestion is to notate the structural and semantic embeddings (i.e., $h$) with layer index (e.g., by superscript) and explain how the transformer layers are stacked.

Quality: The proposed novel architecture is motivated in a natural way. The design of the semantic component sounds good from a technical perspective, but a related theoretical analysis would be more in a demand. The proposed architecture is evaluated on various levels of tasks, and its advantages over SOTA methods seem to be consistent. It would be better to provide standard deviations and a statement of whether the advantage is statistically significant.

Novelty: The proposed neural architecture is novel to me, although it is somewhat straightforward.

Reproducibility: All the adopted datasets, considered baselines, and the implementations are publicly available.
summary_of_the_review: I think the proposed transformer architecture is somewhat novel to me. It is empirically evaluated in an extensive way, showing its effectiveness. Currently, I can only evaluate the behavior of semantic component based on the case shown in experiment, where the semantic neighbors seem to be truly semantically relevant. I don't have confidence to suggest an acceptance now, and more theoretical analysis would resolve my concerns.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a modified Transformer architecture for graphs that leverages neighbors close in graph space and in representation space. While reviewers are in agreement that this is an important direction, the general view is that the novelty relative to other related works in this direction is not particularly high, so there is more of a burden on the experimental results, and there remain a number of concerns, including additional comparisons to baselines and anomalies in the reported results.
justification_for_why_not_higher_score: Would like to see most reviewer concerns around experiments resolved.
Decision: Reject