Spectral Contraction of Boundary-Weighted Filters on δ \delta -Hyperbolic Graphs

Le Vu Anh, Mehmet Dik, Nguyen Viet Anh · 2025

Read Spectral Contraction of Boundary-Weighted Filters on δ \delta -Hyperbolic Graphs by Le Vu Anh, Mehmet Dik, Nguyen Viet Anh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-15464.txt.

Introduction

Le Vu Anh, Mehmet Dik, and Nguyen Viet Anh design a filter for tree-like graphs in a 2025 paper. Many real networks branch like trees, and that shape can break standard graph filters. Their operator weights each edge by how far its ends drift toward the graph's outer boundary. Busemann functions give that distance in curved graph space.

The team proves a closed form bound on the operator's spectral norm. In plain terms, each pass cuts a fixed, curvature-based share of any signal's energy. The filter needs no tuned parameters and is light to run. That makes it a steady tool for signals on hidden hierarchy data.

Catalog record

CREATORLe Vu Anh, Mehmet Dik, Nguyen Viet Anh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE17 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-15464

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Spectral Contraction of Boundary-Weighted Filters on δ \delta -Hyperbolic Graphs Le Vu Anh, Mehmet Dik, Nguyen Viet Anh Abstract Hierarchical graphs often exhibit tree-like branching patterns, a structural property that challenges the design of traditional graph filters. We introduce a boundary-weighted operator that re-scales each edge according to how far its endpoints drift toward the graph’s Gromov boundary. Using Busemann functions on δ \delta -hyperbolic networks, we prove a closed-form upper bound on the operator’s spectral norm: every signal loses a curvature-controlled fraction of its energy at each pass. The result delivers a parameter-free, lightweight filter whose stability follows directly from geometric first principles, offering a new analytic tool for graph signal processing on data with dense or hidden hierarchical structure. I Introduction The past decade has seen a growing interest in graph signal processing (GSP), where the goal is to analyze data supported on irregular domains, such as networks and graphs [ 1 ] . Deep variants, such as Graph Neural Networks (GNNs), now appear in every branch of computational science and engineering, from materials discovery to epidemic forecasting [ 2 , 3 ] . This implementation has exposed key geometric mismatches between standard GNN architectures and the hierarchical nature of many real-world graphs. It motivates a search for alternative approaches based on non-Euclidean geometry. Among these, hyperbolic geometry has proven to be an effective tool for modeling graphs with dense hierarchical or tree-like structure [ 4 ] . Many real-world graphs demonstrate exponential expansion, such as taxonomies, call graphs, and transportation hierarchies. These graphs tend to be nearly tree-like in structure, making hyperbolic geometry a natural choice for modeling. Unlike Euclidean embeddings, hyperbolic representations can encode such hierarchies with significantly lower distortion. As a result, hyperbolic GNNs have demonstrated superior accuracy, robustness, and sample efficiency. This advantage has been validated in recent studies on few-shot learning [ 5 ] , temporal link prediction [ 6 ] , and deep architectures designed to mitigate the over-smoothing effect [ 7 ] . The combination of spectral filtering with hyperbolic embeddings, such as via wavelets and multi-scale designs, also strengthens this trend [ 8 ] . Beyond purely neural methods, a new class of spectral and physics-inspired models has been considered. One recent example is the work of Liu et al. (2024), which introduces a continuous geometry-aware graph diffusion framework based on hyperbolic neural partial differential equations [ 9 ] . By formulating message passing as a continuous-time diffusion process in hyperbolic space, the model leverages the natural geometric alignment of hierarchical graph data. In addition to learned representation, stability has been a priority for the recent GSP technique design, such as how the blind deconvolution mechanism aligns with graph perturbations [ 10 ] . In parallel, adaptive loss functions from signal filtering have been successfully transferred to hyperbolic GSP tasks [ 11 ] . Despite these developments, nearly all existing message-passing mechanisms remain restricted by operations within the hyperbolic manifold itself. They neglect directional cues from the Gromov boundary, a structure that governs signal behavior at large geodesic distances. So far, these asymptotic properties have only appeared indirectly, like in differentially private mechanisms [ 12 ] , deep residual architectures [ 13 ] , or open-world category discovery [ 14 ] , but not as clear edge-level weights in a GSP framework. In short, the following question remains open: How can boundary directions be explicitly embedded into local message-passing operations? We address this problem by proposing a boundary-weighted graph filter that scales each edge via a single exponential Busemann factor. This construction directly adds Gromov-boundary information without increasing the model’s parameter count. The resulting linear operator satisfies a spectral-norm bound of the form \lVert T\rVert_{2}\leq e^{-\alpha\delta} for any \delta -hyperbolic graph, where \alpha is a curvature-dependent scaling parameter. In summary, our key contributions are as follows: • Efficient boundary-aware edge weighting. We derive a vectorised, parameter-free Busemann weighting that augments graph filters with asymptotic geometry without increasing complexity. • Curvature-dependent stability guarantee. We prove that the operator contracts the \ell^{2} -energy of any input signal by at least e^{-\alpha\delta} , establishing the first explicit spectral bound linked to the graph’s hyperbolicity constant. In the remainder of this letter, Section II formalizes the graph-theoretic and geometric setup. Section III introduces the proposed boundary-weighted operator and establishes its contraction property as a function of graph curvature. Section IV concludes with discussions and directions for further theoretical development. II Problem setup We start by formalizing the negatively curved setting that initiates the proposed boundary-weighted filter. • Graph G . We work with a finite, connected, undirected graph G=(V,E) and write d_{G}(u,v) for the usual shortest–path distance. • \delta -hyperbolicity. The graph is \delta -hyperbolic if every geodesic triangle is \delta -thin. It means each side lies inside the \delta -neighbourhood of the two others. Figure 1 shows such a triangle with vertices u,v,w . The shaded corridor of width \delta visualizes the tree-like ”thinness” that provides a base for our contraction bound. • Gromov boundary \partial G . Points in \partial G are equivalence classes of geodesic rays that stay a bounded Hausdorff distance apart. They represent directions to infinity and embed the asymptotic geometry of G . • Anchor pair (o,\xi) . We fix a base vertex o\!\in\!V and a boundary point \xi\!\in\!\partial G . All boundary-aware quantities are measured relative to this reference pair. • Busemann function \beta_{o,\xi} . For every vertex v\!\in\!V \beta_{o,\xi}(v)=\lim_{t\to\infty}\Bigl[d_{G}\bigl(v,\gamma_{\xi}(t)\bigr)-t\Bigr], where \gamma_{\xi} is any geodesic ray from o toward \xi . The limit exists and is independent of the chosen ray. As a result, a 1-Lipschitz “height” of v is given along the boundary direction. • Scale parameter \alpha>0 . A positive scalar controls how strongly boundary discrepancies attenuate edge messages. In section III we show that \alpha also manages the operator’s spectral contraction. Fig. 1: A geodesic triangle in a \delta -hyperbolic graph. The shaded corridor of width \delta shows that each side stays within distance \delta of the union of the other two. This shaded region shows the tree-like geometry that initiates our boundary-weighted filter. III Boundary-weighted filter III-A Main construction We now translate the geometric basis from section II into a drop-in edge reweighting rule that can be inserted into any message-passing layer. Definition 1 (Boundary-weighted edge factor) . For every edge (u,v)\in E , define w_{\alpha}(u,v)\;=\;\exp\!\Bigl[-\alpha\,\bigl|\beta_{o,\xi}(u)-\beta_{o,\xi}(v)\bigr|\Bigr], (1) where \alpha>0 tunes how aggressively boundary divergence is penalized, and (o,\xi) is a fixed anchor pair as defined in Section II . Since \beta_{o,\xi} increases at unit speed along every geodesic ray toward \xi , the quantity |\beta_{o,\xi}(u)-\beta_{o,\xi}(v)| can be read as the vertical height gap between the two endpoints of an edge when the graph is unfolded along the boundary ray. Definition 1 therefore assigns large weights to edges that run horizontally within the same contour band and small weights to those that jump across bands. In fig. 2 , the dashed horizontal lines mark equal height levels. The highlighted edge crosses several levels, so its weight is strongly attenuated. Conversely, edges lying entirely inside one band retain almost their full influence, which is necessary for preserving the low-frequency structure encoded by the hierarchy. Fig. 2: Busemann ”height” in a \delta -hyperbolic graph. Concentric contour

Read the complete text