用矩匹配和神经表示,高效准确地估计大规模网络的图函数。
A Few Moments Please: Scalable Graphon Learning via Moment Matching
- 通过隐式神经网络直接匹配图的子图统计量来估计图函数。
- 在75%的基准测试中优于现有方法,大图计算效率显著提升。
- 提出矩混合法增强学习效果,适合网络分析与图分类任务。
图函数作为稠密图序列的极限对象,在网络数据分析中具有核心地位。然而,现有图函数估计方法常因依赖潜在变量或高成本度量(如Gromov-Wasserstein距离)而难以扩展至大规模网络,且缺乏分辨率无关的近似能力。本文提出一种新型可扩展图函数估计器,通过矩匹配直接恢复图函数,利用隐式神经表示(INRs)建模坐标到图函数值的映射,并训练其匹配观测图中的经验子图计数(即矩)。该直接估计机制实现多项式时间求解,关键规避了Gromov-Wasserstein优化的组合复杂性。基于基础理论,我们证明:当观测子图模式足够代表真实图函数时(在充分大或样本充足的条件下),估计结果在切距离上达到可证明的上界。此外,我们引入MomentMixup——一种在矩空间进行混合法的数据增强技术,显著提升图函数学习性能。实验表明,该方法在小图上精度高,在大图上计算效率优异,在75%的基准设置中超越当前最优可扩展估计器,其余情况相当;同时,MomentMixup在多数基准上提升了图分类准确率。
原文摘要 · Abstract (English)
Graphons, as limit objects of dense graph sequences, play a central role in the statistical analysis of network data. However, existing graphon estimation methods often struggle with scalability to large networks and resolution-independent approximation, due to their reliance on estimating latent variables or costly metrics such as the Gromov-Wasserstein distance. In this work, we propose a novel, scalable graphon estimator that directly recovers the graphon via moment matching, leveraging implicit neural representations (INRs). Our approach avoids latent variable modeling by training an INR--mapping coordinates to graphon values--to match empirical subgraph counts (i.e., moments) from observed graphs. This direct estimation mechanism yields a polynomial-time solution and crucially sidesteps the combinatorial complexity of Gromov-Wasserstein optimization. Building on foundational results, we establish a theoretical guarantee: when the observed subgraph motifs sufficiently represent those of the true graphon (a condition met with sufficiently large or numerous graph samples), the estimated graphon achieves a provable upper bound in cut distance from the ground truth. Additionally, we introduce MomentMixup, a data augmentation technique that performs mixup in the moment space to enhance graphon-based learning. Our graphon estimation method achieves strong empirical performance--demonstrating high accuracy on small graphs and superior computational efficiency on large graphs--outperforming state-of-the-art scalable estimators in 75\% of benchmark settings and matching them in the remaining cases. Furthermore, MomentMixup demonstrated improved graph classification accuracy on the majority of our benchmarks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。