PaperlayerView exact revision on arXiv

Source-linked AI summary

Network Filtering for Big Data: Triangulated Maximally Filtered Graph

Guido Previde Massara, T. Di Matteo, Tomaso Aste

arXiv:1505.02445v2cs.DScond-mat.stat-mechcs.IR

TL;DR

Dense dependency data require filtering methods that reduce complexity while retaining relevant information. TMFG constructs a triangulated network by maximizing an information-related score and supports flexible updates and modeling. Its execution time scales approximately as O(p^2), versus O(p^3) for PMFG.

  • Problem

    The paper addresses how to filter dense, redundant dependency data into sparse networks while retaining relevant information and reducing complexity.

  • Method

    TMFG builds a triangulation using arbitrary similarity weights and local and non-local topological moves, with clique and separator structure available for modeling.

  • Results

    TMFG execution times scale approximately as O(p^2), while PMFG execution times scale approximately as O(p^3).

  • Takeaways & Limitations

    TMFG supports clustering, community detection, and modeling while enabling efficient inference through controlled clique dimensions and limited treewidth.

Abstract

from arXiv · show

We propose a network-filtering method, the Triangulated Maximally Filtered Graph (TMFG), that provides an approximate solution to the Weighted Maximal Planar Graph problem. The underlying idea of TMFG consists in building a triangulation that maximizes a score function associated with the amount of information retained by the network. TMFG uses as weights any arbitrary similarity measure to arrange data into a meaningful network structure that can be used for clustering, community detection and modeling. The method is fast, adaptable and scalable to very large datasets, it allows online updating and learning as new data can be inserted and deleted with combinations of local and non-local moves. TMFG permits readjustments of the network in consequence of changes in the strength of the similarity measure. The method is based on local topological moves and can therefore take advantage of parallel and GPUs computing. We discuss how this network-filtering method can be used intuitively and efficiently for big data studies and its significance from an information-theoretic perspective.

I. INTRODUCTION

The paper motivates filtering dense, redundant dependency data into sparse planar networks that retain relevant structure. It positions TMFG as a fast, adaptable alternative for high-dimensional and frequently updated datasets.

  • I. INTRODUCTION: Information filtering is needed to reduce data complexity and dimensionality while preserving dataset integrity.The paper identifies redundancy across time and variables as an opportunity for retaining relevant dependency structure.
  • I. INTRODUCTION: MST and PMFG filter dense weight matrices by retaining significant subgraphs under global topological constraints.The PMFG retains more edges than the MST while remaining sparse.
  • I. INTRODUCTION: The WMPG problem seeks a maximal planar subgraph with maximum total edge weight, but it is NP-complete.PMFG provides a greedy solution, while other algorithms provide approximate solutions.
  • I. INTRODUCTION: Planar filtered graphs support clustering, dimensionality reduction, market-structure analysis, and portfolio diversification.The cited applications use clique structure or dependency edges to analyze complex datasets.
  • I. INTRODUCTION: TMFG is presented as computationally efficient, online-updatable, and applicable to multipoint dependencies and Markov Random Field modeling.Using T2 and S operators produces triangulated or chordal graphs with clique and separator structure.
  • I. INTRODUCTION: Planar-subgraph extraction is relevant to finance, facility layout, integrated circuits, systems biology, and social systems.Planarity is sometimes geometric and sometimes used to constrain network complexity.

A. Planar Maximally Filtered Graph

This section reviews planar filtered-graph construction through PMFG and deltahedron heuristics. The methods preserve planarity through constrained insertions, with speed gained by avoiding repeated planarity tests.

  • A. Planar Maximally Filtered Graph: PMFG adds weighted edges in non-increasing order and discards edges that violate planarity.Its construction performs O(p^2) planarity tests, each with O(p) complexity, yielding O(p^3) overall complexity.
  • B. Deltahedron heuristic: The deltahedron heuristic starts from K4 and inserts each new vertex into a triangular face using a T2 move.The insertion adds three edges and preserves planarity by construction.
  • B. Deltahedron heuristic: The deltahedron heuristic is faster than PMFG because its vertex ordering is fixed initially and each T2 move avoids planarity testing.The method has no known performance guarantee.
  • B. Deltahedron heuristic: T2 moves produce chordal graphs, enabling polynomial-time solutions for several generally hard graph problems.Examples include maximum clique, graph coloring, and maximum independent set.
  • B. Deltahedron heuristic: The GH-heuristic improves deltahedron construction by caching the best and next-best insertion options and updating the cache during execution.A parameter can optionally control the algorithm’s greediness.

C. Local topological moves: T1, T2, A, & S

TMFG combines local insertion, rewiring, and swap operations to adjust planar filtered graphs. These moves trade chordality against gain and can support topology changes as networks evolve.

  • C. Local topological moves: T1, T2, A, & S: T2 insertion splits a triangular face into three triangular faces, after which the original triangle becomes a 3-clique.This operation is the basic vertex-insertion move used in TMFG construction.
  • C. Local topological moves: T1, T2, A, & S: Leung’s extension can be generated by applying two T2 moves and one T1 move.The figure connects a multi-vertex extension with the local move set.
  • C. Local topological moves: T1, T2, A, & S: The A move inserts a vertex inside a plaquette formed by two neighboring triangular faces and generally produces non-chordal graphs.It can be constructed by combining T1 and T2 moves.
  • C. Local topological moves: T1, T2, A, & S: TMFG can combine T1, T2, A, and S moves to generate planar and higher-genus non-planar filtered graphs.The operators provide controlled topology changes as the network evolves.
  • C. Local topological moves: T1, T2, A, & S: The S operator relabels vertices without changing graph topology, preserving planarity while potentially changing aggregate weight functions.Unlike the local moves, S need not operate locally.

A. TMFG construction

TMFG constructs a planar triangulation by repeatedly inserting the vertex–face pair that maximizes a score gain, beginning from a K4 clique. Optional local moves can improve gains but may sacrifice chordality and increase structural complexity.

  • Core construction: TMFG starts from a K4 clique and repeatedly inserts the vertex–face pair producing the maximum score increase.The score can be the sum of weights on edges added by the insertion.
  • Score optimization: TMFG evaluates gains with a score function S(vh, {va, vb, vc}) for adding vertex vh inside a triangular face.For weighted graphs, the gain is the sum of the three incident edge weights.
  • Score optimization: A cache stores maximum gains and corresponding best vertices for each current face, updating after each insertion and face replacement.The pseudocode calculates MaxGain and BestVertex, selects their maximizing pair, inserts the vertex, and updates the cache.
  • Core construction: The T2 move inserts a vertex into a triangular face, replacing that face with three new triangular faces.The inserted face becomes a clique separator in the resulting graph.
  • Extensions and trade-offs: Optional T1 and A moves exchange or add edges locally, while swap moves can improve gains without changing overall topology.With T1 or A moves, the graph generally becomes a bubble-tree rather than a chordal clique tree.
  • Extensions and trade-offs: TMFG is not greedy over every feasible planar edge insertion, yet it performs as well as or better than PMFG for a broad class of weight matrices.The cited class includes squared correlation coefficient matrices from empirical time series.

B. Dynamical adaptability

TMFG supports dynamic network adaptation through local and inverse operators, allowing the filtered graph to change as data and similarity weights evolve.

  • Online adaptation: TMFG operators support online updates as new data are generated and the matrix of weights changes.The framework also supports creating new nodes when additional variables become relevant and deleting existing nodes.
  • Online adaptation: The local operators T1, T2, T−1, A, A−1, and local S enable dynamical adaptation of the network.These moves provide the mechanisms for modifying the filtered graph as its inputs change.

C. Parallelization and big data

TMFG’s local construction and clique-separator hierarchy support parallel computation, including a proposed O(p) construction using O(log p) processors and linear-size cache updates.

  • Parallel computation: TMFG’s local moves make its construction suitable for parallelization.The operators can perform local network modifications without requiring globally distributed moves.
  • Parallel computation: Triangular separating cliques divide the network into nested inside and outside subgraphs that can be developed independently.Processors can be assigned to seed cliques for local calculations.
  • Complexity and storage: A proposed parallel implementation computes TMFG in O(p) using O(log p) processors.The passage presents this as a possible implementation rather than an implemented result.
  • Complexity and storage: The cache grows linearly with problem dimension, and basis triangles can be assigned to different processors for parallel cache updates.This addresses the size of score vectors in large problems.

D. Memory usage

TMFG can reduce memory demands by computing only correlations or multipoint dependencies needed for incremental gain updates instead of storing full dependency structures.

  • Pairwise dependencies: When q is less than p, TMFG can use approximately p × q memory for time series rather than approximately p×(p−1)/2 for a full correlation matrix.The comparison applies to pairwise dependence measures such as correlation.
  • Multipoint dependencies: For multipoint dependencies, TMFG stores the time series and calculates only relevant gain functions, while other methods may require data on the order of p^3.Examples include partial correlation and mutual information.

IV. MODELING WITH TMFG: INFORMATION THEORETIC PERSPECTIVE

TMFG models high-dimensional systems by factorizing their joint distribution over small cliques and separators, reducing estimation to local marginal probabilities. An information-theoretic construction selects moves that minimize divergence from the unknown true distribution.

  • TMFG filtering reduces interdependent variables to a network of the most relevant interactions for statistical modeling.
  • The TMFG structure forms a tree of 4-cliques separated by 3-clique separators, yielding a triangulated, chordal graph.This structure supports factorized probability models and automatically exposes the clique and separator organization.
  • The model measures dissimilarity between the unknown true distribution P(X) and the TMFG-factorized estimate Q(X) using Kullback-Leibler divergence.The treatment considers discrete variables, with a similar extension described as possible for continuous variables.
  • An information-theoretic TMFG construction chooses each feasible move to minimally increase Hm, thereby minimizing the modeled divergence.For a T2 move, the relevant insertion adds vertex v inside triangular face t and generates a 4-clique u.

V. EXAMPLES OF TMFG CONSTRUCTION AND COMPARISON WITH PMFG

The paper compares TMFG with PMFG across execution time, algorithmic variants, and diverse synthetic and real weight matrices. TMFG scales substantially better and can match or exceed PMFG in retained edge weight, depending on the weight structure.

  • TMFG execution time scales approximately as O(p^2), whereas PMFG scales approximately as O(p^3).Polynomial fits are TT MF G ∼2 · 10−7 · p2 + 6 · 10−4p and TP MF G ∼2 · 10−6 · p3 + 3 · 10−5p2.
  • Execution times are several orders of magnitude faster for TMFG than for PMFG across tested matrix dimensions.Figure 7 compares dimensions p from 50 to 10000 using two-parameter polynomial fits.
  • The comparison evaluates four TMFG variants: the base TMFG, TMFG-T1, TMFG-S, and TMFG-A.The base TMFG uses only T2 moves, while the other variants add local optimization stages.
  • PMFG is usually stronger when high weights are sparse, while TMFG is more effective when high weights are denser or limited to structured subsets.The reported explanation is that PMFG can select isolated high-weight edges, whereas TMFG efficiently selects edge subsets with high total weight.
  • For structured correlation matrices generated with 20 factors, TMFG performs better than PMFG; the study also evaluates less structured 50- and 100-factor matrices and real stock correlations.The experiments use p = 400 for synthetic matrices and p = 342 for the real correlation data.

VI. CONCLUSIONS

TMFG provides a fast, adaptable family of approximate solutions to the Maximal Planar Graph problem, with controlled topology and support for multivariate dependence modeling. Its construction reduces computational and memory demands while enabling online network updates and extensions beyond planarity.

  • VI. CONCLUSIONS: TMFG constructed with T2 and S produces chordal graphs with controlled clique dimensions, enabling efficient inference and Markov Random Field modeling.The construction also yields the associated clique-and-separator structure automatically.
  • VI. CONCLUSIONS: TMFG supports genuinely multivariate score functions over clique elements, including Mutual Information, Total Correlation, Partial Correlation, and Likelihood functions.This extends the supported dependence measures beyond bivariate functions such as correlation.
  • VI. CONCLUSIONS: TMFG avoids preliminary calculation and sorting of all score values, and when p ≫ q it can reduce memory use by calculating dependence functions on demand.The memory footprint can use p × q data points instead of p^2 correlation values or p^d values for a d-variate dependence function.
  • VI. CONCLUSIONS: Local and non-local operators allow controlled topology changes as networks evolve, while the geometric formulation supports generalization to higher-genus simplicial complexes.Future work targets richer structures beyond and below planarity and applications in physical, financial, and biological systems.
Loading 1505.02445v2…