zbMATH — the first resource for mathematics

A quotient space formulation for generative statistical analysis of graphical data. (English) Zbl 07363970
Summary: Complex analyses involving multiple, dependent random quantities often lead to graphical models – a set of nodes denoting variables of interest, and corresponding edges denoting statistical interactions between nodes. To develop statistical analyses for graphical data, especially towards generative modeling, one needs mathematical representations and metrics for matching and comparing graphs, and subsequent tools, such as geodesics, means, and covariances. This paper utilizes a quotient structure to develop efficient algorithms for computing these quantities, leading to useful statistical tools, including principal component analysis, statistical testing, and modeling. We demonstrate the efficacy of this framework using datasets taken from several problem areas, including letters, biochemical structures, and social networks.
68-XX Computer science
94-XX Information and communication theory, circuits
Full Text: DOI
[1] Almohamad, H.; Duffuaa, SO, A linear programming approach for the weighted graph matching problem, IEEE Trans. Pattern Anal. Mach. Intell., 15, 5, 522-525 (1993)
[2] Bahonar, H., Mirzaei, A., Sadri, S., Wilson, R.: Graph embedding using frequency filtering. IEEE Trans. Pattern Anal. Mach. Intell. (2019)
[3] Bai, Y., Ding, H., Qiao, Y., Marinovic, A., Gu, K., Chen, T., Sun, Y., Wang, W.: Unsupervised inductive graph-level representation learning via graph-graph proximity. In: IJCAI (2019)
[4] Caelli, T.; Kosinov, S., An eigenspace projection clustering method for inexact graph matching, IEEE Trans. Pattern Anal. Mach. Intell., 26, 4, 515-519 (2004)
[5] Carletti, V.; Foggia, P.; Saggese, A.; Vento, M., Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3, IEEE Trans. Pattern Anal. Mach. Intell., 40, 4, 804-818 (2017)
[6] Chapel, L., Alaya, M.Z., Gasso, G.: Partial optimal transport with applications on positive-unlabeled learning. Preprint arXiv:2002.08276 (2020)
[7] Chen, H., Perozzi, B., Hu, Y., Skiena, S.: Harp: Hierarchical representation learning for networks. In: Thirty-Second AAAI Conference on Artificial Intelligence (2018)
[8] Chizat, L.; Peyré, G.; Schmitzer, B.; Vialard, FX, Scaling algorithms for unbalanced optimal transport problems, Math. Comput., 87, 314, 2563-2609 (2018) · Zbl 1402.90120
[9] Chowdhury, S., Needham, T.: Gromov-wasserstein averaging in a riemannian framework. Preprint arXiv:1910.04308 (2019)
[10] Conte, D.; Foggia, P.; Sansone, C.; Vento, M., Thirty years of graph matching in pattern recognition, Int. J. Pattern Recogn. Artif. Intell., 18, 3, 265-298 (2004)
[11] Dai, M., Zhang, Z., Srivastava, A.: Testing stationarity of brain functional connectivity using change-point detection in fmri data. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 19-27 (2016)
[12] De Souza, F.D., Sarkar, S., Srivastava, A., Su, J.: Pattern theory-based interpretation of activities. In: 2014 22nd International Conference on Pattern Recognition (ICPR), IEEE, pp. 106-111 (2014)
[13] Defferrard, M., Bresson, X., Vandergheynst, P.: Convolutional neural networks on graphs with fast localized spectral filtering. In: Advances in Neural Information Processing Systems, pp. 3844-3852 (2016)
[14] Dryden, IL; Mardia, KV, Statistical Shape Analysis (1998), Hoboken: Wiley, Hoboken · Zbl 0901.62072
[15] Errica, F., Podda, M., Bacciu, D., Micheli, A.: A fair comparison of graph neural networks for graph classification. Preprint arXiv:1912.09893 (2019)
[16] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Logist. Q., 3, 1-2, 95-110 (1956)
[17] Gold, S.; Rangarajan, A., A graduated assignment algorithm for graph matching, IEEE Trans. Pattern Anal. Mach. Intell., 18, 4, 377-388 (1996)
[18] Gramfort, A., Peyré, G., Cuturi, M.: Fast optimal transport averaging of neuroimaging data. In: International Conference on Information Processing in Medical Imaging, Springer, pp. 261-272 (2015)
[19] Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 855-864 (2016)
[20] Guo, X., Bal, A.B., Needham, T., Srivastava, A.: Statistical shape analysis of brain arterial networks (bans). arXiv:2007.04793 (2020)
[21] Hakimi, SL, Optimum distribution of switching centers in a communication network and some related graph theoretic problems, Oper. Res., 13, 3, 462-475 (1965) · Zbl 0135.20501
[22] Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: Advances in Neural Information Processing Systems, pp. 1024-1034 (2017)
[23] Han, L.; Wilson, RC; Hancock, ER, Generative graph prototypes from information theory, IEEE Trans. Pattern Anal. Mach. Intell., 37, 10, 2013-2027 (2015)
[24] Horaud, R.: A short tutorial on graph laplacians, laplacian embedding, and spectral clustering (2012)
[25] Jain, B.J.: On the geometry of graph spaces. Discrete Appl. Math. 214, 126-144 (2016a) · Zbl 1346.05046
[26] Jain, B.J.: Statistical graph space analysis. Pattern Recogn. 60, 802-812 (2016b) · Zbl 1418.62262
[27] Jain, BJ; Obermayer, K., Structure spaces, J. Mach. Learn. Res., 10, 2667-2714 (2009) · Zbl 1235.68159
[28] Jain, B.J., Obermayer, K.: Learning in riemannian orbifolds. Preprint arXiv:1204.4294 (2012)
[29] Kersting, K., Kriege, N.M., Morris, C., Mutzel, P., Neumann, M.: Benchmark data sets for graph kernels. http://www.graphlearning.io/ (2020)
[30] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. Preprint arXiv:1609.02907 (2016)
[31] Kolaczyk, ED; Lin, L.; Rosenberg, S.; Walters, J.; Xu, J., Averages of unlabeled networks: geometric characterization and asymptotic behavior, Ann. Stat., 48, 1, 514-538 (2020) · Zbl 1439.62068
[32] Krcmar, M., Dhawan, A.: Application of genetic algorithms in graph matching. In: Proceedings of 1994 IEEE International Conference on Neural Networks (ICNN’94), IEEE, vol. 6, pp. 3872-3876 (1994)
[33] Kriege, NM; Johansson, FD; Morris, C., A survey on graph kernels, Appl. Netw. Sci., 5, 1, 1-42 (2020)
[34] Kuhn, HW, The hungarian method for the assignment problem, Naval Res. Logist. Q., 2, 1-2, 83-97 (1955)
[35] Lyzinski, V.; Fishkind, DE; Fiori, M.; Vogelstein, JT; Priebe, CE; Sapiro, G., Graph matching: Relax at your own risk, IEEE Trans. Pattern Anal. Mach. Intell., 38, 1, 60-73 (2016)
[36] Mackaness, WA; Beard, KM, Use of graph theory to support map generalization, Cartogr. Geogr. Inf. Syst., 20, 4, 210-221 (1993)
[37] Maron, H., Lipman, Y.: (probably) concave graph matching. Preprint arXiv:1807.09722 (2018)
[38] Mémoli, F., Gromov-wasserstein distances and the metric approach to object matching, Found. Comput. Math., 11, 4, 417-487 (2011) · Zbl 1244.68078
[39] Narayanan, A., Chandramohan, M., Venkatesan, R., Chen, L., Liu, Y., Jaiswal, S.: graph2vec: Learning distributed representations of graphs. Preprint arXiv:1707.05005 (2017)
[40] Neuhaus, M.; Bunke, H., Bridging the Gap Between Graph Edit Distance and Kernel Machines (2007), London: World Scientific, London · Zbl 1140.68473
[41] Ortega, A.; Frossard, P.; Kovačević, J.; Moura, JM; Vandergheynst, P., Graph signal processing: overview, challenges, and applications, Proc. IEEE, 106, 5, 808-828 (2018)
[42] Pele, O., Werman, M.: A linear time histogram metric for improved sift matching. In: European Conference on Computer Vision, Springer, pp. 495-508 (2008)
[43] Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: Online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 701-710 (2014)
[44] Peyré, G., Cuturi, M., Solomon, J.: Gromov-wasserstein averaging of kernel and distance matrices. In: International Conference on Machine Learning, pp. 2664-2672 (2016)
[45] Riesen, K., Bunke, H.: Iam graph database repository for graph based pattern recognition and machine learning. In: Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), Springer, pp. 287-297 (2008)
[46] Riesen, K.; Bunke, H., Approximate graph edit distance computation by means of bipartite graph matching, Image Vis. Comput., 27, 7, 950-959 (2009)
[47] Sato, R.: A survey on the expressive power of graph neural networks. Preprint arXiv:2003.04078 (2020)
[48] Schölkopf, B.; Smola, A.; Müller, KR, Nonlinear component analysis as a kernel eigenvalue problem, Neural Comput., 10, 5, 1299-1319 (1998)
[49] Séjourné T, Vialard FX, Peyré G (2020) The unbalanced gromov wasserstein distance: Conic formulation and relaxation. Preprint arXiv:2009.04266
[50] Severn, K., Dryden, I.L., Preston, S.P.: Manifold valued data analysis of samples of networks, with applications in corpus linguistics. Preprint arXiv:1902.08290 (2019) · Zbl 1428.62209
[51] Shervashidze, N.; Schweitzer, P.; Van Leeuwen, EJ; Mehlhorn, K.; Borgwardt, KM, Weisfeiler-lehman graph kernels, J. Mach. Learn. Res., 12, 77, 2539-2561 (2011) · Zbl 1280.68194
[52] Shirley, MD; Rushton, SP, The impacts of network topology on disease spread, Ecol. Complex., 2, 3, 287-299 (2005)
[53] Song, L.; Fukumizu, K.; Gretton, A., Kernel embeddings of conditional distributions: a unified kernel framework for nonparametric inference in graphical models, IEEE Signal Process. Mag., 30, 4, 98-111 (2013)
[54] Srivastava, A.; Klassen, EP, Functional and Shape Data Analysis (2016), Berlin: Springer, Berlin · Zbl 1376.62003
[55] Sun, J., Kunegis, J., Staab, S.: Predicting user roles in social networks using transfer learning with feature transformation. In: Proc. ICDM Workshop on Data Mining in Networks (2016)
[56] Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: Line: Large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web, International World Wide Web Conferences Steering Committee, pp. 1067-1077 (2015)
[57] Ugander, J., Karrer, B., Backstrom, L., Marlow, C.: The anatomy of the facebook social graph. Preprint arXiv:1111.4503 (2011)
[58] Umeyama, S., An eigendecomposition approach to weighted graph matching problems, IEEE Trans. Pattern Anal. Mach. Intell., 10, 5, 695-703 (1988) · Zbl 0678.05049
[59] Vayer, T., Chapel, L., Flamary, R., Tavenard, R., Courty, N.: Optimal transport for structured data with application on graphs. Preprint arXiv:1805.09114 (2018)
[60] Vishwanathan, SVN; Schraudolph, NN; Kondor, R.; Borgwardt, KM, Graph kernels, J. Mach. Learn. Res., 11, 1201-1242 (2010) · Zbl 1242.05112
[61] Vogelstein, JT; Conroy, JM; Lyzinski, V.; Podrazik, LJ; Kratzer, SG; Harley, ET; Fishkind, DE; Vogelstein, RJ; Priebe, CE, Fast approximate quadratic programming for graph matching, PLOS one, 10, 4, e0121002 (2015)
[62] Wang, D., Cui, P., Zhu, W.: Structural deep network embedding. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 1225-1234 (2016)
[63] Westenberg, M.A., van Hijum, S.A., Lulko, A.T., Kuipers, O.P., Roerdink, J.B.: Interactive visualization of gene regulatory networks with associated gene expression time series data. In: Visualization in Medicine and Life Sciences, Springer, pp. 293-311 (2008) · Zbl 1255.68272
[64] White, D.; Wilson, RC, Generative models for chemical structures, J. Chem. Inf. Model., 50, 7, 1257-1274 (2010)
[65] Wikipedia talk, chinese network dataset—KONECT. http://konect.uni-koblenz.de/networks/wiki_talk_zh (2017)
[66] Yanardag, P., Vishwanathan, S.: Deep graph kernels. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374 (2015)
[67] Yang, J., Market segmentation and information asymmetry in chinese stock markets: a var analysis, Financ. Rev., 38, 4, 591-609 (2003)
[68] Zhou, F.; De la Torre, F., Factorized graph matching, IEEE Trans. Pattern Anal. Mach. Intell., 38, 9, 1774-1789 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.