Source-linked AI summary
When is a Network a Network? Multi-Order Graphical Model Selection in Pathways and Temporal Networks
Ingo Scholtes
TL;DR
Temporal correlations can invalidate network analyses of pathway data, raising the question of when a network abstraction is justified. The paper combines multiple Markov orders in a layered graphical model and proposes model selection; it reports improved inference of graphical models compared with previously used methods.
Problem
Temporal correlations in pathways can invalidate results from network analysis, leaving open when a network abstraction is justified.
Source: §1 · p. 1Method
The framework combines higher-order Markov models in a multi-layer graphical model and selects its optimal order using pathway characteristics and graph constraints.
Source: §1 · p. 1Results
The model-selection technique considerably improves inference of optimal graphical models compared with previously used methods and is demonstrated on real-world pathway and temporal-network data.
Source: §6 · p. 9Takeaways & Limitations
Principled model selection should precede network-analytic methods, and higher-order abstractions can represent both topological and temporal patterns.
Source: §1 · p. 1, §6 · p. 9The study uses a straightforward higher-order PageRank extension and a simple approach to choosing the temporal window δ; principled inference of δ remains open.
Source: §6 · p. 9
Abstract
from arXiv · showhide
We introduce a framework for the modeling of sequential data capturing pathways of varying lengths observed in a network. Such data are important, e.g., when studying click streams in information networks, travel patterns in transportation systems, information cascades in social networks, biological pathways or time-stamped social interactions. While it is common to apply graph analytics and network analysis to such data, recent works have shown that temporal correlations can invalidate the results of such methods. This raises a fundamental question: when is a network abstraction of sequential data justified? Addressing this open question, we propose a framework which combines Markov chains of multiple, higher orders into a multi-layer graphical model that captures temporal correlations in pathways at multiple length scales simultaneously. We develop a model selection technique to infer the optimal number of layers of such a model and show that it outperforms previously used Markov order detection techniques. An application to eight real-world data sets on pathways and temporal networks shows that it allows to infer graphical models which capture both topological and temporal characteristics of such data. Our work highlights fallacies of network abstractions and provides a principled answer to the open question when they are justified. Generalizing network representations to multi-order graphical models, it opens perspectives for new data mining and knowledge discovery algorithms.
1 INTRODUCTION
Pathway data preserve sequences through a graph, but temporal correlations can make ordinary network analysis unreliable. The paper proposes multi-order models and model selection to determine when network abstractions are justified.
1 INTRODUCTION
- Collections of observed pathways are sequences of vertices traversed in an underlying graph, arising in settings such as click streams and biological cascades.Source: §1 · p. 1
- Graph analytics are often applied because pathway data reveal underlying graph topology, but concerns have been raised about overly naive applications [2, 40].Source: §1 · p. 1
- Temporal correlations can invalidate network-analytic results about clusters, node rankings, and dynamical processes such as information propagation.Source: §1 · p. 1
- The framework combines higher-order Markov models into multi-layer graphical models and selects layers using pathway structure and graph constraints.Source: §1 · p. 1
- The authors present the framework as a principled way to decide when network analysis is justified and to infer higher-order abstractions.Source: §1 · p. 1
2 RELATED WORK
Prior work documents temporal correlations across pathways and temporal networks, while this paper addresses how to select suitable graphical abstractions for multiple independent paths of varying lengths.
2 RELATED WORK
- The review focuses on graph pathways and time-stamped data on temporal or dynamic graphs, relating sequence modeling to pattern mining and graph analysis.Source: §2 · pp. 1–2
- Click-stream studies found that page-order correlations can improve prediction, while model selection may warrant higher orders for topic-level but not page-level navigation.Source: §2 · p. 2
- Correlations in travel, scientific communication, and cargo pathways, as well as time-stamped interactions, have been reported to shape network structure and dynamics [18] [20] [21] [26] [36].Source: §2 · p. 2
- Prior studies report that autocorrelations in pathways and temporal networks challenge topology-based modeling, affecting sequential pattern mining and graph analytics.Source: §2 · p. 2
- Although higher-order methods address these concerns, prior order-selection work did not account for multiple independent paths of varying lengths observed in a graph.Source: §2 · p. 2
3 PRELIMINARIES
The preliminaries formalize pathway data as graph-constrained sequences and explain how Markov order represents memory, how transition probabilities are estimated, and how higher-order graphs encode temporal dependencies.
3 PRELIMINARIES
- The data are a multiset of independent, variable-length paths whose consecutive vertices follow directed edges in an underlying graph.Source: §3 · p. 2
- An order-k Markov chain assumes each next vertex depends only on the k preceding vertices, called the model’s memory.Source: §3 · p. 2
- Zero-order transitions ignore prior vertices, first-order transitions can enforce graph edges, and higher orders capture dependencies beyond topology.Source: §3 · p. 2
- Choosing a Markov order is a model-selection problem based on likelihoods for observed paths, including the independent-path dataset.Source: §3 · pp. 2–3
- For each order, maximum-likelihood transition probabilities are estimated from relative frequencies of subpaths of that length in the observed paths.Source: §3 · p. 3
- Higher-order graphs represent transitions between k-vertex states, encoding memory and path correlations; unlike the first-order graph, they capture deviations from transitivity up to order k.Source: §3 · p. 3, Figure 1 · p. 3
4 MULTI-ORDER GRAPHICAL MODELS
Multi-order graphical models combine Markov models of different orders to capture pathway correlations at multiple length scales, then select how many layers the data support. Synthetic experiments show improved order detection over AIC and BIC, while higher-order PageRank best matches visitation probabilities when its order matches the detected optimum.
4 MULTI-ORDER GRAPHICAL MODELS
- The framework combines layers of higher-order Markov models, each capturing correlations at a particular sequence length, to model pathways of varying lengths.For layers below the maximum order, likelihood uses subpaths of exactly that length; the maximum-order layer uses paths at least that long.Source: §4 · pp. 3–4
4.1 Detection of optimal maximum order
- Nested candidate models support likelihood-ratio tests using Wilk’s theorem, and the method selects the largest order whose p-value is below the significance threshold.The nested models' likelihood-ratio distribution is asymptotically chi-squared, with degrees of freedom given by the difference between models.Source: §4.1 · pp. 4–5
- For sparse graphs, the multi-order model’s degrees of freedom grow considerably slower than the exponential growth expected for standard higher-order Markov chains.The calculation accounts for feasible paths in the underlying graph rather than all possible sequences.Source: §4.1 · pp. 4–5
4.2 Experimential validation
- MOG recovers the known order for N > 300, while AIC requires N > 50,000 and BIC N > 350,000 in the order-four experiment.The comparison uses synthetic paths in a random graph with 10 vertices and 30 directed edges.Source: Figure 2 · p. 5, §4.2 · p. 5
- For order two at fixed edge density, the sample size needed for correct detection quickly exceeds N = 10^6 as graph size varies, whereas MOG detects the correct order with small samples.MOG’s required sample size increases with graph density but remains smaller than BIC and AIC even for fully connected graphs, where model degrees of freedom coincide.Source: Figure 2 · p. 5, §4.2 · p. 6
- PageRank on a k-th-order graph best reproduces ground-truth vertex visitation probabilities when k equals the detected optimal order Kopt.The comparison uses Kendall’s rank correlation on synthetic paths.Source: Figure 3 · p. 6, §4.2 · p. 6
5 APPLICATIONS
Applications to pathway and temporal-network data show that the inferred maximum order distinguishes settings where first-order network models are justified from those requiring higher-order models. PageRank validation supports these choices, while temporal-data results depend on extracting paths using a maximum edge-time difference.
5 APPLICATIONS
- The application covers transportation itineraries, click paths, scientist careers, and temporal interactions, with a restriction to the 100 most-visited articles for WIKI analysis.MSNBC click streams are at page-category level and are not constrained to a graph.Source: §5 · p. 6, §5.1 · p. 7
5.1 Pathway Data
- Pathway analysis finds Kopt > 1 for four of five datasets, unlike BIC- and AIC-based detection, which mostly returns order one.CAREER is the exception to the multi-order result; BIC and AIC return order three for MSNBC.Source: §5.1 · p. 7
- For TUBE, PageRank prediction AUC rises from about 0.69 at order one to 0.96 at Kopt = 6; higher orders do not improve TUBE or WIKI predictions.For CAREER, where Kopt = 1, models with k > 1 do not improve prediction performance.Source: Figure 4 · p. 7, §5.1 · p. 8
5.2 Temporal Network Data
- The temporal-network procedure extracts time-respecting paths using a maximum time difference δ, then uses layers above order one to capture edge-order correlations.The choice of δ is based on the inter-event-time distribution; the authors report that results do not sensitively depend on that choice.Source: §5.2 · p. 8
- Timestamp-shuffled temporal datasets all yield Kopt = 1; in the original data, EMAIL yields order one while HOSP and WORK warrant higher orders.The authors use δ values based on inter-event-time distributions when extracting paths.Source: §5.2 · p. 8
- For HOSP and WORK, inferred orders improve PageRank’s agreement with visitation probabilities and prediction AUC; EMAIL shows no corresponding increase.At Kopt, rank correlations are about 0.71 and 0.67, and AUC values are 0.91 and 0.89 for HOSP and WORK, respectively.Source: Figure 4 · p. 7, §5.2 · p. 8
6 CONCLUSION
The paper presents model selection as a principled way to decide when network abstractions of sequential data are justified. Its multi-order framework improves inference of graphical models and captures temporal and topological characteristics in real-world pathway and temporal-network data.
6 CONCLUSION
- A principled method is needed to decide when network abstractions are justified, and model selection should precede network-analytic methods.The conclusion frames this as a first task before applying network analytics to sequential data.Source: §6 · p. 9
- The proposed model-selection technique considerably improves inference of optimal graphical models that balance complexity and explanatory power, compared with previously used methods.The framework is demonstrated on real-world click streams, career paths, and transportation networks.Source: §6 · p. 9
- Temporal correlations invalidate time-aggregated and time-slice representations, while the method can infer higher-order models capturing temporal and topological characteristics.This conclusion is drawn for time-stamped relational data.Source: §6 · p. 9
- The paper uses a straightforward approach to choose the maximum time difference δ for extracting time-respecting paths; principled inference of δ remains an open problem.The proposed model-selection perspective could be used to infer a δ that maximizes Kopt.Source: §6 · p. 9
- Combining the framework with variable-order Markov models is a future direction expected to improve scalability.Current computational efficiency benefits from sparse higher-order layers and a smaller sample size for detecting the correct order than previous methods.Source: §6 · p. 9