Graph Mining

Counting Subgraphs in Degenerate Graphs
A tighter characterization of the subgraphs for which the homomorphism count can be obtained in near-linear time in sparse graphs.
Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, Asaf Shapira
PDF Arxiv Version
Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles
A characterization of the pattern subgraphs for which the homomorphism count can be obtained in near-linear time in sparse graphs.
PDF Arxiv Version
How to Count Triangles, without Seeing the Whole Graph

Triangle counting is a fundamental problem in the analysis of large graphs. There is a rich body of work on this problem, in varying …
Suman K. Bera, C. Seshadhri
PDF Code Video Arxiv Version
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six

We consider the problem of counting all $k$-vertex subgraphs in an input graph, for any constant $k$. This problem (denoted …
PDF Arxiv Version