Pith. sign in

REVIEW 2 major objections 6 minor 1 cited by

Simple Path Structural Encoding for Graph Transformers

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Counting simple paths between node pairs makes graph transformers see cyclic structure that random-walk edge encodings miss.

desk verdict SPSE is a real step forward for graph transformer encodings, but the per-dataset tuning of its path-count transform contradicts the 'no hyperparameter tuning' fairness claim—so the empirical margin is not as clean as presented. read the letter →

arxiv 2502.09365 v2 pith:ZDNZXZ7Z submitted 2025-02-13 cs.LG cs.AI

Louis Airale , Antonio Longa , Mattia Rigon , Andrea Passerini , Roberto Passerone This is my paper · ORCID
classification cs.LGcs.AI MSC 05C3805C3068T07
keywords graphtransformersstructuraledgeencodingsimplepathcountingrandomwalkcycleself-attentionDAGdecompositionneuralnetworks
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

This paper proposes replacing the random-walk structural encoding (RWSE) used in graph transformers with counts of simple paths between every pair of nodes, calling the result Simple Path Structural Encoding (SPSE). The theoretical core is that, for an edge, the number of length-k simple paths equals the number of (k+1)-cycles containing that edge, giving the encoding provably richer information about local cyclic structure than random-walk probabilities, which the paper shows are ambiguous across even-cycle and path graphs. Because exact simple-path counting is intractable at scale, the paper introduces an approximate algorithm that decomposes the graph into DAGs via combined DFS/BFS node orderings and keeps the maximum count found over decompositions. In benchmark tests across molecular, superpixel and stochastic-block-model datasets, swapping RWSE for SPSE in GRIT, CSA and GPS improves results in most settings while leaving the number of trainable parameters unchanged. If the approximation stays informative, SPSE offers a drop-in edge encoding that strengthens structural expressivity without architectural change.

What carries the argument

The central object is the k-hop simple path matrix S_k, whose (i,j) entry counts simple paths of length k between nodes i and j; SPSE feeds log-compressed versions of S_1, ..., S_K into the edge-encoding network that previously consumed random-walk matrices. The load-bearing identity is Proposition 3: for an edge (i,j) and k ≥ 2, (S_k)_{ij} equals the number of (k+1)-cycles containing that edge, so path counts along edges act as cycle-incidence signatures. The tractability mechanism is the approximate counting algorithm: it generates DAG decompositions from combined DFS/BFS node orderings, counts paths in each DAG via powers of its strictly upper-triangular adjacency matrix, and takes an elementwise maximum over decompositions, giving lower bounds on exact counts at a preprocessing cost of O(K R D_{DFS} N |V|^3).

What would settle it

Run the SPSE counting algorithm on small graphs where exact path counts are computable, including graphs of the Figure 6 type where two paths of the same length between one node pair require a cyclic orientation to be discovered together, and compare the approximate counts to exact values: systematic undercounting in regimes where SPSE shows no gain over RWSE would break the informative-counts premise. A sharper test is to compute exact path counts on CLUSTER-style dense stochastic-block graphs where feasible and check whether restoring exactness recovers the performance gap over RWSE.

Watch

Extended reading notes

Core claim

The paper's central claim is that simple path counts form a more informative structural edge encoding for graph transformers than random walk probabilities. The authors prove (Proposition 3) that for adjacent nodes i and j, the number of length-k simple paths between them equals the number of cycles of length k+1 that contain the edge (i,j), so an edge's SPSE signature pins down the cyclic patterns it participates in, information that random walk landing probabilities are shown to lose (Propositions 1 and 2, including the indistinguishability of even-length cycles from paths under RWSE). To make this tractable, SPSE counts paths through successive DAG decompositions obtained from DFS/BFS node orderings, computing path counts as powers of the nilpotent adjacency matrix of each DAG and storing the maximum over decompositions, which yields lower bounds on true counts. Empirically, replacing RWSE with SPSE in GRIT, CSA and GPS improves performance in 21 of 24 benchmark settings, with statistically significant gains concentrated in molecular datasets (ZINC, Peptides) and superpixel benchmarks (MNIST, CIFAR10), which the paper reads as validating the cycle-counting advantage and the practical viability of the approximation.

Load-bearing premise

The approach assumes that the approximate path counts, which are lower bounds obtained by taking the maximum over DFS/BFS DAG decompositions, stay informative enough for the model to learn from; if dense graphs systematically hide paths from every acyclic decomposition, the claimed superiority over RWSE weakens.

Editorial extensions

If this is right

  • Replacing RWSE with SPSE in GRIT and CSA yields statistically significant gains on molecular benchmarks ZINC and Peptides while keeping the number of trainable parameters unchanged.
  • SPSE lets graph transformers count cycles of lengths 4 through 9 that contain a given edge, as demonstrated on the synthetic cycle-counting dataset.
  • SPSE can be computed once as a preprocessing step and cached, so the added cost is paid before training and does not affect the model's parameter count.
  • On superpixel benchmarks, SPSE improves accuracy in most configurations for both CSA and GRIT, while on the dense CLUSTER benchmark it yields no significant gain, consistent with the paper's analysis of approximation limits.
  • A reasoning analogous to the Path-WL argument indicates that an iterative node-coloring scheme on SPSE-based attention is more expressive than 1-WL, though a formal expressivity comparison between SPSE and RWSE is left open.

Reading between the lines

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

  • SPSE's cycle-incidence reading of edges could serve as a cheap inductive bias for tasks where ring or cycle counts correlate with labels, such as molecular property prediction, potentially complementing cycle-count-based graph kernels.
  • The DAG-decomposition lower-bound counting might be tightened by combining multiple decompositions per root with tie-breaking among BFS children, or by adding cycle-aware orientation heuristics; the paper's own failure case in Figure 6 points at a concrete class where no single acyclic order suffices.
  • If undercounting on dense graphs is the binding constraint, a hybrid encoding that uses exact short-path counts and approximate longer counts could preserve SPSE's cycle signal where it matters; the paper hints that trading longer path lengths for exact shorter counts might be preferable.
  • The equivalence results for RWSE suggest a testable prediction: datasets where aromatic rings or specific cycle structures drive the target label should show a larger SPSE advantage over RWSE, since SPSE provably decodes those cycles from adjacent-edge path counts.
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.

Referee Report

2 major / 6 minor

Summary. This paper proposes Simple Path Structural Encoding (SPSE), an edge-level structural encoding for graph transformers that replaces random walk structural encoding (RWSE) with counts of simple paths of lengths 1 through K between node pairs. The paper proves (Proposition 3) that for adjacent nodes the exact k-hop simple path count equals the number of (k+1)-cycles containing that edge, and it gives two results on the ambiguity of RWSE. Because exact simple-path counting is infeasible in general, the paper proposes an approximate algorithm based on randomized DFS/BFS DAG decompositions that returns lower-bound path counts, followed by a logarithmic normalization. Experiments replace RWSE with SPSE in GRIT, CSA, and GPS on eight datasets from three benchmarks and report gains in most settings, together with a synthetic cycle-counting experiment that validates Proposition 3 qualitatively.

Significance. If the comparison were clean, this would be a useful contribution: SPSE is conceptually simple and adds no trainable parameters, Proposition 3 gives an interpretable local-structure guarantee for exact counts, and the explicit failure cases in Section 5.4 make the limitations unusually honest. The approximate counting algorithm and the released implementation are also concrete assets. As written, however, the empirical superiority claim is weakened by per-dataset tuning of the encoding parameters, and the theoretical motivation applies only to exact counts, so the strength of the claims exceeds what is currently demonstrated.

major comments (2)
  1. [§5.2, Appendix A, Eq. (4)] The claim that "no hyperparameter tuning is performed" to ensure a fair comparison as a drop-in replacement is contradicted by Appendix A, where the values of α, β, and n in Eq. (4) are reported as "the values that led to the best results for each dataset" and differ across datasets in Table 2. These parameters define a per-dataset nonlinear transformation of the path counts before they enter the learned encoding network, whereas the RWSE baseline feeds raw random-walk probabilities through the same network without an equivalent tuned normalization. The empirical comparison therefore does not isolate the structural information of simple paths. Please tune an equivalent RWSE preprocessing step, fix α, β, and n a priori, or explicitly reframe the experiments as SPSE with per-dataset tuned encoding parameters; as written, the "drop-in replacement" claim is not supported.
  2. [§4.1, Algorithm 3 line 16, §5.4] The path counts used by SPSE are lower bounds obtained by taking elementwise maxima over DAG decompositions, and Section 5.4 explicitly describes a graph where two length-4 paths cannot be discovered simultaneously in any acyclic decomposition. Proposition 3 is a statement about exact simple-path counts, so the theoretical cycle-counting motivation does not directly apply to the approximate counts actually fed into the model. The paper gives no bound on the counting error, and Section 5.3 measures only the fraction of paths discovered relative to a chosen canonical configuration, not relative to the true path count. Please quantify the accuracy of the approximate counts on the benchmarks (for example, by comparing against exact counts on small graphs), or prove a lower-bound guarantee that preserves the cycle-relevant information, and discuss how undercounting may affect the reported gains.
minor comments (6)
  1. [§5.2, Table 1] The text says SPSE "improves performance in 21 out of 24 cases (underlined in Table 1)", but the table legend says underlining indicates a difference rather than an improvement, and by my count Table 1 actually shows 22 improvements (all cases except CSA-CLUSTER and GRIT-CLUSTER). Please correct the count and clarify the underline criterion.
  2. [Appendix B] The claim that an iterative node-coloring algorithm based on global attention with SPSE is more expressive than 1-WL is asserted without a proof, and the same paragraph states that a rigorous comparison of SPSE and RWSE expressivity is left to future work. Please mark the 1-WL claim as a conjecture or provide the proof.
  3. [§5.3, Figure 5] The y-axis labeled "proportion of discovered paths" is described in the text as relative to a canonical configuration rather than to the exact path count; please state this explicitly in the caption and define the canonical configuration used.
  4. [§4.2, Eq. (4)] The notation αg^n(x) + β should define g^n explicitly in the equation or immediately before it; currently the composition meaning of the superscript is given only in prose and the equation alone is ambiguous.
  5. [Algorithm 2 and Algorithm 3] Algorithm 2 uses DMAX in the loop but DMAX is not listed among the parameters or inputs, and Algorithm 3 calls SELECTROOTNODE without defining it.
  6. [§5.2] The sentence "replacing walks by path count is done at no additional cost" is misleading because it refers only to trainable parameters; Table 2 shows preprocessing times of up to 80 hours, so please rephrase to clarify that the cost is in offline preprocessing rather than in training-time parameters.

Circularity Check

1 steps flagged · score 5.0 of 10

Per-dataset tuning of SPSE's encoding function (Eq. 4) contradicts the no-tuning claim behind the RWSE comparison; theoretical claims remain independent.

  1. fitted input called prediction [Section 5.2 (Experimental Setup) and Appendix A (Path count encoding parameters α, β and n; Table 2)]
    "It is important to emphasize that no hyperparameter tuning is performed. This decision ensures a fair and unbiased comparison, isolating the contribution of SPSE as a drop-in replacement for RWSE, and demonstrating its effectiveness across different architectures without the need for task-specific adjustments. // In the absence of clear heuristics regarding the effects of parameters α, β and n of Equation (4), we report in Table 2 the values that led to the best results for each dataset."

    Section 5.2 asserts the experiments isolate SPSE as a drop-in replacement because no hyperparameter tuning is performed. Appendix A then states that the parameters (α, β, n) of the encoding function f in Eq. (4) were chosen as 'the values that led to the best results for each dataset,' and Table 2 gives different values of R, K, DDFS and N for every benchmark. These hyperparameters control the nonlinear transformation and the path-count approximation fed to the model, while RWSE probabilities enter the same architectures without an equivalent per-dataset calibrated preprocessing.

full rationale

The theoretical core of the paper is self-contained: SPSE is defined by simple-path counts (Definition 2.5), Propositions 1-3 are proved in Appendix C, and the synthetic cycle-counting experiment (Section 5.1) is a controlled test of Proposition 3. No load-bearing self-citation or imported uniqueness theorem is used. The circularity is confined to the empirical comparison: Section 5.2 states that 'no hyperparameter tuning is performed' to 'isolat[e] the contribution of SPSE as a drop-in replacement,' but Appendix A says α, β, n of Eq. (4) were selected as 'the values that led to the best results for each dataset,' and Table 2 also varies the path-counting hyperparameters R, K, DDFS, N per dataset. Since RWSE baselines are used with their released configurations and without this per-dataset calibrated preprocessing, the 21/24 improvement claim is confounded: part of the gain can be attributed to fitting the encoding function to each benchmark. The prediction 'SPSE is a better drop-in edge encoding' is therefore partly built from benchmark-specific tuning, so the comparison is partially circular, while the theoretical expressivity claims stand independently.

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

The ledger shows the paper's contribution is mostly algorithmic and empirical; no new physical entities are introduced. The main burden is the set of per-dataset hyperparameters and the unproven assumption that approximate lower-bound path counts remain discriminative. The standard DAG path-counting fact is background. The expressivity transfer from Path-WL is stated but not proven.

free parameters (7)
  • alpha (Equation 4 scaling) = 0.2 or 0.5 per dataset (Table 2)
    Scales the log-composed path count encoding; Appendix A says values were chosen as those that led to the best results for each dataset.
  • beta (Equation 4 shift) = 0 (ZINC, PCQM4Mv2) or -0.2 (others)
    Vertical shift of the normalized path count; selected per dataset to optimize benchmark results.
  • n (Equation 4 iteration count) = 1, 2, or 3 per dataset
    Number of repeated log(1+x) compressions; Appendix A treats it as tuned per dataset to compress dynamic range.
  • R (root node proportion) = 40%, 55%, or 100% per dataset
    Controls the fraction of nodes used as roots for DAG decompositions; chosen by hyperparameter search, higher R costs more time.
  • DDFS (maximum DFS depth) = 2 to 11 per dataset
    Controls how many DFS steps precede BFS in path mining; affects which paths can be discovered.
  • N (number of trials) = 1 to 7 per dataset
    Number of random orderings per root; higher N discovers more paths at greater computational cost.
  • K (maximum path length) = 15 to 23 per dataset
    Truncation of the path-count signature; sets the structural scope of the encoding and is fixed to the walk length used by the RWSE baseline.
assumptions (4)
  • domain assumption Path counts computed as maximum over sampled DAG decompositions are informative lower bounds for the downstream learning task.
    Algorithm 3 line 16 stores maxima over DAGs; no formal guarantee that lower bounds preserve enough structural signal. Section 5.4 acknowledges failure cases.
  • domain assumption A Path-WL style expressivity argument extends to global self-attention with SPSE.
    Appendix B states a reasoning similar to the one followed for Path-WL can be used without giving the proof, so expressivity beyond 1-WL is assumed rather than demonstrated.
  • standard math Adjacency matrix powers on a DAG orientation count all simple paths compatible with that ordering.
    Used in Algorithm 3 and is a standard fact about DAGs; each directed path corresponds to a simple path in the original undirected graph.
  • domain assumption Random walk transition probabilities fully characterize the encoding equivalence in Propositions 1 and 2.
    The propositions compare the full infinite sequence of walk probabilities, while the implemented RWSE and SPSE truncate at finite K; the separation results therefore apply exactly only in the infinite limit.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Simple Path Structural Encoding for Graph Transformers." pith.science (2026). https://pith.science/paper/ZDNZXZ7Z

@misc{pith2026250209365,
  author       = {Pith},
  title        = {Pith review of: Simple Path Structural Encoding for Graph Transformers},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZDNZXZ7Z}},
  note         = {Machine review of arXiv:2502.09365}
}
read the original abstract

Graph transformers extend global self-attention to graph-structured data, achieving notable success in graph learning. Recently, random walk structural encoding (RWSE) has been found to further enhance their predictive power by encoding both structural and positional information into the edge representation. However, RWSE cannot always distinguish between edges that belong to different local graph patterns, which reduces its ability to capture the full structural complexity of graphs. This work introduces Simple Path Structural Encoding (SPSE), a novel method that utilizes simple path counts for edge encoding. We show theoretically and experimentally that SPSE overcomes the limitations of RWSE, providing a richer representation of graph structures, particularly for capturing local cyclic patterns. To make SPSE computationally tractable, we propose an efficient approximate algorithm for simple path counting. SPSE demonstrates significant performance improvements over RWSE on various benchmarks, including molecular and long-range graph datasets, achieving statistically significant gains in discriminative tasks. These results pose SPSE as a powerful edge encoding alternative for enhancing the expressivity of graph transformers.

Figures

Figures reproduced from arXiv: 2502.09365 by the authors.

Figure 1
Figure 1. RWSE encodes identically edges from very distinct graphs which are separated by SPSE (see the tree decomposi￾tions in Appendix D) cases of the following result which links RWSE edge en￾codings in even-length cycle graphs and linear graphs (all proofs can be found in Appendix C): Proposition 1. Let G = (V, E) be an even-length cycle graph, i.e. |V| = 2n for some n ∈ N ∗ , and G ′ = (V ′ , E ′ ) a path graph such that… view at source ↗
Figure 2
Figure 2. SPSE edge encoding of adjacent nodes characterizes the cycles to which the edge belongs. Thus bonds in the 6-atom cycles of (A) and (B) are encoded identically (they both belong to a single such cycle), and so are the (C=O) bonds of (C) and (D). Algorithm 1 Count paths between all pairs of nodes (sim￾plified) 1: Parameters: Proportion of root nodes R, maximum length K, maximum DFS depth DDFS, maximum trial number N … view at source ↗
Figure 3
Figure 3. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Cycle counting accuracies for three training configura￾tions of CSA and GRIT with either RWSE or SPSE edge encoding. 5.2. Real-World Benchmarks Datasets. We conduct experiments on graph datasets from three distinct benchmarks, covering both node- and graph￾level tasks.…
Figure 5
Figure 5. Figure 5: Proportion of discovered paths and computation time per sample when varying one hyperparameter at a time, across ZINC, PATTERN, and MNIST datasets. Solid lines (left y-axis) represent the proportion of discovered paths, while dashed lines (right y-axis) indicate comput…
Figure 6
Figure 6. Figure 6: Discovering simultaneously the two paths of length 4 between nodes 0 and 1 requires the directed graph decomposition on the right, which violates the acyclic property. 6. Related Work Graph Transformers. Graph transformers are a class of models designed to process grap…
Figure 7
Figure 7. Figure 7: Tree decompositions for the graphs in [PITH_FULL_IMAGE:figures/full_fig_p016_7.png]
Figure 8
Figure 8. Figure 8: Examples of synthetic graphs generated for the cycle counting experiment [PITH_FULL_IMAGE:figures/full_fig_p017_8.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction

    cs.LG 2025-07 reject novelty 6.0 of 10

    SP4LP encodes a candidate link by feeding the GNN embeddings of nodes on the shortest path between its endpoints into a sequence model, and claims provable expressiveness gains over prior GNN link predictors.

Reference graph

Works this paper leans on

55 extracted references · 41 canonical work pages · cited by 1 Pith paper

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Aromatic cycles are widespread in cold clouds

    Ag \'u ndez, M., Marcelino, N., Tercero, B., and Cernicharo, J. Aromatic cycles are widespread in cold clouds. Astronomy & Astrophysics, 677: 0 L13, 2023

    work page 2023

  3. [3]

    Finding and counting given length cycles

    Alon, N., Yuster, R., and Zwick, U. Finding and counting given length cycles. Algorithmica, 17 0 (3): 0 209--223, 1997

    work page 1997

  4. [4]

    and Yahav, E

    Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021

    2021

  5. [5]

    Specformer: Spectral graph neural networks meet transformers

    Bo, D., Shi, C., Wang, L., and Liao, R. Specformer: Spectral graph neural networks meet transformers. In International Conference on Learning Representations. OpenReview.net, 2023

    work page 2023

  6. [6]

    D., Chamberlain, B

    Bodnar, C., Giovanni, F. D., Chamberlain, B. P., Lio, P., and Bronstein, M. M. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNN s. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022

    work page 2022

  7. [7]

    and Laurent, T

    Bresson, X. and Laurent, T. Residual gated graph convnets. arXiv preprint arXiv:1711.07553, 2017

    arXiv 2017

  8. [8]

    Graph positional and structural encoder

    Cant\" u rk, S., Liu, R., Lapointe-Gagn\' e , O., L\' e tourneau, V., Wolf, G., Beaini, D., and Ramp\' a s ek, L. Graph positional and structural encoder. In International Conference on Machine Learning, pp.\ 5533--5566. PMLR, 2024

    work page 2024

Show all 55 references
  1. [9]

    Structure-aware transformer for graph representation learning

    Chen, D., O’Bray, L., and Borgwardt, K. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pp.\ 3469--3489. PMLR, 2022

    2022

  2. [10]

    Graph propagation transformer for graph representation learning

    Chen, Z., Tan, H., Wang, T., Shen, T., Lu, T., Peng, Q., Cheng, C., and Qi, Y. Graph propagation transformer for graph representation learning. In International Joint Conference on Artificial Intelligence, pp.\ 3559--3567. ijcai.org, 2023

    2023

  3. [11]

    Y., Park, S

    Choi, Y. Y., Park, S. W., Lee, M., and Woo, Y. Topology-informed graph transformer. arXiv preprint arXiv:2402.02005, 2024

    2024

  4. [12]

    and Bhavani, S

    Dhilber, M. and Bhavani, S. D. Community detection in social networks using deep learning. In Distributed Computing and Internet Technology: 16th International Conference, ICDCIT 2020, Bhubaneswar, India, January 9--12, 2020, Proceedings 16, pp.\ 241--250. Springer, 2020

    2020

  5. [13]

    Pace: A parallelizable computation encoder for directed acyclic graphs

    Dong, Z., Zhang, M., Li, F., and Chen, Y. Pace: A parallelizable computation encoder for directed acyclic graphs. In International Conference on Machine Learning, pp.\ 5360--5377. PMLR, 2022

    2022

  6. [14]

    An image is worth 16x16 words: Transformers for image recognition at scale

    Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on...

    2021

  7. [15]

    and Li \`o , P

    Duta, I. and Li \`o , P. Sphinx: Structural prediction using hypergraph inference network. arXiv preprint arXiv:2410.03208, 2024

    2024 arXiv

  8. [16]

    Dwivedi, V. P. and Bresson, X. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020

    2012 arXiv

  9. [17]

    P., Ramp \'a s ek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A

    Dwivedi, V. P., Ramp \'a s ek, L., Galkin, M., Parviz, A., Wolf, G., Luu, A. T., and Beaini, D. Long range graph benchmark. Advances in Neural Information Processing Systems, 35: 0 22326--22340, 2022

    2022

  10. [18]

    P., Joshi, C

    Dwivedi, V. P., Joshi, C. K., Luu, A. T., Laurent, T., Bengio, Y., and Bresson, X. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 0 (43): 0 1--48, 2023

    2023

  11. [19]

    Meta-path learning for multi-relational graph neural networks

    Ferrini, F., Longa, A., Passerini, A., and Jaeger, M. Meta-path learning for multi-relational graph neural networks. In Learning on Graphs Conference, pp.\ 2--1. PMLR, 2024

    2024

  12. [20]

    and Grohe, M

    Flum, J. and Grohe, M. The parameterized complexity of counting problems. SIAM Journal on Computing, 33 0 (4): 0 892--922, 2004

    2004

  13. [21]

    Giscard, P.-L., Kriege, N., and Wilson, R. C. A general purpose algorithm for counting simple cycles and simple paths of any length. Algorithmica, 81: 0 2716--2737, 2019

    2019

  14. [22]

    The expressive power of path-based graph neural networks

    Graziani, C., Drucks, T., Jogl, F., Bianchini, M., franco scarselli, and G \"a rtner, T. The expressive power of path-based graph neural networks. In Forty-first International Conference on Machine Learning, 2024

    2024

  15. [23]

    M., and Di Giovanni, F

    Gutteridge, B., Dong, X., Bronstein, M. M., and Di Giovanni, F. Drew: Dynamically rewired message passing with delay. In International Conference on Machine Learning, pp.\ 12252--12267. PMLR, 2023

    2023

  16. [24]

    A generalization of vit/mlp-mixer to graphs

    He, X., Hooi, B., Laurent, T., Perold, A., LeCun, Y., and Bresson, X. A generalization of vit/mlp-mixer to graphs. In International conference on machine learning, pp.\ 12724--12745. PMLR, 2023

    2023

  17. [25]

    The art of electronics, volume 2

    Horowitz, P., Hill, W., and Robinson, I. The art of electronics, volume 2. Cambridge university press Cambridge, 1989

    1989

  18. [26]

    Ogb-lsc: A large-scale challenge for machine learning on graphs

    Hu, W., Fey, M., Ren, H., Nakata, M., Dong, Y., and Leskovec, J. Ogb-lsc: A large-scale challenge for machine learning on graphs. In Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks 1, NeurIPS Datasets and Benchmarks, 2021

    2021

  19. [27]

    S., Zaki, M

    Hussain, M. S., Zaki, M. J., and Subramanian, D. Global self-attention as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.\ 655--665, 2022

    2022

  20. [28]

    Flowerformer: Empowering neural architecture encoding using a flow-aware graph transformer

    Hwang, D., Kim, H., Kim, S., and Shin, K. Flowerformer: Empowering neural architecture encoding using a flow-aware graph transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.\ 6128--6137, 2024

    2024

  21. [29]

    Johnson, D. B. Finding all the elementary circuits of a directed graph. SIAM Journal on Computing, 4 0 (1): 0 77--84, 1975

    1975

  22. [30]

    Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations. OpenReview.net, 2017

    2017

  23. [31]

    Rethinking graph transformers with spectral attention

    Kreuzer, D., Beaini, D., Hamilton, W., L \'e tourneau, V., and Tossou, P. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34: 0 21618--21629, 2021

    2021

  24. [32]

    A simple and expressive graph neural network based method for structural link representation

    Lachi, V., Ferrini, F., Longa, A., Lepri, B., and Passerini, A. A simple and expressive graph neural network based method for structural link representation. In ICML 2024 Workshop on Geometry-grounded Representation Learning and Generative Modeling, 2024

    2024

  25. [33]

    Enhancing graph transformers with hierarchical distance structural encoding

    Luo, Y., Li, H., Shi, L., and Wu, X.-M. Enhancing graph transformers with hierarchical distance structural encoding. Advances in Neural Information Processing Systems, 2024 a

    2024

  26. [34]

    Transformers over directed acyclic graphs

    Luo, Y., Thost, V., and Shi, L. Transformers over directed acyclic graphs. Advances in Neural Information Processing Systems, 36, 2024 b

    2024

  27. [35]

    K., Coates, M., Torr, P., and Lim, S.-N

    Ma, L., Lin, C., Lim, D., Romero-Soriano, A., Dokania, P. K., Coates, M., Torr, P., and Lim, S.-N. Graph inductive biases in transformers without message passing. In International Conference on Machine Learning, pp.\ 23321--23337. PMLR, 2023

    2023

  28. [36]

    May, J. W. and Steinbeck, C. Efficient ring perception for the chemistry development kit. Journal of Cheminformatics, 6: 0 1--12, 2014

    2014

  29. [37]

    Self-attention in colors: Another take on encoding graph structure in transformers

    Menegaux, R., Jehanno, E., Selosse, M., and Mairal, J. Self-attention in colors: Another take on encoding graph structure in transformers. Trans. Mach. Learn. Res., 2023

    2023

  30. [38]

    Graphit: Encoding graph structure in transformers

    Mialon, G., Chen, D., Selosse, M., and Mairal, J. Graphit: Encoding graph structure in transformers. arXiv preprint arXiv:2106.05667, 2021

    2021 arXiv

  31. [39]

    F., and Vazirgiannis, M

    Michel, G., Nikolentzos, G., Lutzeyer, J. F., and Vazirgiannis, M. Path neural networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning, pp.\ 24737--24755. PMLR, 2023

    2023

  32. [40]

    and Rousseau, R

    Otte, E. and Rousseau, R. Social network analysis: a powerful strategy, also for the information sciences. Journal of information Science, 28 0 (6): 0 441--453, 2002

    2002

  33. [41]

    and Voropaev, A

    Perepechko, S. and Voropaev, A. The number of fixed length cycles in an undirected graph. explicit formulae in case of small lengths. Mathematical Modeling and Computational Physics (MMCP2009), 148, 2009

    2009

  34. [42]

    A., Nothias, L.-F., Vining, O., Meehan, M., Esquenazi, E., and Dorrestein, P

    Quinn, R. A., Nothias, L.-F., Vining, O., Meehan, M., Esquenazi, E., and Dorrestein, P. C. Molecular networking as a drug discovery, drug metabolism, and precision medicine strategy. Trends in pharmacological sciences, 38 0 (2): 0 143--154, 2017

    2017

  35. [43]

    Defining and identifying communities in networks

    Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., and Parisi, D. Defining and identifying communities in networks. Proceedings of the national academy of sciences, 101 0 (9): 0 2658--2663, 2004

    2004

  36. [44]

    Citation networks

    Radicchi, F., Fortunato, S., and Vespignani, A. Citation networks. Models of science dynamics: Encounters between complexity theory and information sciences, pp.\ 233--257, 2011

    2011

  37. [45]

    P., Luu, A

    Ramp \'a s ek, L., Galkin, M., Dwivedi, V. P., Luu, A. T., Wolf, G., and Beaini, D. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35: 0 14501--14515, 2022

    2022

  38. [46]

    J., and Sinop, A

    Shirzad, H., Velingker, A., Venkatachalam, B., Sutherland, D. J., and Sinop, A. K. Exphormer: Sparse transformers for graphs. In International Conference on Machine Learning, pp.\ 31613--31632. PMLR, 2023

    2023

  39. [47]

    D., Chamberlain, B

    Topping, J., Giovanni, F. D., Chamberlain, B. P., Dong, X., and Bronstein, M. M. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022

    2022

  40. [48]

    and Williams, R

    Vassilevska, V. and Williams, R. Finding, minimizing, and counting weighted subgraphs. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp.\ 455--464, 2009

    2009

  41. [49]

    Attention is all you need

    Vaswani, A. Attention is all you need. Advances in Neural Information Processing Systems, 2017

    2017

  42. [50]

    Graph attention networks

    Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference on Learning Representations, 2018

    2018

  43. [51]

    E., and Stoica, I

    Wu, Z., Jain, P., Wright, M., Mirhoseini, A., Gonzalez, J. E., and Stoica, I. Representing long-range context for graph neural networks with global attention. Advances in Neural Information Processing Systems, 34: 0 13266--13279, 2021

    2021

  44. [52]

    How powerful are graph neural networks? In International Conference on Learning Representations, 2019

    Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019

    2019

  45. [53]

    Do transformers really perform badly for graph representation? Advances in neural information processing systems, 34: 0 28877--28888, 2021

    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: 0 28877--28888, 2021

    2021

  46. [54]

    Yun, S., Jeong, M., Kim, R., Kang, J., and Kim, H. J. Graph transformer networks. Advances in neural information processing systems, 32, 2019

    2019

  47. [55]

    From stars to subgraphs: Uplifting any gnn with local structure awareness

    Zhao, L., Jin, W., Akoglu, L., and Shah, N. From stars to subgraphs: Uplifting any gnn with local structure awareness. In International Conference on Learning Representations. OpenReview.net, 2022

    2022

Pith tools

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