K-plex cover pooling for graph neural networks. (English) Zbl 1483.68274
Summary: Graph pooling methods provide mechanisms for structure reduction that are intended to ease the diffusion of context between nodes further in the graph, and that typically leverage community discovery mechanisms or node and edge pruning heuristics. In this paper, we introduce a novel pooling technique which borrows from classical results in graph theory that is non-parametric and generalizes well to graphs of different nature and connectivity patterns. Our pooling method, named KPlexPool, builds on the concepts of graph covers and \(k\)-plexes, i.e. pseudo-cliques where each node can miss up to \(k\) links. The experimental evaluation on benchmarks on molecular and social graph classification shows that KPlexPool achieves state of the art performances against both parametric and non-parametric pooling methods in the literature, despite generating pooled graphs based solely on topological information.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
Software:
ASAP; StructPool; EigenPooling; AFGen; NetworkX; KPlexPool; BRENDA; Algorithm 457; TUDataset; PyTorch; Graclus; PyGReferences:
| [1] | Bacciu D, Di Sotto L (2019) A non-negative factorization approach to node pooling in graph convolutional neural networks. In: Alviano M, Greco G, Scarcello F (eds) AI*IA 2019-advances in artificial intelligence, Lecture notes in computer science. Springer, Cham, pp 294-306, doi:10.1007/978-3-030-35166-3_21 |
| [2] | Bacciu D, Errica F, Micheli A (2018) Contextual graph markov model: a deep and generative approach to graph processing. In: International Conference on Machine Learning, pp 294-303, ISSN: 1938-7228 |
| [3] | Bacciu, D.; Errica, F.; Micheli, A.; Podda, M., A gentle introduction to deep learning for graphs, Neural Netw, 129, 203-221 (2020) · Zbl 1475.68310 · doi:10.1016/j.neunet.2020.06.006 |
| [4] | Battaglia PW, Hamrick JB, Bapst V, Sanchez-Gonzalez A, Zambaldi V, Malinowski M, Tacchetti A, Raposo D, Santoro A, Faulkner R, Gulcehre C, Song F, Ballard A, Gilmer J, Dahl G, Vaswani A, Allen K, Nash C, Langston V, Dyer C, Heess N, Wierstra D, Kohli P, Botvinick M, Vinyals O, Li Y, Pascanu R (2018) Relational inductive biases, deep learning, and graph networks. arXiv:1806.01261 |
| [5] | Bianchi FM, Grattarola D, Alippi C (2020) Spectral clustering with graph neural networks for graph pooling. Proc Int Conf Mach Learn 1 |
| [6] | Blondel, VD; Guillaume, JL; Lambiotte, R.; Lefebvre, E., Fast unfolding of communities in large networks, J Stat Mech Theory Exp (2008) · Zbl 1459.91130 · doi:10.1088/1742-5468/2008/10/P10008 |
| [7] | Borgwardt, KM; Ong, CS; Schönauer, S.; Vishwanathan, SVN; Smola, AJ; Kriegel, HP, Protein function prediction via graph kernels, Bioinform (Oxford, Engl), 21, Suppl 1, i47-56 (2005) · doi:10.1093/bioinformatics/bti1007 |
| [8] | Bron, C.; Kerbosch, J., Algorithm 457: finding all cliques of an undirected graph, Commun ACM, 16, 9, 575-577 (1973) · Zbl 0261.68018 · doi:10.1145/362342.362367 |
| [9] | Bruna J, Zaremba W, Szlam A, LeCun Y (2014) Spectral networks and locally connected networks on graphs. In: Bengio Y, LeCun Y (eds) Proceedings of the 2nd international conference on learning representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings |
| [10] | Cangea C, Veličković P, Jovanović N, Kipf T, Liò P (2018) Towards sparse hierarchical graph classifiers. arXiv:1811.01287 |
| [11] | Cazals, F.; Karande, C., A note on the problem of reporting maximal cliques, Theor Comput Sci, 407, 1, 564-568 (2008) · Zbl 1153.68038 · doi:10.1016/j.tcs.2008.05.010 |
| [12] | Conte A, Grossi R, Marino A (2016) Clique covering of large real-world networks. In: Proceedings of the 31st annual ACM symposium on applied computing, association for computing machinery, Pisa, Italy, SAC ’16, pp 1134-1139, doi:10.1145/2851613.2851816 |
| [13] | Conte A, De Matteis T, De Sensi D, Grossi R, Marino A, Versari L (2018) D2K: scalable community detection in massive networks via small-diameter k-plexes. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining, association for computing machinery, London, United Kingdom, KDD ’18, pp 1272-1281, doi:10.1145/3219819.3220093 |
| [14] | Conte, A.; Grossi, R.; Marino, A., Large-scale clique cover of real-world networks, Inform Comput, 270 (2020) · Zbl 1436.68228 · doi:10.1016/j.ic.2019.104464 |
| [15] | Defferrard M, Bresson X, Vandergheynst P (2016) Convolutional neural networks on graphs with fast localized spectral filtering. In: Proceedings of the 30th international conference on neural information processing systems, Curran Associates Inc., Red Hook, NY, USA, NIPS’16, pp 3844-3852 |
| [16] | Dhillon, IS; Guan, Y.; Kulis, B., Weighted graph cuts without eigenvectors a multilevel approach, IEEE Trans Pattern Anal Mach Intel, 29, 11, 1944-1957 (2007) · doi:10.1109/TPAMI.2007.1115 |
| [17] | Diehl F (2019) Edge contraction pooling for graph neural networks. arXiv:1905.10990 |
| [18] | Diehl F, Brunner T, Le MT, Knoll A (2019) Towards graph pooling by edge contraction. In: ICML 2019 workshop on learning and reasoning with graph-structured data |
| [19] | Dobson, PD; Doig, AJ, Distinguishing enzyme structures from non-enzymes without alignments, J Mol Biol, 330, 4, 771-783 (2003) · doi:10.1016/s0022-2836(03)00628-4 |
| [20] | Errica F, Podda M, Bacciu D, Micheli A (2020) A fair comparison of graph neural networks for graph classification. In: International conference on learning representations |
| [21] | Fey M, Lenssen JE (2019) Fast graph representation learning with PyTorch geometric. In: ICLR workshop on representation learning on graphs and manifolds |
| [22] | Fukushima, K., Neocognitron: a self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position, Biol Cybern, 36, 4, 193-202 (1980) · Zbl 0419.92009 · doi:10.1007/BF00344251 |
| [23] | Gama, F.; Marques, AG; Leus, G.; Ribeiro, A., Convolutional neural network architectures for signals supported on graphs, IEEE Trans Signal Process, 67, 4, 1034-1049 (2019) · Zbl 1415.94107 · doi:10.1109/TSP.2018.2887403 |
| [24] | Gao H, Ji S (2019) Graph U-Nets. In: International Conference on Machine Learning, pp 2083-2092, ISSN: 1938-7228 Section: Machine Learning |
| [25] | Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE (2017) Neural message passing for Quantum chemistry. In: Proceedings of the 34th international conference on machine learning, vol 70, JMLR.org, Sydney, NSW, Australia, ICML’17, pp 1263-1272 |
| [26] | Goodfellow, I.; Bengio, Y.; Courville, A., Deep learning (2016), Cambridge: MIT Press, Cambridge · Zbl 1373.68009 |
| [27] | Gori M, Monfardini G, Scarselli F (2005) A new model for learning in graph domains. In: Proceedings of the 2005 IEEE international joint conference on neural networks, vol 2, pp 729-734. doi:10.1109/IJCNN.2005.1555942, ISSN: 2161-4407 |
| [28] | Hagberg AA, Schult DA, Swart PJ (2008) Exploring network structure, dynamics, and function using networkx. In: Varoquaux G, Vaught T, Millman J (eds) Proceedings of the 7th Python in Science Conference, Pasadena, CA USA, pp 11-15 |
| [29] | Hamilton WL, Ying R, Leskovec J (2017) Inductive representation learning on large graphs. In: Proceedings of the 31st international conference on neural information processing systems, Curran Associates Inc., Long Beach, California, USA, NIPS’17, pp 1025-1035 |
| [30] | Hammond, DK; Vandergheynst, P.; Gribonval, R., Wavelets on graphs via spectral graph theory, Appl Comput Harmonic Anal, 30, 2, 129-150 (2011) · Zbl 1213.42091 · doi:10.1016/j.acha.2010.04.005 |
| [31] | Karypis, G.; Kumar, V., A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J Sci Comput, 20, 1, 359-392 (1998) · Zbl 0915.68129 · doi:10.1137/S1064827595287997 |
| [32] | Kipf TN, Welling M (2017) Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th international conference on learning representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, OpenReview.net |
| [33] | Knyazev B, Taylor GW, Amer M (2019) Understanding attention and generalization in graph neural networks. In: Wallach H, Larochelle H, Beygelzimer A, Alché-Buc F, Fox E, Garnett R (eds) Advances in neural information processing systems 32, Curran Associates, Inc., pp 4202-4212 |
| [34] | Kriege, NM; Johansson, FD; Morris, C., A survey on graph kernels, Appl Netw Sci, 5, 1, 6 (2020) · doi:10.1007/s41109-019-0195-3 |
| [35] | Le Gall F (2014) Powers of tensors and fast matrix multiplication. In: Proceedings of the 39th international symposium on symbolic and algebraic computation, pp 296-303 · Zbl 1325.65061 |
| [36] | LeCun, Y.; Boser, B.; Denker, JS; Henderson, D.; Howard, RE; Hubbard, W.; Jackel, LD, Backpropagation applied to handwritten zip code recognition, Neural Comput, 1, 4, 541-551 (1989) · doi:10.1162/neco.1989.1.4.541 |
| [37] | Lee J, Lee I, Kang J (2019) Self-attention graph pooling. In: International conference on machine learning, pp 3734-3743, ISSN: 1938-7228 Section: Machine Learning |
| [38] | Li, M.; Ma, Z.; Wang, YG; Zhuang, X., Fast Haar transforms for graph neural networks, Neural Netw, 128, 188-198 (2020) · Zbl 1468.68185 · doi:10.1016/j.neunet.2020.04.028 |
| [39] | Li Q, Han Z, Wu XM (2018) Deeper insights into graph convolutional networks for semi-supervised learning. In: McIlraith SA, Weinberger KQ (eds) Proceedings of the thirty-second AAAI conference on artificial intelligence, (AAAI-18), the 30th innovative applications of artificial intelligence (IAAI-18), and the 8th AAAI symposium on educational advances in artificial intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, AAAI Press, pp 3538-3545 |
| [40] | Li Y, Tarlow D, Brockschmidt M, Zemel RS (2016) Gated graph sequence neural networks. In: Proceedings of the 4th international conference on learning representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings |
| [41] | Luzhnica E, Day B, Lio’ P (2019) Clique pooling for graph classification. arXiv:1904.00374 |
| [42] | Ma Y, Wang S, Aggarwal CC, Tang J (2019) Graph convolutional networks with EigenPooling. In: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery and data mining, Association for Computing Machinery, Anchorage, AK, USA, KDD ’19, pp 723-731, doi:10.1145/3292500.3330982 |
| [43] | Micheli, A., Neural network for graphs: a contextual constructive approach, IEEE Trans Neural Netw, 20, 3, 498-511 (2009) · doi:10.1109/TNN.2008.2010350 |
| [44] | Monti F, Boscaini D, Masci J, Rodola E, Svoboda J, Bronstein MM (2017) Geometric deep learning on graphs and manifolds using mixture model CNNs. pp 5115-5124 |
| [45] | Morris, C.; Ritzert, M.; Fey, M.; Hamilton, WL; Lenssen, JE; Rattan, G.; Grohe, M., Weisfeiler and leman go neural: higher-order graph neural networks, Proc AAAI Conf Artif Intel, 33, 1, 4602-4609 (2019) · doi:10.1609/aaai.v33i01.33014602 |
| [46] | Morris C, Kriege NM, Bause F, Kersting K, Mutzel P, Neumann M (2020) TUDataset: a collection of benchmark datasets for learning with graphs. In: ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), arXiv:2007.08663 |
| [47] | Ng, AY; Jordan, MI; Weiss, Y.; Dietterich, TG; Becker, S.; Ghahramani, Z., On spectral clustering: analysis and an algorithm, Advances in neural information processing systems, 849-856 (2002), Cambridge: MIT Press, Cambridge |
| [48] | Poulin V, Théberge F (2019) Ensemble clustering for graphs. In: Aiello LM, Cherifi C, Cherifi H, Lambiotte R, Lió P, Rocha LM (eds) Complex networks and their applications VII, Studies in Computational Intelligence. Springer, Cham, pp 231-243, doi:10.1007/978-3-030-05411-3_19 |
| [49] | Ranjan, E.; Sanyal, S.; Talukdar, P., ASAP: adaptive structure aware pooling for learning hierarchical graph representations, Proc AAAI Conf Artif Intel, 34, 4, 5470-5477 (2020) · doi:10.1609/aaai.v34i04.5997 |
| [50] | RAPIDS Development Team (2018) RAPIDS: collection of libraries for end to end GPU data science |
| [51] | Scarselli F, Yong SL, Gori M, Hagenbuchner M, Tsoi AC, Maggini M (2005) Graph neural networks for ranking Web pages. In: The 2005 IEEE/WIC/ACM international conference on web intelligence (WI’05), pp 666-672, doi:10.1109/WI.2005.67 |
| [52] | Scarselli, F.; Gori, M.; Tsoi, AC; Hagenbuchner, M.; Monfardini, G., The graph neural network model, IEEE Trans Neural Netw, 20, 1, 61-80 (2009) · doi:10.1109/TNN.2008.2005605 |
| [53] | Schomburg, I.; Chang, A.; Ebeling, C.; Gremse, M.; Heldt, C.; Huhn, G.; Schomburg, D., BRENDA, the enzyme database: updates and major new developments, Nucl Acids Res (2004) · doi:10.1093/nar/gkh081 |
| [54] | Shervashidze, N.; Schweitzer, P.; Leeuwen, EJV; Mehlhorn, K.; Borgwardt, KM, Weisfeiler-Lehman graph kernels, J Mach Learn Res, 12, 2539-2561 (2011) · Zbl 1280.68194 |
| [55] | Simonovsky M, Komodakis N (2017) Dynamic edge-conditioned filters in convolutional neural networks on graphs. In: Proceedings of the IEEE conference on computer vision and pattern recognition, pp 3693-3702 |
| [56] | Tomita, E.; Tanaka, A.; Takahashi, H., The worst-case time complexity for generating all maximal cliques and computational experiments, Theor Comput Sci, 363, 1, 28-42 (2006) · Zbl 1153.68398 · doi:10.1016/j.tcs.2006.06.015 |
| [57] | Traag, VA; Waltman, L.; van Eck, NJ, From Louvain to Leiden: guaranteeing well-connected communities, Sci Rep, 9, 1, 5233 (2019) · doi:10.1038/s41598-019-41695-z |
| [58] | Veličković P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y (2018) Graph attention networks. In: International conference on learning representations |
| [59] | Vinyals O, Bengio S, Kudlur M (2016) Order matters: sequence to sequence for sets. In: Proceedings of the 4th international conference on learning representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings |
| [60] | Vishwanathan, SVN; Schraudolph, NN; Kondor, R.; Borgwardt, KM, Graph Kernels, J Mach Learn Res, 11, 40, 1201-1242 (2010) · Zbl 1242.05112 |
| [61] | Wale, N.; Watson, IA; Karypis, G., Comparison of descriptor spaces for chemical compound retrieval and classification, Knowl Inform Syst, 14, 3, 347-375 (2008) · doi:10.1007/s10115-007-0103-5 |
| [62] | Wang Y, Li M, Ma Z, Montufar G, Zhuang X, Fan Y (2020) Haar Graph Pooling. Proc Int Conf Mach Learn 1 |
| [63] | Xu K, Li C, Tian Y, Sonobe T, Kawarabayashi K, Jegelka S (2018) Representation learning on graphs with jumping knowledge networks. In: International conference on machine learning, PMLR, pp 5453-5462, ISSN: 2640-3498 |
| [64] | Xu K, Hu W, Leskovec J, Jegelka S (2019) How powerful are graph neural networks? In: International conference on learning representations |
| [65] | Yanardag P, Vishwanathan S (2015) Deep graph kernels. In: Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, association for computing machinery, New York, NY, USA, KDD ’15, pp 1365-1374, doi:10.1145/2783258.2783417 |
| [66] | Ying R, You J, Morris C, Ren X, Hamilton WL, Leskovec J (2018) Hierarchical graph representation learning with differentiable pooling. In: Proceedings of the 32nd international conference on neural information processing systems, Curran Associates Inc., Montréal, Canada, NIPS’18, pp 4805-4815 |
| [67] | Yuan H, Ji S (2019) StructPool: structured graph pooling via conditional random fields |
| [68] | Zhang L, Wang X, Li H, Zhu G, Shen P, Li P, Lu X, Shah SAA, Bennamoun M (2020) Structure-feature based graph self-adaptive pooling. In: Proceedings of the web conference 2020, Association for Computing Machinery, New York, NY, USA, WWW ’20, pp 3098-3104, doi:10.1145/3366423.3380083 |
| [69] | Zhang M, Cui Z, Neumann M, Chen Y (2018) An end-to-end deep learning architecture for graph classification. In: Proceedings of the thirty-second AAAI conference on artificial intelligence, (AAAI-18), the 30th innovative applications of artificial intelligence (IAAI-18), and the 8th AAAI symposium on educational advances in artificial intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pp 4438-4445 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
