Метод порождения графов с контролем статистических свойств
Автор: Бишук А.Ю., Зухба А.В.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 3 (63) т.16, 2024 года.
Бесплатный доступ
В работе предлагается метод условного порождения графов, учитывающий статистические характеристики графов. Данные характирстики разделяются на две группы. Первая группа, называемая простыми статистиками, может быть вычислена эффективными детерминированными алгоритмами со сложностью не более квадратичной от числа вершин. Такое разделение диктуется дороговизной использования вычислительно сложных алгоритмов на графах, по размеру приближенных к реальным. Вторая группа характеристик порождается в скрытом пространстве и отвечает за закономерности графа, которые невозможно описать «простыми статистиками». Этот подход позволяет порождать графы с точно заданными статистическими характеристиками, при этом сохраняя их разнообразие. Более того, данный метод может быть применен для порождения графов, имеющих схожую структуру с исходным. Работоспособность предложенного метода подтверждается вычислительным экспериментом, проведенном на датасетах Citeseer и Cora.
Порождение данных, порождение графов, графы, вариационный автокодировщик, теория графов, генеративные модели, условное порождение, вариационный вывод
Короткий адрес: https://sciup.org/142243258
IDR: 142243258
Список литературы Метод порождения графов с контролем статистических свойств
- Боровков А.А. Теория вероятностей. Москва: Наука, Физматлит, 1986. 432 с.
- Pattabiraman В. [et al.\. Fast algorithms for the maximum clique problem on massive sparse graphs // Algorithms and Models for the Web Graph: 10th International Workshop. 2013. P. 156-169.
- Saramaki J. [et al.}. Generalizations of the clustering coefficient to weighted complex networks // Physical Review E. 2007. V. 75(2). P. 027105.
- Ying Z. [et al.}. Gnnexplainer: Generating explanations for graph neural networks // Advances in neural information processing systems. 2019. V. 32.
- Kipf T.N., Welling M. Variational Graph Auto-Encoders // Stat. 2016. V. 1050. P. 21.
- Chamberlain B. [et al.}. Grand: Graph neural diffusion // International Conference on Machine Learning. 2021. P. 1407-1418.
- Latora V., Marchiori M. A measure of centralitv based on network efficiency // New Journal of Physics. 2007. V. 9(6). P. 188.
- Kingma D.P., Welling M. Auto-Encoding Variational Baves // Stat. 2022. V. 1050. P. 10.
- Sen P. [et al.}. Collective classification in network data // Al magazine. 2008. V. 29(3). P. 93.
- Rossi R., Ahmed N. The network data repository with interactive graph analytics and visualization // Proceedings of the AAAI conference on artificial intelligence. 2015. V. 29(1).
- Deng L. The mnist database of handwritten digit images for machine learning research [best of the web] // IEEE signal processing magazine. 2012. V. 29(6). P. 141-142.
- Krizhevsky A. [et al.}. Learning multiple layers of features from tiny images // Technical Report University of Toronto. Toronto, Ontario. 2009.
- Sohn K., Lee H., Yan X. Learning structured output representation using deep conditional generative models // Advances in neural information processing systems. 2015. V. 28.
- Mitton J. [et al.}. A Graph VAE and Graph Transformer Approach to Generating Molecular Graphs // ArXiv, abs/2104.04345.
- Simonovsky M., Komodakis N. Graphvae: Towards generation of small graphs using variational autoencoders // Artificial Neural Networks and Machine I.earning K'AXX 2018: 27th International Conference on Artificial Neural Networks. 2018. P. 412-422.
- Zhao J. [et al.}. GraphTune: An Efficient Dependency-Aware Substrate to Alleviate Irregularity in Concurrent Graph Processing // ACM Transactions on Architecture and Code Optimization. 2023. V. 20(3). P. 1-24.
- De Cao N., Kipf T. An implicit generative model for small molecular graphs // ICML 2018 workshop on Theoretical Foundations and Applications of Deep Generative Models. 2018.
- Velickovic P. [et al.}. Graph attention networks // Stat. 2017. V. 1050(20). P. 10-48550.
