Pith. sign in

REVIEW 3 major objections 5 minor 49 references

MultiGraphMatch: a subgraph matching algorithm for multigraphs

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read MultiGraphMatch claims to enumerate every occurrence of a query multigraph in a larger target multigraph, while running 2 to 10 times faster than compared systems on the tested graphs.

desk verdict Novel multigraph matching ideas undermined by a missing injectivity check that can emit invalid matches, but the core is salvageable and deserves a serious referee. read the letter →

arxiv 2501.09736 v1 pith:ETB4X4JX submitted 2025-01-16 cs.DB

Giovanni Micale , Antonio Di Maria , Roberto Grasso , Vincenzo Bonnici , Alfredo Ferro , Dennis Shasha , Rosalba Giugno , Alfredo Pulvirenti This is my paper · ORCID
classification cs.DB
keywords subgraphmatchingmultigraphbitmatrixcompatibilitydomainsymmetrybreakingedgeorderinggraphdatabases
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

Sub-multigraph matching is the problem of finding every occurrence of a small labeled, attributed multigraph (the query) inside a larger one (the target), where several edges of different types may connect the same two nodes. Earlier approaches either ignored such parallel edges or had to enumerate node mappings first and post-process them to pair query edges with target edges, a step that can become exponential in the number of target edges. The paper introduces MultiGraphMatch, which carries node and edge mappings together through the search and uses two mechanisms to keep the search small: a bit matrix that encodes, for every connected node pair, the endpoint labels and the presence of each edge type in each direction, and an ordering of query edges that prefers dense regions with few candidate target edges. The paper reports that MultiGraphMatch finds all occurrences satisfying its five matching conditions and is generally 2 to 10 times faster than the compared state-of-the-art systems on synthetic and real networks.

What carries the argument

The load-bearing structure is the bit matrix: one row per connected pair of target nodes, whose signature is the concatenation of one-hot bit strings for the first endpoint's labels, the types of incoming edges, the types of outgoing edges, and the second endpoint's labels. A target row can serve a query pair when, after possibly reversing the query pair, the signature containment test $\operatorname{Sign}(T) \wedge \operatorname{Sign}(Q) = \operatorname{Sign}(T)$ holds, and after comparing type-dependent degrees of the endpoints so that edge multiplicities are respected. The second mechanism is the query-edge ordering score: for each pair of connected query nodes not yet in the ordering, the score is $(\mathit{CF}, Sc)$, where $\mathit{CF}$ counts already-ordered endpoints and $Sc$ is proportional to total degree times neighbor Jaccard similarity divided by the compatibility-domain size (or just the inverse domain size when both endpoints are already placed). Lexicographic comparison of these pairs makes the search extend from already-matched dense regions with small candidate sets, which is what cuts the number of backtracks.

What would settle it

Build a target with two parallel edges of the same type from $t_1$ to $t_2$, and a query with two distinct edges $q_1q_2$ and $q_1q_3$ of that type. If MultiGraphMatch returns an occurrence mapping both $q_2$ and $q_3$ to $t_2$ (with $q_1$ mapped to $t_1$), then the node mapping is not injective and the output violates Definition 3.2, so the claimed exact enumeration fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that sub-multigraph matching does not need a two-phase node-then-edge approach. MultiGraphMatch first builds compatibility domains: for each directed pair of connected query nodes, the target node pairs whose bit signatures contain the query's bit signature, subject to type-dependent in- and out-degree inequalities that enforce edge multiplicities. It then processes query edges in an order chosen by a score that rises with the number of already-matched endpoints, total degree, and neighborhood Jaccard similarity, and falls with the size of the compatibility domain. The search maintains a partial node mapping and a partial edge mapping simultaneously, adds an occurrence whenever the last query edge in the order is matched, and backtracks otherwise. The paper asserts that this procedure returns exactly the set of occurrences defined by the five conditions of Definition 3.2 (injective node and edge mappings consistent with edge endpoints, node labels, edge types, and property sets), and that experiments show it to be generally 2 to 10 times faster than the compared systems.

Load-bearing premise

The argument assumes that checking that each target edge is still unused and that candidates come from the compatibility domain is enough to keep the node mapping one-to-one, even though the pseudocode never verifies that a newly mapped target node is not already the image of another query node.

Editorial extensions

If this is right

  • Multigraph queries expressed with logical conditions on labels, types, and properties can be answered without a post-processing phase for edge mappings.
  • The ordering heuristic should benefit dense query patterns in particular, because it prioritizes edges whose endpoints are already matched and whose candidate sets are small.
  • On the scalability benchmarks, running time grows as a power law with network scale (exponents roughly 1 to 1.5) while indexing time grows linearly, so the method remains practical as targets grow.
  • Ablation tests indicate that both the bit matrix and the ordering contribute separately to the speedup; removing either one degrades performance.

Reading between the lines

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

  • If the injectivity gap in the pseudocode is repaired, an immediate test is whether the same bit-matrix filtering can be extended to count edge multiplicities directly in the signature, replacing the separate type-dependent degree checks.
  • The reported speedup over general-purpose graph databases may partly reflect the advantage of a purpose-built in-memory index; porting the same data structures into an incremental database engine would separate algorithmic gains from system overhead.
  • A natural stress test is to run the algorithm on targets with many parallel edges between high-degree node pairs, since the bit matrix records only presence or absence of edge types and all multiplicity information is delegated to the degree checks.
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

3 major / 5 minor

Summary. The paper proposes MultiGraphMatch, an in-memory algorithm for exact sub-multigraph matching on labeled, attributed multigraphs. The algorithm introduces a bit-matrix index over target node-pairs, compatibility domains built from bit signatures and type-dependent degree inequalities, a query-edge processing order based on domain cardinalities and local density, and symmetry-breaking conditions adapted from simple-graph matching. The authors report experiments comparing MultiGraphMatch with SuMGra, Neo4J, and Memgraph on synthetic and real networks, plus scalability tests on LDBC graphs, and claim speedups of 2 to 10 times over the compared systems.

Significance. Exact subgraph matching in multigraphs is a legitimate and comparatively under-studied problem, so a correct algorithm with a scalable index and good experimental methodology would be a useful contribution. The paper's strengths are its explicit problem definition, a concrete indexing scheme, an ablation study that isolates the effects of the bit matrix and the ordering heuristic, and benchmarks on several synthetic and real networks with code and datasets made available. However, the central correctness claim is not backed by a proof, and the pseudocode as written admits non-injective node mappings, so the reported experiments currently measure an algorithm that does not solve the SMM problem as defined. The issues appear local and repairable, but the paper cannot be accepted in its present form.

major comments (3)
  1. [§5.5, Algorithms 1 and 2] The matching procedure does not enforce injectivity of the node mapping f, although Definition 3.2 requires f to be injective. In Algorithm 1, lines 12-16 assign f(q):=t and f(q'):=t' without checking whether t or t' is already in the image of f; the only global check (line 11) concerns the edge mapping g. In Algorithm 2, when one endpoint is already mapped (lines 11-16 and 18-22), the unmapped endpoint is assigned the target endpoint of a candidate edge e_T=(f(q),t') or e_T=(t,f(q')) without verifying that this target endpoint is not already mapped to a different query node. Concretely, take query nodes q1 (label X), q2 (label A), q3 (label B) with directed R-edges q1->q2 and q1->q3, and target nodes t1 (label X), t2 (labels A,B) with two parallel R-edges t1->t2. Processing q1->q2 first sets f(q1)=t1, f(q2)=t2. For q1->q3, Algorithm 2 line 13 accepts e_T=(t1,t2) because A_Q(q3)={B} is contained in A_T(t2), and no symmetry-breaking condition relates q2 and q3 since they have different labels. The algorithm then sets f(q3)=t2, producing a match with f(q2)=f(q3), which violates Definition 3.2 and is returned as an occurrence at Algorithm 1 line 28. The fix is to maintain the set of used target nodes and reject any candidate whose not-yet-mapped endpoint is already in the image of f; a correctness proof should accompany this fix.
  2. [§5.5 and §5.7] The paper provides no correctness or completeness proof for the matching procedure. The central claim — that the algorithm returns the list of all occurrences satisfying the five conditions of Definition 3.2 — requires a formal argument: an invariant showing that every partial mapping (f,g) built by the search respects Definition 3.2, an induction over the edge ordering O showing that every complete valid match is eventually reached, and a statement that backtracking restores precisely the information needed to continue the enumeration. Without such a theorem, even after the injectivity bug is fixed, the exact-enumeration claim remains unsupported. Adding such a proof is necessary for the algorithmic contribution to be verifiable.
  3. [§6 and §7] The experimental comparison is affected by the injectivity bug, because MultiGraphMatch can emit non-injective matches that SuMGra, Neo4J, and Memgraph are not asked to produce. The reported running times therefore do not compare the same task, and the speedup claim in Section 7 ('generally faster by a factor ranging from 2 to 10') cannot be taken at face value. The benchmarks should be rerun with the corrected algorithm, and the performance tables and significance statements should be updated accordingly.
minor comments (5)
  1. [§5.3] The text says node and edge properties are not used to build compatibility domains, yet Algorithm 2 checks node and edge properties when constructing candidate lists; please clarify the distinction between domain construction and candidate filtering.
  2. [§5.5, Algorithm 2] In the case where both endpoints are already mapped (lines 5-10), the candidate set is not explicitly restricted to the compatibility domain Dom; this is harmless because the endpoints are fixed, but the pseudocode and prose could state that Dom is no longer needed in that branch.
  3. [Table 3 caption] The caption says 'for each synthetic network' when reporting results on the real networks imdb and panama; it should read 'for each target network.'
  4. [§5.2] The sentence 'the application of the breaking condition q2≺q3 results leads to include solution S1' contains a typo ('results leads'); it should read 'results in including solution S1.'
  5. [Abstract and §7] The abstract's 'factor ranging from 2 to 10' is stronger than the experimental tables suggest, especially for real networks where the margins are smaller and sometimes not significant; please qualify the speedup claim accordingly.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: MultiGraphMatch is self-contained, with its heuristics evaluated on held-out queries and external benchmarks.

full rationale

The paper's derivation chain is not circular. The matching procedure (Algorithms 1 and 2) is a concrete search over compatible edges, where compatibility domains are computed from the stated multigraph labels, types, degrees, and properties rather than from the claimed set of occurrences. The ordering heuristic in Section 5.4 is defined once and then ablated on held-out query sets in Section 6.1.3, so no fitted parameter is renamed as a prediction. The symmetry-breaking conditions are justified by automorphism orbits computed by the external NAUTY tool [30], not by a self-citation chain. The few self-citations, e.g., [10] for variable ordering and [5, 11] for subgraph matching heuristics, support design choices but are not load-bearing for the correctness of the enumeration or for the performance comparison against SuMGra, Neo4J, and Memgraph on external datasets and the LSQB benchmark. No equation in the paper reduces to its own target, and no uniqueness claim is imported from the authors' prior work. A possible gap in the pseudocode regarding injectivity of the node mapping is a correctness concern, not a circularity concern, and therefore does not affect this score.

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

There are no fitted free parameters and no new physical or abstract entities. The central logical burden falls on the completeness of the compatibility-domain filter and on the implicit assumption that edge uniqueness enforces node injectivity, neither of which is proved.

assumptions (3)
  • domain assumption NAUTY computes automorphisms and orbits correctly for the multigraph query after the paper's extension.
    Section 5.2 relies on NAUTY [30] and extracts breaking conditions from computed orbits; no proof is given that the extension to labeled and attributed multigraphs preserves orbit semantics.
  • ad hoc to paper The compatibility-domain filter (bit-signature containment plus type-dependent degree inequalities) is complete for the SMM problem.
    Section 5.3 defines Dom and asserts matched rows are compatible, but no theorem shows every valid target edge pair survives the filter, so missed occurrences are possible in principle.
  • ad hoc to paper The matching procedures in Algorithms 1 and 2 preserve node-mapping injectivity by checking only target-edge uniqueness.
    Algorithm 1 line 11 tests g(e_Q) != e_T but no test checks whether t or t' is already in the image of f; this assumption is needed for Definition 3.2's injective f but is not verified.

how reviews work

0 comments
Cite this review

Pith. "Pith review of MultiGraphMatch: a subgraph matching algorithm for multigraphs." pith.science (2026). https://pith.science/paper/ETB4X4JX

@misc{pith2026250109736,
  author       = {Pith},
  title        = {Pith review of: MultiGraphMatch: a subgraph matching algorithm for multigraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ETB4X4JX}},
  note         = {Machine review of arXiv:2501.09736}
}
read the original abstract

Subgraph matching is the problem of finding all the occurrences of a small graph, called the query, in a larger graph, called the target. Although the problem has been widely studied in simple graphs, few solutions have been proposed for multigraphs, in which two nodes can be connected by multiple edges, each denoting a possibly different type of relationship. In our new algorithm MultiGraphMatch, nodes and edges can be associated with labels and multiple properties. MultiGraphMatch introduces a novel data structure called bit matrix to efficiently index both the query and the target and filter the set of target edges that are matchable with each query edge. In addition, the algorithm proposes a new technique for ordering the processing of query edges based on the cardinalities of the sets of matchable edges. Using the CYPHER query definition language, MultiGraphMatch can perform queries with logical conditions on node and edge labels. We compare MultiGraphMatch with SuMGra and graph database systems Memgraph and Neo4J, showing comparable or better performance in all queries on a wide variety of synthetic and real-world graphs.

Figures

Figures reproduced from arXiv: 2501.09736 by the authors.

Figure 1
Figure 1. Example of multigraph with actors and directors of the movie industry. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Example of sub-multigraph matching. There is only one occurrence of query [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Toy example of SubMultigraph Matching (SMM) with a query [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Indexing data structures associated to the target [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Example of symmetry breaking condition on nodes and edges and application of conditions on [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]
Figure 6
Figure 6. Figure 6: Example of computation of compatibility domains for the query [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: Boxplots of the query-by-query running time differences (in seconds) between MultiGraphMatch [PITH_FULL_IMAGE:figures/full_fig_p022_7.png]
Figure 8
Figure 8. Figure 8: Boxplots of the query-by-query running time differences (in seconds) between MultiGraphMatch [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 9
Figure 9. Figure 9: Boxplots of the log of the running times (in seconds) of MultiGraphMatch (MGM), MultiGraphMatch with no Bit Matrix (MGM-NoBM), MultiGraphMatch with Random Ordering (MGM-RO), MultiGraphMatch with Ordering based on Minimization of Domain Cardinalities (MGM-DC), MultiGrap…
Figure 10
Figure 10. Figure 10: Boxplots of the query-by-query running time differences (in seconds) between MultiGraphMatch [PITH_FULL_IMAGE:figures/full_fig_p027_10.png]
Figure 11
Figure 11. Figure 11: Boxplots of the query-by-query running time differences (in seconds) between MultiGraphMatch [PITH_FULL_IMAGE:figures/full_fig_p028_11.png]
Figure 12
Figure 12. Figure 12: Queries of the LSQB benchmark used for scalability experiments. [PITH_FULL_IMAGE:figures/full_fig_p029_12.png]
Figure 13
Figure 13. Figure 13: Running times (in seconds) of MultiGraphMatch for the networks listed in Table [PITH_FULL_IMAGE:figures/full_fig_p030_13.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 27 canonical work pages

  1. [1]

    K. Alaoui. 2019. A Categorization of RDF Triplestores. In Proceedings of the 4th International Conference on Smart City Applications (Casablanca, Morocco) (SCA ’19). Association for Computing Machinery, New York, NY, USA, Article 66, 7 pages. https://doi.org/10.1145/3368756.3369047

    work page arXiv 2019

  2. [2]

    R. Angles. 2018. The Property Graph Database Model. In Proceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management, Cali, Colombia, May 21-25, 2018 (CEUR Workshop Proceedings, Vol. 2100) . CEUR-WS.org, Cali, Colombia, 1–10

    work page 2018

  3. [3]

    Angles, J.B

    R. Angles, J.B. Antal, A. Averbuch, et al. 2020. The LDBC Social Network Benchmark. CoRR abs/2001.02299 (2020), 1–160. http://arxiv.org/abs/2001.02299

    arXiv 2020

  4. [4]

    Anwar, A.E

    M. Anwar, A.E. Hassanien, V. Sná˜sel, and S.H. Basha. 2022. Subgraph Query Matching in Multi-Graphs Based on Node Embedding. Mathematics 10, 24 (2022), 1–22. https://doi.org/10.3390/math10244830

    work page doi:10.3390/math10244830 2022

  5. [5]

    Aparo, V

    A. Aparo, V. Bonnici, G. Micale, A. Ferro, D. Shasha, A. Pulvirenti, and R. Giugno. 2019. Simple Pattern-only Heuristics Lead to Fast Subgraph Matching Strategies on Very Large Networks. In Practical Applications of Computational Biology and Bioinformatics, 12th International Conference . Springer International Publishing, Cham, 131–138

    work page 2019

  6. [6]

    Barabási and A

    A. Barabási and A. Réka. 1999. Emergence of Scaling in Random Networks. Science 286, 5439 (1999), 509–512. https://doi.org/10.1126/science.286.5439.509

    doi:10.1126/science.286.5439.509 1999

  7. [7]

    Barbagallo, A

    C. Barbagallo, A. Di Maria, A. Alecci, D. Barbagallo, S. Alaimo, L. Colarossi, A. Ferro, C. Di Pietro, M. Purrello, A. Pulvirenti, and M. Ragusa. 2021. VECTOR: An Integrated Correlation Network Database for the Identification of CeRNA Axes in Uveal Melanoma. Genes 12, 7 (2021), 1–19. https://doi.org/10.3390/genes12071004

    work page doi:10.3390/genes12071004 2021

  8. [8]

    Bhattarai, H

    B. Bhattarai, H. Liu, and H.H. Huang. 2019. CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching. In Proceedings of the 2019 International Conference on Management of Data (SIGMOD ’19) . Association for Computing Machinery, New York, NY, USA, 1447–1462. https://doi.org/10.1145/3299869.3300086

    arXiv 2019

Show all 49 references
  1. [9]

    F. Bi, L. Chang, X. Lin, L. Qin, and W. Zhang. 2016. Efficient Subgraph Matching by Postponing Cartesian Products. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD ’16) . Association for Computing Machinery, New York, NY, USA, 1199–1214. https:...

    2016

  2. [10]

    Bonnici and R

    V. Bonnici and R. Giugno. 2017. On the Variable Ordering in Subgraph Isomorphism Algorithms.IEEE/ACM Transactions on Computational Biology and Bioinformatics 14, 1 (2017), 193–203. https://doi.org/10.1109/TCBB.2016.2515595

    2017

  3. [11]

    Bonnici, R

    V. Bonnici, R. Giugno, A. Pulvirenti, D. Shasha, and A. Ferro. 2013. A subgraph isomorphism algorithm and its application to biochemical data. BMC Bioinformatics 14, 7 (2013), 1–13. https://doi.org/10.1186/1471-2105-14-S7-S13

    2013 doi

  4. [12]

    Carletti, P

    V. Carletti, P. Foggia, A. Saggese, and M. Vento. 2018. Challenging the Time Complexity of Exact Subgraph Isomorphism for Huge and Dense Graphs with VF3. IEEE Transactions on Pattern Analysis and Machine Intelligence 40, 4 (2018), 804–818. https://doi.org/10.1109/TPAMI.2017.2696940

    2018

  5. [13]

    S.A. Cook. 1971. The Complexity of Theorem-Proving Procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing (Shaker Heights, Ohio, USA) (STOC ’71). Association for Computing Machinery, New York, NY, USA, 151–158. https://doi.org/10.1145/800157.805047

    1971

  6. [14]

    Cordella, P

    L.P. Cordella, P. Foggia, C. Sansone, and M. Vento. 2004. A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 10 (2004), 1367–1372. https://doi.org/10. 1109/TPAMI.2004.75

    2004

  7. [15]

    Demeyer, T

    S. Demeyer, T. Michoel, J. Fostier, P. Audenaert, M. Pickavet, and P. Demeester. 2013. The Index-Based Subgraph Matching Algorithm (ISMA): Fast Subgraph Enumeration in Large Networks Using Optimized Search Trees. PLOS ONE 8, 4 (04 2013), 1–15. https://doi.org/10.1371/journal.p...

    2013 doi

  8. [16]

    Deutsch, Y

    A. Deutsch, Y. Xu, M. Wu, and V.E. Lee. 2019. TigerGraph: A Native MPP Graph Database. ArXiv abs/1901.08248 (2019), 1–28

    2019 arXiv

  9. [17]

    Francis, A

    N. Francis, A. Green, P. Guagliardo, et al . 2018. Cypher: An Evolving Query Language for Property Graphs. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD ’18). Association for Computing Machinery, New York, NY, USA, 1433–14...

    2018

  10. [18]

    Giugno, V

    R. Giugno, V. Bonnici, N. Bombieri, A. Pulvirenti, A. Ferro, and D. Shasha. 2013. GRAPES: A Software for Parallel Searching on Biological Graphs Targeting Multi-Core Architectures. PLOS ONE 8, 10 (2013), 1–11

    2013

  11. [19]

    Grochow and M

    J.A. Grochow and M. Kellis. 2007. Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking. In Research in Computational Molecular Biology , Vol. 4453. Springer Berlin Heidelberg, Berlin, Heidelberg, 92–106. https://doi.org/10.1007/978-3-540-71681-5_7

    2007 doi

  12. [20]

    M. Han, H. Kim, G. Gu, K. Park, and W. Han. 2019. Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together. InProceedings of the 2019 International Conference on Management J. ACM, Vol. 37, No. 4, Article 111. Publication ...

    2019

  13. [21]

    W. Han, J. Lee, and J. Lee. 2013. Turboiso: Towards Ultrafast and Robust Subgraph Isomorphism Search in Large Graph Databases. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD ’13) . Association for Computing Machinery, New York, NY,...

    2013

  14. [22]

    He and A.K

    H. He and A.K. Singh. 2008. Graphs-at-a-Time: Query Language and Access Methods for Graph Databases. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data (SIGMOD ’08) . Association for Computing Machinery, New York, NY, USA, 405–418. https://doi...

    2008

  15. [23]

    Houbraken, S

    M. Houbraken, S. Demeyer, T. Michoel, P. Audenaert, D. Colle, and M. Pickavet. 2014. The Index-Based Subgraph Matching Algorithm with General Symmetries (ISMAGS): Exploiting Symmetry for Faster Subgraph Enumeration. PLOS ONE 9, 5 (05 2014), 1–15. https://doi.org/10.1371/journa...

    2014 doi

  16. [24]

    Ingalalli, D

    V. Ingalalli, D. Ienco, and P. Poncelet. 2016. SuMGra: Querying Multigraphs via Efficient Indexing. In Database and Expert Systems Applications. Springer International Publishing, Cham, 387–401

    2016

  17. [25]

    Katari, D

    M.S. Katari, D. Shasha, and S. Tyagi. 2021.Statistics is Easy: Case Studies on Real Scientific Datasets. Springer International Publishing, Cham. https://doi.org/10.1007/978-3-031-02433-7

    2021 doi

  18. [26]

    H. Kim, Y. Choi, K. Park, X. Lin, S. Hong, and W. Han. 2022. Fast subgraph query processing and subgraph matching via static and dynamic equivalences. The VLDB Journal 32, 2 (2022), 343–368. https://doi.org/10.1007/s00778-022-00749-x

    2022 doi

  19. [27]

    Larrosa and G

    J. Larrosa and G. Valiente. 2002. Constraint Satisfaction Algorithms for Graph Pattern Matching. Mathematical Structures in Comp. Sci. 12, 4 (2002), 403–422. https://doi.org/10.1017/S0960129501003577

    2002 doi

  20. [28]

    Leskovec and R

    J. Leskovec and R. Sosič. 2016. SNAP: A General-Purpose Network Analysis and Graph-Mining Library. ACM Transactions on Intelligent Systems and Technology (TIST) 8, 1 (2016), 1

    2016

  21. [29]

    McCreesh, P

    C. McCreesh, P. Prosser, and J. Trimble. 2020. The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants. In Graph Transformation. Springer International Publishing, Cham, 316–324

    2020

  22. [30]

    McKay and A

    B.D. McKay and A. Piperno. 2014. Practical graph isomorphism, II. Journal of Symbolic Computation 60 (2014), 94–112. https://doi.org/10.1016/j.jsc.2013.09.003

    2014 doi

  23. [31]

    Mhedhbi, M

    A. Mhedhbi, M. Lissandrini, L. Kuiper, J. Waudby, and G. Szárnyas. 2021. LSQB: A Large-Scale Subgraph Query Benchmark. In Proceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA) (Vi...

    2021

  24. [32]

    Miyazaki

    T. Miyazaki. 1997. The complexity of McKay’s canonical labeling algorithm . DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 28. American Mathematical Society, Providence, RI. 239–256 pages. https: //doi.org/10.1090/dimacs/028/14

    1997 doi

  25. [33]

    Monteiro, F

    J. Monteiro, F. Sá, and J. Bernardino. 2023. Experimental Evaluation of Graph Databases: JanusGraph, Nebula Graph, Neo4j, and TigerGraph. Applied Sciences 13, 9 (2023), 1–16. https://doi.org/10.3390/app13095770

    2023 doi

  26. [34]

    Moorman, T.K

    J.D. Moorman, T.K. Tu, Q. Chen, X. He, and A.L. Bertozzi. 2021. Subgraph Matching on Multiplex Networks. IEEE Transactions on Network Science and Engineering 8, 2 (2021), 1367–1384. https://doi.org/10.1109/TNSE.2021.3056329

    2021

  27. [35]

    Ren and J

    X. Ren and J. Wang. 2015. Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs. Proc. VLDB Endow. 8, 5 (2015), 617–628. https://doi.org/10.14778/2735479.2735493

    2015

  28. [36]

    Ribeiro and F

    P. Ribeiro and F. Silva. 2014. G-Tries: a data structure for storing and finding subgraphs. Data Mining and Knowledge Discovery 28, 2 (2014), 337–377. https://doi.org/10.1007/s10618-013-0303-4

    2014 doi

  29. [37]

    Shang, Y

    H. Shang, Y. Zhang, X. Lin, and J.X. Yu. 2008. Taming Verification Hardness: An Efficient Algorithm for Testing Subgraph Isomorphism. Proc. VLDB Endow. 1, 1 (2008), 364–375. https://doi.org/10.14778/1453856.1453899

    2008

  30. [38]

    C. Solnon. 2010. AllDifferent-based filtering for subgraph isomorphism. Artificial Intelligence 174, 12 (2010), 850–864. https://doi.org/10.1016/j.artint.2010.05.002

    2010 doi

  31. [39]

    Sun and Q

    S. Sun and Q. Luo. 2020. In-Memory Subgraph Matching: An In-Depth Study. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (SIGMOD ’20) . Association for Computing Machinery, New York, NY, USA, 1083–1098. https://doi.org/1...

    2020

  32. [40]

    Y. Sun, G. Li, J. Du, B. Ning, and H. Chen. 2021. A subgraph matching algorithm based on subgraph index for knowledge graph. Frontiers of Computer Science 16, 3 (2021), 163606. https://doi.org/10.1007/s11704-020-0360-y

    2021 doi

  33. [41]

    Timón-Reina, M

    S. Timón-Reina, M. Rincón, and R. Martínez-Tomás. 2021. An overview of graph databases and their applications in the biomedical domain. Database 2021 (2021), 1–22. https://doi.org/10.1093/database/baab026

    2021 doi

  34. [42]

    J.R. Ullmann. 1976. An Algorithm for Subgraph Isomorphism. J. ACM 23, 1 (1976), 31–42. https://doi.org/10.1145/ 321921.321925

    1976

  35. [43]

    J.R. Ullmann. 2011. Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism. ACM J. Exp. Algorithmics 15 (2011), 1–64. https://doi.org/10.1145/1671970.1921702 J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018. MultiGraphMatch: a subgr...

    2011

  36. [44]

    Vilaça, F

    R. Vilaça, F. Cruz, and R. Oliveira. 2010. On the Expressiveness and Trade-Offs of Large Scale Tuple Stores. In On the Move to Meaningful Internet Systems, OTM 2010 . Springer Berlin Heidelberg, Berlin, Heidelberg, 727–744

    2010

  37. [45]

    D. Yang, Y. Ge, T. Nguyen, D. Molitor, J.D. Moorman, and A.L. Bertozzi. 2023. Structural Equivalence in Subgraph Matching. IEEE Transactions on Network Science and Engineering 10, 4 (2023), 1846–1862. https://doi.org/10.1109/ TNSE.2023.3236028

    2023

  38. [46]

    Zampelli, Y

    S. Zampelli, Y. Deville, and C. Solnon. 2010. Solving subgraph isomorphism problems with constraint programming. Constraints 15, 3 (2010), 327–353. https://doi.org/10.1007/s10601-009-9074-3

    2010 doi

  39. [47]

    L. Zeng, Y. Jiang, W. Lu, and L. Zou. 2021. Deep Analysis on Subgraph Isomorphism. arXiv:2012.06802 [cs.DB]

    2021 arXiv

  40. [48]

    Zhang, S

    S. Zhang, S. Li, and J. Yang. 2009. GADDI: Distance Index Based Subgraph Matching in Biological Networks. In Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology (EDBT ’09). Association for Computing Machinery, New ...

    2009 doi

  41. [49]

    Zhao and J

    P. Zhao and J. Han. 2010. On Graph Query Optimization in Large Networks. Proc. VLDB Endow. 3, 1-2 (2010), 340–351. https://doi.org/10.14778/1920841.1920887 A SUPPLEMENTARY TABLES Network Comparison Median time P-value Confidence difference (secs) interval Uniform(2,2) (Neo4J, ...

    2010

Pith tools

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