⚡ electrical engineering

Joint Simplicial Complex Learning via Binary Linear Programming

This paper proposes a joint framework for learning simplicial complexes by formulating the problem as a binary linear program that enforces the inclusion property through linear constraints while simultaneously optimizing smoothness across all simplicial levels.

Original authors: Varun Sarathchandran, Geert Leus

Published 2026-02-10

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Varun Sarathchandran, Geert Leus

Original paper licensed under CC BY 4.0 (http://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 are trying to reconstruct a complex, multi-layered social network—not just who is friends with whom (the pairs), but also who belongs to the same tight-knit "cliques" or "friendship circles" (the groups).

This paper, "Joint Simplicial Complex Learning via Binary Linear Programming," tackles the mathematical challenge of figuring out both the connections and the groups at the same time.

Here is the breakdown of the problem and their solution using a simple analogy.

1. The Problem: The "Lego" Rule

Think of building a structure out of Legos. In a "Simplicial Complex" (the mathematical term for these networks), there is a strict rule called the Inclusion Property.

It’s like saying: "You cannot have a triangle of friends unless all three individual friendships that make up that triangle actually exist."

If you try to learn these networks using old methods, you usually run into two problems:

The "Step-by-Step" Mistake (Hierarchical): You first pick all the friendships, and then you look for triangles. But what if a friendship only exists because it’s part of a larger, important group? By picking friendships first, you might miss the "big picture."
The "Guess and Check" Mistake (Greedy): You try to pick both, but you keep changing your mind back and forth. You pick a triangle, then realize you forgot an edge, so you go back and add it. It’s inefficient and often gets stuck in a loop of "almost right" answers.

2. The Solution: The "Master Architect" (Binary Linear Programming)

The authors propose a new way: instead of building piece-by-piece or guessing, they act like a Master Architect looking at a blueprint.

They use a mathematical tool called Binary Linear Programming. Imagine a giant control panel with thousands of light switches. Each switch represents a possible friendship or a possible triangle.

Switch ON: The connection exists.
Switch OFF: The connection doesn't exist.

Instead of flipping switches one by one, the Architect writes a single, massive set of rules (a "program") and hits "GO." This program looks at all the switches simultaneously.

3. The Secret Sauce: The "Smart Rules"

The Architect’s program uses two special types of rules to make sure the network is accurate:

The "No Ghost Triangles" Rule (Linear Constraint): This is a mathematical "tether" between the friendship switches and the triangle switches. It says: "If you turn on a triangle switch, the friendship switches for its sides MUST be turned on. No exceptions." This ensures the "Lego rule" is never broken.
The "Vibe Check" Rule (Smoothness/Similarity): The researchers look at "signals" (data) coming from the network. For example, in a co-authorship network, the "signal" might be the topics authors write about. If three authors are in a triangle, their topics should be "smooth" or similar. The program looks for the combination of friendships and triangles that makes the most sense based on these "vibes."

4. Why does this matter? (The Results)

The researchers tested this on simulated data and real-world data (like how scientists collaborate).

They found that their "Master Architect" approach was much better at finding the true structure than the "Step-by-Step" or "Guess and Check" methods. Because it looks at everything at once, it can realize that a specific friendship is important because it completes a meaningful group, rather than just looking at the friendship in isolation.

In short: Instead of trying to find the pieces of a puzzle one by one, they solved the entire puzzle in one single, brilliant move.

Technical Summary: Joint Simplicial Complex Learning via Binary Linear Programming

1. Problem Statement

The paper addresses the challenge of learning the topology of higher-order networks, specifically Simplicial Complexes (SCs), from observed signals. While traditional graph learning focuses on pairwise interactions (edges), SCs model multi-way interactions (e.g., triangles) while strictly enforcing the inclusion property: if a $k$ -simplex exists, all its $(k-1)$ -dimensional faces must also exist in the complex.

Existing approaches to SC learning suffer from two main limitations:

Hierarchical Methods: These infer lower-order structures (edges) first and then higher-order structures (triangles). This decouples the levels, preventing higher-order connectivity from informing lower-order estimation.
Greedy/Non-hierarchical Methods: These often use penalty terms to enforce inclusion or alternating optimization. These methods either only implicitly enforce the inclusion property (which can lead to structural violations) or reduce to hierarchical methods when the penalty is high.

2. Methodology

The authors propose a joint, one-shot framework that treats the simultaneous estimation of edges and triangles as a single optimization problem.

A. Mathematical Formulation
Instead of optimizing over incidence matrices directly, the authors operate in the space of "fully connected" complexes. They use binary selection vectors:

$s_1 \in \{0, 1\}^{\bar{N}_1}$ to select edges from all possible node pairs.
$s_2 \in \{0, 1\}^{\bar{N}_2}$ to select triangles from all possible triplets.

B. Binary Linear Program (BLP)
The core contribution is formulating the learning task as a Binary Linear Program:
$\min_{s_1, s_2} h_1^\top s_1 + h_2^\top s_2$
Subject to:

Inclusion Constraint: $s_1 \geq \alpha \bar{B}_2^+ s_2$ . This linear constraint ensures that if a triangle is selected ( $s_2$ ), its constituent edges must also be selected ( $s_1$ ).
Cardinality Constraints: $\mathbf{1}^\top s_1 \geq C_1$ and $\mathbf{1}^\top s_2 \geq C_2$ , ensuring a minimum number of simplices are recovered.
Integrality: $s_1, s_2 \in \{0, 1\}$ .

C. Smoothness Priors (Objective Function)
The cost vectors $h_1$ and $h_2$ are derived from simplicial signals. The authors demonstrate that various smoothness measures can be linearized:

Node-signal smoothness: Uses the graph Laplacian to penalize differences between node values across an edge.
Curl-based smoothness: Penalizes the "circulation" of edge signals around a triangle.
Similarity-based smoothness (New): A novel measure introduced by the authors that penalizes differences between the values of the edges that form a triangle, generalizing classical graph smoothness to higher orders.

3. Key Contributions

Joint Optimization: A framework that allows higher-order topology to guide lower-order topology estimation simultaneously.
Explicit Inclusion via Linear Constraints: Unlike previous works that use non-convex penalties or bilinear constraints, this method uses a linear constraint that guarantees the inclusion property while remaining computationally tractable via BLP.
Generalized Smoothness Framework: The ability to incorporate arbitrary smoothness criteria (including a new similarity-based measure) into a unified linear objective.

4. Results

The authors evaluated their method against hierarchical and greedy baselines using simulated data and a real-world co-authorship network.

Simulated Data: The joint approach consistently achieved higher $F_1$ scores for both edge and triangle detection. It proved that solving for all levels simultaneously allows the model to find a globally optimal structure that hierarchical methods miss.
Real-World Data (Co-authorship): On a dataset where edge signals exhibited high similarity rather than low curl, the joint method significantly outperformed baselines in triangle recovery.
Observation on Baselines: The authors noted that greedy and hierarchical methods often rely heavily on "feasibility" (simply picking whatever is possible) rather than the actual signal priors. The proposed joint method is the only one that effectively uses the signal-based prior to guide the selection of higher-order simplices.

5. Significance

This work provides a principled and mathematically rigorous way to reconstruct the multi-way interaction structures of complex systems. By transforming a complex topological problem into a Binary Linear Program, the authors offer a method that is both structurally accurate (guaranteeing inclusion) and more effective at capturing the underlying patterns in data compared to existing decoupled or penalty-based methods. This has broad implications for signal processing on higher-order networks in fields like biology, social science, and epidemiology.