Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Carleton College

Graph Representation Learning is the application of machine learning techniques on graph-structured data. A few examples of growing topics in Graph Representation Learning include techniques for deep graph embeddings, Graph Neural Networks (GNNs), and applications to knowledge graphs.

Graph Representation Learning

In the dominant machine learning approach, rather than designing explicit step-by-step rules to map inputs to outputs, practitioners define a flexible program whose behavior is governed by a set of adjustable parameters. By presenting this program with a large dataset of examples and labels, a learning algorithm determines the optimal parameter values that maximize the model's performance on the desired task.

Machine Learning Approach

Node embeddings is a way of graph representation. The goal of node embeddings is to map the nodes in the graph into a low-dimensional vector space, where the relations of the nodes in graph can be reflected by the geometric relations in the embedding space. Compared with hand-engineered features, node embeddings are more flexible and they are learned through learning processes.

Node Embeddings

Graph Representation Learning by William Hamilton

Neighborhood overlap metrics between pairs of nodes are useful in helping us quantify the extent to which a pair of nodes are related, which is import in tasks such as predicting the existence of an edge between two nodes.

Neighborhood Overlap Detection

By examining the eigenvectors of graph Laplacian, the nodes can be clustered into K groups. The steps are as follows:
1. Find the smallest K eigenvectors of the graph Laplacian (excluding the smallest one).
2. Let U be the matrix whose columns are the K eigenvectors, then represent each node $v$ as its corresponding row $z_v$ in U.
3. Run K-means clustering on the embeddings $z_v, \forall v\in V$

K-Clustering of Graph Nodes

Graph is a general data structure  to represent complex data in complex systems. 
It is used to describe and analyze objects/entities with relations/interactions.
A graph is a collection of nodes( objects ) and edges (interactions)


Graph Data structure

Machine learning is inherently a problem-driven discipline, where we seek to build models that can learn from data in order to solve particular tasks. Machine learning on graphs is no different, except the usual categories of supervised and unsupervised are not necessarily the most informative or useful when it comes to graphs.

Machine Learning on Graphs

Traditional approaches to classification using graph data follow the standard machine learning paradigm, where we begin by extracting some statistics or features — based on heuristic functions or domain knowledge — and then use these features as input to a standard machine learning classifier.

Graph Statistics and Kernel Methods

The neighborhood aggregation operation is fundamentally a set function. Given a set of neighbor embeddings $\{h_{v}, \forall v \in N(u)\}$, there is no natural ordering of a nodes’ neighbors, and any aggregation function we define must thus be permutation invariant.

Generalized neighborhood aggregation: Set aggregators

GNNs are a general framework for defining deep neural networks on graph data. The goal of GNNs is to generate representations of nodes that actually depend on the structure of the graph, as well as any feature information available.

Graph Neural Networks (GNNs)

One prominent example of alternative theoretical motivations for the GNN framework is the motivation of GNNs based on connections to variational inference in probabilistic graphical models (PGMs).

In this probabilistic perspective, we view the embeddings $z_{u}, \forall u \in V$ for
each node as latent variables that we attempt to infer. Assume that we observe the graph structure and the input node features X, and the goal is to infer the underlying latent variables hat can explain this observed data. Then the message passing operation that underlies GNNs can be viewed as a neural network analogue of certain message passing algorithms that are commonly used for variational inference to infer distributions over latent variables.

Probabilistic Graphical Models (PGM)

Many recent generative models leverage alternative generative frameworks, and among them generative adversarial networks (GANs) are one of the most popular. 

The basic idea behind a general GAN-based generative models is: first define a trainable network $g_{\theta}: R^{d}\rightarrow \chi$. This generator network is trained to generate realistic data samples $\tilde{x} \in \chi$ by taking a random seed $z \in R^{d}$ as input. 

At the same time, define a discriminator network $d_{\phi}: \chi \rightarrow [0,1]$. The
goal of it is to distinguish between real data samples $x \in \chi$ and samples generated by the generator $\tilde{x} \in \chi$.

Adversarial Approaches: Generative adversarial networks (GANs)

Deep generative models aim to design models that can observe a set of graphs {G1, ..., Gn} and learn to generate graphs with similar characteristics as this training set. These approaches avoid hand-coding particular properties—such as community structure or degree distributions.

Deep Generative Models

There are two concrete instantiations of the autoregressive generation
idea: in the first model called GraphRNN, we model autoregressive dependencies using a recurrent neural network (RNN); In the second approach called graph recurrent attention network (GRAN), we generate graphs by using a GNN to condition on the adjacency matrix that has been generated so far.

Recurrent Models for Graph Generation

The goal of graph generation is to build models that can generate realistic graph structures. In some ways, we can view this graph generation problem as the mirror image of the graph embedding problem. There are three common traditional graph generation approaches:
- Erdös-Rényi (ER) model
- Stochastic Block Model (SBM)
- Preferential Attachment (PA) model

Traditional Graph Generation

There are many important sub-area in graph representation learning. However, the author believe that there’re two key areas that have the potential of pushing fundamentals of graph representation learning forward:

1)	Latent graph inference

2)	Breaking the bottleneck of message passing


Key Area For Future Graph Model Development

- Printed circuit boards
- Communication hardware, interfaces and storage
- Integrated circuits
- Very large scale integration design
- Power and energy
- Electronic design automation
- Hardware validation
- Hardware test
- Robustness
- Emerging technologies

Hardware in ACM Computing Classification

- Architectures
- Embedded and cyber-physical systems
- Real-time systems
- Dependable and fault-tolerant systems and networks

Computer systems organization in ACM Computing Classification

- Network architectures
- Network protocols
- Network components
- Network algorithms
- Network performance evaluation
- Network properties
- Network services
- Network types

Networks in ACM Computing Classification

- Software organization and properties
- Software notations and tools
- Software creation and management

Software and its engineering in ACM Computing Classification

- Models of computation
- Formal languages and automata theory
- Computational complexity and cryptography
- Logic
- Design and analysis of algorithms
- Randomness, geometry and discrete structures
- Theory and algorithms for application domains
- Semantics and reasoning

Theory of computation in ACM Computing Classification

- Discrete mathematics
- Probability and statistics
- Mathematical software
- Information theory
- Mathematical analysis
- Continuous mathematics

Mathematics of computing in ACM Computing Classification

- Data management systems
- Information storage systems
- Information systems applications
- World Wide Web
- Information retrieval

Information systems in ACM Computing Classification

- Cryptography
- Formal methods and theory of security
- Security services
- Intrusion/anomaly detection and malware mitigation
- Security in hardware
- Systems security
- Network security
- Database and storage security
- Software and application security
- Human and societal aspects of security and privacy

Security and privacy in ACM Computing Classification

- Human computer interaction (HCI)
- Interaction design
- Collaborative and social computing
- Ubiquitous and mobile computing
- Data Visualization
- Accessibility

Human-centered computing in ACM Computing Classification

- Electronic commerce
- Enterprise computing
- Physical sciences and engineering
- Life and medical sciences
- Law, social and behavioral sciences
- Computer forensics
- Arts and humanities
- Computers in other domains
- Operations research
- Learning Science
- Document management and text processing

Applied computing in ACM Computing Classification

- Professional topics
- Computing / technology policy
- User characteristics

Social and professional topics in ACM Computing Classification

The marriage of Statistics, Computer Science, and Domin knowledge built Data Science.

Data science is interdisciplinary

The list of helpful broad references about ML is categorized as follows:
1- ML books
2- ML online courses
3- ML research papers

Machine Learning references

There are several categories for ML algorithms, including:
 - Supervised Learning
 - Semi-supervised Learning
 - Unsupervised Learning
 - Reinforcement Learning
 - Feature Learning (Representation Learning)

The types of machine learning algorithms differ in their approach, the type of data they input and output, and the type of task or problem that they are intended to solve.


Machine Learning Categories

Python is widely used for machine learning various reasons.
- It is relatively easy to learn.
- The data handling capacity is better than most other languages.
- The community is large, as well as support for other platforms.
- Its’s Open Source.
- It supports developers with frameworks and libraries such as TensorFlow


Machine Learning with Python


here is a cycle for doing machine learning evaluation and selection. The first is representation. You extract and select object features. The second is train. You train the model by fitting the estimator to the data. Afterwards, you evaluate the model to look at its accuracy, recall and all the relevant metrics. Finally you refine the model and feature and go back to step one.

Represent/Train/Evaluate/Refine Cycle

1.Identify diseases and diagnosis
2.Drug discovery and manufacturing
3.Medical imaging diagnosis
4.Personalized medicine
5.Machine learning-based behavioral modification
6.Smart health records
7.Clinical trial and research
8.Crowdsourced data collection
9.Better Radiotherapy
10.Outbreak prediction

Machine learning and applications in healthcare

Almost all deep learning algorithms can be described as specific instances of a simple recipe: combine a data set specification, a cost function, an optimization process, and a model.


Building a Machine Learning Algorithm

A good machine learning practitioner needs to know how to choose an algorithm for a particular application and how to monitor and respond to feed back obtained from experiments in order to improve a machine learning system. We recommend the following practical design process:
- Determine your goals—what error metric to use, and your target value forthis error metric. These goals and error metrics should be driven by the problem that the application is intended to solve.
- Establish a working end-to-end pipeline as soon as possible, including the estimation of the appropriate performance metrics.
- Instrument the system well to determine bottlenecks in performance. Diagnose which components are performing worse than expected and whether poor performance is due to overﬁtting, underﬁtting, or a defect in the data or software.
- Repeatedly make incremental changes such as gathering new data, adjusting hyperparameters, or changing algorithms, based on speciﬁc ﬁndings from your instrumentation.

Practical Methodology

For example, the linear regression algorithm combines a dataset consisting of X and y, the cost function


The cost function typically includes at least one term that causes the learningprocess to perform statistical estimation. The most common cost function is the negative log-likelihood, so that minimizing the cost function causes maximum likelihood estimation. 

In simple terms, the cost function is used to evaluate whether the parameter value W is reasonable.

Cost Function

Active learning (AL) attempts to maximize a model’s performance gain while annotating the fewest samples possible.

Active Learning

In machine learning, parameters can be intuitively understood as adjustable 'knobs' that dictate the behavior of a flexible program. By manipulating these parameters, practitioners can change how the program maps inputs to outputs. Once these parameter values are determined and fixed, the resulting program is referred to as a model.

Machine Learning Model Parameter

A learning algorithm is a 'meta-program' that utilizes a dataset to determine the optimal parameter values for a machine learning model. Instead of explicitly coding the model's behavior, the learning algorithm automatically discovers the best configuration of parameters to improve the model's performance on a specific task.

Learn Before

Related