Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification

Leong Hou U; Pak Lon Ip; Rongqin Chen; Shenghui Zhang; Xuekai Wei; Zhaoqi Lu; Zijie Zhou

REVIEW 5 major objections 6 minor 15 references

Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification

T0 review · 5 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A graph Transformer built from mixed walk tokens, hop tokens, and pretrained global tokens tops six homogeneous and two heterogeneous node-classification benchmarks.

desk verdict The multi-token architecture is a real engineering step forward, but the paper's own Table 1 fails to support the claimed state-of-the-art results, and the theoretical appendix needs serious correction. read the letter →

arxiv 2412.15302 v2 pith:MGJHKIEF submitted 2024-12-19 cs.LG

Zijie Zhou , Zhaoqi Lu , Xuekai Wei , Rongqin Chen , Shenghui Zhang , Pak Lon Ip , Leong Hou U This is my paper · ORCID

classification cs.LG MSC 68T0768R10

keywords graphtransformernodeclassificationtokenizationrandomwalkself-supervisedpretrainingmessagepassingserializationheterogeneousgraphs

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Tokenphormer tries to show that the tokenization scheme, not the attention mechanism, is what limits graph Transformers on node classification. It serializes the graph into walks and gives each node several token types: walk-tokens from four random-walk strategies, a global token from self-supervised pretraining on the serialized graph, and hop-tokens from decoupled message passing. These tokens are learned jointly by a standard Transformer with an attention-based readout. The paper reports state-of-the-art accuracy on six homogeneous benchmarks and best or competitive results on three heterogeneous datasets. If correct, the method makes graph Transformers more adaptable across graph types while retaining local structural information.

What carries the argument

The central object is the multi-token sequence built for each node. Graph serialization turns the graph into a graph document of walks, and graph tokenization turns those walks plus decoupled message-passing layers into tokens: one SGPM-token from self-supervised masked-token pretraining over long non-backtracking walks, three hop-tokens, and a tunable number of walk-tokens from four mixed walk types. The paper argues that the graph document's limiting walk distribution distinguishes non-isomorphic graphs, and uses Hoeffding's inequality to claim that a modest number of walks already covers most neighborhood information. The four walk types are the load-bearing mechanism for fine-grained structure, while SGPM- and hop-tokens extend coverage in length and density.

What would settle it

Hold out the test sets, fix one token budget and one walk-mix ratio for all six homogeneous datasets, then run Tokenphormer and NAGphormer with the same seeds; if Tokenphormer no longer beats NAGphormer by more than one standard deviation on most datasets, the claimed state-of-the-art advantage is not supported.

Watch

Extended reading notes

Core claim

The paper's central claim is that generating multiple fine-grained tokens per node, each capturing a different resolution of graph structure, lets a Transformer represent nodes better than either message-passing GNNs or single-token graph Transformers. Walk-tokens serialize a node's neighborhood through uniform random walks, non-backtracking random walks, a dilated neighborhood jump walk, and a non-backtracking version; the SGPM-token is learned by masked-token pretraining over a graph document of long non-backtracking walks, giving global context; and hop-tokens aggregate each k-hop neighborhood as a separate token, preserving local message-passing information. Tokenphormer feeds all these tokens into a Transformer and uses attention-based readout to weight them. Experiments comparing against 16 baselines report the best accuracy on Cora, Citeseer, Flickr, Photo, DBLP, and Pubmed, plus best results on Wisconsin and Actor among the heterogeneous sets, with the heterogeneous results obtained without SGPM-tokens.

Load-bearing premise

The load-bearing premise is that the per-dataset tuning of walk-token count, walk length, and the 25:25:25:25 walk-mix ratio was done honestly on validation data and is reproducible, since the paper reports only that these hyperparameters were tuned to the best.

Editorial extensions

If this is right

If the reported results hold, token design rather than attention becomes the main lever for graph Transformer performance on node classification.
The ablations imply that every token type contributes, and that removing walk-tokens hurts accuracy the most while removing hop-tokens hurts the least.
The mixed-walk design lets different graph families lean on different walk types, matching the observation that citation networks prefer non-jump walks while Photo benefits most from the non-backtracking neighborhood jump walk.
The expressiveness comparison predicts that, unlike hop-based token budgets, walk-token performance does not collapse as the number of tokens grows past the graph diameter.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable extension the paper leaves implicit is replacing the fixed 25:25:25:25 walk-mix ratio with a learned or dataset-adaptive mixture; the single-walk ablations show each walk type has different strengths, so an adaptive mixture might improve robustness on unseen graph families.
Because the SGPM-token is learned without labels, the global token may be especially valuable in low-label regimes; the paper reports only the standard semi-supervised splits, so this remains an open test.
The same graph serialization and multi-token construction could be carried over to link prediction or graph-level classification, since the walk and jump tokens are not inherently tied to the node-classification objective.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The multi-token graph transformer idea is genuinely new: combining four walk types, a self-supervised global token, and hop tokens in one architecture is more than the usual tweak, and the neighborhood jump walk is a sensible addition. The ablation study is thorough and shows each token type earns its place, which is the paper's strongest contribution. The authors also report standard deviations and cover a useful spread of datasets.

The problem is the central claim. The paper says it achieves state-of-the-art performance, but Table 1 undercuts that on two of six homogeneous datasets: APPNP beats Tokenphormer on Flickr (93.25 vs 92.44) and Gapformer/Gophormer beat it on DBLP (85.50/85.20 vs 85.13). So the model is not the best on those. On the datasets where it is first, the margins are small and there are no paired significance tests, so we cannot tell if those wins are real or noise. Appendix B.2 says the walk-token hyperparameters are "tune[d] ... to the best" without reporting the selected values or confirming that tuning used the validation split. That is a reproducibility gap.

The theory appendix has real errors. Lemma 2 claims graph documents distinguish non-isomorphic graphs, but the proof only establishes that the limiting distribution is proportional to degree, which is not a complete invariant; the lemma is false as stated. Equation 21 also misapplies Hoeffding's inequality: the bound should be exp(-2n eps^2), not that expression divided by n. These can be fixed or removed, but as written they are a liability.

The heterogeneous experiments are more modest than the text suggests: Tokenphormer is second on Cornell, and the paper's wording acknowledges comparability rather than dominance. That is fine, but it should be stated accurately.

Who gets value from this? Researchers working on graph tokenization who want a concrete alternative to NAGphormer and Gophormer. The architecture and ablations are worth studying, but the empirical claim needs to be revised and the appendices cleaned up. This deserves peer review because the core idea and evaluation are substantive, but it needs major revision before acceptance.

Referee Report

5 major / 6 minor

Summary. The paper proposes Tokenphormer, a graph Transformer for semi-supervised node classification. It generates three types of tokens for each node: walk-tokens from four random-walk variants (uniform, non-backtracking, neighborhood jump, and non-backtracking neighborhood jump), an SGPM-token from a BERT-style pretrained model on serialized graph documents, and hop-tokens from decoupled message-passing layers. These tokens are concatenated and processed by a Transformer with an attention-based readout. The authors claim state-of-the-art accuracy on six homogeneous and three heterogeneous benchmarks and provide theoretical appendices on graph-document expressiveness, walk coverage, token expressiveness, and complexity.

Significance. The multi-token architecture is a reasonable and potentially useful contribution to graph Transformers, and the paper has notable strengths: the code is released, results are reported with standard deviations over 10 runs, and ablation studies isolate the token types. However, the current experimental tables do not fully support the central state-of-the-art claim, the theoretical appendices contain mathematically incorrect or unsupported statements, and the hyperparameter description is too vague to reproduce the reported wins. If these issues are fixed, the paper could be a solid empirical contribution.

major comments (5)

[Table 1] The central claim that Tokenphormer 'outperforms existing state-of-the-art graph Transformers and mainstream MPNNs' is contradicted by the paper's own Table 1. On Flickr, APPNP reports 93.25 ± 0.24 versus Tokenphormer's 92.44 ± 0.35; on DBLP, Gapformer (85.50 ± 0.43) and Gophormer (85.20 ± 0.20) both exceed Tokenphormer's 85.13 ± 0.10. The table also bolds Tokenphormer on Flickr and DBLP despite these higher baseline numbers. On the datasets where Tokenphormer is first, no paired significance tests are provided, and several margins are within one standard deviation of the runner-up (e.g., Cora vs. NAGphormer, +0.64 pp). The 'state-of-the-art' wording should be softened to 'competitive' unless significance tests are added and the table formatting corrected.
[Appendix B.2] The reproducibility of the performance claim is compromised by the hyperparameter description. Appendix B.2 states only that walk length, number of walks, and the 25:25:25:25 mix ratio are 'tune[d] ... to the best' and reports no selected values for any dataset. This leaves open whether tuning was done on the validation split rather than the test set, and it makes the reported results impossible to reproduce independently. The paper should report the per-dataset configurations and confirm that test labels were not used for model selection.
[Appendix A.1, Lemma 2/3] The graph-isomorphism claim in Lemma 2 is false as stated. The proof derives that the limiting distribution of the simple random walk is the degree distribution (Eq. 14). Non-isomorphic regular graphs with the same number of vertices and the same degree have identical degree distributions, so the graph document as analyzed cannot distinguish them. The subsequent bijection argument in the proof is not a valid isomorphism test and does not rescue the lemma. I recommend removing or replacing this lemma with a more modest statement about approximate structural coverage, and removing the claim that SGPM-tokens 'capture global information' insofar as it rests on this lemma.
[Appendix A.2, Eq. (21)] Equation (21) misstates Hoeffding's inequality. For a binomial proportion, the correct bound is P(D > ε) ≤ 2 exp(−2ε²n) (or a one-sided version without the factor 2); the extra factor 1/n is not part of Hoeffding's inequality and does not follow from it. In addition, the argument bounds the sampling error for one fixed information type and does not establish a coverage guarantee over all information types. Please correct the inequality and either prove the coverage claim directly or state it as an empirical observation rather than a theorem.
[Table 2] The heterogeneous-dataset claim is also overstated. In Table 2, Tokenphormer is not the best on Cornell (Gapformer 77.57 ± 3.43 vs Tokenphormer 76.22 ± 2.13), and the results are obtained without SGPM-tokens. The conclusion that Tokenphormer 'achieves state-of-the-art performance' on heterogeneous graphs is therefore not established. The text should be revised to 'competitive' and should explicitly note the missing SGPM component in the heterogeneous experiments.

minor comments (6)

[Section 2.1] There is a typo: 'categorized nto' should be 'categorized into'.
[Appendix A.3] There is a typo: 'The the SGPM-token' should be 'The SGPM-token'.
[Main text vs Appendix A.1] The lemma numbering is inconsistent: the main text refers to 'Lemma 2' for graph documents, while Appendix A.1 labels the same statement as 'Lemma 3'.
[Figure 4] The caption and text mention a 'NAN result' for Flickr and DBLP, but the meaning of 'NAN' and the conditions under which it occurs are never explained.
[Equation (6)] Equation (6) has a formatting typo: the second line reads 'H_l^v = FFN(Norm(\hat{H}_l^v) + \hat{H}_l^v' and is missing a closing parenthesis; it should be 'FFN(Norm(\hat{H}_l^v)) + \hat{H}_l^v'.
[References] Several references have duplicated venue strings, e.g., 'arXiv: Learning, arXiv: Learning' for Brody et al. and Zhang et al., and 'International Conference on Learning Representations, International Conference on Learning Representations' for Klicpera et al. These should be cleaned up.

Circularity Check

0 steps flagged · score 2.0 of 10

The central claims are not circular; the only self-referential element is a minor, non-load-bearing citation to the authors' prior work on redundancy-free message passing.

full rationale

The paper's claimed derivation is empirical and self-contained against external baselines. The SGPM-token is produced by a separate self-supervised pretraining objective (masked-token cross-entropy, Eq. 5) on graph documents; the pretraining target is node identity/context rather than the node-classification label, so the token is a feature rather than a fitted answer. The hop-token is standard decoupled message-passing aggregation (Eq. 22: H^k = A^k X), and the walk-tokens are fixed random walks sampled before training; the learnable readout (Eqs. 7-8) and classifier are trained on the labeled train split. Tuning walk number, walk length, and the 25:25:25:25 mix ratio per dataset (Appendix B.2) is ordinary hyperparameter selection, not a parameter fitted to the test labels. The ablation study (Appendix B.3, Table 4) evaluates the contribution of each token type relative to the full model, and Tables 1-2 compare against external baselines. The single self-referential element is the citation to the authors' own (Chen et al. 2022) for the claim that non-backtracking random walks reduce redundancy in generated walk sequences; this is used only as motivation for a design choice and is not the source of the reported accuracy, so it is not load-bearing. Separate correctness concerns, such as Table 1 listing APPNP above Tokenphormer on Flickr and Gapformer above it on DBLP, and the absence of paired significance tests, affect whether the SOTA claim is established, but they are not circularity.

Assumptions & free parameters 5 free parameters · 4 assumptions · 0 invented entities

The model introduces no new physical or mathematical entities; its components are algorithmic constructs. The main free parameters are token-count and walk-generation hyperparameters tuned per dataset. Two theoretical assumptions (graph document expressiveness and walk coverage) are not rigorously proven.

free parameters (5)

number of walk-tokens (m) = not fixed; up to 140 in Fig. 4, tuned per dataset
The number of walk-tokens per node is a capacity hyperparameter that strongly affects accuracy; it is tuned on each dataset.
walk length initialization = 4 (starting point)
Walk lengths start from 4 and are tuned; walk length controls receptive field of walk-tokens.
mixed walk type ratio = 25%:25%:25%:25%
The proportion of the four walk types is set initially equal and then tuned; different datasets favor different walk types.
hop number = 3
The number of hop-tokens is fixed to 3 for all datasets, which limits local context to 3 hops.
SGPM walk length distribution = N(graph radius, 1) or N(10,1)
Walk lengths for SGPM pretraining follow a normal distribution with mean equal to the graph radius or 10; this choice is heuristic.

assumptions (4)

standard math Random walk on a connected, non-bipartite graph converges to a stationary distribution (Lemma 1).
Standard Markov chain theory, used to justify graph serialization by long walks.
ad hoc to paper Graph documents can distinguish non-isomorphic graphs (Lemma 2).
The proof in Appendix A.1 only shows the limiting distribution equals the degree distribution, which is not a complete graph invariant; the claim is used to justify the expressiveness of SGPM-tokens but is not established.
ad hoc to paper Finite random walk tokens can approximate full neighborhood information coverage.
The analysis in Appendix A.2 misapplies Hoeffding's inequality and conflates sampling deviation with coverage probability; the conclusion is not rigorously supported.
domain assumption Non-backtracking random walks mix faster and reduce redundancy.
Cited to Alon et al. 2007 and Chen et al. 2022; assumed when choosing walk types.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification." pith.science (2026). https://pith.science/paper/MGJHKIEF

@misc{pith2026241215302,
  author       = {Pith},
  title        = {Pith review of: Tokenphormer: Structure-aware Multi-token Graph Transformer for Node Classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MGJHKIEF}},
  note         = {Machine review of arXiv:2412.15302}
}

read the original abstract

Graph Neural Networks (GNNs) are widely used in graph data mining tasks. Traditional GNNs follow a message passing scheme that can effectively utilize local and structural information. However, the phenomena of over-smoothing and over-squashing limit the receptive field in message passing processes. Graph Transformers were introduced to address these issues, achieving a global receptive field but suffering from the noise of irrelevant nodes and loss of structural information. Therefore, drawing inspiration from fine-grained token-based representation learning in Natural Language Processing (NLP), we propose the Structure-aware Multi-token Graph Transformer (Tokenphormer), which generates multiple tokens to effectively capture local and structural information and explore global information at different levels of granularity. Specifically, we first introduce the walk-token generated by mixed walks consisting of four walk types to explore the graph and capture structure and contextual information flexibly. To ensure local and global information coverage, we also introduce the SGPM-token (obtained through the Self-supervised Graph Pre-train Model, SGPM) and the hop-token, extending the length and density limit of the walk-token, respectively. Finally, these expressive tokens are fed into the Transformer model to learn node representations collaboratively. Experimental results demonstrate that the capability of the proposed Tokenphormer can achieve state-of-the-art performance on node classification tasks.

Figures

Figures reproduced from arXiv: 2412.15302 by the authors.

**Figure 1.** Idea of Tokenphormer. capable of solving various graph-based tasks. Traditional GNNs follow the message passing scheme (Hamilton, Ying, and Leskovec 2017), aggregating neighboring nodes to update node representation. However, these methods are hindered by issues such as over-smoothing (Chen et al. 2020) and over-squashing (Alon and Yahav 2021). Transformer (Vaswani et al. 2017) has demonstrated remarkable perform… view at source ↗

**Figure 2.** Framework. RW refers to random walk while NJW stands for neighborhood jump walk. Tokenphormer generates [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Transition Probability of Neighborhood Jump [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Expressiveness Comparison. The grey dashed line denotes graph diameter. For Flickr and DBLP, the orange dashed [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

**Figure 6.** Figure 6: hop-token vs walk-token. SGPM-token. Appendix A.1 has demonstrated that the graph document can distinguish between different graphs, showcasing its proficiency in capturing the global information of the graph. The the SGPM-token, derived through SGPM, is critical in a…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 11 canonical work pages

[1]

If they are isomorphic, the limiting distribution of these two graphs must equal each other

Then we can get: X i (C X k wik) = 1→ C = 1P i P k wik (12) Finally, the limiting distribution of the Markov Chain is calculated: π(vi) = P k wikP i P k wik (13) Alternatively, in the scenario whereG is unweighted, i.e., the weight between two connected nodes is 1, the resulting limiting distribution of the graph document can be described as follows: π(vi...

work page 2022
[3]

Graph diameter is calculated using the method described in (Akiba, Iwata, and Kawata 2015)

Dataset Nodes Edges Classes Features Diameter Cora 2,708 5,278 7 1,433 19 Citeseer 3,327 4,522 6 3,703 28 Flickr 7,575 239,738 9 12,047 4 Photo 7,650 238,163 8 745 11 DBLP 17,716 52,864 4 1,639 34 Pubmed 19,717 44,324 3 500 18 Table 3: Statistics on datasets. Graph diameter is calculated using the method described in (Akiba, Iwata, and Kawata 2015). Basel...

work page 2015
[5]

Our experiments also verified this point: when the number of walks increased to a certain degree, the experimental results tended to be stable, and the model reached the fitting

The above analysis demonstrates that, although covering all information from the node’s neighborhood is challeng- ing, obtaining most information is still achievable through a limited number of samplings. Our experiments also verified this point: when the number of walks increased to a certain degree, the experimental results tended to be stable, and the ...

work page 2022
[13]

2023)) for these benchmark datasets

and NAGphormer (Chen et al. 2023)) for these benchmark datasets. The detailed dataset in- formation is presented in Table

work page 2023
[15]

2021), SAN (Kreuzer et al

and eight innovative graph Trans- former models, including GT (Dwivedi and Bresson 2021), Graphormer (Ying et al. 2021), SAN (Kreuzer et al. 2021), Gophormer (Zhao et al. 2021), ANS-GT (Zhang et al. 2022), GraphGPS (Ramp ´aˇsek et al. 2022), Exphormer (Shirzad et al. 2023), Gapformer (Liu et al. 2023), and NAGphormer (Chen et al. 2023). B.2 Experiment Det...

work page 2021
[21]

Let N {l1,l2,...,lk} S denotes number of sampled information types in n times sampling. It is clear that N {l1,l2,...,lk} S fol- lows a binominal distribution: N {l1,l2,...,lk} S ∼ B(n, P{l1,l2,...,lk} S ) (20) At last, according to Hoeffding’s inequality (Hoeffding 1994), we have: D{l1,l2,...,lk} S = | N {l1,l2,...,lk} S n − P {l1,l2,...,lk} S | P (D{l1,...

work page 1994
[2014]

In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)

Glove: Global Vectors for Word Representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). Radford, A.; Narasimhan, K.; Salimans, T.; Sutskever, I.; et al

work page 2014
[2015]

In Ex- perimental Algorithms: 14th International Symposium, SEA 2015, Paris, France, June 29–July 1, 2015, Proceedings 14, 56–67

An exact al- gorithm for diameters of large real directed graphs. In Ex- perimental Algorithms: 14th International Symposium, SEA 2015, Paris, France, June 29–July 1, 2015, Proceedings 14, 56–67. Springer. Alon, N.; Benjamini, I.; Lubetzky, E.; and Sodin, S

work page 2015

Show all 15 references

[2016]

Non-backtracking random walks and a weighted Ihara’s theorem.arXiv preprint arXiv:1603.05553. Kipf, T. N.; and Welling, M

arXiv
[2017]

arXiv preprint arXiv:1711.05101

Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101. Lov´asz, L

arXiv
[2019]

In Proceedings of the 2019 Con- ference of the North

BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Con- ference of the North. Dufter, P.; Schmitt, M.; and Sch ¨utze, H

2019
[2020]

arXiv preprint arXiv:2008.09864

Tackling over-smoothing for general graph convolutional networks. arXiv preprint arXiv:2008.09864. Jones, G. L

2008 arXiv
[2021]

CoRR, abs/2110.13094

Gophormer: Ego-Graph Transformer for Node Classification. CoRR, abs/2110.13094. Appendix A Theoretical Analysis of Tokenphormer In this section, we conduct various analyses to evaluate the effectiveness and expressiveness of Tokenphormer. Through these analyses, we aim to gain...

arXiv
[2022]

In Proceedings of the ACM Web Con- ference 2022, 3248–3258

Grand+: Scalable graph ran- dom neural networks. In Proceedings of the ACM Web Con- ference 2022, 3248–3258. Gilmer, J.; Schoenholz, S. S.; Riley, P. F.; Vinyals, O.; and Dahl, G. E

2022
[2023]

arXiv preprint arXiv:2312.11109

Graph transformers for large graphs. arXiv preprint arXiv:2312.11109. Feng, W.; Dong, Y .; Huang, T.; Yin, Z.; Cheng, X.; Khar- lamov, E.; and Tang, J

arXiv

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

If they are isomorphic, the limiting distribution of these two graphs must equal each other

Then we can get: X i (C X k wik) = 1→ C = 1P i P k wik (12) Finally, the limiting distribution of the Markov Chain is calculated: π(vi) = P k wikP i P k wik (13) Alternatively, in the scenario whereG is unweighted, i.e., the weight between two connected nodes is 1, the resulting limiting distribution of the graph document can be described as follows: π(vi...

work page 2022

[2] [3]

Graph diameter is calculated using the method described in (Akiba, Iwata, and Kawata 2015)

Dataset Nodes Edges Classes Features Diameter Cora 2,708 5,278 7 1,433 19 Citeseer 3,327 4,522 6 3,703 28 Flickr 7,575 239,738 9 12,047 4 Photo 7,650 238,163 8 745 11 DBLP 17,716 52,864 4 1,639 34 Pubmed 19,717 44,324 3 500 18 Table 3: Statistics on datasets. Graph diameter is calculated using the method described in (Akiba, Iwata, and Kawata 2015). Basel...

work page 2015

[3] [5]

Our experiments also verified this point: when the number of walks increased to a certain degree, the experimental results tended to be stable, and the model reached the fitting

The above analysis demonstrates that, although covering all information from the node’s neighborhood is challeng- ing, obtaining most information is still achievable through a limited number of samplings. Our experiments also verified this point: when the number of walks increased to a certain degree, the experimental results tended to be stable, and the ...

work page 2022

[4] [13]

2023)) for these benchmark datasets

and NAGphormer (Chen et al. 2023)) for these benchmark datasets. The detailed dataset in- formation is presented in Table

work page 2023

[5] [15]

2021), SAN (Kreuzer et al

and eight innovative graph Trans- former models, including GT (Dwivedi and Bresson 2021), Graphormer (Ying et al. 2021), SAN (Kreuzer et al. 2021), Gophormer (Zhao et al. 2021), ANS-GT (Zhang et al. 2022), GraphGPS (Ramp ´aˇsek et al. 2022), Exphormer (Shirzad et al. 2023), Gapformer (Liu et al. 2023), and NAGphormer (Chen et al. 2023). B.2 Experiment Det...

work page 2021

[6] [21]

Let N {l1,l2,...,lk} S denotes number of sampled information types in n times sampling. It is clear that N {l1,l2,...,lk} S fol- lows a binominal distribution: N {l1,l2,...,lk} S ∼ B(n, P{l1,l2,...,lk} S ) (20) At last, according to Hoeffding’s inequality (Hoeffding 1994), we have: D{l1,l2,...,lk} S = | N {l1,l2,...,lk} S n − P {l1,l2,...,lk} S | P (D{l1,...

work page 1994

[7] [2014]

In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)

Glove: Global Vectors for Word Representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). Radford, A.; Narasimhan, K.; Salimans, T.; Sutskever, I.; et al

work page 2014

[8] [2015]

In Ex- perimental Algorithms: 14th International Symposium, SEA 2015, Paris, France, June 29–July 1, 2015, Proceedings 14, 56–67

An exact al- gorithm for diameters of large real directed graphs. In Ex- perimental Algorithms: 14th International Symposium, SEA 2015, Paris, France, June 29–July 1, 2015, Proceedings 14, 56–67. Springer. Alon, N.; Benjamini, I.; Lubetzky, E.; and Sodin, S

work page 2015