Don't understand in util.py reconstruct_full function

[xychendave]

Dear author, I read your paper that mentioned the use of Graph Neural Networks (GNN) to recover hidden features, but when I looked at your code in the "util.py reconstruct_full function", it seems like you only used the MSD method to obtain results. Have I misunderstood something?

def reconstruct_full(dim, deg, pr, n, m, fr, to): selected = np.random.choice(np.arange(n), m, replace=False) unselected = np.array(list(set(np.arange(n)) - set(selected))) s = (deg / (pr n n)) 0.25 W = csr_matrix(([s[x] for x in fr], (fr, to))) spd = shortest_path(W, indices=selected) pos_inf = (spd == np.inf) spd[pos_inf] = 0 spd[pos_inf] = spd.max() selected_spd = spd[:, selected] sspd = (selected_spd + selected_spd.T) / 2 sspd = sspd 2 H = np.eye(m) - np.ones(m) / n Ker = - H @ sspd @ H / 2 w, v = np.linalg.eigh(Ker) rec_unnormalized = v[:, -dim:] @ np.diag(w[-dim:]) rec_orig = np.zeros((n, dim)) rec_orig[selected] = rec_unnormalized rec_orig[unselected] = rec_unnormalized[spd[:, unselected].argmin(0)] return rec_orig

[xychendave]

Specifically, In the 'accuracy_of_recovered_features' task in Cora, I didn't observe the backpropagation step for updating 'rec_orign.' Is this a different type of GNN? Thank you for your time.

[WxTu]

Specifically, In the 'accuracy_of_recovered_features' task in Cora, I didn't observe the backpropagation step for updating 'rec_orign.' Is this a different type of GNN? Thank you for your time.

Dear author, I share the same concern as "davechenxy" regarding this matter. Thanks.

[joisino]

Hi,

As shown in Theorem 4.4, a message passing GNN can express the reconstruct_full function. So this is a kind of GNNs. One can rewrite this function in an explicit message-passing manner by the proof of Theorem 4.4. The implementation of reconstruct_full and the message-passing expression are mathematically equivalent, i.e., output the same values, but reconstruct_full is much more efficient (just like Strassen algorithm and the three-for-loop algorithm output the same values, i.e., matrix product, but their efficiency differ.)