🔢 mathematics

Complete Low-Degree Magnitude-Homology Signatures in Fixed Windows for Finite Graphs

This paper presents an efficient computational method combining boundary matrices, normal forms, and closed-form formulas to calculate low-degree integral magnitude homology for finite graphs, demonstrating its superior ability to distinguish nonisomorphic graph pairs compared to ordinary invariants through extensive analysis of standard families and small connected graphs.

Original authors: 朱瑶君

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: 朱瑶君

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive collection of LEGO structures. Some are simple towers, others are intricate castles, and some look completely different but happen to have the exact same number of bricks, the same number of connections, and the same overall shape. If you only counted the bricks and connections, you'd think these different castles were identical twins. But what if there's a secret "fingerprint" hidden deep inside the way the bricks are stacked that reveals they are actually unique?

That's exactly what this paper does, but instead of LEGO, it's looking at graphs (mathematical maps of dots and lines) and their hidden "magnitude homology" fingerprints.

The Secret Fingerprint Hunt

The authors, led by Yaojun Zhu, wanted to see if they could calculate these super-detailed fingerprints for a huge bunch of graphs. The problem is, calculating these fingerprints is like trying to solve a million-piece puzzle where the pieces are giant, heavy numbers. It gets expensive and slow very quickly.

To solve this, the team built a super-efficient "math machine." They combined a few clever tricks:

Stacking the Blocks: Instead of looking at one piece of the puzzle at a time, they stacked the boundary matrices (the rules for how the graph connects) together.
The Magic Clean-Up: They used special math tools called Hermite and Smith normal forms. Think of these as a magical vacuum cleaner that sucks out all the messy, unnecessary numbers and leaves behind a perfectly organized, simplified list of the graph's true structure.
The Cheat Sheet: For some very regular shapes (like perfect stars or complete circles), they didn't do the heavy lifting at all. They used known formulas (closed-form) as a "cheat sheet" to skip the hard work.

The Big Test: Two Different Worlds

The team put their machine to work in two different "rooms" (or windows) to see how well it worked.

Room 1: The Family Album (W(5, 10))
They picked 63 specific, well-known graph families (like paths, cycles, stars, and complete graphs). They asked their machine to find the fingerprints for 4,158 different specific spots in the math structure.

The Result: The machine solved all 4,158 of them. Not a single one was left behind. It was a perfect score.

Room 2: The Chaos Lab (W(3, 6))
This was the real challenge. They grabbed 996 different connected graphs that have up to seven vertices (dots). These weren't just neat families; they were messy, random-looking graphs.

The Result: Again, the machine solved every single one (27,888 groups total).

The Great Identity Crisis

Here is where it gets really fun. The authors took all these graphs and grouped them by their "ordinary profile." This is like grouping people by their height, weight, and shoe size. They found 564 pairs of graphs that looked identical based on these basic stats. They were "twins" in the ordinary sense.

Then, they asked: Does our new magnitude homology fingerprint tell them apart?

They tested three levels of detail:

The "Support" Check: Does the fingerprint exist at all? (Yes/No)
The "Rank" Check: How big is the fingerprint? (Just the size)
The "Integral" Check: What is the fingerprint made of? (The full, detailed number structure)

The Shocking Results:

The "Support" check (the simplest one) could only tell apart 89 of the 564 pairs. It missed most of them.
The "Rank" check and the "Integral" check were much sharper. They successfully separated 434 of the pairs!
This means that for 345 pairs, the graphs looked the same in size, but their internal "multiplicity" (how many times a pattern repeats) was different. The detailed math caught a difference the simple math missed.

However, there were still 130 pairs that even the most detailed "Integral" check couldn't tell apart within this specific window. They remain mystery twins for now.

What This Paper Doesn't Say

It's important to know what this study didn't do.

No Torsion Found: The authors explicitly state that within these specific windows and graphs, they did not find any "torsion" (a weird, twisted kind of math behavior). They know torsion exists in other graphs, but it didn't show up in their specific test cases.
Not a Universal Solution: This isn't a magic key that solves every graph in the universe. It only works for the specific windows they tested (up to degree 5 or 3, and length 10 or 6).
No Future Predictions: The paper doesn't claim this will change how we build bridges or cure diseases. It's purely about understanding the math of graphs better.

The Bottom Line

The paper proves that by combining smart math shortcuts with powerful computer calculations, we can completely map out the low-degree "fingerprint" of hundreds of complex graphs. We learned that looking at just the "size" of these fingerprints is often enough to tell different graphs apart, but sometimes you need the full, detailed number breakdown to catch the subtle differences.

For the 130 pairs that still look identical, the authors suggest we need to look at bigger windows (higher numbers) to see if the mystery twins finally reveal their true colors. But for now, the machine has successfully solved every single puzzle it was asked to solve in these specific rooms.

Technical Summary: Complete Low-Degree Magnitude-Homology Signatures in Fixed Windows for Finite Graphs

Problem Statement
Magnitude homology is a bigraded integral invariant for finite graphs, offering a categorification of the magnitude invariant. While theoretically powerful, the exact computation of integral magnitude homology groups is computationally expensive, particularly due to the potential for torsion, which renders rank tables insufficient as substitutes for full integral data. The paper addresses two specific computational questions:

Can every requested integral magnitude-homology group within a declared bidegree window be determined by combining direct integer computation with exact formulas for standard graph families?
How much discriminatory information is lost when reducing integral signatures to rank signatures (free rank only) or support signatures (zero vs. non-zero only)?

Methodology
The author develops an exact integer-homology framework to compute magnitude homology groups $MH_{k,l}(G)$ within fixed windows $W(K, L) = \{(k, l) : 0 \le k \le K, 0 \le l \le L\}$ . The methodology relies on three core components:

Consecutive Boundary Matrices: For a fixed bidegree $(k, l)$ , the method constructs boundary matrices $A = D_{k,l}$ and $B = D_{k+1,l}$ representing the maps between chain groups. The target group is defined as $\ker(A) / \text{im}(B)$ .
Exact Integer Linear Algebra: The computation utilizes Hermite Normal Form (HNF) and Smith Normal Form (SNF) over the integers.
- An HNF is computed for $A$ to derive an integral basis for $\ker(A)$ .
- This basis is used to transform $B$ into a matrix $Q$ .
- The SNF of $Q$ yields the invariant factors, determining the group structure as a direct sum of free and torsion components ( $\mathbb{Z}^r \oplus \bigoplus \mathbb{Z}/d_i\mathbb{Z}$ ).
- Calculations were performed using python-flint (FLINT library) and verified against SymPy implementations.
Hybrid Computation Strategy:
- Direct Computation: Used for the majority of cases, particularly for the dataset of connected unlabeled graphs.
- Closed-Form Formulas: For standard families (trees, complete graphs, complete bipartite graphs, cycles), the author utilizes existing formulas (Hepworth and Willerton; Gu) to fill gaps or verify results.
- Validation: The two methods were cross-verified on overlapping bidegrees, showing perfect agreement.

Datasets and Scope
The study focuses on two distinct datasets within specific windows:

Standard Graph Families: 63 selected instances (including paths, cycles, stars, complete graphs, double stars, and various trees) analyzed in the window $W(5, 10)$ .
Connected Unlabeled Graphs: All 996 connected unlabeled simple graphs with up to seven vertices, analyzed in the window $W(3, 6)$ .

Key Results

Completeness: The framework successfully resolved all requested groups.
- Standard Families: All 4,158 groups in $W(5, 10)$ were resolved (3,618 via direct computation, 540 via closed-form).
- Small Graphs: All 27,888 groups for the 996 graphs in $W(3, 6)$ were resolved via direct computation.
Discriminatory Power: The study compared nonisomorphic graph pairs that shared identical "ordinary profiles" (vertex count, edge count, degree sequence, diameter, girth, cycle rank, bipartite status, and triangle count). There were 564 such pairs in the 7-vertex dataset.
- Rank vs. Integral: Rank signatures and full integral signatures were identical in their ability to distinguish pairs; both separated 434 pairs.
- Support Signatures: Support signatures (zero/non-zero only) separated only 89 pairs.
- Multiplicity Contribution: The difference between the rank/integral separation (434) and support separation (89) indicates that 345 pairs are distinguished specifically by the multiplicity (ranks) of the homology groups, not just their existence.
Torsion: Within the computed datasets and windows, no torsion factors were observed. All resolved groups were free abelian.

Significance and Claims
The paper claims to provide the first complete dataset of low-degree integral magnitude homology signatures for these specific graph sets. Its primary contribution is demonstrating that:

An exact computational framework combining HNF/SNF with family formulas is feasible for resolving integral groups in fixed windows.
Integral signatures (and by extension, rank signatures) provide significantly more discriminatory power than support signatures for graphs with identical ordinary profiles.
The "multiplicity" of homology groups is a critical invariant for distinguishing finite graphs that standard graph invariants cannot separate.

The author explicitly notes limitations: the results are confined to the specified windows and do not constitute a full classification of finite graphs. The absence of observed torsion is limited to the computed dataset, acknowledging that torsion is known to exist in magnitude homology outside these specific parameters. The remaining 130 indistinguishable pairs define a target for future larger-window comparisons.

The Secret Fingerprint Hunt

The Big Test: Two Different Worlds

The Great Identity Crisis

What This Paper Doesn't Say

The Bottom Line

More like this