Dimension Reduction and Feature Extraction of Graph-Valued Data = 그래프 자료의 차원축소와 특징추출

다국어 초록 (Multilingual Abstract)

Graph-valued data represent data residing on the vertices of the graphs, which are commonly referred to as graph signals. With advancements in monitoring tools and information technology, the availability of graph-valued data from diverse sources, such as social media, sensor networks, and brain activity, has increased. This growth has driven the demand for processing such data and extracting meaningful insights across various disciplines, including economics, epidemiology, and environmental science, leading to the development of graph signal processing in the past two decades (Shuman et al., 2013).
A key distinction in analyzing graph signals, compared to classical statistical methods, is the need to account for the underlying graph structure, which is discrete, irregular, and finite. In this dissertation, we present several novel methodologies for the statistical analysis of graph signals, broadly focusing on dimension reduction and feature extraction, developed both in the vertex domain (Chapter 3) and the graph spectral domain (Chapters 4-6). Specifically, we focus on four key topics: data fitting, cross-spectral analysis, dimension reduction, and factor modeling on graphs, which are explored in detail throughout the dissertation.

In Chapter 3, we propose a quantile-based fitting method for a noisy graph signal, consisting of both the underlying signal and noise on the graph. Unlike traditional data fitting methods, such as smoothing splines or quantile smoothing splines in Euclidean space, the proposed method is designed for the graph domain, considering the inherent structure of graphs. Prevalent graph signal fitting methods rely on optimization problems with $L_2$-norm fidelity, which primarily extract mean-based features of the signal (Stankovic et al., 2019). Moreover, they cannot effectively handle various signal distributions beyond the normal distribution, such as asymmetric or heavy-tailed distributions. In contrast, the proposed method efficiently represents the underlying structure of graph signals in the presence of outliers. More importantly, it identifies various distributional structures of graph signals beyond the mean feature. We further investigate the theoretical properties of the proposed solution, including its existence and uniqueness. Through comprehensive simulation studies and real data analysis using Manhattan Taxi data and United States temperature data, we demonstrate the promising performance of the proposed method.

Chapter 4 presents a cross-spectral analysis tool for bivariate graph signals, aimed at revealing the relationship between their constituent quantities, which is not readily apparent from individual spectral analyses (Segarra et al., 2018). We define joint weak stationarity and introduce graph cross-spectral density and coherence for bivariate graph processes. Several estimators for the cross-spectral density are proposed, and we investigate their theoretical properties. Furthermore, the effectiveness of these estimators is demonstrated through numerical experiments, including simulation studies and applications to French meteorological data. As an interesting extension, we also discuss robust spectral analysis of graph signals in the presence of outliers. This chapter broadens the scope of spectral analysis for graph signals to bivariate graph signals, which plays a crucial role in developing the analysis of multivariate graph signals in the subsequent chapters.

In Chapter 5, a novel principal component analysis method in the graph frequency domain is proposed for dimension reduction of multivariate data residing on graphs. The proposed method not only effectively reduces the dimensionality of multivariate graph signals, but also provides principal components that are interpretable with respect to the graph and a closed-form reconstruction of the original data. In addition, we investigate several propositions related to principal components and the reconstruction errors. We also introduce a graph spectral envelope and optimal graph frequency scaling, which aid in identifying common graph frequencies in multivariate graph signals and estimating the normalized amplitudes of the signal bases in each dimension, respectively. We demonstrate the validity of the proposed method through a simulation study and further apply it to the analysis of G20 economic data and Seoul Metropolitan Subway passenger data.

In Chapter 6, we introduce a new factor model in the graph frequency domain for multivariate graph signals. Utilizing graph filters, the proposed model extends the frequency-domain approach of the dynamic factor model from time series to graphs, enabling a graph-aware and multiscale interpretation of factors across graph frequencies. This approach reduces the dimensionality of graph signals and improves the understanding of their structure. It also allows the use of the extracted factors as the basis for subsequent analyses, such as clustering. We describe the estimation of factors and loadings and investigate the consistency of the factor estimator. In addition, we propose two consistent estimators for determining the number of factors. The finite sample performance of the proposed method is demonstrated through simulation studies under different graph structures, including a comparison with classical factor analysis and an exploration of how the graph structure affects the results. Furthermore, we show its effectiveness by applying it to the G20 economic data, water quality parameter data from the Miho-Cheon catchment on the Geum River network, and passenger data from the Seoul Metropolitan Subway.

국문 초록 (Abstract)

본 학위논문에서는 그래프(graph) 자료의 통계적 분석을 위한 다양한 방법론을 제시하며, 넓은 의미에서 차원축소와 특징추출을 다룬다. 그래프 자료란 그래프의 정점(vertex) 위에 존재하는 자료를 의미하며, 기존의 통계분석 방법과 비교할 때 그래프의 연결구조를 고려해야 한다는 점에서 차이가 있다. 본 논문의 제3장에서는 정점 영역(vertex domain)에서 개발한 방법론을, 제4장부터 제6장까지는 스펙트럼 영역(spectral domain)에서 개발한 방법론을 다룬다. 각 장의 주요 내용은 다음과 같다.

제3장에서는 잡음이 포함된 그래프 자료에 대해 분위수 기반 적합 방법을 제안한다. 기존의 유클리드 공간(Euclidean space)에서 사용되는 적합 방법은 그래프의 연결 구조를 반영하지 못하며, 그래프 구조를 고려한 기존 방법 또한 $L_2$ 노름 기반의 자료 충실도(data fidelity)를 포함하는 목적 함수를 최적화하기 때문에 평균 기반의 특징만을 추출할 수 있어 정규분포를 따르지 않는 자료에는 적합하지 않다. 반면, 제안된 방법은 그래프의 연결 구조를 효과적으로 반영할 뿐만 아니라, 이상점이 존재하는 경우에도 로버스트한 적합 결과를 제공하며, 평균 기반의 특징을 넘어 자료의 다양한 분포적 특성을 파악할 수 있다. 제안된 방법의 이론적 성질을 규명하고, 다양한 시뮬레이션 자료뿐만 아니라 맨해튼 택시 자료 및 미국 기온 자료를 활용하여 그 우수성을 검증한다.

제4장에서는 이변량 그래프 자료에 대한 상호 스펙트럼 분석 기법(cross-spectral analysis)을 제안한다. 구체적으로, 이변량 그래프 과정(bivariate graph process)에 대해 약한 공동 정상성(joint weak stationarity), 상호 스펙트럼 밀도(cross-spectral density), 그리고 기여도(coherence)의 개념을 도입하고, 이들의 추정량을 제시한다. 또한, 해당 추정량의 이론적 성질을 분석한다. 제안된 기법의 유용성을 시뮬레이션 자료와 프랑스 기상 자료를 통해 검증하며, 이상점이 존재하는 경우 로버스트한 스펙트럼 분석에 대해서도 논의한다.

제5장에서는 다변량 그래프 자료의 차원축소를 위한 그래프 주파수 영역(graph frequency domain)에서의 주성분 분석 방법을 제안한다. 제안된 방법은 자료의 차원을 효과적으로 축소할 뿐만 아니라, 원본 자료로의 폐쇄형 복원을 제공한다. 얻어진 주성분은 그래프 구조에 기반한 해석이 가능하며, 이에 대한 이론적 성질도 함께 다룬다. 또한, 그래프 스펙트럼 엔벨로프(graph spectral envelope)와 최적 그래프 주파수 스케일링(optimal graph frequency scaling) 개념을 정의하여 자료 간에 공통으로 존재하는 주파수를 식별하고, 기저 신호에 대한 정규화된 진폭을 추정한다. 시뮬레이션 자료를 통해 제안된 방법의 유효성을 검증하고, 이를 G20 국가들의 경제 지표 및 서울 지하철 승하차 자료에 적용하여 분석을 수행한다.

마지막으로 제6장에서는 다변량 그래프 자료에 대해 그래프 주파수 영역에서의 인자모형(factor model)을 제안한다. 제안된 모형은 그래프 필터(graph filter)를 활용하여 주파수 영역에서의 다차원 시계열 자료에 대한 동적인자모형(dynamic factor model)을 그래프 위로 확장한다. 이 방법은 그래프 주파수별로 인자가 미치는 영향을 해석할 수 있다는 장점이 있으며, 차원 축소와 동시에 자료의 구조를 깊게 이해할 수 있게 한다. 또한, 인자(factor)와 적재(loading)에 대한 추정량을 제시하고, 그들의 일치성(consistency)을 증명한다. 인자의 개수를 결정하기 위한 일치성을 갖는 추정량도 제안한다. 시뮬레이션 자료를 통해 이론적 성질의 유한 표본 성능을 검토하고, 기존 인자모형과의 비교 및 분석에 사용되는 그래프 구조가 결과에 미치는 영향도 함께 분석한다. 나아가 G20 경제 지표, 금강 미호천 수질, 서울 지하철 승하차 자료에 제안된 모형을 적용하여 그 실용성과 해석 가능성을 검증한다.

목차 (Table of Contents)

• 1 Introduction 1
• 2 Background 7
• 2.1 Graph-Valued Data 7
• 2.1.1 Graphs 7
• 2.1.2 Graph Signals 10
• 2.2 Vertex Domain Processing 10
• 2.2.1 Incidence Matrix 11
• 2.2.2 Graph Laplacian 12
• 2.2.3 Graph Shift Operator 14
• 2.3 Spectral Domain Processing 17
• 2.3.1 Graph Fourier Transform 17
• 2.3.2 Graph Filters 20
• 3 Quantile-Based Fitting for Graph Signals 23
• 3.1 Introduction 23
• 3.2 Motivating Examples 26
• 3.3 Graph-Based L2 Fidelity Optimization for Graph Signal Fitting 29
• 3.4 Proposed Method 31
• 3.4.1 Quantile-Based Fitting and Its Properties 31
• 3.4.2 Penalized Iteratively Reweighted Least Squares 33
• 3.4.3 Selection of Smoothing Parameter 34
• 3.5 Simulation Study 35
• 3.5.1 Robustness to Outliers 35
• 3.5.2 Identification of Various Distributional Structures 41
• 3.6 Real Data Analysis 43
• 3.6.1 Manhattan Taxi Data 43
• 3.6.2 United States Hourly Temperature Data 45
• 3.7 Concluding Remarks 47
• 3.A Appendix of Chapter 3 49
• 3.A.1 Proofs 49
• 3.A.2 Remarks on Smoothing Parameter Selection 55
• 3.A.3 Additional Figures 57
• 4 Cross-Spectral Analysis of Bivariate Graph Signals 59
• 4.1 Introduction 59
• 4.2 Background 61
• 4.2.1 Weakly Stationary Graph Processes 61
• 4.2.2 Graph Power Spectral Density 64
• 4.2.3 Nonparametric Estimation of Graph Power Spectral Density 65
• 4.3 Cross-Spectral Analysis on Graphs 67
• 4.3.1 Jointly Weakly Stationary Graph Processes 67
• 4.3.2 Graph Cross-Spectral Density 69
• 4.3.3 Nonparametric Estimation of Graph Cross-Spectral Density 71
• 4.3.4 Graph Coherence 76
• 4.4 Practical Implementation 76
• 4.4.1 Window Design 76
• 4.4.2 Alternative Estimator for Graph Cross-Spectral Density 77
• 4.5 Numerical Experiments 79
• 4.5.1 Detection of Shared Components 79
• 4.5.2 Cross-Spectral Analysis on Meteorological Dataset 82
• 4.6 Robust Spectral Analysis on Graphs 85
• 4.7 Concluding Remarks 88
• 4.A Appendix of Chapter 4 89
• 4.A.1 Proofs 89
• 5 Principal Component Analysis in the Graph Frequency Domain 99
• 5.1 Introduction 99
• 5.2 Motivation for the Study 101
• 5.3 Background 104
• 5.3.1 PCA in the Frequency Domain 104
• 5.3.2 Stationarity of Multivariate Graph Processes 106
• 5.4 PCA in the Graph Frequency Domain 107
• 5.4.1 Proposed Method and Its Properties 107
• 5.4.2 Graph Spectral Envelope and Optimal Graph Frequency Scaling 112
• 5.4.3 Interpretation of Principal Components 113
• 5.5 Simulation Study 113
• 5.5.1 Synthetic Examples Using Two Networks 113
• 5.5.2 Comparison with Existing Methods 119
• 5.6 Real Data Analysis 120
• 5.6.1 G20 Economic Data 120
• 5.6.2 Seoul Metropolitan Subway Line 2 Data 122
• 5.7 Concluding Remarks 128
• 5.A Appendix of Chapter 5 129
• 5.A.1 Dimension Reduction Methods on Graphs 129
• 5.A.2 Proofs 132
• 5.A.3 Additional Figures 137
• 6 Graph Frequency-Domain Factor Modeling 139
• 6.1 Introduction 139
• 6.2 Background 142
• 6.2.1 Comparative Overview: PCA and Factor Analysis 142
• 6.2.2 Factor Analysis for Multivariate Time Series 143
• 6.2.3 Factor Analysis in the Frequency Domain 144
• 6.3 Graph Frequency-Domain Factor Analysis 145
• 6.3.1 Proposed Factor Model 145
• 6.3.2 Estimation 147
• 6.3.3 Interpretation of Factors and Loadings 150
• 6.3.4 Determination of the Number of Factors 151
• 6.4 Simulation Study 153
• 6.4.1 Finite Sample Performance 153
• 6.4.2 Comparison with Classical Factor Analysis 155
• 6.4.3 Effect of Graph Structure 159
• 6.5 Real Data Analysis 159
• 6.5.1 G20 Economic Data 159
• 6.5.2 Miho-Cheon Catchment Data 163
• 6.5.3 Seoul Metropolitan Subway Line 2 Data 169
• 6.6 Concluding Remarks 173
• 6.A Appendix of Chapter 6 174
• 6.A.1 Proofs 174
• 7 Concluding Remarks 203
• 7.1 Summary 203
• 7.2 Future Work 204
• 7.2.1 Locally Stationary Graph Processes 204
• 7.2.2 Network Time Series 206
• 7.2.3 Graphon Signal Processing 207
• Bibliography 211
• Abstract in Korean 229