A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 8 Issue 10
Oct.  2021

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2021  >  8(10): 1697-1708
X. B. Hong, T. Zhang, Z. Cui, and J. Yang, "Variational Gridded Graph Convolution Network for Node Classification," IEEE/CAA J. Autom. Sinica, vol. 8, no. 10, pp. 1697-1708, Oct. 2021. doi: 10.1109/JAS.2021.1004201
Citation: X. B. Hong, T. Zhang, Z. Cui, and J. Yang, "Variational Gridded Graph Convolution Network for Node Classification," IEEE/CAA J. Autom. Sinica, vol. 8, no. 10, pp. 1697-1708, Oct. 2021. doi: 10.1109/JAS.2021.1004201
shu

Variational Gridded Graph Convolution Network for Node Classification

doi: 10.1109/JAS.2021.1004201

  • Key Laboratory of Intelligent Perception and Systems for High-Dimensional Information of Ministry of Education, School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China

Funds:  This work was supported by the Natural Science Foundation of Jiangsu Province (BK20190019, BK20190452), the National Natural Science Foundation of China (62072244, 61906094), and the Natural Science Foundation of Shandong Province (ZR2020LZH008). This work was partly collaborated with State Key Laboratory of High-end Server and Storage Technology
More Information
    Abstract
  • The existing graph convolution methods usually suffer high computational burdens, large memory requirements, and intractable batch-processing. In this paper, we propose a high-efficient variational gridded graph convolution network (VG-GCN) to encode non-regular graph data, which overcomes all these aforementioned problems. To capture graph topology structures efficiently, in the proposed framework, we propose a hierarchically-coarsened random walk (hcr-walk) by taking advantage of the classic random walk and node/edge encapsulation. The hcr-walk greatly mitigates the problem of exponentially explosive sampling times which occur in the classic version, while preserving graph structures well. To efficiently encode local hcr-walk around one reference node, we project hcr-walk into an ordered space to form image-like grid data, which favors those conventional convolution networks. Instead of the direct 2-D convolution filtering, a variational convolution block (VCB) is designed to model the distribution of the random-sampling hcr-walk inspired by the well-formulated variational inference. We experimentally validate the efficiency and effectiveness of our proposed VG-GCN, which has high computation speed, and the comparable or even better performance when compared with baseline GCNs.

     

    • FullText(HTML)
  • loading
    • 1 https://github.com/phanein/deepwalk2 https://github.com/kimiyoung/planetoid3 https://github.com/tkipf/gcn4 https://github.com/PetarV-/GAT5 https://github.com/ZhuangCY/DGCN
    2 https://github.com/kimiyoung/planetoid
    3 https://github.com/tkipf/gcn
    4 https://github.com/PetarV-/GAT
    5 https://github.com/ZhuangCY/DGCN
    Xiaobin Hong and Tong Zhang contributed equally to this work.
    References(68)
  • [1]
    Y. LeCun, L. Bottou, Y. Bengio, P. Haffner, et al., “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998. doi: 10.1109/5.726791
    [2]
    J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, “You only look once: Unified, real-time object detection,” in Proc. Computer Vision and Pattern Recognition, 2016, pp. 779–788.
    [3]
    S. Ren, K. He, R. Girshick, and J. Sun, “Faster R-CNN: Towards real-time object detection with region proposal networks,” in Proc. Advances in Neural Information Processing Systems, 2015, pp. 91–99.
    [4]
    T. Luong, H. Pham, and C. D. Manning, “Effective approaches to attention-based neural machine translation,” in Proc. Empirical Methods in Natural Language Processing, 2015, pp. 1412–1421.
    [5]
    G. Hinton, L. Deng, D. Yu, G. Dahl, A.-r. Mohamed, N. Jaitly, A. Senior, V. Vanhoucke, P. Nguyen, B. Kingsbury, et al., “Deep neural networks for acoustic modeling in speech recognition,” IEEE Signal Processing Magazine, vol. 29, 2012.
    [6]
    F. Orsini, D. Baracchi, and P. Frasconi, “Shift aggregate extract networks,” Frontiers in Robotics and AI, p. 42, 2018.
    [7]
    J. M. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins, “The web as a graph: Measurements, models, and methods,” in Proc. Int. Computing and Combinatorics Conf., Springer, 1999, pp. 1–17.
    [8]
    D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition, 2017, pp. 5410–5419.
    [9]
    K. M. Borgwardt, H.-P. Kriegel, S. Vishwanathan, and N. N. Schraudolph, “Graph kernels for disease outcome prediction from proteinprotein interaction networks,” in Biocomputing. World Scientific, 2007, pp. 4–15.
    [10]
    X. Luo, H. Wu, H. Yuan, and M. Zhou, “Temporal pattern-aware QoS prediction via biased non-negative latent factorization of tensors,” IEEE Trans. Cybernetics, vol. 50, no. 5, pp. 1798–1809, 2019.
    [11]
    T. D. Pham, K. Wardell, A. Eklund, and G. Salerud, “Classification of short time series in early Parkinson’s disease with deep learning of fuzzy recurrence plots,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 6, pp. 1306–1317, 2019. doi: 10.1109/JAS.2019.1911774
    [12]
    L. Wei and E. Keogh, “Semi-supervised time series classification,” in Proc. 12th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, 2006, pp. 748–753.
    [13]
    D. Wu, X. Luo, M. Shang, Y. He, G. Wang, and X. Wu, “A datacharacteristic-aware latent factor model for web services QoS prediction,” IEEE Trans. Knowledge and Data Engineering, 2020.
    [14]
    X. Luo, M. Zhou, S. Li, Y. Xia, Z.-H. You, Q. Zhu, and H. Leung, “Incorporation of efficient second-order solvers into latent factor models for accurate prediction of missing QoS data,” IEEE Trans. Cybernetics, vol. 48, no. 4, pp. 1216–1228, 2017.
    [15]
    J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” arXiv preprint arXiv: 1312.6203, 2013.
    [16]
    M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” in Proc. Advances in Neural Information Processing Systems, 2016, pp. 3844– 3852.
    [17]
    T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proc. Int. Conf. Learning Representations, 2017.
    [18]
    R. Li, S. Wang, F. Zhu, and J. Huang, “Adaptive graph convolutional neural networks,” in Proc. 32nd AAAI Conf. Artificial Intelligence, 2018.
    [19]
    S. Fu, W. Liu, D. Tao, Y. Zhou, and L. Nie, “Hesgcn: Hessian graph convolutional networks for semi-supervised classification,” Information Sciences, vol. 514, pp. 484–498, 2020. doi: 10.1016/j.ins.2019.11.019
    [20]
    S. Fu, W. Liu, Y. Zhou, and L. Nie, “Hplapgcn: Hypergraph p-laplacian graph convolutional networks,” Neurocomputing, vol. 362, pp. 166–174, 2019. doi: 10.1016/j.neucom.2019.06.068
    [21]
    F. Sichao, L. Weifeng, L. Shuying, and Z. Yicong, “Two-order graph convolutional networks for semi-supervised classification,” IET Image Processing, vol. 13, no. 14, pp. 2763–2771, 2019. doi: 10.1049/iet-ipr.2018.6224
    [22]
    B. Wu, Y. Liu, B. Lang, and L. Huang, “DGCNN: Disordered graph convolutional neural network based on the gaussian mixture model,” Neurocomputing, vol. 321, pp. 346–356, 2018. doi: 10.1016/j.neucom.2018.09.008
    [23]
    S. Franco, G. Marco, T. Ah Chung, H. Markus, and M. Gabriele, “The graph neural network model,” IEEE Trans. Neural Networks, vol. 20, no. 1, Article No. 61, 2009. doi: 10.1109/TNN.2008.2005605
    [24]
    W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in Proc. Neural Information Processing Systems, 2017.
    [25]
    J. Atwood and D. Towsley, “Diffusion-convolutional neural networks,” in Proc. Advances in Neural Information Processing Systems, 2016, pp. 1993–2001.
    [26]
    P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez, V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, et al., “Relational inductive biases, deep learning, and graph networks,” Computing Research Repository, 2018.
    [27]
    F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini, “The graph neural network model,” IEEE Trans. Neural Networks, vol. 20, no. 1, pp. 61–80, 2008.
    [28]
    Y. Li, D. Tarlow, M. Brockschmidt, and R. Zemel, “Gated graph sequence neural networks,” in Proc. Int. Conf. Learning Representations, 2016.
    [29]
    H. Dai, Z. Kozareva, B. Dai, A. Smola, and L. Song, “Learning steadystates of iterative algorithms over graphs,” in Proc. Int. Conf. Machine Learning, 2018, pp. 1114–1122.
    [30]
    K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in Proc. Int. Conf. Learning Representations, 2019.
    [31]
    P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in Proc. Int. Conf. Learning Representations, 2018.
    [32]
    L. Lovász, “Random walks on graphs: A survey, combinatorics, Paul Erdos is eighty,” Lecture Notes in Mathematics, vol. 2, no. 1, pp. 1–46, 1993. doi: 10.1007/BFb0077189
    [33]
    X. Hong, T. Zhang, Z. Cui, C. Xu, L. Zhang, and J. Yang, “Fast hyperwalk gridded convolution on graph,” in Proc. Chinese Conf. Pattern Recognition and Computer Vision, Springer, 2020, pp. 197– 208.
    [34]
    H. Kashima, K. Tsuda, and A. Inokuchi, “Marginalized kernels between labeled graphs,” in Proc. 20th Int. Conf. Machine Learning, 2003, pp. 321–328.
    [35]
    N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt, “Efficient graphlet kernels for large graph comparison,” in Proc. Artificial Intelligence and Statistics, 2009, pp. 488–495.
    [36]
    P. Yanardag and S. Vishwanathan, “Deep graph kernels,” in Proc. 21st ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, 2015, pp. 1365–1374.
    [37]
    C. Morris, K. Kersting, and P. Mutzel, “Glocalized weisfeiler-lehman graph kernels: Global-local feature maps of graphs,” in Proc. IEEE Int. Conf. Data Mining, 2017, pp. 327–336.
    [38]
    M. Ceci, A. Appice, N. Barile, and D. Malerba, “Transductive learning from relational data,” in Proc. Int. Workshop on Machine Learning and Data Mining in Pattern Recognition, 2007, pp. 324–338.
    [39]
    R. S. Michalski, “A theory and methodology of inductive learning,” in Machine Learning. Springer, 1983, pp. 83–134.
    [40]
    S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486, no. 3–5, pp. 75–174, 2010. doi: 10.1016/j.physrep.2009.11.002
    [41]
    A. Lancichinetti and S. Fortunato, “Community detection algorithms: A comparative analysis,” Physical Review E, vol. 80, no. 5, p. 056117, 2009.
    [42]
    L. Bai, X. Cheng, J. Liang, and Y. Guo, “Fast graph clustering with a new description model for community detection,” Information Sciences, vol. 388, pp. 37–47, 2017.
    [43]
    M. Schwartz, Telecommunication Networks: Protocols, Modeling and Analysis. Addison-Wesley Longman Publishing Co., Inc., 1986.
    [44]
    A. Chapanond, M. S. Krishnamoorthy, and B. Yener, “Graph theoretic and spectral analysis of enron email data,” Computational &Mathematical Organization Theory, vol. 11, no. 3, pp. 265–281, 2005.
    [45]
    T. He, Y. Liu, T. H. Ko, K. C. Chan, and Y.-S. Ong, “Contextual correlation preserving multiview featured graph clustering,” IEEE Trans. Cybernetics, vol. 50, no. 10, pp. 4318–4331, 2019.
    [46]
    L. Hu, S. Yang, X. Luo, and M. Zhou, “An algorithm of inductively identifying clusters from attributed graphs,” IEEE Trans. Big Data, 2020. DOI: 10.1109/TBDATA.2020.2964544
    [47]
    L. Hu, K. C. Chan, X. Yuan, and S. Xiong, “A variational Bayesian framework for cluster analysis in a complex network,” IEEE Trans. Knowledge and Data Engineering, vol. 32, no. 11, pp. 2115–2128, 2019.
    [48]
    B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, 2014, pp. 701–710.
    [49]
    H. Zhang, X. Shang, H. Luan, M. Wang, and T.-S. Chua, “Learning from collective intelligence: Feature learning using social images and tags,” ACM Transactions on Multimedia Computing, Communications, and Applications, vol. 13, no. 1, p. 1, 2017.
    [50]
    S. Pan, J. Wu, X. Zhu, C. Zhang, and Y. Wang, “Tri-party deep network representation,” Network, vol. 11, no. 9, p. 12, 2016.
    [51]
    A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in Proc. 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, 2016, pp. 855– 864.
    [52]
    L. Qiu, Y. Cao, Z. Nie, Y. Yu, and Y. Rui, “Learning word representation considering proximity and ambiguity,” in Proc. 28th AAAI Conf. Artificial Intelligence, 2014.
    [53]
    T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean, “Distributed representations of words and phrases and their compositionality,” in Proc. Advances in Neural Information Processing Systems, 2013, pp. 3111–3119.
    [54]
    C. J. Geyer, “Introduction to Markov chain Monte Carlo,” Handbook of Markov Chain Monte Carlo, vol. 20116022, p. 45, 2011.
    [55]
    D. P. Kingma and M. Welling, “Auto-encoding variational Bayes,” arXiv: Machine Learning, 2013.
    [56]
    L. Devroye, “Sample-based non-uniform random variate generation,” in Proc. 18th Conf. Winter Simulation, 1986, pp. 260–265.
    [57]
    C. Robert and G. Casella, Monte Carlo Statistical Methods. Springer Science & Business Media, 2013.
    [58]
    P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. EliassiRad, “Collective classification in network data,” AI Magazine, vol. 29, no. 3, pp. 93–93, 2008. doi: 10.1609/aimag.v29i3.2157
    [59]
    J. Klicpera, S. Weißenberger, and S. Günnemann, “Diffusion improves graph learning,” arXiv preprint arXiv: 1911.05485, 2019.
    [60]
    Z. Yang, W. W. Cohen, and R. Salakhutdinov, “Revisiting semisupervised learning with graph embeddings,” in Proc. Int. Conf. Machine Learning, 2016.
    [61]
    A. Carlson, J. Betteridge, B. Kisiel, B. Settles, E. R. Hruschka, and T. M. Mitchell, “Toward an architecture for never-ending language learning,” in Proc. 24th AAAI Conf. Artificial Intelligence, 2010.
    [62]
    B. Dalvi, A. Mishra, and W. W. Cohen, “Hierarchical semi-supervised classification with incomplete class hierarchies,” in Proc. 9th ACM Int. Conf. Web Search and Data Mining, 2016, pp. 193–202.
    [63]
    C. Zhuang and Q. Ma, “Dual graph convolutional networks for graphbased semi-supervised classification,” in Proc. Int. World Wide Web Conf. Steering Committee, 2018, pp. 499–508.
    [64]
    B. Jiang, Z. Zhang, D. Lin, and J. Tang, “Graph learning-convolutional networks,” in Proc. Computer Vision and Pattern Recognition, 2019.
    [65]
    B. Jiang and D. Lin, “Graph laplacian regularized graph convolutional networks for semi-supervised learning,” arXiv preprint arXiv: 1809.09839, 2018.
    [66]
    Y. Feng, H. You, Z. Zhang, R. Ji, and Y. Gao, “Hypergraph neural networks,” in Proc. AAAI Conf. Artificial Intelligence, vol. 33, 2019, pp. 3558–3565.
    [67]
    L. V. Der Maaten and G. E. Hinton, “Visualizing data using t-SNE,” Journal of Machine Learning Research, vol. 9, pp. 2579–2605, 2008.
    [68]
    P. J. Rousseeuw, “Silhouettes: A graphical aid to the interpretation and validation of cluster analysis,” Journal of Computational and Applied Mathematics, vol. 20, no. 1, pp. 53–65, 1987.
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(9)  / Tables(6)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1088) PDF downloads(79) Cited by()

    Highlights

    • Mitigating the problem of exponentially-explosive sampling times in random walk
    • Making the convolution operation on graphs more efficient and flexible like CNN
    • Experimentally validating the efficiency and effectiveness

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return