summaries: 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. 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. 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.  The 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. 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.
abstractText: 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 .
authors.name: Junhan Yang
authors.name: Zheng Liu
authors.name: Shitao Xiao
authors.name: Chaozhuo Li
authors.name: Defu Lian
authors.name: Sanjay Agrawal
authors.name: Amit Singh
authors.name: Guangzhong Sun
authors.name: Xing Xie
references.authors: Songhao Piao Ming Zhou
references.title: Unilmv2: Pseudo-masked language models for unified 8https://support.google.com/adsense/answer/190515?hl=en 9https://support.google.com/google-ads/answer/116495?hl=en
references.authors: Yoshua Bengio Jérôme Louradour Ronan Collobert Jason Weston.
references.title: Curriculum learning
references.venue: Proceedings of the 26th annual international conference on machine learning, pages 41–48.
references.authors: Tom B Brown Benjamin Mann Nick Ryder Melanie Subbiah Jared Kaplan Prafulla Dhariwal Arvind Neelakantan Pranav Shyam Girish Sastry Amanda Askell
references.title: Language models are few-shot learners. arXiv preprint arXiv:2005.14165
references.authors: Jacob Devlin Ming-Wei Chang Kenton Lee Kristina Toutanova.
references.title: Bert: Pre-training of deep bidirectional transformers for language understanding
references.venue: arXiv preprint arXiv:1810.04805.
references.authors: Tianyu Gao Xingcheng Yao Danqi Chen.
references.title: Simcse: Simple contrastive learning of sentence embeddings
references.venue: arXiv preprint arXiv:2104.08821.
references.authors: Will Hamilton Zhitao Ying Jure Leskovec.
references.title: Inductive representation learning on large graphs
references.venue: Advances in neural information processing systems, pages 1024–1034.
references.authors: William L Hamilton Rex Ying Jure Leskovec.
references.title: Representation learning on graphs: Methods and applications
references.venue: arXiv preprint arXiv:1709.05584.
references.authors: Ziniu Hu Yuxiao Dong Kuansan Wang Kai-Wei Chang Yizhou Sun.
references.title: Gpt-gnn: Generative pre-training of graph neural networks
references.venue: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1857–1867.
references.authors: Vladimir Karpukhin Barlas Oğuz Sewon Min Ledell Wu Sergey Edunov Danqi Chen Wentau Yih.
references.title: Dense passage retrieval for open-domain question answering
references.venue: arXiv preprint arXiv:2004.04906.
references.authors: Thomas N Kipf Max Welling.
references.title: Semi-supervised classification with graph convolutional networks
references.venue: arXiv preprint arXiv:1609.02907.
references.authors: Chaozhuo Li Bochen Pang Yuming Liu Hao Sun Zheng Liu Xing Xie Tianqi Yang Yanling Cui Liangjie Zhang Qi Zhang.
references.title: Adsgnn: Behavior-graph augmented relevance modeling in sponsored search
references.venue: arXiv preprint arXiv:2104.12080.
references.authors: Yinhan Liu Myle Ott Naman Goyal Jingfei Du Mandar Joshi Danqi Chen Omer Levy Mike Lewis Luke Zettlemoyer Veselin Stoyanov.
references.title: Roberta: A robustly optimized bert pretraining approach
references.venue: arXiv preprint arXiv:1907.11692.
references.authors: Zhenghao Liu Chenyan Xiong Maosong Sun Zhiyuan Liu.
references.title: Fine-grained fact verification with kernel graph attention network
references.venue: arXiv preprint arXiv:1910.09796.
references.authors: Yi Luan Jacob Eisenstein Kristina Toutanova Michael Collins.
references.title: Sparse, dense, and attentional representations for text retrieval
references.venue: arXiv preprint arXiv:2005.00181.
references.authors: Tomas Mikolov Ilya Sutskever Kai Chen Greg Corrado Jeffrey Dean.
references.title: Distributed representations of words and phrases and their compositionality
references.venue: arXiv preprint arXiv:1310.4546.
references.authors: Jeffrey Pennington Richard Socher Christopher D Manning.
references.title: Glove: Global vectors for word representation
references.venue: 2014 EMNLP, pages 1532–1543.
references.authors: Matthew E Peters Mark Neumann Mohit Iyyer Matt Gardner Christopher Clark Kenton Lee Luke Zettlemoyer.
references.title: Deep contextualized word representations
references.venue: arXiv preprint arXiv:1802.05365.
references.authors: Alec Radford Karthik Narasimhan Tim Salimans Ilya Sutskever
references.title: Improving language understanding by generative pre-training
references.authors: Colin Raffel Noam Shazeer Adam Roberts Katherine Lee Sharan Narang Michael Matena Yanqi Zhou Wei Li Peter J Liu.
references.title: Exploring the limits of transfer learning with a unified text-to-text transformer
references.venue: arXiv preprint arXiv:1910.10683.
references.authors: Samyam Rajbhandari Jeff Rasley Olatunji Ruwase Yuxiong He
references.title: Zero: Memory optimizations toward training trillion parameter models
references.venue: In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis,
references.authors: Nils Reimers Iryna Gurevych.
references.title: Sentence-bert: Sentence embeddings using siamese bertnetworks
references.venue: arXiv preprint arXiv:1908.10084.
references.authors: Jianlin Su Jiarun Cao Weijie Liu Yangyiwen Ou.
references.title: Whitening sentence representations for better semantics and faster retrieval
references.venue: arXiv preprint arXiv:2103.15316.
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Lukasz Kaiser Illia Polosukhin.
references.title: Attention is all you need
references.venue: arXiv preprint arXiv:1706.03762.
references.authors: Petar Veličković Guillem Cucurull Arantxa Casanova Adriana Romero Pietro Lio Yoshua Bengio.
references.title: Graph attention networks
references.venue: International Conference on Learning Representations (ICLR).
references.authors: Chenguang Wang Yangqiu Song Haoran Li Ming Zhang Jiawei Han.
references.title: Text classification with heterogeneous information network kernels
references.venue: Proceedings of the AAAI Conference on Artificial Intelligence, volume 30.
references.authors: Jizhe Wang Pipei Huang Huan Zhao Zhibo Zhang Binqiang Zhao Dik Lun Lee.
references.title: Billionscale commodity embedding for e-commerce recommendation in alibaba
references.venue: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 839–848.
references.authors: Suhang Wang Jiliang Tang Charu Aggarwal Huan Liu.
references.title: Linked document embedding for classification
references.venue: Proceedings of the 25th ACM international on conference on information and knowledge management, pages 115–124.
references.authors: Wenlin Wang Chenyang Tao Zhe Gan Guoyin Wang Liqun Chen Xinyuan Zhang Ruiyi Zhang Qian Yang Ricardo Henao Lawrence Carin.
references.title: Improving textual network learning with variational homophilic embeddings
references.venue: arXiv preprint arXiv:1909.13456.
references.authors: Xiaozhi Wang Tianyu Gao Zhaocheng Zhu Zhiyuan Liu Juanzi Li Jian Tang.
references.title: Kepler: A unified model for knowledge embedding and pre-trained language representation
references.venue: arXiv preprint arXiv:1911.06136.
references.authors: Yonghui Wu Mike Schuster Zhifeng Chen Quoc V Le Mohammad Norouzi Wolfgang Macherey Maxim Krikun Yuan Cao Qin Gao Klaus Macherey
references.title: 2016. Google’s neural machine translation system: Bridging the gap between human and machine translation
references.venue: arXiv preprint arXiv:1609.08144
references.authors: Keyulu Xu Weihua Hu Jure Leskovec Stefanie Jegelka
references.title: How powerful are graph neural networks? arXiv preprint arXiv:1810.00826
references.authors: Zenan Xu Qinliang Su Xiaojun Quan Weijia Zhang.
references.title: A deep neural information fusion architecture for textual network embeddings
references.venue: arXiv preprint arXiv:1908.11057.
references.authors: Cheng Yang Zhiyuan Liu Deli Zhao Maosong Sun Edward Y Chang.
references.title: Network representation learning with rich text information
references.venue: IJCAI, volume 2015, pages 2111–2117.
references.authors: Zhilin Yang Zihang Dai Yiming Yang Jaime Carbonell Ruslan Salakhutdinov Quoc V Le.
references.title: Xlnet: Generalized autoregressive pretraining for language understanding
references.venue: arXiv preprint arXiv:1906.08237.
references.authors: Michihiro Yasunaga Rui Zhang Kshitijh Meelu Ayush Pareek Krishnan Srinivasan Dragomir Radev.
references.title: Graph-based neural multi-document summarization
references.venue: arXiv preprint arXiv:1706.06681.
references.authors: Rex Ying Ruining He Kaifeng Chen Pong Eksombatchai William L Hamilton Jure Leskovec.
references.title: Graph convolutional neural networks for web-scale recommender systems
references.venue: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974–983.
references.authors: Jie Zhou Ganqu Cui Shengding Hu Zhengyan Zhang Cheng Yang Zhiyuan Liu Lifeng Wang Changcheng Li Maosong Sun
references.title: Graph neural networks: A review of methods and applications
references.venue: AI Open,
references.authors: Jie Zhou Xu Han Cheng Yang Zhiyuan Liu Lifeng Wang Changcheng Li Maosong Sun.
references.title: Gear: Graph-based evidence aggregating and reasoning for fact verification
references.venue: arXiv preprint arXiv:1908.01843.
references.authors: Jason Zhu Yanling Cui Yuming Liu Hao Sun Xue Li Markus Pelger Liangjie Zhang Tianqi Yan Ruofei Zhang Huasha Zhao.
references.title: Textgnn: Improving text encoder via graph neural network in sponsored search
references.venue: arXiv preprint arXiv:2101.06323.
sections.heading: 1 Introduction
sections.text: The textual graph is a 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 as 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 et al., 2017a) and GAT (Veličković et al., 2018), neighbours can be effectively aggregated for more informative node embeddings. It is necessary to combine both techniques for better textual graph representation. As
  ∗Work was done by 2021.01 during Junhan Yang and Shitao Xiao’s internship in MSRA
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  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-mounted GNNs for the final node embeddings. Such a representation paradigm has been widely adopted by subsequent works on various scenarios (Zhu et al., 2021; Li et al., 2021; Hu et al., 2020; Liu et al., 2019b; Zhou et al., 2019), where GNNs are combined with powerful PLM-based text encoders.
  The above way of combination is called the “Cascaded Transformers-GNN” architecture (Figure 1 A), as 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 no 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 “transformers” here can be interpreted as a machine learning model, rather than an electric device.
  Our Work. We propose “GNN-nested Transformers” (GraphFormers), which are highlighted for the fusion of GNNs and language models (Figure 1 B). In GraphFormers, the GNN components are nested alongside the transformer layers (TRM) of language models, where the text encoding and graph aggregation are fused as an 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 on 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-head attention, GraphFormers preserve comparable running costs as the existing cascaded Transformers-GNN models.
  On top of the proposed model architecture, we further improve GraphFormers’ representation quality 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 to 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 in the representation process: once a new node is presented, all the neighbours, regardless of whether they have been processed before, need to be encoded from scratch. As a result, a 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.
  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 TransformersGNN baselines with comparable running efficiency.
sections.heading: 2 Related Work
sections.text: 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., 2016b,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., 2013) and GloVe (Pennington et al., 2014). In recent years, the backbone networks are being quickly scaled up: from EMLo (Peters et al., 2018), GPT (Radford et al., 2018), to BERT (Devlin et al., 2018), XLNet (Yang et al., 2019), 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 on 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 on downstream tasks, like text retrieval and classification (Reimers and Gurevych, 2019; Luan et al., 2020; Gao et al., 2021; Su et al., 2021).
  GNN. Graph neural networks are recognized as powerful tools of modeling graph data (Hamilton et al., 2017b; Zhou et al., 2020). Such methods (e.g., GCN (Kipf and Welling, 2016), GAT (Veličković et al., 2018), GraphSage (Hamilton et 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 at first; then, the node embeddings are aggregated via GNNs to generate the final representations. Such a representation paradigm is widely adopted by subsequent works (Zhu et al., 2021; Li et al., 2021; Hu 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”.
sections.heading: 3 GraphFormers
sections.text: In this work, we deal with textual graph data, where each node x is a text. The node x together with its neighbours Nx are denoted as Gx. Our model learns the embedding for node x based on its own textual feature and the information of its neighbourhood Nx. The generated embeddings are expected to capture the relationship between the nodes, i.e., to accurately predict whether two nodes xq and xk are connected based on the embedding similarity.
sections.heading: 3.1 GNN-nested Transformers
sections.text: 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 {H0g}G based on the summation of word embeddings and position embeddings. The embedding sequences are encoded by multiple layers of GNN-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 in the l-th layer, the first token-level embedding (corresponding to [CLS]) is taken as the node-level embedding: zlg ← Hlg[0]. The node-level embeddings
  are gathered from all the nodes and passed to the layerwise GNN for graph aggregation. We leverage Multi-Head Attention (MHA) to encode the node-level embeddings ZlG ({zlg}G), similar as GAT (Veličković et al., 2018). For each attention head, the scaled dot-product attention is performed as:
  ẐlG = MHA(Z l G);
  MHA(ZlG) = Concat(head1, ...,headh);
  headj = softmax( QKT√
  d +B)V;
  Q = ZlGW Q j ; K = Z l GW K j ; V = Z l GW V j ;
  (1)
  In the above equations, WQj , W K j , and W V j 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” (x to x), “center-to-neighbour” (x to Nx), and “neighbour-to-neighbour” (Nx to Nx), respectively.
  Each of the embeddings ẑlg (ẑ l g ∈ ẐlG) is dispatched to its original node and concatenated (⊕) with the token-level embeddings, which gives rise to the graph-augmented token-level embeddings:
  Ĥlg ← Concat(ẑlg,Hlg). (2)
  In this place, the GNN-processed node-level embeddings ẐlG 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̂lg are processed by the transformer component (Vaswani et al., 2017), where the following computations are performed:
  Ĥlg = LN(H l g +MHA asy(Ĥlg));
  Hl+1g = LN(Ĥ l g +MLP(Ĥ l g)).
  (3)
  In the above equations, MLP is the Multi-Layer Projection unit, and LN is the Layer-Norm unit. We use asymmetric Multi-Head Attention (MHAasy), where Q, K, V are computed as:
  Q = HlgW Q j ; K = Ĥ l gW K j ; V = Ĥ l gW V j . (4)
  Therefore, the output sequence Hl+1g will be of the same length as the input sequence H l g. The encoding result will be used as the input token-level embeddings for the next layer. The node-level embedding at the last layer zLx (i.e., H L g [0]) will be used as the final node representation.
  •Workflow. We summarize GraphFormers’ encoding workflow as Algorithm 1. The initial tokenlevel embeddings {H0g}G are independently encoded by the first Transformer layer TRM
  0. For a L-layer GraphFormers, the graph aggregation and text encoding are iteratively performed for the subsequent L-1 steps (from 1 to L− 1). In each step, the node-level embeddings ZlG are gathered and
  Algorithm 1: GraphFormers’ Workflow Input: The input graphs G (consist of the center node x and its neighbours). Output: The embedding for the center node hx.
  1 begin 2 for each text g ∈ G do 3 H1g ← TRM 0(H0g); // Get the initial token-level embeddings
  4 for l = 1, ..., L− 1 do 5 ZlG ← {zlg|g∈G}; // Gather node-level embeddings to GNN 6 ẐlG ← GNN(ZlG); // Graph aggregation in GNN 7 for each text g ∈ G do 8 Ĥlg ← Concat(ẑlg,Hlg); // Get graph-augmented token-level embeddings 9 Hl+1g ← TRM l(Ĥlg); // Text encoding in Transformer
  10 Return hx ← zLx ;
  processed by the layerwise GNN component. The output node-level embeddings ẐlG are dispatched to their original nodes, which generates the graph-augmented token-level embeddings Ĥlg . The graphaugmented token-level embedding are further processed by the Transformer component. Finally, The node-level embedding (for the center node x) in the last layer zLx is taken as our representation result.
  • Encoding Complexity. Given an input of M nodes, each one has P tokens; the time complexity of each layer’s encoding operation is O(M2 +MP 2): the graph aggregation takes O(M2), because M node-level embeddings are gathered for multi-head attention; the text encoding takes O(MP 2), as each of the M node calls for the multi-head attention of P tokens. Compared with Transformers, the GNN’s computation cost is much smaller, mainly because of two reasons: 1) M2 MP 2 in general, 2) operations like MLP are not needed in graph aggregation. Therefore, the working efficiency of GraphFormers is close to the cascaded GNN-Transformers as the extra computation cost of layerwise graph aggregation is relatively small. Such a property is also empirically verified in our experiment.
sections.heading: 3.2 Model Simplification: Unidirectional Graph Aggregation
sections.text: One concern about GraphFormers is that the input nodes are mutually dependent on each other during the encoding process. As a result, to generate the embedding for a 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 is unfavorable in practice as a great deal of unnecessary computation cost might be incurred (i.e., a node will be repetitively encoded every time it serves as a neighbour node). We leverage a simple but effective simplification, the unidirectional graph aggregation, to address this problem. Particularly, only the center node x is required to make reference to the neighbourhood; while the rest of nodes Nx remain independently encoded all by their own textual features:
  Hl+1g =
  { TRMl(Ĥlx), g = x;
  TRMl(Hlg), ∀g ∈ Nx. (5)
  Because the encoding of the neighbour nodes is independent of the center node, the intermediate encoding results {z1...Lg }Nx can be cached in storage2 and reused in subsequent computations when they are needed. As a result, the nodes can be prevented from being encoded repetitively, which saves a great deal of unnecessary computation cost. We empirically verify that GraphFormers maintain similar performances when the above simplification is introduced.
sections.heading: 3.3 Model Training: Two-Stage Progressive Learning
sections.text: • Training Objective. We take advantage of link prediction as our training task. Given a pair of nodes q and k, the model is learned to predict whether they are connected based on their embedding
  2The encoding results can be kept in low-cost devices, whose storage capacity can be regarded as infinite.
  similarity. Particularly, the following classification loss is minimized for a positive pair of q and k:3
  L = − log exp(〈hq,hk〉) exp(〈hq,hk〉) + ∑ r∈R exp(〈hq,hr〉) . (6)
  In the above equation, hq and hk are the node embeddings; 〈·〉 denotes the computation of inner product; R stands for the negative samples. In our 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 as a 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 own 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 is made based on the polluted input nodes. Particularly, for each input node g, a subset of its tokens gm will be randomly masked4. As a result, the classification loss becomes:
  L′ = − log exp(〈hq̃,hk̃〉) exp(〈hq̃,hk̃〉) + ∑ r∈R exp(〈hq̃,hr̃〉) , (7)
  where hq̃ , hk̃, hr̃ are the embeddings generated from the polluted nodes. The masked tokens reduce the informativeness of each individual node; therefore, the model is forced to leverage the whole input nodes to make the right prediction.
  Finally, the model training is organized as a 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 capability of integrating information on graph. In the second stage, the model is continually trained to minimize L based on the original data until the convergence, which makes the model fit into the target distribution.
sections.heading: 4 Experimental Studies
sections.heading: 4.1 Data and Settings
sections.text: We make use of the following three real-world textual graph datasets for our experimental studies.
  • DBLP5, which contains the paper citation graph from DBLP up to 2020-04-09. Two papers are linked if one is cited by the other one. The paper’s title is used as the textual feature.
  •Wikidata5M6 (Wiki) (Wang et al., 2019b), which contains the entity graph from Wikipedia. The first sentence in each entity’s introduction is taken as its textual feature.
  3We remove the naive cases where q and k are included by each other’s neighbour set, Nq and Nk. 4We use the common MLM strategy, where 15% of the input tokens are masked: 80% of them are replaced
  by [MASK], the rest ones are replaced randomly or kept as the original tokens with the same probabilities. 5https://originalstatic.aminer.cn/misc/dblp.v12.7z 6https://deepgraphlearning.github.io/project/wikidata5m
  • Product Graph (Product), an even larger dataset of online products collected by a world-wide search engine. In this dataset, the users’ web browsing behaviors are tracked for the targeted product webpages (e.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 a 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. In our experiment, each text is associated with 5 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 1. The experiment results are 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. In 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, we will take the unidirectional-simplified GraphFormers trained with the two-stage progressive learning as our default model. More details about the implementations and the training/testing configurations are summarized in an Appendix file. It is submitted together with our source code within the supplementary materials.
sections.heading: 4.2 Baselines
sections.text: We focus on the comparison between GNN-nested Transformers and Cascaded Transformers-GNN. To make sure the difference between both architectures can be truthfully reflected from the evaluation results, GraphFormers and the Cascaded Transformers-GNN baselines are equipped with text encoders and graph aggregators of the same capacities. Particularly, we use the BERT-like PLM as our text encoder, where UniLM-base7 (Bao 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 (Veličković et al., 2018), GIN (Xu et al., 2018), GraphSage (Hamilton et al., 2017a). The GAT aggregator, where the node embedding is generated as the weighted sum of all the text embeddings. Each text embedding’s relative importance is calculated as the attention score with the center node. The Pooling-andConcat aggregators, where the center node’s text embedding is concatenated with the neighbours’ pooling result and linearly transformed for the final representation. Depending on the form of pooling function, we have the following options: Max and Mean, where neighbours are aggregated by max-pooling and mean-pooling, respectively; Att, where the neighbours are 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.
  7An enhanced BERT-like PLM showing more competitive performances than peers like RoBERTa, XLNet.
sections.heading: 1 0.6485 0.8087 0.7522 0.6249 0.7946 0.7342
sections.heading: 2 0.6841 0.8308 0.7804 0.6538 0.8137 0.7583
sections.heading: 3 0.6980 0.8396 0.7916 0.6728 0.8256 0.7734
sections.heading: 4 0.7126 0.8485 0.8029 0.6823 0.8319 0.7814
sections.heading: 5 0.7267 0.8565 0.8133 0.6934 0.8386 0.7900
sections.heading: 4.3 Overall Evaluation
sections.text: 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. Particularly, 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 can 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 is critical. With the joint consideration of the center node and neighbour nodes, the PLM+GNNs 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 a 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-GNN baselines’ performances are quite close to each other. In DBLP, PLM+(Max, 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 homogeneous graphs as the nodes are connected based on the same relationships; i.e., 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 a 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 on 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 ≺ Cascaded Transformers-GNN ≺ 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.
sections.heading: 4.4 Ablation Studies
sections.text: 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-simplified 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”) GraphFormers 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 unidirectional-simplified GraphFormers maintain such a 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 is 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. 1) is disabled in GNNs. We find that model’s performance is little affected from the above changes.
sections.heading: 4.5 Efficiency Analysis
sections.text: 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 one 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 Table 5.
  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., 2020)). 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
  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.
sections.heading: 4.6 Online A/B Test on Bing Search
sections.text: GraphFormers has been deployed as one of the major ads retrieval algorithms on Bing Search, and it achieves highly competitive performance against the previous production system (the combination of a wide spectrum of semantic representation algorithms, including large-scale PLMs and cascaded PLMsGNNs). Particularly, the primary objective of Ads service is to maximize the revenue meanwhile increasing the user clicks. Therefore, the following three metrics are taken as the major performance indicators: RPM8 (revenue per thousand impressions), CY (click yield), and CPC9 (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 11-day performance snapshot is demonstrated as Figure 3; it can be observed that in most of the time, all three metrics are significantly improved thanks to the utilization of GraphFormers (the daily performance are measured based on millions of impressions, thus having strong statistic significance).
sections.heading: 5 Conclusion
sections.text: In this paper, we propose a 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 to further strengthen GraphFormers’ representation quality; we 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-GNNs methods with comparable running efficiency and scalability.
sections.heading: 6 Acknowledgement
sections.text: 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).
title: GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph