PaperlayerView exact revision on arXiv

Source-linked AI summary

Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions

Ahmet Erdem Sariyuce, C. Seshadhri, Ali Pinar, Umit V. Catalyurek

arXiv:1411.3312v2cs.SI

TL;DR

Many dense-subgraph formulations are NP-hard, and graph analysis often needs many structures and their relationships rather than a single optimum. The paper builds an exact, efficient nucleus hierarchy and reports dense outputs with quality comparable to or better than prior algorithms, while processing a 39-million-edge graph in less than an hour.

  • Problem

    Many dense-subgraph formulations are NP-hard, and graph analysis seeks many dense subgraphs and their relationships rather than a single optimum.

    Source: §1.1 · p. 2

  • Method

    The paper defines nucleus decompositions as hierarchies of maximal subgraphs where each r-clique participates in many s-cliques, and gives an exact, efficient construction algorithm.

    Source: §1.2 · p. 2

  • Results

    Nucleus outputs are generally denser than the comparison algorithms’ outputs with comparable or larger sizes, and the method processes a 39-million-edge graph in less than an hour.

    Source: §5.2.1 · p. 8, §5.4 · p. 10

  • Takeaways & Limitations

    The (3, 4)-nucleus forest provides a hierarchical view of dense substructures, with the authors reporting it as their highest-quality choice among tested parameters.

    Source: §5 · p. 6

    Preliminary experiments found little benefit from larger r, s choices, while clique enumeration becomes forbiddingly costly and storing 4-cliques is infeasible space-wise.

    Source: §6 · p. 10

Abstract

from arXiv · show

Finding dense substructures in a graph is a fundamental graph mining operation, with applications in bioinformatics, social networks, and visualization to name a few. Yet most standard formulations of this problem (like clique, quasiclique, k-densest subgraph) are NP-hard. Furthermore, the goal is rarely to find the "true optimum", but to identify many (if not all) dense substructures, understand their distribution in the graph, and ideally determine relationships among them. Current dense subgraph finding algorithms usually optimize some objective, and only find a few such subgraphs without providing any structural relations. We define the nucleus decomposition of a graph, which represents the graph as a forest of nuclei. Each nucleus is a subgraph where smaller cliques are present in many larger cliques. The forest of nuclei is a hierarchy by containment, where the edge density increases as we proceed towards leaf nuclei. Sibling nuclei can have limited intersections, which enables discovering overlapping dense subgraphs. With the right parameters, the nucleus decomposition generalizes the classic notions of k-cores and k-truss decompositions. We give provably efficient algorithms for nucleus decompositions, and empirically evaluate their behavior in a variety of real graphs. The tree of nuclei consistently gives a global, hierarchical snapshot of dense substructures, and outputs dense subgraphs of higher quality than other state-of-the-art solutions. Our algorithm can process graphs with tens of millions of edges in less than an hour.

1. INTRODUCTION

Dense-subgraph analysis seeks many related structures across scales, but common formulations are NP-hard and existing objectives do not provide a global hierarchy. The paper introduces nucleus decompositions and shows they organize dense subgraphs by containment, density, and branching.

1.1 The challenges of dense subgraphs

  • Most dense-subgraph formulations are NP-hard, while graph analysis needs many structures and their relationships rather than only one optimum.The motivating questions ask for a global hierarchy and an efficiently solvable objective that directly yields many dense subgraphs.Source: §1.1 · p. 2

1.2 Our contributions

  • An (r, s)-nucleus is a maximal subgraph in which every r-clique belongs to many s-cliques, and incomparable nuclei cannot share an r-clique.Nucleus decompositions generalize k-cores and k-trusses.Source: §1.2 · p. 2
  • For any r < s, nuclei form a hierarchy that becomes denser toward the leaves, and an exact, efficient algorithm computes the decomposition.The authors report that (3, 4)-nuclei were feasible on a 39-million-edge graph in less than an hour.Source: §1.2 · p. 2
  • The (3, 4)-nuclei provide dense subgraphs across a wide range of sizes and densities, with outputs of comparable quality to recent algorithms [43].The facebook example contains 403 nuclei of at least 10 vertices, with many densities close to 1.Source: §1.2 · p. 2
  • The forest encodes containment through ancestor-descendant links; branching represents different graph regions, and incomparable nuclei do not share a triangle.Figure 3 illustrates the facebook forest, with long chains contracted for presentation.Source: Figure 3 · p. 2, §1.2 · p. 3
  • Nuclei become denser toward the leaves, while larger parent subgraphs can retain moderate density; sibling nuclei may overlap in vertices despite not sharing triangles.The authors observe sibling intersections of 4–6 vertices in about 20 pairs, and more pairs with larger intersections in larger graphs.Source: §1.2 · p. 3

2. PREVIOUS WORK

Previous work includes efficient methods for specific dense-subgraph objectives and global decompositions such as k-cores and k-trusses. The authors distinguish their goal of a global hierarchy from methods aimed at only a few dense subgraphs.

Dense subgraph algorithms

  • Existing dense-subgraph methods include polynomial-time objectives and approximation algorithms, as well as practical core-based, clique, and quasi-clique methods [44].The paper treats Tsourakakis et al. as the state-of-the-art comparison and notes that those algorithms are faster than the authors’ method.Source: §2 · p. 3
  • These objective-focused methods typically find one or a few dense subgraphs, rather than providing a global hierarchical view.The authors suggest relating these methods to nuclei as a direction for designing better algorithms.Source: §2 · p. 3

k-cores and k-trusses

  • K-cores, k-trusses, k-plexes, and k-clubs provide other subgraph notions; these methods find moderately dense subgraphs and support global decomposition for visualization.A k-core constrains vertex minimum degree, while a k-truss constrains each edge’s triangle participation.Source: §2 · p. 3

3. NUCLEUS DECOMPOSITION

Nucleus decompositions organize clique-based dense subgraphs into a containment forest, with density increasing toward the leaves. Their clique-connectivity conditions allow distinct nuclei to overlap while retaining a laminar hierarchy.

3. NUCLEUS DECOMPOSITION

  • A k-(r, s)-nucleus is a maximal union of s-cliques where every contained r-clique has S-degree at least k and the r-cliques are S-connected.S-degree counts the s-cliques containing an r-clique; S-connectedness links r-cliques through shared s-cliques.Source: §3 · p. 3
  • For fixed k and r, nuclei on the same number of vertices become denser as s increases, because each edge must participate in more larger cliques.The example contrasts 2-(2, 3) and 2-(2, 4) nuclei; every edge in the latter participates in at least two K4s.Source: §3 · p. 4, Figure 4 · p. 4
  • Setting (r, s) to (1, 2) recovers k-cores, while (2, 3) gives a definition essentially equivalent to k-trusses or triangle-cores.The (2, 3) version also requires triangle-connectedness.Source: §3 · pp. 3–4
  • The (r, s)-nuclei form a laminar family represented as a forest, with each nucleus attached to its smallest containing nucleus.The parent is the smallest-by-cardinality other nucleus that contains the child.Source: §3 · p. 4
  • Incomparable nuclei cannot share an r-clique, yet for r > 2 distinct nuclei can overlap on edges and reveal dense subgraphs that edge-disjoint decompositions miss.The paper illustrates this with two 1-(3, 4)-nuclei, each a K4, intersecting at an edge.Source: §3 · p. 4

4. GENERATING NUCLEUS DECOMPOSITIONS

The algorithm adapts core decomposition to a hypergraph of cliques, then recovers nuclei from connected components at processing thresholds. Its complexity depends on clique enumeration, with a lower-space implementation used for (3, 4)-nuclei.

4. GENERATING NUCLEUS DECOMPOSITIONS

  • The algorithm adapts Matula-Beck core decomposition by processing r-cliques in a hypergraph, since a larger s-clique can contain multiple r-cliques.A direct ordinary-graph analogy works for (r, s) = (1, 2), but not in general.Source: §4 · p. 4
  • set-k assigns each r-clique a κ value while processing cliques in non-decreasing order of degree and maintaining their counts of containing s-cliques.The κ sequence is non-decreasing; processing times define the thresholds used to form G_tk.Source: §4 · pp. 4–5
  • The k-(r, s)-nuclei are exactly the links of connected components of G_tk, allowing the algorithm to recover nuclei from thresholded clique connectivity.The forest is built by traversing components in reverse order of k and avoiding repeated traversal of already determined components.Source: §4 · p. 5

4.1 Bounding the complexity

  • The forest can be built in O(RTr(G) + RTs(G)) time and O(ctr(G) + cts(G)) space, or in O(RTr(G) + sum_v ctr(v)d(v)^(s-r)) time and O(ctr(G)) space.These bounds correspond to storing the clique supergraph or generating adjacencies as needed.Source: §4.1 · p. 5
  • For (3, 4)-nuclei, the implementation uses the lower-space option because K4 storage is too large; it scales to tens of millions of edges with little difficulty.The stated running time is bounded using triangle counts and clustering coefficients, which generally decay with degree.Source: §4.1 · p. 6

5. EXPERIMENTAL RESULTS

Across varied real-world graphs, (3, 4)-nuclei provide hierarchical dense-subgraph forests, many subgraphs across sizes and densities, and restricted overlaps. They generally compare favorably with OQC outputs, while construction remains feasible on graphs with tens of millions of edges.

5. EXPERIMENTAL RESULTS

  • Among tested choices with r < s ≤ 4, (3, 4)-nuclei generally provide the strongest hierarchy and density.The experiments covered a variety of graphs, and the authors report constructing these forests for all graphs in the dataset.Source: §5 · p. 6

5.1 The forest of nuclei

  • In every computed (3, 4)-forest, smaller dense nuclei tend to nest within larger, less dense nuclei, producing prominent branching.Leaves are almost always above 0.8 density, while larger nuclei include intermediate densities; the wikipedia-200611 forest has about 4,000 nuclei.Source: §5.1 · p. 6

5.2 Dense subgraph discovery

  • The (3, 4)-forests yield many nuclei across sizes and densities, including near-cliques and subgraphs with density around 0.2.Across the graphs, the number of nuclei with density at least 0.5 is in the hundreds and exceeds a thousand for wikipedia-200611.Source: §5.2 · p. 6

5.2.1 Comparisons with previous art

  • Barring four instances, a (3, 4)-nucleus is larger and denser than the OQC output; in all but adjnoun, one also has higher density.OQC can run faster, while the nucleus decomposition is deterministic; on wikipedia-200611, OQC sometimes finds larger, denser instances, but smaller nuclei are significantly denser.Source: Table 1 · p. 7, §5.2.1 · p. 8

5.3 Overlapping nuclei

  • (3, 4)-nuclei retain restricted overlaps: pairwise overlaps are typically about half as numerous as nuclei, with Jaccard similarities below 0.1.Significant overlaps between dense clusters occur especially in web-NotreDame and wikipedia-200611; other parameter settings show almost no overlap.Source: §5.3 · pp. 8–9, Figure 12 · p. 9

5.4 Runtime results

  • The most expensive (3, 4)-nucleus construction took less than an hour on wikipedia-200611, producing about 6,000 nuclei with more than 10 vertices.Most of these nuclei had density of at least 0.4; the runtime bound roughly correlates with observed running time.Source: §5.4 · p. 10

6. FURTHER DIRECTIONS

The authors outline future work on bioinformatics applications, parameter choices, faster computation, and incremental maintenance. These directions focus on testing nuclei’s usefulness and improving their practical reach.

6. FURTHER DIRECTIONS

  • The authors are investigating protein–protein and protein–gene interaction networks to test whether (3, 4)-nuclei identify specific functional units.They expect a global view of dense substructures could be useful to biologists; identifying such units would validate dense-subgraph analyses for bioinformatics.Source: §6 · p. 10
  • Larger r and s values offered little preliminary benefit for the forest or nucleus density, while clique enumeration became forbiddingly costly.The authors suggest triangle-based nuclei may suffice, but frame this as a possibility for future theoretical support.Source: §6 · p. 10
  • A faster (3, 4)-nuclei algorithm remains desirable because storing 4-cliques is infeasible in space.The authors seek a method or data structure to quickly determine which 4-cliques contain a given triangle.Source: §6 · p. 10
  • The authors seek incremental algorithms that maintain (r, s)-nuclei as edges arrive in a stream.They suggest adapting existing streaming k-core techniques.Source: §6 · p. 10
Loading 1411.3312v2…