Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks

References

• Adamic, L., and Adar, E. (2005), “How to Search a Social Network,” Social Networks, 27, 187–203. DOI: 10.1016/j.socnet.2005.01.007.
   Web of Science ®Google Scholar
• Albert, R., and Barabási, A.-L. (2002), “Statistical Mechanics of Complex Networks,” Reviews of Modern Physics, 74, 47. DOI: 10.1103/RevModPhys.74.47.
   Web of Science ®Google Scholar
• Babai, L. (2015), “Graph Isomorphism in Quasipolynomial Time,” arXiv no. 1512.03547.
   Google Scholar
• Barak, B., Chou, C.-N., Lei, Z., Schramm, T., and Sheng, Y. (2019), “(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs,” in Advances in Neural Information Processing Systems, pp. 9190–9198.
   Google Scholar
• Bickel, P. J., and Chen, A. (2009), “A Nonparametric View of Network Models and Newman-Girvan and Other Modularities,” Proceedings of the National Academy of Sciences of the United States of America, 106, 21068–21073. DOI: 10.1073/pnas.0907096106.
   PubMed Web of Science ®Google Scholar
• Bickel, P. J., and Doksum, K. A. (2015), Mathematical Statistics: Basic Ideas and Selected Topics, Volume I (Vol. 117), Boca Raton, FL: CRC Press.
   Google Scholar
• Chang, J., Kolaczyk, E. D., and Yao, Q. (2018), “Estimation of Subgraph Density in Noisy Networks,” arXiv no. 1803.02488.
   Google Scholar
• Chung, F., and Lu, L. (2001), “The Diameter of Sparse Random Graphs,” Advances in Applied Mathematics, 26, 257–279. DOI: 10.1006/aama.2001.0720.
   Web of Science ®Google Scholar
• Conte, D., Foggia, P., Sansone, C., and Vento, M. (2004), “Thirty Years of Graph Matching in Pattern Recognition,” International Journal of Pattern Recognition and Artificial Intelligence, 18, 265–298. DOI: 10.1142/S0218001404003228.
   Web of Science ®Google Scholar
• Csardi, G., and Nepusz, T. (2006), “The igraph Software Package for Complex Network Research,” InterJournal, Complex Systems, 1695, 1–9.
   Google Scholar
• Cullina, D., and Kiyavash, N. (2016), “Improved Achievability and Converse Bounds for Erdos-Renyi Graph Matching,” in ACM SIGMETRICS Performance Evaluation Review (Vol. 44), ACM, pp. 63–72. DOI: 10.1145/2964791.2901460.
   Google Scholar
• Cullina, D., and Kiyavash, N. (2017), “Exact Alignment Recovery for Correlated Erdős-Rényi Graphs,” arXiv no. 1711.06783.
   Google Scholar
• Ding, J., Ma, Z., Wu, Y., and Xu, J. (2018), “Efficient Random Graph Matching via Degree Profiles,” arXiv no. 1811.07821.
   Google Scholar
• Dwork, C., and Roth, A. (2014), “The Algorithmic Foundations of Differential Privacy,” Foundations and Trends® in Theoretical Computer Science, 9, 211–407. DOI: 10.1561/0400000042.
   Google Scholar
• Erdős, P., and Rényi, A. (1963), “Asymmetric Graphs,” Acta Mathematica Academiae Scientiarum Hungarica, 14, 295–315. DOI: 10.1007/BF01895716.
   Google Scholar
• Fishkind, D. E., Meng, L., Sun, A., Priebe, C. E., and Lyzinski, V. (2019), “Alignment Strength and Correlation for Graphs,” Pattern Recognition Letters, 125, 295–302. DOI: 10.1016/j.patrec.2019.05.008.
   Web of Science ®Google Scholar
• Fishkind, D. E., Sussman, D. L., Tang, M., Vogelstein, J. T., and Priebe, C. E. (2013), “Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown,” SIAM Journal on Matrix Analysis and Applications, 34, 23–39. DOI: 10.1137/120875600.
   Web of Science ®Google Scholar
• Foggia, P., Percannella, G., and Vento, M. (2014), “Graph Matching and Learning in Pattern Recognition in the Last 10 Years,” International Journal of Pattern Recognition and Artificial Intelligence, 28, 1450001. DOI: 10.1142/S0218001414500013.
   Web of Science ®Google Scholar
• Franke, B., and Wolfe, P. J. (2016), “Network Modularity in the Presence of Covariates,” arXiv no. 1603.01214.
   Google Scholar
• Grave, E., Joulin, A., and Berthet, Q. (2018), “Unsupervised Alignment of Embeddings With Wasserstein Procrustes,” arXiv no. 1805.11222.
   Google Scholar
• Heimann, M., Shen, H., Safavi, T., and Koutra, D. (2018), “Regal: Representation Learning-Based Graph Alignment,” in Proceedings of the 27th ACM International Conference on Information and Knowledge Management, ACM, pp. 117–126.
   Google Scholar
• Janson, S. (2004), “Large Deviations for Sums of Partly Dependent Random Variables,” Random Structures & Algorithms, 24, 234–248.
   Web of Science ®Google Scholar
• Kim, J. H., Sudakov, B., and Vu, V. H. (2002), “On the Asymmetry of Random Regular Graphs and Random Graphs,” Random Structures and Algorithms, 21, 216–224. DOI: 10.1002/rsa.10054.
   Web of Science ®Google Scholar
• Korula, N., and Lattanzi, S. (2014), “An Efficient Reconciliation Algorithm for Social Networks,” Proceedings of the VLDB Endowment, 7, 377–388. DOI: 10.14778/2732269.2732274.
   Google Scholar
• Lancaster, T. (2000), “The Incidental Parameter Problem Since 1948,” Journal of Econometrics, 95, 391–413. DOI: 10.1016/S0304-4076(99)00044-5.
   Web of Science ®Google Scholar
• Liu, X., Wang, Y., and Wang, L. (2019), “Mcdiarmid-Type Inequalities for Graph-Dependent Variables and Stability Bounds,” in Advances in Neural Information Processing Systems, pp. 10890–10901.
   Google Scholar
• Luo, B., and Hancock, E. R. (2001), “Structural Graph Matching Using the EM Algorithm and Singular Value Decomposition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 23, 1120–1136. DOI: 10.1109/34.954602.
   Web of Science ®Google Scholar
• Lyzinski, V. (2018), “Information Recovery in Shuffled Graphs via Graph Matching,” IEEE Transactions on Information Theory, 64, 3254–3273. DOI: 10.1109/TIT.2018.2808999.
   Web of Science ®Google Scholar
• Lyzinski, V., Adali, S., Vogelstein, J. T., Park, Y., and Priebe, C. E. (2014), “Seeded Graph Matching via Joint Optimization of Fidelity and Commensurability,” arXiv no. 1401.3813.
   Google Scholar
• Lyzinski, V., Fishkind, D., Fiori, M., Vogelstein, J., Priebe, C., and Sapiro, G. (2016), “Graph Matching: Relax at Your Own Risk,” IEEE Transactions on Pattern Analysis & Machine Intelligence, 38, 60–73.
   PubMed Web of Science ®Google Scholar
• Lyzinski, V., Fishkind, D., and Priebe, C. (2014), “Seeded Graph Matching for Correlated Erdös-Rényi Graphs,” Journal of Machine Learning Research, 15, 3513–3540.
   Web of Science ®Google Scholar
• Lyzinski, V., Levin, K., Fishkind, D., and Priebe, C. (2016), “On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matching,” Journal of Machine Learning Research, 17, 1–34.
   Web of Science ®Google Scholar
• Lyzinski, V., and Sussman, D. L. (2020), “Matchability of Heterogeneous Networks Pairs,” Information and Inference: A Journal of the IMA, 9, 749–783. DOI: 10.1093/imaiai/iaz031.
   PubMedGoogle Scholar
• Mossel, E., and Xu, J. (2019), “Seeded Graph Matching via Large Neighborhood Statistics,” in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, pp. 1005–1014.
   Google Scholar
• Narayanan, A., and Shmatikov, V. (2009), “De-Anonymizing Social Networks,” in 2009 30th IEEE Symposium on Security and Privacy, IEEE, pp. 173–187.
   Google Scholar
• Newman, M. E. (2001), “The Structure of Scientific Collaboration Networks,” Proceedings of the National Academy of Sciences of the United States of America, 98, 404–409. DOI: 10.1073/pnas.98.2.404.
   PubMed Web of Science ®Google Scholar
• Newman, M. E., and Watts, D. J. (1999), “Renormalization Group Analysis of the Small-World Network Model,” Physics Letters A, 263, 341– 346. DOI: 10.1016/S0375-9601(99)00757-4.
   Web of Science ®Google Scholar
• Neyman, J., and Scott, E. L. (1948), “Consistent Estimates Based on Partially Consistent Observations,” Econometrica: Journal of the Econometric Society, 16, 1–32. DOI: 10.2307/1914288.
   Web of Science ®Google Scholar
• Onaran, E., Garg, S., and Erkip, E. (2016), “Optimal De-Anonymization in Random Graphs With Community Structure,” in 2016 IEEE 37th Sarnoff Symposium. DOI: 10.1109/SARNOF.2016.7846734.
   Google Scholar
• Pedarsani, P., and Grossglauser, M. (2011), “On the Privacy of Anonymized Networks,” in Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 1235–1243. DOI: 10.1145/2020408.2020596.
   Google Scholar
• Qin, T., and Rohe, K. (2013), “Regularized Spectral Clustering Under the Degree-Corrected Stochastic Blockmodel,” in Advances in Neural Information Processing Systems.
   Google Scholar
• Rohe, K., Chatterjee, S., and Yu, B. (2011), “Spectral Clustering and the High-Dimensional Stochastic Blockmodel,” The Annals of Statistics, 39, 1878–1915. DOI: 10.1214/11-AOS887.
   Web of Science ®Google Scholar
• Shirani, F., Garg, S., and Erkip, E. (2017), “Seeded Graph Matching: Efficient Algorithms and Theoretical Guarantees,” arXiv no. 1711.10360.
   Google Scholar
• Stigler, S. M. (2007), “The Epic Story of Maximum Likelihood,” Statistical Science, 22, 598–620. DOI: 10.1214/07-STS249.
   Web of Science ®Google Scholar
• Sussman, D. L., Tang, M., and Priebe, C. E. (2014), “Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 36, 48–57. DOI: 10.1109/TPAMI.2013.135.
   PubMed Web of Science ®Google Scholar
• Vogelstein, J., Conroy, J., Lyzinski, V., Podrazik, L., Kratzer, S., Harley, E., Fishkind, D., Vogelstein, R., and Priebe, C. (2014), “Fast Approximate Quadratic Programming for Graph Matching,” PLoS ONE, 10, e0121002. DOI: 10.1371/journal.pone.0121002.
   Web of Science ®Google Scholar
• Von Mering, C., Krause, R., Snel, B., Cornell, M., Oliver, S. G., Fields, S., and Bork, P. (2002), “Comparative Assessment of Large-Scale Data Sets of Protein–Protein Interactions,” Nature, 417, 399. DOI: 10.1038/nature750.
   PubMed Web of Science ®Google Scholar
• Watts, D., and Strogatz, S. H. (1998), “Collective Dynamics of ‘Small-World’ Networks,” Nature, 393, 440. DOI: 10.1038/30918.
   PubMed Web of Science ®Google Scholar
• Yan, J., Tian, Y., Zha, H., Yang, X., Zhang, Y., and Chu, S. M. (2013), “Joint Optimization for Consistent Multiple Graph Matching,” in Proceedings of the IEEE International Conference on Computer Vision, pp. 1649–1656.
   Google Scholar
• Yan, J., Yin, X., Lin, W., Deng, C., Zha, H., and Yang, X. (2016), “A Short Survey of Recent Advances in Graph Matching,” in Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval, ACM, pp. 167–174. DOI: 10.1145/2911996.2912035.
   Google Scholar
• Yang, Q., and Sze, S. (2007), “Path Matching and Graph Matching in Biological Networks,” Journal of Computational Biology, 14, 56–67. DOI: 10.1089/cmb.2006.0076.
   PubMed Web of Science ®Google Scholar
• Yartseva, L., and Grossglauser, M. (2013), “On the Performance of Percolation Graph Matching,” in Proceedings of the First ACM Conference on Online Social Networks, ACM, pp. 119–130. DOI: 10.1145/2512938.2512952.
   Google Scholar
• Zachary, W. W. (1977), “An Information Flow Model for Conflict and Fission in Small Groups,” Journal of Anthropological Research, 33, 452–473. DOI: 10.1086/jar.33.4.3629752.
   Web of Science ®Google Scholar
• Zaslavskiy, M., Bach, F., and Vert, J.-P. (2009), “Global Alignment of Protein–Protein Interaction Networks by Graph Matching Methods,” Bioinformatics, 25, 1259–1267. DOI: 10.1093/bioinformatics/btp196.
   PubMed Web of Science ®Google Scholar
• Zhang, S., and Tong, H. (2016), “Final: Fast Attributed Network Alignment,” in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp. 1345–1354.
   Google Scholar
• Zhang, Y. (2018a), “Consistent Polynomial-Time Unseeded Graph Matching for Lipschitz Graphons,” arXiv no. 1807.11027.
   Google Scholar
• Zhang, Y. (2018b), “Unseeded Low-Rank Graph Matching by Transform-Based Unsupervised Point Registration,” arXiv no. 1807.04680.
   Google Scholar
• Zhao, Y., Levina, E., and Zhu, J. (2012), “Consistency of Community Detection in Networks Under Degree-Corrected Stochastic Block Models,” The Annals of Statistics, 40, 2266–2292. DOI: 10.1214/12-AOS1036.
   Web of Science ®Google Scholar