PMFG: private API

PortfolioOptimisers.PMFG_T2s — Function
PMFG_T2s(W::MatNum, nargout::Integer = 3)

Build a Triangulated Maximally Filtered Graph (TMFG), an approximation of the maximal planar graph of the largest total weight.

The function starts from a tetrahedron. At each step it inserts one vertex into a triangular face, the T2 move. The Planar Maximally Filtered Graph (PMFG) is an earlier approximation of the same graph. All weights must be non-negative.

DBHTs, logo! and the network estimators call this function. It gives them the planar graph and its cliques. DBHT clusters the assets on them, and LoGo computes a sparse precision matrix on them.

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

The TMFG is not the PMFG

The problem of the weighted maximal planar graph asks for the maximal planar subgraph of the largest total weight, and it is NP-complete. Neither graph solves it exactly. The planar maximally filtered graph of [128] is a greedy heuristic. It takes the edges in order of weight, and it keeps an edge while the graph stays planar.

The TMFG that this function builds is a different and cheaper heuristic, from [129]. It inserts vertices, not edges, so the two graphs are different in general. The name of the function names the PMFG, but the algorithm builds the TMFG. Both are maximal planar graphs, so each has exactly $3N - 6$ edges. A minimum spanning tree has $N - 1$.

Steps 1 and 2 below are a rule of the MATLAB code that accompanies [127]. Algorithm 1 of [129] starts from the tetrahedron of the largest total weight. Steps 9 to 11 and the bound N >= 9 come from the same code, not from [129].

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 the insertion of vertex $v$ into face $f$.
  • $N$: Number of assets.

Algorithm

  1. Score every vertex by s, the row sum of W over the entries above the mean of W.
  2. Take the four vertices of largest s as in_v[1:4], and the rest as ou_v.
  3. Build the tetrahedron on those four vertices. Write its four faces into tri[1:4, :], and its six edges into A.
  4. Build the gain table gain[v, f], one entry for each vertex of ou_v and each face of tri.
  5. Take the pair of largest gain, which gives the vertex ve and the face agm. Remove ve from ou_v and record it in in_v.
  6. Join ve to the three vertices of face agm in A, and record that face in clique3. The face becomes a 3-clique that is not a face.
  7. Replace face agm and append two more, so each of the three faces of the split has ve.
  8. Compute the three changed columns of gain again, and set the row of ve to zero. Repeat from step 5 until ou_v is empty.
  9. Weight the structure with A = W ⊙ ((A + A') .== 1), so a stored entry is an edge and its value is its weight.
  10. When nargout > 3, build cliques. Its first row is the first tetrahedron. Each other row is the 4-clique of one inserted vertex, which holds the face that the vertex entered and the vertex.
  11. When nargout > 4, build cliqueTree. For each 4-clique, count in ss how many of its first three vertices each 4-clique holds, and mark the 4-cliques whose count is 2.

Arguments

  • W: N × N matrix of non-negative, finite weights, such as a similarity matrix of an AbstractNonNegativeSimilarityMatrixAlgorithm or an absolute correlation matrix.
  • nargout: Number of outputs to build. The function builds cliques when nargout > 3, and cliqueTree when nargout > 4. Each is nothing otherwise. The function always builds the first three outputs.

Validation

  • size(W, 1) >= 9, raising DimensionMismatch.
  • No entry of W is NaN, raising DomainError.
  • Every entry of W is non-negative, raising DomainError.

An entry that is exactly zero passes all three checks, but the graph loses an edge for it. A holds the structure in its sparsity pattern, and this function refuses no edge. assert_pmfg_weights holds that check. The callers that read the weighted structure run it. This function does not run it, because logo! reads only the cliques, and a zero does not change its result.

The estimators refuse a negative weight first

NetworkEstimator, DBHT and LoGo reach this function. Each bounds its similarity field by AbstractNonNegativeSimilarityMatrixAlgorithm, and each calls assert_similarity_domain before it maps the distances. Thus a configuration of the library that fails here fails earlier, in the constructor or in assert_similarity_domain. The message of that error names the configuration and not W.

The two checks of this function cover the case that the estimators cannot cover. Any package can subtype that family, so an extension can return a negative weight. Without the checks, the error downstream is silent. DirectHb sums signed weights, so a negative weight can change the set of converging bubbles, and the result is a wrong clustering with no error.

Returns

  • A::SparseMatrixCSC{<:Number, Int}: Weighted adjacency matrix of the TMFG.
  • tri::Matrix{Int}: List of the triangular faces of the TMFG, one face for each row.
  • clique3::Matrix{Int}: List of the 3-cliques that are not triangular faces, one 3-clique for each row. [tri; clique3] holds every 3-clique.
  • cliques::Option{Matrix{Int}}: List of every 4-clique, a tetrahedron, one for each row, or nothing if nargout <= 3.
  • cliqueTree::Option{SparseMatrixCSC{Int, Int}}: Adjacency matrix of the tree of the 4-cliques, or nothing if nargout <= 4.

Related

References

  • [129] 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). Section III.A, Algorithm 1, and Section I for the PMFG as a greedy heuristic.
  • [128] 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). For the PMFG and its construction by edge insertion.
source
PortfolioOptimisers.assert_pmfg_weights — Function
assert_pmfg_weights(A::MatNum,
                    sim::Option{<:AbstractSimilarityMatrixAlgorithm} = nothing,
                    de::Option{<:AbstractDistanceEstimator} = nothing)

Check that no zero weight removed an edge from the graph that PMFG_T2s built.

A maximal planar graph on N >= 3 vertices has exactly 3N - 6 edges. PMFG_T2s returns the structure and the weights in one matrix, A = W ⊙ ((A + A') .== 1). Thus a weight that is exactly zero is an absent edge, not a weak edge, and the consumer does not get a PMFG. This function counts the stored edges, and it refuses a count that is not 3N - 6.

A zero weight is a valid input, but it removes an edge

The check of PMFG_T2s is >= 0, because zero is a correct similarity. LogDistance returns an infinite distance at a correlation of exactly zero, and ExponentialSimilarity maps it to exp(-Inf), which is exactly 0. ComplementSimilarity maps D = 1 to 0. The value is correct, but a zero weight cannot hold an edge.

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

The callers that run the check

The three callers that read the weighted structure run it: DBHTs, calc_weighted_adjacency_graph and calc_distance_weighted_graph.

logo! is the fourth caller of PMFG_T2s, and it does not run the check. It reads the separators and the cliques. PMFG_T2s derives them from the order of insertion and not from A, so a zero weight does not change the result of logo!. A refusal there would refuse a configuration that works.

Algorithm

  1. Count the non-zero entries of A, and divide the count by two, which gives edges. A is symmetric, so it stores each edge two times.
  2. Build source, the part of the message that names the configuration, from the parts of sim and de that the caller gives.
  3. Raise a DomainError when edges is not expected, which is 3N - 6.

Arguments

  • A: N × N weighted adjacency matrix, the first output of PMFG_T2s.
  • sim: Similarity matrix algorithm that made the weights. The message names it, and the function reads it for nothing else, as assert_similarity_domain reads its de.
  • de: Distance estimator from which the similarity comes. The message names it next to sim.

Each caller gives the parts that it holds, so the message names all of the configuration that the caller knows. calc_distance_weighted_graph holds both parts, calc_weighted_adjacency_graph and DBHTs hold the similarity, and a caller that holds only the matrices names neither.

Validation

  • The number of stored edges is 3N - 6, raising DomainError.

Returns

  • nothing.

Related

source

References

[127]
W.-M. Song, T. Di Matteo and T. Aste. Hierarchical information clustering by means of topologically embedded graphs. PloS one 7, e31929 (2012).
[128]
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).
[129]