Graph Representation Learning

From Graph ML to Temporal GNNs

University of Turin

CENTAI Institute S.p.A.


Outline

1️⃣ Introduction to Deep Learning

2️⃣ Graph Representation Learning

Introduction to Deep Learning

  1. Introduction to Deep Learning

Introduction to Deep Learning

  1. Introduction to Deep Learning:

    1.1 Problem Setting

    1.2 The “Deep Learning” Solution

    1.3 Gradient Descent

    1.4 Deep Learning on Graphs

Problem Setting #1

  • Usual problem in Mathematics/Physics: given a “setting”, compute a quantity/functional form;
  • Ex1: Given hydrogen atom, compute energy levels;
  • Ex2: Given two points on a curved surface, find the equation for the shortest path;
  • In all cases, a more or less intuitive but explicit sequence of operations allows for a “proof”;
  • But what if a problem does not admit a proof? E.g. :

    • The intuition required surpasses human capability;

    • The problem is not completely specified.

Problem Setting #2

EXAMPLE: Dog vs Cat classification

Other Tasks: Text Classification, Image Segmentation, Speech to Text, Scientific Machine Learning, Law Discovery, Anti Money Laundering…

Problem Setting #3

What we have:

  • A set of images (\(n \times n\) arrays), whose labels we know: \[\mathcal{D} = \left\{ (X_1, "dog"), (X_2, "cat"), ..., (X_n, "dog") \right\}\]
  • A set of images (\(n \times n\) arrays), whose label we’d like to correctly predict: \[\mathcal{D'} = \left\{ X_{1'}, X_{2'}, ..., X_{n'} \right\}\]

What we want:

  • A function \(f^*\) that maps images to their correct label, both in train and test sets.

Similarly for the other tasks.

These problems are clearly very complicated and underspecified.

The “Deep Learning” Solution

One fits them all:

Write a function family \(f_{\vec{\theta}}\) “flexible enough” to include the target function \(f^*\), then find \(\vec{\theta}^*\) s.t. \(f_{\vec{\theta}^*} \approx f^*\)

  • In our case, we’d look for a \(f_{\vec{\theta}}(X_i) \in \{"dog", "cat"\}\) such that mappings are correct;

  • Very expressive functions: Neural Networks \(f_{\vec{\theta}} = \sigma (W_0 \sigma(W_1 \sigma(...(\sigma(W_n X)))))\);

  • Parameters \(\vec{\theta} = (W_0, ..., W_n)\) iteratively updated via Gradient Descent.

Gradient Descent

  • Choose differentiable point-wise “loss” e.g. (“dog”/“cat” \(\iff y_i = 1/0\)):

\[\mathcal{l}(y_i, f_{\vec{\theta}}(X_i)) = P(y_i | X_i ; f_{\vec{\theta}}(X_i) ) = f_{\vec{\theta}}(X_i)^{y_i} (1-f_{\vec{\theta}}(X_i))^{1-y_i}\]

  • Define dataset-wise loss:

\[\mathcal{L}(D, f_{\vec{\theta}}) = - ln \left( \prod\limits_{i = 1}^n \mathcal{l}(y_i, f_{\vec{\theta}}(X_i)) \right)\]

  • Iteratively update parameters:

\[\vec{\theta} \leftarrow \vec{\theta} - \nabla_{\vec{\theta}} \mathcal{L}(D, f_{\vec{\theta}})\]

Until convergence.

Deep Learning on Graphs

Given a Graph:

Possible Tasks:

  • Node Classification;

  • Link Prediction/Classification;

  • Graph Classification;

  • Subgraph Matching;

  • …

Q: What “functional family” \(f_{\vec{\theta}}\) do we use for Deep Learning on (Temporal) Graphs?

Graph Representation Learning

  1. Graph Machine Learning

  2. Graph Deep Learning

  3. Temporal Graph Deep Learning

Graph Representation Learning

  1. Graph Machine Learning:

    1.1 Early Models

    1.2 Weisfeiler-Leman Kernel

2. Graph Deep Learning

2. Temporal Graph Neural Networks

Early Models

  • Before Deep Learning, features were human-engineered (Machine Learning);
  • Early works can be organized in node/edge/graph-level features;

Node-level:

  • Features: Degree, Eigenvector, Betweeness, Closeness centralities & Clustering Coefficient (CC)/Graphlet Degree Vector (GDV)

  • RW-based: PageRank, DeepWalk, Node2Vec (not inductive!);

Edge-level: Local/Gobal Neighborhood overlap (Katz Index)

Graph-level: (Causal) Anonymous Walks, Graphlet Kernel, Weisfeiler-Leman Kernel.

Weisfeiler-Leman Kernel #1

Def.(Graph Isomorphism) : Two graphs \((V_1, E_1)\) and \((V_2, E_2)\) are isomorphic \(\iff\) \[\exists \text{ bijection }f: V_1 \rightarrow V_2 | (u,v) \in E_1 \implies (f(u), f(v)) \in E_2\]

Obs. : Determining \(f\) is extremely expensive \(\implies\) need for approximate algorithms \(\implies\) WL-kernel

Weisfeiler-Leman Kernel #2

WL-Kernel:

  1. Assign initial color \(c^{(0)}_v\) to each node \(v\);

  2. Iteratively refine colors via: \[c^{(k+1)}_v = HASH\left(c^{(k)}_v, \{ c^{(k)_u | u \in N(v)} \} \right)\]

  3. Terminate when colors stabilize (#nodes iterations maximum);

  4. Assign to each graph the empirical color distribution (histogram)

Weisfeiler-Leman Kernel #3

Obs. WL-Kernel cannot distinguish all non-isomorphic graphs e.g.:

And computes same color for different nodes:

Obs. : GNNs will be differentiable versions of \(HASH\) \(\implies\) less expressive.

Graph Representation Learning

Graph Machine Learning

  1. Graph Deep Learning

    2.1 Historical Derivation of GNNs

    2.2 Message Passing Framework

    2.3 Expressivity of GNNs

3. Temporal Graph Deep Learning

Historical Derivation of GNNs #1

Disadvantages of previous methods:

  • Inherently transductive;
  • Do not incorporate node/edge/graph features;
  • Computed node/edge/graph features are task-independent;
  • Not End-to-End.

\(\implies\) Need for Graph Deep Learning i.e. GNNs!

Historical Derivation of GNNs #2

Historical derivation of GNNs:

  1. Simultaneous discretization of a Riemannian Manifold \(\mathcal{M}\) & Laplace-Beltrami operator yields a graph \(G\) and its laplacian \(L = D - A\)1
  1. \(\hat{L} = D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - \hat{A}\)’s eigenvectors \(U\) used to define the Graph Fourier Transform: \[\mathcal{F}(\vec{x}) = U^{T}\vec{x}\]
  1. \(\mathcal{F}\) used to define Graph Convolution:

\[\vec{g}_{\vec{\theta}} * \vec{x} = U \vec{g}_{\vec{\theta}} U^T \vec{x}\]

  1. Interpret \(\vec{g}_{\vec{\theta}}\) as function of \(\hat{L}\)’s eigenvalues \(\hat{\Lambda}\), and approximate using Chebishev’s polynomials: \[\vec{g}_{\vec{\theta}} \approx \sum\limits_{k = 0}^{K}\theta_k T_k(\hat{\Lambda})\]
  1. Truncate to first-order, group parameters, renormalize, apply non-linearity and generalize to matrices: \[Z \approx \text{ReLU}\left(\tilde{A}X\Theta \right)\] where \(\tilde{A} = D^{-\frac{1}{2}} (A + I) D^{-\frac{1}{2}}\)2

Obs. Alternative approach: MPNNs3

Message Passing Framework #1

INTUITION: We’d like to produce useful representations for each node also taking into account their neighbors (ref. CNNs).

Message Passing Framework #2

MPNN framework prescribes that a GNN is a stacking of layers of the form:

\[\vec{h}^{(k+1)}_v = \vec{\text{COMB}}_k\left(\vec{h}^{(k)}_v, \vec{\text{AGGR}}_k\left( \left\{ \vec{\text{MSG}}_k\left(\vec{h}^{(k)}_v, \vec{h}^{(k)}_u, e_{uv} \right) | u \in N(v) \right\} \right)\right)\]

Message Passing Framework #3

Kipf’s convolution recovered by:

\[\begin{cases} \vec{\text{COMB}}_t &= \text{ReLU}(\cdot) \text{ (no self-information)} \\ \vec{\text{AGGR}}_t &= \sum \\ \vec{\text{MSG}}_t\left(\vec{h}^{(t)}_v, \vec{h}^{(t)}_u, e_{uv} \right) &= \frac{W_t}{\sqrt{deg(u)}\sqrt{deg(v)}}\vec{h}^{(t)}_u \end{cases}\]

Obs. All architectures within this framework are permutation-invariant;

Other architectures are GAT, GraphSAGE, SGCN, etc1

GNN Expressivity #1

  • We may choose to quantify GNN “expressivity” by the number of (sub)graphs it may distinguish when no features are present;
  • In this case, GNNs are at most expressive as the WL-kernel by construction;
  • GNNs may match WL-kernel \(\iff \vec{\text{COMB}}_t \text{, } \vec{\text{AGGR}}_t\text{, } \vec{\text{MSG}}_t\) are all injective on their domains;

GNN Expressivity #2

  • By Kolmogorov-Arnold’s theorem1, every symmetric function can be represented as:

\[f(x_1,...,x_n) = \rho \left(\sum\limits_{i = 1}^{n} \phi(x_i) \right) \text{where $\rho \text{ and } \phi$ are injective nonlinearities}\]

  • Thus, by the Universal Approximation Theorem, the following architecture2 has a chance to match WL expressivity:

\[\vec{h}^{(k+1)}_v = \text{MLP}\left( (1+\epsilon) \vec{h}^{(k)}_v + \sum\limits_{u \in N(v)}\vec{h}^{(k)}_u \right)\]

  • More expressive GNNs may be obtained by mimicking k-WL kernel, or by extending the MPNN framework3.

Graph Representation Learning

1. Graph Representation Learning

2. Graph Deep Learning

  1. Temporal Graph Deep Learning:

    2.1 Framework

    2.2 ROLAND

    2.3 TGAT

Framework

Reviews: Longa et al. (2023), Gravina and Bacciu (2023), Gupta and Bedathur (2022)

ROLAND

  • A meta-model \(\text{GNN}^{(meta)}\), responsible for parameter initialization before fine tuning on each snapshot, is trained via Meta-Learning up to snapshot \(t\);
  • The \(\text{GNN}_{t+1}\) at snapshot \(t+1\) is initialized \(GNN \leftarrow \text{GNN}^{(meta)}\) and fine-tuned on snapshot \(t+1\) via:

\[H^{(t+1)}_{(k+1)} = GRU(H^{(t)}_{(k+1)}, \tilde{H}^{(t+1)}_{(k)})\]

So only current snaphsot and previous final embeddings are needed on GPU (live-update)

  • The meta-model is updated:

\[GNN^{(meta)} \leftarrow (1-\alpha)GNN^{(meta)} + \alpha \text{GNN}_{t+1}\]

And the cycle repeats.

TGAT

Time differences are represented via Bochner’s theorem (translational invariance can be proved):

\[\Phi(\Delta t) = \sqrt{\frac{1}{d}} [cos(\omega_1 \Delta t), sin(\omega_1 \Delta t),...,cos(\omega_d t), sin(\omega_d \Delta t)]\]

Given node \(v\), we define:

\[ Z^{(l-1)}(t) := [ \vec{h}_v^{(l-1)}(t) || \vec{x}_{(v,v)}|| \Phi(0), \vec{h}_{u_1}^{(l-1)}(t_1) || \vec{x}_{(u_1,v)} || \Phi(t-t_1),... \\ ,\vec{h}_{u_1}^{(l-1)}(t_N) || \vec{x}_{(u_N,v)} || \Phi(t-t_N)]^t \\ \vec{q}^{(l-1)}_v(t)^t := \vec{Z}^{(l-1)}_v(t) W_Q := Z^{(l-1)}(t)[0,:]W_Q \\ K^{(l-1)}(t) := Z^{(l-1)}(t)[1:N,:]W_K \\ V^{(l-1)}(t) := Z^{(l-1)}(t)[1:N,:]W_V \\ \]

  • A convolutional self-attention1 layer is defined:

\[\tilde{\vec{h}}_v^{(l)}(t) = \sum\limits_{u \in N(v;t)} \underbrace{softmax \left(\frac{\vec{q}^{(l-1)}_v(t)^t \vec{K}^{(l-1)}_u(t)}{\sqrt{d}}; N(v;t)\right) \vec{V}_u^{(l-1)}(t)}_{\tilde{\vec{h}}_{uv}^{(l)}(t) }\]

  • Final embedding for \(v\) is:

\[\vec{h}_v^{(l)}(t) = \text{ReLU}([\tilde{\vec{h}}_v^{(l)}(t) || \vec{h}_v^{(0)}(t)] W_0^{(l)} + \vec{b}_0^{(l)})W_1^{(l)} + \vec{b}_1^{(l)}\]

Thanks 🙏

References

Aubry, Erwann. 2013. “Approximation of the Spectrum of a Manifold by Discretization.” arXiv. https://doi.org/10.48550/ARXIV.1301.3663.
Burago, Dmitri, Sergei Ivanov, and Yaroslav Kurylev. 2014. “A Graph Discretization of the Laplace–Beltrami Operator.” Journal of Spectral Theory 4 (4): 675–714. https://doi.org/10.4171/jst/83.
Chanpuriya, Sudhanshu, and Cameron N Musco. 2022. “Simplified Graph Convolution with Heterophily.” In Advances in Neural Information Processing Systems, edited by Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho. https://openreview.net/forum?id=jRrpiqxtrWm.
Du, Jian, Shanghang Zhang, Guanhang Wu, Jose M. F. Moura, and Soummya Kar. 2018. “Topology Adaptive Graph Convolutional Networks.” https://arxiv.org/abs/1710.10370.
García Trillos, Nicolás, Moritz Gerlach, Matthias Hein, and Dejan Slepčev. 2019. “Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace–Beltrami Operator.” Foundations of Computational Mathematics 20 (4): 827–87. https://doi.org/10.1007/s10208-019-09436-w.
Gilmer, Justin, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. “Neural Message Passing for Quantum Chemistry.” In Proceedings of the 34th International Conference on Machine Learning - Volume 70, 1263–72. ICML’17. Sydney, NSW, Australia: JMLR.org.
Gravina, Alessio, and Davide Bacciu. 2023. “Deep Learning for Dynamic Graphs: Models and Benchmarks.” https://arxiv.org/abs/2307.06104.
Gupta, Shubham, and Srikanta Bedathur. 2022. “A Survey on Temporal Graph Representation Learning and Generative Modeling.” https://arxiv.org/abs/2208.12126.
Hamilton, William L., Rex Ying, and Jure Leskovec. 2017. “Inductive Representation Learning on Large Graphs.” In, 1025–35. NIPS’17. Red Hook, NY, USA: Curran Associates Inc.
Hein, Matthias, Jean-Yves Audibert, and Ulrike von Luxburg. 2005. “From Graphs to Manifolds – Weak and Strong Pointwise Consistency of Graph Laplacians.” In Lecture Notes in Computer Science, 470–85. Springer Berlin Heidelberg. https://doi.org/10.1007/11503415_32.
Kipf, Thomas N., and Max Welling. 2017. “Semi-Supervised Classification with Graph Convolutional Networks.” https://arxiv.org/abs/1609.02907.
Longa, Antonio, Veronica Lachi, Gabriele Santin, Monica Bianchini, Bruno Lepri, Pietro Lio, Franco Scarselli, and Andrea Passerini. 2023. “Graph Neural Networks for Temporal Graphs: State of the Art, Open Challenges, and Opportunities.” https://arxiv.org/abs/2302.01018.
Lu, Jinpeng. 2020. “Graph Approximations to the Laplacian Spectra.” Journal of Topology and Analysis 14 (01): 111–45. https://doi.org/10.1142/s1793525320500442.
Michel, Gaspard, Giannis Nikolentzos, Johannes Lutzeyer, and Michalis Vazirgiannis. 2023. “Path Neural Networks: Expressive and Accurate Graph Neural Networks.” https://arxiv.org/abs/2306.05955.
Morris, Christopher, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2021. “Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks.” https://arxiv.org/abs/1810.02244.
Nahmias, David. 2017. “An Exposition of Spectral Graph Theory.” https://dnahmias.com/docs/harmonicfinalpaper.pdf.
Vaswani, Ashish, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. “Attention Is All You Need.” In Advances in Neural Information Processing Systems, edited by I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett. Vol. 30. Curran Associates, Inc. https://proceedings.neurips.cc/paper_files/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf.
Veličković, Petar, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. “Graph Attention Networks.” https://arxiv.org/abs/1710.10903.
Wagstaff, Edward, Fabian B. Fuchs, Martin Engelcke, Michael A. Osborne, and Ingmar Posner. 2022. “Universal Approximation of Functions on Sets.” J. Mach. Learn. Res. 23 (1).
Xu, Keyulu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. “How Powerful Are Graph Neural Networks?” In International Conference on Learning Representations. https://openreview.net/forum?id=ryGs6iA5Km.
Zaheer, Manzil, Satwik Kottur, Siamak Ravanbhakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexander J Smola. 2017. “Deep Sets.” In Proceedings of the 31st International Conference on Neural Information Processing Systems, 3394–404. NIPS’17. Red Hook, NY, USA: Curran Associates Inc.