Pith. sign in

REVIEW 3 major objections 5 minor 32 references

Initialization for Network Embedding: A Graph Partition Approach

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Warm-starting network embeddings from a graph-partition sketch improves DeepWalk, node2vec, and LINE by up to 8.7%.

desk verdict A plausible partition-based initialization for network embedding, but the propagation step provably collapses to a constant vector per component, so the reported gains are unreproducible as written. read the letter →

arxiv 1908.10697 v4 pith:3BAEMBZP submitted 2019-08-28 cs.SI cs.LG

Wenqing Lin , Feng He , Faqiang Zhang , Xu Cheng , Hongyun Cai This is my paper · ORCID
classification cs.SIcs.LG
keywords networkembeddinginitializationgraphpartitionabstractrandomwalklinkpredictionnodeclassificationhyperparameterlearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper argues that the initialization of a network embedding matters as much as the embedding algorithm itself, and proposes a graph-partition warm start called GPA. GPA partitions the input graph into about $\sqrt{|V|}$ balanced clusters, collapses each cluster into one weighted abstract node, learns an embedding of that small abstract graph by weighted random walks, and then propagates the abstract vectors to the original nodes. The authors claim that, plugged into DeepWalk, node2vec, and LINE, GPA improves link prediction by up to 7.76% and node classification by up to 8.74% over the HARP initialization, while reducing running time by at least 20%. If true, this offers a cheap, structure-aware replacement for random initialization in standard embedding pipelines.

What carries the argument

The load-bearing object is the abstract graph $G_a$, built from a balanced, edge-cut-minimizing partition of the input graph. Because it has only $k \approx \sqrt{|V|}$ nodes, embedding it is cheap, and its weighted edges encode the inter-community structure that a local coarsening could destroy. The second piece is the propagation step: each node starts with its partition's abstract vector and then repeatedly updates $f_i(v)=\frac{1}{2}(f_i(v)+\frac{1}{|N(v)|}\sum_{u\in N(v)} f_i(u))$, which is intended to spread the sketch-level distinctions among nodes inside the same partition while keeping neighboring nodes close. The third piece is a preprocessing regressor that picks the random-walk count and length for the abstract graph from graph statistics, avoiding expensive on-the-fly tuning.

What would settle it

Run GPA on a connected graph with the propagation threshold $\delta$ set to machine precision, so Algorithm 2 truly runs until convergence; if the returned embeddings are near-constant per connected component, the claimed gains cannot come from a converged initialization and must depend on early stopping, while if they are not near-constant, the algorithm as written is not what was executed.

Watch

Extended reading notes

Core claim

The paper's central claim is that a coarse sketch of the graph, obtained by partitioning and then collapsed into an abstract weighted graph, carries enough structural information to initialize fine-grained node embeddings better than both random vectors and the earlier hierarchical HARP initialization. The pipeline is: partition $G$ into $k = \lceil\sqrt{|V|}\rceil$ subsets with small edge cut; build the abstract graph $G_a$ whose nodes are subsets and whose edge weights count cross-partition edges; run a weighted random-walk embedding on $G_a$; copy each abstract node's vector to all nodes in its partition; then smooth these vectors by iteratively averaging each node with its neighbors. The paper reports consistent accuracy gains across four datasets and three embedding algorithms, with the largest gains on LINE, and a runtime reduction of at least 20% relative to HARP.

Load-bearing premise

Algorithm 2's propagation is assumed to converge to a useful non-degenerate initialization, but the update is a linear averaging map whose only fixed point on a connected component is a constant vector, so iterating to convergence would erase all node distinctions; the paper specifies no iteration limit or early-stopping rule that prevents this.

Editorial extensions

If this is right

  • GPA can be added to existing DeepWalk, node2vec, or LINE pipelines without changing their downstream classifiers, since it only replaces the random initialization.
  • Because the abstract graph has about $\sqrt{n}$ nodes, the initialization cost scales more gently than hierarchical coarsening on large graphs.
  • The largest reported gains occur with LINE, the baseline whose random-init performance is weakest, suggesting warm starts help most when the uninitialized algorithm is far from a good optimum.
  • The regression-based hyperparameter selection removes the need to tune random-walk parameters for the sketch, making the warm start practical in a single run.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension is to use the same partition sketch as a pre-training or curriculum step for graph neural networks, where initialization also influences convergence; the paper does not test this.
  • The propagation depth is effectively a free smoothing parameter: with few iterations the vectors stay close to the partition-level sketch, while many iterations flatten intra-partition differences, so the stopping threshold could be tuned per dataset to trade fidelity against smoothness.
  • The abstract-graph idea could be reused for other expensive graph computations, such as spectral clustering or community detection, by solving the problem on $G_a$ and then refining; this is an extrapolation, not a claim in the paper.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes GPA, a graph-partition-based initialization technique for network embedding. The method partitions the input graph, contracts each partition into an abstract node, embeds the abstract graph with a modified DeepWalk that respects edge weights, propagates these embeddings back to the original nodes, and uses the result to initialize DeepWalk, node2vec, and LINE. A regression model trained on random Kronecker graphs is used to choose random-walk hyperparameters for the abstract graph. Experiments on four datasets report up to 7.76% improvement in link prediction and 8.74% in node classification over HARP and random initialization, with at least 20% runtime reduction.

Significance. If the results were valid, the work would be practically useful: warm-starting non-convex embedding objectives is an under-explored direction, and the abstract-graph sketch is a reasonable way to inject global structural information. The paper presents a clear pipeline and uses a standard evaluation protocol with multiple datasets and algorithms. However, the central algorithm as written has a load-bearing flaw in the propagation step, the empirical evidence lacks variance reporting and reproducibility artifacts, and the hyperparameter-learning component is not validated in isolation. The significance is therefore conditional on substantial revision.

major comments (3)
  1. [Section 3.3, Algorithm 2] The propagation step is defined by f'_i(v) = (f_i(v) + average_{u in N(v)} f_i(u)) / 2, and the loop continues while Delta > delta, with delta said to be proportional to 1/|V|. For a connected component, a fixed point of this linear update satisfies f(v) = average_{u in N(v)} f(u), so by the maximum principle f is constant on the component. Running the loop until convergence therefore returns an initialization with no within-component variation; such an initialization cannot account for the gains in Tables 3 and 4. If the authors in fact stop after a small number of iterations, that stopping rule is absent from Algorithm 2, and the experiments are not reproducible from the text. This is a load-bearing issue for the paper's central claim.
  2. [Section 3.4] The hyperparameter regression is trained on random Kronecker graphs and applied to real abstract graphs, but the paper provides no evidence that this transfer is valid. There is no ablation comparing GPA with and without the regression, no report of regression accuracy or of the selected hyperparameters, and no details of the heuristically enumerated hyperparameter combinations. Since the regression is part of the claimed contribution and directly affects the abstract-graph embedding step, the paper needs validation that this component works as intended.
  3. [Section 4, Tables 3/4 and Figure 4] The experiments are reported as averages over 10 runs with no standard deviations, confidence intervals, or significance tests. Several reported differences are small (e.g., Table 3, DeepWalk Euclidean on Wiki: 0.9411 vs 0.9354; Table 4, node2vec micro-F1 on Blog: 0.3174 vs 0.3028), so without variance information the claimed improvements are not statistically substantiated. The paper also does not release code or data, which compounds the reproducibility problem raised in the comment on Algorithm 2.
minor comments (5)
  1. [Section 2, Eq. (1)] Equation (1) reads 'minimizes ... = ...' and should be written as a proper optimization objective; as printed, the equation is not grammatically a minimization problem.
  2. [Section 3.1] The choice k = ceil(sqrt(|V|)) is presented as a heuristic with no sensitivity analysis; since k controls the abstract graph size and the quality of the initialization, a robustness check would strengthen the paper.
  3. [Section 3.4] The statement that hyperparameter values are 'enumerated by heuristic' is underspecified; the actual ranges and the size of the set H are not given, preventing replication of the hyperparameter-learning procedure.
  4. [Section 4.3, Figure 4] Figure 4 reports running time without error bars and does not state exactly which phases (partitioning, abstract embedding, propagation, hyperparameter selection) are included in the measured time.
  5. [Abstract and Section 4.1] The abstract and conclusion state a maximum link-prediction gain of 7.76%, while the text in Section 4.1 reports 7.8% on LINE/Enron; these numbers should be reconciled.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: GPA's gains are empirical comparisons against external baselines, with no derived quantity defined in terms of a fitted parameter.

full rationale

The paper's central claim is an empirical result: GPA initialization yields higher link-prediction and node-classification scores and lower runtime than HARP and Random across four datasets. Nothing in the derivation chain defines a predicted quantity in terms of a fitted parameter. The abstract-graph embedding is computed by an externally defined DeepWalk variant on a graph constructed from METIS partitions; the propagation rule in Algorithm 2 is a fixed averaging operator with no fitted coefficients; and the hyperparameter regressor is trained only on synthetic random graphs, not on the target datasets. The reported gains are computed from held-out test edges/labels after the embedding algorithms run to completion, so the accuracy numbers are not forced by the regression. The one substantive concern I find—Algorithm 2's stated convergence criterion drives each connected component to a constant vector, and no early-stopping rule is specified—is a reproducibility/correctness issue, not a circularity issue: even if it invalidates the experimental numbers, it does not make the derivation equivalent to its inputs. There are no load-bearing self-citations: the cited algorithms (DeepWalk, node2vec, LINE, METIS, alias method) are external, and HARP is an independent baseline. Accordingly, no circular step is identified.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The method's central claim rests on the quality of the METIS partition, the usefulness of the DeepWalk embedding of the abstract graph, the behavior of the propagation loop, and the transferability of the hyperparameter regression. The propagation assumption is demonstrably false as stated.

free parameters (3)
  • k (number of partitions) = ceil(sqrt(|V|))
    User-defined partition count set to ceil(sqrt(|V|)) with the statement that it works well in practice (Section 3.1). No sensitivity analysis is provided.
  • delta (propagation convergence threshold) = proportional to 1/|V| (exact constant unspecified)
    Determines when Algorithm 2 stops. Since the fixed point is a constant vector, the choice of delta and the actual number of iterations control whether the output is degenerate (Section 3.3).
  • regression weight vector w for hyperparameter selection = not reported
    Learned by SGD on hybrid features from synthetic random graphs; the fitted values are never listed (Section 3.4).
assumptions (4)
  • domain assumption METIS produces a (k,epsilon)-balanced partition that preserves global structure and minimizes edge cut (Section 3.1).
    The abstract graph construction assumes partition quality is sufficient for the sketch to be representative.
  • domain assumption DeepWalk/word2vec on the weighted abstract graph yields an embedding that is a useful sketch of G (Section 3.2).
    The method inherits DeepWalk's quality assumptions without new guarantees for weighted abstract graphs.
  • ad hoc to paper Repeated neighbor averaging in Algorithm 2 converges to a useful initial embedding (Section 3.3).
    This assumption is false: the iteration f <- (f + D^{-1}Af)/2 converges to a constant vector per connected component.
  • ad hoc to paper A regression model trained on random Kronecker graphs transfers to real abstract graphs (Section 3.4).
    No evidence is provided that synthetic abstract graph statistics cover the distribution of real abstract graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Initialization for Network Embedding: A Graph Partition Approach." pith.science (2026). https://pith.science/paper/3BAEMBZP

@misc{pith2026190810697,
  author       = {Pith},
  title        = {Pith review of: Initialization for Network Embedding: A Graph Partition Approach},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3BAEMBZP}},
  note         = {Machine review of arXiv:1908.10697}
}
read the original abstract

Network embedding has been intensively studied in the literature and widely used in various applications, such as link prediction and node classification. While previous work focus on the design of new algorithms or are tailored for various problem settings, the discussion of initialization strategies in the learning process is often missed. In this work, we address this important issue of initialization for network embedding that could dramatically improve the performance of the algorithms on both effectiveness and efficiency. Specifically, we first exploit the graph partition technique that divides the graph into several disjoint subsets, and then construct an abstract graph based on the partitions. We obtain the initialization of the embedding for each node in the graph by computing the network embedding on the abstract graph, which is much smaller than the input graph, and then propagating the embedding among the nodes in the input graph. With extensive experiments on various datasets, we demonstrate that our initialization technique significantly improves the performance of the state-of-the-art algorithms on the evaluations of link prediction and node classification by up to 7.76% and 8.74% respectively. Besides, we show that the technique of initialization reduces the running time of the state-of-the-arts by at least 20%.

Figures

Figures reproduced from arXiv: 1908.10697 by the authors.

Figure 1
Figure 1. A graph G with 4 partitions, each of which is colored differently, and the abstract graph Ga of G. algorithms [4, 10, 21, 27], which would highly degrade their per￾formance without careful configuration. However, the previous approaches do not provide any effective solution about the tuning of hyperparameters. To address the aforementioned issues in the previous approaches, we propose a graph partition based algorit… view at source ↗
Figure 2
Figure 2. The computing framework of GPA. Given the graph G = (V, E), the network embedding of G maps each nodev ∈ V to a d-dimensional vector f (v), where f : V → R d and d is a user-defined parameter satisfying d ≪ |V |. In general, network embedding should preserve the structure ofG. In the other words, network embedding minimizes Õ v,u ∈V [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. The generation of training data for hyperparameter learning. [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The running time of the initialization techniques. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 23 canonical work pages

  1. [1]

    James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. 2011. Algorithms for Hyper-Parameter Optimization. In Advances in Neural Information Processing Systems 24: NIPS 2011, Granada, Spain. 2546–2554

    work page 2011

  2. [2]

    Aydin Buluç, Henning Meyerhenke, Ilya Safro, Peter Sanders, and Christian Schulz. 2016. Recent Advances in Graph Partitioning. In Algorithm Engineering - Selected Results and Surveys . 117–158

    work page 2016

  3. [3]

    Zheng, and Kevin Chen-Chuan Chang

    HongYun Cai, Vincent W. Zheng, and Kevin Chen-Chuan Chang. 2017. A Com- prehensive Survey of Graph Embedding: Problems, Techniques and Applications. CoRR abs/1709.07604 (2017). http://arxiv.org/abs/1709.07604

    arXiv 2017

  4. [4]

    Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015. GraRep: Learning Graph Repre- sentations with Global Structural Information. In Proceedings of the 24th ACM International Conference on Information and Knowledge Management, CIKM 2015, Melbourne, VIC, Australia, October 19 - 23, 2015 . 891–900

    work page 2015

  5. [5]

    Haochen Chen, Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2018. A Tutorial on Network Embeddings. CoRR abs/1808.02590 (2018)

    arXiv 2018

  6. [6]

    Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. 2018. HARP: Hierar- chical Representation Learning for Networks. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, USA, February 2-7, 2018

    work page 2018

  7. [7]

    Peng Cui, Xiao Wang, Jian Pei, and Wenwu Zhu. 2017. A Survey on Network Embedding. CoRR abs/1711.08752 (2017)

    work page Pith review arXiv 2017

  8. [8]

    Yoav Goldberg and Omer Levy. 2014. word2vec Explained: deriving Mikolov et al. ’s negative-sampling word-embedding method.CoRR abs/1402.3722 (2014). arXiv:1402.3722 http://arxiv.org/abs/1402.3722

    arXiv 2014

Show all 32 references
  1. [9]

    Palash Goyal and Emilio Ferrara. 2018. Graph embedding techniques, applications, and performance: A survey. Knowl.-Based Syst. 151 (2018), 78–94

    2018

  2. [10]

    Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17,

    2016

  3. [11]

    Hamilton, Rex Ying, and Jure Leskovec

    William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Representation Learning on Graphs: Methods and Applications. IEEE Data Eng. Bull. 40, 3 (2017), 52–74

    2017

  4. [12]

    Hamilton, Zhitao Ying, and Jure Leskovec

    William L. Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive Represen- tation Learning on Large Graphs. In Advances in Neural Information Processing Systems 30: NIPS 2017, Long Beach, CA, USA . 1025–1035

    2017

  5. [13]

    George Karypis and Vipin Kumar. 1995. Analysis of Multilevel Graph Partitioning. In Proceedings Supercomputing, San Diego, CA, USA, December 4-8, 1995 . 29

    1995

  6. [14]

    George Karypis and Vipin Kumar. 1998. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM J. Scientific Computing 20, 1 (1998), 359–392

    1998

  7. [15]

    Kleinberg, and Christos Faloutsos

    Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, and Christos Faloutsos

  8. [16]

    Jure Leskovec and Rok Sosič. 2016. SNAP: A General-Purpose Network Anal- ysis and Graph-Mining Library. ACM Transactions on Intelligent Systems and Technology (TIST) 8, 1 (2016), 1

    2016

  9. [17]

    Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy. 2018. MILE: A Multi-Level Framework for Scalable Graph Embedding. CoRR abs/1802.09612 (2018)

    2018 arXiv

  10. [18]

    Yao Ma, Zhaochun Ren, Ziheng Jiang, Jiliang Tang, and Dawei Yin. 2018. Multi- Dimensional Network Embedding with Hierarchical Structure. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del Rey, CA, USA, February 5-9,...

    2018

  11. [19]

    Corrado, and Jeffrey Dean

    Tomas Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean

  12. [20]

    Dmytro Mishkin and Jiri Matas. 2015. All you need is a good init. CoRR abs/1511.06422 (2015). arXiv:1511.06422 http://arxiv.org/abs/1511.06422

    2015 arXiv

  13. [21]

    Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. DeepWalk: online learning of social representations. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014. 701–710

    2014

  14. [22]

    Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. 2018. Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, WSDM 2018, Marina Del...

    2018

  15. [23]

    Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei

  16. [24]

    Robert Endre Tarjan. 1974. A Note on Finding the Bridges of a Graph.Inf. Process. Lett. 2, 6 (1974), 160–161

    1974

  17. [25]

    Ke Tu, Peng Cui, Xiao Wang, Fei Wang, and Wenwu Zhu. 2018. Structural Deep Embedding for Hyper-Networks. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, New Orleans, USA, February 2-7, 2018

    2018

  18. [26]

    Michael D. Vose. 1991. A Linear Algorithm For Generating Random Numbers With a Given Distribution. IEEE Trans. Software Eng. 17, 9 (1991), 972–975

    1991

  19. [27]

    Daixin Wang, Peng Cui, and Wenwu Zhu. 2016. Structural Deep Network Em- bedding. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016 . 1225–1234

    2016

  20. [28]

    Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. 2015. Network Representation Learning with Rich Text Information. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-3...

    2015

  21. [29]

    Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. 2018. Network Representation Learning: A Survey. CoRR abs/1801.05852 (2018)

    2018 arXiv

  22. [2005]

    In Knowledge Discovery in Databases: PKDD 2005, Porto, Portugal, October 3-7, 2005, Proceedings

    Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication. In Knowledge Discovery in Databases: PKDD 2005, Porto, Portugal, October 3-7, 2005, Proceedings . 133–145

    2005

  23. [2013]

    In Advances in Neural Information Processing Systems 26: NIPS 2013, Nevada, United States

    Distributed Representations of Words and Phrases and their Composition- ality. In Advances in Neural Information Processing Systems 26: NIPS 2013, Nevada, United States. 3111–3119

    2013

  24. [2015]

    In Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015

    LINE: Large-scale Information Network Embedding. In Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015. 1067–1077

    2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.