# The Impact of Global Structural Information in Graph Neural Networks Applications

^{*}

## Abstract

**:**

## 1. Introduction

- Our Contribution

- We propose and formalize three different types of global structural information “injection”. We test how the injection of global structural information impacts the performance of six GNN architectures (GCN [10], Graphsage [11], and GAT [12] for node-level tasks; GCN with global readout, DiffPool [13] and k-GNN [8] for graph-level tasks) on both transductive and inductive tasks. Results show that the injection of global structural information significantly impacts current state-of-the-art models on common graph-related tasks.
- As we discuss later in the paper, injecting global structural information can be impractical. We then identify a novel and practical regularization strategy, called RWRReg, based on random walks with restart [14]. RWRReg maintains the permutation-invariance of GNN models, and leads to an average $5\%$ increase in accuracy on both node classification and graph classification.
- We introduce a theoretical result proving that the information extracted by random walks with restart can “speed up” the 1-Weisfeiler–Leman (1-WL) algorithm [7]. In more detail, we show that, by constructing an initial coloring based on random walks with restart probabilities, the 1-WL algorithm always terminates in one iteration. Given the known relationship between GNNs and the 1-WL algorithm, this result shows that providing information obtained from random walks with restart to GNN models can improve their practical ability of distinguishing non-isomorphic graphs.

## 2. Preliminaries

#### 2.1. Notation

#### 2.2. Graph Neural Networks

#### 2.3. Random Walks with Restart

## 3. Random Walks with Restart and the Weisfeiler–Leman Algorithm

**Proposition**

**1.**

## 4. Injecting Global Information in MPNNs

#### 4.1. Types of Global Structural Information Injection

**Adjacency Matrix.**We provide GNNs with direct access to the adjacency matrix by concatenating each node’s adjacency matrix row to its feature vector. This explicitly empowers the GNN model with the connectivity of each node, and allows for higher level structural reasoning when considering a neighbourhood (the model will have access to the connectivity of the whole neighbourhood when aggregating messages from neighbouring nodes). In more detail, the row of the adjacency matrix for a specific node pinpoints the position of the node in the graph (i.e., it acts as a kind of positional encoding), and during the message passing procedure, when a node aggregates information from its neighbours, it allows the network to get a more precise positioning of the node in the graph.

**Random Walk with Restart (RWR) Matrix.**We perform RWR [14] from each node v, thus obtaining a n-dimensional vector that gives a score of how much v is “related” to every other node in the graph. For every node, we concatenate its vector of RWR coefficients to its feature vector. The choice of RWR is motivated by their capability to capture the relevance between two nodes [16] and the global structure of a graph [17,18], and by the possibility to modulate the exploration of long-range dependencies by changing the restart probability. Intuitively, if a RWR starting at node v is very likely to visit a node u (e.g., there are multiple paths that connect the two), then there will be a high score in the RWR vector for v at position u. This gives the GNN model higher level information about the global structure of the graph, and, again, it allows for high level reasoning on neighbourhood connectivity.

**RWR Matrix + RWR Regularization.**Together with the addition of the RWR score vector to the feature vector of each node, we also introduce a regularization term based on RWR that pushes nodes with mutually high RWR scores to have embeddings that are close to each other (independently of how far they are in the graph). Let $\mathit{S}$ be the $n\times n$ matrix with the RWR scores. We define the RWRReg (Random Walk with Restart Regularization) loss as follows:

#### 4.2. Choice of Models

- Simple Aggregation Models

- Attention Models

- Pooling Techniques

- Beyond WL

## 5. Evaluation of the Injection of Global Structural Information

#### 5.1. Node Classification

#### 5.2. Graph Classification

#### 5.3. Counting Triangles

## 6. Practical Aspects

#### 6.1. RWRReg

**only**the RWRReg term. We consider the same settings and tasks presented in Section 5, and results are shown in Table 4. The results show that the sole addition of the RWRReg term increases the performance of the considered models by more than 5%. At the same time, RWRReg (i) does not increase the input size or the number of parameters, (ii) does not require additional operations at inference time, (iii) does not require additional supervision (it is in fact a self-supervised objective), (iv) maintains the permutation invariance of MPNN models, and (v) there is a vast literature on efficient methods for computing RWR, even for web-scale graphs (e.g., [15,33,34]). Hence, the only downside of RWRReg is the storage of the RWR matrix during training on very large graphs.

#### 6.2. Sparsification of the RWR Matrix

#### 6.3. Impact of RWR Restart Probability

## 7. Related Work

## 8. Conclusions

## Author Contributions

## Funding

## Data Availability Statement

## Conflicts of Interest

## Appendix A. Proof of Proposition 1

**Proposition**

**A1.**

**Proof.**

## Appendix B. Model Implementation Details

Model | Implementation | Access Date |
---|---|---|

GCN (for node classification) | github.com/tkipf/pygcn | 2 February 2021 |

GCN (for graph classification) GCN (for triangle counting) | github.com/bknyaz/graph_nn | 2 February 2021 |

GraphSage | github.com/williamleif/graphsage-simple | 10 February 2021 |

GAT | github.com/Diego999/pyGAT | 13 February 2021 |

DiffPool | github.com/RexYing/diffpool | 15 February 2021 |

k-GNN | github.com/chrsmrrs/k-gnn | 15 February 2021 |

- Training Details

- Computing Infrastructure

#### Appendix B.1. GCN (Node Classification)

#### Appendix B.2. GCN (Graph Classification)

#### Appendix B.3. GCN (Counting Triangles)

#### Appendix B.4. GraphSage

#### Appendix B.5. GAT

#### Appendix B.6. DiffPool

#### Appendix B.7. k-GNN

## Appendix C. Datasets

Dataset | Nodes | Edges | Classes | Features | Label Rate |
---|---|---|---|---|---|

Cora | 2708 | 5429 | 7 | 1433 | 0.052 |

Pubmed | 19,717 | 44,338 | 3 | 500 | 0.003 |

Citeseer | 3327 | 4732 | 6 | 3703 | 0.036 |

Dataset | Graphs | Classes | Avg. # Nodes | Avg. # Edges |
---|---|---|---|---|

ENZYMES | 600 | 6 | 32.63 | 62.14 |

D&D | 1178 | 2 | 284.32 | 715.66 |

PROTEINS | 1113 | 2 | 39.1 | 72.82 |

TRIANGLES | 45,000 | 10 | 20.85 | 32.74 |

## Appendix D. Adjacency Matrix Features Lead to Bad Generalization on the Triangle Counting Task

**Figure A1.**Training and test losses of GCN with different structural information injection on the triangle counting task.

## Appendix E. Fast Implementation of the Random Walk with Restart Regularization

## Appendix F. Empirical Analysis of the Random Walk with Restart Matrix

**Figure A2.**Average distribution of the RWR weights at different distances for the following node classification datasets: (

**a**) Cora, (

**b**) Pubmed, (

**c**) Citeseer. Distance zero indicates the weight that a node assigns to itself.

**Table A4.**Average and standard deviation, over all nodes, of Kendall Tau-b values measuring the non-trivial relationships between nodes captured by the RWR weights.

Dataset | Average Kendall Tau-b |
---|---|

Cora | $0.729\pm 0.082$ |

Pubmed | $0.631\pm 0.057$ |

Citeseer | $0.722\pm 0.171$ |

## References

- Wu, Z.; Pan, S.; Chen, F.; Long, G.; Zhang, C.; Yu, P.S. A Comprehensive Survey on Graph Neural Networks. arXiv
**2019**, arXiv:1901.00596. [Google Scholar] [CrossRef] [PubMed] [Green Version] - Gilmer, J.; Schoenholz, S.S.; Riley, P.F.; Vinyals, O.; Dahl, G.E. Neural Message Passing for Quantum Chemistry. In Proceedings of the International Conference on Machine Learning, Sydney, Australia, 6–11 August 2017. [Google Scholar]
- Li, Q.; Han, Z.; Wu, X. Deeper Insights Into Graph Convolutional Networks for Semi-Supervised Learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, Palo Alto, CA, USA, 7–8 February 2018. [Google Scholar]
- Alon, U.; Yahav, E. On the Bottleneck of Graph Neural Networks and its Practical Implications. In Proceedings of the International Conference on Learning Representations, Vienna, Austria, 4 May 2021. [Google Scholar]
- Masuda, N.; Porter, M.A.; Lambiotte, R. Random walks and diffusion on networks. Phys. Rep.
**2017**, 716–717, 1–58. [Google Scholar] [CrossRef] - Bronstein, M. Do We Need Deep Graph Neural Networks? Available online: https://towardsdatascience.com/do-we-need-deep-graph-neural-networks-be62d3ec5c59 (accessed on 17 November 2021).
- Weisfeiler, B.; Leman, A. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nauchno-Tech. Inf.
**1968**, 2, 12–16. [Google Scholar] - Morris, C.; Ritzert, M.; Fey, M.; Hamilton, W.L.; Lenssen, J.E.; Rattan, G.; Grohe, M. Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, Honolulu, HI, USA, 27 January–1 February 2019. [Google Scholar]
- Li, G.; Müller, M.; Ghanem, B.; Koltun, V. Training Graph Neural Networks with 1000 layers. In Proceedings of the International Conference on Machine Learning (ICML), Online, 18–24 July 2021. [Google Scholar]
- Kipf, T.N.; Welling, M. Semi-Supervised Classification with Graph Convolutional Networks. In Proceedings of the International Conference on Learning Representations, Toulon, France, 24–26 April 2017. [Google Scholar]
- Hamilton, W.L.; Ying, R.; Leskovec, J. Inductive Representation Learning on Large Graphs. In Proceedings of the Conference on Neural Information Processing Systems, Long Beach, CA, USA, 4–9 December 2017. [Google Scholar]
- Veličković, P.; Cucurull, G.; Casanova, A.; Romero, A.; Liò, P.; Bengio, Y. Graph Attention Networks. In Proceedings of the International Conference on Learning Representations, Vancouver, BC, Canada, 30 April–3 May 2018. [Google Scholar]
- Ying, Z.; You, J.; Morris, C.; Ren, X.; Hamilton, W.L.; Leskovec, J. Hierarchical Graph Representation Learning with Differentiable Pooling. In Proceedings of the Conference on Neural Information Processing Systems, Montréal, QC, Canada, 6–14 December 2018. [Google Scholar]
- Page, L.; Brin, S.; Motwani, R.; Winograd, T. The PageRank citation ranking: Bringing order to the Web. In Proceedings of the 7th International World Wide Web Conference (WWW), Brisbane, Australia, 14–18 April 1998. [Google Scholar]
- Lofgren, P. Efficient Algorithms for Personalized PageRank. arXiv
**2015**, arXiv:1512.04633. [Google Scholar] - Tong, H.; Faloutsos, C.; Pan, J. Fast Random Walk with Restart and Its Applications. In Proceedings of the International Conference on Data Mining, Hong Kong, China, 18–22 December 2006. [Google Scholar]
- Jin, W.; Jung, J.; Kang, U. Supervised and extended restart in random walks for ranking and link prediction in networks. PLoS ONE
**2019**, 14, e0213857. [Google Scholar] [CrossRef] [PubMed] [Green Version] - He, J.; Li, M.; Zhang, H.J.; Tong, H.; Zhang, C. Manifold-Ranking Based Image Retrieval. In Proceedings of the 12th Annual ACM International Conference on Multimedia, New York, NY, USA, 10–16 October 2004; Association for Computing Machinery: New York, NY, USA, 2004; pp. 9–16. [Google Scholar] [CrossRef]
- Shervashidze, N.; Schweitzer, P.; Leeuwen, E.J.; Mehlhorn, K.; Borgwardt, K.M. Weisfeiler-Lehman graph kernels. J. Mach. Learn. Res.
**2011**, 12, 2539–2561. [Google Scholar] - Xu, K.; Hu, W.; Leskovec, J.; Jegelka, S. How Powerful are Graph Neural Networks? In Proceedings of the 7th International Conference on Learning Representations (ICLR), New Orleans, LA, USA, 6–9 May 2019. [Google Scholar]
- Lee, J.B.; Rossi, R.A.; Kim, S.; Ahmed, N.K.; Koh, E. Attention Models in Graphs: A Survey. arXiv
**2018**, arXiv:1807.07984. [Google Scholar] [CrossRef] [Green Version] - Lee, J.B.; Rossi, R.A.; Kong, X. Graph Classification using Structural Attention. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, London, UK, 19–23 August 2018. [Google Scholar]
- Zhang, J.; Shi, X.; Xie, J.; Ma, H.; King, I.; Yeung, D.Y. GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs. In Proceedings of the Uncertainty in Artificial Intelligence, Monterey, CA, USA, 6–10 August 2018. [Google Scholar]
- Cangea, C.; Veličković, P.; Jovanović, N.; Kipf, T.; Liò, P. Towards Sparse Hierarchical Graph Classifiers. In Proceedings of the NeurIPS Workshop on Relational Representation Learning, Montréal, QC, Canada, 3–8 December 2018. [Google Scholar]
- Diehl, F.; Brunner, T.; Truong Le, M.; Knoll, A. Towards Graph Pooling by Edge Contraction. In Proceedings of the ICML Workshop on Learning and Reasoning with Graph-Structured Data, Long Beach, CA, USA, 9–15 June 2019. [Google Scholar]
- Gao, H.; Ji, S. Graph U-Nets. 2019. Available online: http://xxx.lanl.gov/abs/1905.05178 (accessed on 20 February 2021).
- Lee, J.; Lee, I.; Kang, J. Self-Attention Graph Pooling. In Proceedings of the International Conference on Machine Learning, Long Beach, CA, USA, 10–15 June 2019. [Google Scholar]
- Murphy, R.L.; Srinivasan, B.; Rao, V.A.; Ribeiro, B. Relational Pooling for Graph Representations. In Proceedings of the International Conference on Machine Learning, Long Beach, CA, USA, 10–15 June 2019. [Google Scholar]
- Sen, P.; Namata, G.; Bilgic, M.; Getoor, L.; Galligher, B.; Eliassi-Rad, T. Collective Classification in Network Data. AI Mag.
**2008**, 29, 93. [Google Scholar] [CrossRef] [Green Version] - Kersting, K.; Kriege, N.M.; Morris, C.; Mutzel, P.; Neumann, M. Benchmark Data Sets for Graph Kernels. 2016. Available online: https://ls11-www.cs.tu-dortmund.de/staff/morris/graphkerneldatasets#citing_this_website (accessed on 10 February 2021).
- Yang, Z.; Cohen, W.W.; Salakhutdinov, R. Revisiting Semi-Supervised Learning with Graph Embeddings. In Proceedings of the International Conference on Machine Learning, New York, NY, USA, 19–24 June 2016. [Google Scholar]
- Knyazev, B.; Taylor, G.; Amer, M. Understanding Attention in Graph Neural Networks. In Proceedings of the ICLR RLGM Workshop, New Orleans, LA, USA, 6–9 May 2019. [Google Scholar]
- Wei, Z.; He, X.; Xiao, X.; Wang, S.; Shang, S.; Wen, J. TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs. In Proceedings of the 2018 International Conference on Management of Data, Houston, TX, USA, 10–15 June 2018; pp. 441–456. [Google Scholar] [CrossRef] [Green Version]
- Wang, S.; Yang, R.; Wang, R.; Xiao, X.; Wei, Z.; Lin, W.; Yang, Y.; Tang, N. Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries. ACM Transact. Data. Syst.
**2019**, 44, 1–37. [Google Scholar] [CrossRef] [Green Version] - Lofgren, P.; Banerjee, S.; Goel, A. Personalized PageRank Estimation and Search: A Bidirectional Approach. In Proceedings of the Ninth ACM International Conference on Web Search and Data Mining, San Francisco, CA, USA, 22–25 February 2016; Association for Computing Machinery: New York, NY, USA, 22–25 February 2016; pp. 163–172. [Google Scholar] [CrossRef] [Green Version]
- Wang, S.; Yang, R.; Xiao, X.; Wei, Z.; Yang, Y. FORA: Simple and Effective Approximate Single-Source Personalized PageRank. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, 13–17 August 2017; pp. 505–514. [Google Scholar]
- Klicpera, J.; Weißenberger, S.; Günnemann, S. Diffusion Improves Graph Learning. In Proceedings of the Conference on Neural Information Processing Systems, Online, 8–14 December 2019. [Google Scholar]
- Ying, R.; He, R.; Chen, K.; Eksombatchai, P.; Hamilton, W.L.; Leskovec, J. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, London, UK, 19 July 2018; pp. 974–983. [Google Scholar] [CrossRef] [Green Version]
- Zhang, C.; Song, D.; Huang, C.; Swami, A.; Chawla, N.V. Heterogeneous Graph Neural Network. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA, 4–8 August 2019; pp. 793–803. [Google Scholar] [CrossRef]
- Abu-El-Haija, S.; Kapoor, A.; Perozzi, B.; Lee, J. N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, Monterey, CA, USA, 6–10 August 2018. [Google Scholar]
- Abu-El-Haija, S.; Perozzi, B.; Kapoor, A.; Harutyunyan, H.; Alipourfard, N.; Lerman, K.; Steeg, G.V.; Galstyan, A. MixHop: Higher-Order Graph Convolution Architectures via Sparsified Neighborhood Mixing. In Proceedings of the International Conference on Machine Learning, Long Beach, CA, USA, 10–15 June 2019. [Google Scholar]
- Zhuang, C.; Ma, Q. Dual Graph Convolutional Networks for Graph-Based Semi-Supervised Classification. In Proceedings of the 2018 World Wide Web Conference, Lyon, France, 23–27 April 2018; pp. 499–508. [Google Scholar] [CrossRef] [Green Version]
- Klicpera, J.; Bojchevski, A.; Günnemann, S. Predict then Propagate: Graph Neural Networks meet Personalized PageRank. In Proceedings of the International Conference on Learning Representations, New Orleans, LA, USA, 6–9 May 2019. [Google Scholar]
- Bojchevski, A.; Klicpera, J.; Perozzi, B.; Kapoor, A.; Blais, M.J.; Rozemberczki, B.; Lukasik, M.; Gunnemann, S. Scaling Graph Neural Networks with Approximate PageRank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Online, 6–10 July 2020; pp. 2464–2473. [Google Scholar]
- Gao, H.; Pei, J.; Huang, H. Conditional Random Field Enhanced Graph Convolutional Neural Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Anchorage, AK, USA, 4–8 August 2019; pp. 276–284. [Google Scholar] [CrossRef]
- Jiang, B.; Lin, D. Graph Laplacian Regularized Graph Convolutional Networks for Semi-supervised Learning. arXiv
**2018**, arXiv:1809.09839. [Google Scholar] - Xu, K.; Li, C.; Tian, Y.; Sonobe, T.; Ichi Kawarabayashi, K.; Jegelka, S. Representation Learning on Graphs with Jumping Knowledge Networks. In Proceedings of the International Conference on Machine Learning, Stockholm, Sweden, 10–15 July 2018. [Google Scholar]
- Sato, R.; Yamada, M.; Kashima, H. Approximation Ratios of Graph Neural Networks for Combinatorial Problems. In Proceedings of the Conference on Neural Information Processing Systems, Vancouver, BC, Canada, 8–14 December 2019. [Google Scholar]
- Loukas, A. What graph neural networks cannot learn: Depth vs width. In Proceedings of the International Conference on Learning Representations (ICLR), Online, 26 April–1 May 2020. [Google Scholar]
- Xu, K.; Li, J.; Zhang, M.; Du, S.S.; Ichi Kawarabayashi, K.; Jegelka, S. What Can Neural Networks Reason About? In Proceedings of the International Conference on Learning Representations (ICLR), Online, 26 April–1 May 2020. [Google Scholar]
- Andersen, R.; Chung, F.; Lang, K. Local Graph Partitioning using PageRank Vectors. In Proceedings of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), Berkeley, CA, USA, 21–24 October 2006. [Google Scholar] [CrossRef]
- Bahmani, B.; Chowdhury, A.; Goel, A. Fast incremental and personalized PageRank. Proc. VLDB Endow.
**2010**, 4, 173–184. [Google Scholar] [CrossRef] [Green Version] - Micali, S.; Zhu, Z.A. Reconstructing markov processes from independent and anonymous experiments. Discret. Appl. Math.
**2016**, 200, 108–122. [Google Scholar] [CrossRef] - Ivanov, S.; Burnaev, E. Anonymous walk embeddings. arXiv
**2018**, arXiv:1805.11921. [Google Scholar] - Srivastava, N.; Hinton, G.; Krizhevsky, A.; Sutskever, I.; Salakhutdinov, R. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. J. Mach. Learn. Res.
**2014**, 15, 1929–1958. [Google Scholar] - Kingma, D.P.; Ba, J. Adam: A Method for Stochastic Optimization. In Proceedings of the International Conference on Learning Representations, San Diego, CA, USA, 7–9 May 2015. [Google Scholar]
- Clevert, D.A.; Unterthiner, T.; Hochreiter, S. Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs). In Proceedings of the International Conference on Learning Representations, San Juan, PR, USA, 4–6 May 2016. [Google Scholar]
- Ioffe, S.; Szegedy, C. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. In Proceedings of the International Conference on Learning Representations, San Diego, CA, USA, 7–9 May 2015. [Google Scholar]
- Kendall, M.G. The Treatment of Ties in Ranking Problems. Biometrika
**1945**, 33, 239–251. [Google Scholar] [CrossRef] [PubMed]

**Figure 1.**Performance of GCN on node classification for different values of K when trained with RWRReg with Top-K sparsification of the RWR matrix on the following datasets: (

**a**) Cora, (

**b**) Pubmed, (

**c**) Citeseer.

**Figure 2.**Accuracy on Cora (

**a**), and on D&D (

**b**), of GCN without and with the injection of structural information, and for different restart probabilities of RWR.

**Table 1.**Node classification accuracy results of different models with added Adjacency matrix features (AD), RWR features (RWR), and RWR features + RWR Regularization (RWR + RWRReg).

Model | Structural | Dataset | ||
---|---|---|---|---|

Information | Cora | Pubmed | Citeseer | |

none | $0.799\pm 0.029$ | $0.776\pm 0.022$ | $0.663\pm 0.095$ | |

AD | $0.806\pm 0.035$ | $0.779\pm 0.070$ | $0.653\pm 0.104$ | |

GCN | RWR | $0.817\pm 0.025$ | $0.782\pm 0.042$ | $0.665\pm 0.098$ |

RWR + RWRReg | $\mathbf{0.842}\pm \mathbf{0.026}$ | $\mathbf{0.811}\pm \mathbf{0.037}$ | $\mathbf{0.690}\pm \mathbf{0.102}$ | |

none | $0.806\pm 0.017$ | $0.807\pm 0.016$ | $0.681\pm 0.021$ | |

AD | $0.803\pm 0.014$ | $0.803\pm 0.013$ | $0.688\pm 0.020$ | |

GraphSage | RWR | $0.816\pm 0.014$ | $0.807\pm 0.015$ | $0.693\pm 0.019$ |

RWR + RWRReg | $\mathbf{0.837}\pm \mathbf{0.015}$ | $\mathbf{0.820}\pm \mathbf{0.010}$ | $\mathbf{0.728}\pm \mathbf{0.020}$ | |

none | $0.815\pm 0.021$ | $0.804\pm 0.011$ | $0.664\pm 0.008$ | |

AD | $0.823\pm 0.019$ | $0.796\pm 0.014$ | $0.672\pm 0.017$ | |

GAT | RWR | $0.833\pm 0.020$ | $0.811\pm 0.009$ | $0.686\pm 0.009$ |

RWR + RWRReg | $\mathbf{0.848}\pm \mathbf{0.019}$ | $\mathbf{0.828}\pm \mathbf{0.010}$ | $\mathbf{0.701}\pm \mathbf{0.011}$ |

**Table 2.**Graph classification accuracy results of different models with added Adjacency matrix features (AD), RWR features (RWR), and RWR features + RWR Regularization (RWR + RWRReg).

Model | Structural | Dataset | ||
---|---|---|---|---|

Information | ENZYMES | D&D | PROTEINS | |

none | $0.570\pm 0.052$ | $0.755\pm 0.028$ | $0.740\pm 0.035$ | |

AD | $0.591\pm 0.076$ | $0.779\pm 0.022$ | $0.775\pm 0.042$ | |

GCN | RWR | $0.584\pm 0.055$ | $0.775\pm 0.023$ | $0.784\pm 0.034$ |

RWR + RWRReg | $\mathbf{0.616}\pm \mathbf{0.065}$ | $\mathbf{0.790}\pm \mathbf{0.023}$ | $\mathbf{0.795}\pm \mathbf{0.032}$ | |

none | $0.661\pm 0.031$ | $0.793\pm 0.022$ | $0.813\pm 0.017$ | |

AD | $0.711\pm 0.027$ | $0.837\pm 0.020$ | $0.821\pm 0.039$ | |

DiffPool | RWR | $0.687\pm 0.025$ | $0.824\pm 0.028$ | $0.783\pm 0.043$ |

RWR + RWRReg | $\mathbf{0.721}\pm \mathbf{0.039}$ | $\mathbf{0.840}\pm \mathbf{0.024}$ | $\mathbf{0.834}\pm \mathbf{0.038}$ | |

none | $0.515\pm 0.111$ | $0.756\pm 0.021$ | $0.763\pm 0.043$ | |

AD | $0.572\pm 0.063$ | $0.778\pm 0.020$ | $0.751\pm 0.034$ | |

k-GNN | RWR | $\mathbf{0.573}\pm \mathbf{0.077}$ | $\mathbf{0.794}\pm \mathbf{0.022}$ | $0.781\pm 0.028$ |

RWR + RWRReg | $0.571\pm 0.080$ | $0.786\pm 0.021$ | $\mathbf{0.785}\pm \mathbf{0.026}$ |

**Table 3.**Mean Squared Error of GCN with different types of global structural information injection on the TRIANGLES dataset.

Model | TRIANGLES Test Set | ||
---|---|---|---|

Global | Small | Large | |

GCN | $2.290$ | $1.311$ | $3.608$ |

GCN-AD | $4.746$ | $1.162$ | $5.971$ |

GCN-RWR | $2.044$ | $\mathbf{1.101}$ | $2.988$ |

GCN-RWR + RWRReg | $\mathbf{2.029}$ | $1.166$ | $\mathbf{2.893}$ |

**Table 4.**Results for the addition of only the RWRReg term to existing models on node classification (accuracy), graph classification (accuracy), and triangle counting (MSE—lower is better).

Model | Regularization | Dataset | ||
---|---|---|---|---|

Node Classification | ||||

Cora | Pubmed | Citeseer | ||

GCN | none | $0.799\pm 0.029$ | $0.776\pm 0.022$ | $0.663\pm 0.095$ |

RWRReg | $\mathbf{0.861}\pm \mathbf{0.025}$ | $\mathbf{0.799}\pm \mathbf{0.034}$ | $\mathbf{0.686}\pm \mathbf{0.096}$ | |

GraphSage | none | $0.806\pm 0.017$ | $0.807\pm 0.016$ | $0.681\pm 0.021$ |

RWRReg | $\mathbf{0.841}\pm \mathbf{0.016}$ | $\mathbf{0.818}\pm \mathbf{0.017}$ | $\mathbf{0.721}\pm \mathbf{0.021}$ | |

GAT | none | $0.815\pm 0.021$ | $0.804\pm 0.011$ | $0.664\pm 0.008$ |

RWRReg | $\mathbf{0.824}\pm \mathbf{0.022}$ | $\mathbf{0.811}\pm \mathbf{0.013}$ | $\mathbf{0.702}\pm \mathbf{0.013}$ | |

Graph Classification | ||||

ENZYMES | D&D | PROTEINS | ||

GCN | none | $0.570\pm 0.052$ | $0.755\pm 0.028$ | $0.740\pm 0.035$ |

RWRReg | $\mathbf{0.621}\pm \mathbf{0.041}$ | $\mathbf{0.786}\pm \mathbf{0.024}$ | $\mathbf{0.785}\pm \mathbf{0.036}$ | |

DiffPool | none | $0.661\pm 0.031$ | $0.793\pm 0.022$ | $0.813\pm 0.017$ |

RWRReg | $\mathbf{0.733}\pm \mathbf{0.032}$ | $\mathbf{0.822}\pm \mathbf{0.025}$ | $\mathbf{0.820}\pm \mathbf{0.038}$ | |

k-GNN | none | $0.515\pm 0.111$ | $0.756\pm 0.021$ | $0.763\pm 0.043$ |

RWRReg | $\mathbf{0.582}\pm \mathbf{0.075}$ | $\mathbf{0.787}\pm \mathbf{0.022}$ | $\mathbf{0.780}\pm \mathbf{0.028}$ | |

Triangles Test Set | ||||

Global | Small | Large | ||

GCN | none | $2.290$ | $1.311$ | $3.608$ |

RWRReg | $\mathbf{2.187}$ | $\mathbf{1.282}$ | $\mathbf{3.014}$ |

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. |

© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

## Share and Cite

**MDPI and ACS Style**

Buffelli, D.; Vandin, F.
The Impact of Global Structural Information in Graph Neural Networks Applications. *Data* **2022**, *7*, 10.
https://doi.org/10.3390/data7010010

**AMA Style**

Buffelli D, Vandin F.
The Impact of Global Structural Information in Graph Neural Networks Applications. *Data*. 2022; 7(1):10.
https://doi.org/10.3390/data7010010

**Chicago/Turabian Style**

Buffelli, Davide, and Fabio Vandin.
2022. "The Impact of Global Structural Information in Graph Neural Networks Applications" *Data* 7, no. 1: 10.
https://doi.org/10.3390/data7010010