提出一种能保留社区结构的图数据平均图构造方法。
The Spectral Barycentre of a Set of Graphs with Community Structure
- 基于图拉普拉斯矩阵特征值设计多尺度谱距离
- 约束特征向量使平均图继承原始图的社区结构
- 在随机块模型下可收敛到真实均值，实测效果良好
图数据的均值图（barycentre graph）在处理图数据的机器学习中至关重要，它能概括训练集中图的拓扑与连通性结构。本文采用基于归一化图拉普拉斯矩阵特征值的多尺度谱距离定义图间距离。通过优化问题可确定均值图的特征值，但特征向量需额外约束。本文提出对均值图特征向量的结构约束，确保其继承样本图的拓扑结构。特征向量通过探索Soules基库的算法求解。当图是平衡随机块模型的随机实现时，该算法在图规模趋于无穷时，几乎必然收敛到群体均值。蒙特卡洛模拟验证了估计器的理论性质；真实图实验表明该方法在非理想环境中仍有效。
原文摘要 · Abstract (English)
The notion of barycentre graph is of crucial importance for machine learning algorithms that process graph-valued data. The barycentre graph is a "summary graph" that captures the mean topology and connectivity structure of a training dataset of graphs. The construction of a barycentre requires the definition of a metric to quantify distances between pairs of graphs. In this work, we use a multiscale spectral distance that is defined using the eigenvalues of the normalized graph Laplacian. The eigenvalues -- but not the eigenvectors -- of the normalized Laplacian of the barycentre graph can be determined from the optimization problem that defines the barycentre. In this work, we propose a structural constraint on the eigenvectors of the normalized graph Laplacian of the barycentre graph that guarantees that the barycentre inherits the topological structure of the graphs in the sample dataset. The eigenvectors can be computed using an algorithm that explores the large library of Soules bases. When the graphs are random realizations of a balanced stochastic block model, then our algorithm returns a barycentre that converges asymptotically (in the limit of large graph size) almost-surely to the population mean of the graphs. We perform Monte Carlo simulations to validate the theoretical properties of the estimator; we conduct experiments on real-life graphs that suggest that our approach works beyond the controlled environment of stochastic block models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。