Introduction toPersistent Homology for
Graph Analysis
The 5th International Conference on Econometrics and Statistics (EcoSta 2022)
EO385: Dependency in Network Data
6 June 2022
Shizuo Kaji (Kyushu Univ.)How are these different?

AI is good at• Precise observation• Memorising/imitating
examples• Processing huge data
• Accurate operation

Human is good at• Rough estimation• Panoramic view
• Discovering rules from asmall number of examples• Explaining why

Deep Learning(DL)Topological DataAnalysis (TDA)
Maths-basedglobalarytnmeelpcom

Background• DL achieves high performance but has someweakness• TDA has succeeded in capturing data features thatconventional techniques have missed

Data-driven
localConvolutional Neural Nets are shortsighted
No attention is paid for the shapecue, but only the texture cue isconsidered by the model

Goodfellow et al. 2014

Geirhos et al. 2019

These results indicate CNNs are too
sensitive to local features.

Notable applications of TDA

Liquid-Amorphous-Crystalline states of silica
Y. Hiraoka et al. PNAS 2016
Hierarchical structures of amorphous solids characterized
by persistent homologyGene expression data of cells
M. Nicholau et al. PNAS 2011
Topology based data analysis
identifies a subgroup of breast
cancers with a unique mutational
profile and excellent survival

Clustering home insurance patterns
M. Yuvaraj et al. PNAS 2021
Topological clustering of multilayer
networks

Q&A of TDA
TDA techniques
Persistenthomology
Mapper
TFDA

Reeb graph

Path signature
Dimensionality
reduction

Some common questions• TDA = Persistent Homology?
• TDA = Point clouds?
• For what input data is TDA applicable?
• How to understand the output?
• Performance compared to conventional methods?
• Computational cost?
• How much data is necessary?
• How to incorporate TDA into an ML pipeline?

You can find my sample codes that provides a hands-on
walkthrough on various aspects in TDA: Google“Tutorial on Topological Data Analysis” kaji

Topological Features
Data è Topological space è Topological invariants as features

Topological invariants

Easy to compareand manipulate

Transform Spaces à “Numbers”
Stay unchanged under continuous
perturbation; capture global characteristics
Are computable01
They are difficult to find.
Fortunately, topologists have worked for a long time
to discover some nice topological invariants!

Example: Betti number (homology)b0connected
components

b1
loop

b2
cavityEulerb0-b1+b2

１

１１

１

１

１００

１

２

２００００

１

１１

１

１

００

０

２

Space

Homology

Sequence of numbers

Wait, we do not have “spaces”

Is there a hole?

When we look at these samples, we
unconsciously perform density estimationand thresholding to recover the “shape”

a2a1

An easy example of PH0

For each threshold a,
we can count thenumber of segments in{x | f(x)<a}Persistent homology (PH)
◦Extension of homology defined forfunctions over topological spaces(e.g., images, weighted graphs)◦For each topological feature(cycle),
the threshold values with which it
was born and destroyed arerecorded
Space X
Function XàR

PHMulti-set of points in R2
Looks too exotic…
Luckily, we can turn it into a vector!

Data Flow
GraphImage
VolumeTime series

VectorSpacePH
Filtration

Distance(kernel)

Point cloud
Ex. We can compare two graphs
by the distance between their PH

Data
We have many options at these two phases

PH Analysis of GraphGraph Convolution vs Topology
If we look at 1-neighbour of each vertex, the discriminative power is limited to 1-WeisfeilerLehman test (1-WL test).
(K. Xu, W. Hu, J. Leskovec, S. Jegelka. How Powerful are Graph Neural Networks?, ICLR2019)
This results in a theoretical bound for message passing Graph Convolutional Networks.
For example, they cannot distinguish the following two graphs.

They have different topology and distinguishable by their homology.
Global features complements for local features!

Persistent homology of graphUse case 1: A single feature for the whole graphUse case 2: A feature for each vertex

overlapping
multiple points(directed, undirected, weighted)
GraphA fixed size vector

Persistence diagram(multi-set in R2)

PH takes a graph and (vertex or edge) weights.
When weights are not present, we first have to define them in some way (discussed later)

Example
Input: Graph with edge weights

Output: Persistence diagrams

PH0

Bergomi MG, Ferri M, Vertechi P, Zuffi L. Beyond
Topological Persistence: Starting from Networks. 2021

PH1

Basic Idea: Threshold & Count & Connect

PH0PH1

1. Thresholding is applied to obtain
subgraphs by sweeping thresholdvalues
2. Homology is computed for eachsubgraph considered as a 1dimensional simplicial complex
3. “correspondence” between cycles
are considered to identify persistentcycles.
“Functoriality”

Bergomi MG, Ferri M, Vertechi P, Zuffi L. Beyond
Topological Persistence: Starting from Networks. 2021

1&2 are just “threshold and compute features.”
What makes “persistence” special is 3.

Graph to space (complex)◦ Option 1: Consider a graph as a 1-dimensional simplicial complex
PH0: connected components (clusters)
PH1: cycles
no higher PH◦ Option 2: (directed) flag complex: k-clique = (k-1)-simplex
PH0: connected components (clusters)
PH1: cycles of length > 3
PH2: cavity consisting of >4 vertices surrounded by triangles◦ Option 3: Path complex (rarely used in applications)Constructing Filtrations
attributes

Use vertex-dependent
filtration to obtain vertexwise features.

Filtration

1. No attributes => define vertex weights only from the combinatorial structure◦ Degree at vertices◦ Power filtration (= create a complete graph with edge weighted with path length )◦ WL-test

2. Graph with vertex weights (0-cochain)◦ edge weight is defined as the maximum of the vertex weights of its ends

3. Graph with edge weights (1-cochain)◦ vertex weight is defined as the minimum of the adjacent edges

4. Dynamic graph with only vertex/edge creation◦ Weight is defined by the creation time
◦ e.g., SNS (user –(follow,like)-> user), Wikipedia (user –(edit)-> article), Twitter (user –(retweet)-> user),

5. Dynamic graph with vertex/edge creation and deletion◦ Zig-zag persistence

PH Vectorisation techniques

Persistence diagrams can be turned into fixed-size vectors.
The size of the vector as well as some hyper-parameters are specified
by the user
◦ persistence image (JMLR2015)◦ persistence landscape (JMLR2015)◦ persistence curves (CVPRW2020)
There are also deep-learning based vectorisation techniques◦ Deep learning with topological signatures (NIPS2017)
Vectorisation involves some hyper-parameter tuning.
Vectorised PH features can be used in a standard ML pipeline.

GNN + PH

PH is differentiable at almost all input◦ Persistent Weisfeiler–Lehman Procedure (ICML2019)
Use WL-test to define distance between nodes to compute PH◦ Persistent Homology based Graph Convolution Network(ICCV2021)
Use PH as feature extractor
and the loss function (similarity measure between two nodeweighted graphs)◦ Topological Graph Neural Networks (ICLR2022)
Use PH as a layer of GNN (note that PH is differentiable)
Hybrid of Graph Neural Network and Persistent homology would be a
promising approach to local-global analysis of networks

Software: PH for graphs◦ giotto-tdaa comprehensive Python package for persistent homology.
It has a tutorial “Topological feature extraction from graphs”◦ A Persistent Weisfeiler–Lehman Procedure for Graph Classificationcompanion codes for the paper for graph classification◦ torchph
PyTorch extensions for persistent homology

PH for Identifying
Graph Structure-- Causality Detection -Bando-K-Yaguchi (JSIAM Letters, 2022)
based onConvergent Cross Mapping (CCM), Sugihara et al. Science, 2012

Causality in Network of variables
T h e n e w e ng l a n d j o u r na l o f m e dic i n e35Switzerland

Sweden30r=0.791
P<0.0001

Chocolateconsumption？
？

Nobel Laureates per 10 Million Population

EconomyClimateAustria

20

NorwayUnited Kingdom

15

The Netherlands

UnitedStates

Ireland

Belgium
CanadaPolandPortugal Greece

Germany

France105

Numberof Nobel
Laureates

Denmark

25Finland
Australia

Italy
Spain

Japan

0China0

Brazil51015

Chocolate Consumption (kg/yr/capita)

Messerli, F. H. (2012)

Figure 1. Correlation between Countries’ Annual Per Capita Chocolate Consumption and the Number of Nobel
Laureates per 10 Million Population.

Nobel laureates, yet we observe 32.
Discussion
How to detect：Intervention (e.g., cut the supply of chocolate
forabout
2014 years!)Consideringthat in this instance the observed
The principal finding of this study is a surpris- number exceeds the expected number by a fac=> In many cases, it is not feasible
ingly powerful correlation between chocolate tor of more than 2, one cannot quite escape theintake per capita and the number of Nobel laure- notion that either the Nobel Committee in
Goal today：Causal inference from observation
ates in (data)various countries. Of course, a correla- Stockholm has some inherent patriotic bias
tion between X and Y does not prove causation when assessing the candidates for these awards
indicates that either X influences Y, Y influ- or, perhaps, that the Swedes are particularlyÞ Challenge: We cannot observe everything but
ences X, or X and Y are influenced by a common sensitive to chocolate, and even minuscule
underlying mechanism. However, since choco- amounts greatly enhance their cognition.

Granger Causality
Nobel Laureate C. W. Granger (1969)
Compare two models

Xobservation!! , !" , … , !# …

?

Yobservation$! , $" , … , $# …

A$# = &($$# )B$# = &($$# , !$# )If Model B performs better than A=>“X granger causes Y”

Causality in dynamical systems“X causes Y” = The evolution rule of Y is dependent on the state of X

total system !×#": $ → $:!
(: $×* → *:&!"# = " &!
+!"# = ((&! , +! )XYupstream system !
$!"# = & $!

downstream system #'!"# = (($! , '! )We have limited access to the system◦ We have no way to gain complete knowledge of the state space◦ Only partial information is available through observation

observation ,: ! → / $(a map from the state space to a Euclidean space)statesystem $'!!

'!!"#Ex. State of Pacific Ocean

observation
observed data(time series) %('! )%('!! )%('!!"# )Two observations:(Temperature, sea level)Reconstruction of the state space$*$

randomprojectionv! → /$◦ For a large %, a generic observation ): + → -%is known to be an embedding(more precisely, such & are dense in the space of smooth maps)

observation faithfully
captures the stateBut◦ We cannot always make enough large observation.
(intuitively, ) is the number of simultaneous observations; e.g., temperature, humidity,…)

Delay-coordinate embedding(Takensʼ embedding)Instead of large simultaneous observation,
we can (surprisingly!) reconstruct the state spacefrom a series of single observation
Define ': X → +! by' , = (& ," , & ,"#$ , & ,"#% , … , & ,"#!&$ )E: embedding dimension
Theorem (Takens 1981)

in practice, E is a hyper-parameter

Under a mild assumption on the periodic orbits of the system,
for a large + and a generic %,the image of the delay-coordinate embedding approximates the attractor of the system
Note: Delay-coordinate embedding provides a powerful tool for time-series analysis(not only for causality inference but also e.g., prediction).

Delay-coordinate embedding
for a coupled system
Observation from the caused system can recover the total system
Total system $×.
'= 1 '!
/ !"#2!"# = 3('! , 2! )upstream $'!"# = 1 '!
observation%% ('! )XcausalityY

downstream .
2!"# = 3('! , 2! )observation%& ('! )Theorem (Stark 1999)

Under a mild assumption on the periodic orbits of " ,the delay-coordinates of a generic observation /4 (&! )approximates the attractor of the total system $×*

Down-stream system knows all
Daily
Amount of
Sakura flowering

Daily
Temperaturecausing

Which direction is easier to predict?

Topological consequence
System X

causality

Rec(Y)Rec(X)Reconstructedattractor of ,2System Y

prediction

Reconstructedattractor of ,3There exists a continuous surjection (≒ prediction)from Rec(Y) to Rec(X).
Note: This means, Granger causality is not appropriate for a deterministic system  Causality detection
by PH(Proof-of-Concept)
Applicability to real-world data is yet
to be investigated.
Idea:
Time-series for each vertex=> Spaces for each vertex and edge=> comparing PH for the spaces                            