Planar Maximally Filtered Graph: private API

PortfolioOptimisers.PMFG_T2s — Function

PMFG_T2s(W::MatNum, nargout::Integer = 3)

Constructs a Triangulated Maximally Filtered Graph (TMFG) starting from a tetrahedron and recursively inserting vertices inside existing triangles (T2 move) in order to approximate a Maximal Planar Graph with the largest total weight, also known as the Planar Maximally Filtered Graph (PMFG). All weights must be non-negative.

This function is a core step in the DBHT (Direct Bubble Hierarchical Tree) and LoGo algorithms, providing the planar graph structure and clique information required for hierarchical clustering and sparse inverse covariance estimation.

nargout is a positional argument, and every caller passes it positionally.

The TMFG approximates the PMFG, and is not it

The planar maximally filtered graph is the exact solution of the weighted maximal planar graph problem, which is costly. The triangulation this function builds is the cheap greedy approximation to it, so the name of the function is the problem and the algorithm is the approximation. Both are maximal planar graphs, so both carry exactly $3N - 6$ edges against the $N - 1$ of a minimum spanning tree.

Mathematical definition

The T2 move inserts vertex $v$ into face $f$ and gains the weight of the three edges it adds. The greedy step takes the pair that gains most.

\[\begin{align} g(v,\, f) &= \sum_{u \in f} W_{u,\,v}\,, \\ (v^{\star},\, f^{\star}) &= \underset{v \notin V,\, f \in F}{\arg\max}\; g(v,\, f)\,. \end{align}\]

Where:

$W_{u,\,v}$: Weight of the pair $(u,\, v)$, the entry of the input matrix.
$f$: Triangular face, a set of three vertices.
$F$: Set of the faces built so far.
$V$: Set of the vertices inserted so far.
$g(v,\, f)$: Gain of inserting vertex $v$ into face $f$.
$N$: Number of assets.

Algorithm

Score every vertex by s, the row sum of W over the entries above the mean of W.
Take the four vertices of largest s as in_v[1:4], and the rest as ou_v.
Build the tetrahedron on those four vertices: its four faces into tri[1:4, :], and its six edges into A.
Build the gain table gain[v, f], one entry per vertex of ou_v and per face of tri.
Take the pair of largest gain, giving the vertex ve and the face agm. Remove ve from ou_v and record it in in_v.
Join ve to the three vertices of face agm in A, and record that face in clique3, so it becomes a 3-clique that is no longer a face.
Replace face agm and append two more, so the three faces of the split each carry ve.
Rebuild the three changed columns of gain, and zero the row of ve. Repeat from step 5 until every vertex is inserted.
Weight the structure: A = W ⊙ ((A + A') .== 1), so a stored entry is an edge and its value is its weight.
When nargout > 3, build cliques: the initial tetrahedron, then one 4-clique per inserted vertex, holding the face it entered and itself.
When nargout > 4, build cliqueTree: for each 4-clique, count in ss how many of its first three vertices every 4-clique holds, and mark the ones whose count is 2.

Arguments

W: N × N matrix of non-negative, finite weights (e.g. a similarity matrix from an AbstractNonNegativeSimilarityMatrixAlgorithm, or an absolute correlation matrix).
nargout: Number of outputs to build. cliques is built when nargout > 3 and cliqueTree when nargout > 4; each is nothing otherwise. The first three outputs are always built.

Validation

N >= 9 is required for a meaningful PMFG.
No entry in W is NaN.
All entries in W are non-negative.

An entry that is exactly zero passes all three and still costs the graph an edge, because A carries the structure in its sparsity pattern and this function declines no edge on the way in. That is assert_pmfg_weights's check, and it runs in the callers that consume the weighted structure rather than here, because logo! reads only the cliques and is unaffected by a zero.

The checks are a backstop, not the enforcement

Every estimator that reaches this function — NetworkEstimator, DBHT and LoGo — bounds its similarity field by AbstractNonNegativeSimilarityMatrixAlgorithm and calls assert_similarity_domain before it transforms, so a shipped configuration that would fail here fails earlier, at construction or at the seam, with a message that names the configuration rather than W.

These two checks are kept for the case those cannot cover: that family is open by declaration, so an extension can subtype it and return a negative anyway. The failure downstream is silent — DirectHb sums signed mass and a cancelling row manufactures a separating bubble — so a wrong clustering would come back with no error at all.

Returns

A::SparseMatrixCSC{<:Number, Int}: Adjacency matrix of the PMFG with weights.
tri::Matrix{Int}: List of triangles (triangular faces) in the PMFG.
clique3::Matrix{Int}: List of 3-cliques that are not triangular faces; all 3-cliques are given by [tri; clique3].
cliques::Option{Matrix{Int}}: List of all 4-cliques (tetrahedra), or nothing if nargout <= 3.
cliqueTree::Option{SparseMatrixCSC{Int, Int}}: 4-cliques tree structure (adjacency matrix), or nothing if nargout <= 4.

Related

References

[60] G. P. Massara, T. Di Matteo and T. Aste. Network Filtering for Big Data: Triangulated Maximally Filtered Graph. Journal of Complex Networks 5, 161–178 (2016).
[59] M. Tumminello, T. Aste, T. Di Matteo and R. N. Mantegna. A tool for filtering information in complex systems. Proceedings of the National Academy of Sciences 102, 10421–10426 (2005).

source

PortfolioOptimisers.assert_pmfg_weights — Function

assert_pmfg_weights(A::MatNum,
                    sim::Option{<:AbstractSimilarityMatrixAlgorithm} = nothing,
                    de::Option{<:AbstractDistanceEstimator} = nothing)

Check that the weights did not delete an edge from the graph PMFG_T2s built.

A maximal planar graph on N >= 3 vertices has exactly 3N - 6 edges, and PMFG_T2s returns the structure and the weights in one matrix, A = W ⊙ ((A + A') .== 1). An exactly zero weight is therefore an absent edge rather than a weak one, and what reaches the consumer is no longer a PMFG. This function counts the stored edges and refuses the difference.

The zero is admissible input and an unusable structure

PMFG_T2s's own check is >= 0 and stays that way, because a zero is an honest similarity. ExponentialSimilarity maps the infinite distance LogDistance returns at an exactly zero correlation to exp(-Inf), which is 0 exactly, and ComplementSimilarity maps D = 1 to 0. The value is right. What it cannot do is carry an edge.

Without this check the failure is a BoundsError about a matrix index, raised much later inside turn_into_Hclust_merges, because HierarchyConstruct4s then builds fewer merges than the dendrogram needs.

Where it runs, and where it deliberately does not

At the three sites that consume the weighted structure: DBHTs, calc_weighted_adjacency_graph and calc_distance_weighted_graph.

logo! is the fourth PMFG_T2s caller and is not guarded. It reads separators and cliques, which PMFG_T2s derives from the insertion order rather than from A, so a zero weight does not change its answer and refusing it would refuse a configuration that works.