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

• URL: http://arxiv.org/abs/2603.09564v1
• Date: Tue, 10 Mar 2026 12:08:56 GMT
• Title: a-TMFG: Scalable Triangulated Maximally Filtered Graphs via Approximate Nearest Neighbors
• Abstract summary: We present a novel approach to scaling the construction of artificial graphs from data inspired by TMFG.<n>The algorithm is tested for robustness and is evaluated on datasets with millions of observations.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule.<n>We analyze the algorithm under the block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves proportional sampling to cluster size.
  arXiv  Detail & Related papers  (2026-07-30T02:45:31Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs.<n>We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
  arXiv  Detail & Related papers  (2026-02-13T08:12:38Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
  We show how to parameterise topological masks as a learnable function of a weighted adjacency matrix. Our efficient masking algorithms provide strong performance gains for tasks on image and point cloud data.
  arXiv  Detail & Related papers  (2024-10-04T14:24:06Z)
• Learning Cartesian Product Graphs with Laplacian Constraints [10.15283812819547]
  We study the problem of learning Cartesian product graphs under Laplacian constraints. We establish statistical consistency for the penalized maximum likelihood estimation. We also extend our method for efficient joint graph learning and imputation in the presence of structural missing values.
  arXiv  Detail & Related papers  (2024-02-12T22:48:30Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport [0.1933681537640272]
  Nearest neighbour graphs are widely used to capture the geometry or topology of a dataset. One of the most common strategies to construct such a graph is based on selecting a fixed number k of nearest neighbours (kNN) for each point. We propose a simple approach to construct an adaptive neighbourhood graph from a single parameter, based on quadratically regularised optimal transport.
  arXiv  Detail & Related papers  (2022-08-01T04:24:58Z)
• Sublinear Algorithms for Hierarchical Clustering [14.124026862687941]
  We study hierarchical clustering for massive graphs under three well-studied models of sublinear computation. We design sublinear algorithms for hierarchical clustering in all three models.
  arXiv  Detail & Related papers  (2022-06-15T16:25:27Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
  Graph neural networks (GNNs) are a popular class of parametric model for learning over graph-structured data. Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on benchmark tasks. In this work, we ask whether these results can be extended to heterogeneous graphs, which encode multiple types of relationship between different entities.
  arXiv  Detail & Related papers  (2020-11-19T06:03:35Z)
• Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
  Graph Convolutional Networks (GCNs) have proven to be successful tools for semi-supervised classification on graph-based datasets. We propose a new GCN variant whose three-part filter space is targeted at dense graphs.
  arXiv  Detail & Related papers  (2020-08-03T08:48:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.