{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,17]],"date-time":"2023-08-17T04:55:33Z","timestamp":1692248133457},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006298","name":"S\u00e4chsische Aufbaubank","doi-asserted-by":"publisher","award":["100378180"],"id":[{"id":"10.13039\/501100006298","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Min Knowl Disc"],"published-print":{"date-parts":[[2021,7]]},"abstract":"Abstract<\/jats:title>Graph Convolutional Networks (GCNs) have proven to be successful tools for semi-supervised classification on graph-based datasets. We propose a new GCN variant whose three-part filter space is targeted at dense graphs. Our examples include graphs generated from 3D point clouds with an increased focus on non-local information, as well as hypergraphs based on categorical data of real-world problems. These graphs differ from the common sparse benchmark graphs in terms of the spectral properties of their graph Laplacian. Most notably we observe large eigengaps, which are unfavorable for popular existing GCN architectures. Our method overcomes these issues by utilizing the pseudoinverse of the Laplacian. Another key ingredient is a low-rank approximation of the convolutional matrix, ensuring computational efficiency and increasing accuracy at the same time. We outline how the necessary eigeninformation can be computed efficiently in each applications and discuss the appropriate choice of the only metaparameter, the approximation rank. We finally showcase our method\u2019s performance regarding runtime and accuracy in various experiments with real-world datasets.<\/jats:p>","DOI":"10.1007\/s10618-021-00752-w","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T15:20:11Z","timestamp":1618500011000},"page":"1318-1341","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Pseudoinverse graph convolutional networks"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-5155-0115","authenticated-orcid":false,"given":"Dominik","family":"Alfke","sequence":"first","affiliation":[]},{"given":"Martin","family":"Stoll","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"752_CR1","doi-asserted-by":"publisher","DOI":"10.3389\/fams.2018.00061","author":"D Alfke","year":"2018","unstructured":"Alfke D, Potts D, Stoll M, Volkmer T (2018) NFFT meets Krylov methods: fast matrix-vector products for the graph Laplacian of fully connected networks. Front Appl Math Stat. https:\/\/doi.org\/10.3389\/fams.2018.00061","journal-title":"Front Appl Math Stat"},{"key":"752_CR2","unstructured":"Bai S, Zhang F, Torr PH (2019) Hypergraph convolution and hypergraph attention arxiv:1901.08150"},{"key":"752_CR3","doi-asserted-by":"crossref","unstructured":"Bauer F, Jost J (2013) Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplacian. Commun Anal Geom 21(4):787\u2013845","DOI":"10.4310\/CAG.2013.v21.n4.a2"},{"key":"752_CR4","unstructured":"Bianchi FM, Grattarola D, Alippi C, Livi L (2019) Graph neural networks with convolutional ARMA filters arXiv:1901.01343"},{"issue":"3","key":"752_CR5","doi-asserted-by":"publisher","first-page":"1350","DOI":"10.1137\/17M1117835","volume":"78","author":"J Bosch","year":"2018","unstructured":"Bosch J, Klamt S, Stoll M (2018) Generalizing diffuse interface methods on graphs: nonsmooth potentials and hypergraphs. SIAM J Appl Math 78(3):1350\u20131377","journal-title":"SIAM J Appl Math"},{"key":"752_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-00080-0","volume-title":"Hypergraph theory","author":"A Bretto","year":"2013","unstructured":"Bretto A (2013) Hypergraph theory, 1st edn. Eng, Springer, Math","edition":"1"},{"issue":"4","key":"752_CR7","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1109\/MSP.2017.2693418","volume":"34","author":"M Bronstein","year":"2017","unstructured":"Bronstein M, Bruna J, Lecun Y, Szlam A, Vandergheynst P (2017) Geometric deep learning: going beyond Euclidean data. IEEE Signal Process Mag 34(4):18\u201342. https:\/\/doi.org\/10.1109\/MSP.2017.2693418","journal-title":"IEEE Signal Process Mag"},{"key":"752_CR8","unstructured":"Bruna J, Zaremba W, Szlam A, LeCun Y (2014) Spectral networks and locally connected networks on graphs. In: Proc Int Conf Learn Represent, ICLR 14"},{"key":"752_CR9","doi-asserted-by":"crossref","unstructured":"Chan THH, Louis A, Tang ZG, Zhang C (2018) Spectral properties of hypergraph Laplacian and approximation algorithms. J ACM 65(3):15:1\u201315:48","DOI":"10.1145\/3178123"},{"key":"752_CR10","unstructured":"Chen JJ, Ma T, Xiao C (2018) FastGCN: Fast learning with graph convolutional networks via importance sampling. In: Proc Int Conf Learn Represent, ICLR 14"},{"key":"752_CR11","unstructured":"Coll B, Morel JM (2005) A non-local algorithm for image denoising. Proc IEEE Comput Soc Conf Comput Vis Pattern Recognit, CVPR 05:60\u201365"},{"key":"752_CR12","unstructured":"Defferrard M, Bresson X, Vandergheynst P (2016) Convolutional neural networks on graphs with fast localized spectral filtering. In: Adv Neural Inf Process Syst 29, NIPS 16"},{"key":"752_CR13","unstructured":"Dua D, Graff C (2017) UCI machine learning repository. http:\/\/archive.ics.uci.edu\/ml"},{"key":"752_CR14","doi-asserted-by":"crossref","unstructured":"Feng Y, You H, Zhang Z, Ji R, Gao Y (2019) Hypergraph neural networks. In: 33rd AAAI Conf Artif Intell, AAAI 19","DOI":"10.1609\/aaai.v33i01.33013558"},{"key":"752_CR15","unstructured":"Fey M, Lenssen JE (2019) Fast graph representation learning with PyTorch Geometric. In: ICLR workshop on representation learning on graphs and manifolds, ICLR 19"},{"issue":"3","key":"752_CR16","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1137\/070698592","volume":"7","author":"G Gilboa","year":"2008","unstructured":"Gilboa G, Osher S (2008) Nonlocal operators with applications to image processing. Multiscale Model Simul 7(3):1005\u20131028","journal-title":"Multiscale Model Simul"},{"key":"752_CR17","unstructured":"Glorot X, Bengio Y (2010) Understanding the difficulty of training deep feedforward neural networks. In: Proc 13th Int Conf Artif Intell Stat, AISTATS 10, vol\u00a09"},{"key":"752_CR18","doi-asserted-by":"publisher","unstructured":"Golovinskiy A, Funkhouser T (2009) Min-cut based segmentation of point clouds. In: Proc IEEE Int Conf Comput Vis, ICCV 09, https:\/\/doi.org\/10.1109\/ICCVW.2009.5457721","DOI":"10.1109\/ICCVW.2009.5457721"},{"key":"752_CR19","unstructured":"Golub GH, Van Loan CF (1996) Matrix computations, 3rd edn. The Johns Hopkins University Press"},{"key":"752_CR20","first-page":"1024","volume":"17","author":"W Hamilton","year":"2017","unstructured":"Hamilton W, Ying Z, Leskovec J (2017) Inductive representation learning on large graphs. Adv Neural Inf Process Sys, NIPS 17:1024\u20131034","journal-title":"Adv Neural Inf Process Sys, NIPS"},{"key":"752_CR21","first-page":"2427","volume":"13","author":"M Hein","year":"2013","unstructured":"Hein M, Setzer S, Jost L, Rangapuram SS (2013) The total variation on hypergraphs - learning on hypergraphs revisited. Adv Neural Inf Process Sys, NIPS 13:2427\u20132435","journal-title":"Adv Neural Inf Process Sys, NIPS"},{"key":"752_CR22","first-page":"305","volume":"05","author":"M Herbster","year":"2005","unstructured":"Herbster M, Pontil M, Wainer L (2005) Online learning over graphs. Proc Int Conf Mach Learn, New York, US, ICML 05:305\u2013312","journal-title":"Proc Int Conf Mach Learn, New York, US, ICML"},{"key":"752_CR23","doi-asserted-by":"crossref","unstructured":"Horn RA, Johnson CR (1985) Matrix analysis. Cambridge University Press","DOI":"10.1017\/CBO9780511810817"},{"key":"752_CR24","unstructured":"Kingma D, Ba JL (2015) Adam: a method for stochastic optimization. In: Proc Int Conf Learn Represent, ICLR 15"},{"key":"752_CR25","unstructured":"Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. In: Proc Int Conf Learn Represent, ICLR 17"},{"key":"752_CR26","first-page":"13333","volume":"19","author":"J Klicpera","year":"2019","unstructured":"Klicpera J, Wei\u00dfenberger S, G\u00fcnnemann S (2019) Diffusion improves graph learning. Adv Neural Inf Process Sys, NIPS 19:13333\u201313345","journal-title":"Adv Neural Inf Process Sys, NIPS"},{"key":"752_CR27","unstructured":"Mercado P, Gautier A, Tudisco F, Hein M (2018) The power mean laplacian for multilayer graph clustering. In: Proc Int Conf Artif Intell Stat, PMLR, AISTATS 18, vol\u00a084, pp 1828\u20131838"},{"key":"752_CR28","doi-asserted-by":"publisher","unstructured":"Munoz D, Bagnell JA, Vandapel N, Martial H (2009) Contextual classification with functional max-margin Markov networks. In: Proc IEEE Comput Soc Conf Comput Vis Pattern Recognit, CVPR 09, https:\/\/doi.org\/10.1109\/CVPR.2009.5206590","DOI":"10.1109\/CVPR.2009.5206590"},{"key":"752_CR29","first-page":"849","volume":"01","author":"AY Ng","year":"2002","unstructured":"Ng AY, Jordan MI, Weiss Y (2002) On spectral clustering: analysis and an algorithm. Adv Neural Inf Process Sys, MIT Press, NIPS 01:849\u2013856","journal-title":"Adv Neural Inf Process Sys, MIT Press, NIPS"},{"key":"752_CR30","doi-asserted-by":"crossref","unstructured":"Nguyen A, Le B (2013) 3D point cloud segmentation: a survey. Proc IEEE Conf Robot Autom Mechatron, RAM 13:225\u2013230","DOI":"10.1109\/RAM.2013.6758588"},{"key":"752_CR31","doi-asserted-by":"publisher","first-page":"1697","DOI":"10.1109\/TPAMI.2016.2614980","volume":"39","author":"P Purkait","year":"2017","unstructured":"Purkait P, Chin TJ, Sadri A, Suter D (2017) Clustering with hypergraphs: the case for large hyperedges. IEEE Trans Pattern Anal Mach Intell 39:1697\u20131711","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"752_CR32","doi-asserted-by":"publisher","unstructured":"Saad Y (2011) Numerical methods for large eigenvalue problems. SIAM. https:\/\/doi.org\/10.1137\/1.9781611970739","DOI":"10.1137\/1.9781611970739"},{"key":"752_CR33","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1109\/MSP.2012.2235192","volume":"30","author":"D Shuman","year":"2013","unstructured":"Shuman D, Narang S, Frossard P, Ortega A, Vandergheynst P (2013) The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains. IEEE Signal Process Mag 30:83\u201398","journal-title":"IEEE Signal Process Mag"},{"issue":"3","key":"752_CR34","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1137\/S0895479800371529","volume":"23","author":"GW Stewart","year":"2002","unstructured":"Stewart GW (2002) A Krylov-Schur algorithm for large eigenproblems. SIAM J Matrix Anal Appl 23(3):601\u2013614","journal-title":"SIAM J Matrix Anal Appl"},{"key":"752_CR35","first-page":"496","volume":"18","author":"Y Tao","year":"2018","unstructured":"Tao Y, Sun Q, Du Q, Liu W (2018) Nonlocal neural networks, nonlocal diffusion and nonlocal modeling. Adv Neural Inf Process Sys, NIPS 18:496\u2013506","journal-title":"Adv Neural Inf Process Sys, NIPS"},{"key":"752_CR36","doi-asserted-by":"crossref","unstructured":"von Luxburg U (2007) A tutorial on spectral clustering. Stat Comp 17(4):395\u2013416","DOI":"10.1007\/s11222-007-9033-z"},{"key":"752_CR37","unstructured":"Wu Z, Pan S, Chen F, Long G, Zhang C, Yu PS (2019) A comprehensive survey on graph neural networks arxiv:1901.00596"},{"key":"752_CR38","first-page":"1509","volume":"19","author":"N Yadati","year":"2019","unstructured":"Yadati N, Nimishakavi M, Yadav P, Nitin V, Louis A, Talukdar P (2019) Hypergcn: a new method for training graph convolutional networks on hypergraphs. Adv Neural Inf Process Sys, NIPS 19:1509\u20131520","journal-title":"Adv Neural Inf Process Sys, NIPS"},{"key":"752_CR39","doi-asserted-by":"publisher","unstructured":"Zhang S, Tong H, Xu J, Maciejewski R (2019) Graph convolutional networks: a comprehensive review. Comput Soc 6(11) https:\/\/doi.org\/10.1186\/s40649-019-0069-y","DOI":"10.1186\/s40649-019-0069-y"},{"key":"752_CR40","unstructured":"Zhou D, Huang J, Sch\u00f6lkopf B (2006) Learning with hypergraphs: clustering, classification, and embedding. In: Adv Neural Inf Process Syst, NIPS 06"}],"container-title":["Data Mining and Knowledge Discovery"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00752-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10618-021-00752-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10618-021-00752-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,23]],"date-time":"2021-06-23T07:54:18Z","timestamp":1624434858000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10618-021-00752-w"}},"subtitle":["Fast filters tailored for large Eigengaps of dense graphs and hypergraphs"],"short-title":[],"issued":{"date-parts":[[2021,4,15]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["752"],"URL":"https:\/\/doi.org\/10.1007\/s10618-021-00752-w","relation":{},"ISSN":["1384-5810","1573-756X"],"issn-type":[{"value":"1384-5810","type":"print"},{"value":"1573-756X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,15]]},"assertion":[{"value":"31 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All used datasets are publicly available.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability of data and material"}},{"value":"The authors have made their code available online at ExternalRef removed.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"The authors declare that they have no conflict of interest.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}