题目内容

在一个由 $N$ 个节点组成的无向图中，节点编号为 $0$ 至 $N-1$，图不包含自环（若输入中出现自环将被直接忽略）。每个节点 $i$ 拥有一个 $d$ 维的原始特征向量 $x_i$，所有特征构成矩阵 $X \in \mathbb{R}^{N \times d}$。节点之间的边由无向边集合 $E$ 给出，边可能存在重复，但处理时将对边进行去重。

定义节点 $i$ 的邻居集合 $\mathcal{N}(i)$ 为与其直接相连的所有节点。对每个节点计算邻域平滑特征：

若 $\mathcal{N}(i)$ 为空（即节点度数为 $0$），则直接令 $h_i = x_i$。所有节点经上式聚合后得到特征矩阵 $H \in \mathbb{R}^{N \times d}$。

接下来利用已知标签的训练节点训练一个线性分类器。设训练索引集合为 $T$，对应的真实二值标签为 $y_T \in \{0,1\}^{|T|}$。采用岭回归（带 $L_2$ 正则化）求解：

闭式解为：

其中 $H_T$ 是 $H$ 中对应训练索引的行构成的子矩阵，$I$ 为单位阵。

对每个测试节点 $i$，计算线性得分 $\eta_i = h_i^\top w$，再通过 logistic 函数得到预测概率：

最终预测标签为 $\hat{y}_i = \mathbb{1}[p_i \ge 0.5]$。

你需要仅使用 numpy、pandas、scikit-learn 三个库实现上述逻辑。图规模极小，直接用 numpy 循环遍历节点与邻居即可，不必考虑性能优化。

本题数据范围：节点总数 $N$ 不超过 $20$，特征维数 $d$ 不超过 $5$，边数 $|E|$ 不超过 $30$。训练样本数 $|T|$ 在 $2$ 到 $4$ 之间，测试样本数不超过 $8$，且训练集与测试集互不相交。训练标签中 $0$ 与 $1$ 的比例均在 $25\%$ 到 $75\%$ 范围内。所有特征值及计算过程中涉及的数值均按浮点数处理。

输入描述

输入为一整行 JSON 字符串，包含以下字段：

• nodes：形状为 $N \times d$ 的二维数组，表示每个节点的原始特征向量。
• edges：边列表，每个元素是一个长度为 $2$ 的数组 $[u, v]$，表示节点 $u$ 与 $v$ 之间的无向边。可能出现重复边或自环，重复边将被去重，自环将被忽略。
• train_idx：一维整数数组，给出已知标签的节点索引集合 $T$。
• train_y：与 train_idx 等长的一维数组，值为 $0$ 或 $1$，表示训练节点对应的真实标签。
• test_idx：一维整数数组，给出需要预测标签的节点索引集合。

输出描述

输出为一行 JSON 字符串，包含三个字段：

• weights：长度为 $d$ 的浮点数数组，表示训练得到的权重向量 $w$，每个元素四舍五入保留 $6$ 位小数。
• test_proba：长度与 test_idx 相同的数组，按测试节点顺序给出预测概率 $p_i$，同样四舍五入保留 $6$ 位小数。
• test_pred：长度相同的数组，给出预测的整数标签（$0$ 或 $1$）。

样例1

输入

{"nodes":[[1.0],[2.0],[0.0]],"edges":[[0,1],[1,0]],"train_idx":[0,1],"train_y":[0,1],"test_idx":[2]}

输出

{"weights": [0.332594], "test_proba": [0.500000], "test_pred": [1]}

说明

图中包含重复边 [0,1] 和 [1,0]，去重后实际存在的边只有 0-1。因此节点 0 和 1 组成一个连通分量，节点 2 为孤立节点。

邻域平滑特征计算：节点 0 的邻居为 {1}，$h_0 = (1.0 + 2.0) / 2 = 1.5$；同理 $h_1 = 1.5$；节点 2 度数为 $0$，$h_2 = x_2 = 0.0$。

训练集为节点 0 和 1，$H_T = [[1.5], [1.5]]$，标签 $y_T = [0, 1]$。岭回归参数 $\lambda = 0.01$，计算 $A = H_T^\top H_T + \lambda I = 4.5 + 0.01 = 4.51$，$b = H_T^\top y_T = 1.5$，解得权重 $w = 1.5 / 4.51 \approx 0.332594$（保留 $6$ 位小数）。

测试节点 2 的线性得分 $h_2 \cdot w = 0$，经 logistic 函数得概率 $p_2 = 0.5$，保留 $6$ 位小数为 $0.500000$，按规则 $p_2 \ge 0.5$ 预测为 $1$。

样例2

输入

{"nodes":[[1,0],[0,1],[100,0],[0,-100]],"edges":[],"train_idx":[0,1],"train_y":[0,1],"test_idx":[2,3]}

输出

{"weights": [0.000000, 0.990099], "test_proba": [0.500000, 0.000000], "test_pred": [1, 0]}

说明

图中无边，所有节点的邻域平滑特征等于其原始特征，即 $h_i = x_i$。训练节点 0 和 1 的特征正交，$H_T = [[1,0],[0,1]]$。

计算 $A = H_T^\top H_T + 0.01 I = 1.01 I$，$b = H_T^\top y_T = [0, 1]^\top$，解得 $w = [0,\, 1/1.01] \approx [0.000000,\, 0.990099]$（保留 $6$ 位小数）。

测试节点 2 的特征为 $[100, 0]$，与 $w$ 正交，得分 $\eta_2 = 0$，概率 $p_2 = 0.5$，保留 $6$ 位小数为 $0.500000$，预测为 $1$。测试节点 3 的特征为 $[0, -100]$，得分 $\eta_3 = -99.0099$，经过 logistic 函数后所得概率极其接近 $0$，四舍五入保留 $6$ 位小数为 $0.000000$，预测为 $0$。该样例同时覆盖了预测概率恰为 $0.5$ 和接近于 $0$ 的边界情况。