Features and Applications of Graph Neural Networks
Graph data, as described in “Graph Data Processing Algorithms and Applications to Machine Learning/Artificial Intelligence Tasks,” refers to data structures consisting of vertices (nodes) and edges (edges) connecting them. They represent a variety of network data, such as social media friendships, follower relationships, communities, transportation networks, computer networks, genome and protein interaction networks, customers’ past purchase histories and preferences, etc., and are used to model various systems and relationships in the real world. The G-Net is used to model various systems and relationships in the real world.
Graph neural networks (GNNs) apply deep learning to such graph data, extracting features from the data, constructing neural networks based on the feature representations, and connecting them in multiple stages to capture complex data patterns and build models with nonlinearities Graph Neural Networks.
The difference between ordinary deep learning and graph neural networks lies in the data structures and the algorithms that handle them.
In ordinary deep learning, image data, text data, and other data structures are made into a regular, uniform grid-like data structure and computed based on matrix arithmetic algorithms. In contrast, in graph data, some nodes have many neighbors while others do not, making it difficult to create a uniform data structure with variable neighbor vertices. Furthermore, the topology is complex and very distant nodes may be joined by edges, and locality is not preserved, nodes are not ordered, etc., which are also very different.
In terms of algorithms for handling data, while general deep learning can be applied to all tasks such as classification, regression, clustering, dimensionality compression, etc., with unstructured data represented by vectors, with graph data, tasks for nodes (node classification), tasks for edges For graph data, however, the data structure and approach differ for each task: tasks for nodes (node classification), tasks for edges (link prediction), tasks for graphs (graph classification), and tasks as generative models (graph generation).
For example, in node classification, in a social network representing friendships, if the nodes of the graph are “people,” the edges connecting the nodes are “friendships,” and the characteristics of each node are the attributes of the people (age, gender, occupation, etc.), then node classification requires not only the characteristics of the node itself but also those of its neighbors (its friends). The approach is to learn the characteristics of each node by propagating the node’s characteristics to its neighbors (representation learning).
In graph classification, which identifies the class to which a graph belongs, for example, an approach is taken to find the characteristics of each node (e.g., water solubility, toxicity, etc.) in a chemical compound, with atoms as nodes and bonds as edges.
Given a graph, the task of finding node pairs that should be connected by edges and the probability of an edge occurring at each node is link prediction, which is applied, for example, in social media to recommend a friend or in a bipartite graph consisting of products and purchasing users to predict product purchases. The graph generation is a task that seeks probabilities of edges.
Graph generation is the task of building a model that, given a certain property of a graph, generates similar graphs with that property, and is applied, for example, in drug discovery, to models that generate many graph structures of chemical compounds with a certain property.
The method of embedding, which estimates the similarity between unstructured data by converting unstructured data into vectors and calculating the similarity between the vectors using various methods as described in “Similarity in Machine Learning,” is used not only for natural language processing as described in “Overview, Algorithms and Implementation of Multilingual Embedding,” but also for “Multilingual Embedding” (see “Multilingual Embedding” in “Multilingual Embedding”), but also to cross search systems for image and audio data as described in “Application and Implementation of ElasticSearch and Machine Learning for Multimodal Search“.
In GNNs, a method called “graph embedding” has been proposed, in which the structural information of each node in a graph is represented as a low-dimensional vector. By using this method, the distance between nodes, which is conventionally represented by edges, is reduced to the distance between vectors, which reduces the computational cost and can be used for tasks such as node classification, node clustering, graph visualization, and link prediction by applying parallel and distributed algorithms. They are summarized in “A Survey on Network Embedding“.
The advantage of node embedding is that it enables learning by vectorization of structural information while taking into account a large amount of node attribute information, facilitating the application of deep learning algorithms. Tasks for which node embedding can be applied include dimensional compression of structural information that takes into account node attribute information, which has been difficult to achieve with conventional graph data approaches. Typical graph embedding methods include DeepWalk, LINE, node2Vec, GraRep, GCN, GraphSAGE, and Variational Graph AutoEncoder (described below).
Another application of existing machine learning approaches to GNNs is graph convolution.
Convolution in general image recognition involves scanning a small-sized rectangle called a filter over the input image while performing a sum-of-products operation to detect where in the input image a pattern similar to the pattern represented by the filter is located, and by combining such convolutions, the localization of the input image consisting of individual images By combining such convolutions, local and global features of the input image consisting of individual images are hierarchically recognized.
To apply this to graphs, it is necessary to use data structures and algorithms that apply to graph data that is not localized and that increases or decreases in the number of vertices, rather than (pixel) data that exists regularly in a lattice-like pattern. There are two approaches to this: (1) Spectral graph convolution and (2) Spacial graph convolution.
Spectral graph convolution is a transformation and inverse transformation of the graph Laplacian into space by eigenvectors, which is then transformed into frequency components by Fourier transform in signal processing. Typical approaches for these include ChebNet, ChebyNet, and GCN (Graph Convolutional Network), which are discussed below.
Spacial graph convolution is a method of learning representations by considering the operation of collecting attribute information of surrounding nodes connected by edges to individual nodes as a convolution operation, which is also called graph convolution of message passing. Typical approaches include PATCHY-SAN, DCNN (Diffusion-Convolutional Neural Network), and GraphSAGE, as described below.
In addition, there are several other types of graph autoencoders, such as Structural Deep Network Embedding (SDNE) and Variational Graph Auto-Encoders (VGAE), as well as attention models based on the Encoder-Decoder model, such as the Graph Attention Network (GAT), reported in “Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies. We have also developed a number of other models, including an attention model based on the Encoder-Decoder model, an adversarial attack model reported in “Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies,” and a Temporal Convolutional Model, which is based on the GAT model. Temporal Convolutional Networks (TCN)、Spatio-Temporal Graph Convolutional Networks (STGCN)、Dynamic Graph Convolutional Neural Networks (DGCNN)、Dynamic Attributed Network Embedding framework(DANE)、Continuous-Time Dynamic Network Embeddings(CTDNE)、Causal Anonymous Walks(CAWs)、Dynamic Graph Embedding Model(DynGEM)、Dynamic REPresentations over dynamic graphs(DyREP)、JOint Dynamic user-Item Embedding model(JODIE)、Temporal Graph ATtention(TGAT)、DynamicTriad, and other dynamic graph structure models.
In addition, there are several other types of graph autoencoders, such as Structural Deep Network Embedding(SDNE), Variational Graph Auto-Encoders(VGAE) and attention models based on the Encoder-Decoder model, such as Graph Attention Network(GAT) adversarial attack model reported in “Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies“, Temporal Convolutional Networks (TCN)、Spatio-Temporal Graph Convolutional Networks (STGCN)、Dynamic Graph Convolutional Neural Networks (DGCNN)、Dynamic Attributed Network Embedding framework(DANE)、Continuous-Time Dynamic Network Embeddings(CTDNE)、Causal Anonymous Walks(CAWs)、Dynamic Graph Embedding Model(DynGEM)、Dynamic REPresentations over dynamic graphs(DyREP)、JOint Dynamic user-Item Embedding model(JODIE)、Temporal Graph ATtention(TGAT)、DynamicTriad and other dynamic graph structure models.
To summarize the above, the following several innovations are necessary for deep learning of graph data.
1. capture the graph structure:
Use adjacency matrices and edge features: Graph neural networks (GNNs) use adjacency matrices to capture the adjacency relationships of nodes and propagate information based on them. Edge features can also be leveraged to account for relationships between different nodes.
Graph attributes and structural information: Graphs contain attributes (attributes) and structural information about nodes and edges. Appropriate use of this information can improve the expressive power of the model, allowing for graph-level features such as node degree and cluster coefficients to be taken into account.
2. node representation updates:
Design of Aggregation Function: The function used to aggregate node adjacency information should be chosen appropriate for each graph, e.g., average pooling, maximum pooling, LSTM cells, etc.
Use of adjacency information: The information held by the nodes in the graph is used to update the representation of each node. Typical methods include aggregating the features of neighboring nodes and combining them with the features of the current node.
3. addressing the nature of graphs:
Variable-length graphs: Since graphs have a variable-length structure, they must be designed to accommodate graphs of different sizes. This includes padding, masking, and dynamic graph pooling.
Balancing locality and globality: Graph data has both local patterns and global structure, and the model needs to successfully capture both of these localities and globalities. This includes, for example, the introduction of hierarchical GNNs and the use of attention mechanisms.
4. model design:
Introduce graph pooling: as graphs get larger, it can be expensive to process them using all nodes, so a graph pooling layer may be introduced to process the graph in a hierarchical manner.
Combination with Recurrent Neural Networks (RNNs): RNNs and GNNs are sometimes combined when considering sequences and time-dependencies within the graph structure.
Utilizing transformers: Transformer architectures are sometimes used in the processing of graph data. By taking advantage of the self-attention mechanism on graphs, relationships between nodes can be learned.
5. data augmentation and regularization:
Data Extensions to Graphs: Data extensions to graph data, such as image and text data, are also important. This could include cutting out random subgraphs of the graph or adding noise to node features.
Dropout and batch regularization: Regularization methods such as dropout and batch regularization may be applied to improve the generalization performance of the model.
Thus, graph data can be used to represent data structures that could not be represented in the past, and various applications are being considered. These are listed in papers such as “Graph neural networks: A review of methods and applications,” and include text, images, physics, chemistry, biology, transportation networks, recommendation systems, combinatorial optimization, and many others.
For example, image processing can recognize the relationship between objects in an image to identify whether it is a pet and its owner or a police dog and a criminal being chased,
In the recommendation system, the relationship between a user and a product is represented as a node and the relationship between a user and a product as a purchase is represented as an edge, and when the input is a user or a product, the predicted purchase (missing edge) is sought,
In traffic volume forecasting, the road is divided into segments and represented as a graph, and the traffic volume and distance from the camera at each segment are used as input to forecast traffic congestion and speed,
Graphical analysis/prediction and generation of software structures, and
Applied to language processing, it can be used for contextual and contextual analysis/prediction and generation, as well as
Context prediction and anomaly detection, and
Alternatively, the recent battle against covid-19 involved the application of spatio-temporal graph neural network approaches using biomedical data, epidemiological networks, and supply chain network data. Furthermore, anomaly detection using GNNs is also being considered.
For other applications, see the Murata Lab site at Tokyo Institute of Technology and the reference “Graph Neural Networks: Foundations, Frontiers, and Applications.
- Deconstruction and graph neural networks
In philosophy, ideas have been presented in response to dynamic frame changes. One of them would be what is called poststructuralism. Post-structuralism recognises dynamic elements as differences that could not be seen in static pattern recognition, and by considering changes in patterns, deviations from patterns and deviations from patterns as problems, it discusses the dynamically changing world and tries to describe something like human creativity. This approach is similar to the world of graph neural networks in terms of artificial intelligence technology. In graph neural networks, embeddings are not only the characteristics of the network itself, but also incorporate the topology of the relationships with other entities to which they are connected, which are the characteristics of the network itself.
Various graph neural network implementations
Graph Neural Network implementations are mainly done using deep learning frameworks such as pytorch. Examples of these are described below.
PyTorch is a deep learning library developed by Facebook and provided as open source. It has features such as flexibility, dynamic computation graphs, and GPU acceleration, making it possible to implement a variety of machine learning tasks. Below we describe various examples of implementations using PyTorch.
A graph neural network (GNN) is a type of neural network for data with a graph structure. ) to express relationships between elements. Examples of graph-structured data include social networks, road networks, chemical molecular structures, and knowledge graphs.
This section provides an overview of GNNs and various examples and Python implementations.
We will provide an overview of “Graph Neural Networks: Foundations, Frontiers, and Applications” published by Springer in 2022.
Graph Convolutional Neural Networks (GCN) is a type of neural network that enables convolutional operations on data with a graph structure. While regular convolutional neural networks (CNNs) are effective for lattice-like data such as image data, GCNs were developed as a deep learning method for non-lattice-like data with very complex structures, such as graph data and network data.
Graph Embedding (Graph Embedding) is an approach that combines graph theory and machine learning by mapping the graph structure into a low-dimensional vector space, where the nodes and edges of the graph are represented by dense numerical vectors and processed by a machine learning algorithm. The purpose of graph embedding is to represent each node as a dense vector while preserving information about the graph structure, and this representation makes it possible to handle a wide variety of information. In addition, by using the distance between vectors instead of the distance between nodes conventionally represented by edges, the computational cost can be reduced, and parallel and distributed algorithms can be applied to tasks such as node classification, node clustering, graph visualization, and link prediction.
The encoder/decoder model is one of the key architectures in deep learning, which is structured to encode an input sequence into a fixed-length vector representation and then decode that representation to generate a target sequence. The encoder and decoder model in Graph Neural Networks (GNNs) provides a framework for learning feature representations (embeddings) from graph data and using those representations to solve various tasks on the graph.
Dynamic Graph Embedding is a technique for analyzing time-varying graph data, such as dynamic networks and time-varying graphs. While conventional embedding for static graphs focuses on obtaining a fixed representation of nodes, the goal of dynamic graph embedding is to obtain a representation that corresponds to temporal changes in the graph.
Spatio-Temporal Graph Convolutional Network (STGCN) is a convolution for time-series data on a graph consisting of nodes and edges. Recurrent Neural Network, RNN), which is a model used to predict time variation instead of a recurrent neural network (RNN). This is an effective approach for data where geographic location and temporal changes are important, such as traffic flow and weather data.
GNNs (Graph Neural Networks) are neural networks for handling graph-structured data, which use node and edge (vertex and edge) information to capture patterns and structures in graph data, and are applicable to social network analysis, chemical structure prediction, recommendation systems, graph It can be applied to social network analysis, chemical structure prediction, recommendation systems, graph-based anomaly detection, etc.
Adversarial attack is one of the most widely used attacks against machine learning models, especially for input data such as images, text, and voice. Adversarial attacks aim to cause misrecognition of machine learning models by applying slight perturbations (noise or manipulations). Such attacks can reveal security vulnerabilities and help assess model robustness
Random Walk is a basic concept used in graph theory and probability theory to describe random movement patterns in graphs and to help understand the structure and properties within a graph.
Message passing in machine learning is an effective approach to data and problems with graph structures, and is a widely used technique, especially in methods such as Graph Neural Networks (GNN).
ChebNet (Chebyshev network) is a type of Graph Neural Network (GNN), which is one of the main methods for performing convolution operations on graph-structured data. ChebNet is an approximate implementation of convolution operations on graphs using Chebyshev polynomials, which are used in signal processing.
PATCHY-SAN was proposed by Niepert in “Learning Convolutional Neural Networks for Graphs”. The proposed method solves these problems for arbitrary graphs. This method uses the Weisfeiler-Lehman (WL) kernel, a graph kernel, to measure the similarity between graphs. The specific steps are (1) first sort the nodes by the labels attached by the WL kernel, select a certain number (ω) of nodes from the graph, and then select k nodes that are close in distance to it and order them to obtain a matrix, (2) repeat this for each node attribute ⌘(a_v\) to obtain ⌘(\omega (2) This is repeated for each node attribute \(\times k\times a_v\) to create a tensor of \(\times k\times a_v\), and (3) This tensor is used for convolution as in the case of images.
DCNN is a type of Convolutional Neural Network (CNN), which is described in “Overview, Algorithm and Implementation Examples of CNN” for data structures such as images and graphs. (Graph Convolutional Neural Networks, GCN)” in “Overview, Algorithms, and Examples of Implementation. While ordinary CNN is effective when the data has a grid-like structure, it is difficult to apply it directly to graphs and atypical data, and GCN was developed as a deep learning method for non-grid-like data with very complex structures such as graph data and network data. DCNN applies the concept of the Diffusion Model described in “Overview of Diffusion Models, Algorithms, and Examples of Implementations” to GCN.
Graph Attention Network (GAT) is a deep learning model that uses an attention mechanism to learn the representation of nodes in a graph structure. GAT is a model that uses a set of mechanisms to learn the representation of a node.
Graph Isomorphism Network (GIN) is a neural network model for learning isomorphism of graph structures. The graph isomorphism problem is the problem of determining whether two graphs have the same structure, and is an important approach in many fields.
GraphSAGE (Graph Sample and Aggregated Embeddings) is one of the graph embedding algorithms for learning node embeddings (vector representation) from graph data. By sampling and aggregating the local neighborhood information of nodes, it effectively learns the embedding of each node. This approach makes it possible to obtain high-performance embeddings for large graphs.
Variational Graph Auto-Encoders (VGAE) is a type of VAE described in “Overview, Algorithms, and Examples of Variational Autoencoder (VAE)” for graph data.
VERSE (Vector Space Representations of Graphs) is one of the methods for learning to embed graph data. By embedding graph data in a low-dimensional vector space, it quantifies the characteristics of nodes and edges and provides a representation to be applied to machine learning algorithms. VERSE is known for its ability to learn fast and effective embeddings, especially for large graphs.
- GraphWave Overview, Algorithm, and Example Implementation
GraphWave is a method for learning graph data embedding, a technique for converting node and edge features into low-dimensional vectors that can be useful for applying graph data to machine learning algorithms. GraphWave is a unique approach that can learn effective embeddings by considering the graph structure and surrounding information.
- Overview of LINE (Large-scale Information Network Embedding), Algorithm, and Implementation Examples
LINE (Large-scale Information Network Embedding) is a graph data algorithm for efficiently embedding large-scale information networks (graphs). LINE aims to learn feature vectors (embeddings) of nodes (a node represents an individual element or entity in a graph), which can then be used to capture relationships and similarities among nodes and applied to various tasks.
Node2Vec is one of the algorithms for effectively embedding nodes in graph data. Node2Vec is based on similar ideas to Word2Vec and will use random walks to learn to embed nodes. The algorithm captures the similarity and relatedness of nodes and has been applied to different graph data-related tasks.
GraREP (Graph Random Neural Networks for Representation Learning) is a new deep learning model for graph representation learning. Graph representation learning is the task of learning the representation of each element (node or edge) from graph structure data consisting of nodes and edges, and plays an important role in various fields such as social networks, molecular structures, and communication networks.
Structural Deep Network Embedding (SDNE) is a type of graph autoencoder that extends autoencoders to graphs. An autoencoder is a neural network that performs unsupervised learning to encode given data into a low-dimensional vector in a latent space. Among them, SDNE is a multi-layer autoencoder (Stacked AutoEncoder) that aims to maintain first-order and second-order proximity simultaneously.
Dynamic Graph Neural Networks (D-GNN) are a type of Graph Neural Networks (GNN) designed to deal with dynamic graph data, where nodes and edges change with time. It is designed to handle data in which nodes and edges change over time. (For more information on GNNs, see “Overview of Graph Neural Networks and Examples of Applications and Python Implementations. network data.
Dynamic Graph Embedding is a powerful technique for graph data analysis that takes temporal variation into account. This approach aims to have a representation of nodes and edges on a time axis when graph data varies along time.
- ST-GCN (Spatio-Temporal Graph Convolutional Networks) Overview, Algorithm and Examples of Implementation
ST-GCNs (Spatio-Temporal Graph Convolutional Networks) are a type of graph convolutional networks designed to handle video and temporal data. data), this method can perform feature extraction and classification by considering both spatial information (relationships between nodes in the graph) and temporal information (consecutive frames or time steps). It is primarily used for tasks such as video classification, motion recognition, and sports analysis.
- Overview of DANMF (Dynamic Attributed Network with Matrix Factorization) and Examples of Implementations
DANMF (Dynamic Attributed Network with Matrix Factorization) is one of the graph embedding methods for network data with dynamic attribute information. The method learns to embed nodes by combining node attribute information with the network structure. This method is particularly useful when dynamic attribute information is included, and is suitable when node attributes change with time or when different attribute information is available at different time steps.
DeepWalk is one of the machine learning algorithms for graph data analysis and is particularly suited for a task called node representation learning (Node Embedding), a method aimed at embedding nodes into a low-dimensional vector space, where nodes share with their neighbors in the graph DeepWalk has been used in a variety of applications, including social networks, web page link graphs, and collaborative filtering.
- Overview and implementation examples of multi-agent systems using graph neural networks
Multi-agent systems using graph neural networks (GNNs) are a suitable approach when multiple agents interact in a graph structure and relationships and dependencies between agents are modelled.
Overview of graph neural network technology, a framework for deep learning on graph data. Used for estimation of compound properties, natural language processing using Atttension, co-occurrence networks, image information processing, etc.
Reference Information and Reference Books
“A Gentle Introduction to Graph Neural Networks” by GoogleReasearch, which conducts cutting-edge research on Graph Neural Networks, and the Murata Lab at Tokyo Institute of Technology have a variety of examples of GNN research in Japan.
For more information on graph data, see “Graph Data Processing Algorithms and Applications to Machine Learning/Artificial Intelligence Tasks. Also see “Knowledge Information Processing Techniques” for details specific to knowledge graphs. For more information on deep learning in general, see “About Deep Learning.
Reference book is
“Graph Neural Networks: Foundations, Frontiers, and Applications“等がある。
“Introduction to Graph Neural Networks“
“Graph Neural Networks in Action“
コメント