PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning the Topology of a Simplicial Complex Using Noisy Simplicial Signals

Andrei Buciulea, Elvin Isufi, Geert Leus, Antonio G. Marques

arXiv:2609.12866v1eess.SP

TL;DR

Learning an SC topology from signals is challenging when methods rely on pairwise proxies or restrictive observation settings. This paper formulates inference from noisy nodal and partial edge signals using sparse topology selection and block-coordinate descent. It reports convergence to a stationary point of a relaxed penalized formulation and modest computational complexity.

  • Problem

    Existing SC-inference methods often rely on restrictive assumptions, including known topology with fully observed edge signals or access only to nodal data.

    Source: §I · p. 2

  • Method

    The approach models topology with binary edge and triangle selection vectors and uses relaxed block-coordinate descent with greedy edge and triangle selection.

    Source: §I · p. 2, §VI · p. 12

  • Results

    The algorithm converges to a coordinate-wise minimum that is stationary for the relaxed penalized formulation, and its computational complexity is reported as modest.

    Source: F. Convergence results · p. 8, §VI · p. 12

  • Takeaways & Limitations

    The framework offers a computationally tractable route to infer higher-order SC structure from noisy signals with partial edge observations.

    Source: §I · p. 2, E. BCD SC-learning · p. 7, §VI · p. 12

    The approach assumes sparse edges and triangles, smooth node signals, and low-curl edge observations.

    Source: §I · p. 2

Abstract

from arXiv · show

Graphs are a fundamental tool for modeling the irregular (non-Euclidean) structure of complex data. However, they are inherently limited to representing pairwise relationships, making them inadequate for datasets exhibiting higher-order interactions. Simplicial complexes (SCs) have emerged as a promising framework for capturing such higher-order dependencies. This paper focuses on the problem of identifying the topology of an SC from signals, which serves as the foundation for SC-based processing and learning schemes. We consider a setting where we observe noisy signals (features) associated with the nodes of the SC (0-simplices) and a subset of the edges (1-simplices). We assume the observed signals are smooth over the unknown SC topology, and that the higher-order interactions are sparse. Building on these assumptions, we formulate topology learning as a nonconvex optimization problem and propose an efficient block-coordinate descent (BCD) algorithm to solve it. A key step in our formulation is the modeling of the topology of the SC using binary edge and triangle selection vectors, combined with efficient greedy algorithms for optimizing such vectors. We establish theoretical convergence guarantees to a stationary point of a relaxed (penalized) version of the problem and discuss computational complexity. Multiple numerical experiments with both synthetic and real-world datasets validate the effectiveness of our approach, highlighting the capability of SC-learning methods to uncover and model higher-order relationships in complex datasets.

I. INTRODUCTION

Simplicial complexes model higher-order interactions, but learning their topology remains difficult when prior methods rely on restrictive observation settings or pairwise proxies. The paper introduces the SC structure and signal assumptions underlying its approach to inference.

I. INTRODUCTION

  • Many SC-inference methods rely on pairwise proxies or assume either a known graph with fully observed edge signals or node-only observations.These restrictions motivate joint inference from partial node and edge observations while respecting SC closure.Source: §I · p. 2
  • The paper targets second-order SC recovery from noisy node signals and a subset of noisy edge signals, assuming sparse structure, smooth node signals, and low-curl edge signals.Node smoothness favors connections between similar-valued nodes, while triangle smoothness favors small curl.Source: §I · p. 2
  • A relaxation and block-coordinate descent algorithm use greedy edge and triangle selection, with convergence to a stationary point of a penalized formulation.The paper also reports optimality for each step within its variable block.Source: §I · p. 2

II. NOTATION PRELIMINARIES

  • An order-2 simplicial complex contains nodes, edges, and filled triangles, and every triangle must include its three boundary edges.The incidence matrices encode memberships among these simplex dimensions.Source: §II · p. 3
  • The observations comprise noisy nodal signals and noisy edge-flow signals available only on a subset of active edges.The edge sampling matrix selects the observed edge rows from the full edge-signal matrix.Source: §II · p. 3
  • Nodal smoothness measures variation across edges, while edge-signal smoothness is modeled through small curl over filled triangles.The paper assumes low-curl flows, which it associates with signals concentrated in slow-varying curl components.Source: §II · pp. 3–4

III. AN OPTIMIZATION APPROACH FOR LEARNING SC FROM SIGNAL OBSERVATIONS

The section formulates SC learning from noisy nodal and partially observed edge signals under sparsity and smoothness assumptions. It first presents an incidence-matrix optimization and then identifies its feasibility and closure challenges.

III. AN OPTIMIZATION APPROACH FOR LEARNING SC FROM SIGNAL OBSERVATIONS

  • The paper's main formulation replaces incidence matrices with edge and triangle selection vectors and recasts the simplicial-complex closure constraint.This alternative formulation is the paper's main focus.Source: §III · p. 4

A. Problem statement and naive formulation

  • The task is to recover edges and filled triangles from noisy node observations and partial noisy edge signals, assuming sparse simplices, smooth node signals, and low-curl edge signals..Source: A. Problem statement and naive… · p. 4
  • The incidence-matrix objective combines edge and triangle sparsity, noisy-signal fit, and nodal and edge-signal smoothness, with constraints for SC validity and observed edges.Its closure constraint imposes a necessary algebraic condition for the simplicial-complex property.Source: A. Problem statement and naive… · p. 4
  • The incidence-matrix formulation is nonconvex, makes feasible incidence matrices difficult to enforce, and has a closure condition that is necessary but not sufficient.When inactive edge columns are set to zero, the condition can still permit a triangle whose three edges are absent.Source: A. Problem statement and naive… · p. 4

B. SC-learning approach via simplex selection

The formulation represents topology with binary edge and triangle selection vectors and enforces the simplicial closure condition. This recasting reduces variables and constraints, though binary variables and bilinear terms remain challenging.

B. SC-learning approach via simplex selection

  • Binary edge and triangle selection vectors recast topology inference as a selection problem over the complete simplicial complex.An entry is active when its corresponding edge or triangle is included.Source: B. SC-learning approach via simplex… · pp. 4–5
  • The SCC constraint requires every selected triangle to have all three of its supporting edges selected.It checks whether edges required by selected triangles are active.Source: B. SC-learning approach via simplex… · p. 5
  • The reformulation uses fewer variables and constraints, simpler feasible sets, and linear expressions in place of several multilinear terms.The formulation also uses a user-specified triangle budget and an ε term that ensures unique edge interpolation and zero signals on certain inactive edges.Source: B. SC-learning approach via simplex… · p. 5
  • The reformulated problem remains challenging because the selection vectors are binary and the objective and SCC constraint include bilinear interactions.These include bilinear terms in the SCC constraint and smoothness term.Source: B. SC-learning approach via simplex… · p. 5

IV. A BCD SC APPROACH: OPTIMAL SOLUTIONS AND ALGORITHMIC DESIGN

The algorithm handles the formulation through alternating updates over four variable blocks and a penalty for SCC violations. With the other blocks fixed, the triangle-selection update is obtained by a greedy score-based rule.

IV. A BCD SC APPROACH: OPTIMAL SOLUTIONS AND ALGORITHMIC DESIGN

  • The BCD algorithm alternates among four blocks, using an SCC-violation penalty and greedy procedures to address sparsity and binary constraints.The blocks are the nodal signals, edge signals, edge-selection vector, and triangle-selection vector.Source: §IV · p. 5

A. Optimization of the triangle selection vector

  • With other variables fixed, the optimal triangle-selection update chooses the triangle-budget entries with the smallest scores.Each score combines a sparsity cost, an edge-signal smoothness term, and an SCC-violation penalty; the SCC penalty vanishes when all three edges are selected.Source: A. Optimization of the triangle… · p. 6
  • Sorting triangle scores has average complexity O(T̄ log T̄), while computing the scores adds complexity dominated by the smoothness term.The sorting cost is described as relatively efficient; score computation is more costly.Source: A. Optimization of the triangle… · p. 6

B. Optimization of the edge selection vector

With the other variables fixed, the edge-selection update is greedy and score-based. Its soft treatment of simplicial closure preserves flexibility for block-coordinate updates, with a final step enforcing closure.

B. Optimization of the edge selection vector

  • Hard SCC enforcement at every iteration can prevent removing links from filled triangles, limiting block-update flexibility and potentially invalidating standard BCD convergence guarantees.The text describes this as a reason for using an SCC penalty rather than enforcing the constraint as a hard constraint at each iteration.Source: B. Optimization of the edge selection… · p. 6
  • A finite SCC penalty may not ensure exact feasibility, so post-processing adds missing edges to any filled triangle to enforce closure.For sufficiently large γ, the recovered solution satisfies SCC in practice, but exact feasibility is not theoretically guaranteed by a finite penalty.Source: B. Optimization of the edge selection… · p. 6
  • The optimal edge update greedily activates edges by ascending score, always includes observed edges, and can select more than Emin edges.The edge count can exceed Emin when many triangles are selected and the SCC penalty parameter γ is sufficiently large.Source: B. Optimization of the edge selection… · pp. 6–7

C. Optimization of the nodal signals

The signal updates optimize nodal and edge signals while holding the topology variables fixed. Nodal denoising balances smoothness against observed-data fidelity, while edge interpolation incorporates topological constraints.

C. Optimization of the nodal signals

  • With topology and edge signals fixed, the nodal-signal update is a convex, differentiable denoising problem whose smoothness–fidelity trade-off is governed by β1/η0.Its solution follows from setting the gradient to zero; the matrix to invert is positive definite.Source: C. Optimization of the nodal signals · p. 7

D. Optimization of the edge signals

  • With topology and nodal signals fixed, the edge-signal update optimizes the edge signals using observed values and an edge-signal smoothness term.The interpolation is coupled to the inferred simplicial topology rather than being generic denoising or inpainting.Source: D. Optimization of the edge signals · p. 7
  • The εη1I term makes the edge-signal solution unique and sets to zero signals on edges that are neither observed nor part of a filled triangle.Without ε, the matrix would be rank-deficient for such edges.Source: D. Optimization of the edge signals · p. 7

E. BCD SC-learning

GreedySCL alternates updates to edge and triangle selections with estimates of the node and edge signals. Its greedy updates avoid exhaustive search over candidate simplices, keeping computational costs manageable as the number of nodes grows.

E. BCD SC-learning

  • GreedySCL iteratively estimates edge and triangle selection vectors alongside node and edge signals, then outputs the final topology and signal estimates.The algorithm includes a closure step that adds edges required by selected filled triangles.Source: E. BCD SC-learning · pp. 7–8
  • The algorithm sorts candidate edges and triangles in O(N^2 log(N)) and O(N^3 log(N)), respectively.It runs for ℓmax iterations.Source: E. BCD SC-learning · p. 7
  • Greedy ranking and selection avoid exhaustive search despite the O(N^3) candidate-triangle count, leaving sorting and matrix operations as the dominant costs.The iteration count is typically a few tens, keeping the overall cost manageable for larger graphs than brute-force search can handle.Source: E. BCD SC-learning · p. 7
  • Greedy edge and triangle selection avoids the O(N^7) and O(N^10.5) complexity terms associated with a generic convex solver.Those terms correspond to the edge and triangle variable counts, respectively.Source: E. BCD SC-learning · p. 8
  • A few gradient-descent iterations can approximate the signal least-squares updates, with negligible optimality loss in the numerical setups examined.This replaces computing the optimal signal estimates with pseudoinverses at each iteration.Source: E. BCD SC-learning · p. 8

F. Convergence results

The convergence analysis relaxes the binary and norm-zero terms and uses block-coordinate descent on a penalized formulation. Under assumption AS5, the iterates converge to a stationary point of that relaxed problem, while simplicial closure may require a final repair step.

F. Convergence results

  • The convergence proof relies on uniqueness of the greedy block solutions under AS5, including conditions that exclude problematic score ties and zeros.The relaxed formulation replaces the simplicial closure constraint with a penalty term.Source: F. Convergence results · p. 8
  • The analysis replaces norm-zero terms with one-norms, relaxes binary selection vectors to [0, 1], and linearizes the cardinality constraints.For vectors in [0, 1], the resulting sum constraints ensure the stated minimum numbers of selected edges and triangles.Source: F. Convergence results · p. 8
  • Under assumption AS5, the iterates converge to the set of stationary points of the relaxed penalized problem as ℓ tends to infinity.The proof uses block-coordinate minimization and establishes that the resulting block-coordinate minimum is stationary.Source: F. Convergence results · p. 9
  • The convergence guarantee concerns the relaxed problem; the original discrete formulation has no well-defined notion of stationarity.The iterates are binary and feasible for the relaxed problem and the penalized counterpart of the original formulation.Source: F. Convergence results · p. 9
  • Simplicial closure is promoted by a penalty but is not guaranteed along iterations; a final closure step adds edges needed by selected filled triangles.The final output is therefore a valid simplicial complex, and the objective increase from closure is explicitly bounded by the added-edge scores.Source: F. Convergence results · p. 9

V. NUMERICAL RESULTS

The numerical section evaluates topology recovery, signal denoising and recovery, algorithmic behavior, and performance on a real co-authorship dataset. Its synthetic experiments use several graph families and compare the proposed method with two alternatives.

V. NUMERICAL RESULTS

  • The numerical section covers topology recovery, node and edge signal recovery, algorithmic behavior, and evaluation on a real co-authorship dataset.The real-data experiment compares the proposed method against relevant baselines.Source: §V · p. 9
  • Synthetic tests use 20-node ER, SBM, and BA graphs, with half of triangles filled, 70% of edge signals observed, and results averaged over 100 realizations.Each setup uses 1,000 node and edge signal samples.Source: §V · p. 9
  • The comparisons include G-SCL, S-SCL without an enforced relationship between incidence matrices, and RC based on node-signal correlations.Hyperparameters are grid-searched for best average performance in each setting, using the same tuning strategy across methods.Source: §V · p. 9

A. Topology recovery

The experiments examine topology recovery, signal denoising, algorithm behavior, and co-authorship data. Across these settings, the proposed approach recovers higher-order structure from node and edge signals and converges to a stationary point of its relaxed formulation.

A. Topology recovery

  • G-SCL achieves higher edge and triangle F-scores than S-SCL and reaches stable recovery with fewer samples; its advantage persists under increasing noise.The comparison is attributed to jointly estimating edges and triangles from node and edge signals, which exploits their coupling and provides complementary constraints against noise.Source: A. Topology recovery · p. 10, Figure 2 · p. 10
  • With missing node observations, recovery is not very sensitive to the missing-node fraction but is sensitive to available edge-signal coverage; more edge observations improve both edge and triangle F-scores.Triangle recovery is harder, and S-SCL fails to infer triangles in this regime; available edge signals partially compensate for missing node information.Source: A. Topology recovery · p. 10
  • Misclassified edges and triangles receive consistently lower smoothness rankings than competing methods, placing them closer to satisfying the assumed smoothness condition.The ranking analysis complements the recovery results in Fig. 2.Source: A. Topology recovery · pp. 10–11

B. Signal denoising/recovery

  • Denoising improves as signal noise increases, while node-signal denoising degrades with more missing node data and edge-signal denoising remains stable across that perturbation.Denoising is consistently better for X0 than X1; the passage attributes the difference likely to fewer filled triangles providing structural support for X1.Source: B. Signal denoising/recovery · p. 11, Figure 3 · p. 11

C. Algorithm Insights

  • Edge estimates converge before triangle estimates, and the four-subproblem algorithm combines closed-form and greedy updates; its most computationally demanding updates scale with the number of candidate edges.Convergence is consistent across ER, BA, and SBM graphs; memory use grows with network size, notably through X1, the largest matrix in the formulation.Source: C. Algorithm Insights · pp. 11–12, Figure 4 · p. 11
  • Increasing the SCC penalty γ reduces normalized SCC violation to zero beyond a threshold while edge F-score stays nearly unchanged and triangle F-score improves to a plateau.At lower γ values, the pre-completion violation converges to a nonzero value, so the final closure step is needed to obtain a valid simplicial complex.Source: C. Algorithm Insights · p. 12, Figure 5 · p. 12

D. Co-authorship dataset

  • On the co-authorship dataset, G-SCL outperforms S-SCL and RC in recovering edges and filled triangles as graph size increases.S-SCL is comparable in edge recovery but weak on triangles; RC is weak on edges and performs better than S-SCL, though below G-SCL, on triangles.Source: D. Co-authorship dataset · p. 12, Figure 6 · p. 12

VI. CONCLUSIONS

  • The paper concludes that its BCD framework learns simplicial-complex topology from noisy, partially observed signals and converges to a stationary point of the relaxed penalized formulation.The experiments cover synthetic and real-world datasets; future work is proposed on higher-order complexes and alternative ways to relate signal properties to topology.Source: §VI · p. 12

APPENDIX A PROOF OF OPTIMALITY OF GREEDY ALLOCATION

The appendix proves the optimality of the greedy allocation rules for selecting triangles and edges. Both rules activate candidates with the smallest scores while respecting their respective constraints.

A. Proof of Lemma 2

  • For triangles, the optimal greedy allocation sets the T_budget entries with the smallest scores to one and all remaining entries to zero.The binary selection vector makes its ℓ0 count equal the number of selected entries, and the constraint requires at least T_budget selections.Source: A. Proof of Lemma 2 · p. 13

B. Proof of Lemma 3

  • For edges, the optimal allocation activates the smallest-score candidates while ensuring every observed edge is selected and respecting the edge-cardinality constraint.If at least E_min scores are negative, all negative-score edges are activated; otherwise, the E_min smallest scores determine the selection.Source: B. Proof of Lemma 3 · p. 13

APPENDIX B PROOF OF THEOREM 1 (CONVERGENCE OF BCD)

The proof establishes BCD convergence by relaxing the binary problem and applying continuous block-coordinate convergence results. In the relaxed selection-vector subproblems, the original greedy solutions remain optimal.

APPENDIX B PROOF OF THEOREM 1 (CONVERGENCE OF BCD)

  • Under suitable conditions, BCD converges to a block-coordinate minimum that is stationary for the relaxed objective.The proof uses convergence results for block-convex problems in.Source: Appendix B · p. 13
  • The proof relaxes the binary problem, solves it by alternating minimization, and verifies the conditions of [40, Th. 4] to establish convergence.The solutions from Lemmas 2–5 also solve the relaxed subproblems.Source: Appendix B · p. 13

A. Optimality of Lemmas 2-5 for the relaxed formulation

  • The relaxed matrix-variable problems are the same as those in the original formulation, so Lemmas 4 and 5 remain optimal.Source: A. Optimality of Lemmas 2-5 for the… · p. 13
  • The relaxed selection-vector problems are linear and entrywise separable apart from cardinality constraints, and their optima select entries with the smallest scores.The number of selected entries is the larger of the number of negative scores and the cardinality minimum; the resulting solutions match Lemmas 2 and 3.Source: A. Optimality of Lemmas 2-5 for the… · p. 14

B. Convergence of the relaxed formulation using BCD

Under the no-degeneracy assumption, the relaxed problem meets conditions for BCD convergence, and its limit points are stationary for the penalized formulation. The proof verifies compactness, cyclic updates, smoothness, and uniqueness of block solutions.

  • The convergence argument requires compact level sets, cyclic block updates, a continuously differentiable coupling term, and unique block solutions.Under these conditions, limit points are coordinate-wise minima and hence stationary points.Source: B. Convergence of the relaxed… · p. 14
  • Positive quadratic penalties keep the matrix variables bounded on objective sublevel sets, making those sets compact so block subproblems attain minimizers.The box constraints bound the selection vectors; the penalties are coercive in the matrix variables.Source: B. Convergence of the relaxed… · p. 14
  • With other blocks fixed, each block problem is convex; positive-definite quadratic terms give unique matrix-block minimizers, while (AS5) excludes degeneracies in selection-block solutions.The algorithm updates the four blocks in a fixed round-robin order, so each is updated infinitely often.Source: B. Convergence of the relaxed… · p. 14
  • Under (AS5), every limit point of BCD iterates is a stationary point of the penalized relaxed problem, and the solution is feasible for the penalized version of (6).Source: B. Convergence of the relaxed… · p. 15
Loading 2609.12866v1…