64 accepted papers
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 appro…
This paper develops fast graph Fourier transform (GFT) algorithms with O(nlogn) runtime complexity for rank-one updates of the path graph. We first show that several commonly-used audio and video coding transforms belong to this class of GFTs, which we denote by DCT+. Next, starting from an arbitrar…
We introduce a novel uncertainty principle for generalized graph signals that extends classical time-frequency and graph uncertainty principles into a unified framework. By defining joint vertex-time and spectral-frequency spreads, we quantify signal localization across these domains, revealing a tr…
Choosing an appropriate frequency definition and norm is critical in graph signal sampling and reconstruction. Most previous works define frequencies based on the spectral properties of the graph and use the same frequency definition and ℓ<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xli…
In real-time applications utilizing point clouds, no-reference point cloud quality assessment (NR-PCQA) methods are essential to improve the accuracy of downstream tasks. For example, in point cloud denoising, NR-PCQA results can be benchmarks for determining the optimal parameters when reference da…
Point clouds are utilized in various 3D applications such as cross-reality (XR) and realistic 3D displays. In some applications, e.g., for live streaming using a 3D point cloud, real-time point cloud denoising methods are required to enhance the visual quality. However, conventional high-precision d…
In this study, we challenge the traditional approach of frequency analysis on directed graphs, which typically relies on a single measure of signal variation such as total variation. We argue that the inherent directionality in directed graphs necessitates a multifaceted analytical approach that inc…
In most work to date, graph signal sampling and reconstruction algorithms are intrinsically tied to graph properties, assuming bandlimitedness and optimal sampling set choices. However, practical scenarios often defy these assumptions, leading to suboptimal performance. In the context of sampling an…
A basic premise in graph signal processing (GSP) is the existence of an underlying graph capturing pairwise similarities/correlations between nodes, using which graph filtering tasks such as denoising and interpolation are performed. In practice, node-to-node similarities often evolve over time, and…
This paper proposes a compression framework for adjacency matrices of weighted graphs based on graph filter banks. Adjacency matrices are widely used mathematical representations of graphs and are used in various applications in signal processing, machine learning, and data mining. In many problems…
Indirect surveys, in which respondents provide information about other people they know, have been proposed for estimating (nowcasting) the size of a hidden population where privacy is important or the hidden population is hard to reach. Examples include estimating casualties in an earthquake, condi…
In this paper, we propose a method, based on graph signal processing, to optimize the choice of k in k-nearest neighbor graphs (kNNGs). kNN is one of the most popular approaches and is widely used in machine learning and signal processing. The parameter k represents the number of neighbors that are…
As language models become more general purpose, increased attention needs to be paid to detecting out-of-distribution (OOD) instances, i.e., those not belonging to any of the distributions seen during training. Existing methods for detecting OOD data are computationally complex and storage-intensive…
Point cloud applications suffer from geometric noise caused by measurement errors induced by the point cloud acquisition system. We propose a novel graph construction method, surface-consistent non-negative kernel regression (SC-NNK), that can achieve more accurate denoising of geometry information…
Point clouds are utilized in many 3-D applications such as cross-reality (XR) and realistic 3-D display. They consist of a set of points with 3-D coordinates and associated color signals. These color signals are often perturbed by noise induced by the measurement errors of scanning devices. In this…
User generated content (UGC) refers to videos that are uploaded by users and shared over the Internet. UGC may have low quality due to noise and previous compression. When re-encoding UGC for streaming or downloading, a traditional video coding pipeline will perform rate-distortion (RD) optimization…
Modern machine learning systems are increasingly trained on large amounts of data embedded in high-dimensional spaces. Often this is done without analyzing the structure of the dataset. In this work, we propose a framework to study the geometric structure of the data. We make use of our recently int…
In numerous graph signal processing applications, data is often missing for a variety of reasons, and predicting the missing data is essential. In this paper, we consider data on graphs modeled as bandlimited graph signals. Predicting or reconstructing the unknown signal values for such a model requ…
Feature spaces in the deep layers of convolutional neural networks (CNNs) are often very high-dimensional and difficult to inter-pret. However, convolutional layers consist of multiple channels that are activated by different types of inputs, which suggests that more insights may be gained by studyi…
Spatio-temporal graph convolutional networks (STGCN) have become popular recently because they can handle structured data with dynamic temporal variations. However, the lack of interpretability limits the potential application of STGCNs. Gradient-based class activation maps (Grad-CAM) are a popular…
We propose a novel graph-based denoising method to correct the quantization error (step noise) arising in the process of generating the visual hull, a commonly used technique to synthesize free-viewpoint video. To reduce this step noise effectively, we propose two new notions of consistency, pixel v…
Active learning aims to reduce the cost of labeling through selective sampling. Despite reported empirical success over passive learning, many popular active learning heuristics such as uncertainty sampling still lack satisfying theoretical guarantees. Towards closing the gap between practical use a…
We introduce chroma subsampling for 3D point cloud attribute compression by proposing a novel technique to sample points irregularly placed in 3D space. While most current video compression standards use chroma subsampling, these chroma subsampling methods cannot be directly applied to 3D point clou…
Many applications that use point clouds, such as 3D immersive telepresence, suffer from geometric quality degradation. This noise may be caused by measurement errors of the capturing device or by the point cloud estimation method. In this paper, we propose a novel graph-based point cloud denoising a…
This paper presents a graph learning framework to produce sparse and accurate graphs from network data. While our formulation is inspired by the graphical lasso, a key difference is the use of a nonconvex alternative of the ℓ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://ww…
Learning a suitable graph is an important precursor to many graph signal processing (GSP) pipelines, such as graph signal compression and denoising. Previous graph learning algorithms either i) make assumptions on graph connectivity (e.g., graph sparsity), or ii) make edge weight assumptions such as…
Biorthogonal graph wavelet filterbanks, also known as GraphBior, are one of the most popular graph transforms used in image compression, but up to now, they could be designed based on two known admissible fundamental matrices: i) the random walk Laplacian, which heavily penalizes low degree pixels,…
Although spatio-temporal graph neural networks have achieved great empirical success in handling multiple correlated time series, they may be impractical in some real-world scenarios due to a lack of sufficient high-quality training data. Furthermore, spatio-temporal graph neural networks lack theor…
In the past decade, several multi-resolution representation theories for graph signals have been proposed. Bipartite filter-banks stand out as the most natural extension of time domain filter-banks, in part because perfect reconstruction, orthogonality and bi-orthogonality conditions in the graph sp…
Understanding complex hand actions, such as assembly tasks or kitchen activities, from hand skeleton data is an important yet challenging task. In this paper, we analyze hand skeleton-based complex activities by modeling dynamic hand skeletons through a spatiotemporal graph convolutional neural netw…
In most cases deep learning architectures are trained disregarding the amount of operations and energy consumption. However, some applications, like embedded systems, can be resource-constrained during inference. A popular approach to reduce the size of a deep learning architecture consists in disti…
Data driven graph constructions are often used in machine learning applications. However, learning an optimal graph from data is still a challenging task. K-nearest neighbor and -neighborhood methods are among the most common graph construction methods, due to their computational simplicity, but the…
Graph vertex sampling set selection aims at selecting a set of vertices of a graph such that the space of graph signals that can be reconstructed exactly from those samples alone is maximal. In this context, we propose to extend sampling set selection based on spectral proxies to arbitrary Hilbert s…
This paper proposes a coded distributed graph processing framework to alleviate the communication bottleneck in large-scale distributed graph processing. In particular, we propose a topology-aware coded computing (TACC) algorithm that has two salient features. First, we propose a topology-aware grap…
Analysis of hand skeleton data can be used to understand patterns in manipulation and assembly tasks. This paper introduces a graph-based representation of hand skeleton data and proposes a method to perform unsupervised temporal segmentation of a sequence of sub-tasks in order to evaluate the effic…
Lapped transforms are transform coding tools with basis functions that overlap across blocks in order to reduce blocking artifacts. In this work, we take the uniform line graph model interpretation of the discrete cosine transform (DCT) and extend it to lapped transforms. We first extend the conditi…
This paper considers the graph signal sampling problem when some of the selected samples are lost or unavailable due to sensor failures or adversarial erasures. We formulate a robust graph signal sampling problem where only a subset of selected samples are received, and the goal is to maximize the w…
We propose a method for graph learning from spatiotemporal measurements. We aim at inferring time-varying graphs under the assumption that changes in graph topology and weights are sparse in time. The problem is formulated as a convex optimization problem to impose a constraint on the temporal relat…
We consider the problem of sampling signals defined on the nodes of a graph. This problem arises in many contexts where the data is not structured and needs to be reconstructed from a few samples. While other graph signal sampling techniques have been recently developed in the literature, these are…
We study covariance matrix estimation for the case of partially observed random vectors, where different samples contain different subsets of vector coordinates. Each observation is the product of the variable of interest with a 0 - 1 Bernoulli random variable. We analyze an unbiased covariance esti…
This paper presents a framework for perfect reconstruction two-channel critically-sampled graph filter banks with spectral domain sampling. Graph signals have a unique characteristic: sampling in the vertex and graph spectral domains are generally different, in contrast to classical signal processin…
The first step in solving a classification problem is to collect and label a sufficient amount of training data. Given the time and cost associated to data labeling, crowdsourcing systems (e.g., Amazon Mechanical Turk) are often used. However, one of the key disadvantages of crowdsourcing systems is…
A common smoothness model used in graph based regularization approaches is to require the energy of signals to be small with respect to the graph Laplacian of the graph. In this paper, we suggest an alternative approach which can effectively incorporate the high frequency information of the graph fo…
This paper addresses the problem of finding optimal sensor placement, i.e., determining F sensor positions from N possible locations. We propose a sensor selection method based on the localization operator of graph signal processing. This method can select sensors while considering the localizations…
Current formulations of critically-sampled graph wavelet filterbanks work only for bipartite graphs where downsampling signals on either partition leads to a spectrum folding phenomenon. The lack of such a natural downsampling scheme for arbitrary graphs poses difficulties in designing filterbanks.…
Learning graph topology from data is challenging. Previous work leads to learning graphs on which the graph signals used for training are smooth. In this paper, we propose an optimization framework for learning multiple graphs, each associated to a class of signals, such that representation of signa…
When a line graph is symmetric, the associated graph Fourier transform has a fast implementation. In this paper, we extend this idea to the 2D non-separable case, where the graph of interest is a square-shaped grid. We investigate a number of symmetry types for 2D grids. Then, for each type of symme…
The GraSP toolbox aims at processing and visualizing graphs and graphs signal with ease. In the demo, we show those capabilities using several examples from the literature and from our own experiments.
The bilateral filter (BF) is a prominent tool for adaptive, structure-preserving image filtering. It can be interpreted as a graph-based filter, where the nodes of the graph correspond to image pixels and link weights correspond to filter coefficients. Graphs associated to BFs of typical sizes used…
In this paper, we extend the recent definition of graph stationarity into a definition of local stationarity. Doing so, we present a metric to assess local stationarity using projections on localized atoms on the graph. Energy of these projections defines the local power spectrum of the signal. We u…
This paper studies graph-based active learning, where the goal is to reconstruct a binary signal defined on the nodes of a weighted graph, by sampling it on a small subset of the nodes. A new sampling algorithm is proposed, which sequentially selects the graph nodes to be sampled, based on an aggres…
This paper introduces a novel framework for combining multiple weighted graphs into a single optimized weighted graph. In our framework, we first develop a statistical formulation for the graph combining problem with a maximum likelihood criterion, and derive its optimality conditions. We then use t…
The observation of frequency folding in graph spectrum during down-sampling for signals on bipartite graphs-analogous to the same phenomenon in Fourier domain for regularly sampled signals-has led to the development of critically sampled wavelet filterbanks such as GraphBior. However, typical graph-…
The advent of advanced acquisition techniques in 3D media applications has led to an increasing trend of capturing dynamic objects and scenes via 3D point cloud sequences. This form of data is composed of time-indexed frames, each consisting of a collection of points with position and color attribut…
The ever increasing quantity of user generated photos, nearly all compressed using JPEG, has created a growing storage burden on photo storage and sharing services. This creates the need for compression techniques that take JPEG compressed images as inputs. In this paper we propose two novel very lo…
We consider the problem of selecting optimal sensor placements. The proposed approach is based on the sampling theorem of graph signals. We choose sensors that maximize the graph cut-off frequency, i.e., the most informative sensors for predicting the values on unselected sensors. We study the exist…
Graph signal processing models high dimensional data as functions on the vertices of a graph. This theory is constructed upon the interpretation of the eigenvectors of the Laplacian matrix as the Fourier transform for graph signals. We formulate the graph learning problem as a precision matrix estim…
Moving object segmentation in video has uses in many applications and is a particularly challenging task when the video is acquired by a moving camera. Typical approaches that rely on principal component analysis (PCA) tend to extract scattered sparse components of the moving objects and generally f…
In this paper, we propose a graph-based lifting transform for intra-predicted video sequences. The transform can approximate the performance of a Graph Fourier Transform (GFT) for a given graph, but does not require computing eigenvectors. A predict-update bipartition is designed based on a Gaussian…
We propose a new framework for manifold denoising using the Spectral Graph Wavelet transform, which enables non-iterative denoising directly in the graph frequency domain, an approach inspired by conventional wavelet-based signal denoising methods. We theoretically justify our approach, based on the…
We give a probabilistic interpretation of sampling theory of graph signals. To do this, we first define a generative model for the data using a pairwise Gaussian random field (GRF) which depends on the graph. We show that, under certain conditions, reconstructing a graph signal from a subset of its…
Graph-based methods play an important role in unsupervised and semi-supervised learning tasks by taking into account the underlying geometry of the data set. In this paper, we consider a statistical setting for semi-supervised learning and provide a formal justification of the recently introduced fr…
Image denoising is an under-determined problem, and hence it is important to define appropriate image priors for regularization. One recent popular prior is the graph Laplacian regularizer, where a given pixel patch is assumed to be smooth in the graph-signal domain. The strength and direction of th…
Spectrum sensing is an essential functionality of cognitive radio wireless networks (CRWNs) that enables detecting unused frequency sub-bands for dynamic spectrum access. This paper proposes a compressed spectrum sensing framework by (i) constructing a sparsity basis in wavelet domain that helps com…