{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T11:12:09Z","timestamp":1719918729704},"reference-count":45,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,8,21]],"date-time":"2020-08-21T00:00:00Z","timestamp":1597968000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"We propose a novel algorithm for unsupervised graph representation learning with attributed graphs. It combines three advantages addressing some current limitations of the literature: (i) The model is inductive: it can embed new graphs without re-training in the presence of new data; (ii) The method takes into account both micro-structures and macro-structures by looking at the attributed graphs at different scales; (iii) The model is end-to-end differentiable: it is a building block that can be plugged into deep learning pipelines and allows for back-propagation. We show that combining a coarsening method having strong theoretical guarantees with mutual information maximization suffices to produce high quality embeddings. We evaluate them on classification tasks with common benchmarks of the literature. We show that our algorithm is competitive with state of the art among unsupervised graph representation learning methods.<\/jats:p>","DOI":"10.3390\/a13090206","type":"journal-article","created":{"date-parts":[[2020,8,21]],"date-time":"2020-08-21T13:21:51Z","timestamp":1598016111000},"page":"206","source":"Crossref","is-referenced-by-count":0,"title":["Hierarchical and Unsupervised Graph Representation Learning with Loukas\u2019s Coarsening"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"http:\/\/orcid.org\/0000-0003-1498-8251","authenticated-orcid":false,"given":"Louis","family":"B\u00e9thune","sequence":"first","affiliation":[{"name":"ENS de Lyon, UCB Lyon 1, CNRS, Laboratoire de Physique, UMR 5672, 69342 Lyon, France"}]},{"given":"Yacouba","family":"Kaloga","sequence":"additional","affiliation":[{"name":"ENS de Lyon, UCB Lyon 1, CNRS, Laboratoire de Physique, UMR 5672, 69342 Lyon, France"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-4536-8354","authenticated-orcid":false,"given":"Pierre","family":"Borgnat","sequence":"additional","affiliation":[{"name":"ENS de Lyon, UCB Lyon 1, CNRS, Laboratoire de Physique, UMR 5672, 69342 Lyon, France"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-4906-9573","authenticated-orcid":false,"given":"Aur\u00e9lien","family":"Garivier","sequence":"additional","affiliation":[{"name":"ENS de Lyon, UCB Lyon 1, CNRS, UMPA UMR 5669 and LIP UMR 5668, 69342 Lyon, France"}]},{"given":"Amaury","family":"Habrard","sequence":"additional","affiliation":[{"name":"Laboratoire Hubert Curien, UJM-Saint-Etienne, UMR 5516, 42100 Saint-\u00c9tienne, France"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,21]]},"reference":[{"key":"ref_1","unstructured":"Hamilton, W.L., Ying, R., and Leskovec, J. (2017). Representation learning on graphs: Methods and applications. arXiv."},{"key":"ref_2","unstructured":"Narayanan, A., Chandramohan, M., Venkatesan, R., Chen, L., Liu, Y., and Jaiswal, S. (2017). graph2vec: Learning distributed representations of graphs. arXiv."},{"key":"ref_3","first-page":"1","article-title":"Graph reduction with spectral and cut guarantees","volume":"20","author":"Loukas","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"ref_4","unstructured":"Togninalli, M., Ghisu, E., Llinares-L\u00f3pez, F., Rieck, B., and Borgwardt, K. (2019, January 8\u201314). Wasserstein weisfeiler-lehman graph kernels. Proceedings of the Annual Conference on Neural Information Processing Systems 2019, Vancouver, BC, Canada."},{"key":"ref_5","first-page":"1201","article-title":"Graph kernels","volume":"11","author":"Vishwanathan","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"ref_6","unstructured":"Shervashidze, N., and Borgwardt, K.M. (2009, January 7\u201310). Fast subtree kernels on graphs. Proceedings of the 23rd Annual Conference on Neural Information Processing Systems 2009, Vancouver, BC, Canada."},{"key":"ref_7","first-page":"2539","article-title":"Weisfeiler-lehman graph kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_8","unstructured":"Feragen, A., Kasenburg, N., Petersen, J., De Bruijne, M., and Borgwardt, K. (2013, January 5\u20138). Scalable kernels for graphs with continuous attributes. Proceedings of the 27th Annual Conference on Neural Information Processing Systems 2013, Lake Tahoe, NV, USA."},{"key":"ref_9","unstructured":"Kriege, N., and Mutzel, P. (2012). Subgraph matching kernels for attributed graphs. arXiv."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Morris, C., Kriege, N.M., Kersting, K., and Mutzel, P. (2016, January 12\u201315). Faster kernels for graphs with continuous attributes via hashing. Proceedings of the 2016 IEEE 16th International Conference on Data Mining (ICDM), Barcelona, Spain.","DOI":"10.1109\/ICDM.2016.0142"},{"key":"ref_11","unstructured":"Veli\u010dkovi\u0107, P., Fedus, W., Hamilton, W.L., Li\u00f2, P., Bengio, Y., and Hjelm, R.D. (2019, January 6\u20139). Deep graph infomax. Proceedings of the ICLR, New Orleans, LA, USA."},{"key":"ref_12","unstructured":"Hamilton, W., Ying, Z., and Leskovec, J. (2017, January 4\u20139). Inductive representation learning on large graphs. Proceedings of the Annual Conference on Neural Information Processing Systems 2017, Long Beach, CA, USA."},{"key":"ref_13","unstructured":"Sun, F.Y., Hoffman, J., Verma, V., and Tang, J. (2020, January 26\u201330). Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. Proceedings of the ICLR, Addis Ababa, Ethiopia."},{"key":"ref_14","unstructured":"Bianchi, F.M., Grattarola, D., Livi, L., and Alippi, C. (2019). Hierarchical representation learning in graph neural networks with node decimation pooling. arXiv."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1109\/TCSI.2012.2215780","article-title":"Kron reduction of graphs with applications to electrical networks","volume":"60","author":"Dorfler","year":"2013","journal-title":"IEEE Trans. Circuits Syst. I Regul. Pap."},{"key":"ref_16","unstructured":"Bravo Hermsdorff, G., and Gunderson, L. (2019, January 8\u201314). A unifying framework for spectrum-preserving graph sparsification and coarsening. Proceedings of the Annual Conference on Neural Information Processing Systems 2019, Vancouver, BC, Canada."},{"key":"ref_17","unstructured":"Ying, Z., You, J., Morris, C., Ren, X., Hamilton, W., and Leskovec, J. (2018, January 3\u20138). Hierarchical graph representation learning with differentiable pooling. Proceedings of the Annual Conference on Neural Information Processing Systems 2018, Montreal, QC, Canada."},{"key":"ref_18","unstructured":"Maria, F., Grattarola, D., and Alippi, C. (2020, January 12\u201318). Spectral clustering with graph neural networks for graph pooling. Proceedings of the 37th International Conference on Machine Learning, Online Event."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S.Y. (2020). A comprehensive survey on graph neural networks. IEEE Trans. Neural Networks Learn. Syst., 1\u201321.","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"ref_20","unstructured":"Defferrard, M., Bresson, X., and Vandergheynst, P. (2016, January 5\u201310). Convolutional neural networks on graphs with fast localized spectral filtering. Proceedings of the Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain."},{"key":"ref_21","unstructured":"Kipf, T.N., and Welling, M. (2017, January 24\u201326). Semi-supervised classification with graph convolutional networks. Proceedings of the ICLR, Toulon, France."},{"key":"ref_22","unstructured":"Veli\u010dkovi\u0107, P., Cucurull, G., Casanova, A., Romero, A., Li\u00f2, P., and Bengio, Y. (May, January 30). Graph attention networks. Proceedings of the ICLR, Vancouver, BC, Canada."},{"key":"ref_23","unstructured":"Luan, S., Zhao, M., Chang, X.W., and Precup, D. (2019, January 8\u201314). Break the ceiling: Stronger multi-scale deep graph convolutional networks. Proceedings of the Annual Conference on Neural Information Processing Systems 2019, Vancouver, BC, Canada."},{"key":"ref_24","unstructured":"Loukas, A. (2020, January 26\u201330). What graph neural networks cannot learn: Depth vs. width. Proceedings of the ICLR, Addis Ababa, Ethiopia."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1109\/TSP.2018.2887403","article-title":"Convolutional neural network architectures for signals supported on graphs","volume":"67","author":"Gama","year":"2019","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_26","first-page":"12","article-title":"A reduction of a graph to a canonical form and an algebra arising during this reduction","volume":"2","author":"Weisfeiler","year":"1968","journal-title":"Nauchno-Tech. Informatsia"},{"key":"ref_27","unstructured":"Kriege, N.M., Giscard, P.L., and Wilson, R. (2016, January 5\u201310). On valid optimal assignment kernels and applications to graph classification. Proceedings of the Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain."},{"key":"ref_28","unstructured":"Mikolov, T., Sutskever, I., Chen, K., Corrado, G.S., and Dean, J. (2013, January 5\u20138). Distributed representations of words and phrases and their compositionality. Proceedings of the 27th Annual Conference on Neural Information Processing Systems 2013, Lake Tahoe, NV, USA."},{"key":"ref_29","unstructured":"Hjelm, R.D., Fedorov, A., Lavoie-Marchildon, S., Grewal, K., Bachman, P., Trischler, A., and Bengio, Y. (2019, January 6\u20139). Learning deep representations by mutual information estimation and maximization. Proceedings of the ICLR, New Orleans, LA, USA."},{"key":"ref_30","unstructured":"Nowozin, S., Cseke, B., and Tomioka, R. (2016, January 5\u201310). f-gan: Training generative neural samplers using variational divergence minimization. Proceedings of the Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain."},{"key":"ref_31","unstructured":"Melamud, O., and Goldberger, J. (August, January 30). Information-theory interpretation of the skip-gram negative-sampling objective function. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Short Papers), Vancouver, BC, Canada."},{"key":"ref_32","unstructured":"Xu, K., Hu, W., Leskovec, J., and Jegelka, S. (2019, January 6\u20139). How powerful are graph neural networks?. Proceedings of the ICLR, New Orleans, LA, USA."},{"key":"ref_33","unstructured":"Varoquaux, G., Vaught, T., and Millman, J. (2008, January 19\u201324). Exploring network structure, dynamics, and function using NetworkX. Proceedings of the 7th Python in Science Conference (SciPy2008), Pasadena, CA, USA."},{"key":"ref_34","unstructured":"Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. (2019, January 8\u201314). Provably powerful graph networks. Proceedings of the Annual Conference on Neural Information Processing Systems 2019, Vancouver, BC, Canada."},{"key":"ref_35","unstructured":"Morris, C., Ritzert, M., Fey, M., Hamilton, W.L., Lenssen, J.E., Rattan, G., and Grohe, M. (February, January 27). Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, Honolulu, HI, USA."},{"key":"ref_36","unstructured":"Vayer, T., Chapel, L., Flamary, R., Tavenard, R., and Courty, N. (2019, January 9\u201315). Optimal Transport for structured data with application on graphs. Proceedings of the ICML 2019\u201436th International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_37","unstructured":"Kersting, K., Kriege, N.M., Morris, C., Mutzel, P., and Neumann, M. (2020, August 20). Benchmark Data Sets for Graph Kernels. Available online: https:\/\/chrsmrrs.github.io\/datasets\/docs\/datasets\/."},{"key":"ref_38","unstructured":"Orsini, F., Frasconi, P., and DeRaedt, L. (2015, January 25\u201331). Graph invariant kernels. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina."},{"key":"ref_39","unstructured":"Kingma, D.P., and Ba, J. (2014). Adam: A method for stochastic optimization. arXiv."},{"key":"ref_40","unstructured":"Nikolentzos, G., Siglidis, G., and Vazirgiannis, M. (2019). Graph kernels: A survey. arXiv."},{"key":"ref_41","unstructured":"Errica, F., Podda, M., Bacciu, D., and Micheli, A. (2019). A Fair Comparison of Graph Neural Networks for Graph Classification. arXiv."},{"key":"ref_42","unstructured":"Xiao, H., Rasul, K., and Vollgraf, R. (2017). Fashion-MNIST: A Novel Image Dataset for Benchmarking Machine Learning Algorithms. arXiv."},{"key":"ref_43","unstructured":"Gilmer, J., Schoenholz, S.S., Riley, P.F., Vinyals, O., and Dahl, G.E. (2017). Neural Message Passing for Quantum Chemistry. arXiv."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1400","DOI":"10.1103\/PhysRevLett.47.1400","article-title":"Diffusion-limited aggregation, a kinetic critical phenomenon","volume":"47","author":"Witten","year":"1981","journal-title":"Phys. Rev. Lett."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"5686","DOI":"10.1103\/PhysRevB.27.5686","article-title":"Diffusion-limited aggregation","volume":"27","author":"Witten","year":"1983","journal-title":"Phys. Rev. B"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/206\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T10:33:06Z","timestamp":1719916386000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,21]]},"references-count":45,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090206"],"URL":"http:\/\/dx.doi.org\/10.3390\/a13090206","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,21]]}}}