PaperlayerView exact revision on arXiv

Source-linked AI summary

Representing higher-order dependencies in networks

Jian Xu, Thanuka L. Wickramarathne, Nitesh V. Chawla

arXiv:1508.03113v6cs.SIphysics.soc-ph

TL;DR

Conventional first-order networks can discard dependencies on previous steps when representing sequential data, limiting the fidelity of network analyses. The paper introduces HON to extract and embed variable-order dependencies while preserving compatibility with existing algorithms, and reports more accurate simulations and altered clustering and ranking results. HON is also compact because it adds higher-order structure only where dependencies are necessary.

  • Problem

    First-order network representations assume the next movement depends only on the current node, missing higher-order dependencies in sequential data and limiting movement simulations.

  • Method

    HON extracts significant variable-order dependencies from sequential data and embeds them in a network whose structure remains compatible with existing analysis algorithms.

  • Results

    HON produces more accurate movement simulations than conventional first-order and fixed second-order networks, with accuracy improving through maximum order five.

  • Takeaways & Limitations

    HON makes clustering and ranking reflect higher-order movement patterns, including indirect species-introduction pathways and repeated web-browsing behavior.

  • Takeaways & Limitations

    HON may require postprocessing to aggregate results across split nodes, and parameter choices can influence the resulting network structure.

Abstract

from arXiv · show

To ensure the correctness of network analysis methods, the network (as the input) has to be a sufficiently accurate representation of the underlying data. However, when representing sequential data from complex systems such as global shipping traffic or web clickstream traffic as networks, conventional network representations that implicitly assume the Markov property (first-order dependency) can quickly become limiting. This assumption holds that when movements are simulated on the network, the next movement depends only on the current node, discounting the fact that the movement may depend on several previous steps. However, we show that data derived from many complex systems can show up to fifth-order dependencies. In these cases, the oversimplifying assumption of the first-order network representation can lead to inaccurate network analysis results. To address this problem, we propose the Higher-Order Network (HON) representation that can discover and embed variable orders of dependencies in a network representation. Through a comprehensive empirical evaluation and analysis, we establish several desirable characteristics of HON, including accuracy, scalability, and direct compatibility with the existing suite of network analysis methods. We illustrate how HON can be applied to a broad variety of tasks, such as random walking, clustering, and ranking, and we demonstrate that by using it as input, HON yields more accurate results without any modification to these tasks.

Results

The Higher-Order Network (HON) represents variable-length dependencies in sequential data while retaining compatibility with conventional network analysis. Across synthetic and real-world data, HON improves movement simulation and changes clustering and ranking by preserving higher-order patterns.

  • Network representation: HON represents network nodes as entities or sequences of entities, allowing simulated movements to depend on multiple prior steps while retaining conventional graph structure.Its node and edge data structure remains compatible with existing network-analysis methods.
  • Validation: HON correctly recovered all 30 predefined higher-order dependencies in synthetic data, identified mixed orders from second through fourth, and extracted no false dependencies beyond fourth order.The synthetic dataset contained 10,000,000 movements and 400 first-order dependencies.
  • Higher-order dependencies: Real data contained dependencies up to fifth order in global shipping and third order in clickstream browsing, whereas retweet diffusion showed only first-order dependencies.The results support using variable orders rather than imposing a fixed first- or second-order representation.
  • Random walking: By increasing HON’s maximum order to five, one-step ship-movement accuracy doubled relative to the conventional first-order network.The first-order network’s two-step return probability was 10.7%, compared with above 40% on HON.
  • Random walking: HON’s three-step simulation was one magnitude more accurate than the first-order network because higher-order nodes preserve movement memory across steps.First-order simulations quickly lose the prior path context needed to reproduce return patterns and loops.
  • Clustering and ranking: HON changes downstream analyses by capturing indirect shipping pathways in clustering and repeated browsing patterns in PageRank-based ranking.In shipping, HON can reveal overlapping invasion-risk clusters; in clickstreams, pages can gain or lose ranking when higher-order loops are represented.

Materials and Methods

HON extracts significant, supported higher-order dependencies at variable orders, then embeds them in a network through higher-order nodes, edge conversion, and rewiring. Its design targets accurate, compact, and algorithm-compatible network representations.

  • Materials and Methods: HON construction first extracts supported higher-order rules that significantly change next-step probabilities, then adds those rules to a first-order network.Rule extraction grows path orders incrementally; network wiring adds higher-order nodes and rewires edges.
  • Materials and Methods: Rule extraction permits variable dependency orders, so different paths can condition future movements on different numbers of previous entities.For example, one path can encode a fourth-order dependency while another encodes a second-order dependency in the same dataset.
  • Materials and Methods: Higher-order rules become edges from sequence-based nodes, while rewiring preserves edge-weight sums and directs edges toward the highest possible orders.The wiring process creates higher-order nodes, rewires incoming edges, and redirects valid-rule edges when higher-order target nodes exist.
  • Materials and Methods: Given fixed parameters, HON wiring produces a unique result without optimization or greedy methods.The authors also state that the source code is publicly available.
  • Materials and Methods: Unlike variable-order Markov models and global-order estimation methods, HON is designed specifically as a network representation with variable dependency orders.The paper distinguishes HON from VOM trees and fixed-order models by focusing on network representation rather than only prediction or one global order.

Supplementary Material

The supplementary material identifies the rule-extraction and network-wiring algorithms used to construct HON.

  • Supplementary Material: The supplementary material includes an empirical comparison with the Variable-order Markov model.
  • Supplementary Material: Algorithm 1 presents the rule extraction algorithm.
  • Supplementary Material: Algorithm 2 presents the network wiring algorithm.

Figures and Tables

The figures compare first-order networks with Higher-Order Networks (HONs) across shipping movement simulation, port clustering, web-page ranking, and clickstream structure. They show that representing prior-step dependencies changes predicted movements, clusters, and rankings.

  • Network representations: The shipping network comparison uses edge weights from port-to-port trips, while HON conditions transitions on previous locations.In the first-order representation, movements from Singapore toward Los Angeles or Seattle have similar probabilities regardless of arrival path.
  • Random walking: HON doubles next-step random-walking accuracy and improves three-step accuracy by one magnitude over the first-order network.The shipping trajectories reserve the last three steps for testing; error bars on HONs are 0.11% ± 0.02%.
  • Clustering: First-order clustering conflates Valletta and Malta Freeport, whereas HON reveals overlapping clusters for international ports.The clustering uses MapEquation; overlapping HON clusters indicate multiple potential invasion sources.
  • Ranking: Using HON changes web-page PageRank scores, with 26% of pages showing more than 10% relative ranking changes and over 90% losing score.The ranking comparison uses a log-log scale, where deviations from the diagonal indicate significant changes.
  • Clickstream structure: For clickstreams, HON preserves first-order transitions while representing repeated photo-viewing and uploading loops that receive higher PageRank.The higher-order loop makes random walkers more likely to remain among the photo pages and less likely to return to the homepage.

1 Data sets

The study evaluates HON on global shipping, web clickstream, Weibo retweet, and synthetic trajectory data. These datasets span large real-world systems and controlled higher-order movement patterns.

  • Global shipping data: The shipping dataset covers 3,415,577 voyages by 65,591 ships across 4,108 ports and regions from May 1, 2012 to April 30, 2013.A minimum support of 10 filters noise in the shipping experiments.
  • Retweet data: The retweet dataset records 23,755,810 Weibo retweets involving 1,776,950 users.The data records who retweeted whose messages and when, and was crawled in 2012.

2 Algorithms

The algorithms extract variable-order dependency rules from sequential data and wire them into a graph with higher-order nodes and edges. The procedure compares conditional next-step distributions, controls support and order, and remains compatible with first-order data.

  • Distribution building: Observed subsequence frequencies are counted and normalized into movement distributions before graph construction.BUILDOBSERVATIONS counts subsequences from second order onward, while BUILDDISTRIBUTIONS builds paths and normalizes source-node frequencies.
  • Rule extraction: Rule extraction recursively extends source sequences when adding prior entities significantly changes the next-step probability distribution.The procedure starts at first order, stops at insufficient support or maximum order, and uses Kullback–Leibler divergence for comparison.
  • Rule extraction: The algorithm retains the last source node with a significantly distinct next-step distribution as the dependency order for each path.Rules are added when maximum order is exceeded or no matching higher-order source can be extended; preceding paths are also included for wiring.
  • Scope: The data type determines whether higher-order dependencies occur and how high their orders can be.The method is presented for vessel trajectories, gene sequences, language, diffusion, and other data types.
  • Compatibility: HON is backwards compatible: when data has no higher-order dependencies, all extracted rules are first-order and the output is a first-order network.The algorithm can also handle diffusion data by changing the subsequence-extraction function to use only the newest entity subsequence.
  • Network wiring: Network wiring converts rules in ascending order and rewires higher-order transitions to the highest available target nodes.Rewiring replaces lower-order edges when the corresponding higher-order node exists, preserving edge weights.

3 Parameter discussion

Minimum support and maximum order govern HON’s accuracy, size, and computational behavior. Appropriate support removes noise and compresses the network, while increasing maximum order captures additional dependencies until accuracy converges.

  • Minimum support: Low minimum support admits noisy subsequences, whereas high minimum support can exclude true but infrequent patterns.Thus, support must balance noise filtering against retention of less frequent dependencies.
  • Minimum support: The optimal minimum support can differ across data types and can be found by parameter sweeping.An appropriate minimum support can substantially reduce network size while improving representation accuracy.
  • Maximum order: Increasing maximum order from 1 to 5 keeps improving random-walking accuracy, which converges at order 5.Network size follows the same trend because most dependencies have lower orders and fewer have higher orders.
  • Maximum order: A high maximum order does not significantly increase HON construction time because longer subsequences usually fail the minimum-support requirement.A maximum order of five is sufficient for most applications.

4 Empirical comparison with the Variable-order Markov (VOM) model

The comparison shows that HON and VOM extract different higher-order rules because they retain nodes using different mechanisms. HON preserves the nodes and wiring needed to represent variable-order dependencies, whereas VOM can retain unnecessary nodes, prune necessary ones, and omit dependencies.

  • Rule extraction: HON and VOM use different mechanisms to decide which variable-order nodes to retain.HON grows rules from first order, whereas VOM prunes recursively from higher orders.
  • Rule extraction: HON retains a third-order dependency when its next-step distribution differs significantly from the corresponding lower-order distribution.In the example, g|f,d is retained because its distribution differs from g, while g|f is not retained when its distribution matches g.
  • Comparison with VOM: VOM can prune nodes needed to construct higher-order links while retaining nodes unnecessary for HON’s network representation.The example identifies f|d as necessary for building the link to g|f,d and g|f as unnecessary because it shares g’s distribution.
  • Network wiring: HON’s wiring captures distinct routing patterns while retaining first-order links and adding higher-order nodes and edges.The example represents ships arriving through the canal from d and e as taking different subsequent routes.
  • Comparison with VOM: VOM’s pruning may underestimate dependency orders by removing higher-order nodes whose distributions differ from first-order nodes.The cited example contrasts z|y,x,w with z.
  • Numerical comparison: Under identical parameters, HON and VOM produce considerably different extracted rules beyond first order, supporting separate rule-extraction procedures.The comparison used the same preprocessing, maximum order, minimum support, distance measure, and significance threshold.

Supplementary figures, tables, and algorithms

The supplementary material details HON’s rule-extraction and network-wiring procedures, illustrates their operation, and reports sensitivity, PageRank, and HON–VOM comparison materials.

  • Rule extraction: HON counts subsequences across orders and retains those meeting minimum support until the support or maximum-order condition fails.The procedure then compares next-step probability distributions for increasingly extended source sequences.
  • Network wiring: The supplementary network-wiring procedure converts first-order rules into edges, adds higher-order nodes, and rewires edges toward the highest-order valid targets.Edge weights are preserved during rewiring.
  • Parameter sensitivity: Increasing HON’s maximum order keeps improving random-walking accuracy but converges near maximum order 5.The sensitivity analysis also reports that suitable minimum support can reduce network size and improve representation accuracy.
  • HON–VOM comparison: The HON–VOM example shows VOM pruning nodes necessary for network representation while retaining nodes that are unnecessary.The resulting HON representation captures higher-order dependencies while retaining first-order information.
  • PageRank: Table S1 reports changes in PageRank scores when HON replaces a first-order network.The supplementary materials also list the top 15 PageRank score gainers and losers for clickstream data.
Loading 1508.03113v6…