PaperlayerView exact revision on arXiv

Source-linked AI summary

Signal-Aware Cayley Completion: Choosing Between an Exact and a Lossy Abelian Host

Rigobert Fokam Soup, Laurent Bitjoka

arXiv:2609.01523v1eess.SP

TL;DR

Exact graph Fourier analysis can require a larger host, while completion keeps the vertex count fixed at the cost of perturbing the graph. The paper proposes a linear-time routing procedure and tests edited-edge energy as a signal-aware completion criterion. Energy-based selection recovers 61.3% of the available performance gap, though the experiments do not establish that the effect persists beyond eight vertices.

  • Problem

    Exact group-based Fourier analysis requires either enlarging a graph into an abelian Cayley host or perturbing it through completion, creating a trade-off between host size and signal fidelity.

    Source: §1 · p. 2

  • Method

    The paper gives a linear-time procedure for routing between isometric embedding and completion, and evaluates edited-edge Dirichlet energy for choosing among completions.

    Source: §1 · p. 2, §12 · p. 17

  • Results

    61.3% of the available performance gap is recovered by least-energy selection among equal-cost completions, while the criterion is not strictly monotone and the router takes the exact branch on real payment data.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Completion cost alone does not predict signal effect; edited-edge energy is the paper’s empirical selection criterion, while real anti-money-laundering data show no gain over maximum degree.

    Source: §1 · p. 2, §12 · p. 17

    The selection criterion degrades markedly at n = 8, so the paper makes no claim that it persists on larger graphs.

    Source: §11 · p. 17

Abstract

from arXiv · show

Group-embedding graph signal processing buys exact Fourier analysis either by enlarging the domain until a graph embeds isometrically into an abelian Cayley graph, or by perturbing the graph until it is one. We give a linear-time procedure that chooses between the two, and study the criterion governing the lossy branch. We prove that the perturbation of the Dirichlet form is exactly the signed sum of the edited-edge energies, and is bounded in modulus by their total, into which the combinatorial cost of the completion does not enter. We confirm experimentally that this energy predicts signal fidelity strongly though not strictly monotonically (Spearman rho = -0.79 on an instance where the completion, and hence the cost, is held fixed), while the cost itself carries no information about it. Selecting among completions of identical cost by this energy recovers 61 percent of the available performance gap on the exhaustive range, on a sample too small to establish that the effect persists beyond eight vertices. On real payment data the router takes the exact branch everywhere; on real anti-money-laundering data the completion invariant is a re-encoding of maximum degree and is not distinguishable from it, and the linear-time bound it rivals is shown to have a blind spot on near-complete graphs.

1. Introduction

The paper frames exact graph Fourier analysis as a choice between enlarging the host and editing the graph, then separates structural routing from signal-aware completion selection. Its findings show that edited-edge energy, rather than completion cost, tracks signal fidelity, while real-data tests expose limits of the structural bound.

1. Introduction

  • The isometric route preserves the graph and embeds it in an abelian Cayley host, whereas completion keeps order n by editing edges.For irregular graphs, the isometric host order can reach 2n−1; the completion route pays in perturbation instead.Source: §1 · p. 2
  • Circular convolution on a finite non-periodic signal is equivalent to adding the path’s wraparound edge, whose artefact depends on the endpoint samples.This illustrates why edge count alone does not describe the signal cost of completion.Source: §1 · p. 2
  • The routing decision depends on graph structure and runs in linear time, while choosing among completions depends on the signal.The paper studies these as separate questions: which route to take, and which completion to use when editing.Source: §1 · p. 2
  • 61.3% of the available performance gap is recovered by choosing the least-energy completion among equal-cost options, at no search cost.The criterion is experimentally strong but not strictly monotone, with Spearman ρ = −0.79 when the completion is held fixed.Source: §1 · p. 2, Figure 1 · p. 3, Figure 2 · p. 4
  • On real payment data the router sends every component to the isometric branch, while the anti-money-laundering completion invariant re-encodes maximum degree.The linear-time bound provides no added value over degree on that dataset and has a blind spot on near-complete graphs.Source: §1 · pp. 2–3

2. Related work

Prior work supplies graph-signal transforms, structured-host embeddings, and algebraic tools, but the paper’s focus is a single minimal-edit abelian host and a signal-aware criterion for choosing edits. Its preliminaries define the edit and host-order quantities used in that analysis.

2.1. Graph signal processing

  • Graph signal processing work covers Laplacian and shift-based spectral methods, wavelets, and sampling; group embedding makes the host transform an exact finite-group Fourier transform.The cited group-embedding approach supplies exact Parseval, convolution, and unitary translation properties.Source: §2.1 · p. 5

2.2. Circulant structure

  • Circulant-graph work builds filtering and filterbanks or decomposes graphs into cyclic pieces, while this paper seeks one minimal-edit abelian host and an invariant for choosing edits.The paper’s target is a host of arbitrary group structure rather than a decomposition into cyclic components.Source: §2.2 · p. 5

2.3. Isometric embedding into structured hosts

  • Isometric-embedding literature enlarges the host for exactness; this paper instead perturbs the graph through completion, treating the routes as endpoints of a trade-off.The cited literature includes hypercube, Hamming-graph, scale, and related structured-host embeddings.Source: §2.3 · p. 5

2.4. Algebraic background

  • The algebraic background includes Cayley and vertex-transitive graphs, sum-free-set bounds, Smith normal form, and the census ordering used by prior work.The passage distinguishes vertex transitivity from being a Cayley graph.Source: §2.4 · p. 5

3. Preliminaries

  • The preliminaries define γ△ as the minimum edit distance over abelian Cayley representations, with γ+ restricting the minimum to additions; γ△ is zero exactly for abelian Cayley graphs.The paper computes these exactly through n ≤ 7 and uses local search beyond that range; its signal-specific Dirichlet-form identity differs from uniform coarsening and sparsification guarantees.Source: §3 · pp. 6–7

4. The two branches and the router

The paper presents isometric embedding, completion, and a fallback as three branches, with a structural linear-time router and a separate fidelity-based threshold for deciding whether completion is tolerable. The signal-aware threshold can change the route suggested by structure alone.

4. The two branches and the router

  • The three options are exact isometric embedding, fixed-order completion with perturbation, or fallback to matrix graph signal processing when completion is also too costly.The isometric branch has no perturbation; the completion branch pays in both edge edits and signal fidelity.Source: §4 · p. 7
  • A fidelity threshold, rather than γ alone, governs whether completion is acceptable, using edited-edge signal energy relative to the signal’s Dirichlet energy.The quantities come directly from the edited set and signal statistics, without spectral computation; η = 0.25 is calibrated on these instances, not proposed as universal.Source: §4 · pp. 7–8
  • For smooth signals with approximately equal edgewise second moments, the fidelity ratio reduces to edited-edge fraction weighted by relative energy on edited edges.The paper instantiates η = 0.25 as roughly a quarter of the signal’s own Dirichlet energy displaced by the edit.Source: §4 · p. 8
  • Cycle rank and the degree bound tri(G) = max(0, n∆/2m − 1) form the linear-time structural router.This criterion does not incorporate signal fidelity, which explains why Zachary’s karate club is routed to completion in Table 1 but to Branch 3 when fidelity is considered.Source: §4 · p. 8, Table 1 · p. 8
  • The structural route’s karate-club example contrasts a completion host of order 34 with an isometric host exceeding 8 × 10^9.The isometric pipeline reports k = 33, and the passage notes that the later section accounts for the completion’s fidelity cost.Source: §4 · p. 8

5. Why γ cannot be the criterion

With completion cost held constant, edited-edge Dirichlet energy is strongly associated with host signal fidelity, though not monotonically. The paper explains this criterion through an exact signed perturbation identity and bounds, while noting that convolution-error guarantees remain open.

5. Why γ cannot be the criterion

  • Host performance falls from 16.38 to 10.40 dB as Eedit grows, with Spearman ρ = −0.79, while γ stays constant and carries no information about signal effect.The association is strong but not strictly monotone; the two largest energies recover by 0.3 dB.Source: §5 · p. 9
  • The host ties the Laplacian within half a decibel at Eedit = 0, while an 8 × 8 grid example ranges from a 16.17 dB host gain to a 12.8 dB host loss.The authors frame an abelian host's value as structural—exact Parseval, convolution, and unitary translation—not improved mean-squared error.Source: §5 · pp. 9–10

5.1. Why this quantity, and not another

  • The edited-edge Dirichlet energy is exactly the signed perturbation of the Dirichlet form, whose modulus is bounded by the total edited-edge energy.For a signal smooth on G, its energy on H is at most λ∥x∥2 + Eedit(x); the edge-count cost γ does not appear in the identity.Source: §5.1 · p. 10
  • The signal-free bound ∥LH − LG∥2 ≤ 2 maxv degF(v) implies each Laplacian eigenvalue moves by at most that amount.Edits spread across vertices are spectrally gentler than edits concentrated on a hub, even at the same γ.Source: §5.1 · p. 10
  • The paper leaves open a convolution-theorem error bound: the proposition controls quadratic forms, not eigenvectors, and general completions need not provide a spectral gap.The authors identify eigenvector perturbation as the part that enters filtering error.Source: §5.1 · pp. 10–11
  • Across three Eedit values, host SNR decreases with ideal low-pass, Tikhonov, and heat-kernel filters, while the seven-signal association remains strong but not monotone.For Tikhonov, host SNR is 17.14 → 15.34 → 10.10 dB; for heat kernel, it is 16.97 → 15.37 → 11.12 dB.Source: §5.1 · p. 11

6. Choosing among equally cheap completions

Across the tested filter and noise settings, selecting the completion with the least edited-edge energy beats random selection, but the criterion weakens with graph size. Its evidence supports use on the exhaustive range, not a claim that the effect persists at larger sizes.

6. Choosing among equally cheap completions

  • 89.2% of the 120 instances have ρ < 0, with a Wilson 95% interval of [82.3%, 93.6%].The sign of the association is established, but its exact rate is not.Source: §6 · p. 11
  • Across nine filter-bandwidth and noise-level combinations, ρ is negative and arg min Eedit beats random selection in all nine.The criterion is strongest when filter width matches signal bandwidth; it is insensitive to noise and sensitive to bandwidth.Source: §6 · pp. 11–12
  • The test uses 120 graph-signal instances from 40 sampled graphs, with γ and |F| constant within each instance and regret measured against the best available completion.The underlying pool contains 587 of 965 connected six- and seven-vertex graphs with at least three distinct minimum-cost completions; signals are smooth on the original graph.Source: §6 · p. 11, Table 3 · p. 12
  • A mean regret of 1.45 dB remains against the best available completion, so the criterion is not optimal.The authors leave identifying a better predictor open.Source: §6 · p. 12
  • At n = 8, point estimates degrade substantially, but eight instances per column leave the proportions statistically indistinguishable.The authors report the scaling result only as an indication, not a measurement.Source: §6 · p. 12, Table 4 · p. 12
  • The authors verify the selection criterion on the exhaustive range but report no evidence that it survives to graph sizes of practice.At n = 8 it remains an improvement, but a small one.Source: §6 · pp. 12–13
  • The proposed explanation is that the identity controls the quadratic form, not eigenvectors, while competing hosts increasingly differ in eigenvector structure as n grows.Accounting for eigenvectors or establishing the criterion at scale is identified as an open problem.Source: §6 · p. 13
  • On a circulant host of order 60, denoising is 24.82 dB for E = 1.09, 5.39, and 14.86, 10.69 dB at E = 25.75, and −0.01 dB at E = 241.09.Performance is flat at low energy and collapses past a threshold, so Eedit is an admissibility filter rather than a ranking.Source: §6 · p. 13

7. Experimental setup

The experiments compare denoising with matched spectral-coefficient counts and use a specific graph-based signal and noise setup. The real-data pipelines construct simple graphs from payment and laundering records, with additional projection used for the latter.

7. Experimental setup

  • Synthetic signals are unit-mean-square, corrupted with white Gaussian noise, and denoised using the same number of spectral coefficients in both bases.Reported figures average over the stated number of independent noise realisations; low-pass filtering keeps host characters with the smallest Laplacian eigenvalues.Source: §7 · p. 13
  • Keeping the lowest discrete Fourier transform indices is correct only when S = {±1}; otherwise it gives badly misleading results.Source: §7 · p. 13
  • PaySim is reduced to an undirected simple customer-to-customer graph, excluding degree-one merchant leaves and balance columns identified as a source of label leakage.Statistics use the first 20 simulation steps.Source: §7 · p. 13
  • IBM AML HI-Small transaction blocks are parsed as undirected simple graphs, identifying nodes by (bank, account) pairs and dropping self-loops.The free-text description following each typology name is discarded.Source: §7 · pp. 13–14
  • The co-counterparty projection joins accounts that share a neighbor in the account graph, while skipping vertices of degree above 200.This avoids a single hub contributing a clique on its whole neighborhood.Source: §7 · p. 14

8. Real data I: payment networks route to the exact branch

The payment data form forests of stars, so every component takes the isometric branch and is solved exactly with a provably minimal host. The largest component is a 94-vertex star.

8. Real data I: payment networks route to the exact branch

  • Among 19,392 components with at least eight vertices, none contains a cycle; the largest component has 94 vertices.Across the reported run, the graph has 410,677 accounts, 357,729 edges, and 52,948 components.Source: §8 · p. 14
  • The largest component has 94 vertices and is exactly K1,93, with minimal isometric host order ν = 186 and excursion ratio ε = 94/186 = 0.505.Its maximum degree is 93; the reported acyclic, connected structure and degree force it to be a star.Source: §8 · p. 14
  • Every payment-graph component is routed to the isometric branch, yielding exact solutions with provably minimal hosts and no completion, perturbation, or distortion.The account-level graphs are forests of stars, with cycle rank zero throughout.Source: §8 · p. 14

9. Real data II: a negative result on laundering typologies

On IBM AML HI-Small, the completion invariant distinguishes hub-dominated typologies no better than the linear-time degree bound, while maximum degree does slightly better. The typologies have differing median invariant values, but the data also contain labeling and connectivity artefacts.

9. Real data II: a negative result on laundering typologies

  • The dataset contains 370 labelled laundering subgraphs across eight typologies; γ△ is computed exactly for 232 instances within exhaustive range and by search beyond it.Source: §9 · p. 14
  • The invariant orders the typologies sensibly, with median γ△ values of 0.000 for CYCLE and BIPARTITE, 0.125 for RANDOM, and 0.500 for STACK.Source: §9 · p. 14
  • On the binary hub-typology task, γ△ and the linear-time degree bound each attain 85.4% accuracy with no false positives, while maximum degree does slightly better.γ△ correlates with maximum degree at r = 0.872; all three exceed the 50.5% majority-class baseline.Source: Table 5 · p. 15, §9 · p. 15
  • Other tested invariants separate the classes considerably less well, indicating that the degree bound’s performance is not merely because the task is easy.Source: §9 · p. 15
  • After transaction directions are symmetrised, 14 of 54 CYCLE-labelled blocks contain no cycle; BIPARTITE and STACK blocks are disconnected in 63% and 60% of cases, respectively.Source: §9 · p. 15

10. A blind spot in the linear-time bound

Projecting accounts that share a counterparty can turn star-like structure into complete graphs, which pass the linear-time degree triage despite being near-complete. The resulting low score therefore cannot distinguish well-structured graphs from graphs that are cheap simply because they are complete.

10. A blind spot in the linear-time bound

  • On PaySim steps 1–5, all 92 projected components with at least eight vertices pass completion triage, making a 100% pass rate vacuous.The projection has 2,413 nodes and 18,838 edges.Source: §10 · p. 16
  • The co-counterparty projection of a disjoint union of stars is a union of complete graphs on the leaf sets, plus one isolated vertex per centre.For K1,q, the projection is Kq plus an isolated vertex.Source: §10 · p. 16
  • The largest projected component has 46 vertices and is K46, where γ△=0 because a complete graph is already an abelian Cayley graph.For regular graphs, the degree bound n∆/2m − 1 is zero, placing complete graphs at the bottom of the triage scale.Source: §10 · p. 16
  • Near-complete graphs can sit at the bottom of the triage scale, so deployment should screen them before trusting a low score.The bound cannot distinguish a graph cheap because it is well structured from one cheap because it is complete.Source: §10 · p. 16

11. Limitations

Completion can reduce host size while imposing severe graph perturbation, and the paper offers an empirical signal-fidelity criterion rather than an error-propagation theorem. The experiments also leave scaling and filter generality unresolved.

11. Limitations

  • A cyclic-host completion of karate club uses 70 edits on 78 edges (γ△≈0.897), so the paper identifies Branch 3 as the correct routing decision.The host shrinks from order 233 to order 34, but the graph remains severely perturbed.Source: §11 · p. 16
  • The paper gives no error-propagation bound connecting host metric distortion to convolution error; deriving one is left for future work.The proposed bridge would control convolution error using a distortion-dependent bound; the companion paper [42] shows edit count and bi-Lipschitz distortion are independent invariants.Source: §11 · p. 17
  • The selection criterion degrades markedly at n = 8, PaySim conclusions rely on reported run statistics, and learned or data-adaptive denoising filters were not tested.The paper makes no claim that the selection effect persists to large graphs.Source: §11 · p. 17

12. Conclusion

The paper presents a linear-time two-branch procedure and finds that edited-edge Dirichlet energy, rather than completion cost, guides the lossy branch. Its evidence supports structural exactness on graphs with small hosts, not a general denoising improvement.

12. Conclusion

  • The paper gives an operational two-branch procedure routed in linear time, with edited-edge Dirichlet energy predicting signal effects where combinatorial completion cost does not.On real payment data the router takes the exact branch everywhere; on real laundering data the invariant adds nothing to a linear-time degree bound, which has a blind spot on near-complete graphs.Source: §12 · p. 17
  • The framework’s supported value is structural exactness for graphs admitting small hosts and a linear-time verdict for graphs that do not, not general denoising improvement.The experiments do not support a claim of general improvement in denoising performance.Source: §12 · p. 17
  • The authors identify scaling the selection criterion, controlling eigenvector perturbation, and jointly optimizing γ and Eedit as future directions.They also propose automatic detection of near-complete inputs, using complement density as a cheap flag.Source: §12 · pp. 17–18

Funding

  • The research received no specific grant from funding agencies in the public, commercial, or not-for-profit sectors.Source: Funding · p. 18

Data availability

  • Experiment scripts and derived data are deposited on Zenodo, and both datasets are public.The datasets are cited as and.Source: Data availability · p. 18
Loading 2609.01523v1…