Unit-2 - Machine Learning with Graphs
Introduction: Machine Learning for Graphs
A graph is a way to represent relationships between things.
• Nodes (Vertices): The “things” or entities.
• Edges: The connections or relationships between those entities.
Example:
• In a social network, people are nodes, and friendships are edges.
• In a transport network, cities are nodes, and roads are edges.
Graphs can have:
• Attributes: e.g., a node (person) has age or interests; an edge (friendship) has strength
or frequency of communication.
• Types: directed/undirected, weighted/unweighted, dynamic/static.
Why Machine Learning for Graphs?
Traditional ML works well with tabular data (rows & columns) or images (grid pixels).
But graphs are irregular:
• Nodes have different numbers of neighbors.
• No fixed spatial order.
We need special techniques to:
• Predict properties of nodes, edges, or entire graphs.
Applications of Machine Learning on Graphs
• Social networks: Friend recommendation (Facebook, LinkedIn).
• Healthcare: Protein interaction networks for drug discovery.
• Transportation: Predict traffic flow using road networks.
• E-commerce: Product recommendation graphs.
• Cybersecurity: Detect fraudulent connections.
Traditional Methods for ML on Graphs
Before Graph Neural Networks (GNNs) and deep learning, researchers used classical machine
learning and graph theory techniques to work with graphs.
These methods relied on:
• Handcrafted features (manually designed metrics),
• Mathematical similarity measures, and
• Classical ML models like SVMs or decision trees.
Goal: Convert the graph’s structure into numerical features that standard ML models can
understand.
Common Features:
• Degree: Number of connections a node has.
• Clustering Coefficient: How tightly a node’s neighbors are connected.
• Centrality Measures:
o Betweenness centrality: How often a node lies on shortest paths.
o PageRank: Importance of a node in the network.
• Graph-level stats: Diameter, density, average path length.
For Undirected Graph
Node Embeddings
A node embedding is a way to represent each node of a graph as a numeric vector (like a list
of numbers).
Why?
Machine learning models work best with numbers. Graphs are not regular grids or tables. So,
we encode each node’s role and connections into a fixed-size vector.
Why Do We Need Node Embeddings?
Graphs can be huge and complex:
• Billions of nodes (like social networks).
• Relationships are irregular.
Node embeddings let us:
• Apply standard ML models (logistic regression, SVM, deep nets).
• Measure similarity between nodes using vector math (e.g., cosine similarity).
Link Analysis: PageRank, Label Propagation for Node Classification
Link Analysis: PageRank, Label Propagation for Node Classification
Link analysis is about understanding the importance or labels of nodes by looking at
connections (links/edges) between them.
Key idea:
A node is important or belongs to a group depending on how it is connected to others.
Two classic techniques:
1. PageRank – measures importance of nodes.
2. Label Propagation – spreads known labels through the network.
PageRank
PageRank was created by Google to rank web pages.
A page is important if:
• Many other important pages link to it.
• Not just the number of links, but also the quality of those links.
Think of it like academic citations:
• A paper is influential if it is cited by other influential papers.
Label Propagation (for Node Classification)
Sometimes you know the labels of a few nodes (e.g., which users like sports).
You want to predict the labels of the rest, assuming:
• Connected nodes tend to share the same label.
Graph Neural Networks: Design Space, Applications of Graph Neural Networks,
Knowledge Graph Embeddings, Reasoning over Knowledge Graphs, Frequent Subgraph
Mining with GNNs