Summary of "Khipu 2021 Event Series in AI: Graph Neural Networks"

The Khipu 2021 Event Series in AI: Graph Neural Networks featured a comprehensive tutorial and research talks on Graph Neural Networks (GNNs), covering foundational theory, architectural principles, and practical applications in various scientific domains.

Key Technological Concepts and Analysis

1. Foundations and Theory of Graph Neural Networks (Joan Bruna)

Motivation: Deep learning excels in high-dimensional data but struggles with scalability and interpretability. GNNs extend convolutional neural networks (CNNs) to non-Euclidean domains (graphs, manifolds) by leveraging geometric deep learning principles.
Geometric Deep Learning Blueprint:
- Defines a framework to generalize convolutional operations from grids (images) to arbitrary graphs and manifolds.
- Uses families of linear operators (e.g., diffusion operators, graph Laplacians) that respect domain symmetries (permutations, rotations).
- Combines these operators with point-wise nonlinearities to build stable, equivariant representations.
Stability and Invariance:
- GNNs are permutation equivariant, meaning relabeling graph nodes leads to corresponding relabeling of outputs.
- Stability to graph perturbations (quasi-symmetries) is crucial for robustness.
- Integral Lipschitz filters are introduced to balance stability and discriminability, but they limit the ability to discriminate high-frequency components.
- GNNs overcome this limitation by using nonlinearities that demodulate high-frequency signals into low-frequency components, enabling both stability and discriminability.
Applications Highlighted:
- Particle physics (Large Hadron Collider jet reconstruction)
- Neutrino detection (IceCube detector)
- Fluid dynamics and glassy systems simulations
- Protein folding and drug design (notably DeepMind’s AlphaFold uses rotationally invariant GNNs)
- Algorithmic reasoning, causal inference, and dynamic/evolving graphs (e.g., social networks)
Open Challenges:
- Limitations of message-passing architectures in expressivity.
- Need for multi-scale and hierarchical GNNs for scientific computing.

2. Graph Neural Networks: Why and How (Alejandro Rivero)

Why Machine Learning on Graphs?
- Graphs model both virtual data structures (e.g., word adjacency in texts, recommendation systems) and physical infrastructures (e.g., drone swarms, wireless networks).
How to Build GNNs?
- Generalize convolutions from time and images (line and grid graphs) to arbitrary graphs by defining convolutions as polynomials of adjacency matrices.
- GNN layers are compositions of graph convolutions (graph filters) and point-wise nonlinearities.
- GNNs are scalable due to exploiting signal structure encoded by the graph, unlike fully connected networks which do not scale well.
Graph Frequency Representation
- Graph filters can be analyzed in the graph Fourier domain by decomposing the graph shift operator.
- This reveals that graph filters act as point-wise multiplications in the frequency domain, simplifying analysis.
Permutation Equivalence
- GNNs and graph filters are permutation equivariant, ensuring consistent outputs regardless of node labeling.
- This property allows learning from symmetries and generalizing to unseen graph parts.
Stability to Perturbations
- Introduces the concept of relative (multiplicative) perturbations of graphs.
- Stability bounds depend on integral Lipschitz constants of filters and perturbation magnitude.
- Trade-off between stability and discriminability: stable filters lose ability to distinguish high-frequency signals.
Advantage of GNNs over Graph Filters
- Nonlinearities in GNNs enable demodulation of high frequencies, allowing stable discrimination of complex features.
Summary:
- GNNs extend CNNs to graphs, leveraging permutation equivariance and stability.
- They outperform fully connected networks and simple graph filters.
- Theoretical insights explain why GNNs work well and provide a blueprint for designing architectures.

3. Research on Graph Representations and Change Detection (Paola Bermolen)

Problem Setting
- Focus on modeling dynamic wireless networks as sequences of graphs.
- Use random dot product graph (RDPG) models where edge probabilities are inner products of latent node embeddings.
Latent Position Estimation
- Spectral embedding techniques estimate latent node vectors from adjacency matrices.
- Example: Bipartisan US Senate voting network, where embeddings reveal political party structure.
Online Change Point Detection
- Goal: Detect changes in the underlying graph model in real-time (online) using sequential hypothesis testing.
- Method: Estimate latent positions from training data, then monitor deviations in new graph observations.
- Statistical tests based on differences in adjacency matrices and their embeddings detect significant model shifts.
Scalability and Optimization
- Propose