Back

GOAT: A Global Transformer on Large-scale Graphs

Kezhi KongJiuhai ChenJohn KirchenbauerRenkun NiC. Bayan BrussTom Goldstein

article2023ICML74 citations

Proposes GOAT, a scalable graph transformer that reduces global self-attention complexity from quadratic to linear via cluster-based dimensionality reduction, enabling efficient and theoretically bounded node classification across multi-million-node homophilous and heterophilous graphs.

Listen

Large graph datasets with millions of entities and connections are critical across modern industries, powering applications such as e-commerce recommendation systems, fraud detection, and patent analysis. Existing machine learning methods on graphs face a fundamental dilemma: standard graph neural networks assume that connected entities share similar attributes (homophily) and struggle when connected entities differ (heterophily). Meanwhile, powerful transformer models that could theoretically learn both patterns fail to scale to large graphs because comparing every entity to every other entity requires impractical amounts of computer memory.

The article evaluates a new scalable global transformer architecture called GOAT (Global trAnsformer on large-scale graphs). The main objective is to demonstrate that a single model can efficiently perform node classification on multi-million-node graphs regardless of whether the network exhibits homophilous or heterophilious connection patterns.

The research evaluates this model across four large-scale benchmark datasets comprising up to 2.9 million nodes, covering both homophilious environments (such as product co-purchasing and academic citations) and heterophilious environments (such as patent citation networks and publication years). To overcome memory bottlenecks, the approach uses a clustering-based dimensionality reduction technique that summarizes the entire graph into a compact set of representative centroids (a codebook), reducing computational complexity from quadratic to linear. This global context is combined with a local attention module that directly examines multi-hop neighbor relationships, supported by theoretical proofs ensuring that the mathematical approximation introduces bounded, controlled error.

The empirical findings demonstrate that GOAT achieves strong and balanced performance across varied graph types. First, on homophilious datasets, GOAT matched or outperformed standard graph models, achieving 72.41% accuracy on the academic network and 82.00% on the product network. Second, on heterophilious datasets, GOAT significantly outperformed traditional graph neural networks by approximately 10 to 20 percentage points across various data splits, matching specialized heterophily architectures. Third, across all tested scenarios, GOAT achieved the highest overall average accuracy (64%) compared to baseline models (which averaged between 55% and 61%), while a state-of-the-art scalable graph transformer benchmark failed completely due to out-of-memory errors. Finally, ablation studies showed that the global context module contributed up to a 3% performance boost on heterophilious graphs, confirming the value of long-range pattern learning.

These results demonstrate that organizations do not need to diagnose network structures in advance or maintain separate, specialized models for different graph types. Adopting an adaptive transformer architecture reduces engineering overhead and operational risk when graph properties are mixed or unknown. Furthermore, the linear scaling enables organizations to train models on standard enterprise hardware without incurring prohibitive cloud computing or graphics hardware costs.

Decision-makers should consider piloting scalable graph transformers in workflows where entity relationships are complex or poorly understood. Implementation teams should start by benchmarking the global-only variant for high-throughput pipelines, as it provides rapid convergence with minimal memory overhead, and introduce the local module when predictive precision is paramount. Future technical initiatives should focus on exploring more efficient neighbor sampling methods and investigating multi-layer transformer configurations.

The primary operational limitation is that the local attention component relies on neighborhood sampling, which can create processing bottlenecks as the search depth expands. Additionally, the current implementation is restricted to a single attention layer, leaving the potential of deeper architectures unmeasured. Despite these constraints, the theoretical guarantees and consistent empirical results provide high confidence that this approach represents a robust, scalable foundation for enterprise graph analysis.

classificationcloud computingclustering algorithmsscalable graph transformerscalable global attentionlarge-scale graphs
Kong et al (2023).pdf

No sufficiently relevant recommendations were found.

Cover for GOAT: A Global Transformer on Large-scale Graphs

Topics

classificationcloud computingclustering algorithmscodebookscommercedimensionality reduction techniquese-commerceencoder-decoderengineeringgraph neural networks

Keywords

scalable graph transformerscalable global attentionlarge-scale graphslarge-scale node classification tasksOpen Graph Benchmarkneighbor samplingpositional encodings

Table of Contents

  • 1. Introduction
  • 2. Preliminaries
  • 3. Method
  • 4. Experiments
  • 5. Ablation Studies & Analysis
  • 6. Related Work
  • 7. Conclusion
  • Acknowledgements
  • References
  • A. More Theoretical Analysis
  • B. More Ablation Studies
  • C. Proofs
  • C.1. Proof of Proposition A.1
  • C.2. Proof of Theorem 3.2
  • C.3. Proof of Theorem 3.3
  • C.4. Proof of Corollary 3.4
  • D. Experimental Details
  • D.1. Dataset Downloading
  • D.2. GOAT
  • D.3. Baseline Models

Knowls

  1. Knowl 1 — GOAT combines global and local attention for node classification

    model/method

    GOAT is a one-layer, multi-head graph transformer designed for transductive node classification on large graphs. Each node forms a query from its transformed features and absolute positional embedding; the global module lets it attend to a compressed representation of all graph nodes, while the local module lets it attend directly to sampled nearby nodes. GOAT uses pretrained node2vec embeddings as absolute positional encodings in the global module and a separate relative-distance encoding in the local module. It combines the outputs of the two attention modules, along with their corresponding node features and positional encodings, for prediction. Unlike a message-passing architecture that fixes how neighboring nodes contribute, GOAT learns attention weights from data and can therefore represent associations not restricted to homophilous neighborhoods. The experiments use one attention layer; extending this design to multiple layers is not established by the paper.

  2. Knowl 2 — Direct local attention uses sampled multi-hop neighbors and distance biases

    model/method

    For a target node ii, GOAT’s local module samples its neighbors out to ll hops and lets ii attend directly to the sampled nodes rather than recursively aggregating one-hop messages. The attention score from ii to sampled node jj is Sij=(XiWQ)(XjWK)⊤d+bD(i,j)S_{ij}=\frac{(X_iW_Q)(X_jW_K)^\top}{\sqrt{d}}+b_{D(i,j)}. Here, XiX_i and XjX_j are the input feature row vectors for nodes ii and jj; WQW_Q and WKW_K are learned query and key projections; dd is the projected feature dimension; D(i,j)D(i,j) is their shortest-path distance; and brb_r is a learned scalar bias for distance rr. Scores are normalized over the sampled candidates for each target. The reported configuration samples three-hop neighborhoods with fanouts [20,10,5][20,10,5] at successive hops. The direct attention and distance-specific biases give the module flexibility to learn how information from different hop distances contributes.

  3. Knowl 3 — A K-means codebook implements approximate global attention

    model/method

    GOAT compresses graph-wide keys and values by assigning nodes to kk clusters. For a node-feature matrix X∈Rn×fX\in\mathbb{R}^{n\times f}, let P∈{0,1}n×kP\in\{0,1\}^{n\times k} be the one-hot node-to-cluster assignment matrix, with one nonzero entry in each row. Let mjm_j be the number of nodes assigned to cluster jj, and let m=(m1,…,mk)m=(m_1,\ldots,m_k). The feature centroid matrix is C=diag⁡(m)−1P⊤XC=\operatorname{diag}(m)^{-1}P^\top X, with the inverse applied to nonempty clusters. The compressed keys and values are Kc=CWKK_c=CW_K and Vc=CWVV_c=CW_V, where WKW_K and WVW_V are learned projections. For a mini-batch feature matrix XBX_B, queries are Q=XBWQQ=X_BW_Q, and the global output is computed as Softmax⁡(QKc⊤/d+log⁡m)Vc\operatorname{Softmax}(QK_c^\top/\sqrt d+\log m)V_c, with softmax applied row-wise and the cluster-count term correcting for the number of nodes represented by each centroid. GOAT caches and updates centroid statistics using an exponential moving average of mini-batch assignments and feature sums; it uses batch normalization when updating the centroids and stores the one-hot assignments sparsely. For fixed codebook size, attention computation is O(bdk)O(bdk) for batch size bb and projected dimension dd, rather than forming an n×nn\times n attention matrix. The reported experiments use a codebook size of 4,096 and a compressed dimension of 64.

  4. Knowl 4 — Random projections give a bounded-error global-attention approximation

    theoretical result

    Assume positional information has already been incorporated into the node features. Let X∈Rn×fX\in\mathbb{R}^{n\times f} be the feature matrix for nn nodes, XB∈Rb×fX_B\in\mathbb{R}^{b\times f} the features of a mini-batch of bb query nodes, and WQ,WK,WV∈Rf×dW_Q,W_K,W_V\in\mathbb{R}^{f\times d} the learned projections. Define S=XBWQ(XWK)⊤/dS=X_BW_Q(XW_K)^\top/\sqrt d. The paper establishes that, for any ε>0\varepsilon>0, projection matrices PA,PV∈Rn×kP_A,P_V\in\mathbb{R}^{n\times k} can be chosen so that Softmax⁡(SPA)PV⊤XWV\operatorname{Softmax}(SP_A)P_V^\top XW_V approximates the full-attention output Softmax⁡(S)XWV\operatorname{Softmax}(S)XW_V with probability greater than 1−O(1/n)1-O(1/n), with Frobenius error at most ε∥Softmax⁡(S)∥F∥XWV∥F\varepsilon\|\operatorname{Softmax}(S)\|_F\|XW_V\|_F. The required projection dimension is k=O(log⁡(n)/ε2)k=O(\log(n)/\varepsilon^2). This is an existence guarantee for the projection scheme; the practical GOAT implementation uses K-means assignments to construct its compressed representation.

  5. Knowl 5 — Feature quantization bounds the output error of compressed attention

    theoretical result

    Let X~\widetilde X be the codebook reconstruction of node features XX, with quantization error ∥X−X~∥F≤ε∥X∥F\|X-\widetilde X\|_F\leq\varepsilon\|X\|_F. For a mini-batch XBX_B, define fW(Y)=Softmax⁡(XBWQ(YWK)⊤/d)f_W(Y)=\operatorname{Softmax}(X_BW_Q(YW_K)^\top/\sqrt d), where WQ,WK,WVW_Q,W_K,W_V are learned projections and softmax is row-wise. Write AB=fW(X)A_B=f_W(X) and A~B=fW(X~)\widetilde A_B=f_W(\widetilde X); the full and compressed outputs are XBout=ABXWVX_B^{\mathrm{out}}=A_BXW_V and X~Bout=A~BX~WV\widetilde X_B^{\mathrm{out}}=\widetilde A_B\widetilde XW_V. If fWf_W has Lipschitz constant bounded by LL, the paper gives the Frobenius error bound ∥X~Bout−XBout∥F≤ε[1+O(L)]∥AB∥F∥X∥F∥WV∥F\|\widetilde X_B^{\mathrm{out}}-X_B^{\mathrm{out}}\|_F\leq\varepsilon[1+O(L)]\|A_B\|_F\|X\|_F\|W_V\|_F. The guarantee relates output error to feature quantization error and the sensitivity of the batch attention map.

  6. Knowl 6 — GOAT is competitive across large homophilous and heterophilous benchmarks

    empirical result

    The evaluation is transductive node classification: all nodes are visible during training, but only training nodes have labels. It uses official OGB splits for ogbn-arxiv (54% training) and ogbn-products (8%); for arxiv-year and snap-patents it uses random splits with 10%, 20%, or 50% training data and a fixed 25% validation set. The respective edge-homophily ratios are 0.66, 0.81, 0.222, and 0.073. GOAT uses one attention layer, codebook size 4,096, compressed dimension 64, dropout 0.5, batch normalization, and Adam with learning rate 10−310^{-3}; head counts and hidden channels are arxiv 4/128, products 2/256, arxiv-year 4/128, and patents 2/128. Each GOAT result is averaged over four runs. The entries below are test accuracies in percent, shown as mean ± reported error bar, for GCNJK, GAT, LINKX, MixHop, and GOAT, respectively; GPS ran out of memory on every dataset.

    • ogbn-arxiv: 69.57 ± 0.20, 71.95 ± 0.36, 66.18 ± 0.33, 71.29 ± 0.29, 72.41 ± 0.40.
    • ogbn-products: 72.84 ± 0.36, 79.45 ± 0.59, 71.59 ± 0.71, 73.48 ± 0.29, 82.00 ± 0.43.
    • arxiv-year, 10% training: 43.34 ± 0.08, 38.34 ± 0.10, 46.22 ± 0.24, 45.13 ± 0.25, 49.44 ± 0.11; 20%: 44.77 ± 0.10, 39.19 ± 0.12, 49.16 ± 0.42, 47.18 ± 0.24, 51.21 ± 0.44; 50%: 47.74 ± 0.23, 40.27 ± 0.20, 53.53 ± 0.36, 50.37 ± 0.25, 53.57 ± 0.18.
    • snap-patents, 10% training: 32.50 ± 0.10, 32.72 ± 0.10, 49.74 ± 0.46, 33.57 ± 0.06, 44.31 ± 0.43; 20%: 32.97 ± 0.06, 32.96 ± 0.09, 54.32 ± 0.50, 33.96 ± 0.06, 49.55 ± 0.31; 50%: 33.52 ± 0.05, 33.10 ± 0.09, 60.12 ± 0.23, 34.28 ± 0.07, 54.97 ± 0.23.

    GOAT leads on both homophilous datasets and on arxiv-year at 10% and 20% training; at 50% on arxiv-year its score is 0.04 points above LINKX. LINKX leads on snap-patents at all three training ratios. The paper reports overall performance averages of 64 for GOAT and 61 for LINKX, so the results support cross-regime competitiveness, not universal dataset-by-dataset superiority. The 50%-training MixHop result on snap-patents uses GraphSAINT sampling; the GAT ogbn-products entry is taken from the OGB leaderboard because the authors’ mini-batch SAINT result was substantially lower.

  7. Knowl 7 — The global-only variant is much faster per epoch than neighborhood-sampled baselines

    empirical result

    The paper compares epoch times for GAT with neighbor sampling, GOAT with both global and local modules, and GOAT-G, the global-only GOAT variant. Times are seconds per epoch on ogbn-arxiv and ogbn-products; the batch sizes are 1,000 and 4,000.

    • Batch 1,000: GAT takes 9.76 s on ogbn-arxiv and 127.42 s on ogbn-products; GOAT-G takes 2.88 s and 5.58 s; full GOAT takes 8.00 s and 109.51 s.
    • Batch 4,000: GAT takes 8.31 s and 113.47 s; GOAT-G takes 2.33 s and 4.36 s; full GOAT takes 7.62 s and 101.73 s.

    Thus, compressed global attention alone is substantially faster per epoch than GAT on these graphs, especially ogbn-products. Adding the local module makes full GOAT’s epoch time comparable to GAT’s, consistent with the paper’s finding that local neighbor sampling—not the approximate global module—is the main efficiency bottleneck.

  8. Knowl 8 — Local-attention ablations show gains from longer-range neighborhoods

    empirical result

    The paper compares GOAT variants whose local module attends to sampled neighborhoods of different maximum hop ranges. The reported accuracy scores for 1-, 2-, and 3-hop variants are, respectively: ogbn-arxiv, 71.23, 72.26, and 72.41; arxiv-year with 50% training data, 50.18, 52.06, and 53.57; ogbn-products, 78.18, 78.74, and 82.00; and snap-patents with 50% training data, 47.47, 49.44, and 54.97. Accuracy rises with the evaluated hop range on all four datasets, with the largest 1-to-3-hop increase on snap-patents. In a separate local-only comparison, the paper reports that the global module adds about 3 percentage points on arxiv-year, while local-only is about as strong as full GOAT on homophilous ogbn-arxiv.

  9. Knowl 9 — Increasing the codebook size improves the reported attention-model scores

    empirical result

    The codebook-size ablation varies the number of K-means centroids while holding the rest of the evaluated model configuration fixed. At sizes 512, 1,000, 2,000, and 4,000, the reported scores are 71.92, 71.99, 72.14, and 72.41 on ogbn-arxiv, and 50.90, 51.21, 52.51, and 53.57 on arxiv-year. The larger codebook corresponds to better scores at each tested size on both datasets; arxiv-year is more sensitive, improving by 2.67 points from 512 to 4,000, compared with 0.49 points on ogbn-arxiv. The main experiments therefore use 4,096 codebook entries.

  10. Knowl 10 — Neighbor sampling and model depth remain scalability limitations

    limitation

    GOAT’s local module inherits the neighborhood-explosion cost of neighbor sampling: for an ll-hop neighborhood and average graph degree dd, the paper describes the cost as O(dl)O(d^l). The authors identify this sampling step as the primary efficiency bottleneck when local attention is enabled; the global-only variant avoids that cost. The evaluated GOAT model has one attention layer. Deeper attention is difficult because the sampled neighbors and codebook nodes provide inputs to the target node but are not updated to the same feature state as that target. A proposed straightforward extension—recursively sampling neighbors and adding codebooks at each layer—would increase overhead, and the paper does not evaluate it.

Coverage note — The supplementary Johnson–Lindenstrauss proposition and theorem proofs are omitted as proof machinery supporting the included approximation guarantees; baseline-only hyperparameter-sweep details are omitted because they do not add a separate GOAT contribution.

References

  1. 1.Abu-El-Haija, S., Perozzi, B., Kapoor, A., Alipourfard, N., Lerman, K., Harutyunyan, H., Ver Steeg, G., and Galstyan, A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pp. 21–29. PMLR, 2019.
  2. 2.Beltagy, I., Peters, M. E., and Cohan, A. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05150, 2020.
  3. 3.Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., and Hsieh, C.-J. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 257–266, 2019.
  4. 4.Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
  5. 5.Chien, E., Chang, W.-C., Hsieh, C.-J., Yu, H.-F., Zhang, J., Milenkovic, O., and Dhillon, I. S. Node feature extraction by self-supervised multi-scale neighborhood prediction. arXiv preprint arXiv:2111.00064, 2021.
  6. 6.Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., Kaiser, L., et al. Rethinking attention with performers. arXiv preprint arXiv:2009.14794, 2020.
  7. 7.Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
  8. 8.Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
  9. 9.Dwivedi, V. P. and Bresson, X. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
  10. 10.Dwivedi, V. P., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875, 2021.
  11. 11.Fey, M., Lenssen, J. E., Weichert, F., and Leskovec, J. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. In International Conference on Machine Learning, pp. 3294–3304. PMLR, 2021.
  12. 12.Geisler, S., Schmidt, T., S¸irin, H., Zugner, D., Bojchevski, A., and Gunnemann, S. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 34, 2021.
  13. 13.Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263–1272. PMLR, 2017.
  14. 14.Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855–864, 2016.
  15. 15.Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
  16. 16.Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118–22133, 2020a.
  17. 17.Hu, Z., Dong, Y., Wang, K., and Sun, Y. Heterogeneous graph transformer. In Proceedings of The Web Conference 2020, pp. 2704–2710, 2020b.
  18. 18.Huang, Q., He, H., Singh, A., Lim, S.-N., and Benson, A. R. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010.13993, 2020.
  19. 19.Huang, W., Zhang, T., Rong, Y., and Huang, J. Adaptive sampling towards fast graph representation learning. Advances in neural information processing systems, 31, 2018.
  20. 20.Hussain, M. S., Zaki, M. J., and Subramanian, D. Edge-augmented graph transformers: Global self-attention is enough for graphs. arXiv preprint arXiv:2108.03348, 2021.
  21. 21.Johnson, W. B. and Lindenstrauss, J. Extensions of lipschitz mappings into a hilbert space 26. Contemporary mathematics, 26:28, 1984.
  22. 22.Kane, D. M. and Nelson, J. Sparser johnson-lindenstrauss transforms. Journal of the ACM (JACM), 61(1):1–23, 2014.
  23. 23.Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
  24. 24.Kitaev, N., Kaiser, Ł., and Levskaya, A. Reformer: The efficient transformer. arXiv preprint arXiv:2001.04451, 2020.
  25. 25.Kong, K., Li, G., Ding, M., Wu, Z., Zhu, C., Ghanem, B., Taylor, G., and Goldstein, T. Flag: Adversarial data augmentation for graph neural networks. arXiv preprint arXiv:2010.09891, 2020.
  26. 26.Kreuzer, D., Beaini, D., Hamilton, W., Letourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34, 2021.
  27. 27.Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., and Lim, S. N. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 2021.
  28. 28.Liu, M., Wang, Z., and Ji, S. Non-local graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
  29. 29.Maziarka, L., Majchrowski, D., Danel, T., Gainski, P., Tabor, J., Podolak, I., Morkisz, P., and Jastrzebski, S. Relative molecule self-attention transformer. arXiv preprint arXiv:2110.05841, 2021.
  30. 30.McPherson, M., Smith-Lovin, L., and Cook, J. M. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415–444, 2001.
  31. 31.Mialon, G., Chen, D., Selosse, M., and Mairal, J. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.05667, 2021.
  32. 32.Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
  33. 33.Rampa´sek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scalable graph transformer. arXiv preprint arXiv:2205.12454, 2022.
  34. 34.Rong, Y., Bian, Y., Xu, T., Xie, W., Wei, Y., Huang, W., and Huang, J. Self-supervised graph transformer on large-scale molecular data. Advances in Neural Information Processing Systems, 33:12559–12571, 2020.
  35. 35.Shi, Y., Huang, Z., Feng, S., Zhong, H., Wang, W., and Sun, Y. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03509, 2020.
  36. 36.Tay, Y., Bahri, D., Yang, L., Metzler, D., and Juan, D.-C. Sparse sinkhorn attention. In International Conference on Machine Learning, pp. 9438–9447. PMLR, 2020.
  37. 37.Tay, Y., Bahri, D., Metzler, D., Juan, D.-C., Zhao, Z., and Zheng, C. Synthesizer: Rethinking self-attention for transformer models. In International Conference on Machine Learning, pp. 10183–10192. PMLR, 2021.
  38. 38.Van Den Oord, A., Vinyals, O., et al. Neural discrete representation learning. Advances in neural information processing systems, 30, 2017.
  39. 39.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017.
  40. 40.Velickovi ˇ c, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.
  41. 41.Wang, S., Li, B. Z., Khabsa, M., Fang, H., and Ma, H. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006.04768, 2020.
  42. 42.Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.-i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. In Dy, J. and Krause, A. (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5453–5462. PMLR, 10–15 Jul 2018. URL https://proceedings.mlr.press/v80/xu18c.html.
  43. 43.Ying, C., Cai, T., Luo, S., Zheng, S., Ke, G., He, D., Shen, Y., and Liu, T.-Y. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34, 2021.
  44. 44.Zaheer, M., Guruganesh, G., Dubey, K. A., Ainslie, J., Alberti, C., Ontanon, S., Pham, P., Ravula, A., Wang, Q., Yang, L., et al. Big bird: Transformers for longer sequences. Advances in Neural Information Processing Systems, 33:17283–17297, 2020.
  45. 45.Zeng, H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931, 2019.
  46. 46.Zhang, J., Zhang, H., Xia, C., and Sun, L. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
  47. 47.Zhao, J., Li, C., Wen, Q., Wang, Y., Liu, Y., Sun, H., Xie, X., and Ye, Y. Gophormer: Ego-graph transformer for node classification. arXiv preprint arXiv:2110.13094, 2021.
  48. 48.Zhu, C., Ping, W., Xiao, C., Shoeybi, M., Goldstein, T., Anandkumar, A., and Catanzaro, B. Long-short transformer: Efficient transformers for language and vision. Advances in Neural Information Processing Systems, 34, 2021.
  49. 49.Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793–7804, 2020.

Citation

MLA
Kong, K., et al. “GOAT: A Global Transformer on Large-scale Graphs”. International Conference on Machine Learning, vol. 202, 2023, pp. 17375–90, https://proceedings.mlr.press/v202/kong23a.html.
APA
Kong, K., Chen, J., Kirchenbauer, J., Ni, R., Bruss, C. B., & Goldstein, T. (2023). GOAT: A Global Transformer on Large-scale Graphs. International Conference on Machine Learning, 202, 17375–17390. https://proceedings.mlr.press/v202/kong23a.html
Chicago
Kong, K., J. Chen, J. Kirchenbauer, R. Ni, C. B. Bruss, and T. Goldstein. 2023. “GOAT: A Global Transformer on Large-scale Graphs”. International Conference on Machine Learning 202: 17375–90. https://proceedings.mlr.press/v202/kong23a.html.
Harvard
Kong, K. et al. (2023) “GOAT: A Global Transformer on Large-scale Graphs”, International Conference on Machine Learning. PMLR, pp. 17375–17390. Available at: https://proceedings.mlr.press/v202/kong23a.html.
Vancouver
1. Kong K, Chen J, Kirchenbauer J, Ni R, Bruss CB, Goldstein T (2023) GOAT: A Global Transformer on Large-scale Graphs. In: International Conference on Machine Learning. PMLR, pp 17375–17390

BibTeX

@InProceedings{pmlr-v202-kong23a,
  title = 	 {{GOAT}: A Global Transformer on Large-scale Graphs},
  author =       {Kong, Kezhi and Chen, Jiuhai and Kirchenbauer, John and Ni, Renkun and Bruss, C. Bayan and Goldstein, Tom},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {17375--17390},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/kong23a/kong23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/kong23a.html},
  abstract = 	 {Graph transformers have been competitive on graph classification tasks, but they fail to outperform Graph Neural Networks (GNNs) on node classification, which is a common task performed on large-scale graphs for industrial applications. Meanwhile, existing GNN architectures are limited in their ability to perform equally well on both homophilious and heterophilious graphs as their inductive biases are generally tailored to only one setting. To address these issues, we propose GOAT, a scalable global graph transformer. In GOAT, each node conceptually attends to all the nodes in the graph and homophily/heterophily relationships can be learnt adaptively from the data. We provide theoretical justification for our approximate global self-attention scheme, and show it to be scalable to large-scale graphs. We demonstrate the competitiveness of GOAT on both heterophilious and homophilious graphs with millions of nodes.}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/