count-graph-homs: Yes we count!

The count-graph-homs library is the first ever ™️ 100%-SageMath-compatible implementation of the homomorphism counting algorithm (Prop. 1.6) from "Homomorphisms Are a Good Basis for Counting Small Subgraphs" by Radu Curticapean, Holger Dell, and Dániel Marx.

The library is designed to be efficient, accurate, and user-friendly, making it ideal for students and researchers who want to incorporate graph homomorphism counting into their work. The code is well documented, so that it is potentially useful for educational purposes.

For people who are curious about graph homomorphisms, you are invited to read Wikipedia to get started!

---

Table of Contents

• count-graph-homs: Yes we count!
  • Table of Contents
  • Installation
  • Structure
  • API Documentation
    • Module: standard_hom_count.py
    • Module: parallel_hom_count.py
  • Relevant Work
  • Acknowledgements
  • Contributing
  • License

---

Installation

Note: We are working towards merging the code into the SageMath codebase, so that users could use it in SageMath directly.

The current recommended way to use the count-graph-homs library is from source:

git clone https://github.com/guojing0/count-graph-homs.git
cd count-graph-homs
sage -n

After running the above commands, you should see a SageMath (Jupyter) notebook open in your browser. You may try to run the following to see if the library is working correctly:

from standard_hom_count import GraphHomomorphismCounter

square = graphs.CycleGraph(4)
bip = graphs.CompleteBipartiteGraph(2, 4)

counter = GraphHomomorphismCounter(square, bip)
count = counter.count_homomorphisms()
print(count)

It should print 128, which is the correct answer.

For more details on the usage of the library, please see tutorial.ipynb to get started.

Structure

• tutorial.ipynb: A Jupyter notebook file for tutorials.
• standard_hom_count.py: Sequential implementation of the homomorphism counting algorithm (will be in Sage).
• parallel_hom_count.py: parallel implementation using Dask, Numba, and Numpy (optional Sage package).
• helpers/: A directory of helper functions and utilities.
  • help_functions.py
  • nice_tree_decomp.py
• deprecated/: Deprecated codes for educational purposes only.
  • hom_count_basic.py
  • hom_count_int.py
  • hom_count_int_dict.py

API Documentation

Module: standard_hom_count.py

Class: GraphHomomorphismCounter

• Constructor:

  • __init__(self, graph, target_graph, density_threshold=0.5, graph_clr=None, target_clr=None, colourful=False)
    • Parameters:
      • graph: A Sage graph representing the source graph.
      • target_graph: A Sage graph representing the target graph.
      • density_threshold (default: 0.5): The density threshold for the target graph representation.
      • graph_clr (default: None): A list of integers representing the colors of the vertices of the source graph.
      • target_clr (default: None): A list of integers representing the colors of the vertices of the target graph.
      • colourful (default: False): A boolean indicating whether or not counting the number of color-preserving homomorphisms.

• Methods:

  • count_homomorphisms(self): Return the number of homomorphisms.

---

Module: parallel_hom_count.py

Class: ParallelGraphHomomorphismCounter

• Constructor:

  • __init__(self, graph, target_graph, density_threshold=0.5, graph_clr=None, target_clr=None, colourful=False)
    • Parameters:
      • graph: A Sage graph representing the source graph.
      • target_graph: A Sage graph representing the target graph.
      • density_threshold (default: 0.5): The density threshold for the target graph representation.
      • graph_clr (default: None): A list of integers representing the colors of the vertices of the source graph.
      • target_clr (default: None): A list of integers representing the colors of the vertices of the target graph.
      • colourful (default: False): A boolean indicating whether or not counting the number of color-preserving homomorphisms.

• Methods:

  • count_homomorphisms_parallel(self, node=None): Return the number of homomorphisms with parallel computation.

Relevant Work

1. Master thesis of Christian Janos Lebeda and Jonas Mortensen: HomSub: Counting small subgraphs via homomorphisms

2. Master thesis of Emil Ruhwald Nielsen, Otto Stadel Clausen, and Elisabeth Terp Reeve: Counting subgraph patterns in large graphs

3. Emily Jin, Michael Bronstein, Ismail Ilkan Ceylan, and Matthias Lanzinger: Homomorphisms Counts for Graph Neural Networks: All About That Basis

Near the completion of this project, the developer also learned of the following Rust implementation:

• Julian Mende: Count Homomorphisms in Rust

Acknowledgements

The developer (Jing Guo) first would like to thank Radu Curticapean for his guidance and support. He also takes inspiration from works and implementations of the authors of the two Master theses mentioned above.

This work was supported by the research grant from the European Union (ERC, CountHom, 101077083). Views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

Contributing

We welcome contributions to this project! If you have found a bug or have any suggestions for improvement, please open an issue or submit a pull request.

License

MIT