CS Paper Radar

Finding Many Overlapping Dense Subgraphs Using Triadic Cohorts

Sabyasachi Basu, C. Seshadhri

cs.SI cs.DS ·submitted 2026-09-04 08:46 UTC · v1
theory

Abstract

Graphs are a standard representation for data in the social sciences, cybersecurity, computer infrastructure, bioinformatics, and more. Typical real-world graphs are sparse, meaning the average degree is small (in the tens, while the number of vertices is more than millions). When graph data is collected from a source, a major task is to perform data exploration. Thus, any region of ``density" is of interest, since it indicates special structure. An important goal is to cover a significant portion of the graph using dense subgraphs. Existing algorithms that find many dense subgraphs do not have overlapping output, and hence provide limited coverage. Other methods that produce overlapping clusters do not generate dense subgraphs. The main goal of this paper is to develop provable and practical methods that can provide overlapping dense subgraphs that can cover large portions of real-world networks. Our contribution is an algorithm CohortRecovery that achieves this goal. We first develop a mathematical framework of triadic cohorts that captures the notion of ``detectable dense subgraphs'' that potentially overlap. We prove that CohortRecovery can output a set of dense subgraphs, such that each triadic cohort is almost completely contained in some dense subgraph. We give a practical implementation of CohortRecovery and demonstrate it on a variety of datasets. It typically runs in under ten minutes on a commodity machine even on graphs with tens of millions of edges. For numerous datasets, CohortRecovery is able to cover more than 25\% of the vertices in non-trivial subgraphs of density more than 0.8, and is significantly better than a wide variety of scalable graph clustering/community detection algorithms. Moreover, we demonstrate that output of CohortRecovery captures ground truth clusters obtained by manual curation.

Closest papers

Nearest neighbours by meaning across the whole index.

Faster network motif discovery by counting isomorphic subtrees

cs.DS ·2026-09-30 ·Tarek Tohme, Joshua A. Grochow
theory similarity 0.62
Abstract

We develop a new algorithm for counting the number of subgraphs of a network isomorphic to a given query graph (#SubgraphIsomorphism), motivated by network motif search. High-degree vertices (hubs), common in real-world networks, contribute to a combinatorial explosion in the number of subgraphs, making existing motif search algorithms intractable for motif sizes greater than $\approx 8$ on a wide variety of networks of interest. Our procedure leverages the $k$-core decomposition and a novel subtree-counting technique to quickly scan the periphery of a network. These two innovations allow our algorithm to significantly speed up its predecessors in practice, especially as most real-world networks have a relatively large periphery. We prove that #RootedSubtreeIsomorphism, a key subroutine in our algorithm, is #P-complete via a reduction from counting bipartite matchings. We provide analytic upper bounds on our algorithm's execution time, and evaluate its performance on 11 real-world networks of varying topologies.

0.15

Scalable Approximate Algorithm for Dynamic Densest Subhypergraphs with Solution-Guided Maintenance

cs.DB ·2026-09-30 ·Jingbang Chen, Chenhao Ma, Yingli Zhou
similarity 0.58
Abstract · 19 pages

Hypergraphs model interactions involving groups of entities, and finding highly connected groups is a fundamental task in analyzing these data. When interactions arrive and expire, maintaining a dense group can require frequent and expensive changes to the underlying representation. We propose CAP, a scalable algorithm that explicitly maintains a $(1+ε)$-approximate densest subhypergraph under hyperedge insertions and deletions. The algorithm keeps a solution candidate together with an endpoint allocation that bounds the optimum density. The candidate's density guides maintenance: an update triggers repair only when this bound is too large to establish the required approximation. Local searches redistribute load or find a denser candidate, allowing CAP to retain useful solutions across many updates. We give an analysis that relates maintenance work to the size of the regions searched and the density lost by the maintained solution. It identifies conditions under which local repair remains inexpensive and provides a theoretical explanation for the observed efficiency. Experiments on real-world hypergraphs show speedups of up to nearly four orders of magnitude over the evaluated dynamic baselines, while supporting frequent queries and high accuracy. CAP also remains competitive with specialized dynamic graph methods on ordinary graphs, with speedups of up to approximately $64\times$ on the tested workloads.

0.26

Single-Pass Estimation of the Clustering Coefficient Distribution in Graph Streams

cs.DS ·2026-09-20 ·Cristian Boldrin, C. Seshadhri
published similarity 0.58
Abstract · VLDB 2027

Triangle counting is one of the most fundamental problems in network analysis. Given the massive sizes of real-world graphs, there is a long history of small-space streaming algorithms providing accurate estimates for this problem. However, most of the results focus on estimating the total triangle count or the number of triangles incident to individual nodes. In practice, one often wants fine-grained information to understand how triangles are distributed, as captured by clustering coefficients. In particular, a standard network analysis task requires computing the binned degree-wise clustering coefficient distribution, which provides a rich and informative summary of the structure of the graph. In this work we present BOLIDE, the first efficient and practical algorithm for estimating binned degree-wise clustering coefficients in streaming. Our algorithm makes a single pass over the edge stream, and is allowed to store only a small fraction of the total number of edges. BOLIDE carefully combines different sampling strategies to efficiently gather degree and triangle information across sets of nodes. As a result, our algorithm provably approximates the binned degree-wise clustering coefficients, and provides guarantees on the amount of memory used. Our experimental evaluation shows that BOLIDE accurately estimates clustering coefficient distributions while efficiently processing large datasets with billions of edges and triangles.

0.31

Constant-Factor Local Approximation for Bipartite Densest Subgraph

cs.DS ·2026-10-16 ·Michael Kapralov, Jakub Łącki, Silvio Lattanzi, Guy Weissenberg
similarity 0.56
Abstract

Given a vertex $v$ in a large bipartite graph $G$, can one quickly find a small densely connected region near $v$? This is the algorithmic core of many fraud detection, community detection, and recommender systems. One would like a local algorithm, i.e., an algorithm that probes $G$ in only a small number of locations to find such a region. Our main contribution is the first constant-factor local approximation, independent of the maximum degree of the graph, for the classical notion of bipartite density: if the sides of a bipartite subgraph are $S$ and $T$, its density is $d(S,T):=e(S,T)/\sqrt{|S||T|}$, where $e(S,T)$ is the number of edges between $S$ and $T$. We consider cohesive dense subgraphs, since every dense subgraph contains a cohesive core of at least the same density. For such a cohesive dense subgraph $S\mathbin{\dot\cup}T$ with at most $k$ vertices per side, our algorithm, starting from any vertex in $S\mathbin{\dot\cup}T$, uses $O_ε(k^{4+ε})$ neighbor queries to find a subgraph $X\mathbin{\dot\cup}Y$ of density $Ω_ε(d(S,T))$ on $O_ε(k^{2+ε})$ vertices, for every fixed $ε>0$. Our result improves upon the result of Andersen (2010), whose approximation guarantee depends logarithmically on the maximum degree. We complement our positive result with information-theoretic and computational limitations showing that the quadratic dependence on $k$ in the output size is essentially unavoidable for constant-factor approximation. Our main technical innovation is an adaptation of the Lovász-Simonovits curve to the bipartite density problem, based on weak-$\ell_p$ norm bounds.

0.28

Faster Algorithms for Finding Small Induced Patterns in Sparse Host Graphs

cs.DS ·2026-09-30 ·Priyanshi Agrawal, Balagopal Komarath
similarity 0.56
Abstract · 38 pages, 70 figures

We study algorithms for detecting induced subgraphs corresponding to fixed pattern graphs in host graphs. We show that at least five of the 21 connected graphs on five vertices can be detected in time roughly the product of the number of vertices and the number of edges, and that at least 65 of the 112 connected graphs on six vertices can be detected in time nearly quadratic in the number of edges. We also give algorithms for detecting induced paths and cycles on seven vertices, running in time roughly the number of vertices times the square of the number of edges. Our main technical tool is a generalized notion of tree decomposition width, called (p, q)-width. It yields algorithms whose running times depend on both the number of vertices and the number of edges, and are never worse than existing bounds. Whenever the host graph has fewer than roughly quadratically many edges in its number of vertices, our bounds are strictly faster. For some patterns, including the seven-vertex cycle, our algorithms are optimal under standard complexity-theoretic assumptions. We further develop this approach using pattern-based polynomials that exploit the structure of tree decompositions, not just their width. This gives algorithms for detecting induced paths and cycles on an even number of vertices in bipartite graphs, running in time roughly the (k-1)-th power of the number of edges for paths on 2k vertices, and that same bound times the number of vertices for cycles on 2k vertices. These are faster than the best known algorithms for general graphs.

0.16

AutoGraphForge: Towards Automated Graph Theory Discovery

cs.AI cs.LOmath.CO ·2026-09-03 ·Ján Pastorek
theorycode/data similarity 0.56
Abstract · 17 pages, 1 figure, 3 tables. Submitted to ITAT 2026 (Information Technologies -- Applications and Theory), CEUR Workshop Proceedings. Code:…

We report on our ongoing project to develop a computational pipeline, AutoGraphForge, for an automated graph-theoretic conjecturing-refuting-formalizing-proving system. Conjecture generation is counterexample-guided and runs in rounds: a Graffiti3 generator proposes conjectures over a small, evolving snapshot table $T$ (initially a few hundred graphs with their computed invariants) that grows only by counterexamples to its own conjectures. A novelty filter of $559$ classical and folklore relations, closed under transitive composition and linear identity substitution, decides via a linear program whether a candidate is already implied by known results. Surviving candidates are tested against a dataset of about $348,000$ graphs, unioning the complete House of Graphs invariant export, the exhaustive census of all connected graphs on at most nine vertices, several extremal families (strongly regular, minimal Ramsey, Cayley, cages, barbells, lollipops, spiders), and random models. Counterexample-search algorithms then attack the remainder. Run for several rounds on an HPC cluster, the loop yields $6,522$ conjectures that survived the refutation dataset, the novelty filter and every active-search run -- among them nontrivial relations between the annihilation number and the edge-cover number for bipartite and regular graphs, which we prove by hand. A subsequent formalization and proving stage deterministically translates each surviving conjecture into a Lean 4 statement skeleton; every candidate proof is kernel-verified against a pinned mathlib4 and our custom invariant preamble. This stage integrates two neural provers -- DeepSeek-Prover-V2-671B (served with vLLM) and the Lean-specialised OProver-32B -- behind the independent kernel check. It is implemented end-to-end and passes initial sanity checks, with the full pipeline currently running on the cluster.

0.43

The Power of Bidegeneracy for Hypergraph Data Structures

cs.DS cs.DBcs.DM ·2026-11-03 ·Marco Bressan, Stefano Clemente, Giacomo Fumagalli, Daniel Paul-Pena, C. Seshadhri
similarity 0.56
Abstract

A hypergraph $H = (V,E)$ describes a set system over a vertex universe $V$. Hypergraphs are increasingly popular in network science, as they represent interactions between subsets of vertices. A natural challenge is to design a data structure for $H$ to quickly answer basic questions about it, e.g. how many neighbors a vertex $v$ has or whether a hyperedge contains a vertex subset $S$. Such questions are trivial for graphs, for which we simply inspect the adjacency list. The gold standard, from a data structures perspective, would be near-linear time preprocessing and query answering in (poly)logarithmic time. Since this is unlikely for arbitrary $H$, we ask for well-motivated hypergraph properties that can make such a goal possible. We introduce bidegeneracy, a measure of hypergraph sparsity that strictly generalizes many other measures, including bounded degree, bounded rank, and bounded $\infty$-degeneracy. We show that bounded bidegeneracy yields fast hypergraph data structures. For a large set of fundamental queries, including their listing and sampling versions, we obtain near-linear preprocessing and (poly)logarithmic query time. Moreover, direct reductions from assumptions like the Orthogonal Vectors Conjecture suggest that, without assumptions on the input, these structures require almost-quadratic preprocessing or almost-linear query time. We use bidegeneracy to compute a compressed representation of $H$ and perform careful reductions to stabbing and searching problems in $\mathbb{R}^d$. Our framework significantly extends the well-studied "partial matching" problem of finding database entries through wildcard search. It also uncovers an intriguing connection between hypergraph sparsity, compression, and the complexity of hypergraph primitives. We also find remarkably low bidegeneracy in hypergraph datasets from the literature, suggesting practical consequences.

0.25

Fully Dynamic Triangle and 4-Vertex Subgraph Counting: From Theory to Practice and Back Again

cs.DS ·2026-10-21 ·Kathrin Hanauer, Sophia Heck, Monika Henzinger, Leonhard Sidl
published similarity 0.56
Abstract · Short version to appear at ALENEX 2027

Counting small patterns is a core primitive in large-scale graph analytics, with numerous applications in data management and network analysis. As modern graphs are massive and continuously evolving, maintaining such counts efficiently under updates is essential. Although specialized dynamic algorithms for patterns with up to four vertices exist, they remain largely theoretical; practitioners instead rely on general-purpose or approximate methods. We present an in-depth study of two dynamic approaches by Eppstein et al. and Hanauer et al. for maintaining counts of triangles and all connected four-vertex subgraph patterns, both based on variants of heavy-light vertex partitioning. We introduce theoretical and practical optimizations and develop hybrid variants that combine complementary strengths of both approaches. Experiments on 56 large real-world and synthetic dynamic graphs show that our optimized algorithms outperform the original methods and strong static and dynamic baselines on nearly all instances, both in total running time and worst-case update time, with speedups of up to several orders of magnitude. We further provide practical guidelines for algorithm selection and tuning. To the best of our knowledge, this is the first comprehensive empirical study of heavy-light partitioning for dynamic subgraph counting, and our findings may inform other algorithms based on this technique.

0.39