Modelling Populations of Interaction Networks via Distance Metrics

George Bolt, Simón Lunagómez, Christopher NemetharXiv 2022 · DOI · arXiv

Abstract

Network data arises through observation of relational information between a collection of entities. Recent work in the literature has independently considered when (i) one observes a sample of networks, connectome data in neuroscience being a ubiquitous example, and (ii) the units of observation within a network are edges or paths, such as emails between people or a series of page visits to a website by a user, often referred to as interaction network data. The intersection of these two cases, however, is yet to be considered. In this paper, we propose a new Bayesian modelling framework to analyse such data. Given a practitioner-specified distance metric between observations, we define families of models through location and scale parameters, akin to a Gaussian distribution, with subsequent inference of model parameters providing reasoned statistical summaries for this non-standard data structure. To facilitate inference, we propose specialised Markov chain Monte Carlo (MCMC) schemes capable of sampling from doubly-intractable posterior distributions over discrete and multi-dimensional parameter spaces. Through simulation studies we confirm the efficacy of our methodology and inference scheme, whilst its application we illustrate via an example analysis of a location-based social network (LSBN) data set.

Introduction: The Challenge of Multiple Interaction Networks

Network data is a cornerstone of modern data science, yet it manifests in diverse forms. Traditional statistical network analysis typically focuses on two scenarios: analyzing a single large graph or analyzing a population of static graphs (e.g., brain connectomes from multiple subjects). A third, increasingly prevalent form is the interaction network, where data consists of sequences or sets of paths, such as a user's clickstream on a website or a day's worth of location check-ins.

While methods exist for populations of static graphs and single interaction networks, the intersection—populations of interaction networks—has remained largely unaddressed. For example, how does one calculate the "average" daily movement pattern for a population of hundreds of social media users? Historically, researchers have resorted to aggregating these paths into static graphs by counting total edge frequencies. However, this aggregation destroys higher-order dependencies and sequential information. This paper introduces a novel Bayesian framework to model these populations directly, preserving the integrity of the path-level data.

Methodology: Distance-Based Bayesian Modelling

The proposed framework treats collections of paths as the fundamental unit of observation. By defining probability distributions based on distance metrics between these complex discrete objects, the authors can perform statistical inference analogous to classical methods.

Data Representation and Models

The authors model data as either interaction sequences (where the order of paths matters) or interaction multisets (where only the presence and frequency of paths matter). They introduce two primary models:

  • Spherical Interaction Sequence (SIS)
  • Spherical Interaction Multiset (SIM)

These models utilize a user-specified distance metric (such as Edit distance or Matching distance) to define a distribution centered around a "mode" (location) and controlled by a "dispersion" parameter (scale). This approach provides a Gaussian-like intuition for discrete, high-dimensional network spaces.

Examples of interaction networks representing user movements between venue categories.

The iExchange Algorithm

Performing Bayesian inference on these models results in a "doubly-intractable" posterior—meaning the normalizing constants of the distributions cannot be computed. To solve this, the authors developed the iExchange algorithm. This scheme combines the Exchange Algorithm with Involutive MCMC (iMCMC), allowing for efficient sampling by proposing edits (insertions, deletions, or node changes) and using auxiliary data to cancel out the intractable constants without needing to calculate them directly.

Key Results and Applications

The efficacy of the framework was demonstrated through both simulation and real-world data analysis.

Simulation Studies

Using the "Hollywood model" to generate synthetic heavy-tailed network data, the authors confirmed that as the sample size increased from 25 to 100 observations, the inferred mode reliably concentrated around the ground truth. Furthermore, in missing-data tasks, the posterior predictive distribution's accuracy matched the true data-generating distribution once training samples reached 100.

Foursquare Check-in Analysis

The model was applied to a Foursquare dataset (Yang et al., 2015) of user check-ins in New York. By treating each user's daily check-in sequence as an interaction network, the SIM model successfully identified an "average" behavioral profile. Common identified paths included transitions from "Outdoors/Recreation" to "Food" and "Professional" to "Food." Unlike traditional graph aggregation, which might suggest a general connectivity between these categories, the SIM model explicitly identified the specific path structures that characterize typical user behavior, eliminating the ambiguity of aggregated adjacency matrices.

Discussion and Future Directions

The primary contribution of this work is the ability to preserve higher-order dependencies in network populations. By modeling paths directly, the authors avoid the pitfalls of aggregating paths into a standard graph adjacency matrix, which often destroys sequential reality. Framing complex discrete objects through location and scale parameters provides a statistically rigorous way to answer basic questions like "what is the average user behavior?"

However, several avenues for future work remain. The current model assumes all observations come from one underlying distribution, whereas real data is often heterogeneous; future extensions could incorporate mixture models to cluster users. Additionally, evaluating distance metrics is computationally expensive, making the approach slow for massive datasets. Finally, the framework does not yet incorporate observation-level metadata, such as user demographics, which could be addressed in a future regression-like framework.

Summary updated

Abstract

Network data arises through observation of relational information between a collection of entities. Recent work in the literature has independently considered when (i) one observes a sample of networks, connectome data in neuroscience being a ubiquitous example, and (ii) the units of observation within a network are edges or paths, such as emails between people or a series of page visits to a website by a user, often referred to as interaction network data. The intersection of these two cases, however, is yet to be considered. In this paper, we propose a new Bayesian modelling framework to analyse such data. Given a practitioner-specified distance metric between observations, we define families of models through location and scale parameters, akin to a Gaussian distribution, with subsequent inference of model parameters providing reasoned statistical summaries for this non-standard data structure. To facilitate inference, we propose specialised Markov chain Monte Carlo (MCMC) schemes capable of sampling from doubly-intractable posterior distributions over discrete and multi-dimensional parameter spaces. Through simulation studies we confirm the efficacy of our methodology and inference scheme, whilst its application we illustrate via an example analysis of a location-based social network (LSBN) data set.
BibTeX
@misc{bolt2022modelling,
  author = {George Bolt and Simón Lunagómez and Christopher Nemeth},
  title = {{Modelling Populations of Interaction Networks via Distance Metrics}},
  year = {2022},
  eprint = {2206.09995},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.09995},
}
Figure