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
- Score every vertex by
s, the row sum ofWover the entries above the mean ofW. - Take the four vertices of largest
sasin_v[1:4], and the rest asou_v. - Build the tetrahedron on those four vertices. Write its four faces into
tri[1:4, :], and its six edges intoA. - Build the gain table
gain[v, f], one entry for each vertex ofou_vand each face oftri. - Take the pair of largest gain, which gives the vertex
veand the faceagm. Removevefromou_vand record it inin_v. - Join
veto the three vertices of faceagminA, and record that face inclique3. The face becomes a 3-clique that is not a face. - Replace face
agmand append two more, so each of the three faces of the split hasve. - Compute the three changed columns of
gainagain, and set the row ofveto zero. Repeat from step 5 untilou_vis empty. - Weight the structure with
A = W ⊙ ((A + A') .== 1), so a stored entry is an edge and its value is its weight. - When
nargout > 3, buildcliques. 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. - When
nargout > 4, buildcliqueTree. For each 4-clique, count insshow many of its first three vertices each 4-clique holds, and mark the 4-cliques whose count is2.
Arguments
W:N × Nmatrix of non-negative, finite weights, such as a similarity matrix of anAbstractNonNegativeSimilarityMatrixAlgorithmor an absolute correlation matrix.nargout: Number of outputs to build. The function buildscliqueswhennargout > 3, andcliqueTreewhennargout > 4. Each isnothingotherwise. The function always builds the first three outputs.
Validation
size(W, 1) >= 9, raisingDimensionMismatch.- No entry of
WisNaN, raisingDomainError. - Every entry of
Wis non-negative, raisingDomainError.
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, ornothingifnargout <= 3.cliqueTree::Option{SparseMatrixCSC{Int, Int}}: Adjacency matrix of the tree of the 4-cliques, ornothingifnargout <= 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.
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
- Count the non-zero entries of
A, and divide the count by two, which givesedges.Ais symmetric, so it stores each edge two times. - Build
source, the part of the message that names the configuration, from the parts ofsimanddethat the caller gives. - Raise a
DomainErrorwhenedgesis notexpected, which is3N - 6.
Arguments
A:N × Nweighted adjacency matrix, the first output ofPMFG_T2s.sim: Similarity matrix algorithm that made the weights. The message names it, and the function reads it for nothing else, asassert_similarity_domainreads itsde.de: Distance estimator from which the similarity comes. The message names it next tosim.
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, raisingDomainError.
Returns
nothing.
Related
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]
- 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), arXiv:https://academic.oup.com/comnet/article-pdf/5/2/161/13794756/cnw015.pdf.