Pith. sign in

REVIEW 4 major objections 5 minor 60 references

Chordless Structure: A Pathway to Simple and Expressive GNNs

T0 review · 4 major / 5 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 A graph neural network that reads only chordless cycles and paths claims strictly more expressive power than k-hop message passing, at polynomial cost.

desk verdict A plausible chordless-structure architecture with real experimental effort, but the central expressiveness proof is unsupported, and the one-sentence proof of Theorem 4.7 argues the wrong direction. read the letter →

arxiv 2505.19188 v1 pith:L5EVSX3T submitted 2025-05-25 cs.LG

Hongxu Pan , Shuxian Hu , Mo Zhou , Zhibin Wang , Rong Gu , Chen Tian , Kun Yang , Sheng Zhong This is my paper
classification cs.LG MSC 68T0705C3805C60
keywords graphneuralnetworkschordlesscyclespathsexpressivenessWeisfeiler-Lehmantestk-hopmessagepassingisomorphismmolecularpropertyprediction
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

The paper sets out to show that a graph neural network can gain expressive power by deliberately ignoring chords. It proposes CSGNN, which aggregates over chordless cycles and chordless paths instead of plain neighborhoods or all cycles, and argues that these chordless structures alone carry the information a graph model needs. The central theoretical result is that CSGNN is strictly more expressive than the k-hop GNN (KPGNN) with polynomial complexity. Experiments on graph isomorphism benchmarks and on molecular and social datasets are presented as evidence that this chordless inductive bias also helps in practice, with CSGNN matching or beating models that carry 3-WL-level expressiveness guarantees.

What carries the argument

The central object is the chordless structure. A chordless cycle is a cycle that has no chord, where a chord is an edge joining two nonconsecutive nodes of the cycle; a chordless path is a path with the same property. The load-bearing idea is that a cycle with a chord can be rebuilt from smaller chordless cycles and paths, so the chordless pieces act as a compact basis for the graph's cyclic structure. CSGNN uses chordless paths and cycles as aggregation neighborhoods, and the optional feature encoding turns membership in chordless cycles into a binary node feature, which the paper motivates through regular cell complexes and topological cones. Enumerating the structures costs $O(c(G)(|V|+|E|))$, where $c(G)$ is the number of chordless cycles, keeping the whole model polynomial.

What would settle it

A graph search for two non-isomorphic graphs with identical multisets of chordless cycles and identical multisets of chordless paths would refute Theorem 3.5: CSGNN sees only those structures, so it could not separate the pair, and the claimed expressiveness advantage would lose its foundation. Strongly regular graphs and other 3-WL-failing pairs are natural places to look for such a pair.

Watch

Extended reading notes

Core claim

The paper's central claim is that what limits simple message-passing GNNs is the presence of cycles, and that the informative part of a cycle is its chordless core: a cycle or path containing no edge between two nonconsecutive nodes. CSGNN enumerates all chordless cycles and chordless paths, then runs message passing over them as aggregation neighborhoods, and can also mark each node with an indicator of which chordless cycles contain it. The paper proves in Theorem 4.7 that CSGNN is more expressive than KPGNN when both are restricted to chordless paths of length at most $k$, and it gives additional separation results for color-equivalent graphs with different numbers of connected components and for cut edges. Its structural reason is Theorem 3.5: chordless cycles and chordless paths together provide enough information to describe a graph's structure, so dropping chords does not weaken the model.

Load-bearing premise

The chain of proof rests on the claim that chordless cycles and chordless paths together carry enough information to describe a graph's useful structure, so that omitting chords loses nothing.

Editorial extensions

If this is right

  • CSGNN distinguishes all 11,117 non-isomorphic graphs on eight nodes, all 600 EXP graph pairs, and the strongly regular graph pairs in the SR family, including cases that defeat 3-WL.
  • The expressiveness gain comes without the usual price: chordless structure enumeration is $O(c(G)(|V|+|E|))$, while k-GNN-style higher-order methods require at least $O(n^{k+1})$.
  • The chordless features are portable: adding them to a standard GIN model raises ROC-AUC on ogbg-MolHIV to 82.22, above the other listed baselines.
  • The chordless compression is also a memory win: CSGNN uses far less memory than exhaustive PathNN and avoids the out-of-memory failures of cycle-based CY2C-GCN on the DD dataset.

Reading between the lines

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

  • Beyond the paper's claims, if chordless cycles do encode enough structure, chordless-cycle counts could serve as a cheap polynomial-time proxy for full cycle counts in substructure-counting tasks.
  • Beyond the paper's claims, the same chordless encoding could be grafted onto other base architectures, such as graph transformers; a natural test is whether the expressiveness advantage survives attention-based aggregation.
  • Beyond the paper's claims, the formal guarantee in Theorem 4.7 is specifically against KPGNN, while the stronger-sounding 'beyond 3-WL' statement rests on empirical SR results; the two should be read at different strengths.
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

4 major / 5 minor

Summary. The manuscript proposes CSGNN, a graph neural network that augments message passing with chordless cycles and chordless paths. The main theoretical claim is Theorem 4.7: CSGNN is strictly more expressive than the k-hop GNN (KPGNN) with polynomial complexity. The paper also argues in Theorem 3.5 that chordless cycles and chordless paths suffice to describe graph structure, gives a feature encoding inspired by topological cones, and reports experiments on EXP, Graph8c, SR, ZINC, TUDataset, and ogbg-MolHIV. The abstract additionally claims that CSGNN achieves better performance than GNNs of 3-WL expressiveness.

Significance. The motivation is reasonable: chordless cycles are far fewer than all cycles, and the cited enumeration algorithm of Uno and Satoh gives polynomial complexity, so an expressiveness separation based on chordless structures could be practically useful. The paper provides code and evaluates on standard synthetic and real benchmarks, which is a strength. However, the central expressiveness proof is not present as written: Theorem 4.7's proof points to a nonexistent theorem, and the decomposition theorem relies on a weak lemma and an unproved conjecture. The manuscript therefore does not currently establish its headline theoretical claim, and the empirical results alone do not compensate for that gap.

major comments (4)
  1. [Section 4.3, Theorem 4.7] The proof of Theorem 4.7 is not a proof of strict expressiveness. It first states that CP[k] is contained in KPGNN's computational scope, which gives CP[k] ≼ KPGNN, i.e., the opposite of the direction needed to show that CSGNN is strictly more expressive. The required converse, KPGNN ≼ CSGNN, is deferred to 'theorem 3.2', but no Theorem 3.2 exists; Corollary 3.2 only says that WL-indistinguishable non-isomorphic graphs contain cycles, which does not imply that chordless paths and cycles can simulate k-hop message passing. No separating pair of graphs or preservation argument is supplied. The central claim of the paper is therefore unsupported.
  2. [Section 3.2 and Appendix E.1] Theorem 3.5, the claim that chordless cycles and chordless paths provide enough information to describe a graph, is load-bearing for the entire approach, but it is not established. Lemma 3.4's proof in Appendix E.1 handles only a path with a single chord and asserts that one chord near the middle suffices; it does not treat multiple or crossing chords, nor does it show that every path can be reconstructed from chordless segments. Theorem 3.5 also relies on the unproved Cycle Double Cover Conjecture. If chordless structures do not determine all cycles and paths, the expressiveness comparison to KPGNN collapses.
  3. [Section 4.2, Lemma 4.3] Lemma 4.3's subdivision argument does not preserve the graph isomorphism problem: adding subdivision nodes changes the graph, and the proof does not show that CSGNN's ability to distinguish the subdivided graphs transfers to the original graphs. Since the lemma is presented as a way to 'uniform the form' of graphs for the expressiveness analysis, this transfer argument is required. As written, the lemma cannot support the subsequent theoretical claims.
  4. [Section 4.3, Theorem 4.9 and Appendix E.3] The proof of Theorem 4.9 does not derive the stated result. It assumes that after removing the last layer, the graphs are trees, without justifying that the graphs have the required layered form; the case analysis does not connect color-equivalence to CSGNN's actual aggregation mechanism; and the proof references 'Lemma 3.6', which does not exist. Since Theorem 4.9 and Corollary 4.10 are offered as evidence of CSGNN's expressiveness, this is another gap in the theoretical narrative.
minor comments (5)
  1. [General] There are several broken references: the proof of Theorem 4.7 cites 'theorem 3.2' instead of Corollary 3.2, Section 4.3 cites 'Lemma 3.6' although no such lemma exists, and Table/Figure cross-references include 'Figure??' in Section 4.3 and Appendix E.2.
  2. [Section 2.2 and Section 3.1] There are typos and duplicated text: 'as knwon' appears in Section 2.2, and the sentence beginning 'We write u∈CC_k(v) if...' is repeated verbatim in Section 3.1.
  3. [Section 4.3] The notation CP[k] in Theorem 4.7 is used as though it were a GNN class, but it is not defined; the statement CP[k] ≼ KPGNN mixes a feature-set notation with the GNN class KPGNN and needs a precise definition.
  4. [Tables 2 and 3] The model is called CSGNN in the text but 'CSGIN' in Tables 2b and 3b; the naming should be made consistent.
  5. [NeurIPS Checklist] The checklist answers are not consistent with the manuscript content: the authors answer 'Yes' to 'Theory assumptions and proofs' despite the gaps described above, and 'No' to 'Limitations' even though the paper relies on an unproved conjecture and a partial decomposition lemma.

Circularity Check

1 steps flagged · score 6.0 of 10

The paper's foundational premise that chordless structures suffice is justified by a proof that assumes the same decomposition; the separate KPGNN-expressiveness theorem is a non-proof but not circular.

  1. other [Section 3.2, Lemma 3.4 and Appendix E.1; used by Theorem 3.5]
    "Lemma 3.4. With the set of chordless paths, one can find all paths in the graph. ... Proof. Given a path containing a chord, we focus on the decomposition of the subpath that includes the chord ... it suffices to select a single chord—preferably one whose endpoints are near the middle of the path—to partition it into chordless segments. This approach avoids exhaustive decomposition over all edges or chords, and is sufficient for our purposes."

    Lemma 3.4 is the load-bearing support for Theorem 3.5 ('Chordless cycles and chordless paths together provide enough information to describe the structure of a graph'). The proof asserts exactly what the lemma must establish: that a path can be recovered by partitioning it into chordless segments. It neither proves that one chosen chord yields chordless subpaths nor that the set of all chordless paths determines the original path's vertex ordering and chord endpoints. 'Sufficient for our purposes' is the conclusion, not an argument. Hence the paper's central premise that omitting chords loses no structural information is assumed in its own proof.

full rationale

The only genuinely circular step is the proof of Lemma 3.4 / Theorem 3.5: the sufficiency of chordless paths is asserted rather than derived, and Theorem 3.5 inherits this assumption. The paper's headline expressiveness theorem (Theorem 4.7) is also not supported: its proof establishes only CP[k] ≼ KPGNN (chordless paths are within KPGNN's k-hop scope) and defers the required converse to 'theorem 3.2', which does not exist as stated (Corollary 3.2 only notes that 1-WL-equivalent non-isomorphic graphs contain cycles). That is an invalid inference and a missing proof, but it is not a circular reduction in the sense of 'prediction equals input by construction', so it is weighed here rather than listed as a circular step. The experimental claims on SR, ZINC, TUDataset, and ogbg-MolHIV are external benchmarks and are not fitted-input predictions, and there is no load-bearing self-citation chain. Because the central 'chordless decomposition' premise is established by assuming itself, the overall derivation is partially circular, giving score 6 rather than a lower score. Additionally, the NeurIPS checklist says 'Answer: [No]' to Limitations while claiming limitations are discussed 'at the points where they naturally arise'; this is a consistency gap, not a circularity.

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

The central claim depends on four premises: (1) every cycle can be represented by chordless cycles/paths, justified via a conjecture; (2) Lemma 3.4 (chordless paths suffice to build all paths) with a non-rigorous proof; (3) any graph can be transformed to a 1-WL-colorable graph without loss; (4) the restricted color-equivalence class of graphs used in Theorem 4.9. None of these are independently established.

assumptions (4)
  • domain assumption Cycle Double Cover Conjecture (stated as a conjecture in §3.2) is assumed to justify that chordless cycles and paths are sufficient to reconstruct all paths (Theorem 3.5).
    The paper says 'In graph theory, we have a conjecture' and then uses Lemma 3.3/3.4 to conclude Theorem 3.5 without proving or citing a proof of the conjecture. This is a load-bearing unproved premise.
  • ad hoc to paper Lemma 3.4: 'With the set of chordless paths, one can find all paths in the graph.'
    The proof in Appendix E.1 only handles a single chord and says 'select a single chord' with no iterative or general argument; it appears to be false for paths with multiple crossing chords.
  • ad hoc to paper Every graph in the considered class can be transformed into a 1-WL-colorable graph by subdividing edges (Lemma 4.3).
    The construction in E.2 is not rigorous: adding a middle node to avoid same-colored edges may break the graph's isomorphism class, and it is unclear how the transformation maps back to the original graphs.
  • domain assumption The color-equivalence condition in Theorem 4.9 is a structural requirement on the input graphs.
    Theorem 4.9 only holds for graphs that admit a color-equivalence automorphism (Definition 4.6) and have different numbers of connected components; this is a highly restrictive, unnatural class of graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Chordless Structure: A Pathway to Simple and Expressive GNNs." pith.science (2026). https://pith.science/paper/L5EVSX3T

@misc{pith2026250519188,
  author       = {Pith},
  title        = {Pith review of: Chordless Structure: A Pathway to Simple and Expressive GNNs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L5EVSX3T}},
  note         = {Machine review of arXiv:2505.19188}
}
read the original abstract

Researchers have proposed various methods of incorporating more structured information into the design of Graph Neural Networks (GNNs) to enhance their expressiveness. However, these methods are either computationally expensive or lacking in provable expressiveness. In this paper, we observe that the chords increase the complexity of the graph structure while contributing little useful information in many cases. In contrast, chordless structures are more efficient and effective for representing the graph. Therefore, when leveraging the information of cycles, we choose to omit the chords. Accordingly, we propose a Chordless Structure-based Graph Neural Network (CSGNN) and prove that its expressiveness is strictly more powerful than the k-hop GNN (KPGNN) with polynomial complexity. Experimental results on real-world datasets demonstrate that CSGNN outperforms existing GNNs across various graph tasks while incurring lower computational costs and achieving better performance than the GNNs of 3-WL expressiveness.

Figures

Figures reproduced from arXiv: 2505.19188 by the authors.

Figure 1
Figure 1. Chord and statistics of IMDB datasets. • k-GNN [33]: Observing the MPNNs are bounded by the 1-WL test, researchers imitate the K-WL test to design k-GNNs [33]. However, the computational and memory complexity of k-GNNs is at least O(|V | k+1) and O(|V | k ) respectively, which is infeasible for large graphs [24]. • Subgraph GNN [5]: Recognising that MPNNs are limited to identifying subgraph structures, researchers p… view at source ↗
Figure 2
Figure 2. WL-tree of Graph G. 2 Preliminaries 2.1 Notation Let G = (V, E) be an undirected graph consisting of a set of nodes V and a set of edges E ⊆ V × V . We denote by n the number of nodes in G and by m its number of edges. The set N (v) represents the neighbors of node v, and the set Nk(v) represents the k-hop neighborhood of node v. When considering colored graphs G = (V, E, c), we have a color function c : V −→ C, whe… view at source ↗
Figure 3
Figure 3. Examples of WL-indistinguishable graphs where CSGNN succeeds: (a) distinction by [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Examples of non-isomorphic graphs indistinguishable by WL tests. (a) 1-WL failure on [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Accuracy and Run time(s) comparison on SR datasets [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: By comparing the counts between chordless cycles and other cycles, we can see that the [PITH_FULL_IMAGE:figures/full_fig_p021_6.png]
Figure 7
Figure 7. Figure 7: Two WL-equivalent graphs that have different number of connected components [PITH_FULL_IMAGE:figures/full_fig_p023_7.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

60 extracted references · 36 canonical work pages

  1. [1]

    The sur- prising power of graph neural networks with random node initialization.arXiv preprint arXiv:2010.01179, 2020

    Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization.arXiv preprint arXiv:2010.01179, 2020

    arXiv 2010

  2. [2]

    Shortest path networks for graph property prediction

    Ralph Abboud, Radoslav Dimitrov, and Ismail Ilkan Ceylan. Shortest path networks for graph property prediction. InLearning on Graphs Conference, pages 5–1. PMLR, 2022

    work page 2022

  3. [3]

    Breaking the limits of message passing graph neural networks

    Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. InInternational Conference on Machine Learning, pages 599–608. PMLR, 2021

    work page 2021

  4. [4]

    Weisfeiler and lehman go cellular: Cw networks.Advances in neural information processing systems, 34:2625–2640, 2021

    Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks.Advances in neural information processing systems, 34:2625–2640, 2021

    work page 2021

  5. [5]

    Bronstein

    Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M. Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting.IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(1):657–668, 2023

    work page 2023

  6. [6]

    Kagnns: Kolmogorov-arnold networks meet graph learning, 2024

    Roman Bresson, Giannis Nikolentzos, George Panagopoulos, Michail Chatzianastasis, Jun Pang, and Michalis Vazirgiannis. Kagnns: Kolmogorov-arnold networks meet graph learning, 2024

    work page 2024

  7. [7]

    An end-to-end attention-based approach for learning on graphs, 2024

    David Buterez, Jon Paul Janet, Dino Oglic, and Pietro Lio. An end-to-end attention-based approach for learning on graphs, 2024

    work page 2024

  8. [8]

    Can graph neural networks count substructures?Advances in neural information processing systems, 33:10383–10395, 2020

    Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures?Advances in neural information processing systems, 33:10383–10395, 2020

    2020

Show all 60 references
  1. [9]

    Topology-informed graph transformer.arXiv preprint arXiv:2402.02005, 2024

    Yun Young Choi, Sun Woo Park, Minho Lee, and Youngho Woo. Topology-informed graph transformer.arXiv preprint arXiv:2402.02005, 2024

    2024

  2. [10]

    Cycle to clique (cy2c) graph neural network: A sight to see beyond neighborhood aggregation

    Yun Young Choi, Sun Woo Park, Youngho Woo, and U Jin Choi. Cycle to clique (cy2c) graph neural network: A sight to see beyond neighborhood aggregation. InThe Eleventh International Conference on Learning Representations, 2022

    2022

  3. [11]

    Convolutional neural networks on graphs with fast localized spectral filtering.Advances in neural information processing systems, 29, 2016

    Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering.Advances in neural information processing systems, 29, 2016

    2016

  4. [12]

    The expressive power of path based graph neural networks

    Tamara Drucks, Caterina Graziani, Fabian Jogl, Monica Bianchini, Franco Scarselli, and Thomas Gärtner. The expressive power of path based graph neural networks. InICML, 2024

    2024

  5. [13]

    A fair comparison of graph neural networks for graph classification.arXiv preprint arXiv:1912.09893, 2019

    Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification.arXiv preprint arXiv:1912.09893, 2019

    1912 arXiv

  6. [14]

    How powerful are k-hop message passing graph neural networks.Advances in Neural Information Processing Systems, 35:4776–4790, 2022

    Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks.Advances in Neural Information Processing Systems, 35:4776–4790, 2022

    2022

  7. [15]

    Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning.Nature Methods, 17(2):184–192, 2020

    Pablo Gainza, Freyr Sverrisson, Frederico Monti, Emanuele Rodola, Davide Boscaini, Michael M Bronstein, and Bruno E Correia. Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning.Nature Methods, 17(2):184–192, 2020

    2020

  8. [16]

    Neural message passing for quantum chemistry

    Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. InInternational conference on machine learning, pages 1263–1272. PMLR, 2017

    2017

  9. [17]

    Inductive representation learning on large graphs.Advances in neural information processing systems, 30, 2017

    Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.Advances in neural information processing systems, 30, 2017

    2017

  10. [18]

    Hamilton, Rex Ying, and Jure Leskovec

    William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs, 2018. 10

    2018

  11. [19]

    Toward a spectral theory of cellular sheaves.Journal of Applied and Computational Topology, 3(4):315–358, 2019

    Jakob Hansen and Robert Ghrist. Toward a spectral theory of cellular sheaves.Journal of Applied and Computational Topology, 3(4):315–358, 2019

    2019

  12. [20]

    Zinc: a free tool to discover chemistry for biology.Journal of chemical information and modeling, 52(7):1757–1768, 2012

    John J Irwin, Teague Sterling, Michael M Mysinger, Erin S Bolstad, and Ryan G Coleman. Zinc: a free tool to discover chemistry for biology.Journal of chemical information and modeling, 52(7):1757–1768, 2012

    2012

  13. [21]

    PhD thesis, Dissertation, RWTH Aachen University, 2020, 2020

    Sandra Kiefer.Power and limits of the Weisfeiler-Leman algorithm. PhD thesis, Dissertation, RWTH Aachen University, 2020, 2020

    2020

  14. [22]

    Kipf and Max Welling

    Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017

    2017

  15. [23]

    Geodesic graph neural network for efficient graph representation learning.Advances in neural information processing systems, 35:5896– 5909, 2022

    Lecheng Kong, Yixin Chen, and Muhan Zhang. Geodesic graph neural network for efficient graph representation learning.Advances in neural information processing systems, 35:5896– 5909, 2022

    2022

  16. [24]

    The expressive power of graph neural networks.Graph Neural Networks: Foundations, Frontiers, and Applications, pages 63–98, 2022

    Pan Li and Jure Leskovec. The expressive power of graph neural networks.Graph Neural Networks: Foundations, Frontiers, and Applications, pages 63–98, 2022

    2022

  17. [25]

    Sign and basis invariant networks for spectral graph representation learning

    Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.13013, 2022

    2022 arXiv

  18. [26]

    Geniepath: Graph neural networks with adaptive receptive paths

    Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. InProceedings of the AAAI conference on artificial intelligence, volume 33, pages 4424–4431, 2019

    2019

  19. [27]

    Graph inductive biases in transformers without message passing

    Liheng Ma, Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K Dokania, Mark Coates, Philip Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message passing. InInternational Conference on Machine Learning, pages 23321–23337. PMLR, 2023

    2023

  20. [28]

    When subgraph isomorphism is really hard, and why this matters for graph databases.Journal of Artificial Intelligence Research, 61:723–759, 2018

    Ciaran McCreesh, Patrick Prosser, Christine Solnon, and James Trimble. When subgraph isomorphism is really hard, and why this matters for graph databases.Journal of Artificial Intelligence Research, 61:723–759, 2018

    2018

  21. [29]

    Clustering of large databases of compounds: using the mdl “keys” as structural descriptors.Journal of chemical information and computer sciences, 37(3):443–448, 1997

    Malcolm J McGregor and Peter V Pallai. Clustering of large databases of compounds: using the mdl “keys” as structural descriptors.Journal of chemical information and computer sciences, 37(3):443–448, 1997

    1997

  22. [30]

    Path neural networks: Expressive and accurate graph neural networks

    Gaspard Michel, Giannis Nikolentzos, Johannes F Lutzeyer, and Michalis Vazirgiannis. Path neural networks: Expressive and accurate graph neural networks. InInternational Conference on Machine Learning, pages 24737–24755. PMLR, 2023

    2023

  23. [31]

    Tudataset: A collection of benchmark datasets for learning with graphs.arXiv preprint arXiv:2007.08663, 2020

    Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs.arXiv preprint arXiv:2007.08663, 2020

    2007 arXiv

  24. [32]

    Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.Advances in Neural Information Processing Systems, 33:21824–21840, 2020

    Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings.Advances in Neural Information Processing Systems, 33:21824–21840, 2020

    2020

  25. [33]

    Weisfeiler and leman go neural: Higher-order graph neural networks

    Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. InProceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602–4...

    2019

  26. [34]

    K-hop graph neural networks

    Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. K-hop graph neural networks. Neural Networks, 130:195–205, 2020

    2020

  27. [35]

    Deepinf: Social influence prediction with deep learning

    Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang. Deepinf: Social influence prediction with deep learning. InProceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2110–2119, 2018. 11

    2018

  28. [36]

    Recipe for a general, powerful, scalable graph transformer.Advances in Neural Information Processing Systems, 35:14501–14515, 2022

    Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer.Advances in Neural Information Processing Systems, 35:14501–14515, 2022

    2022

  29. [37]

    Effective consideration of ring structures in cast/cnmr for highly accurate 13c nmr chemical shift prediction.Tetrahedron, 61(31):7431–7437, 2005

    Hiroko Satoh, Hiroyuki Koshino, Takeaki Uno, Shungo Koichi, Satoru Iwata, and Tadashi Nakata. Effective consideration of ring structures in cast/cnmr for highly accurate 13c nmr chemical shift prediction.Tetrahedron, 61(31):7431–7437, 2005

    2005

  30. [38]

    P. D. Seymour. Sums of circuits. In J. A. Bondy and U. S. R. Murty, editors,Graph Theory and Related Topics, pages 341–355. Academic Press, New York, 1979

    1979

  31. [39]

    Dynamic edge-conditioned filters in convolutional neural networks on graphs

    Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neural networks on graphs. InProceedings of the IEEE conference on computer vision and pattern recognition, pages 3693–3702, 2017

    2017

  32. [40]

    Beyond homophily: Structure-aware path aggregation graph neural network

    Yifei Sun, Haoran Deng, Yang Yang, Chunping Wang, Jiarong Xu, Renhong Huang, Linfeng Cao, Yang Wang, and Lei Chen. Beyond homophily: Structure-aware path aggregation graph neural network. InIJCAI, pages 2233–2240, 2022

    2022

  33. [41]

    Weisfeiler and lehman go paths: Learning topological features via path complexes

    Quang Truong and Peter Chin. Weisfeiler and lehman go paths: Learning topological features via path complexes. InProceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15382–15391, 2024

    2024

  34. [42]

    An efficient algorithm for enumerating chordless cycles and chordless paths

    Takeaki Uno and Hiroko Satoh. An efficient algorithm for enumerating chordless cycles and chordless paths. InInternational Conference on Discovery Science, pages 313–324. Springer, 2014

    2014

  35. [43]

    Graph attention networks.arXiv preprint arXiv:1710.10903, 2017

    Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks.arXiv preprint arXiv:1710.10903, 2017

    2017 arXiv

  36. [44]

    The reduction of a graph to canonical form and the algebra which appears therein.nti, Series, 2(9):12–16, 1968

    Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein.nti, Series, 2(9):12–16, 1968

    1968

  37. [45]

    Self-supervised graph learning for recommendation

    Jiancan Wu, Xiang Wang, Fuli Feng, Xiangnan He, Liang Chen, Jianxun Lian, and Xing Xie. Self-supervised graph learning for recommendation. InProceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, pages 726–735, 2021

    2021

  38. [46]

    A non-asymptotic analysis of oversmoothing in graph neural networks.arXiv preprint arXiv:2212.10701, 2022

    Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks.arXiv preprint arXiv:2212.10701, 2022

    2022 arXiv

  39. [47]

    Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks.Decision Support Systems, 38(3):473–487, 2004

    Jennifer J Xu and Hsinchun Chen. Fighting organized crimes: using shortest-path algorithms to identify associations in criminal networks.Decision Support Systems, 38(3):473–487, 2004

    2004

  40. [48]

    How powerful are graph neural networks?CoRR, abs/1810.00826, 2018

    Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?CoRR, abs/1810.00826, 2018

    2018 arXiv

  41. [49]

    Cycle representation learning for inductive relation prediction

    Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, and Chao Chen. Cycle representation learning for inductive relation prediction. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors,Proceedings of the 39th International Conferen...

  42. [50]

    Cycle invariant positional encoding for graph representation learning

    Zuoyu Yan, Tengfei Ma, Liangcai Gao, Zhi Tang, Chao Chen, and Yusu Wang. Cycle invariant positional encoding for graph representation learning. InLearning on Graphs Conference, pages 4–1. PMLR, 2024

    2024

  43. [51]

    Analyzing learned molec- ular representations for property prediction.Journal of chemical information and modeling, 59(8):3370–3388, 2019

    Kevin Yang, Kyle Swanson, Wengong Jin, Connor Coley, Philipp Eiden, Hua Gao, Angel Guzman-Perez, Timothy Hopper, Brian Kelley, Miriam Mathea, et al. Analyzing learned molec- ular representations for property prediction.Journal of chemical information and modeling, 59(8):3370–3...

    2019

  44. [52]

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

    Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation?Advances in neural information processing systems, 34:28877–28888, 2021. 12

    2021

  45. [53]

    Graph convolutional neural networks for web-scale recommender systems

    Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974–983, 2018

    2018

  46. [54]

    Hierarchical graph representation learning with differentiable pooling.Advances in neural information processing systems, 31, 2018

    Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling.Advances in neural information processing systems, 31, 2018

    2018

  47. [55]

    The expressive power of graph neural networks: A survey.arXiv preprint arXiv:2308.08235, 2023

    Bingxu Zhang, Changjun Fan, Shixuan Liu, Kuihua Huang, Xiang Zhao, Jincai Huang, and Zhong Liu. The expressive power of graph neural networks: A survey.arXiv preprint arXiv:2308.08235, 2023

    2023 arXiv

  48. [56]

    A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests

    Bohang Zhang, Guhao Feng, Yiheng Du, Di He, and Liwei Wang. A complete expressiveness hierarchy for subgraph gnns via subgraph weisfeiler-lehman tests. InInternational Conference on Machine Learning, pages 41019–41077. PMLR, 2023

    2023

  49. [57]

    An end-to-end deep learning architecture for graph classification

    Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. InProceedings of the AAAI conference on artificial intelligence, volume 32, 2018

    2018

  50. [58]

    Nested graph neural networks.Advances in Neural Information Processing Systems, 34:15734–15747, 2021

    Muhan Zhang and Pan Li. Nested graph neural networks.Advances in Neural Information Processing Systems, 34:15734–15747, 2021

    2021

  51. [59]

    Limitations

    Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence enhanced graph neural network. In International Conference on Artificial Intelligence and Statistics, pages 2896–2906. PMLR, 2020. 13 NeurIPS Paper Checklist 1.Claims Question: Do the main claims made in the abstract and in...

    2020

  52. [60]

    Guidelines: • The answer NA means that the paper does not involve crowdsourcing nor research with human subjects

    Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals...

    2025

Pith tools

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