GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph
Authors: Junhan Yang
Zheng Liu
Shitao Xiao
Chaozhuo Li
Defu Lian
Sanjay Agrawal
Amit S
Guangzhong Sun
Xing Xie
Venue: NeurIPS 2021 Poster (2021)
Keywords: representation learning on textual graph
text mining
graph mining
relevance modeling

Abstract: The representation learning on textual graph is to generate low-dimensional embeddings for the nodes based on the individual textual features and the neighbourhood information. Recent breakthroughs on pretrained language models and graph neural networks push forward the development of corresponding techniques. The existing works mainly rely on the cascaded model architecture: the textual features of nodes are independently encoded by language models at first; the textual embeddings are aggregated by graph neural networks afterwards. However, the above architecture is limited due to the independent modeling of textual features. In this work, we propose GraphFormers, where layerwise GNN components are nested alongside the transformer blocks of language models. With the proposed architecture, the text encoding and the graph aggregation are fused into an iterative workflow, making each node's semantic accurately comprehended from the global perspective. In addition, a progressive learning strategy is introduced, where the model is successively trained on manipulated data and original data to reinforce its capability of integrating information on graph. Extensive evaluations are conducted on three large-scale benchmark datasets, where GraphFormers outperform the SOTA baselines with comparable running efficiency. The source code is released at https://github.com/microsoft/GraphFormers .

GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph
Junhan Yang"; Zheng Liu", Shitao Xiao", Chaozhuo Li*, Defu Lian',
Sanjay Agrawal", Amit Singh", Guangzhong Sun', Xing Xie
University of Science and Technology China, Hefei, China
Microsoft Research Asia, Beijing, China
Beijing University of Posts and Telecommunications Beijing, China Microsoft India Development Center, Bengaluru, India
yangjun220mail.usta ustc edu, cn,
(chengliu,cli,siiee siwiiiiiittttiinnniiiiiiooe crosoft. com,
stxiao@bupt.edu cn,
(liandefu [1iandefu.gzsun]ee gus.uuu.ggguunuuutt.....d en,
sanjayitt00gmaill.cm
Abstract
The representation learning on textual graph to generate low-dimensional embed- dings for the nodes based the individual textual features and the neighbourhood information. Recent breakthroughs on pretrained language models and graph neu- ral networks push forward the development of corresponding techniques. The existing works mainly rely on the cascaded model architecture: the textual fea- tures of nodes are independently encoded by language models first; the textual embeddings are aggregated by graph neural networks afterwards. However, the above architecture limited due the independent modeling of textual features. In this work, we propose GraphFormers, where layerwise GNN components are nested alongside the transformer blocks language models. With the proposed architecture, the text encoding and the graph aggregation are fused into an iterative workflow, making each node's 's semantic accurately comprehended from the global perspective. In addition, progressive learning strategy is introduced, where the model is successively trained on manipulated data and original data to reinforce its capability of integrating information on graph. Extensive evaluations are conducted on three large-scale benchmark datasets, where GraphFormers outperform the SOTA basclines with comparable running efficiency. The source code is released at httlappp://ggtttab.o./omreereree
Introduction
The textual graph is widely existed data format, where each node is annotated with its textual feature. The representation learning on textual graph is to generate low-dimensional node embeddings based on the individual textual features and the information from the neighbourhood. In recent years, the breakthroughs in pretrained language models and graph neural networks contribute to the development of corresponding techniques. Particularly, with pretrained language models, such BERT (Devlin et al.] 2018) and RoBERTa (Liu et al. 2019a), the underlying semantics of texts can be captured more precisely; at the same time, with graph neural networks, like GraphSage (Hamilton al. 2017a) and GAT (Veličković et al., 2018). neighbours can effectively aggregated for more informative node embeddings. It necessary combine both techniques for better textual graph representation. As
WWrk was done by 2021.01 during Junhan Yang and Shitao Xiao's intersship in MSRA
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

GNN
ONI
N1
N2
N1
N2
GNN
TRM
TRM
TRM
TRM
TRM
TRM
COC
ONZ
GNN
TRM
TRM
TRM
TRM
TRM
TRM
ONNI ON2
TRM
TRM
TRM
TRM
TRM
(A) Cascaded Transformers-GNN
GNN-nested Transformers
Figure I: Model architecture comparison (a center node C is connected with two neighbours NI, N2). (A) Cascaded Transformers-Gr GNN:: text embeddings independently generated by language models and aggregated by rear- mounted GNNs. (B) GNN-nested Transformers: the text encoding and graph aggregation are iteratively performed with the layerwise GNNs and Transformers (TRM).
suggested by GraphSage (Hamilton et al. 2017a) and PinSage (Ying et al. 2018), the textual feature
can be independently modeled by text encoders and further aggregated by rear- year-mounted GNNs for the final node embeddings. Such a representation paradigm has been widely adopted by subsequent works on various scenarios (Zhu et al. [021]] Li et al.) [021]] Hu et al.) 2020 Liu et al., 2019b] Zhou al. 2019), where GNNs are combined with powerful PLM- text encoders.
The above way of combination is called the "Cascaded Transformers-Gi the language models (built upon Transformers) are deployed ahead of the GNN component. With the above architecture, the text encoding and the graph aggregation are performed in two consecutive steps, where there is information exchange between the nodes when text embeddings are generated. However, the above workflow is defective considering that the linked nodes are correlated, whose underlying semantics can be mutually enhanced. For example, given a node "notes on transformers" and its neighbour "tutorials on machine translation"; by making reference to the whole context, the machine learning model, rather than an electric device.
architecture (Figure A
"transformers" here can be interpreted
Our Work. We propose "GNN-nested Transformers" (GraphFormers), which are highlighted for the fusion of GNNs and language models (Figure BB) In GraphFormers, the GNN components nested alongside the transformer layers (TRM) of language models, where the text encoding and graph aggregation are fused as iteratively workflow. In each iteration, the linked nodes will exchange information with each other in the layerwise GNN component; thus, each node will be augmented by its neighbourhood information. The transformer component will work the augmented node features, where increasingly informative node representations can be generated for the next iteration. Compared with the cascaded architecture, GraphFormers achieve more sufficient utilization of the cross-node information on graph, which significantly benefit the representation quality. Given that the layerwise GNN components merely involve simple and effective multi- heald attention, GraphFormers preserve comparable running costs as the existing cascaded Transformers-Gie models.
On top of the proposed model architecture, and practicability as follows. Firstly, the training of GraphFormers is likely to be shortcut: in many cases, the center node itself can be "sufficiently informative", where the training tasks can be accomplished without leveraging the neighbourhood information. As such, GraphFormers may end up with insufficiently trained GNNs. Inspired by recent success of curriculum learning (Bengio et al. 2009). we propose to train the model progressively: the first round of training is performed with manipulated data, where the nodes are randomly polluted; thus, it becomes harder to make prediction merely rely on the center nodes, and the model will be forced to leverage the whole input nodes. The second round of training gets back the unpolluted data, where the model will be fit into the targeted distribution. Another concern about GraphFormers is that all the linked nodes are mutually dependent the representation process: once a new node presented, all the neighbours. regardless of whether they have been processed before, need to be encoded from scratch. As a result, great deal of unnecessary computations will be incurred. We introduce unidirectional graph attention to alleviate this problem: only the center node is required to make reference to the neighbours, while the neighbour nodes remain independently encoded. By this means, the existing neighbours' encoding results can be cached and reused, which significantly saves the computation cost.
further improve GraphFormers' representation quality

---

Extensive evaluations are conducted with three million-scale textual graph datasets: DBLP, Wiki and Product, where the representation quality is measured by the link prediction accuracy. According to our experiment results, GraphFormers significantly outperform the SOTA cascaded Transformers- GNN baselines with comparable running efficiency.
Related Work
The textual graph representation is an important research topic in multiple areas, such as natural language processing, information retrieval and graph learning (Yang et al. (2015) Wang et al. 220 a Yasunaga et al. 2017 Wang et al. 2019a Xu et al. 2019). To learn high-quality representation for textual graph, techniques on natural language understanding and graph representation need to be jointly leveraged. In recent years, breakthroughs on pretrained language models (PLM) and graph neural networks (GNN) significantly advance the development of corresponding techniques.
PLM. The PLMs are proposed to learn universal language models with neural networks trained on large-scale corpus. The early works were based on shallow networks, e.g, word embeddings
learned by Skip-Gram (Mikolov et al. (013) and GloVe (Pennington et al. 2014). In recent years. the backbone networks are being quickly scaled up: from EMLo (Peters et al. 20188 8), GPT (Radford et al.) 2018).18).. to BERT (Devlin et al. 2018), XLNet (Yng et al. 2 T5 (Raffel et al. 2019)). GPT-3 (Brown et al. 2020). The large-scale models, which get fully trained with massive data, demonstrate superior performances
general NLP tasks. One of the most critical usages of PLMs is text representation, where the underlying semantics of texts are captured by low-dimensional embeddings. Such embeddings achieve competitive results downstream tasks, like text retrieval and classification (Reimers and Gurevych 2019 Luan et al. 2020 Gao et al. [021] [uu et al.! 2021).
GNN. Graph neural networks are recognized as powerful tools of modeling graph data (Hamilton et al. 2017b; /hhuu et al. 2200). Such methods (e.g., GCN (Kipf and Welling 2016), GAT (Veličković al. 2018). GraphSage (Hamilton al.) 2017a) learn effective message passing mechanisms such that information between the nodes can get aggregated for expressive graph representations.
Graph neural networks may also incorporate node attributes, like texts; and it's quite straightforward to leverage GNNs and PLMs for textual graph representation following the "cascaded architecture" suggested by GraphSage (Hamilton et al.) 2017a): : the node features are independently encoded first; then, the node embeddings are aggregated via GNNs to generate the final representations. Such representation paradigm is widely adopted by subsequent works (Zhu et al., 2021 Li et al., 202T] [uu et al. 2020 Liu et al.) 2019b Zhou et al., 2019). However, the above approaches treat the text encoding and graph aggregation as two consecutive steps, where the node-level features are independently processed. Our work is different from these approaches as the text encoding and graph aggregation are fused as an iterative workflow based on the "GNN-nested Transformers".
3 GraphFormers
In this work, we deal with textual graph data, where each node x is a text. The node x together with its neighbours N₂ are denoted G.. Our model learns the embedding for node based on its textual feature and the information of its neighbourhood Nz. The generated embeddings are expected to capture the relationship between the nodes, i..., to accurately predict whether two nodes 2. and Iyk are connected based on the embedding similarity.
3.1 GNN-nested Transformers
The encoding process of GraphFormers is indicated as follows. The input nodes (the center node and its neighbours) are tokenized into sequences of tokens, with special tokens [CLS] padded in the front, whose states are used for node representation. The input sequences are mapped into the initial embedding sequences g G based on the summation of word embeddings and position embeddings. The embedding sequences encoded by multiple layers of GNN-nested nested Transformers (shown as Figure 2) where the graph aggregation and text encoding are iteratively performed.
Graph Aggregation in GNN. Each node is enhanced by its neighbourhood information based on the layerwise graph aggregation. For each node the 1-th layer, the first token-level embedding (corre- sponding to [CLS]) is taken as the node-level embedding: 2 +- H [O]. The node-level embeddings
3

---

Normh
2/
Forward
Forward
Forward
Attention
Multi-Hlead Attention
2/
Attcation
Afcention
+
21
Figure 2: GNN-nested Transformers (using the 1-th layer for illustration). The graph aggregation is performed in the first place: the node-level embeddings fz are gathered from all the nodes and processed by the GNN component (the leftmost rectangle). The GNN processed node-level embeddings {2] Ja are dispatched to their original nodes, which forms the graph-augmented token- level embeddings. The graph-augmented token-level embeddings are further encoded by Transformer.
are gathered from all the nodes and passed the layerwise GNN for graph aggregation. We leverage Multi-Head Attention (MHA) to encode the node-level embeddings Z ((2)))), similar as GAT (Veličković et al. 2018). For each attention head, the scaled dot- pro-product attention is performed as:
2/c MHH(Z
M Concat(heade 1... head;);
QKT +BVV;
(1)
head softmax
Vd
Q = Z W K = W/W, WK = z/W wy;
In the above equations, W WK and wy are the projection matrices of MHA, corresponding to the j-th attention head. A learnable position bias B is added to the dot-product result; the positions differentiate the relationship between the nodes; i.e., "center-to-center" to x)) "center-to-neighborr (x to N2), and toriabobott--nigbburr (N₂ to N2), respectively.
Each of the embeddings 2 (2), E 2//) is dispatched to its original node and concatenated (0) with the leven-level embeddings, which gives rise the graph-augmented token-level embeddings:
A + Concat (z H
(2)
In this place, the GNN-processed node-level embeddings 2% can be interpreted as "messagers", with which the neighbourhood information can be introduced to each of the nodes.
Text Encoding in Transformer. The graph-augmented token-level embeddings H' are processed by the transformer component (Vaswani et al. 2017). where the following computations are performed:
H = LN(H + MHA RaN (H:));
(3)
H = LN + ML.
In the above equations. MLP is the Multi-Layer Projection unit and LN is the Layer-Norm unit. We use asymmetric Multi-Heal Attention (MHA ), where Q, K, V are computed as:
Q = H W. K W. V Wy
(4)
Therefore, the output sequence Hi+1 will be of the same length as the input sequence 9- The encoding result will be used as the input token-level embeddings for the next layer. The node-level embedding at the last layer z (i.e., (0) will be used as the final node representation.
Workflow. We summarize GraphFormers' encoding workflow Algorithm I The initial token- level embeddings {H) are independently encoded by the first Transformer layer TRM", For T.-layer GraphFormers, the graph aggregation and text encoding are iteratively performed for the subsequent L-1 steps (from to 1). In each step, the node-level embeddings Z are gathered and

---

Algorithm 1: GraphFormers' Workflow
Input:
The input graphs G (consist of the center node and its neighbours). The embedding for the center node h
Output:
begin
2
for each text E G do
L H - TRM (H²): : // Get the initial token-level embeddings
for
1 11=1.-. L.....L----... do
Z - [z]lgGG); // Gather node-level embeddings to GNN
2/g 5 GNN((Z)) // Graph aggregation in GNN
for each text E G do
H - Concat 22y H²); // Get graph-augmented token-level embeddings
H+ t- TRM' (H; ); Text encoding Transformer 9
g
10
Return h + 1 2
processed by the layerwise GNN component. The output node-level embeddings 2/3 are dispatched to their original nodes, which generates the graph-augmented token-level embeddings H The graph- augmented token-level embedding are further processed by the Transformer component. Finally, The node-level embedding (for the center node in the last layer z is taken
representation result.
Encoding Complexity. Given an input of Al nodes, each one has P tokens; the time complexity of each layer's encoding operation is O + M P2): the graph aggregation takes O(M²), because M node-level embeddings are gathered for multi-heat attention; the text encoding takes ( (2), as each of the M node calls for the multi-head attention of P tokens. Compared with Transformers, the GNN's computation cost much smaller, mainly because of two reasons: M < M p2 in general, 2) operations like MLP are not needed in graph aggregation. Therefore, the working efficiency of GraphFormers close to the cascaded Transfornsssmmrrs as the extra computation cost of layerwise graph aggregation is relatively small. Such a property is also empirically verified in our experiment.
3.2 Model Simplification: Unidirectional Graph Aggregation
One concern about GraphFormers is that the input nodes are mutually dependent on each other during encoding process. As a result, to generate the embedding for node, all the related nodes in its neighbourhood need to be encoded from scratch, regardless of whether they have been processed before. Such a property unfavorable in practice as great deal of unnecessary computation cost might be incurred (i.c., node will be repetitively encoded every time it serves neighbour node). We leverage a simple but effective simplification, the unidirectional graph aggregation, to address this problem. Particularly, only the center node is required to make reference to the neighbourhood; while the rest of nodes Ng remain independently encoded all by their own textual features:
TRM = x; TRM (H)). E
H
(5)
Because the encoding of the neighbour nodes independent of the center node, the intermediate encoding results {z] {z),"N,, can be cached in storage and reused in subsequent computations when they are needed. As a result, the nodes can be prevented from being encoded repetitively, which saves great deal of unnecessary computation cost. We empirically verify that GraphFormers maintain similar performances when the above simplification is introduced.
3.3 Model Training: Two-Stage Progressive Learning
Training Objective. We take advantage of link prediction as our training task. Given a pair of nodes and k the model is learned to predict whether they are connected based on their embedding
Thhe encoding results be kept low-cost devices, whose storage capacity be regarded as infinite.
5

---

Table 1: Specifications of the experimental datasets: the number of items, the number of neighbour nodes on average, and the number of training, validation, testing cases.
Product
#llem
5,643,688
4,894,081
4,818,679
#N
4.71
9.31
8.86
#Train
22,146,934
3,009,506
7,145,834
#Valid
30,000
60,000
66,167
#Test
306,742
100,000
100,000
similarity. Particularly, the following classification loss minimized for a positive pair of q and k: cxp( (hg ha))
C log exp((hg) h₂)) + EPER exp( (ha. h,))
(6)
In the above equation, h and h3 are the node embeddings; (.) denotes the computation of inner product; R stands for the negative samples. In implementation, we leverage "in-batch negative samples" (Karpukhin et al.] 2020; Luan et al.) 2020) for the reduction of encoding cost: a positive sample in one training instance will be used negative sample in the rest of the training instances within the same mini-batch.
Two-stage Training. In GraphFormers, the information from the center node and neighbour nodes are not treated equally, which may undermine the model's training effect. Particularly, the center node's information can be directly utilized, while the neighbourhood information needs to be introduced via three steps: 1) encoded as node-level embeddings, 2) making graph aggregation with the center node, and 3) introduced to center node's graph augmented token-level embeddings. The message passing pathway can shortcut when the center nodes are "sufficiently informative", i.e., two nodes are sufficiently similar with each other in terms of their textual features, such that their connection can be predicted without considering the neighbours. Given the existence of such cases, GraphFormers may end up with well-trained Transformers but insufficiently trained GNNs.
To alleviate the above problem, we introduce a warm-up training task, where the link prediction made based on the polluted input nodes. Particularly, for each imput node g, a subset of its tokens Jm will be randomly masked") 44 As a result, the classification loss becomes:
exp( hg))
C' = exp( (ha, ha)) + EvEr exp((h;, h;))
where hj. hi. h are the embeddings generated from the polluted nodes. The masked tokens reduce the informativeness of each individual node; therefore, the model is forced leverage the whole input nodes to make the right prediction.
Finally, the model training is organized two-stage progressive learning process. In the first stage, the model is trained to minimize L' based on the polluted nodes until its convergence, which reinforce the model's 's capability of integrating information on graph. In the second stage, the model continually trained to minimize L based on the original data until the convergence, which makes the model fit into the target distribution.
4 Experimental Studies
4.1 Data and Settings
We make use of the following three real- world textual graph datasets for our experimental studies.
DBLF which contains the paper citation graph from DBLP up to 2020-04-09. Two papers linked if one cited by the other one. The paper's title is used as the textual feature.
Wikidata5M (Wiki) Waag et al. 2019b), which contains the entity graph from Wikipedia. The first sentence in each entity's ' introduction is taken as its textual feature.
P We remove the naive cases where q and i included by each other's neighbour set, N₂ and Ng-
"We use the common MLM strategy, where 15% of the input tokens are masked: 80% of them are replaced by [MASK], the rest ones replaced randomly or kept the original tokens with the same probabilities.

---

Table 2: Overall evaluation (GraphFormers marked in bold, the best baseline underlined). Graph-
Formers outperforms all baselines, especially the ones based on cascaded Transformers GNNN.
Product
Wiki
Methods
P6
NDCG
MRR
P6
NDCG
MRR
P@1
NDCG
MRR
PLM
0.6563
0.7911
0.7344
0.5673
0.7484
0.6777
0.3466
0.5799
0.4712
TNVE
0.4618
0.6204
0.5364
0.2978
0.5295
0.1786
0.4274
0.2933
IFTN
0.5233
0.6740
0.5982
0.3691
0.5798
0.4276
0.2945
PLM+GAT
0.7540
0.8637
0,8232
0.6633
0.8204
0.7667
0,3006
0.5430
0.4270
PLM+Max
0.7570
0.8678
0,8280
0.6934
0.8386
0.7900
0,3712
0.6071
0.5022
PLM+Mcan
0.7550
0.8671
0.8271
0.6896
0.8359
0.7866
0,3664
0.6037
0.4980
PLM+Au
0.7513
0,8652
0.8246
0.6910
0.8366
0.7875
0,3709
0.6067
0,5018
GraphFormers
0.7786
0.8793
0,8430
0.7267
0.8565
0,8133
0.3952
0,6230
0.5220
Product Graph (Product), an even larger dataset of online products collected by world-wide search engine. In this dataset, the users' web browsing behaviors are tracked for the targeted product webpages (c.g., Amazon webpages of Nike shoes). The user's continuously browsed webpages within a short period of time (e.g.. 30 minutes) is called a "session". The products within common session are connected in the graph (which is a common way of graph construction in e-commerce scenarios (Ying et al. 2018 Wang et al. 2018)). Each product has its unique textual description, which specifies information like the product name, brand, and saler, etc.
The textual features of all the datasets are in English. We make use of uncased WordPiece (Wu et al. 2016) to tokenize the input text. our experiment, each text is associated with uniformly sampled neighbours (without replacement); for texts with neighbourhood smaller than 5, all the neighbours will be utilized. We summarized the specifications of all the datasets with Table [ The experiment results evaluated in terms of link prediction accuracy, i.e., to predict whether a query node and key node are connected given the textual features of themselves and their neighbours. each testing instance, one query is provided with 300 keys: 1 positive plus 299 randomly sampled negative cases. We leverage three common metrics to measure the prediction accuracy: Precision 1, NDCG, and MRR. Without specifications, will take the unidirectional-simpiii two-stage progressive learning as our default model. More details about the implementations and the training/testing configurations summarized in Appendix file. It is submitted together with our source code within the supplementary materials.
GraphFormers trained with the
4.2 Baselines
We focus on the comparison between GNN-nested Transformers and Cascaded Transformers-GNY To make sure the difference between both architectures can be truthfully reflected from the evaluation results, GraphFormers and the Cascaded Transformers- NaNeeformerr-GNNNNAAN baselines are equipped with text encoders and graph aggregators of the same capacities. Particularly,
the BERT-like PLM as text encoder, where UniLMMbased [Bo et al. 2020) is chosen as the network backbone for all related methods; the final layer's [CLS] token embedding is used for the text embedding.
We enumerate the following representative graph aggregators as used in GAT (Veličković et al. 2018). GIN (Xu et al.) 2018). GraphSage (Hamilton et al., (2)7a). The GAT aggregator, where the node embedding is generated as the weighted sum all the text embeddings. Each text embedding relative importance is calculated as the attention score with the center node. The Pooling-and- Concat aggregators, where the center node's 's text embedding is concatenated with the neighbours' pooling result and linearly transformed for the final representation. Depending the form of pooling function, we have the following options: Max and Mean, where neighbours are aggregated by max-pooling and meean-polingg respectively: Att, where the neighbours summed up based on the attention weights with the center node. By comparison, the neighbourhood information may get more emphasized with GAT; while the center node itself tends to be highlighted with Pooling-and- Concat.
We consider two more baselines which make use of simplified text encoders (such as CNN) and network embeddings: TNVE (Wang et al. 2019a) and IFTN (Xu et al., 2019). We also include the PLM only baseline, which merely leverages the textual feature of the center node.
An enhanced BERT-like PLM showing more competitive performances than peers like RoBERTa, XLNet.
7

---

Table 3: Impact of neighbour size (#N).
GraphFormers
PLM+Max
#N
P@i
NDCG
MRR
P@
NDCG
MRR
0.6485
0.8087
0.7522
0.6249
0.7946
0.7342
2
0.6841
0.8308
0,7804
0.6538
0.8137
0.7583
3
0.6980
0.8196
0,7916
0.6728
0.8256
0.7734
0.7126
0,84885
0,8029
0.6823
0.8319
0.7814
0.7267
0,8365
0,8133
0.6934
0.8386
0.7900
4.3 Overall Evaluation
The overall evaluation results are reported in Table 2 It's observed that GraphFormers consistently outperform all the baselines, especially the ones based on the cascaded Transformers-GNN with notable advantages. Partieularly, it achieves 2.9%, 4.8%, 6.5% relative improvements over the most competitive baselines (underlined) on each of the experimental datasets. Such an observation indicates that the relationship between the nodes be captured more accurately based on the node embeddings generated by GraphFormers, which verifies the effectiveness of our proposed method.
We also observe the following underlying factors that may influence the representation quality.
Firstly, the effective utilization of neighbourhood information critical. With the joint consideration of the center node and neighbour nodes, the PLM++NNs methods, including GraphFormers and the cascaded Transformers- GNN baselines, significantly outperform the PLM only baseline in most of the time. We further analyze the impact of neighbourhood size as Table 3 with fraction of neighbour nodes randomly sampled for each center node (using DBLP for illustration). It can be observed that both GraphFormers and PLM+Max (the most competitive baseline) achieve higher prediction accuracy than the PLM only method (P@ 1:0.5673, NDCG:0.7484, MRR:0.6777, as reported in Table 2) even with fewer neighbour nodes included. With the increasing number of neighbour nodes, the advantages become gradually enlarged. However, the marginal gain is vanishing, as the relative improvement becomes smaller when more neighbours are included. In all the testing cases, GraphFormers maintain consistent advantages over PLM+Max, which reaffirms the effectiveness of our proposed methods.
Secondly, the capacity of the text encoder is crucial for textual graph representation. All the pretrained language model based methods (GraphFormers, Cascaded Transformers GNN baselines, PLM-only baseline) significantly outperform the baselines with simplified text encoders (TNVE, IFTN).
Thirdly, the representation quality is also sensitive to the form of graph aggregator. In Product, the cascaded Transformers-GGi baselines' performances
quite close to each other. In DBLP, PIM++MMx, Mean, Att) outperforms PLM+GAT. In Wiki, not only PLM++(Max, Mean, Att) but also PLM-only baseline outperform PLM+GAT. Such phenomenons could be attributed to the type of graph: whether it is homogeneous or heterogeneous. Particularly, both Product and DBLP can be regarded as homogencous graphs as the nodes are connected based on the same relationships; i.c. co-view relationship in Product, and citation relationship in DBLP. In both homogeneous graphs, the connected nodes may have quite similar semantics (the co-viewed products usually serve similar user intents, and the citation relationships usually indicate similar research topics): thus, the incorporated neighbour nodes will probably provide complementary information for the link prediction between the center nodes. However, Wiki is heterogeneous graph, where the connections between entities may have highly different semantics. As a result, the incorporation of neighbour nodes may not contribute to the link prediction task, especially when the incorporated neighbours and the prediction target are connected to the center nodes with totally different relationships. Considering that GAT tends to focus more the neighbourhood, its performance can be vulnerable in such unfavorable situations. These findings suggest that the neighbourhood information should be properly handled in case that the information of the center node is wiped out.
Finally, we may conclude different methods' utility in textual graph representation: simplified text encoders < PLMs x Cascaded Transformers-GNi X GNNs-nested Transformers. Such findings are consistent with our expectation that the precise modeling of individual textual feature and the effective integration of neighbourhood information will jointly contribute to high-quality textual graph representation. GraphFormers enjoy the high expressiveness of PLMS and leverage layerwise nested-GNNs to facilitate graph aggregation, which contributes to both of the above perspectives.
8

---

Table 4: Ablation Studies (The top ablated methods are marked in bold; "1"/""" the performance is increased/decreesed compared with the default setting). "-Progressive": two-stage progressive learning disabled; "-Simplified": unidirectional simplification disabled; "-Shared GNNs GNNs parameters are not shared across the layers; "-Position": GNNs learnable position bias disabled.
Product
DBLP
Wiki
Methods
P@
NDCG
MRR
P@
NDOG
MRR
P@1
NDCG
MRR
GraphFFormers
0,7786
0.8793
0.8430
0,7267
0.8565
0.8133
0.3952
0.6230
0.5220
Max
0,2570
0.8678
0.8280
0.6934
0.8386
0.7900
0.3712
0,5022
Progressive
0.7688
0.8751
0.8373
0,7096
0.8468
0.8007
0.3834
0,6155
0.5127
Simplified
0.7795
0,8798
0.8436
0.7225
0.8542
0.8102
0.3923
0,6209
0.5195
Shared GNNs
0.7788
0.8795
0.8433
0.7256
0.8558
0.8123
0.3945 4
0.6221 +
0,5211 J
Prsition
0.7788
0.8795
0.8434
0.7276
0.8570
0.8139
0.3942
0,6222
0.5211
Table 5: Time and memory costs per mini-batch for PLM+Max and GraphFormers, with neighbour size increased from 3 to 200. GraphFormers achieve similar efficiency and scalability as PLM+Max.
20
50
200
Time: PLM+Max
60.29 ms
93.41 ms
161.40 ms
295.92 ms
684.16 ms
1357.93 ms
2706.35 ms
Time: Framhrormers
63.95
97.19
170.16
306. ms
714.32 ms
1411.09
2801.77
Mem: PMM+Max
1.33 GiB
1.39 GiB
1.55 GiB
1.82 GiB
2.67 GiB
4.09 GiB
6.92 GiB
Mem: GraphFormers
1.33 GiB
1.39 GiB
1.55 GiB
1.83 GiB
2.70 GiB
4.28 GiB
7.33 GiB
4.4 Ablation Studies
The ablation studies (as Table 4 are performed to clarify the following issues: 1) the impact of two-stage progressive learning, and 2) the impact of unidirectional-smpliiee GraphFormers.
Firstly, the two-stage progressive learning substantially improves GraphFormers' representation quality. Without such a training strategy ("-Progressive": training directly on the original data), the model's performance is decreased by 0.98%, 1.71%, and 1.18% in each of the datasets, respectively.
Secondly, the performances between simplified and non-simplified ("-Simplified") GraphFormen are comparable. In fact, the necessity of graph aggregation is not equivalent for the center node and the neighbour nodes: since the center node is the one for representation, it is much more important to ensure that the center node may extract complementary information from its neighbours. The iitiircttionalsimplifiii
GraphFormers maintain such property; thus, there is little impact on the final performances. Such a finding affirms that we may safely leverage the simplified model to save the cost of repetitively encoding the existing neighbours.
We make two additional ablation studies. "-Shared GNNs": the GNNs parameters sharing disabled, where each layer maintains its own graph aggregator (by default, the layerwise GNN components in GraphFormers share the same set of parameters). " "-Position": the learnable position bias (b in Eq. D is disabled in GNNs. We find that model's performance is little affected from the above changes.
4.5 Efficiency Analysis
We compare the time efficiency between GNN-nested Transformers (GraphFormers) and Cascaded Transformers+GNN (using PLM+Max for comparison). The evaluation is made with a Nvidia P100 GPU. Each mini-batch contains 32 encoding instances; each instance contains center and #N neighbour nodes; the token length of each node is 16. We report the average time and memory (GPU RAM) costs per mini-batch as T
Firstly, the time and memory costs of both methods grow linearly with the increment of neighbours. (There are overheads of time and memory costs. The time cost overhead may come from CPU processing; while the memory cost overhead is mainly due to the model parameters (Rajbhandari et al. )) We may approximately remove the overheads by deducting the time and memory costs where #N=3). Such a finding is consistent with our theoretical analysis in Section 3.1
Secondly, the overall time and memory costs of GraphFormers are quite close to PLM+Max. When the number of neighbour nodes is small, the differences between both methods are almost ignorable. The differences become slightly larger when more neighbour nodes are included, because the layerwise

---

10-
224
66-
2.08
135
-02
-05
Figure 3: Online A/B Test: the relative improvements of RPM, CY and CPC against the last version of production system in Bing Search (green: positive; blue: negative). In most of the time, all three performance indicators are significantly improved thanks to the utilization of GraphFormers.
graph aggregations in GraphFormers get increasingly time consuming. However, the differences are still relatively small: merely around 3.5% of the overall running costs when #N is increased to 200 ("#N=200" is already more than enough for most of the real world scenarios).
Based on the above observations, we may conclude that GraphFormers are more accurate, meanwhile equally efficient and scalable as the conventional cascaded Transformer+GNNs.
4.6 Online A/B Test on Bing Search
GraphFormers has been deployed as one of the major ads retrieval algorithms on Bing Search, and achieves highly competitive performance against the previous production system (the combination of wide spectrum semantic representation algorithms, including large-scale PLMs and cascaded PLMs- GNNs). Particularly, the primary objective of Ads service is to maximize the revenue meanwhile increasing the user clicks. Therefore, following three metrics are taken as the major performance indicators: RPM (revenue per thousand impressions). CY (click yicld), and CPC (cost per click). During our large-scale online A/B test, GraphFormers significantly improves the overall RPM, CY, CPC by 1.87%, 0.96% and 0.91%, respectively. A 1 11-day performance snapshot is demonstrated as Figure 3 can be observed that in most of the time, all three metrics are significantly improved thanks to the utilization of GraphFormers (the daily performance measured based on millions of impressions, thus having strong statistic significance).
5 Conclusion
In this paper, we propose novel model architecture GraphFormers for textual graph representation. By having GNNs nested alongside each transformer layer of the pretrained language model, the underlying semantic of each textual node can be precisely captured and effectively integrated for high-quality textual graph representation. On top of the fundamental architecture, we introduce the two-stage progressive training strategy further strengthen GraphFormers' representation quality; also simplify the model with the unidirectional graph aggregation, which eliminates the unnecessary computation cost. The experimental studies on three large-scale textual graph datasets verify the effectiveness of our proposed methods, where GraphFormers notably outperform the existing cascaded Transformer-GNe GNNSs methods with comparable running efficiency and scalability.
6
Acknowledgement
We are grateful to anonymous reviewers for their constructive comments on this work. The work was supported by grants from the National Natural Science Foundation of China (No. 62022077).
References
Hangbo Bao, Li Dong, Furu Wei. Wenhui Wang, Nan Yang. Xiaodong Liu, Yu Wang. Jianfeng Gao, Songhao Piao, Ming Zhou, et al. 2020. Unilmv2: Pseudo-masker language models for unified
https://suppor..goo// wtt/s////ooooooaa//ss//////////e 16095
10

---

language model pre-training, In International Conference on Machine Learning, pages 642-652. PMLR.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. 2009, Curriculum learning. In Proceedings of the 26th annual international conference on machine learning, pages 41-48.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. arXiv preprint arXiv: 14165.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 04.000
Tianyu Gao, Xingcheng Yao, and Danqi Chen. 2021. Simese: Simple contrastive learning of sentence embeddings. arXiv preprint 2xXiv:2104.0882)
Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017a. Inductive representation learning on large graphs. Advances in neural information processing systems, pages 1024-1034.
William L. Hamilton, Rex Ying, and Jure Leskovec. 2017b. Representation learning on graphs: Methods and applications. arXiv preprint arXiv:1709.0553:
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-We Chang, and Yizhou Sun. 2020. Gpt-gnn: Generative pre- pre-training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pages 1857-1867.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen- tau Yih. 2020. Dense passage retrieval for open-domain question answering. arXiv preprint arXiv:2004.04996.
Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609.02977
Chaozhuo Li, Bochen Pang, Yuming Liu, Hao Sun, Zheng Liu, Xing Xie, Tianqi Yang, Yanling Cui, Liangjic Zhang, and Qi Zhang. 2021. Adsgnn: Behavior-graph augmented relevance modeling in sponsored search. XrXiv preprins ArXiv:2104 222104442200000 /2080.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019a. Roberta: A robustly optimized bert pretraining approach. arXiv preprint 1rXiv:1907.110
Zhenghao Liu, Chenyan Xiong, Maosong Sun, and Zhiyuan Liu. 2019b. Fine-grained fact verification with kernel graph attention network. arXiv preprint arXiv: 1910.0979.
Yi Luan, Jacob Eisenstein, Kristina Toutanova, and Michael Collins. 2020. Sparse, dense, and attentional representations for text retrieval. arXiv preprint arXiv:2005.00181.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Distributed representations of words and phrases and their compositionality. arXiv preprint 110.v:1310:4546,
Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014. Glove: Global vectors for word representation. In 2014 EMNLP, pages 1532-1543.
Matthew E Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. arXiv preprint 18Xiv:/802.08::
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018. Improving language understanding by generative pre-training
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2019. Exploring the limits of transfer learning with unified text-to-text transformer. arXiv preprint 190...391.

---

Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. 2020. Zero: Memory opti- mizations toward training trillion parameter models. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-16. IEFE.
Nils Reimers and Iryna Gurevych. 2019. Sentence-bert: Sentence embeddings using siamese bert- networks, arXiv preprini arXiv: 1908. 10084.
Jianlin Su, Jiarun Cao, Weijie Liu, and Yangyiwen Ou. 2021. Whitening sentence representations for better semanties and faster retrieval. arXiv preprint arXiv:2103.15316
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention all you need. arXiv preprint
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2018. Graph attention networks. International Conference on Learning Representations (ICLR).
Chenguang Wang, Yangqiu Song, Haoran Li, Ming Zhang, and Jiawei Han. 2016a. Text classification with heterogeneous information network kernels. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30.
Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. 2018. Billion- scale commodity embedding for e-commerce recommendation in alibaba. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 839-848.
Suhang Wang. Jiliang Tang, Charu Aggarwal, and Huan Liu. 2016b. Linked document embedding for classification. In Proceedings of the 25th ACM international on conference information and knowledge management, pages 115-124.
Wenlin Wang, Chenyang Tao, Zhe Gan, Guoyin Wang, Liqun Chen, Xinyuan Zhang, Ruiyi Zhang, Qian Yang. Ricardo Henao, and Lawrence Carin. 2019a. Improving textual network learning with variational homophilic embeddings. arXiv preprint arXiv: 13456.
Xiaozhi Wang, Tianyu Gao, Zhaocheng Zhu, Zhiyuan Liu, Juanzi Li, and Jian Tang. 2019b. Kepler: A unified model for knowledge embedding and pre-trained language representation. arXiv preprint arXiv:1911.0611
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le. Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016. Google's neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv: 1609608194.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.000
Zenan Xu, Qinliang Su, Xiaojun Quan, and Weijia Zhang. 2019. A deep neural information fusion architecture for textual network embeddings. arXiv preprint arxiv:1908.1103:
Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y Chang. 2015. Network representation learning with rich text information. In IJCAI, volume 2015, pages 2111-2117.
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Ruslan Salakhutdinov, and Quoe V Le. 2019, Xlnet: Generalized autoregressive pretraining for language understanding. arXiv preprint arXiv:1906.000 08237.
Michihiro Yasunaga Rui Zhang, Kshitijh Meelu, Ayush Pareek, Krishnan Srinivasan, and Dragomir Radev. 2017. Graph-based neural multi-document summarization. arXiv preprint arXiv: 1ee.1106606888
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. 2018. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974-983.
12

---

Jie Zhou, Ganqu Cui, Shengding Hu. Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2020. Graph neural networks: review of methods and applications. Al Open, 1:57-81.
Jie Zhou, Xu Han, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2019. Gear: Graph-based evidence aggregating and reasoning for fact verification. arXiv preprint arXiv:1908.01843.
Jason Zhu, Yanling Cui, Yuming Liu, Hao Sun, Xue Li, Markus Pelger, Liangjie Zhang, Tianqi Yan, Ruofei Zhang, and Huasha Zhao. 2021. Textgnn: Improving text encoder via graph neural network in sponsored search. arXiv preprint arXiv:2101.06323.
13


Reviews:
[{"review_id": "WmgEa5y7DTD", "reviewer": "Reviewer_1iRC", "summary": "This paper proposes a means to encode text feature for nodes in textual graphs, where a layerwise aggregation module (implemented as a multi-head self-attention) is appended after each Transformer encoder block that aggregates the hidden representations of (sampled) neighbor nodes. The produced contextual representations are dispatched to each node for the computation of next Transformer encoder block. To mitigate the possible model degradation issue that the aggregation module might be insufficiently trained, the authors also propose a two-stage training schedule where the model is first trained on nodes with corrupted inputs until convergence and then trained on normal data.", "questions": "", "limitations": "", "rating": 6, "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 proposes a novel text feature extraction method for textual graphs where intermediate representations of each node are contextualized using representations from neighbor nodes. It also proposes a two-stage training schedule to balance the capacity of the pre-trained text encoder and the aggregation modules.\n\nThe motivation that node representations should be contextualized in order to distinguish between nodes with similar texts but very different semantics is interesting. And the main method in this paper is clearly represented overall. However, there are still some concerns that I'd prefer the authors to address:\n\n- Position bias: In Eq. (1),  a learnable position bias is added to the unnormalized attention score where three types of bias (c2n,c2c,n2n) are utilized. What is the purpose of the bias term? It doesn't seem important to distinguish between the center node and the neighbor nodes. The ablation result seems to be insignificant and is not elaborated. \n- On data settings: In DBLP citation graph, the text feature is chosen to be the title of each paper, which I suspect might be not informative enough to encode the semantics of the paper. This issue is especially crucial when the titles are short. I was wondering if the authors have considered using abstracts as well.\n- Performance on Wiki: In line 274, the authors provide justification for the inferior performance of PLM+GAT on Wiki (see Table 2) from the heterogeneity of Wiki graph and that the incorporation of neighbor nodes might not contribute to the link prediction task. This justification seems at odds with the motivation and the performance of the proposed model (i.e., that the neighbor nodes can serve as additional information in generating the node representations).\n\nOverall I think the paper is built upon good motivations, but some aspects of the empirical results are not explained or not convincing enough. \n\n( Several minor notation issues and typos:\n\n- In Eq. (1), a multi-head self-attention is used to aggregate the information between nodes, in which a learnable position bias $\\mathbf{b}$ is added to the attention score. I believe the notation should be $\\mathbf{B}$ by convention.\n- Other typos: line 188: leverage (what?) of; line 257: varnishing -> vanishing; line 267: be attribute(d) to\n\n)\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In the last section, the authors list some of the limitations of the proposed method: 1. it doesn't take the edge information into account; 2. It is specifically designed for textual graphs.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "30"}, "extra_text": {}}, {"review_id": "WHuNMh4Nb2V", "reviewer": "Reviewer_Kwpr", "summary": "This paper proposes GraphFormers for text graph tasks where GNNs are nested in each layer of the transformer-based pretrained language model. In this way, each node can appropriate graph structure to build semantic representations more effectively. Two-stage progressive training and unidirectional graph aggregation are further proposed to improve representation quality and avoid unnecessary computation. They use three real-world million-scale textual graph datasets (DBMLP, Wikidata, Product Graph) and demonstrate consistent improvements compared with traditional cascaded transformers-GNN models.", "questions": "", "limitations": "", "rating": 7, "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": "Originality: The author first identify the weakness of the \"cascaded transformers-GNN\" architecture: the text encoding and graph aggregation are in two consecutive with no information exchanged in text embeddings. Based on this insight, the proposed approach differs from the traditional \"cascaded transformers-GNN\" by interleaving transformers and GNNs. They have adequately discussed a comprehensive set of related work in pretrained LM and GNNs.\n\nQuality: While this modification is simple, it is reasonable to nest GNNs into transformers to better encode information incorporating graph structures. The example in line 37-40 is helpful to illustrate the usefulness. The early usage and repetitive usage of graph structure is the main advantage of GraphFormers versus traditional manners. The added nested GNN operation is also small compared to transformers as discussed algorithmically and empirically.\n\nIn experiments, through comparison with other SOTA models and different variants of PLM+GNNs, the advantages of GraphFormers are supported and verified. \n\nHowever, the authors should clarify two things:\n1. Clearly define the center nodes against the neighbour nodes. Which node is defined as center nodes in each tasks? and how this will affect the results?\n2. In each layer of GNN, is the parameter shared? In other words, do you make sure the number of parameters is the same between GNN-nested transformers and Cascaded Transformers-GNN?\n\nClarify: The paper is well written and easy to follow. The technical components are documented in detail with equations and visualizations. However, the center node should be clearly defined.\n\nSignificance: In general, I believe their results of this new technique are solid. While the technique is simple and straightforward, comprehensive results have been presented to valid its effectiveness and efficiency. The proposed method can potentially change how other researchers use PLM and GNNs in a wide range of NLP tasks.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have acknowledged the limitations of their current work including (1) not including edge information, (2) only used for textual graphs. This opens up further directions.\n\nI don't see any potential negative societal impact.\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "LekmNA4Pq36", "reviewer": "Reviewer_nCrZ", "summary": "The paper proposes GraphFormer, an architecture built on top of GAT and Transformers for textual graphs. The motivation behind the architecture is that the existing techniques on textual graphs involve a cascade process where the nodes are first encoded using a language model after which a GNN is applied. With GraphFormers, the graph aggregation and encoding can happen iteratively, allowing for better contextualization of nodes with text like “notes on transformers” since transformers can be interpreted as ML models or electrical devices depending on the surrounding context.\n\nThe authors also lay out a 2-step training procedure whereby they first train on a version of the graph with injected noise via link prediction before training on the actual graph. The motivation behind this is given as the fact that training on the graph with injected noise makes the GNN component of the GraphFormer model more robust without which the transformer part will dominate.", "questions": "", "limitations": "", "rating": 7, "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": "Overall, this paper is a good one.  I like the motivation presented by the authors for their work. Indeed the cascade process for encoding textual graphs is not optimal, and the community as a whole will benefit from having a more concerted approach.\n\nStrengths of the paper:\n* The presented architecture is intuitive to understand where GNN and transformer are iteratively applied in the neighborhood aggregation process to allow for text at a node to be encoded taking into account the graph context.\n* Several experiments are performed to show the superiority of GraphFormer over cascaded approaches in link prediction task on three benchmark datasets.\n* Authors utilize caching in a succinct manner to decrease the recomputation needed for encoding different nodes in the graph; the caching works by preventing nodes that are neighbors of a central node to aggregate from the neighbors.\n\nWeaknesses of the paper:\n* The organization of the paper and the way in which the equations for GraphFormer are presented make the paper a bit hard to follow.\n* There are other works on making GNNs and aggregations within them scalable via caching (e.g., https://arxiv.org/pdf/2001.07524.pdf) but the authors have not made use of that, instead reinventing the wheel a little.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do clearly call out the limitation of the work in that GraphFormers are only applicable to textual graphs and does not take edge information like edge type or edge features into account. Therefore, they can’t be applied to heterogenous graphs.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5 hours"}, "extra_text": {}}, {"review_id": "3zVbh9_YaOI", "reviewer": "Reviewer_yPsh", "summary": "For representation learning on textual graphs, Cascaded Transformers-GNN architectures have been used, as language models and GNN are independently and consecutively deployed. The authors' claims, however, this approach has a limitation of information fusion of text encoding and graph structures. The authors proposed GNN-nested Transformers named as GraphFormers, where GNN components are nested alongside the transformer layers of language models. Also, the author proposed a progressive learning strategy and unidirectional graph attention to effectively train the graph network modules. The efficacy of the GraphFormers is demonstrated on 3 textual graph datasets (DBLP, Wiki, and Product Ads datasets), achieving SOTA performance.", "questions": "", "limitations": "", "rating": 6, "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": "1. Originality\n    1. The problem this paper tackle is interesting in which utilizing the neighborhood information during text encoding, and the proposing approach that inserting GNN layers into the transformer layers of PLM seems novel.\n    2. However, the nested GNN module's functionality is utilizing the related information of neighborhood nodes to learn the center node's representation using multi-headed attention layers. My main concern is that the proposed model should be theoretically and experimentally explained the differences to feeding all concatenated texts (i.e., $[g_1; g_2; ... ; g_n] , g_i \\in G_x$)  into transformer-based PLMs (especially large scale PLMs such as GPT-x, T5, etc) as an input. The concatenated text input approach may have advantages in the sense of more flexible and rich attention representation.\n2. Quality\n    1. This paper's claims are technically sound, and experimental results support the efficacy of GraphTransformers.\n    2. The proposed uni-directional graph attention for model simplification and two-stage progressive learning methods are well-studied through the ablation studies.\n3. Clarity\n    1. Overall, the paper is well-organized and well-written.\n    2. In figure 2, the asymmetric MHA is not correctly represented. From the figure, readers can misunderstand as symmetric MHA of $\\hat{H_g^l}$). Furthermore, in Algorithm 1 (in Appendix), Transformers[l]( Hg_hat[l], asymmetric = True) is not understandable. According to eq.4, the MHA^asy requires two different inputs.\n4. Significance\n    1. Lack of baseline of recent previous work (TwinBERT, AdsGNN, TextGNN, MetaBERT)\n    2. Lack of comparison with other PLMs. \n        - What is 'BERT-like PLM' exactly?\n        - Lack of leveraging recent large-scale PLMs such as T5 and GPT-x.\n    3. Lack of **comparison with feeding concatenated text inputs into large scale PLMs**\n    4. The Product Ads dataset is not published so that it is hard to reproduce the results. Since the dataset is new, the details such as how the dataset is collected, categories of the items, etc. should be explained. \n    5. Lack of qualitative analysis.\n    6. From table 4, there was little performance decrease when the learnable position bias is disabled, which concluding the bias is unnecessary.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors addressed the limitations of this work in terms of the problem scopes. From the author's checklist, I could find the Product Graph dataset is a private industrial dataset. I would like to recommend denote this and that the dataset will not be published due to the privacy issue in the main manuscript.", "review_text": "", "extra_scores": {"ethical_concerns": ".", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new model for learning representations on a textual graph. The key idea is to combine Transformer and graph neural network. Experimental results show that the proposed approach works better than the traditional cascade approach.

Strength
* The paper is generally clearly written, although there is still room for improvements on the presentation.
* The proposed model appears to be reasonable and technically sound.
* Experimental results have demonstrated the effectiveness of the proposed method.
* The reviewers pointed out some issues with the paper. The authors have successfully addressed most of them, particularly they provide new experimental results.

Weakness
* There are details that are not explained very clearly. The authors are encouraged to further improve the presentation.
* There are still problems with the English of the paper. For example, “graph aggregation and text encoding are iterative performed” --> it should be "iteratively". The authors are encouraged to do further proofreading. Please significantly revise the paper based on your replies in the rebuttal if the paper is accepted.

Minor comments: It is not clear for non-experts what the downstream tasks are from the explanation in the abstract and introduction. Please add that.


Decision: Accept (Poster)