GraphOmakase

26년 4월 3주차 그래프 오마카세

omakasechef

12 Apr 2026 — 16 min read

Learning Laplacian Forms for Graph Signal Processing via the Deformed Laplacian

Learning the graph Laplacian from observed data is one of the most investigated and fundamental tasks in Graph Signal Processing (GSP). Different variants of the Laplacian, such as the combinatorial, signless or signed Laplacians have been considered depending on the type of features to be extracted from the data. The main contribution of this paper is the introduction of a parametric Laplacian, called the deformed Laplacian, defined as a quadratic matrix polynomial that provides a parametric dictionary for graph signal processing. The deformed Laplacian can be interpreted as the generator of a parametric linear reaction-diffusion dynamics on graphs, capturing the interplay between diffusive coupling and nodal reaction effects. It is a parametric polynomial matrix that enables the design of novel topological operators tailored to both the underlying graph structure and the observed signals. Interestingly, we show that several Laplacian variants proposed in the literature arise as special cases of the deformed Laplacian. We then develop a method to jointly learn the deformed Laplacian and the graph signals from data, showing how its use improves signal representation across a broad class of graphs compared to standard Laplacian forms. Through extensive numerical experiments on both synthetic and real-world datasets, including financial and communication networks, we assess the benefits of the proposed method in terms of graph signal reconstruction error and sparsity of the representation.

arXiv.orgStefania Sardellitti

Keywords

Graph Signal Processing
Generalized Deformed Laplacian
Spectral Properties
Deformed Graph Signal Processing

클러스터 구조가 있으면 조합 라플라시안(Combinatorial Laplacian), 이분 그래프(Bipartite Graph)라면 부호 없는 라플라시안(Signless Laplacian), 협력/적대 관계가 섞인 부호 그래프(Signed Graph)라면 부호 라플라시안(Signed Laplacian). 이와 같이 그래프 신호처리의 첫 시작점은 데이터에 알맞는 라플라시안 형태를 선택해야 합니다.
당연하게도 현실 데이터는 이 구분이 깔끔하게 맞아 떨어지지 않는 경우가 훨씬 많습니다. 클러스터와 이분 구조가 동시에 나타나거나, 어느 쪽인지조차 모르는 상태에서 분석을 시작해야 할 때도 있습니다.
처음 그래프 신호 처리를 접하시거나 다루시는 분들에게는 과연 어떤 라플라시안 행렬을 활용해야 하지? 라는 질문이 자연스럽게 드실 겁니다. 이번 주 오마카세에서 소개할 논문은 바로 이 지점에 정면으로 답합니다.

💡

처음부터 하나의 연산자로 통일해두고, 데이터로부터 가장 적합한 형태를 학습하면 된다.

기존 GSP 방법론은 적합한 라플라시안 형태에 대한 사전 지식을 전제로 설계되어 있습니다. 이 논문은 그 전제를 걷어내고, 단 하나의 파라메트릭 연산자로 여러 라플라시안 형태를 포괄하면서 데이터로부터 최적의 형태를 자동으로 학습하는 프레임워크를 제안합니다.
개인적으로 정말 존경하는 그래프 및 위상 신호처리의 대가이신 Stefania 교수님의 논문인 만큼 많은 구독자 여러분분들께 정독을 권장하는 논문입니다. 어려운 요소들을 최대한 제하고 핵심 부분만 간추려서 전달해드리겠습니다.

Deformed Graph Laplacian, DGL : 변형 라플라시안

논문의 핵심 아이디어는 생각보다 간결합니다. 기존의 여러 라플라시안 변형들을 아우르는 2차 행렬 다항식 하나를 (통일하여) 정의하는 것입니다.

$$
L_{\mathrm{DF}}(r) = (D - I) r^2 - A r + I
$$

여기서 r은 실수 파라미터, A 는 인접 행렬, D는 차수 행렬입니다. 이 2차 행렬 다항식은 r=0일 때 항등 행렬 $\mathbf{I}$ 가 되어 항상 regular임을 보장합니다. (즉, 고유값 0이 존재하지 않습니다.)
이 단순해 보이는 수식 안에 기존 라플라시안 세 가지(조합, 부호화) 가 모두 특수한 경우로 포함됩니다.

여기서 중요한 수학적 포인트가 있습니다. 이 대응 관계는 단순히 행렬이 같다는 것을 넘어, 각 라플라시안의 고유벡터가 다항식 고유값 문제의 해로서 $ \mathbf{L}_\text{DF}(r) $의 커널에 포함된다는 것입니다.
- 예를 들어 그래프가 이분 구조를 가지면 r=−1이 $ \det(\mathbf{L}_\text{DF}(-1)) = 0 $을 만족하는 고유값이 되고, 그 고유벡터의 부호 패턴이 이분 분리 구조를 드러냅니다. 마찬가지로 부호 균형 그래프(balanced signed graph)에서는 r=1이 고유값이 되며, 해당 고유벡터가 두 커뮤니티를 분리합니다.
즉, 기존에 세 가지 선택지로 나뉘어 있던 것이 이제 r이라는 하나의 연속적인 knob로 통합됩니다. r=1과 r=−1 사이 어딘가 실제 데이터에 가장 잘 맞는 표현이 될 수도 있으며, 어떤 표준 형태에도 해당하지 않는 실수 구간 위의 $ r^\star $이 최적값일 수 있습니다.

Reaction-Diffusion 과정으로의 재해석

변형 라플라시안은 단순한 수학적 트릭이 아니라, 물리적으로도 직관적인 해석을 갖습니다. 이 연산자는 순전히 데이터 표현 도구로만 보던 라플라시안을 그래프 위에서의 파라메트릭 반응-확산(Reaction-Diffusion) 과정의 생성자(generator)로 이애하는 새로운 인사이트를 제공합니다.
연속 공간에서의 반응-확산 방정식은 다음과 같습니다.

$$
\frac{\partial \phi(x,t)}{\partial t} = \eta \nabla^2 \phi(x,t) + h(x,t)
$$

이를 그래프 위로 이산화하고 각 노드의 국소 반응 항을 모델링하여 위 식에 대입하면 전체 다이나믹스가 정확하게 변형 라플라시안으로 표현됩니다.

$$
\frac{d\phi(t)}{dt} = - L_{\mathrm{DF}}(r),\phi(t)
$$

직관적으로 각 노드의 신호 변화는 확산, 반응의 균형으로 결정됩니다. 여기에서 확산은 이웃 노드들의 신호 평균 방향으로 당겨지는 힘을, 반응은 노드 자체의 차수에 비례하는 국소적 증폭 또는 감쇠를 의미합니다.
- 여기서 파라미터 r은 이 두 힘의 상대적 강도를 조절합니다. r이 클수록 이웃 간 확산이 강해지고, r이 특정 값을 갖게 되면 국소 반응 항이 지배적인 형태로 전환됩니다. 이 관점은 동적 그래프나 시계열 신호 분석에서 유용한 해석 틀을 제공합니다.
기존의 순수 확산 모델(조합 라플라시안)은 이 프레임워크의 특수한 경우에 불과합니다.

Deformed Graph Fourier Transform : 변형 그래프 푸리에 변환

기존 GSP에서 그래프 푸리에 변환(GFT)은 조합 라플라시안의 고유벡터 $\mathbf{U}$를 기저로 정의됩니다.
변형 라플라시안은 r에 따라 고유벡터$ \mathbf{U}(r)$가 달라지므로, 이를 스펙트럼 기저로 사용하면 변형 그래프 푸리에 변환(DGFT)을 정의할 수 있습니다. 신호 $\mathbf{x}$가 K개의 DGFT 계수만으로 표현될 때 이를 대역 제한(band-limited) 신호라고 지칭합니다.
논문의 소규모 합성 실험 하나가 이를 잘 보여줍니다. 11개 노드로 구성된 준이분(quasi-bipartite) + 클러스터 혼합 그래프에서, K=4개 계수로 신호를 복원하는 오차를 r 구간 [−1,2]에 걸쳐 탐색했을 때, r=0.1 근방에서 오차가 최소가 되었습니다.
조합 라플라시안(r=1)이나 부호 없는 라플라시안(r=−1) 모두 이보다 높은 오차를 보였습니다. 이는 해당 그래프가 어느 표준 형태로도 깔끔하게 설명되지 않으며, 두 구조의 중간 어딘가에 해당하는 r 값이 최적이었음을 의미합니다.

라플라시안 형태와 신호 표현의 동시 학습

논문의 실질적인 기여는 rr r과 신호 표현을 동시에 데이터로부터 학습하는 프레임워크입니다. M개의 그래프 신호 $\mathbf{X} = [\mathbf{x}^{(1)}, \ldots, \mathbf{x}^{(M)}]$가 주어졌을 때, 다음 최적화 문제를 풀게 됩니다.

$$
\min_{S,\, r,\, U(r)} \; (1 - \gamma)\,\operatorname{tr}\!\big(X^\top \mathrm{L_{DF}}(r)\, X\big)
+ \gamma \,\| X - U(r) S \|_F^2
$$

첫 번째 항 $\text{tr}(\mathbf{X}^T\mathbf{L}_\text{DF}(r)\mathbf{X}) $ 는 인접 노드 간 신호 변화의 총합을 나타내는 quadratic form입니다. 이를 최소화하는 것은 신호가 그래프 구조에 대해 부드럽게 분포하도록 스무딩 효과를 유도합니다.
두 번째 항 $\gamma \,\| X - U(r) S \|_F^2$은 기저 벡터만으로 원신호를 얼마나 잘 복원하는지를 측정합니다. 여기서 $\gamma \to 0 $ 이면 스무딩 우선, $ \gamma \to 1$ 이면 데이터 피팅 우선으로 두 목표의 균형을 조절합니다. 다음 항을 최소화하면 희소한 스펙트럼 표현으로 아웃풋을 강제합니다.

Algorithm 1 : Line search for approximated optimal r ($r^{star}$)

이 문제는 non-convex이기 때문에, 본 논문에서는 r에 대한 선형 탐색을 통해 효율적인 근사 해를 구하는 알고리즘(Algorithm 1)을 제안합니다.
- 구체적으로, $ r_0 = -\alpha $에서 시작하여 간격 $ \beta $로 증가시키면서, 각 r에 대해
  $ \mathbf{L}_{\mathrm{DF}}(r) \succeq 0 $ 조건을 만족하는 경우에만 계산을 수행합니다.
- 이때, 상위 K개의 DGFT 계수를 유지하여 복원된 신호를 구성하고, 해당 신호에 대한 목적 함수 값을 계산한다. 최종적으로, 가장 작은 재구성 오차를 갖는 $ r^\star $를 선택합니다.

논문은 합성 데이터와 실제 데이터 두 가지 측면에서 검증합니다.

세 종류의 합성 그래프(클러스터 그래프, 이분 그래프, 부호 균형 그래프)에 대해 각각의 표준 라플라시안 고유벡터로 생성한 신호를 입력으로 사용했습니다. 해당 알고리즘이 올바른 라플라시안을 찾아가는지를 위주로 검증을 수행합니다.
- γ 변화에 따른 최적 $r^\star$ 추이를 보면, 클러스터 그래프와 부호 그래프는 데이터 피팅 우선일수록(^\star \to 1\)로 수렴합니다.
- 이분 그래프는 $\gamma$ 변화에 무관하게 $r^\star = -1$을 안정적으로 유지합니다. 즉, 알고리즘이 최적의 라플라시안에 대응하는 r 값을 데이터로부터 회복해냄을 보여줍니다.
더 어려운 시나리오로, 위상이 시간에 따라 변화하는 동적 그래프(랜덤 그래프 → 클러스터 그래프 → 이분 그래프, 40 타임스텝)에서 복원 오차를 비교했습니다.
- 변형 라플라시안은 전 구간에 걸쳐 조합 라플라시안과 부호 없는 라플라시안보다 낮은 NMSE를 달성했습니다.
- 고정된 라플라시안 형태는 그래프 위상이 바뀌는 순간부터 표현력이 저하되지만, 변형 라플라시안은 각 시점에서 r을 다시 탐색함으로써 이에 적응합니다.

실제 데이터셋으로는 S&P500 주식 네트워크와 코펜하겐 통신 네트워크를 사용하여 현실 그래프가 표준 라플라시안으로 설명되는지를 검증하였습니다.
- 실험 결과, 주식 네트워크에서는 전 관측 기간에 걸쳐 최적 $r^\star$는 부호 없는 라플라시안에 해당하지 않았으며, 그래프가 이분 구조로 설계되었음에도 실제 신호 표현에 최적인 연산자 형태는 달랐습니다. 특히 2020년 1월 이후 COVID-19 충격 시기에 NMSE가 하락했는데, 이는 시장 구조가 급격하게 변화하는 시기에 신호의 스펙트럼 표현이 오히려 더 희소해졌음을 의미합니다.
- 코펜하겐 통신 네트워크의 경우, 스파시티 K가 증가할수록 NMSE가 감소하는 명확한 trade-off가 확인되었으며, $\gamma \to 1$일수록 오차가 감소합니다. 역시 최적 $r^\star$는 모든 $\gamma$ 구간에서 조합 라플라시안 또는 부호 없는 라플라시안에 해당하는 표준값에 수렴하지 않았습니다. 현실 통화 네트워크는 어느 형태로도 완전히 설명되지 않는다는 점을 실증적으로 보여주었습니다.

이번 논문이 제시하는 관점을 한 문장으로 압축하면 이렇습니다.

💡

어떤 라플라시안을 선택할 것인가의 질문을 던지는 것이 아니라, 데이터로부터 가장 적합한 라플라시안 형태를 학습할 수 있는가에 대해 고민하라.

이 질문의 전환은 그래프 구조를 바꾸기 전에 그 위에서 정의하는 함수를 먼저 다시 바라보아야 한다는 이전 오마카세 인사이트의 연장선에서 연산자 자체를 고정된 선택이 아닌 학습의 대상으로 만드는 구체적인 방법론을 제시합니다.
물론 현재 프레임워크는 무방향 그래프에 국한되어 있고, 선형 탐색 방식은 대규모 그래프에서 계산 비용이 증가할 수 있습니다. 또한 r이 단일 스칼라이기 때문에 그래프 내 부분 구조가 서로 다른 복합적 위상에 대해서는 표현력의 한계가 있을 수 있습니다.
이러한 방향의 확장 — 예를 들어 노드별 또는 엣지별로 r을 다르게 부여하는 공간 가변 변형 라플라시안 — 은 흥미로운 후속 연구 방향이 될 것으로 보입니다. GSP 작업에서 라플라시안 선택이 막막하게 느껴진다면, r을 학습하는 것도 하나의 선택지로 고려해보시면 좋겠습니다.
더 깊이 이해하고 싶은 분들을 위한 참고하기 좋은 자료들입니다.
- GSP에 대한 개요