PaperlayerView exact revision on arXiv

Source-linked AI summary

Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification

Albert Angel, Nick Koudas, Nikos Sarkas, Divesh Srivastava

arXiv:1203.0060v1cs.DB

TL;DR

Real-time story identification requires efficient maintenance of dense subgraphs as social-media posts stream in and update entity associations. The paper formalizes this problem and proposes DYNDENS, which combines update-change theory with sparse-subgraph maintenance and indexing. Experiments on real and synthetic datasets report that the approach is effective and scalable, while too-dense subgraphs can make exploration costly.

  • Problem

    Real-time story identification requires maintaining dense subgraphs under streaming edge-weight updates across broad density definitions, whereas existing techniques apply only to limited subsets.

  • Method

    DYNDENS uses theoretical bounds on the change caused by one edge update, maintains sparse and dense subgraphs incrementally, and uses an efficient subgraph index with sound heuristics.

  • Results

    The approach is validated by thorough experiments on real and synthetic datasets, which highlight its effectiveness and scalability for rapidly evolving datasets.

  • Takeaways & Limitations

    Maintaining sparse subgraphs alongside dense ones enables efficient incremental computation of dense subgraphs for real-time story identification.

  • Takeaways & Limitations

    Exploring too-dense subgraphs can require |V| dense-subgraph insertions and dominate processing costs; adapting DYNDENS to social graphs and changing thresholds remains open.

Abstract

from arXiv · show

Recent years have witnessed an unprecedented proliferation of social media. People around the globe author, every day, millions of blog posts, social network status updates, etc. This rich stream of information can be used to identify, on an ongoing basis, emerging stories, and events that capture popular attention. Stories can be identified via groups of tightly-coupled real-world entities, namely the people, locations, products, etc., that are involved in the story. The sheer scale, and rapid evolution of the data involved necessitate highly efficient techniques for identifying important stories at every point of time. The main challenge in real-time story identification is the maintenance of dense subgraphs (corresponding to groups of tightly-coupled entities) under streaming edge weight updates (resulting from a stream of user-generated content). This is the first work to study the efficient maintenance of dense subgraphs under such streaming edge weight updates. For a wide range of definitions of density, we derive theoretical results regarding the magnitude of change that a single edge weight update can cause. Based on these, we propose a novel algorithm, DYNDENS, which outperforms adaptations of existing techniques to this setting, and yields meaningful results. Our approach is validated by a thorough experimental evaluation on large-scale real and synthetic datasets.

1. INTRODUCTION

The paper frames real-time story identification as maintaining dense entity subgraphs under streaming edge-weight updates, then introduces DYNDENS to address this challenge efficiently across broad density definitions.

  • Motivation: Millions of social-media posts provide an ongoing stream for identifying emerging stories and events that capture popular attention.Stories have a strong temporal component, making timeliness important for identification.
  • Story representation: Stories can be represented as cohesive groups of strongly associated real-world entities, forming dense subgraphs in an evolving weighted entity graph.Posts tend to mention entities corresponding to individual story facets, whose union forms the overall story.
  • Problem: ENGAGEMENT addresses dense subgraph maintenance under streaming edge-weight updates and user-specified size constraints.Each published post updates one or more entity-graph edges, creating a need for highly efficient processing.
  • Problem: A single edge-weight change can affect the density of many subgraphs, potentially requiring unbounded graph exploration, while existing techniques cover only limited density notions.The paper therefore seeks incremental maintenance without recomputing dense subgraphs from scratch.
  • Approach and validation: DYNDENS uses theoretical bounds on update-induced changes, sparse-subgraph maintenance, an efficient index, and theoretically sound heuristics to incrementally maintain dense subgraphs.The approach is evaluated on real and synthetic datasets, with the paper reporting effectiveness and reduced memory consumption and processing effort.

2. FORMALIZATION

ENGAGEMENT maintains threshold-dense, size-bounded subgraphs in a weighted graph whose edge weights change over time. DYNDENS combines update-sensitive exploration, sparse auxiliary subgraphs, an index, and heuristics to support incremental maintenance.

  • 2. FORMALIZATION: In real-time story identification, vertices represent entities, edge weights represent pairwise association strengths, and dense subgraphs represent cohesive stories.Association strength can be computed using measures such as log-likelihood ratio, χ2, or correlation coefficient.
  • 2. FORMALIZATION: Density is defined as total induced edge score divided by S_n, allowing many literature definitions through the choice of S_n.AVGWEIGHT uses S_n = n·(n−1)/2, while AVGDEGREE uses S_n = n.
  • 2. FORMALIZATION: The framework restricts S_n to intuitive monotonicity properties that exclude density definitions behaving counter-intuitively on unweighted cliques.The formalization also treats vertices as natural-number identifiers and introduces notation for basis vectors and subgraphs.
  • 2. FORMALIZATION: ENGAGEMENT maintains all subgraphs with density at least T and cardinality at most Nmax after each edge-weight update.Updates may adjust, add, or remove one or more edges.
  • 2. FORMALIZATION: DYNDENS incrementally updates affected dense subgraphs and explores candidate augmentations using cheap exploration, ordinary exploration, and iterative exploration.The algorithm also supports explore-all when non-neighboring vertices must be considered.
  • 2. FORMALIZATION: At most ⌈δ/δit⌉ exploration iterations are required to identify all newly dense subgraphs after an update of magnitude δ.The iteration bound follows from the paper’s growth-property analysis and uses thresholds T_n controlled by δit.
  • 3.1 The DYNDENS Algorithm: The DYNDENS exploration procedure prunes subgraphs that were already too dense before the update and avoids unnecessary repeated exploration where possible.It also mitigates the cost of explore-all through an implicit index representation.
  • 3.2 Implementation Considerations: Too-dense subgraphs can make explore-all dominant because explicitly inserting their disconnected supergraphs requires |V| dense-subgraph insertions; IMPLICITTOODENSE represents these supergraphs implicitly and experimentally provides significant performance benefits.The index uses a fictitious vertex ∗ to represent the relevant supergraphs rather than inserting each one explicitly.

4. THEORETICAL RESULTS

The theoretical results bound how far a single edge-weight update can affect dense subgraphs and use those bounds to justify DYNDENS’s exploration strategy. The analysis also characterizes iteration limits and the space–time tradeoff controlled by δit.

  • Correctness and exploration bounds: The analysis proves correctness by bounding the number of exploration iterations required after an edge-weight update, while detailed complexity results are omitted due to space constraints.The bound depends on the update magnitude and underpins DYNDENS’s correctness.
  • Correctness and exploration bounds: For sufficiently small updates, every newly-dense subgraph contains a previously stable-dense subgraph of one smaller cardinality, making it discoverable in the first exploration set C1.The proof uses a pigeonhole argument: if all smaller subgraphs were sparse, the larger subgraph would already have been very dense before the update.
  • Parameterization and tradeoffs: The proposed Tn instantiation simplifies the sufficient condition for the theory to δ < δit and yields O(n) or O(1) behavior under the stated choices of Sn.When Sn = n, the passage reports O(n); when Sn = n(n −1), it reports O(1).
  • Correctness and exploration bounds: DYNDENS needs at most ⌈δ/δit⌉ iterative exploration steps to find all newly-dense subgraphs after an update of magnitude δ.The result requires exploring stable- and newly-dense subgraphs across successive sets C0, C1, and onward; stable-dense subgraphs need not be re-explored subsequently.
  • Interpretation of update magnitude: The theory interprets an update as a perturbation whose impact can extend farther through the graph as its magnitude δ increases.Larger updates may therefore require exploration farther from the affected edge.
  • Parameterization and tradeoffs: The parameter δit controls a space–time tradeoff: higher values maintain more dense subgraphs but require fewer exploration iterations, whereas lower values reduce space overhead.The practical choice of δit is data-dependent, although DYNDENS performs well across a wide range of values.

5. EVALUATION

The evaluation examines DYNDENS’s feasibility, scalability, implementation choices, comparisons with alternative techniques, and qualitative story-identification results.

  • Experimental setup: DYNDENS was evaluated for feasibility, scalability, and efficiency factors using real-world and synthetic datasets.The experiments also examine the main factors contributing to DYNDENS’s efficiency.
  • Identifying emerging stories: Exponential decay with a two-hour tweet mean life adapts association measures to identify current emerging stories rather than cumulative stories.Without decay, the same techniques identify cumulative stories to date.
  • Efficiency and scalability: DYNDENS processed the dataset in 40–85 seconds, whereas the variant without IMPLICITTOODENSE exceeded 20 minutes and was terminated.This comparison used weighted data across Nmax ∈ {9, 10}, T ∈ [0.44, 0.5], and δit between 1% and 50% of its maximum.
  • Comparison with other techniques: DYNDENS’s runtime was 936 seconds versus 958 seconds for STIX, while BASELINE managed only 15–30 recomputations in the time DYNDENS processed the weighted dataset.The authors characterize DYNDENS as better suited to ENGAGEMENT, while STIX suits maximal-clique identification in unweighted subgraphs.
  • Qualitative results: Qualitative results included prominent bin Laden discussions, the Libya crisis, Harry Potter, and Lady Gaga.The evaluation presents sample results because important-story ground truth is unavailable for the relevant media settings.

6. HEURISTICS

DYNDENS includes two heuristics that reduce unnecessary exploration, offering modest performance improvements while preserving result quality.

  • Evaluation: The heuristics provide modest gains without affecting result quality, and their low implementation effort supports including them in DYNDENS.They are less crucial to performance than IMPLICITTOODENSE.
  • MAXEXPLORE: MAXEXPLORE replaces a pessimistic exploration bound with a cheap bound using the updated edge’s neighborhood and the explored subgraph’s cardinality.It is intended to reduce iterations on dense subgraphs.
  • DEGREEPRIORITIZE: DEGREEPRIORITIZE organizes the search space to often avoid redundant explorations originating from multiple dense subgraphs.Its design is inspired by a degree-based criterion.
  • Evaluation: The heuristics improved performance by up to over 10% under the evaluated settings.Figure 4(h) compares variants with neither, either, or both heuristics enabled for T = 0.7 and Nmax ∈ {8, 9, 10}.

7. RELATED WORK

Related work spans dense-subgraph, clique, dynamic-graph, clustering, data-structure, and local-density methods, but differs from ENGAGEMENT in goals or update setting.

  • Cliques and dense subgraphs: Incremental maximal-clique maintenance is closely related to the unweighted AVGWEIGHT, T = 1 special case, but ENGAGEMENT enumerates cardinality-constrained cliques rather than unconstrained maximal cliques.The authors state that the former is better suited to real-time story identification.
  • Cliques and dense subgraphs: GRASP can be dynamized for unweighted graphs and AVGWEIGHT, but it targets large dense subgraphs and need not identify all dense subgraphs.ENGAGEMENT requires enumeration of all dense subgraphs because each may represent a story of interest.
  • Dynamic and local-density methods: Local-density methods use neighbor-based patterns over sliding windows, whereas ENGAGEMENT requires a substantially different density problem and cannot directly use those techniques.The cited methods decide augmentation using local information only.
  • Dynamic graph methods: Max-flow methods maintain clusters containing user-specified nodes or identify top-1 AVGDEGREE subgraphs, not efficiently dynamized top-k or threshold variants.Other dynamic-graph methods focus on properties such as planarity, connectivity, or triangle counting rather than density.
  • Clustering: Incremental clustering handles node insertion and deletion, while evolutionary clustering additionally uses historical data for temporal smoothing; neither directly accommodates streaming edge-weight updates.The related problems therefore differ from ENGAGEMENT’s update semantics.
  • Offline dense-subgraph methods: Offline shingling and LSH methods target large or moderate cliques and are not readily effective for the smaller, dynamically updated subgraphs considered here.Shingling is geared toward 100–10K-node subgraphs, while LSH has a significant preprocessing phase.

8. CONCLUSIONS

The paper presents DYNDENS as an efficient solution for maintaining dense subgraphs under streaming edge-weight updates and validates it on real and synthetic datasets.

  • Conclusions: DYNDENS addresses dense-subgraph maintenance under streaming edge-weight updates for a broad definition of graph density.The problem is motivated by mining important stories and events as they emerge from social media.
  • Conclusions: The algorithm is based on theoretical results quantifying the magnitude of change caused by a single edge-weight update.The authors describe DYNDENS as the first efficient algorithm for this broad setting.
  • Conclusions: DYNDENS is reported to scale gracefully to rapidly evolving datasets, with efficiency and effectiveness validated on real and synthetic data.The paper identifies efficient maintenance as its main focus.
  • Future directions: Applying ENGAGEMENT to online communities remains an open adaptation problem because those graphs are often directed and involve larger-cardinality subgraphs than stories.The paper also identifies adapting DYNDENS to execution-time changes in density threshold T as an open technical problem.
Loading 1203.0060v1…