Topology-Aware Graph Signal Sampling for Pooling in Graph Neural Networks

Topology-Aware Graph Signal Sampling for Pooling in Graph Neural Networks

Amirhossein Nouranizadeh, Mohammadjavad Matinkia, Mohammad Rahmati

Abstract

As a generalization of convolutional neural networks to graph-structured data, graph convolutional networks learn feature embeddings based on the information of each node’s local neighborhood. However, due to the inherent irregularity of such data, extracting hierarchical representations of a graph becomes a challenging task. Several pooling approaches have been introduced to address this issue. In this paper, we propose a novel topology-aware graph signal sampling method to specify the nodes that represent the communities of a graph. Our method selects the sampling set based on the local variation of the signal of each node while considering vertex-domain distances of the nodes in the sampling set. In addition to the interpretability of the sampled nodes provided by our method, the experimental results both on stochastic block models and real-world dataset benchmarks show that our method achieves competitive results compared to the state-of-the-art in the graph classification task. 

Keywords

graph neural networks, pooling layer, graph signal sampling, graph classification

References

  • [1] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 779– 788.
  • [2] G. Hinton, L. Deng, D. Yu, G. E. Dahl, A.-r. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, T. N. Sainath et al., “Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups,” IEEE Signal processing magazine, vol. 29, no. 6, pp. 82–97, 2012.
  • [3] M.-T. Luong, H. Pham, and C. D. Manning, “Effective ap- proaches to attention-based neural machine translation,” arXiv preprint arXiv:1508.04025, 2015.
  • [4] Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey et al., “Google’s neural machine translation system: Bridging the gap between human and machine translation,” arXiv preprint arXiv:1609.08144, 2016.
  • [5] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst, “Geometric deep learning: going beyond euclidean data,” IEEE Signal Processing Magazine, vol. 34, no. 4, pp. 18–42, 2017.
  • [6] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” IEEE Transactions on Neural Networks, vol. 20, no. 1, pp. 61–80, 2008.
  • [7] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” arXiv preprint arXiv:1609.02907, 2016.
  • [8] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in Advances in neural information processing systems, 2017, pp. 1024–1034.
  • [9] P.Velicˇkovic ́, G. Cucurull, A.Casanova, A.Romero, P.Lio, and Y.Bengio, “Graph attention networks,” arXiv preprint arXiv:1710.10903, 2017. [10] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph
  • neural networks?” arXiv preprint arXiv:1810.00826, 2018.
  • [11] Z.Wu, S.Pan, F.Chen, G.Long, C.Zhang, and P.S. Yu, “A comprehensive survey on graph neural networks,” arXiv preprint arXiv:1901.00596, 2019.
  • [12] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Ex- tending high-dimensional data analysis to networks and other irregular domains,” IEEE signal processing magazine, vol. 30, no. 3, pp. 83–98, 2013.
  • [13] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 2017, pp. 1263–1272.
  • [14] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, 2016, pp. 855– 864.
  • [15] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 2014, pp. 701–710
  • [16] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in Proceedings of the 24th international conference on world wide web, 2015, pp. 1067–1077.
  • [17] L. Backstrom and J. Leskovec, “Supervised random walks: predicting and recommending links in social networks,” in Proceedings of the fourth ACM international conference on Web search and data mining, 2011, pp. 635–644.
  • [18] R. v. d. Berg, T. N. Kipf, and M. Welling, “Graph convolutional matrix completion,” arXiv preprint arXiv:1706.02263, 2017.
  • [19] Q. Lu and L. Getoor, “Link-based classification,” in Proceedings of the 20th International Conference on Machine Learning (ICML-03), 2003, pp. 496–503.
  • [20] M. Nickel, K. Murphy, V. Tresp, and E. Gabrilovich, “A review of relational machine learning for knowledge graphs,” Proceedings of the IEEE, vol. 104, no. 1, pp. 11–33, 2015.
  • [21] P. D. Dobson and A. J. Doig, “Distinguishing enzyme structures from non-enzymes without alignments,” Journal of molecular biology, vol. 330, no. 4, pp. 771–783, 2003.
  • [22] S. V. N. Vishwanathan, N. N. Schraudolph, R. Kondor, and K. M. Borgwardt, “Graph kernels,” Journal of Machine Learning Research, vol. 11, no. Apr, pp. 1201–1242, 2010.
  • [23] N. Shervashidze, P. Schweitzer, E. J. v. Leeuwen, K. Mehlhorn, and K. M. Borgwardt, “Weisfeiler-lehman graph kernels,” Journal of Ma- chine Learning Research, vol. 12, no. Sep, pp. 2539–2561, 2011.
  • [24] D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams, “Convolutional networks on graphs for learning molecular fingerprints,” in Advances in neural information processing systems, 2015, pp. 2224–2232.
  • [25] M.Niepert, M.Ahmed, and K.Kutzkov, “Learning convolutional neural networks for graphs,” in International conference on machine learning, 2016, pp. 2014–2023.
  • [26] S. Kearnes, K. McCloskey, M. Berndl, V. Pande, and P. Riley, “Molecular graph convolutions: moving beyond fingerprints,” Journal of computer-aided molecular design, vol. 30, no. 8, pp. 595–608, 2016.
  • [27] Z. Ying, J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec, “Hierarchical graph representation learning with differentiable pooling,” in Advances in neural information processing systems, 2018, pp. 4800– 4810.
  • [28] J.Lee, I.Lee, and J.Kang, “Self-attention graph pooling,”arXivpreprint arXiv:1904.08082, 2019.
  • [29] M. Zhang, Z. Cui, M. Neumann, and Y. Chen, “An end-to-end deep learning architecture for graph classification,” in Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
  • [30] O. Vinyals, S. Bengio, and M. Kudlur, “Order matters: Sequence to sequence for sets,” arXiv preprint arXiv:1511.06391, 2015.
  • [31] H. Gao and S. Ji, “Graph u-nets,” arXiv preprint arXiv:1905.05178, 2019.
  • [32] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” arXiv preprint arXiv:1312.6203, 2013.
  • [33] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in Advances in neural information processing systems, 2016, pp. 3844–3852.
  • [34] R. Li, S. Wang, F. Zhu, and J. Huang, “Adaptive graph convolutional neural networks,” in Thirty-second AAAI conference on artificial intelligence, 2018.
  • [35] M.Niepert, M.Ahmed, and K.Kutzkov, “Learning convolutionalneural networks for graphs,” in International conference on machine learning, 2016, pp. 2014–2023.
  • [36] Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel, “Gated graph sequence neural networks,” arXiv preprint arXiv:1511.05493, 2015.
  • [37] I. S. Dhillon, Y. Guan, and B. Kulis, “Weighted graph cuts without eigenvectors a multilevel approach,” IEEE transactions on pattern analysis and machine intelligence, vol. 29, no. 11, pp. 1944–1957, 2007.
  • [38] H. Gao, Y. Liu, and S. Ji, “Topology-aware graph pooling networks,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
  • [39] A. Anis, A. Gadde, and A. Ortega, “Efficient sampling set selection for bandlimited graph signals using graph spectral proxies,” IEEE Transactions on Signal Processing, vol. 64, no. 14, pp. 3775–3789, 2016.
  • [40] K. M. Borgwardt, C. S. Ong, S. Schönauer, S. Vishwanathan, A. J. Smola, and H.-P. Kriegel, “Protein function prediction via graph kernels” Bioinformatics, vol. 21, no. suppl_1, pp. i47–i56, 2005.
  • [41] A.K.Debnath, R.L.Lopezde Compadre, G.Debnath, A.J.Shusterman, and C. Hansch, “Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity,” Journal of medicinal chemistry, vol. 34,
  • no. 2, pp. 786–797, 1991.
  • [42] F. Orsini, P. Frasconi, and L. De Raedt, “Graph invariant kernels,” in Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
  • [43] A.Paszke, S.Gross, S.Chintala, G.Chanan, E.Yang, Z.DeVito,Z.Lin, A. Desmaison, L. Antiga, and A. Lerer, “Automatic differentiation in pytorch,” 2017.
  • [44] M. Fey and J. E. Lenssen, “Fast graph representation learning with pytorch geometric,” arXiv preprint arXiv:1903.02428, 2019.
About Journal
Editorial Board
Guide For Authors
Submit Your Manuscript
Latest Issue
Past Issues
© Copyright - The CSI Journal on Computer Science and Engineering
Produced by Intelligent Information Solutions Center