a-TMFG: Scalable Triangulated Maximally Filtered Graphs via Approximate Nearest Neighbors

Lionel Yelibi

stat.MLMar 10, 2026

a-TMFG: Scalable Triangulated Maximally Filtered Graphs via Approximate Nearest Neighbors

Authors: Lionel Yelibi

Organizations: Department of Statistical Sciences, University of Cape Town, Rondebosch, 7701, Cape Town, Western Cape, South Africa

Abstract

The traditional Triangular Maximally Filtered Graph (TMFG) construction requires pre-computation and storage of a dense correlation matrix; this limits its applicability to small and medium-sized datasets. Here we identify key memory and runtime complexity challenges when using TMFG at scale. We then present the Approximate Triangular Maximally Filtered Graph (a-TMFG) algorithm. This is a novel approach to scaling the construction of artificial graphs from data inspired by TMFG. The method employs k-Nearest Neighbors Graphs (kNNG) for initial construction, and implements a memory management strategy to search and estimate missing correlations on-the-fly. This provides representations to control combinatorial explosion. The algorithm is tested for robustness to the parameters and noise, and is evaluated on datasets with millions of observations. This new method provides a parsimonious way to construct graphs for use-cases where graphs are used as input to supervised and unsupervised learning but where no natural graph exists.

Figures & tables

Figure 1: The face counts against the location

L_{j}

of a given face

f_{j}

in the face universe

\mathcal{F}

used in the TFMG algorithm. This shows that most of the selected faces are found at the end of the sequence of faces (on the right near location

L_{j}=0

) rather than near the beginning (near location

L_{j}=-1

). This implies that scaling can be enhanced by exploiting the exploration frontier on the right of the plot, and forgetting unnecessary faces (See Section 2 ). This is what the “approximate" refinement of the TMFG method (a-TFMG) exploits.

Panel of Figure 2 — Figure 2: Network topologies derived from a 1-factor Gaussian mixture model. ( 2(a) ) block-diagonal correlation matrix. ( 2(b) ) Exact TMFG constructed from the same dataset. The TMFG induces a sparse, hierarchical structure, highlighting the need for generative models capable of capturing short-range interactions (see Section 4 ).

Panel of Figure 3 — Figure 3: Topological consistency of 1,000 exact TMFGs estimated from identically parameterized 1-factor models ( $N=1000,K=5$ ). ( 3(a) ) Average shortest path between intra-cluster nodes. ( 3(b) ) Distribution of pairwise Jaccard scores between the resulting edge lists. The near-zero Jaccard overlap illustrates the instability of TMFGs on purely block-diagonal matrices, motivating the use of GMRFs in Section 4 .

Figure 4: UMAP projection of an a-TMFG constructed for $N=100,000$ nodes generated from a Gaussian Markov Random Field (Section 4.1 ). The scalable algorithm successfully recovers the ground-truth clusters while preserving the dendritic, maximal planar topology characteristic of exact TMFGs.

Figure 5: Average Jaccard similarity between a-TMFG and the exact connectivity matrix across varying dataset sizes $N$ and GMRF spatial dependence parameter $\alpha$ . As analyzed in Section 4.2 , the algorithm optimally recovers structures when $0.2\leq\alpha\leq 0.3$ .

Panel of Figure 6 — Figure 6: Impact of the initial $k$ -NN graph neighborhood size $k$ on a-TMFG construction for $N=50,000$ . ( 6(a) ) Jaccard similarity relative to the unconstrained graph. ( 6(b) ) Total runtime in seconds. A moderate neighborhood size ( $k\geq 50$ ) is sufficient to achieve high structural fidelity while minimizing initial computational overhead (Section 4.3 ).

Panel of Figure 7 — Figure 7: Trade-offs associated with the maximum face universe limit $|\mathcal{F}|$ for $N=100,000$ . ( 7(a) ) Jaccard similarity to the exact TMFG. ( 7(b) ) Construction runtime. Constraining $|\mathcal{F}|$ to the “elbow" of the curve in the Jaccard similarity score of Figure ( 7(a) ) optimally balances structural accuracy with computational and memory efficiency (Section 4.4 ).

Figure 8: Empirical runtime scaling of the proposed a-TMFG against the exact Fast-TMFG algorithm. The bounded universe and HNSW queries enable a-TMFG to maintain a near-linear

\mathcal{O}(UN)

trajectory, whereas exact methods hit computational bottlenecks near

N=25,000

due to their inherent

\mathcal{O}(N^{2})

complexity (Section 4.5 ).

Graph Construction

See all 15 papers

Memory Is No Longer a Bottleneck: Memory-Efficient Graph Filtering for Scalable Collaborative Filtering
Jun 19, 2026Jin-Duk Park, Won-Yong ShinMemory-Efficient Inference Krylov Subspace Methods
School of Mathematics and Computing (Computational Science and Engineering), Yonsei University, Seoul 03722, Republic of Korea
Scalable GNN-based Knowledge Graph Representation Learning with Efficient Message Passing
Sep 28, 2026Huu Tan Mai, Cuong Xuan Chu, Heiko Paulheim +1Graph Neural Networks Graph Representation Learning
Bosch Center for Artificial Intelligence, Robert-Bosch-Campus 1, 71272 Renningen, Germany · University of Mannheim, Schloss, 68131 Mannheim, Germany
RAFT: Redundancy-Aware Input Filtering for Temporal Graph Neural Network Training
Oct 17, 2026Yue Dai, Sarah Zhou, Youtao ZhangTemporal GNNs
Department of Computer Science, Illinois Institute of Technology, Chicago, USA · BASIS Independent Silicon Valley, San Jose, CA, USA · Department of Computer Science, University of Pittsburgh, Pittsburgh, USA

Jun 19, 2026J/K move · Enter open · S save

Memory Is No Longer a Bottleneck: Memory-Efficient Graph Filtering for Scalable Collaborative Filtering

Jin-Duk Park, Won-Yong Shin

School of Mathematics and Computing (Computational Science and Engineering), Yonsei University, Seoul 03722, Republic of Korea

Memory-Efficient Inference Krylov Subspace Methods Collaborative Filtering

Open paper AskPDF arXiv

Graph convolutional networks (GCNs) have demonstrated significant success in capturing complex user-item relationships for collaborative filtering (CF). However, due to their reliance on extensive model training, training-free graph filtering (GF)-based CF methods have emerged as a promising alternative, offering computational efficiency by smoothing graph signals via matrix operations. In particular, polynomial GF-based approaches demonstrate improved accuracy through their ability to design more expressive and flexible filtering functions. Despite these advantages, existing GF methods suffer from a critical memory bottleneck: they necessitate storing the full item similarity graph, incurring prohibitive memory costs for large-scale datasets, which limits their practical applicability. To tackle this challenge, we propose Mem-GF (Memory-efficient GF), a new GF-based CF method that departs from conventional designs by principally leveraging the structure of Krylov subspaces as a core mechanism for approximating polynomial graph filters without explicitly storing the item similarity graph. We theoretically analyze the minimum Krylov subspace size that guarantees lossless approximation. Through extensive experiments, we demonstrate that Mem-GF achieves up to 5.74

\times

lower memory usage and 4.38

\times

speedup in runtime, while consistently exceeding the recommendation accuracy of state-of-the-art GF and GCN-based methods. Mem-GF robustly scales to datasets with tens of millions of interactions, establishing itself as a practically viable and theoretically grounded solution for efficient CF.

Abstract

Graph Construction

Explore similar work

Memory Is No Longer a Bottleneck: Memory-Efficient Graph Filtering for Scalable Collaborative Filtering

Scalable GNN-based Knowledge Graph Representation Learning with Efficient Message Passing

RAFT: Redundancy-Aware Input Filtering for Temporal Graph Neural Network Training