Notes on the basics of Graph Neural Network

Some notes

• if for any pair of nodes, we can traverse from node A to node B, then it is strongly connected

• graph diameter means the longest distance of any pair of nodes

• degree centrality means N_degree / (n - 1)

• eigenvector centrality is a measure of the influence of a node in a network https://en.wikipedia.org/wiki/Eigenvector_centrality

  • Unsupervised Learning for Identifying High Eigenvector Centrality Nodes: A Graph Neural Network Approach https://arxiv.org/pdf/2111.05264.pdf

• Betweenness centrality is a way of detecting the amount of influence a node has over the flow of information in a graph https://neo4j.com/docs/graph-data-science/current/algorithms/betweenness-centrality/#:~:text=Betweenness%20centrality%20is%20a%20way,of%20nodes%20in%20a%20graph.

  • Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach https://arxiv.org/pdf/1905.10418.pdf

• A Graph Neural Network to approximate Network Centrality metrics in Neo4j https://medium.com/neo4j/a-graph-neural-network-to-approximate-network-centralities-in-neo4j-2ee96705a464

• network dismantling problem

  • The purpose of Network Dismantling (ND) is to find an optimal set of nodes and removing these nodes can greatly decrease the network connectivity

  • Machine learning dismantling and early-warning signals of disintegration in complex systems https://www.nature.com/articles/s41467-021-25485-8

  • Betweenness Approximation for Hypernetwork Dismantling with Hypergraph Neural Network https://arxiv.org/pdf/2203.03958.pdf

  • Generalized network dismantling https://www.pnas.org/doi/10.1073/pnas.1806108116

    • realistic removal costs

• The Split-and-Connect (SPAC) Method

  • A simple yet effective balanced edge partition model for parallel computing https://dl.acm.org/doi/pdf/10.1145/3084451

  • Scalable Edge Partitioning https://arxiv.org/pdf/1808.06411.pdf

Resources

videos

• https://www.bilibili.com/video/BV1K5411H7EQ

• https://www.bilibili.com/video/BV1iT4y1d7zP

  • https://distill.pub/2021/gnn-intro/

books

• Graph Representation Learning Book

  • https://www.cs.mcgill.ca/~wlh/grl_book/

• Graph Neural Networks

  • https://graph-neural-networks.github.io/