自然·物理：奇異值分解在復(fù)雜系統(tǒng)研究中的應(yīng)用

復(fù)雜系統(tǒng)通常由大量互相作用的異質(zhì)組成部分構(gòu)成，這些系統(tǒng)在微觀上表現(xiàn)出高維、非線性動力學(xué)行為，但其宏觀表現(xiàn)往往由少數(shù)主導(dǎo)模式?jīng)Q定。這種現(xiàn)象啟發(fā)了低秩假說（Low-rank hypothesis）：即復(fù)雜系統(tǒng)的整體動力學(xué)可以通過一個低秩矩陣所描述的相互作用模式進行有效近似。奇異值分解（Singular Value Decomposition, SVD）正是揭示這種低秩結(jié)構(gòu)的核心數(shù)學(xué)工具，它能夠從高維、嘈雜的數(shù)據(jù)中提取最重要的模式，形成對系統(tǒng)降維的自然框架。

本文是The low-rank hypothesis of complex systems論文的II. SVD IN THE STUDY OF COMPLEX SYSTEMS部分，論文正文見集智俱樂部公眾號1月15日文章《自然·物理：復(fù)雜系統(tǒng)的低秩假說》。

撰文 | 王璇

審校 | 趙思怡

論文題目：The low-rank hypothesis of complex systems

論文鏈接：https://www.nature.com/articles/s41567-023-02303-0

發(fā)表時間：2024 年 1 月 10 日

論文來源：Nature Physics

當(dāng)你對AI說“畫一只有戴帽子的微笑貓”，它為何能理解并生成這幅不存在的圖像？AI的“思考”并非像素層面的操作，而是對語義的捕捉與建模。在看似魔法般的創(chuàng)作背后，是數(shù)學(xué)在悄然搭建一座橋梁。一端是抽象的文字描述（“貓”“帽子”“微笑”），另一端是具體的視覺圖像。這座橋梁的核心支柱，便是奇異值分解（Singular Value Decomposition, SVD）。

從生成“戴帽子的貓”的語義潛在空間回到現(xiàn)實世界中的復(fù)雜系統(tǒng)，SVD的核心思想是從高維、嘈雜的數(shù)據(jù)中提取少數(shù)主導(dǎo)模式。同樣構(gòu)成了理解復(fù)雜系統(tǒng)結(jié)構(gòu)與其動力學(xué)行為的關(guān)鍵數(shù)學(xué)支柱。若將AI繪畫中的“語義方向”類比于復(fù)雜系統(tǒng)中的“主導(dǎo)相互作用模式”，那么SVD正是揭示這些隱藏模式、實現(xiàn)系統(tǒng)降維描述的通用語言。

詳情請見《線性代數(shù)：一名合格科研人的筑基課丨新課上線》

在復(fù)雜系統(tǒng)的研究中，一個基礎(chǔ)且影響深遠的現(xiàn)象是：盡管系統(tǒng)在微觀上可能包含海量組分與錯綜復(fù)雜的相互作用，但其宏觀行為往往由少數(shù)幾個關(guān)鍵變量或模式主導(dǎo)。這便是復(fù)雜系統(tǒng)的“低秩假說”。本部分內(nèi)容將從隨機圖理論的視角切入，系統(tǒng)性地檢視這一假設(shè)。在眾多廣泛使用的網(wǎng)絡(luò)模型中，其權(quán)重矩陣的期望值天然蘊含低秩結(jié)構(gòu)，這為低秩假設(shè)提供了堅實的理論基礎(chǔ)。針對難以直接顯式分解的模型（如有向軟配置模型及其加權(quán)版本），嚴格證明其奇異值以指數(shù)級速度衰減，從而在更深刻的意義上驗證了低秩近似的合理性。

進一步地，研究者們不僅滿足于“低秩”的定性判斷，而且通過有效秩這一系列定量指標(biāo)，來刻畫奇異值衰減的快慢，并探究其背后的標(biāo)度規(guī)律。不同的衰減模式（如指數(shù)、冪律）將導(dǎo)致有效秩迥異的漸近行為，這為理解不同類別網(wǎng)絡(luò)的“內(nèi)在維度”提供了精確的度量。此外，SVD為有向、加權(quán)乃至帶符號的網(wǎng)絡(luò)提供了天然、穩(wěn)定的中心性度量（權(quán)威中心性與樞紐中心性），避免了特征值分解可能帶來的復(fù)數(shù)困境。

研究者還初步探索復(fù)雜系統(tǒng)的動態(tài)適應(yīng)性。在自適應(yīng)網(wǎng)絡(luò)中，網(wǎng)絡(luò)結(jié)構(gòu)本身會隨動力學(xué)或外部環(huán)境演變，其有效秩也可能隨之演化，這為理解學(xué)習(xí)、演化等過程提供了新的視角。最后，簡要概述SVD在動力系統(tǒng)降維中的強大作用，它將系統(tǒng)的奇異值譜與降維誤差直接關(guān)聯(lián)，為在高維網(wǎng)絡(luò)動力學(xué)中提取可理解的宏觀方程奠定了理論基礎(chǔ)。

總而言之，從靜態(tài)的網(wǎng)絡(luò)結(jié)構(gòu)到動態(tài)的演化過程，從理論的隨機模型到實證的真實系統(tǒng)，SVD提供了一套連貫、強大且可計算的理論工具，用以捕捉復(fù)雜系統(tǒng)中那“多者異也”（More is different）的簡約之美。

隨機圖的SVD

盡管隨機圖及其特征值譜的研究歷史悠久[1–11]，但其SVD性質(zhì)在文獻中關(guān)注較少。實際上，許多網(wǎng)絡(luò)科學(xué)[12]或譜圖論[2, 13, 14]入門教材甚至未涉及SVD。然而，正如復(fù)雜系統(tǒng)分析所顯示，SVD為理解網(wǎng)絡(luò)的低秩結(jié)構(gòu)與動力學(xué)模式提供了強大工具，因此值得更多關(guān)注。

考慮一個隨機網(wǎng)絡(luò)模型，其鄰接矩陣或權(quán)重矩陣W可以寫作：

陣，對于每個以概率p重連的位置，其元素為-1或1。其奇異值衰減通常不呈指數(shù)型，說明其有效秩較高。這類例子提醒我們，低秩并非普適規(guī)律，而是廣泛存在于大多數(shù)隨機網(wǎng)絡(luò)與復(fù)雜系統(tǒng)模型中。

在物理學(xué)、機器學(xué)習(xí)及神經(jīng)科學(xué)中，也存在明確的低秩例子：如Sherrington-Kirkpatrick自旋玻璃模型的相互作用矩陣，其期望矩陣為秩一形式；經(jīng)典隨機矩陣高斯系綜在〈W〉=0時秩為零；其他尖峰隨機矩陣或有限秩外源隨機矩陣則體現(xiàn)了低秩結(jié)構(gòu)在大規(guī)模極限下的普適性。

值得注意的是，即便期望矩陣〈W〉明確依賴低秩矩陣L，實際矩陣W的有效低秩性仍需通過奇異值譜分析來驗證。例如，在軟配置模型中，盡管沒有顯式的秩分解，其奇異值仍呈指數(shù)級快速衰減。這一現(xiàn)象將在下一節(jié)通過有向軟配置模型與最大熵隨機圖的分析得到嚴格證明。

有向軟配置模型中奇異值的指數(shù)級遞減

在復(fù)雜網(wǎng)絡(luò)分析中，我們通常只能獲取網(wǎng)絡(luò)的部分信息。因此，將觀察到的復(fù)雜網(wǎng)絡(luò)描述為一組可能的網(wǎng)絡(luò)，每個網(wǎng)絡(luò)具有一定概率，是合理的。為了在最小偏差的前提下確定這些概率分布，可以依賴香農(nóng)熵的最大化原理[15]。這種方法保證在給定約束下網(wǎng)絡(luò)模型最無偏，從而廣泛應(yīng)用于隨機圖模型的構(gòu)建。

最大熵網(wǎng)絡(luò)模型的拉格朗日乘子法

最大熵網(wǎng)絡(luò)模型通常通過拉格朗日乘子法得到。這一方法最早由拉格朗日和歐拉提出，但在嚴格數(shù)學(xué)表述上，Carathéodory 在 1935 年的變分法著作中系統(tǒng)闡明了其適用條件。其核心思想是：在約束條件下，最大熵概率分布可表示為指數(shù)族形式。

對于隨機鄰接矩陣A，在滿足某些軟約束（如期望度數(shù)或其他結(jié)構(gòu)量）的情況下，最大熵概率分布為：

這個公式揭示了期望矩陣元素遵循Fermi-Dirac 分布，保證所有值在 (0,1) 之間。

奇異值分解與指數(shù)衰減

期望鄰接矩陣可以表示為一系列秩為一的矩陣之和，每一項對應(yīng)一個奇異值。這一分解揭示了奇異值的快速衰減規(guī)律。通過數(shù)學(xué)推導(dǎo)可知，若矩陣元素滿足適度條件（如小于 1/2），則其奇異值至少以指數(shù)速度下降：

類似地，在另一類參數(shù)條件下，奇異值也存在類似的指數(shù)上界。這一性質(zhì)表明，有向軟配置模型的期望鄰接矩陣是低秩近似的，這對于網(wǎng)絡(luò)壓縮、降維以及社區(qū)發(fā)現(xiàn)具有重要意義。

在加權(quán)網(wǎng)絡(luò)中，最大熵方法同樣適用。對權(quán)重矩陣W的期望值進行分析，可得到類似的指數(shù)衰減，與有向軟配置模型不同，權(quán)重矩陣的元素遵循Bose-Einstein 分布，其取值域不受限制，但奇異值仍然呈指數(shù)衰減趨勢。這表明，即使在加權(quán)網(wǎng)絡(luò)中，主要結(jié)構(gòu)信息仍高度集中于少數(shù)奇異向量上。

奇異值分布和矩陣密度對有效秩的影響

本小節(jié)關(guān)注一個核心問題：奇異值的衰減形態(tài)如何決定矩陣的有效秩，并由此刻畫復(fù)雜系統(tǒng)的“內(nèi)在維度”。為此，我們引入三類常用的有效秩指標(biāo)——穩(wěn)定秩（srank）、核范數(shù)秩（nrank）與熵秩（erank），并系統(tǒng)分析它們在不同奇異值分布下的漸近行為。

整體思路并不依賴具體模型的細節(jié)，而是圍繞一個更為抽象、卻極具解釋力的概念展開：奇異值包絡(luò)線。通過為真實奇異值序列構(gòu)造上下界包絡(luò)函數(shù)，可以將離散譜問題轉(zhuǎn)化為連續(xù)函數(shù)的積分估計問題，從而大幅簡化分析，同時保留對漸近行為的精確控制。

奇異值包絡(luò)線

這兩個函數(shù)在x=1處歸一化為1，從而避免通過整體縮放人為引入虛假的秩標(biāo)度。

這一設(shè)定的關(guān)鍵意義在于：有效秩的大小不再依賴于每一個具體奇異值，而主要由其整體衰減輪廓所決定。

圖S4：典型的奇異值包絡(luò)函數(shù) w(x)，描述了歸一化奇異值σi/σ1隨連續(xù)變量 x（在索引 i 之間插值）的遞減行為，及其對srank、nrank和erank漸近行為的影響（右下子圖）。

除了奇異值的衰減形態(tài)，矩陣的密度同樣會影響有效秩，尤其是穩(wěn)定秩。一般而言，在其他條件相同的情況下，更稠密的矩陣往往具有更高的穩(wěn)定秩，這一結(jié)論可通過通用不等式直接給出。這為比較不同網(wǎng)絡(luò)（如稀疏真實網(wǎng)絡(luò)與稠密隨機模型）提供了額外的結(jié)構(gòu)維度。

有向網(wǎng)絡(luò)的中心性度量

對于有向網(wǎng)絡(luò)，其對應(yīng)矩陣的特征值與特征向量通常為復(fù)數(shù)，這使得基于特征值分解的傳統(tǒng)中心性定義在解釋和應(yīng)用上面臨困難。因此，在有向情形下，有必要對中心性度量的構(gòu)造方式進行調(diào)整。一種自然且穩(wěn)定的替代方案是采用奇異值分解（SVD）。

基于有向網(wǎng)絡(luò)的 SVD，可以得到兩類互補的頂點中心性度量：權(quán)威中心性（authority centrality），對應(yīng)于主導(dǎo)左奇異向量 u1；以及樞紐中心性（hub centrality）對應(yīng)于主導(dǎo)右奇異向量v1[16, 17]，如圖 S5 所示。

這一點指導(dǎo)了在構(gòu)造降維動力學(xué)時對可觀測量的選擇。同時，當(dāng)在定理 S57 中采用右奇異向量作為降維矩陣時，這一視角也有助于理解其中出現(xiàn)的不同項與方程所具有的物理或結(jié)構(gòu)含義。

需要指出的是，在帶符號網(wǎng)絡(luò)（即由包含負權(quán)重的矩陣描述的網(wǎng)絡(luò)）中，上述基于 SVD 的中心性度量可能存在解釋上的歧義。這是因為在該情形下，主導(dǎo)左、右奇異向量通常包含正負混合的分量，經(jīng)典的 Perron–Frobenius 定理[4] 不再適用，從而無法保證中心性向量的非負性與唯一性。這一限制提示，在處理帶符號網(wǎng)絡(luò)時，有必要對中心性的定義及其物理含義進行更為謹慎的解讀。

圖 S5：（a）權(quán)威中心性與樞紐中心性分別由主導(dǎo)左奇異向量與主導(dǎo)右奇異向量的分量給出。（b）幼年斑馬魚（Danio rerio）中尺度連接組網(wǎng)絡(luò)的中心性分布，該網(wǎng)絡(luò)包含N=71個社區(qū)，并加入了自環(huán)（改編自文獻 [18]）。

自適應(yīng)網(wǎng)絡(luò)

復(fù)雜系統(tǒng)不僅由其非線性動力學(xué)和網(wǎng)絡(luò)結(jié)構(gòu)所刻畫，還體現(xiàn)在其對環(huán)境變化的適應(yīng)能力上[19]。因此，一個復(fù)雜網(wǎng)絡(luò)的有效秩可能隨時間和系統(tǒng)狀態(tài)發(fā)生變化。通過一個初步研究考察了這一現(xiàn)象，方法是提取秀麗隱桿線蟲（C. elegans）連接組在不同成熟階段的有效秩，如圖 S6 所示。結(jié)果顯示，穩(wěn)定秩會隨個體年齡增長而減小。關(guān)于這一現(xiàn)象，還需要進一步研究，以檢驗這種下降是否具有統(tǒng)計顯著性，并闡明有效秩隨成熟階段降低所對應(yīng)的生物學(xué)含義。

圖 S6：描述秀麗隱桿線蟲大腦連接結(jié)構(gòu)的矩陣在不同成熟階段的奇異值分布。對應(yīng)的穩(wěn)定秩分別為：21.6（發(fā)育階段 1）、19.7（發(fā)育階段 5）以及 18.5（發(fā)育階段 8）。

此外，文獻[20]的數(shù)值計算表明，對神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練會降低其穩(wěn)定秩。這一現(xiàn)象在一定程度上與上述生物學(xué)實例觀察到的趨勢一致，提示穩(wěn)定秩可能與網(wǎng)絡(luò)功能優(yōu)化和適應(yīng)性調(diào)節(jié)密切相關(guān)。

動力系統(tǒng)中的奇異值分解

SVD在動力系統(tǒng)中的應(yīng)用范圍非常廣泛，尤其是在工程學(xué)和線性控制系統(tǒng)領(lǐng)域中[21]。此外，SVD 也已經(jīng)被推廣到非線性算符的情形[22]。甚至還可以對隨時間演化的矩陣動力學(xué)，

在降維實踐中，如何合理選擇降維矩陣M往往是一個具有挑戰(zhàn)的問題[25] ，SVD 的一個重要優(yōu)勢在于：其奇異值為非負實數(shù)，奇異向量為實向量。這使得奇異值分解在解析譜結(jié)構(gòu)和為動力學(xué)定義可解釋的觀測量時特別有用。相比之下，若采用一般實矩陣的特征值分解，降維矩陣可能為復(fù)數(shù)，從而導(dǎo)致原本實值的動力系統(tǒng)在降維后表現(xiàn)為復(fù)動力學(xué)[25, 26]。

從靜態(tài)網(wǎng)絡(luò)結(jié)構(gòu)到動態(tài)演化過程，從隨機模型到真實系統(tǒng)，SVD提供了一套連貫、強大且可計算的理論工具。它揭示了復(fù)雜系統(tǒng)中“多者異也”的簡約之美，將高維復(fù)雜行為映射為少數(shù)主導(dǎo)模式，為網(wǎng)絡(luò)壓縮、降維、中心性度量及動力學(xué)建模提供堅實的數(shù)學(xué)基礎(chǔ)。

參考文獻

[1] Z. Füredi and J. Komlós, "The eigenvalues of random symmetric matrices," Combinatorica 1, 233 (1981).

[2] P. Bonacich, "Power and Centrality: A Family of Measures," Am. J. Sociol. 92, 1170 (1987); F. Chung, Spectral Graph Theory (CBMS, Rhode Island, 1994).

[3] F. Chung, L. Lu, and V. Vu, "Spectra of random graphs with given expected degrees," Proc. Natl. Acad. Sci. U.S.A. 100, 6313 (2003).

[4] S. N. Dorogovtsev, A. V. Goltsev, J. F. F. Mendes, and A. N. Samukhin, "Spectra of complex networks," Phys. Rev. E 68, 046109 (2003).

[5] P. Van Mieghem, Graph Spectra for Complex Networks (Cambridge University Press, 2011).

[6] F. Chung and M. Radcliffe, "On the spectra of general random graphs," Electron. J. Comb. 18, P215 (2011).

[7] R. R. Nadakuditi and M. E. J. Newman, "Graph Spectra and the Detectability of Community Structure in Networks," Phys. Rev. Lett. 108, 188701 (2012).

[8] T. P. Peixoto, "Eigenvalue Spectra of Modular Networks," Phys. Rev. Lett. 111, 098701 (2013).

[9] C. Castellano and R. Pastor-Satorras, "Topological determinants of complex networks spectral properties: structural and dynamical effects," Phys. Rev. X 7, 0414 (2017).

[10] M. E. J. Newman, X. Zhang, and R. R. Nadakuditi, "Spectra of random networks with arbitrary degrees," Phys. Rev. E 99, 042309 (2019).

[11] A. Athreya, J. Cape, and M. Tang, "Eigenvalues of stochastic blockmodel graphs and random graphs with low-rank edge probability matrices," Sankhya A 84, 36 (2022).

[12] E. Estrada and P. Knight, A first course on network science (Oxford University Press, 2015); A.-L. Barabási, Network science (Cambridge University Press, 2016); V. Latora, V. Nicosia, and G. Russo, Complex Networks: Principles, Methods and Applications (Cambridge University Press, 2017); M. E. J. Newman, Networks (Oxford University Press, 2018).

[13] V. Nikiforov, "The energy of graphs and matrices," J. Math. Anal. Appl. 326, 1472 (2007); B. Nica, A Brief Introduction to Spectral Graph Theory (European Mathematical Society, Zurich, 2018).

[14] D. M. Cvetkovic, M. Doob, and H. Sachs, "Spectra of graphs. Theory and application," (1980).

[15] E. T. Jaynes, "Information Theory and Statistical Mechanics," The Phys. Rev. 106, 620 (1957).

[16] J. M. Kleinberg, "Authoritative sources in a hyperlinked environment," in SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms (1998) p. 668.

[17] M. E. J. Newman, Networks (Oxford University Press, 2018).

[18] M. Kunst, E. Laurell, N. Mokayes, A. Kramer, F. Kubo, A. M. Fernandes, D. F?rster, M. Dal Maschio, and H. Baier, "A Cellular-Resolution Atlas of the Larval Zebrafish Brain," Neuron 103, 21 (2019).

[19] M. Mitchell, Complexity: A Guided Tour (Oxford University Press, 2009).

[20] C. H. Martin and M. W. Mahoney, "Implicit self-regularization in deep neural networks: Evidence from random matrix theory and implications for learning," J. Mach. Learn. Res. 22, 1 (2021).

[21] A. C. Antoulas, Approximation of Large-Scale Dynamical System (SIAM, 2005).

[22] K. Fujimoto, "What are singular values of nonlinear operators?" in 43rd IEEE Conf. Decis. Control (2004) p. 1623.

[23] O. Koch and C. Lubich, "Dynamical low-rank approximation," SIAM J. Matrix Anal. Appl. 29, 434 (2007).

[24] P. Holme and J. Saram?ki, "Temporal networks," Phys. Rep. 519, 97 (2012).

[25] V. Thibeault, G. St-Onge, L. J. Dubé, and P. Desrosiers, "Threefold way to the dimension reduction of dynamics on networks: An application to synchronization," Phys. Rev. Research 2, 043215 (2020).

[26] V. Thibeault, Réduire la dimension des systèmes complexes : un regard sur l'émergence de la synchronisation, Master's thesis, Université Laval (2020).

本文經(jīng)授權(quán)轉(zhuǎn)載自微信公眾號“集智俱樂部”。

特 別 提 示

1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閱不同主題系列科普文章。

2. 『返樸』提供按月檢索文章功能。關(guān)注公眾號，回復(fù)四位數(shù)組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。