Modeling Sparse Graph Sequences and Signals Using Generalized Graphons
Graphons are limit objects of sequences of graphs and are used to analyze the behavior of large graphs. Recently, graphon signal processing has been developed to study signal processing on large graphs. A major limitation of this approach is that any sparse sequence of graphs inevitably converges to the zero graphon, rendering the resulting signal processing theory trivial and inadequate for sparse graph sequences. To overcome this limitation, we propose a new signal processing framework that leverages the concept of generalized graphons and introduces the stretched cut distance as a measure to compare these graphons. Our framework focuses on the sampling of graph sequences from generalized graphons and explores the convergence properties of associated operators, spectra, and signals. Our signal processing framework provides a comprehensive approach to analyzing and processing signals on graph sequences, even if they are sparse. Finally, we discuss the practical implications of our theory for real-world large networks through numerical experiments.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Generalized Graphon Process: Convergence of Graph Frequencies in Stretched Cut Distance
Graphons have traditionally served as limit objects for dense graph sequences, with the cut distance serving as the metric for convergence. However, sparse graph sequences converge to the trivial graphon under the conven…
Transfer LearningEfficient Recovery of Sparse Graph Signals from Graph Filter Outputs
This paper investigates the recovery of a node-domain sparse graph signal from the output of a graph filter. This problem, which is often referred to as the identification of the source of a diffused sparse graph signal,…
Learning to Reconstruct Missing Data from Spatiotemporal Graphs with Sparse Observations
Modeling multivariate time series as temporal signals over a (possibly dynamic) graph is an effective representational framework that allows for developing models for time series analysis. In fact, discrete sequences of …
ImputationMultivariate Time Series ImputationTime SeriesTime Series Analysis+1Dynamic Graph Neural Networks for Sequential Recommendation
Modeling user preference from his historical sequences is one of the core problems of sequential recommendation. Existing methods in this field are widely distributed from conventional methods to deep learning methods. H…
Graph AttentionGraph Neural NetworkLink PredictionSequential RecommendationGTT-Net: Learned Generalized Trajectory Triangulation
We present GTT-Net, a supervised learning framework for the reconstruction of sparse dynamic 3D geometry. We build on a graph-theoretic formulation of the generalized trajectory triangulation problem, where non-concurren…
3D geometryEvent Segmentation