Learning Changes in Graphon Attachment Network Models

Xinyuan Fan, Bufan Li, Chenlei Leng, Weichi Wu
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:15779-15803, 2025.

Abstract

This paper introduces Graphon Attachment Network Models (GAN-M), a novel framework for modeling evolving networks with rich structural dependencies, grounded in graphon theory. GAN-M provides a flexible and interpretable foundation for studying network formation by leveraging graphon functions to define attachment probabilities, thereby combining the strengths of graphons with a temporal perspective. A key contribution of this work is a methodology for learning structural changes in these networks over time. Our approach uses graph counts—frequencies of substructures such as triangles and stars—to capture shifts in network topology. We propose a new statistic designed to learn changes in the resulting piecewise polynomial signals and develop an efficient method for change detection, supported by theoretical guarantees. Numerical experiments demonstrate the effectiveness of our approach across various network settings, highlighting its potential for dynamic network analysis.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-fan25f, title = {Learning Changes in Graphon Attachment Network Models}, author = {Fan, Xinyuan and Li, Bufan and Leng, Chenlei and Wu, Weichi}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {15779--15803}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/fan25f/fan25f.pdf}, url = {https://proceedings.mlr.press/v267/fan25f.html}, abstract = {This paper introduces Graphon Attachment Network Models (GAN-M), a novel framework for modeling evolving networks with rich structural dependencies, grounded in graphon theory. GAN-M provides a flexible and interpretable foundation for studying network formation by leveraging graphon functions to define attachment probabilities, thereby combining the strengths of graphons with a temporal perspective. A key contribution of this work is a methodology for learning structural changes in these networks over time. Our approach uses graph counts—frequencies of substructures such as triangles and stars—to capture shifts in network topology. We propose a new statistic designed to learn changes in the resulting piecewise polynomial signals and develop an efficient method for change detection, supported by theoretical guarantees. Numerical experiments demonstrate the effectiveness of our approach across various network settings, highlighting its potential for dynamic network analysis.} }
Endnote
%0 Conference Paper %T Learning Changes in Graphon Attachment Network Models %A Xinyuan Fan %A Bufan Li %A Chenlei Leng %A Weichi Wu %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-fan25f %I PMLR %P 15779--15803 %U https://proceedings.mlr.press/v267/fan25f.html %V 267 %X This paper introduces Graphon Attachment Network Models (GAN-M), a novel framework for modeling evolving networks with rich structural dependencies, grounded in graphon theory. GAN-M provides a flexible and interpretable foundation for studying network formation by leveraging graphon functions to define attachment probabilities, thereby combining the strengths of graphons with a temporal perspective. A key contribution of this work is a methodology for learning structural changes in these networks over time. Our approach uses graph counts—frequencies of substructures such as triangles and stars—to capture shifts in network topology. We propose a new statistic designed to learn changes in the resulting piecewise polynomial signals and develop an efficient method for change detection, supported by theoretical guarantees. Numerical experiments demonstrate the effectiveness of our approach across various network settings, highlighting its potential for dynamic network analysis.
APA
Fan, X., Li, B., Leng, C. & Wu, W.. (2025). Learning Changes in Graphon Attachment Network Models. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:15779-15803 Available from https://proceedings.mlr.press/v267/fan25f.html.

Related Material