SCOTT

Synthesizing Curvature Operations and Topological Tools

SCOTT is a Python package for computing curvature filtrations for graphs and graph distributions. This repository accompanies our NeurIPS 2023 paper: Curvature Filtrations for Graph Generative Model Evaluation.

Our method introduces a novel way to compare graph distributions, avoiding the limitations of Maximal Mean Discrepancy (MMD), which has known drawbacks.

By combining discrete curvature on graphs with persistent homology, SCOTT provides expressive descriptors of graph sets that are:

• Robust
• Stable
• Expressive
• Compatible with Statistical Testing

The package is highly adaptable, offering several options for user customization, including different curvature computation methods and diverse metrics for comparing persistent homology outputs.

Cite Us

If you find this package useful in your research, please consider citing:

@misc{southern2023curvature,
      title={Curvature Filtrations for Graph Generative Model Evaluation},
      author={Joshua Southern and Jeremy Wayland and Michael Bronstein and Bastian Rieck},
      year={2023},
      eprint={2301.12906},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

Installation

Using pip

Install curvature-filtrations via pip:

$ pip install curvature-filtrations

Building from Source

Our dependencies are managed with poetry, which can be installed with pip install poetry. To install from source:

1. Clone the repository

$ git clone https://github.com/aidos-lab/curvature-filtrations.git

1. Navigate to the directory

$ cd curvature-filtrations

3. Install dependencies

$ poetry install

Quick Start

The example.py script demonstrates how to compute the distance between two graph distributions.

To use SCOTT with your own data, replace the example graph distributions with your own. Distributions should be lists of networkx graphs or single networkx graphs.

Run our Example Script

python scripts/example.py

Tutorials

For a walkthrough of customization options and the intermediary functionalities supported by SCOTT objects, please see /notebooks. We offer the following two tutorials:

1. Customizing how your comparison is executed: custom_compare.ipynb

Read this section if: Your primary goal is to find the distance between your graph distributions, but you are looking for additional ways to customize the curvature and distance measures used.

Functionalities demonstrated in this tutorial include:

• Changing the method used for curvature calculations and associated hyperparameters
• Selecting and customizing the vectorization used to compare persistence diagrams

2. Breakdown of intermediate functionalities: bagpipeline.ipynb

Read this section if: You want to better understand the underlying workflow of this process and/or are interested in the output from intermediate steps in the process.

Functionalities demonstrated in this tutorial include:

• Calculating curvature for one graph or graph distribution
• Executing a curvature filtration to produce a persistence diagram
• Converting persistence diagrams into a topological descriptor (e.g. persistence landscape)
• Computing the distance between topological descriptors

Both tutorials are supported by /notebooks/utils.py.

Core Components

KILT

KILT stands for: Krvature-Informed Links and Topology is an object that can compute curvature filtrations for single graphs.

import networkx as nx
from scott import KILT,Comparator

G = nx.erdos_reyni(14,0.4)

kilt = KILT(measure="forman_curvature")

D = kilt.fit_transform(G)
print(f"Forman Curvature Filtration:")
print(f"Curvature Filtration Values:{kilt.curvature}")
print(D)

Comparator

Comparator handles comparisons between graphs or graph distributions!

import networkx as nx
from scott import KILT,Comparator

graph_dist1 = [nx.erdos_reyni(10,0.4) for _ in range(40)]
graph_dist2 = [nx.erdos_reyni(20,0.6) for _ in range(50)]

compare = Compare(measure="forman_curvature")

dist = compare.fit_transform(graph_dist1,graph_dist2,metric="image")

print(f"Distance between distributions measured by Forman Filtration: {dist}")