提出a-TMFG算法，让大规模数据也能高效构建关联图
a-TMFG: Scalable Triangulated Maximally Filtered Graphs via Approximate Nearest Neighbors
- 用k近邻图初建骨架，动态估算缺失相关性
- 在百万级数据上验证有效，内存与时间开销显著降低
- 适合无天然图结构的机器学习任务
传统三角最大过滤图（TMFG）需预先计算并存储密集相关矩阵，限制了其在小中规模数据上的应用。本文识别出大规模使用时的内存与运行时间瓶颈，并提出近似三角最大过滤图（a-TMFG）算法。该方法基于k-近邻图（kNNG）进行初始构造，采用内存管理策略实时搜索和估计缺失相关性，从而控制组合爆炸问题。算法在含百万观测的数据集上进行了鲁棒性测试与评估，结果表明其可高效构建适用于监督与非监督学习的人工图结构，尤其适用于无自然图结构的场景。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。