Traditional ML methods with Graphs
Imagine you’re at a buzzing party. Every person (node) here has a story, and understanding them individually helps us grasp the party’s vibe. Initially, in traditional ML, we were like artists, hand-picking features to understand each node (individual elements), link (relationships), or the entire graph. Let’s break these down:
Node-Level Features: Here, we focus on individual nodes. Think of analyzing a single person in our social network — what are their interests, how many connections do they have, or how often do they interact with others? This level is all about the characteristics of each node.
Link-Level Features: Now, we shift to the edges. This is like examining the strength of friendship between two people. Are they best friends, acquaintances, or just distant connections? Link-level features explore the nature and strength of relationships between nodes.
Graph-Level Features: Finally, we zoom out for a bird’s-eye view of the entire graph. It’s like gauging the overall vibe of our social network. Is it tightly-knit or loosely connected? Are there any more closely connected subgroups or small communities? Graph-level features capture the overarching structure and properties of the entire graph.
Node level
Being Influential: Importance-based features
Node Degree: Think of it as counting how many handshakes each person at our party has made. Simple, yet it doesn’t tell us about the significance of these connections.
Node Centrality: Now we’re getting somewhere! It’s like figuring out how many people someone knows and how influential these connections are. There are different flavors to this:
- Eigenvector Centrality: Here’s a fun thought — “You are the average of your five closest friends.” This method looks at the importance of your connections. It’s not about quantity but quality. Google’s PageRank and the Katz centrality are variations of the eigenvector centrality.
A*x = lambda * x
Here:
- A is the adjacency matrix of the graph, where A_ij is 1 if nodes i and j are connected and 0 otherwise.
- x is the eigenvector centrality vector. Each element of the vector provides the centrality score of a node in the network.
- lambda is the largest eigenvalue of the adjacency matrix A.
import networkx as nx
import matplotlib.pyplot as plt
G = nx.path_graph(4)
G.add_edges_from([(0,1),(1,2),(0,2),(2,3)])
centrality = nx.eigenvector_centrality(G)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color = 'skyblue', node_size = 2000, edge_color='k', linewidths=1, font_size=15)
for node, (x,y) in pos.items():
plt.text(x, y+0.1, s = f"{centrality[node]:.2f}", horizontalalignment = 'center')
plt.show()
- Betweenness Centrality: Have you ever met a Super Connector? Someone who seems to know everyone and is crucial in connecting different groups? That’s what this measures.
centrality = nx.betweenness_centrality(G)
Betweenness centrality is typically takes into account all nodes and usually normalized [0,1] so we can compare scores in different graphs.
- Closeness Centrality: This one is about being in the know. If someone has a short path to everyone else at the party, they’re considered central. Do they have direct access to others or rely on intermediaries to make connections?
centrality = nx.closeness_centrality(G)
Here:
- V is the set of nodes in G
- d(v,u) is the shortest path distance between node v and node u
- n−1 represents the total possible connections (excluding the node itself).
Peeking into the Local Scene: Structure-Based Features
- Clustering Coefficient: Let’s say you’re curious about how tight-knit a person’s friend group is. This measures the interconnectedness among someone’s friends.
nx.clustering(G)
# output: {0: 1.0, 1: 1.0, 2: 0.3333333333333333, 3: 0}- Graphlets and Graphlet Degree Vector (GDV): Now, imagine we’re not just looking at friendships (edges) and triangles of friends, but at more complex connections — like entire friend circles and their dynamics. Graphlets are these intricate patterns, and GDV is like a detailed map of a person’s social network down to the neighborhood level.
The Predictive Power of Node-Level Analysis
This microscopic focus on individual nodes allows us to uncover the characteristics and roles of these entities and their potential impact within the larger network. There are some of the transformative implications of node-level tasks:
Influencer Identification in Social Networks: We can pinpoint influential individuals in social networks by analyzing node centrality and importance. This insight is crucial for everything from viral marketing to the spread of information (or misinformation).
Protein Function Prediction in Bioinformatics: Scientists can predict protein functions by examining the structural and descriptive features of nodes in protein-interaction networks.
Network Resilience Analysis: Identifying key nodes (like major hubs in transportation or communication networks) can enhance security and develop contingency plans against failures or attacks.
Financial Market Analysis: In economic networks, node-level analysis can reveal key players or institutions, their roles, and their potential impact on market dynamics. This information is invaluable for risk assessment and strategic planning in financial sectors.
Customized Recommendations: Understanding individual preferences and behaviors (nodes) in recommendation systems leads to more accurate and personalized suggestions, much like Amazon’s product recommendations.
Link level
The Art of Link Prediction: Building Bridges in Data
Get Aizhan Smith’s stories in your inbox
Join Medium for free to get updates from this writer.
Link prediction is akin to whether two strangers at a party will become friends or business partners. In graphs, this involves estimating whether a link (or edge) should exist between two nodes. It’s crucial in various applications, from recommending new friends on social media to identifying potential protein interactions in biology.
Understanding Link Prediction Approaches:
- Links Missing at Random: This method is ideal for static networks, like protein-protein interactions. Here, we intentionally remove some links and then try to predict them. It’s like guessing which people at a party know each other but haven’t interacted yet.
- Links Appearing Over Time: This approach is perfect for dynamic, evolving networks like social or citation networks. It tracks how relationships develop over time.
When developing link-level features, we consider two main types:
- Distance-Based Features: Like measuring the shortest path between two nodes. While it’s useful, this method doesn’t capture the strength of the relationship, such as the degree of neighborhood overlap.
- Neighborhood overlap.
Local Neighborhood Overlap:
This is about understanding the strength of connections. How many mutual acquaintances do two people (nodes) share? It’s the count of shared neighboring nodes between two nodes.
Common Neighbors: This is based on the idea that if two people have many mutual friends, they’re more likely to know each other. In graph terms, the more common neighbors two nodes have, the more likely they are to be connected.
Jaccard’s Coefficient: This takes the common neighbors approach a step further. It’s not just about how many mutual friends two people have but also how significant this number is compared to the total number of distinct friends they have collectively. Mathematically, it’s the size of the intersection of the neighbors of two nodes divided by the size of their union.
Adamic/Adar Index: Similar to Jaccard’s, but it gives more weight to less-connected mutual friends based on the idea that shared connections with less popular individuals are more significant.
Global neighborhood overlap:
- Limitations of the local neighborhood overlap methods yield a score of zero if two nodes don’t share any common neighbors, yet they might still connect in the future. Global Neighborhood Overlap resolve the limitation by considering the entire graph.
Katz Index: This method counts the number of paths of all lengths between two nodes, summarizing the overall connectivity. Unlike simpler measures that might only consider direct connections (such as common neighbors), the Katz Index takes into account the total number of paths between two nodes and gives more weight to shorter paths. This approach acknowledges that connections can be indirect and still significant.
Predictive Power: The Impact of Link-Level Analysis
Understanding and predicting the connections between nodes is not just academically intriguing; it has practical implications:
Social Network Analysis: It helps predict future connections, understand community formation, and even identify influential groups or individuals.
Biological Networks: In bioinformatics, link prediction can hint at undiscovered biological pathways or protein interactions.
Recommendation Systems: It’s used in e-commerce and streaming services to suggest products, movies, or songs based on user connectivity patterns.
Fraud Detection: In financial networks, analyzing the links can help identify unusual patterns indicative of fraudulent activities.
Zooming Out to Graph Embeddings: A Panoramic View
Alright, friends, let’s step back for a moment. After getting to know everyone at our graph-themed party, it’s time to capture the whole scene. Imagine graph embeddings as taking a drone shot of the entire party. It transforms the bustling chatter and myriad interactions into a neat, numerical snapshot. It’s like turning a vibrant scene into a crystal-clear photograph that tells a thousand stories.
Crafting the Perfect Graph Snapshot
When it comes to traditional ML methods for graph-level predictions, think of it as a bit like photography. Instead of focusing on individual features, we use kernel methods, a bit like choosing the right lens to capture the essence of our graph party.
- Kernel Methods: These are like our camera settings, designed to measure the similarity between different graphs. Imagine each graph as a unique party scene; the kernel is our way of comparing these scenes. Once the kernel is defined, an off-the-shelf ML model, such as kernel SVM, can be used to make predictions.
- Graph Kernels: Now, this is where it gets exciting. Just like in photography, where we have different types of lenses, in graph theory, we have various graph kernels:
- Graphlet Kernel: This one counts different graphlets (small subgraphs) within a graph. It’s like capturing the people and the various small groups chatting away at our party.
Weisfeiler-Lehman Kernel: Here, we use the neighborhood structure to enrich our understanding of each node. WL kernel is like our detective’s secret weapon. It allows us to delve deep into the heart of a graph, uncovering layers of relationships and interactions that might not be immediately apparent. By iteratively refining our understanding of each node based on its neighborhood, the WL Kernel paints & color codes a detailed and comprehensive picture of the entire network.
- Random Walk Kernel: Imagine this as tracing the path guests take as they mingle through the party, giving us an insight into how they connect and move around.
Counting graphlets can be like photographing every guest at our party — a daunting task! It’s complex and can be quite resource-intensive. Plus, our comparisons might get skewed if our parties (graphs) are different sizes.
Now we are at the end of our fantastic party/article. In the previous article “The ABCs of Graphs: A Beginner’s Handbook” we went through basics of the Graph Theory. In the following article, we will finally dive into the fascinating world of Graph Neural Networks. Meanwhile, remember that each connection tells a story, and every node holds a clue to a larger mystery. Ultimately, it’s all about connecting the dots to reveal the bigger picture.
