PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Kathrin Hanauer, Sophia Heck, Monika Henzinger, Leonhard Sidl

arXiv:2610.29776v1cs.DS

TL;DR

Exact dynamic counting of triangles and four-vertex patterns has been little studied empirically despite specialized algorithms with strong theoretical guarantees. This paper corrects, optimizes, and combines heavy-light approaches, finding large speedups over static, dynamic, and matching baselines. It also identifies practical configurations and conditions that can affect theoretical guarantees.

  • Problem

    Exact dynamic counting of triangles and four-vertex patterns has received little empirical study, particularly for approaches with strong theoretical guarantees.

    Source: §1 · p. 1

  • Method

    The paper corrects and optimizes the heavy-light algorithms of Eppstein et al. and Hanauer et al., and analyzes hybrid combinations.

    Source: §1 · p. 2

  • Results

    On 56 large instances, optimized algorithms achieve mean speedups of up to four orders of magnitude over static recomputation, three orders over the only dynamic counting baseline, and 26× over continuous matching.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper recommends HHH*-HA|late.2 for counting all patterns simultaneously and reports HHH*-H/HHH*-HA as the most effective approaches overall.

    Source: §6 · p. 10

    Under relaxed reassignment, stale vertices can violate the low-degree bound and waive the amortized update-time guarantee under adversarial updates.

    Source: §4.2.4 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

Subgraph counts characterize local network structure and support applications ranging from clustering coefficients to motif analysis. This paper brings theoretically strong dynamic counting algorithms closer to practice through corrections, optimizations, and extensive evaluation.

1 Introduction

  • Subgraph frequencies describe local structure and underpin measures and applications including clustering coefficients, database joins, motif analysis, recommendation, and fraud detection.The clustering coefficient relates triangle counts to length-2 paths and measures transitivity.Source: §1 · p. 1
  • Exact dynamic counting of triangles and four-vertex patterns has received little empirical study, especially for heavy-light algorithms with strong theoretical guarantees.The cited prior four-vertex study considered induced counts, whereas non-induced counts allow extra edges and admit faster algorithms.Source: §1 · pp. 1–2
  • The paper implements and optimizes algorithms by Hanauer et al. and Eppstein et al. for triangles and all connected four-vertex patterns.The approaches use heavy-light partitioning variants; their ability to count 4-cliques also permits induced counts.Source: §1 · pp. 1–2
  • On 56 large instances, optimized algorithms achieve mean speedups of up to four orders of magnitude over static recomputation, three orders over the only dynamic counting baseline, and 26× over continuous matching.The study also corrects algorithm descriptions, improves auxiliary structures, explores partition maintenance, and analyzes hybrid combinations.Source: §1 · p. 2

2 Related Work

Prior work provides specialized dynamic algorithms for triangles and connected four-vertex patterns, but empirical evaluation of theoretically strong approaches has been limited. Other empirical efforts address induced counts or general continuous matching.

2 Related Work

  • Empirical work also covers approximate or streaming triangle counting, arbitrary-pattern matching, and specialized static counting for patterns up to five vertices.Continuous subgraph matching algorithms can provide frequencies through extraction.Source: §2 · p. 2
  • Eppstein and Spiro maintain triangle counts in O(h) amortized update time, while Eppstein et al. extend the approach to non-induced four-vertex subgraphs in O(h^2).Here h is the graph's h-index and lies in O(√m).Source: §2 · p. 2
  • Hanauer et al. give heavy-light algorithms for non-induced four-vertex patterns with O(m^(2/3)) amortized updates, except cliques at O(m) and paths at O(√m).They also provide a triangle algorithm with the same guarantees as Kara et al..Source: §2 · p. 2
  • Schiller et al. provide the only prior empirical study of dynamic four-vertex counting, maintaining induced counts by neighborhood scanning in O(D^2) update time.D denotes maximum vertex degree.Source: §2 · p. 2

3 Preliminaries

The preliminaries establish graph and pattern-counting notation, define dynamic updates, and introduce heavy-light vertex partitions. Node updates are excluded for simplicity.

3 Preliminaries

  • The graph notation defines n and m as vertex and edge counts, degree and neighborhood sets, and D as maximum degree.The passage also defines degree and neighborhood quantities restricted to a vertex subset.Source: §3 · p. 2
  • A pattern count is the number of isomorphic subgraphs divided by the pattern's automorphism count, with induced counts requiring all edges among selected vertices.The considered patterns are triangles, 3-paths, claws, paws, 4-cycles, diamonds, and 4-cliques.Source: §3 · p. 2
  • A dynamic graph applies an initially given graph and an ordered, previously unknown sequence of edge insertions and deletions; node updates are not explicitly considered.The authors state node updates can be handled straightforwardly.Source: §3 · pp. 2–3
  • A heavy-light partition divides vertices into high-degree H and remaining low-degree L sets, with partitions maintained in amortized constant time per update.The text denotes the amortized number of vertices changing partition per update.Source: §3 · p. 3

4 Triangle and 4-Vertex Subgraph Count-

HHH and EGST maintain dynamic subgraph counts through high/low vertex partitions, auxiliary counts, and neighborhood scans. The section reviews HHH’s ε-Partition, its corrections and practical rebalancing variants, then EGST’s h-Index partition and update bound.

4.1 Common Overall Architecture

  • Both algorithms partition vertices into high- and low-degree sets, maintain anchored auxiliary counts, and combine those counts with neighborhood scans to obtain pattern counts.For insertions they update partitioning, auxiliary structures, and pattern counts in that order; after deletions, the auxiliary and pattern-count steps are swapped.Source: §4.1 · p. 3

4.2.1 ε-Partition

  • HHH achieves O(m^1/2) amortized updates for triangles and 3-paths and O(m^2/3) for other connected four-vertex patterns except 4-cliques.It maintains auxiliary non-induced subgraph counts and updates pattern counts after graph changes; 4-cliques can instead be maintained by direct scanning in O(m) worst-case time.Source: §4.2.1 · p. 3

4.2.3 Corrections

  • HHH’s original description gives an incorrect count for 3-paths containing a fixed edge when that edge is terminal and the first adjacent inner vertex is low-degree.The correction is obtained by applying the stated lemma twice, swapping the endpoints’ roles.Source: §4.2.3 · pp. 3–4

4.2.4 Optimizations

  • HHH’s practical optimizations prioritize lower-degree scans, index high-degree neighbors, restrict anchors to high-degree vertices, and add auxiliary-structure uses for triangles and 4-cliques without changing asymptotic time.Neighborhood partitioning replaces scans over all high-degree vertices with scans over a vertex’s high-degree neighbors.Source: §4.2.4 · p. 4
  • Lazy rebalancing can leave vertices stale, violate the bound on DL, and waive the amortized update-time guarantee under an adversarial update sequence.The resulting DL may be Θ(m).Source: §4.2.4 · p. 5
  • Late rebalancing preserves orig’s amortized update times while improving worst-case update times by factors in [√m, m].It gradually processes reclassification over the new epoch, with constant many VPUs per update and only on vertices of degree O(m^ε).Source: §4.2.4 · p. 5

4.3 EGST Algorithm

  • EGST uses the h-Index partition, where |H| and DL are both O(h), yielding O(h^2) amortized update time.Its auxiliary structures use high-degree anchors except for S3.Source: §4.3.1 · p. 5

Corrections and Completions

The section fills in omitted or ambiguous EGST update rules and corrects 3-path counting cases. It also separates the algorithms from their partitions to analyze cross-combinations and their update-time bounds.

Corrections and Completions

  • EGST’s omitted mixed-degree S2/S3 update cases are added, while subgraph counting maintains S2 only with high-degree anchors to reduce memory.The S3 definition for low-low updates is applied to the missing cases as well.Source: Corrections and Completions · p. 5
  • The proposed S5/S6 rules handle mixed-degree updates without mixed-degree S2 anchors; S6 additionally requires both specified edges to be present.The original S6 rule cannot use S2 to test whether the low-degree vertices are adjacent.Source: Corrections and Completions · pp. 5–6
  • EGST’s 3-path updates omit cases and overcount triangles when the updated edge is central; the corrections add triangle-aware counting and cover the missing high-low non-central case.The central-edge correction finds common neighbors using S2 for low-degree vertices and adjacency tests for high-degree vertices when both endpoints are high-degree.Source: Corrections and Completions · p. 6

4.4 Separating Algorithms and Partitioning

  • Under an abstract partition P, HHH with h-Index matches EGST’s update bounds for every pattern except 4-cliques, where HHH uses O(m) and EGST O(h^2).EGST achieves the 4-clique bound through S6 and S7, using |H| and DL in O(h).Source: §4.4 · p. 6
  • HHH and EGST have identical update complexity for triangles and 3-paths, but EGST scales quadratically with |H| for paws, 4-cycles, and diamonds.EGST’s auxiliary structures contain only low-degree non-anchor vertices, so patterns requiring both non-anchor vertices in H require enumerating all pairs in H.Source: §4.4 · p. 6

5 Experimental Evaluation

The evaluation tests optimized and hybrid dynamic counters on diverse real-world and synthetic graphs, alongside dynamic and static baselines. The results show strong performance overall, with different partition choices trading total runtime, update time, and memory.

5.1 Methodology

  • Experiments use real-world and synthetic dynamic graphs, compare against dynamic counters, continuous subgraph matching, and static recomputation, and report medians over three runs.The full dataset and balanced engineering subset cover four graph groups; the engineering subset uses the first two million updates from six graphs per group.Source: §5.1 · p. 7, Table 5.1 · p. 7

5.2 HHH and ε-Partition Optimizations

  • High-degree anchors make HHH*-H 21.9× faster in total time and 116.1× faster in maximum update time than HHH*, while using 49.0× less memory.Adding auxiliary counting structures is only slightly beneficial when all patterns are counted.Source: §5.2 · pp. 7–8

5.2.2 Analysis of ε for the ε-Partition

  • For HHH*-HA on ES, counting all patterns is fastest at ε = 0.2, below theoretical optima, because neighborhood scanning and shared auxiliary structures change the runtime tradeoff.Counting time dominates overall runtime; the optimal ε cannot be derived by averaging individual pattern optima.Source: §5.2.2 · p. 8, Figure 5.1 · p. 8

5.3 Optimizing EGST Performance

  • EGST*-HD achieves 4.3× faster total runtime and 132.9× faster maximum update time than base EGST, with high-degree anchors contributing most of the gain.For all patterns, h(17/16) has similar total runtime to late.367, with 1.3× faster maximum updates and 14.8% less memory.Source: §5.3 · p. 9, §5.3.1 · p. 9, Figure 5.3 · p. 9

5.3.1 Different Partitions for EGST

  • For single patterns, EGST has no clear partition winner; triangles and 4-cliques are fastest without a partition, while late is faster for several other patterns.Across graphs, ε = 0.333 wins on 17 of 24 graphs by up to 1.3×, whereas h(17/16) wins on dense, high-count instances such as Wiki by up to 3.3×.Source: §5.3.1 · p. 9, Figure 5.4 · p. 9

5.4 Comparison to Static Baselines

  • Optimized HHH*-HA|late.2 and EGST*-HD|h(17/16) outperform static algorithms and non-optimized counterparts in total and maximum update time.The comparison uses the first 150,000 updates of each ES instance to accommodate static runtimes.Source: §5.4 · p. 9, Figure 5.4 · p. 9
  • HHH*-H is 1.8×–26.2× faster than Graphflow/RapidFlow, while HHH*-HA is ≥264.6× faster than DNA for all patterns.On graphs with very low pattern frequency, Graphflow can outperform HHH*-H by up to 44%.Source: Figure 5.5 · p. 9, §5.4 · p. 10

Performance Evaluation on FS

On FS, HHH*-HA|late.2 generally outperforms EGST*-HD|h(17/16), though its runtime advantage uses more memory and EGST*-HD times out on three Wiki instances.

Performance Evaluation on FS

  • 2.7× overall speedup: HHH*-HA|late.2 beats EGST*-HD|h(17/16) on the remaining instances, except KRONc-R and KRONg-R with very few pattern counts.The speedup ranges from 0.9–8.3×; scanning algorithms without auxiliary structures remain preferable on those exceptions.Source: Performance Evaluation on FS · p. 10
  • EGST*-HD|h(17/16) timed out on Wiki-D/E/F after 97.5%/61.0%/39.2% of updates, while HHH*-HA|late.2 finished them in 7.9 h/13.7 h/13.2 h.Timed-out runs were recorded as 24 h, underestimating reported speedups.Source: Performance Evaluation on FS · p. 10
  • HHH*-HA|late.2 uses 74.9% more memory than EGST*-HD|h(17/16); increasing ε in late reduces memory at the expense of runtime.The comparison evaluates tuned and untuned combinations on FS with a 24 h timeout.Source: Performance Evaluation on FS · p. 10

6 Conclusion and Practical Recommenda-

The authors recommend HHH*-H/HHH*-HA configurations for dynamic subgraph counting, with choices tuned to pattern, memory constraints, and expected count size. The fastest option can trade away update-time guarantees.

6 Conclusion and Practical Recommenda-

  • HHH*-H/HHH*-HA are the authors’ most effective dynamic subgraph-counting algorithms, with speedups of up to several orders of magnitude.For all patterns simultaneously, they recommend HHH*-HA|late.2.Source: §6 · p. 10
  • For diamonds, paws, and 4-cycles, use HHH*-H|late.233; for 3-paths, use HHH*-H|late.333.Source: §6 · p. 10
  • For triangles, 4-cliques, and claws, prefer HHH*/EGST* scanning or direct counting without partitioning.When counts are known to be small, auxiliary structures may add overhead, making scanning routines preferable.Source: §6 · pp. 10–11
  • For memory-constrained use, increase ε in late to trade runtime for memory; at ε ≥ 0.4 switch to h(17/16), or to EGST*-HD|h(17/16) if needed.Source: §6 · p. 10
  • Lazy was about 1% faster than late in practice, but waives amortized and worst-case update-time guarantees.Source: §6 · p. 10

A.1 Extended Related Work

The extended related work covers static counting and motif identification, theoretical dynamic algorithms and their limits, and empirical continuous subgraph matching. It distinguishes frequency counting from detection and matching-oriented work.

A.1 Extended Related Work

  • The overview omits subgraph detection, which asks only whether a pattern occurs, and notes that extracting frequencies from matching or enumeration is straightforward.It points readers to surveys for broader static and dynamic subgraph-counting coverage.Source: §A.1 · p. 16
  • Static work spans motif identification, exact algorithms for patterns up to five vertices, and approximate or streaming methods, especially for triangles.Subgraph counting for arbitrary patterns generalizes the NP-hard subgraph isomorphism problem.Source: §A.1 · p. 16
  • Dynamic triangle and four-vertex counting has specialized heavy-light and h-index algorithms, including Kara et al., Eppstein et al., and Hanauer et al..Hanauer et al. give pattern-specific update-time bounds, with different bounds for cliques and paths.Source: §A.1 · p. 16
  • Conditional lower bounds constrain fully dynamic connected four-vertex counting, while other work gives a faster 4-cycle bound and batch-dynamic clique algorithms.The cited lower bounds rely on the combinatorial k-clique and OMv conjectures [1, 27].Source: §A.1 · p. 16
  • Schiller et al. empirically study induced triangle and four-vertex counting with neighborhood scanning and O(D^2) update time.Source: §A.1 · p. 16
  • Continuous subgraph matching commonly uses indexes, while Graphflow computes incremental changes without an explicit index; surveyed studies find no single dominant algorithm.Reported strengths vary by query and data-graph characteristics, including sparse or tree queries and dense queries.Source: §A.1 · p. 16

A.2 Proof of Correctness for HHH 3-Path Counting

The lemma counts 3-paths extending an edge when the middle vertex is low-degree. It subtracts two classes of invalid extensions from the auxiliary-structure count.

A.2 Proof of Correctness for HHH 3-Path Counting

  • The number of 3-paths v-u-x-y with x ∈ L is vLV[u] − Av − uLv[u,v].Here Av = degu(v) when v ∈ L, and 0 otherwise.Source: §A.2 · p. 16
  • The subtraction removes extensions where x = v or y = v, which would not form valid 3-paths.vLV[u] counts paths u-x-y with x ∈ L; uLv[u,v] counts 2-paths adjacent to both u and v with a low-degree joint.Source: §A.2 · pp. 16–17

A.3 The HHH Algorithm with High Anchors

Restricting auxiliary-structure anchors to high-degree vertices changes their maintenance and query routines: counts involving low-degree vertices are recovered through neighborhood scans, with cases handled by pattern and partition position.

A.3 The HHH Algorithm with High Anchors

  • Auxiliary structures now use high-degree anchors; edge updates add an O(1) anchor check except for t, whose update is adapted without changing its prior time bound.The anchor restriction can improve practical running time with (O-NP).Source: §A.3 · p. 17
  • Partition swaps reset counts when a vertex moves to L and rebuild them when it moves to H, using structure-specific routines and bounds.For vLV, the rebuild takes O(m^ε); uLv and cLV take O(m^2ε), while uLLv takes O(m^3ε).Source: §A.3 · p. 17
  • For edge updates, the query algorithm scans neighbors of low-degree vertices whose auxiliary counts are no longer stored, then adjusts the relevant pattern totals.Triangle counts split third vertices into H and L cases, using different neighborhood counts when an endpoint is low-degree.Source: §A.3 · p. 17
  • Three-path and paw updates use separate cases for edge position and vertex partition, combining triangle counts, degree terms, and direct neighborhood counts.Three-path counts correct for triangles; paw counts distinguish the arm, an edge adjacent to the arm, and the third triangle edge.Source: §A.3 · pp. 17–18
  • For 4-cycles and diamonds, high-high endpoints retain the existing auxiliary-structure routines, while cases with low endpoints count through neighborhoods.The diamond routine distinguishes whether the updated edge is the chord or part of the 4-cycle.Source: §A.3 · p. 18

A.4 Optimizing the HHH Algorithm: (O-A) Extra Use of Auxiliary Structures

The section evaluates extra auxiliary structures for counting patterns on ES and describes their role in triangle and 4-clique updates. Their value depends on whether patterns are counted individually or simultaneously.

A.4 Optimizing the HHH Algorithm: (O-A) Extra Use of Auxiliary Structures

  • For triangles, looking up uHv avoids iterating over H when the edge endpoints and third vertex are high-degree, without changing the asymptotic update time.The passage states that uHv is maintained in O(m^max(1−ε,ε)) time.Source: §A.4 · p. 18
  • 2.59× (4-cliques) and 2.25× (triangles) faster without maintaining and using auxiliary structures when counting only that pattern.For all patterns simultaneously, using all available auxiliary structures performed similarly, within 2%.Source: Figure A.1 · p. 18, §A.4 · p. 18
  • For 4-cliques, cL can count cases with one low-degree and one high-degree non-endpoint in a single pass over H, yielding O(m^(1−ε)) time for that case.The stated amortized update time remains O(m) when ε ≤ 1/2.Source: §A.4 · p. 18
  • (O-A) was 0.1% faster in geometric mean, as reduced neighbor traversals were slightly offset by lookup times and branch prediction misses.This comparison concerns counting all patterns simultaneously.Source: §A.4 · p. 18

A.5 Bounding Reclassifications during Major Rebalancing

This section examines EGST’s partitioned counting approach from theoretical and practical perspectives. It covers rebalancing costs and partition changes, auxiliary structures, tuning and optimizations, dataset statistics, and single-pattern evaluations.

A.5 Bounding Reclassifications during Major Rebalancing

  • An MR reclassifies O(m^1−ε) vertices, and performing the corresponding soft VPUs preserves the original total MR cost of O(m · Taux).The reclassification bound follows because both the old and new high-degree sets have size O(m^1−ε).Source: §A.5 · pp. 18–19, §A.6 · p. 19

A.7 Degree Bound Degradation under lazy

  • Lazy rebalancing can let DL grow to Θ(m), while late rebalancing retains O(m · Taux) total MR cost and uses a constant number of VPUs per update on vertices of degree O(m^ε).The late-rebalancing degree bound holds when each vertex changes partition.Source: §A.7 · p. 19, §A.8 · p. 19

A.9 Impact of ε-Partitions on Worst-case Update Times in HHH

  • Orig/soft yield worst-case bounds of O(m^3/2) for triangles and 3-paths and O(m^5/3) for paws, 4-cycles, and diamonds; lazy yields O(m), O(m^2), and O(m^3) bounds, respectively.For lazy, O(m) applies to triangles, O(m^2) to 3-paths and paws, and O(m^3) to 4-cycles and diamonds.Source: §A.9 · p. 19, Table A.2 · p. 20
  • Late rebalancing gives worst-case update times of O(m^1/2) for triangles, O(m^2/3) for paws, and O(m) for 3-paths, 4-cycles, and diamonds, while preserving amortized bounds.It achieves these bounds by spreading rebalancing VPUs across subsequent updates.Source: §A.9 · p. 20, Table A.2 · p. 20

A.10 Proof of Correctness for EGST 3-Path Counting

  • EGST counts 3-paths with a high-degree endpoint by combining S0 and S2 counts and subtracting invalid paths, in O(h) time.The corrections exclude paths in which an endpoint repeats as an internal vertex.Source: §A.10 · p. 20

A.11 Direct Partition Swaps of the EGST Algorithm

  • Direct EGST partition swaps scan a moving vertex’s 2-hop neighborhood, updating auxiliary counts by removing its low-degree non-anchor role and adding its anchor role.The swaps take O(h^2) for S0–S2 and O(h^3) for S3–S7, with DL ∈ O(h).Source: §A.11 · p. 20

A.12 Proof of the Gradual Factor for the h-Index Partition

  • With h-Index thresholds c·h for moves into H and h for moves into L, the partition has O(1/h) amortized changes per update for any c > 1.Source: §A.12 · p. 21

A.13 The EGST Algorithm with an Abstract Partition

  • Under an abstract partition, EGST auxiliary-structure update costs depend on |H|, DL, and amortized partition changes; partition swaps can use simulated edge updates or the direct-swap optimization.Source: §A.13 · p. 22
  • EGST with an abstract partition handles four-vertex patterns by case-splitting on whether vertices are high- or low-degree, with amortized update times listed in Table 4.2.The appendix describes cases for 4-cycles, diamonds, and 4-cliques using auxiliary structures and neighborhood enumeration.Source: §A.13 · p. 23

A.14 Full Dataset Statistics

  • Tables A.3 and A.4 report full-dataset and engineering-dataset statistics, including update, graph-size, degree, and pattern-count measures.The full-dataset table also includes insertion ratio, h-index, h3/m ratio, clustering coefficient, and network type.Source: §A.14 · p. 23, Table A.3 · p. 24, Table A.4 · p. 25

A.15 Tuning the Rebalancing Frequency

  • Changing ρ yields individual-graph speedups of up to 1.5× (orig), 1.3× (soft), 1.2× (lazy), and 1.1× (late), but ρ = 2 remains within 1–9% of alternatives in geometric mean.The best factor is graph-specific; the reported geometric-mean gaps for ρ = 2 are within 1% for lazy, 2% for late, 3% for soft, and 9% for orig.Source: §A.15 · p. 26, Figure A.2 · p. 26

A.16 Proposed Optimizations

  • EGST*-HD improves maximum update time by 132.9× and total runtime by 4.3× over EGST when counting all subgraphs on ES.EGST*-H alone achieves a 4.3× total-runtime speedup and improves maximum update time by 130.1×; EGST*-D yields only a 1.4% total-runtime improvement, with maximum update-time differences within 1%.Source: §A.16 · p. 26

A.17 Counting Single Patterns

  • The single-pattern evaluation examines HHH*-H and EGST*-HD across vertex partitions with varying ε on ES data, excluding claws because their update time is constant.The corresponding evaluations are shown in Figures A.4 and A.5.Source: Figure A.4 · p. 27, Figure A.5 · p. 27
Loading 2610.29776v1…