Pith. sign in

REVIEW 4 minor 56 references

The Fine-Grained Complexity of Counting Hypergraph Motifs

T0 review · 0 major / 4 minor · reviewed 2026-07-11 · grok-4.5

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

Pith's one-line read Exact hypergraph motif counting is always fixed-parameter near-quadratic in rank, and admits fixed-parameter near-linear time precisely for the degenerate Venn diagrams.

desk verdict Clean FPT-near-quadratic / near-linear dichotomy for all 26 three-edge hypergraph motifs under rank, with the hard work done by colourful fractures that kill cancellations. read the letter →

arxiv 2607.05040 v1 pith:YNG4N5XZ submitted 2026-07-06 cs.CC cs.DM

Madhumitha Krishnakumar , Marc Roth This is my paper · ORCID
classification cs.CCcs.DM MSC 68Q2505C6568R10
keywords hypergraphmotifsVenndiagramsfine-grainedcomplexityparameterisedcountinghomomorphismbasisgeneralisedhypertreewidthTriangleHypothesisHyperclique
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

Hypergraph motifs are three-edge connected subhypergraphs whose intersections match a prescribed Venn diagram pattern. Prior algorithms took cubic time even on bounded-rank inputs, including ordinary graphs. This paper proves that every such motif can be counted exactly in time that is fixed-parameter near-quadratic in the number of edges once the rank is treated as the parameter. The same running time improves to fixed-parameter near-linear if and only if the Venn diagram is degenerate (one edge forced inside another). For every non-degenerate diagram the near-linear regime is impossible unless standard fine-grained hypotheses fail. The result therefore supplies a complete dichotomy for the three-edge case and explains exactly when the cubic barrier can be beaten.

What carries the argument

The hypergraph-homomorphism basis (linear combinations of homomorphism counts obtained from quotients of the motif hypergraphs) together with a colourful intermediate problem defined via fractures of the host. Non-zero coefficients of non-α-acyclic terms survive for every non-degenerate diagram, and Dedekind interpolation transfers hardness; generalised hypertree-width at most 2 (respectively 1) yields the matching upper bounds.

What would settle it

Exhibit either an FPT-near-linear algorithm for any single non-degenerate Venn diagram, or a near-linear algorithm for detecting triangles in graphs or hypercliques in uniform hypergraphs; either would collapse the claimed dichotomy.

Watch

Extended reading notes

Core claim

Every Venn diagram admits an exact counting algorithm running in f(rank(G))·Õ(|E(G)|^{2}) time. This improves to f(rank(G))·Õ(|E(G)|) time exactly when the diagram is degenerate, i.e., forces one of the three hyperedges to be fully contained in another. For all non-degenerate diagrams no fixed-parameter near-linear algorithm exists unless the Triangle Hypothesis or the Hyperclique Hypothesis fails.

Load-bearing premise

The near-linear lower bounds for non-degenerate diagrams rest on the Triangle Hypothesis and the Hyperclique Hypothesis remaining true.

Editorial extensions

If this is right

  • On any class of bounded-rank hypergraphs the cubic algorithms of Lee et al. are never optimal: every motif is near-quadratic and the degenerate ones are near-linear.
  • The same dichotomy immediately specialises to ordinary graphs (rank 2), giving a complete fine-grained classification of three-edge motif counting on simple graphs.
  • Any future improvement of the generalised-hypertree-width algorithms for homomorphism counting would automatically improve the motif-counting upper bounds by the same factor.
  • The hereditary fractional-hypertree-width and adaptive-width criteria already supply matching FPT and ETH-hardness results for generalised motifs on more than three edges, leaving only the open gap inherited from hypergraph homomorphism counting.

Reading between the lines

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

  • The colourful-fracture technique introduced here is likely reusable for any motif-counting problem whose patterns are defined by emptiness constraints on intersections, including higher-arity relational queries.
  • Closing the remaining gap between fractional hypertree-width and adaptive width for hypergraph homomorphisms would immediately give a complete FPT dichotomy for all generalised hypergraph motifs.
  • The same linear-combination approach should yield conditional lower bounds for approximate counting of non-degenerate motifs under the same fine-grained hypotheses.
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

0 major / 4 minor

Summary. The paper classifies the fine-grained parameterized complexity of exact counting of hypergraph motifs (connected 3-edge subhypergraphs whose intersections match a Venn diagram V in {0,1}^7) with respect to the rank of the host hypergraph G. It proves that #HyperMotif(V) always admits an FPT-near-quadratic algorithm f(rank(G)) · Õ(|E(G)|^2). Moreover, FPT-near-linear time is possible if and only if V is degenerate (one edge forced to be contained in another); for every non-degenerate V the problem is not FPT-near-linear unless the Triangle Hypothesis or the Hyperclique Hypothesis fails. The proofs proceed by expressing motif counts as linear combinations of (colourful) hypergraph homomorphism counts via fractures and Möbius inversion over the fracture lattice, isolating a non-α-acyclic term of generalized hypertreewidth >1 for non-degenerate diagrams, and invoking known near-linear hardness of homomorphism counting from non-acyclic patterns. Partial FPT/ETH results are also given for generalized motifs of order k>3 via hereditary fractional hypertreewidth and adaptive width.

Significance. The result supplies a tight, exhaustive dichotomy for a motif-counting problem that was introduced for practical hypergraph analysis (Lee–Ko–Shin, VLDB 2020) and whose previous algorithms were cubic even on bounded-rank or 2-uniform instances. The improvement to near-quadratic (and near-linear for the degenerate cases) is therefore both theoretically clean and immediately relevant to the original application domain. The technical machinery—hypergraph fractures, the colourful intermediate problem, and coefficient non-vanishing arguments that survive multiple non-isomorphic realisations of the same Venn diagram—extends the recent hypergraph-homomorphism basis of Bressan et al. (SODA 2026) in a non-trivial way and is likely reusable for other hypergraph motif problems. The partial classification for k>3 correctly identifies the open gap with the still-unresolved complexity of unbounded-rank hypergraph homomorphism counting, so the paper does not overclaim.

minor comments (4)
  1. Figure 2 and Definition 2.14: the visual distinction between degenerate (green) and non-degenerate (red) diagrams is helpful, but a short explicit list of the containment conditions that characterise the twelve degenerate diagrams would make the dichotomy easier to verify without inspecting every picture.
  2. Section 4 (especially Lemmas 4.3–4.7): the case-by-case coefficient calculations for the fourteen non-degenerate diagrams are correct but somewhat repetitive; a short table summarising, for each V_i, the chosen host (Δ(j1,j2,j3) or Γ(j1,j2,j3)) and the resulting non-zero coefficient of the coarsest fracture would improve readability.
  3. Lemma 3.8 / Algorithm 1: the claimed O(r^{2} · ∥G∥ · ∥F∥) bound for the colour-preserving tensor product is fine, yet the algorithm description does not explicitly state that edges of unequal cardinality are discarded; a one-line remark would remove any ambiguity.
  4. Page 9, line 3 of the abstract and several places in the introduction: the notation |G| is used for the input size while |E(G)| appears in the running-time statements; a uniform convention (or an explicit remark that |G| = Θ(|V| + |E|) under the no-isolated-vertex assumption) would avoid minor confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: standard fine-grained reduction from motif counts to homomorphism counts under external hypotheses

full rationale

The paper's central dichotomy (FPT-near-quadratic for every Venn diagram; FPT-near-linear precisely for the degenerate ones) is obtained by expressing #M(V o G) as a finite linear combination of hypergraph homomorphism counts (Lemma 5.2 / Eq. (2)–(3)), bounding the generalised hypertreewidth of the surviving terms by elementary bag-cover arguments (Lemma 5.1), and, for the lower bound, isolating a non-α-acyclic term via a colourful fracture expansion whose coefficients are explicit Möbius products over the fracture lattice (Corollary 3.4 and Lemmas 4.3–4.7). The hardness of the isolated term is imported from Brault-Baron / Mengel under the Triangle and Hyperclique Hypotheses, which are external, publicly stated conjectures, not results of the present authors. No quantity is defined in terms of a later-recovered prediction, no parameter is fitted to data, and the self-citations (Bressan et al. SODA 2026 for the homomorphism basis and Dedekind interpolation) supply only the general algebraic toolkit, not the specific non-vanishing coefficients or the degeneracy classification. The derivation is therefore self-contained against its stated external benchmarks.

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

The central dichotomy rests on standard fine-grained hypotheses (Triangle, Hyperclique, ETH), on the known complexity of hypergraph homomorphism counting for bounded ghtw / fhtw / adaptive width, and on the algebraic identity expressing motif counts as linear combinations of homomorphism counts via the Möbius function of the partition / fracture lattice. No free parameters are fitted; the only invented technical devices are the colourful intermediate problem and the hypergraph-fracture formalism, both of which are definitional tools rather than physical entities.

assumptions (5)
  • domain assumption Triangle Hypothesis: no algorithm decides the existence of a triangle in an m-edge graph in Õ(m) time.
    Invoked (together with Hyperclique) to obtain near-linear hardness for non-α-acyclic homomorphism counting (Theorem 5.8 / Brault-Baron).
  • domain assumption Hyperclique Hypothesis: for no k > h > 2 does an algorithm decide a k-hyperclique in an h-uniform n-vertex hypergraph in Õ(n^{k-ε}) time.
    Same role as Triangle Hypothesis for the lower-bound side of the dichotomy.
  • domain assumption ETH: 3-SAT cannot be solved in exp(o(n)) time.
    Used only for the #W[1]-hardness side of the partial classification of generalised motifs (Theorem 1.5 / Marx).
  • standard math Homomorphism counting from a hypergraph of generalised hypertreewidth w can be performed in Õ(|G|^w) time (Yannakakis + extensions).
    Black-box upper-bound engine for both the quadratic and the linear algorithms (Theorem 5.3).
  • standard math Complexity monotonicity / Dedekind interpolation for linear combinations of (colourful) hypergraph homomorphism counts.
    Taken from Bressan et al. (SODA 2026 / full version); allows isolation of the hardest term once a non-zero coefficient is exhibited.
invented entities (2)
  • Hypergraph fracture and fractured hypergraph H♮ρ⃗
    purpose: Provides a colourful intermediate problem whose homomorphism expansion has simpler, controllable coefficients, avoiding cancellations that appear in the uncoloured expansion.
    Definitional technical device introduced in Section 2.1.4; no independent physical or empirical existence claimed.
  • Colourful hypergraph motif counting problem #ColHyperMotif(V)
    purpose: Intermediate problem that is FPT-linear-time equivalent to the original problem yet admits a cleaner coefficient analysis.
    Introduced in Section 2.2.3 and used throughout Sections 3–5; purely algorithmic construct.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Fine-Grained Complexity of Counting Hypergraph Motifs." pith.science (2026). https://pith.science/paper/YNG4N5XZ

@misc{pith2026260705040,
  author       = {Pith},
  title        = {Pith review of: The Fine-Grained Complexity of Counting Hypergraph Motifs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YNG4N5XZ}},
  note         = {Machine review of arXiv:2607.05040}
}
abstract

Introduced by Lee, Ko, and Shin (VLDB 2020), a hypergraph motif is a connected subhypergraph consisting of three hyperedges whose intersections satisfy a prescribed pattern. Such patterns are represented by Venn diagrams $\mathcal{V}\in\{0,1\}^7$, indicating which of the seven regions determined by three sets must be empty or non-empty. Lee et al. designed and implemented exact and approximate algorithms for counting, in a hypergraph $G$, the motifs specified by $\mathcal{V}$; their algorithms run in worst-case cubic time in the number of hyperedges of $G$. This cubic worst case can occur even for hypergraphs of bounded rank, and already for $2$-uniform hypergraphs, that is, for simple graphs. In this work, we give a complete fine-grained picture of the parameterised complexity of exact hypergraph motif counting with respect to the rank of the input hypergraph. We use $\tilde{O}$ to hide polylogarithmic factors in the input size. First, we show that every Venn diagram $\mathcal{V}$ admits an exact counting algorithm running in FPT-near-quadratic time, \[ f(\mathsf{rank}(G))\cdot \tilde{O}(|E(G)|^2), \] for some computable function $f$. Second, we precisely characterise when this can be improved to FPT-near-linear time. We prove that such an algorithm exists exactly for the degenerate Venn diagrams, namely those that force one of the three hyperedges to be fully contained in another. For all non-degenerate Venn diagrams, we show that no FPT-near-linear-time algorithm exists unless either the Triangle Hypothesis or the Hyperclique Hypothesis fails. Exact hypergraph motif counting is thus always fixed-parameter near-quadratic in the rank, and the degenerate Venn diagrams are precisely the cases admitting fixed-parameter near-linear time.

Figures

Figures reproduced from arXiv: 2607.05040 by the authors.

Figure 1
Figure 1. (Left:) An indexing of the intersections of three sets. (Centre): Illustration of the Venn diagram V = (0, 1, 1, 1, 1, 1, 1). (Right): A hypergraph satisfying V. 1 Introduction Motif counting refers to the problem of computing the number of occurrences of a small pattern in a large host network. Examples include subgraph counting, induced subgraph counting, as well as counting answers to a query in a relational data… view at source ↗
Figure 2
Figure 2. The Venn diagrams V1, . . . , V14 represent the non-degenerate cases. We show that hypergraph motifs corresponding to those Venn diagrams cannot be counted in (FPT-)near-linear time under standard lower bound assumptions. In contrast, the Venn diagrams V15, . . . , V26 are degenerate, and we will see that counting hypergraph motifs corresponding to those Venn diagrams is possible in (FPT-)near-linear time. Our initi… view at source ↗
Figure 3
Figure 3. A pair of non-isomorphic 4-uniform hypergraphs, [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Hypergraph H and the fractured hypergraph H♮⃗ρ with respect to the fracture ⃗ρ = {{e1}, {e2}}, ⊤, . . . , ⊤  . 2.1.4 Fractures of Hypergraphs Similar to fractures in graphs [45], we define hypergraph fractures and fractured hypergraphs. Definition 2.8 (Hypergraph Frac…
Figure 5
Figure 5. Figure 5: A Venn diagram with its 7 sections [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: A hypergraph and its associated Venn diagram. It can also be encoded as the binary vector, [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: Examples of ∆(j1, j2, j3) and Γ(j1, j2, j3). 4 The Homomorphism Basis for Non-Degenerate Venn Diagrams In Corollary 3.4, we have shown that coeffH,V (⊤⃗ ) = X ⃗σ∈L(H,V) Y v∈V (H) (−1)|σv|−1 · (|σv| − 1)! . In the current section, for each non-degenerate Venn diagram V,…
Figure 8
Figure 8. Figure 8: The resulting fractured hypergraphs of H = Γ(1, 0, 0) from splitting vertices b, c, and d, respectively, and their representative Venn diagrams. First, since x has degree 1, ⃗σx = ⊤. Next, for satisfying V14, a vertex of degree 3 is necessary; this can only be achieved…
Figure 2
Figure 2. Figure 2: Theorem 5.4 (Main Theorem, Upper Bound). Let V be a Venn diagram. The problem #HyperMotif(V) can be solved in FPT near-quadratic time, that is, there is a computable function f such that the problem can be solved in time f(rank(G)) · O˜(|G| 2 ). Moreover, if V is degen…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 3 linked inside Pith

  1. [1]

    Popular conjectures imply strong lower bounds for dynamic problems

    Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434–443. IEEE Computer Society, 2014

    2014

  2. [2]

    Beyond Pairwise Clustering

    Sameer Agarwal, Jongwoo Lim, Lihi Zelnik-Manor, Pietro Perona, David Kriegman, and Serge Belongie. Beyond Pairwise Clustering. In2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’05), volume 2, pages 838–845, 2005

    2005

  3. [3]

    Ahmed, Jennifer Neville, Ryan A

    Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick G. Duffield. Efficient graphlet counting for large networks. In Charu C. Aggarwal, Zhi-Hua Zhou, Alexander Tuzhilin, Hui Xiong, and Xindong Wu, editors,2015 IEEE International Conference on Data Mining, ICDM 2015, Atlantic City, NJ, USA, November 14-17, 2015, pages 1–10. IEEE Computer Society, 2015. 32

    2015

  4. [4]

    Parameterised holant prob- lems.CoRR, abs/2409.13579, 2024

    Panagiotis Aivasiliotis, Andreas G¨ obel, Marc Roth, and Johannes Schmitt. Parameterised holant prob- lems.CoRR, abs/2409.13579, 2024

    arXiv 2024

  5. [5]

    Parameterised holant prob- lems

    Panagiotis Aivasiliotis, Andreas G¨ obel, Marc Roth, and Johannes Schmitt. Parameterised holant prob- lems. In Keren Censor-Hillel, Fabrizio Grandoni, Jo¨ el Ouaknine, and Gabriele Puppis, editors,52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, volume 334 ofLIPIcs, pages 7:1–7:14. Schlos...

    2025

  6. [6]

    Cenk Sahinalp

    Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S. Cenk Sahinalp. Biomolec- ular network motif counting and discovery by color coding.Bioinformatics, 24(13):i241–i249, 07 2008

    2008

  7. [7]

    Clustering in graphs and hypergraphs with categorical edge labels

    Ilya Amburg, Nate Veldt, and Austin Benson. Clustering in graphs and hypergraphs with categorical edge labels. InProceedings of The Web Conference 2020, pages 706–717, April 2020

    2020

  8. [8]

    On the desirability of acyclic database schemes.J

    Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. On the desirability of acyclic database schemes.J. ACM, 30(3):479–513, 1983

    1983

Show all 56 references
  1. [9]

    Benson, Rediet Abebe, Michael T

    Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. Simplicial closure and higher-order link prediction.Proceedings of the National Academy of Sciences, 2018

    2018

  2. [10]

    (The relevance of the list: propositional logic and complexity of the first order)

    Johann Brault-Baron.De la pertinence de l’´ enum´ eration : complexit´ e en logiques propositionnelle et du premier ordre. (The relevance of the list: propositional logic and complexity of the first order). PhD thesis, University of Caen Normandy, France, 2013

    2013

  3. [11]

    Hypergraph acyclicity revisited.ACM Comput

    Johann Brault-Baron. Hypergraph acyclicity revisited.ACM Comput. Surv., 49(3):54:1–54:26, 2016

    2016

  4. [12]

    The complexity of counting small sub-hypergraphs.CoRR, abs/2506.14081, 2025

    Marco Bressan, Julian Brinkmann, Holger Dell, Marc Roth, and Philip Wellnitz. The complexity of counting small sub-hypergraphs.CoRR, abs/2506.14081, 2025

    2025 arXiv

  5. [13]

    The parameterised complexity of counting small sub-hypergraphs

    Marco Bressan, Julian Brinkmann, Holger Dell, Marc Roth, and Philip Wellnitz. The parameterised complexity of counting small sub-hypergraphs. In Kasper Green Larsen and Barna Saha, editors,Pro- ceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, V...

    2026

  6. [14]

    Counting subgraphs in somewhere dense graphs.SIAM J

    Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, and Marc Roth. Counting subgraphs in somewhere dense graphs.SIAM J. Comput., 53(5):1409–1438, 2024

    2024

  7. [15]

    Counting answers to existential positive queries: A complexity classifi- cation

    Hubie Chen and Stefan Mengel. Counting answers to existential positive queries: A complexity classifi- cation. In Tova Milo and Wang-Chiew Tan, editors,Proceedings of the 35th ACM SIGMOD-SIGACT- SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, U...

    2016

  8. [16]

    Juedes, Iyad A

    Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems.Inf. Comput., 201(2):216–231, 2005

    2005

  9. [17]

    Kanj, and Ge Xia

    Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity.J. Comput. Syst. Sci., 72(8):1346–1367, 2006

    2006

  10. [18]

    Understanding the Complexity of Induced Subgraph Isomorphisms

    Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. InProc. of ICALP, pages 587–596, 2008

    2008

  11. [19]

    Homomorphisms are a good basis for counting small subgraphs

    Radu Curticapean, Holger Dell, and D´ aniel Marx. Homomorphisms are a good basis for counting small subgraphs. InProc. of ACM STOC, pages 210–223, 2017

    2017

  12. [20]

    Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts

    Radu Curticapean and D´ aniel Marx. Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. InProc. of IEEE FOCS, pages 130–139, 2014

    2014

  13. [21]

    Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D´ aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer, 2015. 33

    2015

  14. [22]

    The complexity of counting homomorphisms seen from the other side.Theor

    V´ ıctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side.Theor. Comput. Sci., 329(1-3):315–323, 2004

    2004

  15. [23]

    Counting induced subgraphs: An algebraic approach to #w[1]-hardness.Algorithmica, 84(2):379–404, 2022

    Julian D¨ orfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting induced subgraphs: An algebraic approach to #w[1]-hardness.Algorithmica, 84(2):379–404, 2022

    2022

  16. [24]

    Counting small induced subgraphs with edge-monotone properties

    Simon D¨ oring, D´ aniel Marx, and Philip Wellnitz. Counting small induced subgraphs with edge-monotone properties. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, ...

    2024

  17. [25]

    Counting small induced subgraphs with hereditary properties.SIAM J

    Jacob Focke and Marc Roth. Counting small induced subgraphs with hereditary properties.SIAM J. Comput., 53(2):189–220, 2024

    2024

  18. [26]

    Gonzalo Gomez-Sanchez, Luisa Delgado-Serrano, David Carrera, David Torrents, and Josep Ll. Berral. Clustering and graph mining techniques for classification of complex structural variations in cancer genomes.Scientific Reports, 12(1):3244, February 2022

    2022

  19. [27]

    Hypertree decompositions and tractable queries

    Georg Gottlob, Nicola Leone, and Francesco Scarcello. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci., 64(3):579–627, 2002

    2002

  20. [28]

    Marc H. Graham. On the universal relation. Technical report, University of Toronto, Toronto, Ontario, Canada, 1979

    1979

  21. [29]

    The complexity of homomorphism and constraint satisfaction problems seen from the other side.J

    Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side.J. ACM, 54(1):1:1–1:24, 2007

    2007

  22. [30]

    Constraint solving via fractional edge covers.ACM Trans

    Martin Grohe and D´ aniel Marx. Constraint solving via fractional edge covers.ACM Trans. Algorithms, 11(1):4:1–4:20, 2014

    2014

  23. [31]

    Yuchi Huang, Qingshan Liu, Shaoting Zhang, and Dimitris N. Metaxas. Image retrieval via probabilistic hypergraph ranking. In2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pages 3376–3383, June 2010

    2010

  24. [32]

    AHP: learning to negative sample for hyperedge prediction

    Hyunjin Hwang, Seungwoo Lee, Chanyoung Park, and Kijung Shin. AHP: learning to negative sample for hyperedge prediction. In Enrique Amig´ o, Pablo Castells, Julio Gonzalo, Ben Carterette, J. Shane Culpepper, and Gabriella Kazai, editors,SIGIR ’22: The 45th International ACM SI...

    2022

  25. [33]

    Learning on Weighted Hypergraphs to Integrate Protein Interactions and Gene Expressions for Cancer Outcome Prediction

    TaeHyun Hwang, Ze Tian, Rui Kuangy, and Jean-Pierre Kocher. Learning on Weighted Hypergraphs to Integrate Protein Interactions and Gene Expressions for Cancer Outcome Prediction. In2008 Eighth IEEE International Conference on Data Mining, pages 293–302, December 2008

    2008

  26. [34]

    On the Complexity of k-SAT.J

    Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT.J. Comput. Syst. Sci., 62(2):367–375, 2001

    2001

  27. [35]

    Adaptive Hypergraph Learning and its Application in Image Classification.IEEE Transactions on Image Processing, 21, 2012

    Jun Yu, Dacheng Tao, and Meng Wang. Adaptive Hypergraph Learning and its Application in Image Classification.IEEE Transactions on Image Processing, 21, 2012

    2012

  28. [36]

    Topological network alignment uncovers biological function and phylogeny.Journal of the Royal Society Interface, 7(50):1341–1354, 2010

    Oleksii Kuchaiev, Tijana Milenkovi´ c, Vesna Memiˇ sevi´ c, Wayne Hayes, and Nataˇ sa Prˇ zulj. Topological network alignment uncovers biological function and phylogeny.Journal of the Royal Society Interface, 7(50):1341–1354, 2010

    2010

  29. [37]

    Hypergraph motifs: Concepts, algorithms, and discoveries

    Geon Lee, Jihoon Ko, and Kijung Shin. Hypergraph motifs: Concepts, algorithms, and discoveries. Proc. VLDB Endow., 13(11):2256–2269, 2020

    2020

  30. [38]

    Hypergraph motifs and their extensions beyond binary.VLDB J., 33(3):625–665, 2024

    Geon Lee, Seokbum Yoon, Jihoon Ko, Hyunju Kim, and Kijung Shin. Hypergraph motifs and their extensions beyond binary.VLDB J., 33(3):625–665, 2024. 34

    2024

  31. [39]

    Link prediction in social networks based on hypergraph

    Dong Li, Zhiming Xu, Sheng Li, and Xin Sun. Link prediction in social networks based on hypergraph. InProceedings of the 22nd International Conference on World Wide Web, pages 41–42, May 2013

    2013

  32. [40]

    American Mathematical Society, 2012

    L´ aszl´ o Lov´ asz.Large Networks and Graph Limits, volume 60 ofColloquium Publications. American Mathematical Society, 2012

    2012

  33. [41]

    Tractable hypergraph properties for constraint satisfaction and conjunctive queries.J

    D´ aniel Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries.J. ACM, 60(6):42:1–42:51, 2013

    2013

  34. [42]

    Lower bounds for conjunctive query evaluation.CoRR, abs/2506.17702, 2025

    Stefan Mengel. Lower bounds for conjunctive query evaluation.CoRR, abs/2506.17702, 2025

    2025 arXiv

  35. [43]

    Lower bounds for conjunctive query evaluation

    Stefan Mengel. Lower bounds for conjunctive query evaluation. In Floris Geerts and Benny Kimelfeld, editors,Companion of the 44th Symposium on Principles of Database Systems, PODS 2025, Berlin, Germany, June 22-27, 2025, page 5. ACM, 2025

    2025

  36. [44]

    R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network Mo- tifs: Simple Building Blocks of Complex Networks.Science, 298(5594):824–827, 2002. eprint: https://www.science.org/doi/pdf/10.1126/science.298.5594.824

    2002 doi

  37. [45]

    Parameterized counting and cayley graph expanders.SIAM J

    Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina, and Philip Wellnitz. Parameterized counting and cayley graph expanders.SIAM J. Discret. Math., 37(2):405–486, 2023

    2023

  38. [46]

    Counting and finding homomorphisms is universal for parameterized complexity theory

    Marc Roth and Philip Wellnitz. Counting and finding homomorphisms is universal for parameterized complexity theory. In Shuchi Chawla, editor,Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2161–218...

    2020

  39. [47]

    Query answering exploiting structural properties.SIGMOD Rec., 34(3):91–99, 2005

    Francesco Scarcello. Query answering exploiting structural properties.SIGMOD Rec., 34(3):91–99, 2005

    2005

  40. [48]

    StreaM - A Stream-Based Algo- rithm for Counting Motifs in Dynamic Graphs

    Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. StreaM - A Stream-Based Algo- rithm for Counting Motifs in Dynamic Graphs. InAlgorithms for Computational Biology, pages 53–67, Cham, 2015

    2015

  41. [49]

    Network motifs in the transcriptional regulation network of escherichia coli.Nature Genetics, 31(1):64–68, 2002

    Shai Shen-Orr, Ron Milo, Shmoolik Mangan, and Uri Alon. Network motifs in the transcriptional regulation network of escherichia coli.Nature Genetics, 31(1):64–68, 2002

    2002

  42. [50]

    Stanley.Enumerative Combinatorics

    Richard P. Stanley.Enumerative Combinatorics. Cambridge Studies in Advanced Mathematics. Cam- bridge University Press, 2 edition, 2011

    2011

  43. [51]

    Counting motifs in the human interactome.Nature communications, 4(1):1–8, 2013

    Ngoc Hieu Tran, Kwok Pui Choi, and Louxin Zhang. Counting motifs in the human interactome.Nature communications, 4(1):1–8, 2013

    2013

  44. [52]

    Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher

    Charalampos E. Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher. Scalable motif-aware graph clustering. InProc. of WWW, page 1451–1460, 2017

    2017

  45. [53]

    Kleinberg

    Johan Ugander, Lars Backstrom, and Jon M. Kleinberg. Subgraph frequencies: mapping the empirical and extremal geography of large graph collections. In Daniel Schwabe, Virg´ ılio A. F. Almeida, Hartmut Glaser, Ricardo Baeza-Yates, and Sue B. Moon, editors,22nd International Wor...

    2013

  46. [54]

    Algorithms for acyclic database schemes

    Mihalis Yannakakis. Algorithms for acyclic database schemes. InVery Large Data Bases, 7th Interna- tional Conference, September 9-11, 1981, Cannes, France, Proceedings, pages 82–94. IEEE Computer Society, 1981

    1981

  47. [55]

    C. T. Yu and M. Z. Ozsoyoglu. An algorithm for tree-query membership of a distributed query. In The IEEE Computer Society’s Third International Computer Software and Applications Conference, COMPSAC 1979, 6-8 November, 1979, Chicago, Illinois, USA, pages 306–312. IEEE, 1979. 35

    1979

  48. [56]

    Learning with hypergraphs: Clustering, classification, and embedding

    Dengyong Zhou, Jiayuan Huang, and Bernhard Sch¨ olkopf. Learning with hypergraphs: Clustering, classification, and embedding. InAdvances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancou...

    2006

Pith tools

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