• 讲座标题：Introduction to Network Data Analysis

• 中文标题：网络数据分析导论

• 讲授者： Dr. Zongming Ma \text{Dr. Zongming Ma} Dr. Zongming Ma

• 讲授者邮箱（课程内容问题可联系）： zongming.ma@gmail.com \text{zongming.ma@gmail.com} zongming.ma@gmail.com

• 腾讯会议 I D \rm ID ID：

  第一节课（讲座时间： 2021/07/28 08:00-11:30(UTC+8) \text{2021/07/28 08:00-11:30(UTC+8)} 2021/07/28 08:00-11:30(UTC+8)） 353417977 353417977 353417977（密码： 123456 123456 123456）https://meeting.tencent.com/s/MuR1hV5tczeW

  第二节课（讲座时间： 2021/07/29 08:00-11:30(UTC+8) \text{2021/07/29 08:00-11:30(UTC+8)} 2021/07/29 08:00-11:30(UTC+8)） 482857838 482857838 482857838（密码： 123456 123456 123456）https://meeting.tencent.com/s/iyUdNiXsohiy

  第三节课（讲座时间： 2021/07/30 08:00-11:30(UTC+8) \text{2021/07/30 08:00-11:30(UTC+8)} 2021/07/30 08:00-11:30(UTC+8)） 107999260 107999260 107999260（密码： 123456 123456 123456）https://meeting.tencent.com/s/9UwpnnmlCKbc

序言

这门课是叉院开设在今年 7 7 7月 28 28 28日至 7 7 7月 30 30 30日的短期课程，主要讲授在网络图中的模型与应用，重心偏于统计理论以及数学规划，难度较高。讲授者以板书形式授课，笔者对板书内容进行的翻译，预计更新至 7 7 7月 30 30 30日，不过那天可能会有事无法详细记录最后一节课的内容。

讲授者介绍及课程大纲见本文 Lecture 1 \text{Lecture 1} Lecture 1中的内容，笔者认为该课程的质量是非常高的，由于不计学分且讲授者出于中美关系问题不让学院在公众号宣传，上课人数较少，有兴趣的朋友可以抽空来听听，虽然目前图神经网络已经有长足的应用与发展，但是笔者一向认为缺乏理论支撑的工作往往是难以长久的。

另上述邮箱可用于联系讲授者进行课程内容答疑，此后两天课程时间改为从 08 : 30 08:30 08:30开始，中途下课一次。

---

文章目录

• 序言
• Lecture 1 \text{Lecture 1} Lecture 1 概论
• Lecture 2 \text{Lecture 2} Lecture 2 统计决策理论导论
• Lecture 3 \text{Lecture 3} Lecture 3 随机块模型（一）

---

Lecture 1 \text{Lecture 1} Lecture 1 概论

1. 讲授者介绍：

   Dr. Zongming Ma is an Associate Professor of Statistics of the Wharton School at the University of Pennsylvania. He received his PhD in Statistics from Stanford University in 2010 and has since then been on the faculty of the Wharton Statistics Department. Dr. Ma’s research interests include high-dimensional statistical inference, nonparametric statistics, network data analysis, and their applications in biomedical data analysis. He is a recipient of a Sloan Research Fellowship and an NSF CAREER Award.

2. 课程大纲：

   1. Introduction to network data
      (a) Examples of typical network data
      (b) Important characteristics
      (c) Main challenges: modeling, algorithm, theory
      (d) This course: exchangeable network models, SBM / DCBM / latent space models
   2. A short introduction to statistical decision theory
      (a) Model, parameter, action space, loss, risk
      (b) Statistical optimality: Cramer–Rao, Bayes, minimax, rate minimax
      (c) Why the rate minimax viewpoint makes sense for complex decision problems
      (d) Neyman-Pearson lemma
      (e) Statistical optimality vs. computational efficiency
   3. Stochastic block models (1)
      (a) Data, model and parametrization
      (b) Likelihood and mean structure
      (c) To start with: planted partition model (balanced 2-block model)
      i. Spectral clustering
      ii. SDP relaxation of MLE
      iii. Approximate message passing
   4. Stochastic block models (2): Performance guarantee of spectral clustering
      (a) Prelude: three different regimes for community detection
      (b) l2 loss function
      (c) l∞ loss function
      (d) From spectral clustering to rate minimaxity
   5. Stochastic block models (3): Performance guarantee of SDP relaxations
   6. From SBMs to DCBMs
      (a) Reminder: why DCBMs
      (b) Generalization of spectral clustering
      (c) Generalization of SDP
      (d) Rate optimality in DCBMs
   7. Latent space models
      (a) Intro to latent space models
      (b) Connection to 1-bit matrix completion
      (c) Parameter estimation
      (d) Community detection
   8. Other models and connections to other statistical problems

---

Lecture 2 \text{Lecture 2} Lecture 2 统计决策理论导论

本节内容为数理统计回顾。

1. 模型，参数，参数空间

   ( 1 ) (1) (1) 模型：给定数据 X X X，模型即生成 X X X的概率分布 F F F，记为 X ∼ F X\sim F X∼F。

   ( 2 ) (2) (2) 参数：我们并不 100 % 100\% 100%确定模型是正确，因此通常考虑一组模型，由参数 θ \theta θ来索引（index）。

   ( 3 ) (3) (3) 参数空间：即参数 θ \theta θ的定义域 Θ \Theta Θ。

2. 行为空间，损失函数与风险函数

   ( 1 ) (1) (1) 理论框架：给定数据 X X X，模型 F θ F_\theta Fθ​，需要制定决策，如估计、检验以及预测。

   ( 2 ) (2) (2) 行为空间：决策可以采取的所有值构成行为空间，记为 A \mathcal{A} A，我们需要得出某个映射 X → A X\rightarrow\mathcal{A} X→A。

   • 在检验中， A = { 0 , 1 } \mathcal{A}=\{0,1\} A={0,1}或 A = [ 0 , 1 ] A=[0,1] A=[0,1]表示是否拒绝零假设或表示随机检验中拒绝零假设的概率。

   ( 3 ) (3) (3) 损失函数：给定一个行动 a ∈ A a\in A a∈A，损失函数 l ( a , θ ) l(a,\theta) l(a,θ)用于衡量该行为有多坏。

   • 确定检验中，一种合理的损失函数： l ( a , θ ) = 1 a = 1 ⋅ 1 θ ∈ H 0 + 1 a = 0 ⋅ 1 θ ∈ H 1 l(a,\theta)=\textbf{1}_{a=1}\cdot\textbf{1}_{\theta\in H_0}+\textbf{1}_{a=0}\cdot\textbf{1}_{\theta\in H_1} l(a,θ)=1a=1​⋅1θ∈H0​​+1a=0​⋅1θ∈H1​​
   • 随机检验中，一种合理的损失函数： l ( a , θ ) = a ⋅ 1 θ ∈ H 0 + ( 1 − a ) ⋅ 1 θ ∈ H 1 l(a,\theta)=a\cdot\textbf{1}_{\theta\in H_0}+(1-a)\cdot\textbf{1}_{\theta\in H_1} l(a,θ)=a⋅1θ∈H0​​+(1−a)⋅1θ∈H1​​

   ( 4 ) (4) (4) 风险函数：即损失函数的期望值， R ( θ ) = E θ [ l ( a ( X ) , θ ) ] R(\theta)=\mathbb{E}_\theta\left[l(a(X),\theta)\right] R(θ)=Eθ​[l(a(X),θ)]，这是一个只与 θ \theta θ相关的函数。
   R ( θ ) = E θ ∥ g ^ ( θ ) − g ( θ ) ∥ 2 2 (2.1) R(\theta)=\mathbb{E}_\theta\left\|\hat g(\theta)-g(\theta)\right\|_2^2\tag{2.1} R(θ)=Eθ​∥g^​(θ)−g(θ)∥22​(2.1)

3. 统计最优性

   ( 1 ) (1) (1) Cramer-Rao \text{Cramer-Rao} Cramer-Rao定理（无偏估计量的最小方差）： X 1 , . . . , X n ∼ i i d f θ ( x ) X_1,...,X_n\overset{iid}{\sim}f_\theta(x) X1​,...,Xn​∼iidfθ​(x)，设 W ( x ) = W ( X 1 , . . . , X n ) W(x)=W(X_1,...,X_n) W(x)=W(X1​,...,Xn​)是任意一个估计函数，其中 x ∈ X x\in\mathcal{X} x∈X，使得 d d θ E θ [ W ( x ) ] = ∫ X ∂ ∂ θ [ W ( x ) f θ ( x ) ] \frac{\text{d}}{\text{d}\theta}\mathbb{E}_\theta[W(x)]=\int_\mathcal{X}\frac\partial{\partial\theta}\left[W(x)f_\theta(x)\right] dθd​Eθ​[W(x)]=∫X​∂θ∂​[W(x)fθ​(x)]，且 E θ W 2 ( x ) \mathbb{E}_\theta W^2(x) Eθ​W2(x)有穷，则有：
   var θ ( W ( x ) ) ≥ [ d d θ E θ [ W ( x ) ] ] 2 E θ [ ( ∂ ∂ θ log ⁡ f θ ( x ) ) 2 ] (2.2) \text{var}_\theta(W(x))\ge\frac{\left[\frac{\text{d}}{\text{d}\theta}\mathbb{E}_\theta[W(x)]\right]^2}{\mathbb{E}_{\theta}\left[\left(\frac{\partial}{\partial \theta}\log f_\theta(x)\right)^2\right]}\tag{2.2} varθ​(W(x))≥Eθ​[(∂θ∂​logfθ​(x))2][dθd​Eθ​[W(x)]]2​(2.2)

   • 注意很多时候 var θ ( W ( x ) ) \text{var}_\theta(W(x)) varθ​(W(x))是可以作为风险函数使用的，因此可以得到风险函数的下界，且这个下界与 g ( θ ) g(\theta) g(θ)估计值 g ^ ( θ ) \hat g(\theta) g^​(θ)是无关的。

   • 若某个无偏估计量达到 Cramer-Rao \text{Cramer-Rao} Cramer-Rao下界，则该无偏估计量是有效的。

   • 这对参数空间中每一个 θ \theta θ都是最优的，因此是点点最优，一个推论是在指数族分布的 f θ ( x ) = exp ⁡ { a ( θ ) + b ( θ ) W ( x ) } f θ 0 ( x ) f_\theta(x)=\exp\left\{a(\theta)+b(\theta)W(x)\right\}f_{\theta_0}(x) fθ​(x)=exp{a(θ)+b(θ)W(x)}fθ0​​(x)上是成立点点最优的性质的。

   ( 2 ) (2) (2) 贝叶斯法则：

   • 平均最优：假设参数 θ \theta θ的密度函数为 π ( θ ) \pi(\theta) π(θ)，其中 θ ∈ Θ \theta\in\Theta θ∈Θ，则平均风险可以定义为：
     r π = ∫ Θ R ( θ , δ ) π ( θ ) d θ (2.3) r_\pi=\int_\Theta R(\theta,\delta)\pi(\theta)\text{d}\theta\tag{2.3} rπ​=∫Θ​R(θ,δ)π(θ)dθ(2.3)
     其中 R ( θ , δ ) = E θ [ l ( x ) , θ ] R(\theta,\delta)=\mathbb{E}_\theta\left[l(x),\theta\right] R(θ,δ)=Eθ​[l(x),θ]，上式就是贝叶斯风险函数，表示的是一种平均风险，如果某个估计量使得平均风险按最小，则称其为平均最优。

     由于这里涉及到参数 θ \theta θ的分布，就有先验与后验的区别，与贝叶斯相关的总是后验的：
     π ( θ ∣ x ) = f ( x ∣ θ ) ⋅ π ( θ ) m ( x ) ∫ Θ R ( θ , δ ) π ( θ ) d θ = ∫ Θ [ ∫ X l ( θ , δ ( x ) ) f ( x ∣ θ ) d x ] π ( θ ) d θ = ∫ X [ ∫ Θ l ( θ , a ) π ( θ ∣ x ) d θ ] m ( x ) d x (2.4) \pi(\theta|x)=\frac{f(x|\theta)\cdot\pi(\theta)}{m(x)}\\ \int_\Theta R(\theta,\delta)\pi(\theta)\text{d}\theta=\int_\Theta\left[\int_\mathcal{X}l(\theta,\delta(x))f(x|\theta)\text{d}x\right]\pi(\theta)\text{d}\theta=\int_{\mathcal{X}}\left[\int_\Theta l(\theta,a)\pi(\theta|x)\text{d}\theta\right]m(x)\text{d}x\tag{2.4} π(θ∣x)=m(x)f(x∣θ)⋅π(θ)​∫Θ​R(θ,δ)π(θ)dθ=∫Θ​[∫X​l(θ,δ(x))f(x∣θ)dx]π(θ)dθ=∫X​[∫Θ​l(θ,a)π(θ∣x)dθ]m(x)dx(2.4)
     交换积分次序后可以发现，贝叶斯估计量（平均最小）等价于最小化：
     argmin a ∫ Θ l ( θ , a ) π ( θ ∣ x ) d θ = δ π ( x ) (2.5) \text{argmin}_a\int_\Theta l(\theta,a)\pi(\theta|x)\text{d}\theta=\delta^\pi(x)\tag{2.5} argmina​∫Θ​l(θ,a)π(θ∣x)dθ=δπ(x)(2.5)
     称为贝叶斯法则，即最优估计量是使得后验均值最小的点。一般 l ( θ , a ) = ( θ − a ) 2 l(\theta,a)=(\theta-a)^2 l(θ,a)=(θ−a)2或是 l ( θ ) = ∣ θ − a ∣ l(\theta)=|\theta-a| l(θ)=∣θ−a∣，后者的贝叶斯法则取后验中位数（ M A E \rm MAE MAE的最小值取在中位数）。

   ( 3 ) (3) (3) 最小最大最优性：

   • 定义：称对于 θ \theta θ的一个估计量 δ M ( x ) \delta^{M}(x) δM(x)是最小最大估计量，若 sup ⁡ θ ∈ Θ R ( θ , δ M ) = inf ⁡ δ sup ⁡ θ ∈ Θ R ( θ , δ ) \sup_{\theta\in\Theta}R(\theta,\delta^M)=\inf_{\delta}\sup_{\theta\in\Theta}R(\theta,\delta) supθ∈Θ​R(θ,δM)=infδ​supθ∈Θ​R(θ,δ)，这就是最小最大最优性，这是一个很悲观的最优性。

   • 与贝叶斯估计量的联系：设 { π m ( θ ) } \{\pi_m(\theta)\} {πm​(θ)}是一系列 least favorable \text{least favorable} least favorable的先验分布，若每个先验分布 π \pi π，有 r π ≤ r = lim ⁡ m → ∞ r π m r_\pi\le r=\lim_{m\rightarrow\infty}r_{\pi_m} rπ​≤r=limm→∞​rπm​​，其中 r π m = ∫ R ( θ , δ π m ) π m ( θ ) d θ r_{\pi_m}=\int R(\theta,\delta^{\pi_m})\pi_m(\theta)\text{d}\theta rπm​​=∫R(θ,δπm​)πm​(θ)dθ，这是在 π m \pi_m πm​下贝叶斯风险。

   • 定理：假设 { π m ( θ ) } \{\pi_m(\theta)\} {πm​(θ)}满足 r π ≤ r = lim ⁡ m → ∞ r π m r_\pi\le r=\lim_{m\rightarrow\infty}r_{\pi_m} rπ​≤r=limm→∞​rπm​​，且 δ \delta δ是一个满足 sup ⁡ θ R ( θ , δ ) = r \sup_\theta R(\theta,\delta)=r supθ​R(θ,δ)=r的估计量，则 δ \delta δ是最小最大的（minimax）。

   • 渐近最小最大速率最优性：最小最大速率 η \eta η，最小最大风险 sup ⁡ θ R ( θ ， δ n M ) ≈ η n \sup_\theta R(\theta，\delta_n^M)\approx \eta_n supθ​R(θ，δnM​)≈ηn​，

   ( 4 ) (4) (4) 黎曼皮尔森引理：检验最优性

   • 定义假设检验 H 0 : θ = θ 0  v.s.  H 1 : θ = θ 1 H_0:\theta=\theta_0\text{ v.s. }H_1:\theta=\theta_1 H0​:θ=θ0​ v.s. H1​:θ=θ1​，给定检验水平 α \alpha α，最优检验指似然比检验，即拒绝域为 f θ 1 ( x ) f θ 2 ( x ) > k \frac{f_{\theta_1}(x)}{f_{\theta_2}(x)}>k fθ2​​(x)fθ1​​(x)​>k。

---

Lecture 3 \text{Lecture 3} Lecture 3 随机块模型（一）

想象一个学院内学生的社交关系网络，同年级学生之间的社交关系通常比跨年级的多得多，此时各个年级的学生就可以视为不同的块，可以使用随机块模型来刻画这种社交网络。

1. 初始化：

   ( 1 ) (1) (1) 数据： n n n个节点 { 1 , 2 , . . . , n } \{1,2,...,n\} {1,2,...,n}构成一个无向图，可以使用一个对称的零一邻接矩阵 A = { a i j } A=\{a_{ij}\} A={aij​}来表示，其中 a i i = 0 a_{ii}=0 aii​=0，即不存在指向自身的边。

   ( 2 ) (2) (2) 模型（生成模型）：

   • Erdos-Renyi \text{Erdos-Renyi} Erdos-Renyi模型： ∀ i < j , a i j = a j i ∼ i i d Bernoulli ( p ) \forall i<j,a_{ij}=a_{ji}\overset{iid}{\sim}\text{Bernoulli}(p) ∀i<j,aij​=aji​∼iidBernoulli(p)

   • 随机块模型（stochastic block model，下简称为 SBM \text{SBM} SBM），也称为 planted partition model \text{planted partition model} planted partition model

     存在 k k k个块（区），以及离散概率分布 α = ( α 1 , . . . , α k ) \alpha=(\alpha_1,...,\alpha_k) α=(α1​,...,αk​)，其中 α i ∈ ( 0 , 1 ) \alpha_i\in(0,1) αi​∈(0,1)满足 ∑ i = 1 k α i = 1 \sum_{i=1}^k\alpha_i=1 ∑i=1k​αi​=1。则

     任意节点 i i i，根据概率 α \alpha α将它分配到某个块（区）中，我们得到标签向量 z ∈ { 1 , . . . , k } n z\in\{1,...,k\}^n z∈{1,...,k}n，

     设 B ∈ [ 0 , 1 ] k × k B\in[0,1]^{k\times k} B∈[0,1]k×k为一个对称矩阵， ∀ i < j \forall i<j ∀i<j， a i j = a j i ∼ i n d Bernoulli ( B z i z j ) a_{ij}=a_{ji}\overset{\rm ind}{\sim}\text{Bernoulli}(B_{z_iz_j}) aij​=aji​∼indBernoulli(Bzi​zj​​)，则可以生成邻接矩阵 A A A。

   • 第二种版本：前两个模型的杂交版，直接给定固定的标签向量 z ∈ { 1 , . . . , k } n z\in\{1,...,k\}^n z∈{1,...,k}n，则其余部分和 SBM \text{SBM} SBM相同。

   • 最简单的版本： k = 2 k=2 k=2， α = ( 0.5 , 0.5 ) \alpha=(0.5,0.5) α=(0.5,0.5)， B = [ p , q ; q , p ] B=[p,q;q,p] B=[p,q;q,p]，且 p > q p>q p>q（即同一个块中节点连接的概率比不同块间点连接的概率要大）。

     我们主要研究这种最简单的模型（事实上其中很多结论并不浅然）。

2. 信号加噪声的角度：

   A = E [ A ] + ( A − E [ A ] ) A=\mathbb{E}[A]+(A-\mathbb{E}[A]) A=E[A]+(A−E[A])，即邻接矩阵由信号 E [ A ] \mathbb{E}[A] E[A]与噪声 A − E [ A ] A-\mathbb{E}[A] A−E[A]构成。

   假设 z = ( 1 , 1 , . . . , 1 , 2 , 2 , . . . , 2 ) z=(1,1,...,1,2,2,...,2) z=(1,1,...,1,2,2,...,2)，即前 n 2 \frac n2 2n​都是 1 1 1（前一半属于一个块），后 n 2 \frac{n}{2} 2n​都是（后一半属于一个块） 2 2 2，则可以得到：
   E [ A ] = [ 1 n 2 0 0 1 n 2 ] n × 2 [ p q q p ] 2 × 2 [ 1 n 2 ⊤ 0 ⊤ 0 ⊤ 1 n 2 ⊤ ] 2 × n (3.1) \mathbb{E}[A]=\left[\begin{matrix}\textbf{1}_{\frac n2}&0\\0&\textbf{1}_{\frac n2}\end{matrix}\right]_{n\times 2}\left[\begin{matrix}p&q\\q&p\end{matrix}\right]_{2\times2}\left[\begin{matrix}\textbf{1}_{\frac n2}^\top&0^\top\\0^\top&\textbf{1}_{\frac n2}^\top\end{matrix}\right]_{2\times n}\tag{3.1} E[A]=[12n​​0​012n​​​]n×2​[pq​qp​]2×2​[12n​⊤​0⊤​0⊤12n​⊤​​]2×n​(3.1)
   注意到 E [ A ] \mathbb{E}[A] E[A]有两个特征值 n ( p + q ) 2 > 0 \frac{n(p+q)}2>0 2n(p+q)​>0与 n ( p − q ) 2 > 0 \frac{n(p-q)}2>0 2n(p−q)​>0，所有其他的特征值都是 0 0 0，非零特征值对应的特征向量分别为 [ 1 n , . . . , 1 n ] [\frac1{\sqrt{n}},...,\frac1{\sqrt{n}}] [n ​1​,...,n ​1​]与 [ 1 n , . . . , − 1 n ] [\frac1{\sqrt{n}},...,-\frac1{\sqrt{n}}] [n ​1​,...,−n ​1​]（前一半符号为正，后一半符号为负）。

   则 A = E [ A ] + ( A − E [ A ] ) A=E[A]+(A-E[A]) A=E[A]+(A−E[A])， X = θ + z X=\theta+z X=θ+z，即信号 θ \theta θ加噪声 z z z， A A A的特征向量表征了节点分布在哪些块。

3. 图二分的角度：

   定义 G = ( V , E ) G=(V,E) G=(V,E)是无向图，我们想要找到一个不相交的顶点划分 V = S 1 ∪ S 2 V=S_1\cup S_2 V=S1​∪S2​，满足连接两个块的边权重和是最小的。

   即删掉尽可能少的边，使得图上的顶点分为两块互不连通的块。

   假设 n n n是偶数， m 1 = m 2 = n 2 m_1=m_2=\frac n2 m1​=m2​=2n​，且边权重都是 1 1 1，则给定任意一个图划分，定义矩阵 W = { w i u } ∈ { 0 , 1 } n × 2 W=\{w_{iu}\}\in\{0,1\}^{n\times 2} W={wiu​}∈{0,1}n×2，其中 w i u w_{iu} wiu​表示节点 i i i是否属于 S u S_u Su​，则所有删除掉的边的权重和为：
   1 2 tr ( A ( J − W W ⊤ ) ) (3.2) \frac12\text{tr}(A(J-WW^\top))\tag{3.2} 21​tr(A(J−WW⊤))(3.2)
   这是一个简约的数学表示，容易证明其正确性，其中 J J J为 n n n维全一方阵。

   于是图二分问题可以定义为：
   minimize 1 2 tr ( A ( J − W W ⊤ ) ) subject to w i u ∈ { 0 , 1 } W ⋅ [ 1 1 ] = 1 n = [ 1 1 . . . 1 ] W ⊤ 1 n = [ n 2 n 2 ] (3.3) \begin{aligned} &\text{minimize}&&\frac12\text{tr}(A(J-WW^\top))\\ &\text{subject to}&&w_{iu}\in\{0,1\}\\ &&&W\cdot\left[\begin{matrix}1\\1\end{matrix}\right]=\textbf{1}_n=\left[\begin{matrix}1\\1\\...\\1\end{matrix}\right]\\ &&&W^\top \textbf{1}_n=\left[\begin{matrix}\frac n2\\\frac n2\end{matrix}\right] \end{aligned}\tag{3.3} ​minimizesubject to​​21​tr(A(J−WW⊤))wiu​∈{0,1}W⋅[11​]=1n​=⎣⎢⎢⎡​11...1​⎦⎥⎥⎤​W⊤1n​=[2n​2n​​]​(3.3)
   上述规划问题等价于：
   maximize tr ( W ⊤ A W ) subject to w i u ∈ { 0 , 1 } W 1 2 = 1 n W ⊤ 1 n = [ n 2 n 2 ] (3.4) \begin{aligned} &\text{maximize}&&\text{tr}(W^\top AW)\\ &\text{subject to}&&w_{iu}\in\{0,1\}\\ &&& W\textbf{1}_2=\textbf{1}_n\\ &&&W^\top \textbf{1}_n=\left[\begin{matrix}\frac n2\\\frac n2\end{matrix}\right] \end{aligned}\tag{3.4} ​maximizesubject to​​tr(W⊤AW)wiu​∈{0,1}W12​=1n​W⊤1n​=[2n​2n​​]​(3.4)
   这是一个整数规划，非常难于求解，因此需要做凸规划的 relax \text{relax} relax。

   定义 X = W W ⊤ ∈ R n × n X=WW^\top\in\R^{n\times n} X=WW⊤∈Rn×n，则问题 relax \text{relax} relax为：
   maximize tr ( A X ) subject to X ⪰ 0 J ≥ X ≥ 0 x i i = 1 i = 1 , 2 , . . . , n X 1 n = [ n 2 n 2 ] (3.5) \begin{aligned} &\text{maximize}&&\text{tr}(AX)\\ &\text{subject to}&&X\succeq 0\\ &&& J\ge X\ge 0\\ &&&x_{ii}=1\quad i=1,2,...,n\\ &&&X\textbf{1}_n=\left[\begin{matrix}\frac n2\\\frac n2\end{matrix}\right] \end{aligned}\tag{3.5} ​maximizesubject to​​tr(AX)X⪰0J≥X≥0xii​=1i=1,2,...,nX1n​=[2n​2n​​]​(3.5)
   这个问题的理想解是 X ∗ = [ J 0 0 J ] X^*=\left[\begin{matrix}J&\textbf{0}\\\textbf{0}&J\end{matrix}\right] X∗=[J0​0J​]，其中 J J J为 n 2 \frac n2 2n​维全一方阵。

4. 似然的角度：

   z ∈ { 1 , 2 } n z\in\{1,2\}^n z∈{1,2}n，则有：
   log ⁡ p ( a i j ∣ z , p , q ) = { log ⁡ p if  a i j = 1  and  z i = z j log ⁡ ( 1 − p ) if  a i j = 0  and  z i = z j log ⁡ q if  a i j = 1  and  z i ≠ z j log ⁡ ( 1 − q ) if  a i j = 0  and  z i ≠ z j = [ a i j log ⁡ p + ( 1 − a i j log ⁡ ( 1 − p ) ) ] 1 z i = z j + [ a i j log ⁡ q + ( 1 − a i j log ⁡ ( 1 − q ) ) ] 1 z i ≠ z j (3.6) \begin{aligned} \log p(a_{ij}|z,p,q)&=\left\{\begin{aligned} &\log p&&\text{if } a_{ij}=1\text{ and }z_i=z_j\\ &\log (1-p)&&\text{if } a_{ij}=0\text{ and }z_i=z_j\\ &\log q&&\text{if } a_{ij}=1\text{ and }z_i\neq z_j\\ &\log (1-q)&&\text{if } a_{ij}=0\text{ and }z_i\neq z_j\\ \end{aligned}\right.\\ &=\left[a_{ij}\log p+(1-a_{ij}\log(1-p))\right]\textbf{1}_{z_i=z_j}+\left[a_{ij}\log q+(1-a_{ij}\log(1-q))\right]\textbf{1}_{z_i\neq z_j} \end{aligned}\tag{3.6} logp(aij​∣z,p,q)​=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​​logplog(1−p)logqlog(1−q)​​if aij​=1 and zi​=zj​if aij​=0 and zi​=zj​if aij​=1 and zi​​=zj​if aij​=0 and zi​​=zj​​=[aij​logp+(1−aij​log(1−p))]1zi​=zj​​+[aij​logq+(1−aij​log(1−q))]1zi​​=zj​​​(3.6)
   对应地完整的对数似然函数：
   l ( A ∣ z , p , q ) = ∑ 1 ≤ i < j ≤ n log ⁡ p ( a i j ∣ z i , z j , p , q ) (3.7) l(A|z,p,q)=\sum_{1\le i<j\le n}\log p(a_{ij}|z_i,z_j,p,q)\tag{3.7} l(A∣z,p,q)=1≤i<j≤n∑​logp(aij​∣zi​,zj​,p,q)(3.7)
   于是我们需要最大化对数似然函数：
   argmax z l ( A ∣ z , p , q ) = argmax z ∑ 1 ≤ i < j ≤ n [ ( log ⁡ p 1 − p − log ⁡ q 1 − q ) a i j + log ⁡ 1 − p 1 − q ] 1 z i = z j = argmax z ∑ 1 ≤ i < j ≤ n ( a i j − λ ) 1 z i = z j = argmax z ∑ 1 ≤ i < j ≤ n a i j 1 z i = z j (3.8) \begin{aligned} \text{argmax}_z l(A|z,p,q)&=\text{argmax}_{z}\sum_{1\le i<j\le n}\left[\left(\log\frac{p}{1-p}-\log\frac{q}{1-q}\right)a_{ij}+\log\frac{1-p}{1-q}\right]\textbf1_{z_i=z_j}\\ &=\text{argmax}_z\sum_{1\le i<j\le n}\left(a_{ij}-\lambda\right)\textbf1_{z_i=z_j}\\ &=\text{argmax}_z\sum_{1\le i<j\le n}a_{ij}\textbf1_{z_i=z_j} \end{aligned}\tag{3.8} argmaxz​l(A∣z,p,q)​=argmaxz​1≤i<j≤n∑​[(log1−pp​−log1−qq​)aij​+log1−q1−p​]1zi​=zj​​=argmaxz​1≤i<j≤n∑​(aij​−λ)1zi​=zj​​=argmaxz​1≤i<j≤n∑​aij​1zi​=zj​​​(3.8)
   其中 λ = log ⁡ 1 − q 1 − p log ⁡ p 1 − p − log ⁡ q 1 − q \lambda = \frac{\log\frac{1-q}{1-p}}{\log\frac{p}{1-p}-\log\frac{q}{1-q}} λ=log1−pp​−log1−qq​log1−p1−q​​，于是 z z z的最大似然估计就是如下的规划：
   maximize ∑ 1 ≤ i < j ≤ n a i j 1 z i = z j subject to ∑ i 1 z i = 1 = ∑ i 1 z i = 2 = n 2 (3.9) \begin{aligned} &\text{maximize}&&\sum_{1\le i<j\le n}a_{ij}\textbf1_{z_i=z_j}\\ &\text{subject to}&&\sum_i\textbf{1}_{z_i=1}=\sum_i\textbf{1}_{z_i=2}=\frac{n}2 \end{aligned}\tag{3.9} ​maximizesubject to​​1≤i<j≤n∑​aij​1zi​=zj​​i∑​1zi​=1​=i∑​1zi​=2​=2n​​(3.9)
   其中 a i i = 0 a_{ii}=0 aii​=0，定义 X = { 1 z i = z j } ∈ { 0 , 1 } n × n X=\{\textbf{1}_{z_i=z_j}\}\in\{0,1\}^{n\times n} X={1zi​=zj​​}∈{0,1}n×n是一个对称矩阵，上述规划等价于：
   maximize tr ( A X ) subject to X = X ⊤ x i j ∈ { 0 , 1 } i = 1 , 2 , . . . , n , j = 1 , 2 , . . . , n X 1 n = n 2 1 n x i i = 1 i = 1 , 2 , . . . , n (3.10) \begin{aligned} &\text{maximize}&&\text{tr}(AX)\\ &\text{subject to}&&X=X^\top\\ &&& x_ij\in\{0,1\}\quad i=1,2,...,n,j=1,2,...,n\\ &&&X\textbf{1}_n=\frac n2\textbf{1}_n\\ &&&x_{ii}=1\quad i=1,2,...,n \end{aligned}\tag{3.10} ​maximizesubject to​​tr(AX)X=X⊤xi​j∈{0,1}i=1,2,...,n,j=1,2,...,nX1n​=2n​1n​xii​=1i=1,2,...,n​(3.10)
   注意这里还是一个整数规划，继续 relax \text{relax} relax为凸规划：
   maximize tr ( A X ) subject to X ⪰ 0 J ≥ X ≥ 0 x i i = 1 i = 1 , 2 , . . . , n X 1 n = [ n 2 n 2 ] (3.11) \begin{aligned} &\text{maximize}&&\text{tr}(AX)\\ &\text{subject to}&&X\succeq 0\\ &&& J\ge X\ge 0\\ &&&x_{ii}=1\quad i=1,2,...,n\\ &&&X\textbf{1}_n=\left[\begin{matrix}\frac n2\\\frac n2\end{matrix}\right] \end{aligned}\tag{3.11} ​maximizesubject to​​tr(AX)X⪰0J≥X≥0xii​=1i=1,2,...,nX1n​=[2n​2n​​]​(3.11)
   这与式 ( 3.5 ) (3.5) (3.5)中的规划完全一致，这意味着从似然的角度得出的结果与从图二分的角度得出的结果具有某种一致性。