Pith. sign in

REVIEW 4 major objections 6 minor 43 references

GraSP: Simple yet Effective Graph Similarity Predictions

T0 review · 4 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 GraSP predicts GED and MCS more accurately and faster than ten baselines by replacing cross-graph node matching with positional encodings and multi-scale pooling.

desk verdict GraSP's empirical results are solid and worth a referee; the 1-WL expressiveness proof does not hold up. read the letter →

arxiv 2412.09968 v1 pith:R63VPFKK submitted 2024-12-13 cs.LG

Haoran Zheng , Jieming Shi , Renchi Yang This is my paper · ORCID
classification cs.LG MSC 68T0705C6068R10
keywords graphsimilaritycomputationeditdistancemaximumcommonsubgraphneuralnetworksrandomwalkpositionalencoding1-WLtestmulti-scalepooling
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

GraSP is a graph neural network for estimating graph edit distance (GED) and maximum common subgraph (MCS), two NP-hard similarity measures used in retrieval, drug discovery, and code comparison. The paper argues that the cross-graph node-matching modules used by previous GNN methods are unnecessary: a backbone that embeds each graph independently, enriched with random-walk positional encodings and a multi-scale pooling of node representations, predicts both metrics better than ten baselines on four real-world datasets while running in time linear in the number of nodes. The paper further claims a theoretical expressiveness result: GraSP can distinguish non-isomorphic graphs that the 1-WL isomorphism test cannot, provided the graphs' random-walk positional encodings differ. If correct, this would make accurate graph similarity practical for large graph collections and simplify learned similarity models substantially.

What carries the argument

The engine of GraSP is random-walk positional encoding (RWPE) combined with residual gated graph convolution and multi-scale pooling. RWPE gives node $i$ the diagonal entries $(A D^{-1})^\ell_{ii}$ for $\ell=1,\dots,k$, encoding return probabilities of random walks, and these are concatenated with learned label embeddings so initial features carry global topology. The backbone updates these features with residual gated graph convolution (RGGC) layers, where learnable gates control how much neighbor information flows in, and the representations from every layer are concatenated. Multi-scale pooling mixes attention pooling and summation pooling with a learnable per-dimension weight vector $a$, producing $z = a \odot z_{\text{att}} + (1-a) \odot z_{\text{sum}}$. The prediction head then combines the Euclidean distance of two graph embeddings with a Neural Tensor Network interaction term via a learned scalar $\beta$. Each component is designed to keep discriminative information while avoiding pair-by-pair node matching, which is what makes the method's complexity effectively linear in graph size.

What would settle it

Feed two non-isomorphic, 1-WL-indistinguishable graphs with distinct RWPE multisets through GraSP with trained pooling; if their final graph embeddings coincide, Proposition 1 fails as stated. Separately, computing exact GED on a random subset of IMDBMulti and PTC pairs would show whether the reported MAE advantages survive replacement of the heuristic labels.

Watch

Extended reading notes

Core claim

GraSP's central claim is that graph similarity prediction does not need cross-graph node-level interaction. The model embeds each graph separately—node labels concatenated with random-walk positional encoding, passed through residual gated graph convolution layers, then pooled by a learnable mixture of attention and summation pooling—and predicts GED or MCS from the Euclidean distance and an NTN interaction term of the two graph embeddings. The paper reports that this design outperforms ten competitors on AIDS700nef, IMDBMulti, LINUX, and PTC, winning all reported metrics for MCS and nearly all for GED, while having the fastest inference time. Proposition 1 states that for non-isomorphic graphs that the 1-WL test cannot distinguish, GraSP produces different graph representations whenever the two graphs have different sets of initial positional encodings, which the paper argues random walks provide for sufficiently large $k$.

Load-bearing premise

The claim that GraSP surpasses the 1-WL test rests on the premise that distinct multisets of positional-encoding-enhanced node features must produce distinct pooled graph embeddings, which summation and attention pooling do not guarantee.

Editorial extensions

If this is right

  • Cross-graph node-level interaction modules are not necessary for strong GED and MCS prediction, so similarity models can be built from per-graph embeddings alone.
  • Because positional encodings and graph embeddings can be computed once per graph and reused, online inference is fast: GraSP has the shortest inference time among all compared methods on all four datasets.
  • Random-walk positional encoding plus residual gated convolution gives graph embeddings that are more discriminative than standard message-passing GNNs bounded by the 1-WL test, under the conditions of Proposition 1.
  • The same architecture and loss serve both GED and MCS prediction, so switching the target metric requires only changing the regression label, not the model structure.
  • GraSP generalizes to larger unseen graphs: trained on graphs up to size 25 or 50, it keeps lower GED prediction error than GREED and H2MN on query graphs with 25-50 nodes.

Reading between the lines

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

  • Beyond the paper: because GraSP embeds each graph independently, all database graphs can be embedded once and cached, so a similarity query becomes a nearest-neighbour search over precomputed vectors rather than a fresh pair-wise evaluation.
  • Beyond the paper: the proof of Proposition 1 would become unconditional if the pooling step were replaced by an injective aggregation such as sorted or histogram-based pooling, a small architectural change that directly tests the theoretical claim.
  • Beyond the paper: setting the random-walk length $k$ above the graph diameter would more reliably satisfy the precondition that non-isomorphic graphs have distinct positional-encoding multisets, and this could be validated across the four datasets as a hyperparameter principle.
  • Beyond the paper: the same pair-independent encoder plus distance-and-interaction head could be transferred to other NP-hard graph-pair scores such as subgraph isomorphism counts, since the method does not rely on alignment structure.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. GraSP is a graph-similarity prediction model for estimating graph edit distance (GED) and maximum common subgraph (MCS). The architecture enhances node features with random-walk positional encodings (RWPE), processes them through stacked ResGatedGraphConv layers, pools node representations via a learned convex combination of attention and sum pooling, and predicts GED/MCS using a weighted combination of Euclidean distance and a Neural Tensor Network interaction term. The paper reports experiments against ten baselines on AIDS700nef, IMDBMulti, LINUX, and PTC, claiming state-of-the-art MAE, rank correlation, and precision-at-k in most settings, lower inference time, and ablations supporting each component. It also claims a theoretical result (Proposition 1) that GraSP can generate different graph representations for non-isomorphic graphs that the 1-WL test cannot distinguish, with a proof in the appendix.

Significance. The empirical core of the paper is valuable. On the two datasets with exact GED ground truth (AIDS700nef, LINUX) and for MCS with exact MCSPLIT labels, GraSP consistently outperforms the baselines by a wide margin on most metrics, and the efficiency comparison supports the design choice of omitting cross-graph node-level interactions. The paper also provides code, hyperparameter settings, sensitivity analysis, ablations, heatmaps, and generalization experiments, which is a concrete reproducibility asset. The theoretical expressiveness claim, however, is not established by the current proof: the pooling operation is non-injective, and the RWPE precondition of Proposition 1 does not hold for all 1-WL-inseparable graph pairs. These issues do not invalidate the empirical findings, but they require the theoretical claim to be repaired or substantially weakened before the paper can be accepted.

major comments (4)
  1. [Analysis of GRASP and Appendix: Proof of Proposition 1] The proof of Proposition 1 is invalid in its final inference. From the fact that the multisets of initial node representations {h_u^(0)} and {h_v^(0)} differ, the proof concludes that the final graph embeddings differ. This does not follow: the sum pooling z_sum = sum_i h_i and the attention pooling z_att defined before Eq. (5) are not injective multiset readouts, and the learned vector a in Eq. (5) does not restore injectivity. Two different multisets of node vectors can have the same sum or the same attention-weighted sum, and the RGGC layers in Eq. (3) with ReLU and learned matrices can also collapse distinct inputs. The proof needs either an injective pooling map whose injectivity is proven under the stated assumptions, or a revised claim limited to separation at the node-representation level rather than the graph-embedding level.
  2. [Analysis of GRASP and Appendix sensitivity analysis] The precondition of Proposition 1, that the two graphs have different sets of initial RWPEs, is asserted to hold for non-isomorphic graphs when k is sufficiently large ('it can be guaranteed'), but this is false. The Shrikhande graph and the 4x4 rook's graph are non-isomorphic, 1-WL-indistinguishable strongly regular graphs with the same parameters (16,6,2,2), and every vertex in both graphs has the same Rayleigh quotient / closed-walk return sequence for every step k, so the multisets of RWPE features are identical for all k. Proposition 1 therefore does not cover an infinite family of 1-WL-inseparable pairs, and the conclusion 'GraSP can surpass the 1-WL test' is not established. The authors should either restrict the claim to graphs for which the RWPE multisets are guaranteed to differ, use a positional encoding with a proven separation guarantee, or explicitly acknowledge the limitation.
  3. [Experiments: Data and ground truth] For IMDBMulti and PTC, the ground-truth GED is not exact but is defined as the minimum of the Beam, Hungarian, and VJ approximations. All MAE, rank-correlation, and precision-at-k numbers in Tables 1-2 for these datasets are therefore computed against approximate targets, and the reported superiority on IMDBMulti and PTC is conditional on the quality of those heuristics. The main text should state this limitation clearly when the datasets are introduced, and ideally the authors should report a comparison on a subset with exact GED values or quantify the heuristic error, especially because PTC has larger graphs where the approximation gap is likely larger.
  4. [Appendix: Additional ablation studies (Table 9)] The ablation claim that GraSP outperforms all ablated versions is overstated. In Table 9 on PTC under the GED metric, GRASP (w/o NTN) achieves MAE 3.367, which is lower than the full model's MAE 3.556, even though the full model has better rank-correlation and precision-at-k scores. Similarly, in Table 7 on IMDBMulti, GRASP (w/o pe) and GRASP (w/o NTN) are statistically comparable to the full model on several metrics. The text should qualify the ablation conclusions per metric and per dataset rather than stating that the full model is best on all metrics.
minor comments (6)
  1. [Throughout] The paper uses 'GRASP', 'GraSP', and 'G RASP' interchangeably; a single consistent spelling should be used in the title, abstract, and body.
  2. [Figure 2] Figure 2 is difficult to read in the submitted version; the component labels, tensor shapes, and pooling symbols should be enlarged or vectorized so that the architecture can be inspected.
  3. [Eq. (7)] The notation z_1^T W_I^{[1:t]} z_2 for the NTN tensor contraction is ambiguous; the authors should define the exact contraction over the tensor slices and specify the output dimensions of each term.
  4. [Paragraph after Eq. (8)] The adaptation of Eq. (8) to MCS is described informally ('we keep the right-hand side of Eq. (8) unchanged and change the left-hand side'); the text should state explicitly that the same prediction head is trained with MCS targets and explain how the distance and interaction terms are combined for a similarity objective.
  5. [Complexity analysis] The complexity analysis states that RWPE pre-computation takes O(k|V|^2) but then excludes it as a preprocessing step; the authors should clarify whether this cost is paid once per graph, amortized over all graph pairs, and how it affects the end-to-end comparison with baselines.
  6. [Conclusion] The final paragraph says GraSP 'passes the 1-WL test', but Proposition 1 claims it surpasses the 1-WL test; the wording should be corrected to avoid implying that the model is only as expressive as 1-WL.

Circularity Check

1 steps flagged · score 3.0 of 10

Empirical results are independent, but the theoretical expressiveness claim reduces the output graph-embedding separation to the RWPE input-feature separation; the pooling step in Proposition 1's proof is asserted, not derived.

  1. renaming known result [Section 'Analysis of GRASP' (paragraph following Proposition 1); Appendix 'Proof of Proposition 1']
    "According to the definition of RWPE, nodes on non-isomorphic graphs generally get different sets of RWPEs when k is sufficiently large (Dwivedi et al. 2022). Thus, RWPE satisfies this precondition that the sets of positional encodings are different. Therefore, graph embeddings that are more discriminative than the 1-WL test are obtained."

    The 'surpasses 1-WL' conclusion is inherited from the RWPE input rather than shown to be produced by GraSP. Proposition 1's only substantive content is that different initial position-encoding sets yield different final graph embeddings; the Appendix proof bridges this gap with 'Therefore' after Eq. (4), without proving that the RGGC layers, the summation/attention pooling, or the learned interpolation in Eq. (5) are injective. Summation pooling z_sum = sum_i h_i can map distinct multisets to the same vector, so distinct RWPE feature sets do not by construction imply distinct GraSP graph embeddings. The claim is the input condition renamed as an output property.

full rationale

No self-citation chain or fitted-input circularity is present: the GED/MCS predictions are supervised fits to external ground-truth labels, and the reported comparisons against ten baselines on four datasets stand independently. The use of Beam/Hungarian/VJ minima as GED ground truth for IMDBMulti and PTC affects label quality but is not a reuse of the model's own predictions, so it does not constitute circularity. The circularity is confined to the theoretical expressiveness argument. Proposition 1 contains the separating information in its precondition ('the two graphs have different sets of initial position encodings'), and the proof's final inference that this propagates through non-injective pooling to different graph embeddings is asserted rather than derived. The main text then presents the RWPE input difference as GraSP's own expressiveness ('Therefore, graph embeddings that are more discriminative than the 1-WL test are obtained'). Because the empirical contribution is self-contained, the score is moderate rather than high.

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

The empirical claim depends on a large set of trainable parameters and per-dataset hyperparameters; this is normal for a supervised method but means the 'prediction' is a fitted estimator. The theoretical expressiveness claim depends on an unproven and in general false step: distinct node feature sets do not imply distinct pooled graph embeddings. No invented entities are introduced; RWPE, RGGC, NTN, and attention/sum pooling are pre-existing components.

free parameters (7)
  • All neural network weights (feature MLPs, RGGC layers, pooling MLPs, NTN weights) = learned by gradient descent on the training MSE
    The model is a supervised regressor; the entire prediction function is fitted to the training pairs, so the empirical result is a fitted estimator rather than a closed-form derivation.
  • RWPE step size k = 16 (AIDS, IMDBMulti), 10 (LINUX), 20 (PTC)
    Tuned from {w/o, 8, 16, 24, 32}; this is the positional signal that the 1-WL expressiveness claim depends on.
  • Number of RGGC layers = 8 (AIDS, LINUX, PTC), 4 (IMDBMulti)
    Tuned from {4, 6, 8, 10, 12}; controls receptive field and is dataset-specific.
  • Hidden dimension d = 64 on all datasets
    Tuned from {16, 32, 64, 128, 256}; sets node and graph embedding size.
  • NTN output dimension t = not reported
    Defined in Eq. (7) but its value is not given in the hyperparameter table; the interaction head depends on it.
  • Learned blend coefficients a (pooling) and beta (prediction) = learned
    Eqs. (5) and (8) train a vector and a scalar to combine pooling schemes and distance/interaction terms.
  • Training hyperparameters (learning rate, weight decay, batch size, epochs) = learning rate 1e-4 to 2e-3, weight decay 5e-4, batch size 256, epochs 5,000 to 30,000
    From Table 5; chosen per dataset and affect the final model, but not the architectural claim.
assumptions (5)
  • standard math MPGNNs are bounded by the 1-WL test (Xu et al. 2019)
    Used to frame the expressiveness claim in the Analysis section.
  • domain assumption RWPE gives different positional encoding sets for the 1-WL indistinguishable graphs considered when k is large enough
    Precondition of Proposition 1; asserted with a citation but not proved here, and not guaranteed for all graph pairs.
  • standard math Two 1-WL indistinguishable graphs have the same label multiset at initialization
    Used implicitly in the Appendix proof of Proposition 1.
  • ad hoc to paper Minimum of Beam, Hungarian, and VJ approximations is acceptable as ground-truth GED for IMDBMulti and PTC
    Chosen because exact GED is infeasible; affects all MAE comparisons on those datasets.
  • domain assumption Benchmark datasets and the 6:2:2 split are representative and supervised i.i.d. assumptions hold
    Standard for the empirical evaluation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GraSP: Simple yet Effective Graph Similarity Predictions." pith.science (2026). https://pith.science/paper/R63VPFKK

@misc{pith2026241209968,
  author       = {Pith},
  title        = {Pith review of: GraSP: Simple yet Effective Graph Similarity Predictions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R63VPFKK}},
  note         = {Machine review of arXiv:2412.09968}
}
read the original abstract

Graph similarity computation (GSC) is to calculate the similarity between one pair of graphs, which is a fundamental problem with fruitful applications in the graph community. In GSC, graph edit distance (GED) and maximum common subgraph (MCS) are two important similarity metrics, both of which are NP-hard to compute. Instead of calculating the exact values, recent solutions resort to leveraging graph neural networks (GNNs) to learn data-driven models for the estimation of GED and MCS. Most of them are built on components involving node-level interactions crossing graphs, which engender vast computation overhead but are of little avail in effectiveness. In the paper, we present GraSP, a simple yet effective GSC approach for GED and MCS prediction. GraSP achieves high result efficacy through several key instruments: enhanced node features via positional encoding and a GNN model augmented by a gating mechanism, residual connections, as well as multi-scale pooling. Theoretically, GraSP can surpass the 1-WL test, indicating its high expressiveness. Empirically, extensive experiments comparing GraSP against 10 competitors on multiple widely adopted benchmark datasets showcase the superiority of GraSP over prior arts in terms of both effectiveness and efficiency. The code is available at https://github.com/HaoranZ99/GraSP.

Figures

Figures reproduced from arXiv: 2412.09968 by the authors.

Figure 1
Figure 1. GED and MCS examples from AIDS700nef dataset. Left: GED is 2 and right: MCS is 6. petitors over 4 real datasets in GED and MCS prediction tasks under various settings. The empirical results exhibit that GRASP can consistently achieve superior GED/MCS estimation performance over all the baselines while retain￾ing high efficiency. In summary, our contributions are as follows: • We propose a new approach GRASP for GSC,… view at source ↗
Figure 2
Figure 2. The architecture of GRASP [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 4
Figure 4. Inference time in second(s) per 10k pairs. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figures from the paper (10 more)
Figure 5
Figure 5. Figure 5: A ranking case study of GED prediction on AIDS700nef. [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: Hyperparameters sensitivity analysis. Params AIDS700nef IMDBMulti LINUX PTC GED learning rate 1e −4 to 1e −3 1e −4 to 1e −3 2e −4 to 2e −3 1e −4 to 1e −3 weight decay 5e −4 5e −4 5e −4 5e −4 batch size 256 256 256 256 epochs 3e 4 3e 4 2e 4 5e 3 # of gnn layers 8 4 8 8 …
Figure 7
Figure 7. Figure 7: Absolute error heatmap on GED on AIDS700nef. [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]
Figure 8
Figure 8. Figure 8: Absolute error heatmap on GED on IMDBMulti. [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 9
Figure 9. Figure 9: Absolute error heatmap on GED on LINUX. 0 20 40 10 20 Query Size (a) GRASP 0 20 40 10 20 (b) GREED 0 20 40 10 20 0 5 10 15 20 25 (c) ERIC [PITH_FULL_IMAGE:figures/full_fig_p011_9.png]
Figure 10
Figure 10. Figure 10: Absolute error heatmap on GED on PTC. (a) Using attention. (b) Using add. (c) Using multi [PITH_FULL_IMAGE:figures/full_fig_p011_10.png]
Figure 11
Figure 11. Figure 11: T-SNE visualization on IMDBMulti with atten [PITH_FULL_IMAGE:figures/full_fig_p011_11.png]
Figure 12
Figure 12. Figure 12: A ranking case on IMDBMulti. Query 0 2 2 Ground-truth GED 2 2 ... 4 ... 11 12 0 rank=1 2 rank=2 2 rank=3 2 Predicted GED by GraSP rank=4 2 rank=5 ... 4 ... ... rank=400 ... 11 rank=799 12 rank=800 [PITH_FULL_IMAGE:figures/full_fig_p012_12.png]
Figure 13
Figure 13. Figure 13: A ranking case on LINUX. Query 1 2 4 Ground-truth GED 5 5 ... 39 ... 204 209 3 rank=1 5 rank=2 5 rank=3 6 Predicted GED by GraSP rank=4 6 rank=5 ... 40 ... ... rank=137 ... 204 rank=274 209 rank=275 [PITH_FULL_IMAGE:figures/full_fig_p012_13.png]
Figure 14
Figure 14. Figure 14: A ranking case on PTC. Additional Case Studies Three case studies on IMDBMulti, LINUX, and PTC un￾der GED are included in [PITH_FULL_IMAGE:figures/full_fig_p012_14.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 37 canonical work pages

  1. [1]

    Bai, Y.; Ding, H.; Bian, S.; Chen, T.; Sun, Y.; and Wang, W. 2019. SimGNN: A Neural Network Approach to Fast Graph Similarity Computation. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining , 384--392

    work page 2019

  2. [2]

    Bai, Y.; Ding, H.; Gu, K.; Sun, Y.; and Wang, W. 2020. Learning-Based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching. In The Thirty-Fourth AAAI Conference on Artificial Intelligence , 3219--3226

    work page 2020

  3. [3]

    B.; and Gamper, J

    Blumenthal, D. B.; and Gamper, J. 2020. On the exact computation of the graph edit distance. Pattern Recognit. Lett., 134: 46--57

    work page 2020

  4. [4]

    M.; and Kriegel, H

    Borgwardt, K. M.; and Kriegel, H. 2007. Graph Kernels For Disease Outcome Prediction From Protein-Protein Interaction Networks. In Proceedings of the Pacific Symposium, 4--15

    work page 2007

  5. [5]

    Bresson, X.; and Laurent, T. 2017. Residual Gated Graph ConvNets. arXiv preprint arXiv:1711.07553

    arXiv 2017

  6. [6]

    Bunke, H.; and Allermann, G. 1983. Inexact graph matching for structural pattern recognition. Pattern Recognit. Lett., 1(4): 245--253

    work page 1983

  7. [7]

    Bunke, H.; and Shearer, K. 1998. A graph distance metric based on the maximal common subgraph. Pattern Recognit. Lett., 19(3-4): 255--259

    work page 1998

  8. [8]

    Chang, L.; Feng, X.; Lin, X.; Qin, L.; Zhang, W.; and Ouyang, D. 2020. Speeding Up GED Verification for Graph Similarity Search. In 36th IEEE International Conference on Data Engineering , 793--804

    work page 2020

Show all 43 references
  1. [9]

    P.; Joshi, C

    Dwivedi, V. P.; Joshi, C. K.; Luu, A. T.; Laurent, T.; Bengio, Y.; and Bresson, X. 2023. Benchmarking Graph Neural Networks. J. Mach. Learn. Res., 24: 43:1--43:48

    2023

  2. [10]

    P.; Luu, A

    Dwivedi, V. P.; Luu, A. T.; Laurent, T.; Bengio, Y.; and Bresson, X. 2022. Graph Neural Networks with Learnable Structural and Positional Representations. In The Tenth International Conference on Learning Representations

    2022

  3. [11]

    Fankhauser, S.; Riesen, K.; and Bunke, H. 2011. Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching. In Graph-Based Representations in Pattern Recognition - 8th IAPR-TC-15 International Workshop , volume 6658 of Lecture Notes in Computer Science, 102--111

    2011

  4. [12]

    Kendall, M. G. 1938. A New Measure of Rank Correlation. Biometrika, 30(1/2): 81--93

    1938

  5. [13]

    Kim, J. 2020. Nass: A New Approach to Graph Similarity Search. arXiv preprint arXiv:2004.01124

    2020 arXiv

  6. [14]

    Kim, J.; Choi, D.; and Li, C. 2019. Inves: Incremental Partitioning-Based Verification for Graph Similarity Search. In Advances in Database Technology - 22nd International Conference on Extending Database Technology, 229--240

    2019

  7. [15]

    N.; and Welling, M

    Kipf, T. N.; and Welling, M. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In 5th International Conference on Learning Representations

    2017

  8. [16]

    Lee, J.; Jin, R.; and Jain, A. K. 2008. Rank-based distance metric learning: An application to image retrieval. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition

    2008

  9. [17]

    Li, P.; Wang, Y.; Wang, H.; and Leskovec, J. 2020. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning. In Annual Conference on Neural Information Processing Systems

    2020

  10. [18]

    Li, Y.; Gu, C.; Dullien, T.; Vinyals, O.; and Kohli, P. 2019. Graph Matching Networks for Learning the Similarity of Graph Structured Objects. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, 3835--3845

    2019

  11. [19]

    X.; Wu, C.; and Ji, S

    Ling, X.; Wu, L.; Wang, S.; Ma, T.; Xu, F.; Liu, A. X.; Wu, C.; and Ji, S. 2021. Multilevel graph matching networks for deep graph similarity learning. IEEE Trans. Neural Networks Learn. Syst. , 34(2): 799--813

    2021

  12. [20]

    Liu, Y.; Li, C.; Jiang, H.; and He, K. 2020. A Learning Based Branch and Bound for Maximum Common Subgraph Related Problems. In The Thirty-Fourth AAAI Conference on Artificial Intelligence , 2392--2399

    2020

  13. [21]

    McCreesh, C.; Prosser, P.; and Trimble, J. 2017. A Partitioning Algorithm for Maximum Common Subgraph Problems. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 712--719

    2017

  14. [22]

    Neuhaus, M.; Riesen, K.; and Bunke, H. 2006. Fast Suboptimal Algorithms for the Computation of Graph Edit Distance. In Structural, Syntactic, and Statistical Pattern Recognition, Joint IAPR International Workshops , volume 4109 of Lecture Notes in Computer Science, 163--172

    2006

  15. [23]

    Piao, C.; Xu, T.; Sun, X.; Rong, Y.; Zhao, K.; and Cheng, H. 2023. Computing Graph Edit Distance via Neural Graph Matching. Proc. VLDB Endow. , 16(8): 1817--1829

    2023

  16. [24]

    Qin, C.; Zhao, H.; Wang, L.; Wang, H.; Zhang, Y.; and Fu, Y. 2021. Slow Learning and Fast Inference: Efficient Graph Similarity Computation via Knowledge Distillation. In Annual Conference on Neural Information Processing Systems, 14110--14121

    2021

  17. [25]

    T.; Sabharwal, Y.; and Ranu, S

    Ranjan, R.; Grover, S.; Medya, S.; Chakaravarthy, V. T.; Sabharwal, Y.; and Ranu, S. 2022. GREED: A Neural Framework for Learning Graph Distance Functions. In Annual Conference on Neural Information Processing Systems

    2022

  18. [26]

    T.; Singh, A

    Ranu, S.; Calhoun, B. T.; Singh, A. K.; and Swamidass, S. J. 2011. Probabilistic Substructure Mining From Small - Molecule Screens . Molecular Informatics, 30(9): 809--815

    2011

  19. [27]

    Riesen, K.; and Bunke, H. 2009. Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput., 27(7): 950--959

    2009

  20. [28]

    Sato, R. 2020. A Survey on The Expressive Power of Graph Neural Networks. arXiv preprint arXiv:2003.04078

    2020 arXiv

  21. [29]

    D.; and Ng, A

    Socher, R.; Chen, D.; Manning, C. D.; and Ng, A. Y. 2013. Reasoning With Neural Tensor Networks for Knowledge Base Completion. In 27th Annual Conference on Neural Information Processing Systems, 926--934

    2013

  22. [30]

    Spearman, C. 1987. The Proof and Measurement of Association between Two Things. The American Journal of Psychology, 100(3/4): 441--471

    1987

  23. [31]

    Tan, W.; Gao, X.; Li, Y.; Wen, G.; Cao, P.; Yang, J.; Li, W.; and Za \" ane, O. R. 2023. Exploring attention mechanism for graph similarity learning. Knowl. Based Syst., 276: 110739

    2023

  24. [32]

    D.; Kramer, S.; and Helma, C

    Toivonen, H.; Srinivasan, A.; King, R. D.; Kramer, S.; and Helma, C. 2003. Statistical Evaluation of the Predictive Toxicology Challenge 2000-2001. Bioinform., 19(10): 1183--1193

    2003

  25. [33]

    van der Maaten, L.; and Hinton, G. 2008. Visualizing Data using t-SNE. Journal of Machine Learning Research, 9(86): 2579--2605

    2008

  26. [34]

    Wang, R.; Zhang, T.; Yu, T.; Yan, J.; and Yang, X. 2021. Combinatorial Learning of Graph Edit Distance via Dynamic Embedding. In IEEE Conference on Computer Vision and Pattern Recognition , 5241--5250

    2021

  27. [35]

    Wang, X.; Ding, X.; Tung, A. K. H.; Ying, S.; and Jin, H. 2012. An Efficient Graph Indexing Method. In IEEE 28th International Conference on Data Engineering , 210--221

    2012

  28. [36]

    Weisfeiler, B.; and Leman, A. 1968. The reduction of a graph to canonical form and the algebra which appears therein. Nauchno-Technicheskaya Informatsia, 12--16

    1968

  29. [37]

    Xu, K.; Hu, W.; Leskovec, J.; and Jegelka, S. 2019. How Powerful are Graph Neural Networks? In 7th International Conference on Learning Representations

    2019

  30. [38]

    Yanardag, P.; and Vishwanathan, S. V. N. 2015. Deep Graph Kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , 1365--1374

    2015

  31. [39]

    Zeng, Z.; Tung, A. K. H.; Wang, J.; Feng, J.; and Zhou, L. 2009. Comparing Stars: On Approximating Graph Edit Distance. Proc. VLDB Endow. , 2(1): 25--36

    2009

  32. [40]

    Zhang, Z.; Bu, J.; Ester, M.; Li, Z.; Yao, C.; Yu, Z.; and Wang, C. 2021. H2MN: Graph Similarity Learning with Hierarchical Hypergraph Matching Networks. In The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , 2274--2284

    2021

  33. [41]

    Zhuo, W.; and Tan, G. 2022. Efficient Graph Similarity Computation with Alignment Regularization. In Annual Conference on Neural Information Processing Systems

    2022

  34. [42]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all...

  35. [43]

    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 gl...

Pith tools

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