Graph Neural Networks: A Brief Analysis
What are Graphs?
Graphs are data structures that represent a set of objects to which other pairs of objects are connected. Objects to be connected are represented by points called vertices / nodes, and the connections between them are called edges.
Graphs are defined as: G = (V, E), where V is the set of vertices and E is the set of edges.
Graphs can be used to represent a wide range of real-world data sets, including social networks, cellular structures, geographical maps, and so on. Graphs can also be used to model random data such as photos and text. Graph theory exists because we need a mechanism to express relationships between objects computationally and mathematically. Users on a social media site, neighbors in a neighborhood, addresses or places on a map, pixels in a picture, or neurons in our brain are all examples of these objects. The foundation of graph theory, particularly as it applies to machine learning, is that most of our data can be better understood when we can represent its relationships. Therefore, graphs are used to integrate these relationships so that we can work with the entire dataset.
What are GNNs?
Convolutional Neural Networks (CNNs) cannot solve graph-related issues because graph data is extremely complicated, and it poses multiple problems for CNNs. Graph Neural Network (GNN) is a relatively modern deep learning approach that falls under the domain of neural networks that focuses on processing data on graphs to make complicated graph data understandable. These algorithms search for information in graphs and predict outcomes based on the information acquired. The fundamental application is node classification, in which each node v is naturally characterized by its characteristics and linked nodes x and is associated with a ground-truth label tᵥ. Given a partly labeled graph G, the goal of a GNN is to learn a state embedding hᵥ ∈ Rˢ that comprises information about each node’s neighbors and itself. The state embedding hᵥ is an s-dimensional vector of node v that can be used to generate an output oᵥ as the predicted label for node v.
where,
xᵥ is feature vector for node v.
xco[v] is feature vector for the edges of node v.
hNv denotes the embedding of the neighboring nodes of v.
xNv denotes the features of the neighboring nodes of v.
The function f is a parametric function called local transition function. It is shared by all nodes and updates node state based on the input neighborhood. Function g is the local output function that computes the GNN output by passing the state h v and the feature xv to the function g. Both functions f and g can be seen as feed-forward neural networks.
Let H, O, X, and XN be the matrices formed by stacking all the embeddings, outputs, features, and node features, respectively. Then we get a compact form as follows:
where F, the global transition function, and G, the global output function, are stacked representations of f and g for each node in a graph. The fixed point of Eq H =F(H,X) is the value of H, which is uniquely determined under the assumption that F is a contraction map. GNN computes the state using the standard iterative technique suggested by Banach’s fixed point theorem:
where H^t represents the t-th iteration of H. For any starting value, the dynamical system Eq. H^(t+1) = F(H^t, X) converges exponentially quickly to the solution.
Applications of GNNs
1. Improving Travel Time Predictions
Many individuals use tools like Google Maps to know time estimates for forthcoming travels, whether they’re on their way to catch a flight, seeking for some new cafes etc. However, factors such as traffic volume and road construction might throw those projections off. Google teams employed graph neural networks to reduce the risk of incorrect forecasts.
They began by constructing “supersegments,” which were sections of nearby roadways that shared considerable traffic volumes. By considering local road networks as graphs, GNNs came into the picture. Each route segment is a node, and the edge points are adjacent segments or sites where roads meet. The graph neural networks predicted traffic on roads ahead and behind a vehicle, as well as the number of automobiles on nearby and intersecting routes.
2. Assisting Self-Driving Cars in Making Better Decisions
Autonomous vehicles are not yet widely available in all locations, but people are enthusiastic about how they may transform society for the better. The GNN collects data on vector relationships like when an automobile approaches a junction or a pedestrian approaches a crossing, for example. That data might be used by the graph neural network to determine how other automobiles would react. When driving through traffic, the car may thus make more appropriate judgments. More precisely, the data is used by the autonomous vehicle to offer valuable context hints about the surrounding environment. Humans perform this naturally by depending on their past experiences. They can predict the chance of something occurring even if it does not occur in actual life.
However, an autonomous vehicle does not have such foundation to draw on when functioning. In this case, a “agent” was a car or a person in the autonomous automobile’s environment, and the surroundings were the “scene.” The GNN results were compared to those obtained by another form of neural network by the researchers. They discovered that when there were 50 agents per scene, the graph neural network performed 18% better.
3. Reducing Biased Social Media Suggestions
When someone accesses their social media profile, they will frequently receive recommendations for different pages or individuals to follow. In order for this to happen, graph neural networks function in the background. However, one acknowledged problem is that they frequently make those decisions based on sensitive traits such as a person’s gender or color. A new graph neural network was created to reduce these possible causes of bias.
It was designed to work differently by focusing on non-sensitive details about an individual. This model was trained using two sets of real-world data from social media users in Slovakia and basketball players from the National Basketball Association (NBA). The results revealed that the model could still categorize people properly even when it did not have access to as much data, which may cause bias. As a result, it demonstrates that GNNs may be utilized to reduce bias.
4. Image classification
Convolutional neural networks are the most widely used technology for image categorization (CNN). GNNs, on the other hand, are currently employed for image classification. When given a large training set of labeled classes, GNNs also produce appealing results. In the present scenario, efforts are centered around improving these models’ performance on zero-shot and few-shot learning challenges. The term “Zero shot learning” (ZSL) is an attempt to learn to recognize classes unbeknownst to the model during its training. The presence of a labeled training set of seen classes and information about how each unseen class is semantically connected to the seen ones are required for ZSL recognition. In ZSL image classification, one approach is to use structural information in the form of graphs.
As a result, GNN looks to be highly tempting in this regard. Knowledge graphs can give the knowledge required to direct the ZSL task. The type of information represented in the knowledge graph varies between techniques. These graphs may be based on similarities between photos or those of objects identified from images using object detection. The graphs may additionally include semantic information derived from word embeddings of the picture category labels. GNNs may then be trained on this structured data to assist the ZSL image classification-recognition process.
5. Predict Side-Effects due to Drug Interactions
Hundreds of thousands of seniors are hospitalized in the United States annually as a result of the bad side effects of one or more prescription medicines. Meanwhile, the number of elderly persons who are taking various medications at the same time is increasing. Given the proliferation of medications, it is impossible to evaluate each combination of drugs for interaction effects experimentally. Practically, medical professionals rely on training, a detailed knowledge of a patient’s medical history, and a thorough understanding of the literature on the drugs in use to assess the risk of severe side effects.
Classification and similarity algorithms have already been used for this problem, producing interaction scores. For a variety of reasons, these outcomes have been limited. They generate scalar values that indicate the risk of interaction without describing the nature of the interaction. These algorithms are confined to pairs of drugs. A Stanford team was able to create a model that can predict particular drug-drug interaction effects owing to the interaction of more than two pharmaceuticals by using a sort of GNN called a Graph Convolutional Network (GCN). This approach, which beats earlier methods in detecting such effects, may detect side effects that aren’t caused by the particular input drugs.
Limitations of GNNs
A paper titled, “How strong are GNNs” is a must read when it comes to discussing the limitations of GNN. It gives the reader a better understanding of the scenarios when it fails.
- According to the paper, one such example is the mean and max layers in convolutional networks using GNN. Because of the restricted and shallow learning, it affects the mean and max calculation algorithms. It reduces the network’s accuracy since it is unable to put values accurately enough.
- Another issue is the computational cost. Even if we adopt graphs as the data structure, the computational cost would rise with each weight update and iteration. As previously demonstrated, with each iteration, each node would have even more nodes in its information box, increasing the number of relations and weights to compute for each node.
Conclusion
Owing to their expressive capability and clear representation of graphical data, Graph Neural Networks are gaining prominence steadily. As a result, they have a wide range of applications in fields where graph structures may be extracted from data. GNN is still a relatively uncharted topic, and it will need time and application to better appreciate the overall drawbacks of them in various situations. However, it provides a foundation for a sector that can improve the accuracy of logistics and network-based systems.
References
About me
Hello everyone, I’m Himanshu Bhawnani, an AI/ML enthusiast and member of the AI wing at Geekhaven, IIIT Allahabad. I’m currently a Sophomore at college and am exploring the different areas in the world of Artificial Intelligence. Reach me at Linkedin.
