Antonio Ortega

Kenta Yanagiya, Junya Hara, Hiroshi Higashi et al.

In this paper, we propose a compression framework for weighted graphs in which the graph topology is transmitted losslessly and edge weights are compressed lossily. A challenge in the lossy compression of edge weights is that the underlying relationships between edges are ambiguous. To address this issue, we first transform the unweighted graph into the corresponding line graph, whose nodes represent the edges of the original graph and whose edges encode the relationships between them. The line graph transform allows us to regard edge weights as a graph signal defined on the line graph. Instead of transmitting the edge-weight vector, we first transform it with a graph filter bank on the line graph. Then, quantization and entropy coding are performed on the transformed coefficients of the edge weight vector. In addition to the lossy compression method, we formalize edge smoothness on the line graph and show that it serves as a measure of the difficulty of compression. The proposed smoothness measure can be easily calculated without converting to a line graph. This provides insight into the expected compression performance of a given weighted graph. Experiments on synthetic and real-world data validate the effectiveness of the proposed method by comparing it with existing matrix preprocessing methods.

Saghar Bagheri, Gene Cheung, Tim Eadie et al.

A crucial assumption in graph signal processing (GSP) is the existence of an underlying graph that captures the pairwise similarities between nodes, allowing filters to be designed based on this graph for tasks such as denoising. For spatial-temporal data in which node-to-node similarities evolve over time, a static spatial graph is insufficient. In this paper, to represent slowly time-varying pairwise relationships, we model the graph changes in two consecutive adjacency matrices $P = W^{(2)} - W^{(1)}$ across time as a low-rank matrix. % Specifically, given an initial adjacency matrix $W^{(1)}$ at time $t=1$, we jointly interpolate a signal $x_2$ and estimate $W^{(2)}$ at $t=2$ using both a graph signal smoothness prior for $x_2$ and a low-rank prior on $¶$. We alternate optimization steps. With $W^{(2)}$ fixed, $x_2$ is interpolated by solving a linear system. Alternatively, holding $x_2$ fixed, $W^{(2)}$ is updated via proximal gradient descent (PGD). The proximal mapping of the rank term $Gamma(W^{(2)} - W^{(1)})$ is approximated in linear time using a fast orthogonal matching pursuit (OMP) algorithm that selects a sparse combination of atoms from a dictionary $cR$ formed by the outer products of $W^{(1)}$'s eigenvectors. We unroll iterations of our algorithm into layers to build a lightweight neural network for limited data-driven parameter tuning. Experiments show that our joint optimization achieves better signal interpolation compared to existing time-varying graph models.

Samuel Fernández-Menduiña, Eduardo Pavez, Antonio Ortega

Despite their theoretical advantages, spectral methods based on the graph Fourier transform (GFT) are seldom used in graph neural networks (GNNs) due to the cost of computing the eigenbasis and the lack of vertex-domain locality in spectral representations. As a result, most GNNs rely on local approximations such as polynomial Laplacian filters or message passing, which limit their ability to model long-range dependencies. In this paper, we introduce a novel factorization of the GFT into operators acting on subgraphs, which are then combined via a sequence of Cauchy matrices. We use this factorization to propose a new class of spectral GNNs, which we term L2G-Net (Local-to-Global Net). Unlike existing spectral methods, which are either fully global (when they use the GFT) or local (when they use polynomial filters), L2G-Net operates by processing the spectral representations of subgraphs and then combining them via structured matrices. Our algorithm avoids full eigendecompositions, exploiting graph topology to construct the factorization with quadratic complexity in the number of nodes, scaled by the subgraph interface size. Experiments on benchmarks stressing non-local dependencies show that L2G-Net outperforms existing spectral techniques and is competitive with the state-of-the-art with orders of magnitude fewer learnable parameters.