Learning Root Source with Marked Multivariate Hawkes Processes

Wei Zhang, Fan Bu, Derek Owens-Oas, Katherine A. Heller, Xiaojin ZhuarXiv 2018 · arXiv

Introduction

In the digital age, conversation threads are ubiquitous, appearing in formats ranging from Reddit discussions to courtroom transcripts. While some platforms preserve a clear "reply-to" structure, many others do not, leaving the underlying parent-child relationships between utterances latent. This lack of explicit structure makes it difficult to identify the "Original Poster" (OP) or the true initiator of a specific idea or piece of news.

Identifying the root source is challenging because conversations often resemble a "forest" rather than a single tree; individuals may intermittently start new topics while simultaneously responding to others. This paper introduces a generative model based on marked multivariate Hawkes processes to infer this hidden branching structure and identify the original initiators.

Methodology: Marked Multivariate Hawkes Processes

The authors model conversations using Marked Multivariate Hawkes Processes (MHPs). Hawkes processes are self-exciting point processes where the occurrence of an event (e.g., a comment) increases the probability of future events. In this context, each participant is treated as a separate dimension or source.

Visualization of the branching structure in a multivariate Hawkes process across three sources.

The model incorporates three key components to capture the dynamics of conversation:

  1. Temporal Locality: Reflects the intuition that responses are more likely to occur shortly after a parent comment.
  2. Individual Heterogeneity: Accounts for varying intrinsic rates at which different users start new topics or respond to others.
  3. Vocabulary Inheritance: A novel mechanism where a reply's content is modeled as a mixture of the user’s own vocabulary and the vocabulary of the parent comment.

To handle the uncertainty of attribution, the authors define Root Source Probability ($r_i^{(s)}$), which quantifies the likelihood that a specific individual $s$ initiated the thread leading to event $i$.

Summary of notation used in the proposed model.

Calculating these probabilities over all possible trees is computationally prohibitive. To address this, the authors derive an efficient dynamic programming algorithm that computes probabilities recursively, scaling linearly with the number of events. Parameters such as the influence matrix ($\mathbf{A}$) and word inheritance rates ($\gamma$) are estimated using Variational Expectation-Maximization (EM).

Experimental Evaluation

The model was evaluated across three diverse datasets:

  • Synthetic Data: Used to verify parameter recovery and accuracy against a known ground truth in a controlled environment.
  • Reddit: A 2016 US Election "Megathread" served as a real-world benchmark. Reddit's metadata provides a ground-truth reply structure, allowing for objective validation of the model's structural inferences.
  • 12 Angry Men: A transcript of the 1957 film provided a practical application for qualitative evaluation in a setting without ground-truth metadata.

Key Results and Insights

The proposed method, RP_FIT, demonstrated high accuracy on synthetic data, closely tracking an "Oracle" model. On the Reddit dataset, it achieved a Top-10 accuracy of 0.79, significantly outperforming heuristic baselines that rely solely on temporal proximity.

A key insight is the role of Vocabulary Inheritance as a proxy for structural links. The model effectively uses the recurrence of specific, rare words as a signal of a response relationship. Furthermore, the authors introduced a "Power" score based on the sum of a user's root source probabilities, reflecting their ability to initiate topics. In the 12 Angry Men analysis, this score correctly identified the film's protagonist (Juror 8) and antagonist (Juror 3) as the primary drivers of discussion.

Conclusion and Future Work

This research provides a principled framework for identifying initiators in complex, multi-topic environments. While the current model uses a "bag-of-words" approach, future work could integrate advanced NLP techniques like word embeddings to better capture semantic inheritance. Additionally, exploring dynamic parameters that shift as a debate evolves could further refine the model's accuracy in long-form conversations.

Summary updated

BibTeX
@misc{zhang2018learning,
  author = {Wei Zhang and Fan Bu and Derek Owens-Oas and Katherine A. Heller and Xiaojin Zhu},
  title = {{Learning Root Source with Marked Multivariate Hawkes Processes}},
  year = {2018},
  eprint = {1809.03648},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1809.03648},
}
Figure