Machine Learning On Graphs

Introduction to Machine Learning on Graphs
- Fundamentals of graph theory: basic definitions (nodes, edges, degree, paths, connectivity, centrality), graph types (directed, weighted, multigraphs, bipartite, etc.), computational representations (adjacency lists, matrices).
- Standard terminology and notation used in the literature and implementations.
- Motivations and context: why graphs are a natural data structure for machine learning.
- Practical applications: examples from biology (protein interaction networks), social sciences (social networks), finance (fraud detection), industry (predictive maintenance), knowledge representation.
Machine Learning on Graphs without Feature Learning
- Main tasks:
—- Node classification based on structural properties.
—- Link prediction based on graph topology.
- Topology-based methods:
—- Structural similarities (Common Neighbors, Jaccard, Adamic-Adar).
—- Random walks and PageRank for ranking and inference.
- Graph Kernels and Graph SVM:
—- Graph and substructure kernels (walk-based, subtree-based, graphlet-based).
—- Use of kernels in SVM classifiers.
- Graph clustering techniques:
—- Metis (cut minimization-based partitioning).
—- Leiden and Infomap (community detection).
- Case studies: classification and clustering on real-world datasets (e.g., citation networks, social graphs).

Graph Representation Learning with Shallow Networks
- Motivations for graph embedding: reducing structural complexity, mapping nodes/edges/graphs to vector spaces.
- Shallow methods (non end-to-end learning):
—- DeepWalk: random walks + Skip-gram model.
—- node2vec: extension of DeepWalk with biased exploration (BFS/DFS).
—- LINE: first- and second-order proximity preservation.
- Evaluation of embeddings:
—- Metrics for link prediction, node classification, and clustering.
—- Benchmarking on standard datasets.
Graph Representation Learning with Deep Feature Learning
- Introduction to Graph Neural Networks (GNNs)
— Core concepts: message passing, aggregation, update.
— Differences between GNNs and traditional MLPs/CNNs.
- Main architectures:
—- Graph Convolutional Networks (GCNs): spatial convolution on graphs.
—- Graph Attention Networks (GATs): attention mechanisms for weighted aggregation.
—- GraphSAGE: neighborhood sampling and differentiable aggregation.
- Advanced training aspects:
—- Mini-batching and sampling techniques.
—- Over-smoothing and regularization.
—- Negative sampling for efficient training.
- Implementation and evaluation:
—- Frameworks (PyTorch Geometric, DGL).
—- Training and validation pipelines.
Graph Representation Learning for Heterogeneous Networks and Knowledge Graphs
- Definition of heterogeneous networks: graphs with multiple node and edge types.
- Knowledge graphs: graphs with typed relations and explicit semantics (subject-predicate-object triples).
- Embedding methods for heterogeneous networks:
—- metapath2vec: meta-path guided random walks.
—- HERec: meta-path decomposition + personalized embeddings.
—- R-GCN: extension of GCNs for relational data
—- HAN: hierarchical attention over meta-paths.
- Knowledge graph embedding methods:
—- Translational methods: TransE, TransH.
—- Factorization-based methods: DistMult, ComplEx.
- Application:
—- Knowledge-graph-based recommendation systems.
Graph Representation Learning for Temporal Networks
- Introduction to temporal graphs:
— Definitions: graphs evolving over time (events, dynamic nodes/edges).
— Classification: snapshot-based (discrete time) vs. event-based (continuous time).
- Methods for discrete-time temporal graphs:
—- Snapshot-based GCN variants.
—- Temporal random walks and adaptations of node2vec/DeepWalk.
- Methods for continuous-time dynamic graphs:
—- TGN (Temporal Graph Networks): memory-based node/event representation.
—- TGAT (Temporal Graph Attention Networks): temporal attention mechanisms.
- Case studies:
—- Social network evolution.
—- Event prediction in communication or financial networks.