PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Algorithms for Densest Subgraph Discovery

Yixiang Fang, Kaiqiang Yu, Reynold Cheng, Laks V. S. Lakshmanan, Xuemin Lin

arXiv:1906.00341v2cs.DBcs.SI

TL;DR

DSD asks for the subgraph with the highest density, including under h-clique-density. This paper uses cores to build exact and approximation algorithms, extending them to pattern-density; its experiments report speedups over existing approaches.

  • Problem

    DSD seeks a subgraph with the highest density, including under h-clique-density.

    Source: §3 · p. 3

  • Method

    The paper uses k-cores and (k, Ψ)-cores to develop exact and approximation algorithms, extending the core-based approach to pattern-density.

    Source: §1 · pp. 1–2

  • Results

    CoreExact is up to four orders of magnitude faster than the state-of-the-art exact solution, and CoreApp is up to two orders faster than the existing approximation solution.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The core-based solutions extend beyond edge- and h-clique-density to densest-subgraph discovery under pattern-density.

    Source: §9 · p. 12

    The (kmax, Ψ)-core approximation may not contain the densest subgraph or share any vertices with it.

    Source: §6.2 · p. 7

Abstract

from arXiv · show

Densest subgraph discovery (DSD) is a fundamental problem in graph mining. It has been studied for decades, and is widely used in various areas, including network science, biological analysis, and graph databases. Given a graph G, DSD aims to find a subgraph D of G with the highest density (e.g., the number of edges over the number of vertices in D). Because DSD is difficult to solve, we propose a new solution paradigm in this paper. Our main observation is that a densest subgraph can be accurately found through a k-core (a kind of dense subgraph of G), with theoretical guarantees. Based on this intuition, we develop efficient exact and approximation solutions for DSD. Moreover, our solutions are able to find the densest subgraphs for a wide range of graph density definitions, including clique-based and general pattern-based density. We have performed extensive experimental evaluation on eleven real datasets. Our results show that our algorithms are up to four orders of magnitude faster than existing approaches.

1. INTRODUCTION

DSD seeks dense subgraphs under edge, clique, and broader pattern-based density definitions, but existing solutions can be computationally expensive. The paper uses cores to develop exact and approximation methods, with experiments reporting substantial speedups.

1. INTRODUCTION

  • The paper targets edge- and h-clique-density because existing DSD methods can be expensive, with clique-based discovery described as especially complex.An edge is the 2-clique; h-clique-density also supports finding larger near-cliques.Source: §1 · p. 1
  • A densest edge-based subgraph lies in some k-core, which can be much smaller than the full graph.The paper extends this idea to (k, Ψ)-cores for h-clique-density.Source: §1 · p. 1
  • Tight upper and lower density bounds for each (k, Ψ)-core bound ρopt and help locate the densest subgraph in selected cores.These selected cores are often much smaller than the entire graph.Source: §1 · p. 2
  • For exact discovery, the method narrows the search to a specific (k, Ψ)-core, then uses binary search and maximum flow, moving to smaller flow networks as bounds improve.For approximation, it extracts the (kmax, Ψ)-core without computing every core; that core has theoretical approximation guarantees.Source: §1 · p. 2
  • The paper generalizes density to pattern-density and extends k-clique-core to k-pattern-core so its solutions can handle arbitrary pattern graphs.A diamond is given as an example pattern.Source: §1 · p. 2
  • CoreExact is up to four orders of magnitude faster than the state-of-the-art exact solution, while CoreApp is up to two orders faster than the existing approximation solution.Experiments cover real and synthetic graphs ranging from a few thousand to millions of vertices and edges.Source: §1 · p. 2

2. RELATED WORK

Prior work studies edge- and clique-based densest-subgraph problems, alongside other dense-subgraph models. The paper distinguishes its core-based methods by their pattern coverage, deterministic approximation, and reported empirical performance.

2. RELATED WORK

  • Edge-based densest-subgraph methods include parametric maximum-flow solutions, while exact methods can perform poorly on large graphs.The greedy method in gives a 0.5-approximation; the streaming method in gives a 1/(2 + 2ε)-approximation.Source: §2 · p. 2
  • Prior h-clique densest-subgraph work generalizes edge-density, with h=2 as the edge case; triangle-dense subgraphs have been used to identify researcher groups and senator clusters.A top-k local triangle-densest-subgraphs variant is also studied.Source: §2 · p. 2
  • The paper reports that its algorithms outperform prior exact CDS algorithms [65, 49] and the deterministic approximation algorithm [65].Its core-based approximation is deterministic, unlike the randomized approximation in, which has a failure probability.Source: §2 · p. 2
  • Unlike prior CDS work limited to h-cliques, this paper supports general patterns, while other models such as k-core and k-truss do not necessarily maximize edge- or clique-density.The paper identifies these differences as distinctions from existing dense-subgraph models.Source: §2 · p. 2

3. PROBLEM DEFINITION

The paper defines densest-subgraph discovery by selecting a subgraph with the highest density under a chosen measure. It formalizes edge- and h-clique-based densities and the corresponding discovery problem.

3. PROBLEM DEFINITION

  • The paper’s data model is an undirected, unweighted, simple graph; n and m denote its vertex and edge counts.The maximum vertex degree is denoted by d.Source: §3 · p. 3
  • A clique instance is a set of h vertices connected pairwise, and a vertex’s clique-degree counts the instances containing it.The paper does not count permutations of vertices as separate instances; its triangle example has clique-degrees 2, 1, and 2 for A, B, and C.Source: §3 · p. 3
  • For an h-clique Ψ, h-clique-density is the number of Ψ clique instances divided by the number of vertices.The passage identifies μ(G, Ψ) as the number of clique instances.Source: §3 · p. 3
  • The CDS problem returns the subgraph whose h-clique-density is highest; when h=2, clique-density reduces to edge-density.The paper uses CDS for edge- or h-clique-based discovery, distinguishing EDS when needed.Source: §3 · p. 3

4. EXISTING APPROACHES

The section reviews flow-based exact and peeling-based approximation methods for densest-subgraph discovery, then identifies efficiency limits that motivate a core-based approach.

4.1 The Exact Method

  • Exact solves densest-subgraph discovery through binary search over maximum-flow cuts, while rebuilding a flow network on the full graph can be costly.The search tests whether a subgraph exceeds a guessed density using a minimum s-t cut.Source: §4.1 · p. 3, §4.3 · p. 4

4.2 The Approximation Method

  • PeelApp repeatedly removes the vertex with the fewest clique instances and returns the residual subgraph with the highest density observed.For edge density, it provides a 0.5-approximation in O(m) time, compared with Exact’s O((mn + m^3) log n) time for an exact result.Source: §4.2 · p. 4, §4.3 · p. 4

4.3 Limitations of Existing Methods

  • Existing methods can be inefficient on large graphs and complex cliques: Exact exceeded five days on a moderate 6-clique graph, while PeelApp exceeded two days at million scale.Exact also uses loose initial bounds and large full-graph flow networks; PeelApp spends effort evaluating early residual graphs unlikely to contain the densest subgraph.Source: §4.3 · p. 4

5. THE CLIQUE-BASED CORES

The section generalizes k-cores to clique-based cores and uses their density bounds and decomposition to locate dense subgraphs; it also extends the framework to general patterns.

5.1 k-core and (k, Ψ)-core

  • A (k, Ψ)-core is the largest subgraph in which every vertex participates in at least k instances of clique Ψ.These cores are nested as k increases and may be disconnected.Source: §5.1 · pp. 4–5

5.2 Density Bounds of (k, Ψ)-core

  • The section establishes lower and upper bounds for clique-core density and shows ρopt ≤ kmax; for an edge core with kmax=2, the example bounds are 1 and 2.The example graphs attain the lower bound, while a sequence of graphs approaches the upper bound.Source: §5.2 · p. 5

5.3 (k, Ψ)-core Decomposition

  • The decomposition repeatedly removes the vertex with the smallest clique-degree, updating affected vertices’ clique-degrees as clique instances disappear.The remaining graph after recursively removing vertices with clique-degree below k is the (k, Ψ)-core, when non-empty.Source: §5.3 · p. 5

5.4 Extension and Discussion

  • The framework extends to arbitrary pattern graphs, and when Ψ is a subpattern of Ψ′ with equal vertex counts, each (k, Ψ′)-core lies within the corresponding (k, Ψ)-core.For non-clique patterns, these cores differ from k-(r, s) nuclei, which are defined using cliques and require S-connectedness.Source: §5.4 · p. 6

6. CORE-BASED APPROACHES

The core-based approach narrows densest-subgraph search to relevant cores, then uses flow-based exact search or a maximum-core approximation.

6.1 The Core-Based Exact Method

  • CoreExact tightens density bounds, prunes residual and disconnected-core candidates, and progressively builds smaller flow networks.Source: §6.1 · p. 6
  • For exact CDS, the densest subgraph lies in the (k, Ψ)-core where k=⌈ρopt⌉, and CoreExact uses binary-search flow cuts there.Source: §6.1 · p. 6

6.2 The Core-Based Approximation Methods

  • The (kmax, Ψ)-core is a 1/|VΨ|-approximation to CDS, although it need not overlap the optimum.Source: §6.2 · p. 7
  • CoreApp finds the (kmax, Ψ)-core from high-clique-degree induced subgraphs, stopping when remaining vertices cannot exceed kmax.Source: §6.2 · pp. 7–8
  • CoreApp is up to two orders of magnitude faster than PeelApp and IncApp in practice.Source: §6.2 · p. 8

6.3 Discussions

  • For densest-k-subgraph queries, the minimum core number among query vertices yields a smaller core for flow search.Source: §6.3 · p. 8

7. THE PDS PROBLEM AND SOLUTIONS

The PDS problem seeks a subgraph maximizing pattern instances per vertex. The paper adapts core-based approximate and exact methods, including a grouped-instance flow network.

7.1 The PDS Problem

  • Pattern density is the number of pattern instances divided by the number of vertices, and PDS seeks a subgraph maximizing that measure.Source: §7.1 · p. 8

7.2 Algorithms for PDS Problem

  • PeelApp's pattern-degree version gives a 1/|VΨ|-approximation, and IncApp and CoreApp can also be adapted.Source: §7.2 · pp. 8–9
  • PExact correctly finds the densest subgraph under pattern-density by adapting an exact flow-based method to pattern instances and pattern-degrees.Source: §7.2 · p. 9
  • CorePExact combines k-pattern-core optimizations with construct+, which groups instances sharing vertex sets while preserving PExact's minimum st-cut capacity.Source: §7.2 · p. 9

8. EXPERIMENTS

Experiments compare exact and approximation algorithms across ten real graphs, three synthetic graphs, clique densities, and general pattern densities. The reported results favor core-based methods in speed, with performance depending on graph and pattern characteristics.

8.1 DSD for Edge- and h-Clique-Densities

  • CoreExact is at least 4.5× and up to four orders of magnitude faster than Exact on five small datasets.The authors attribute the gain to locating densest subgraphs in smaller clique-cores and reducing flow-network sizes.Source: §8.1 · p. 10, Figure 8 · p. 11
  • CoreApp is up to three orders of magnitude faster than Nucleus and two orders faster than PeelApp on the five largest datasets.CoreApp finds the maximum clique-core top-down, skipping cores with smaller clique-core numbers.Source: §8.1 · p. 10, Figure 8 · p. 11
  • More than 95% of triangle flow-network nodes are pruned after six CoreExact iterations on Ca-HepTh.The flow networks shrink as tighter lower bounds locate the densest subgraph in smaller cores; pruning decreases as clique size increases.Source: §8.1 · p. 10, Figure 9 · p. 11
  • Pruning1 supplies most CoreExact savings; Pruning2 and Pruning3 still contribute non-trivially on Ca-HepTh.Core-decomposition time is a small share of CoreExact’s cost and decreases with clique size.Source: §8.1 · p. 10, Table 3 · p. 10, Figure 10 · p. 11
  • CoreApp’s approximation ratio averages 0.956 times PeelApp’s on 6/10 instances, while both methods have the same theoretical guarantee.Their actual ratios are close to 1.0 in most cases.Source: Figure 11 · p. 11, §8.1 · p. 11
  • CoreApp is much faster than CoreExact, while CoreExact suits small-to-moderate graphs and CoreApp suits larger graphs such as UK-2002.CoreExact uses binary-search flow computations; CoreApp directly computes the maximum clique-core.Source: Figure 12 · p. 11, §8.1 · p. 11

8.2 DSD for Pattern-Densities

  • CorePExact is up to four orders of magnitude faster than PExact on two small datasets for general patterns.Exact-algorithm running times vary with the number of instances of each pattern.Source: §8.2 · p. 11, Figure 15 · p. 12
  • CoreApp is up to two orders of magnitude faster than PeelApp for general-pattern approximation.The running time of approximation algorithms generally increases with graph size.Source: Figure 16 · p. 12, §8.2 · p. 12

9. CONCLUSIONS

The conclusion presents core-based exact and approximation algorithms for edge-, h-clique-, and pattern-density densest-subgraph discovery. Future work includes tighter core-density bounds, size-constrained densest subgraphs, and applying the techniques to randomized approximation.

9. CONCLUSIONS

  • The paper generalizes its core-based exact and approximation solutions from edge- and h-clique-density to pattern-density.Experiments report that exact core-based solutions outperform existing algorithms by up to four orders of magnitude, and approximation solutions by up to two orders.Source: §9 · p. 12
  • Future directions include tighter (k, Ψ)-core density bounds, size-constrained densest subgraphs, and speeding up randomized approximation using core-based techniques.The randomized approximation direction is tied to [49].Source: §9 · p. 12

A. DATASET STATISTICS

The appendix characterizes the experimental networks as varied and gives a minimum st-cut time bound in terms of graph size and clique instances.

A. DATASET STATISTICS

  • The experimental networks range from 1 to 3.8M connected components, have diameters from 3 to 135, and power-law α values from 2.28 to 63.7.The reported characteristics also include vertex and edge counts, kmax, and triangle-core size.Source: A. DATASET STATISTICS · p. 16

B.1 Proofs for Section 4

  • Each minimum st-cut computation takes O(n · |Λ| + min(n, |Λ|)^3) time and O(n + |Λ|) space, where |Λ| is the number of clique instances.The cited minimum-cut procedure is Gusfield’s algorithm [2].Source: §B.1 · p. 16

B.2 Proofs for Section 5.2

The proof establishes that every connected component of a densest subgraph has the same clique-density.

B.2 Proofs for Section 5.2

  • All connected components of a clique-densest subgraph have equal clique-density; otherwise, removing the less-dense component would yield a denser subgraph.The argument extends from two components to any number of components.Source: §B.2 · p. 16

B.3 Proofs for Section 7.2

The proofs establish that PExact finds the pattern-densest subgraph and justify its minimum-cut and binary-search criteria. They also prove a 1/|VΨ|-approximation guarantee for PeelApp.

B.3 Proofs for Section 7.2

  • PeelApp returns a 1/|VΨ|-approximation for the pattern-densest subgraph problem.Source: §B.3 · p. 16
  • PExact correctly finds the pattern-densest subgraph of G.The proof section also establishes that the PExact and construct+ flow networks have the same minimum-cut capacity.Source: §B.3 · pp. 16–17
  • Distinct pattern-density values differ by at least 1/n(n−1), or 1/n when the vertex sets have equal size, supporting the binary-search stopping rule.Source: §B.3 · pp. 16–17
  • The minimum-cut capacity is obtained by summing its contributing edge capacities, as expressed in Eq. (11).The proof considers the cases where A1 is empty and nonempty.Source: §B.3 · p. 17
  • A minimum cut has S\{s} nonempty when some subgraph has pattern-density above α; otherwise, the minimum cut is ({s}, A∪B∪{t}).Source: §B.3 · p. 17

C. PSEUDOCODES OF PEXACT

D. OPTIMIZINGCOREDECOMPOSITION FOR SPECIAL PATTERNS

The section extends core decomposition to general patterns and describes faster degree computation and updates for stars and loops, using diamonds as the loop example.

D. OPTIMIZINGCOREDECOMPOSITION FOR SPECIAL PATTERNS

E. RESULTS ON ADDITIONAL DATASETS

On three additional datasets, approximation-algorithm efficiency results were highly similar to those in the main paper. In a yeast protein-interaction network, pattern-specific densest subgraphs had distinct shapes.

E. RESULTS ON ADDITIONAL DATASETS

F. MORE CASE STUDIES

  • In the yeast PPI network of 1,116 proteins and 2,148 interactions, densest subgraphs for different patterns had distinct shapes and could represent subnetworks with specific functions.Figure 21 highlights the pattern-specific subgraphs and their union’s induced subnetwork.Source: F. MORE CASE STUDIES · p. 19, Figure 21 · p. 19
Loading 1906.00341v2…