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 connected to the target node; however, its appropriate selection is still a challenging problem. Therefore, most kNNGs use ad hoc selection methods for k. In the proposed method, we assume that a different k can be chosen for each node. We formulate a discrete optimization problem to seek the best k with a constraint on the sum of distances of the connected nodes. The optimal k values are efficiently obtained without solving a complex optimization. Furthermore, we reveal that the proposed method is closely related to existing graph learning methods. In experiments on real datasets, we demonstrate that the kNNGs obtained with our method are sparse and can determine an appropriate variable number of edges per node. We validate the effectiveness of the proposed method for point cloud denoising, comparing our denoising performance with achievable graph construction methods that can be scaled to typical point cloud sizes (e.g., thousands of nodes).

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 of interest, these adjacency matrices can be large, so efficient compression methods are crucial. In this paper, we propose a lossy compression of weighted adjacency matrices, where the binary adjacency information is encoded losslessly (so the topological information of the graph is preserved) while the edge weights are compressed lossily. For the edge weight compression, the target graph is converted into a line graph, whose nodes correspond to the edges of the original graph, and where the original edge weights are regarded as a graph signal on the line graph. We then transform the edge weights on the line graph with a graph filter bank for sparse representation. Experiments on synthetic data validate the effectiveness of the proposed method by comparing it with existing lossy matrix compression methods.

Neuromorphic cameras, also known as event-based cameras, can detect changes in the environmental brightness asynchronously and independently for each pixel. They output the changes, i.e., events, as 3-D (2-D pixel coordinates + time) streaming data. While event-based cameras are used in many applications because of their desirable characteristics, e.g., high temporal resolution, low latency, low power consumption, and high dynamic range, their measurements contain considerable noise due to their high sensitivity. In this paper, we propose a simple yet effective denoising method for event-based cameras based on graph spectral features. We utilize the fact that the real events captured are often densely distributed in the streaming data while the noise events are spatiotemporally sparse. In the proposed method, we first construct a graph where nodes represent events and edges represent the spatiotemporal distance between the events. Next, we calculate the Fiedler vector, which is the eigenvector of the graph operator associated with the second smallest eigenvalue. The obtained Fiedler vector is used for extracting real events directly. In the calculation of the Fiedler vector, we leverage a power method instead of the naive eigenvalue decomposition and thereby reduce its computational complexity. In experiments, we demonstrate that the proposed method effectively removes noise events from the raw events compared to alternative methods.

We propose a sampling set selection method for graph signals under arbitrary signal priors. Most approaches of graph signal sampling assume that signals are bandlimited. However, in practical situations, there exist many full-band graph signals like piecewise smooth/constant signals. Our sampling set selection method allows for arbitrary graph signal models as long as they are linear. This can be derived from a generalized sampling framework. In contrast to existing works, we focus on the direct sum condition between sampling and reconstruction subspaces where the direct sum condition plays a key role for the best possible recovery of sampled signals. We also design a fast sampling set selection algorithm based on the proposed method with the Neumann series approximation. In sampling and recovery experiments, we validate the effectiveness of the proposed method for several graph signal models.

We propose a design method of sampling matrices for graph signals that guarantees perfect recovery for arbitrary graph signal subspaces. When the signal subspace is known, perfect reconstruction is always possible from the samples with an appropriately designed sampling matrix. However, most graph signal sampling methods so far design sampling matrices based on the bandlimited assumption and sometimes violates the perfect reconstruction condition for the other signal models. In this paper, we formulate an optimization problem for the design of the sampling matrix that guarantees perfect recovery, thanks to a generalized sampling framework for standard signals. In experiments with various signal models, our sampling matrix presents better reconstruction accuracy both for noiseless and noisy situations.

We consider generalized sampling for stochastic graph signals. The generalized graph sampling framework allows recovery of graph signals beyond the bandlimited setting by placing a correction filter between the sampling and reconstruction operators and assuming an appropriate prior. In this paper, we assume the graph signals are modeled by graph wide sense stationarity (GWSS), which is an extension of WSS for standard time domain signals. Furthermore, sampling is performed in the graph frequency domain along with the assumption that the graph signals lie in a periodic graph spectrum subspace. The correction filter is designed by minimizing the mean-squared error (MSE). The graph spectral response of the correction filter parallels that in generalized sampling for WSS signals. The effectiveness of our approach is validated via experiments by comparing the MSE with existing approaches.