Pith. sign in

REVIEW 3 major objections 4 minor 30 references

Hybrid Low-order and Higher-order Graph Convolutional Networks

T0 review · 3 major / 4 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 This paper claims that element-wise max fusion of low- and high-order neighborhoods, with weights shared across orders, lets graph convolutional networks beat prior higher-order models while using fewer trainable parameters.

desk verdict A simple weight-sharing, max-pooling higher-order GCN with modest gains on some benchmarks, but the paper's own tables contradict its state-of-the-art claim and the evaluation protocol is too loose to trust the numbers. read the letter →

arxiv 1908.00673 v1 pith:IQNKVXUL submitted 2019-08-02 cs.LG stat.ML

FangYuan Lei , Xun Liu , QingYun Dai , Bingo Wing-Kuen Ling , Huimin Zhao , Yan Liu This is my paper · ORCID
classification cs.LGstat.ML
keywords graphconvolutionalnetworkhigher-orderneighborhoodweightsharingfusionpoolingtextclassificationsemi-supervisednodecomputationalcomplexity
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 is trying to establish that a graph convolutional network can capture the benefits of higher-order neighborhood information, meaning nodes several hops away, without the usual parameter explosion, by fusing first- through third-order propagated features with element-wise maximum pooling and reusing a single weight matrix across all orders. If the claim is right, the practical payoff is that high-order graph convolution becomes affordable on large graphs: the trainable parameter count stays fixed as the neighborhood order grows, instead of multiplying by the order as in concatenation-based higher-order GCNs. The authors test this on five text networks under supervised learning and three citation networks under semi-supervised learning, reporting the best accuracy on most of those benchmarks with fewer trainable weights than the Text GCN baseline. Their own tables show MR and Pubmed are exceptions where baselines do better, so the claim is not that the fusion wins universally.

What carries the argument

The load-bearing object is the fusion pooling operator $P_{\max}$, an element-wise maximum over the first $p$ neighborhood propagations; it keeps the propagated tensor shape unchanged, so adding another order does not add a new weight matrix. Weight sharing is the companion mechanism: one trainable $W_l$ is applied to every order in a layer, so the parameter count does not scale with $p$. The third piece is right-to-left iterative multiplication, $\hat{A}^p X W_1 = \hat{A}(\cdots(\hat{A}X))W_1$, which avoids explicitly forming dense high powers of the adjacency matrix. Together these pieces carry the argument that high-order neighborhood information can be fused at the parameter cost of a first-order GCN.

What would settle it

An ablation that swaps $P_{\max}$ for element-wise sum on Cora, Citeseer, and the text datasets would settle whether the max-pooling mechanism is load-bearing; if accuracy does not change, the claimed fusion mechanism is not the cause of the improvement. The paper's own MR and Pubmed results already provide a partial negative: on those datasets the hybrid high-order models fall short of the best baselines reported in the same tables.

Watch

Extended reading notes

Core claim

The central discovery, stated on the paper's own terms, is that element-wise max over the first $p$ powers of the normalized adjacency matrix, applied to feature-transformed representations, is a cheap and effective nonlinear way to mix low- and high-order neighborhood information. The HLHG-2 and HLHG-3 models stack two graph convolutional layers and one fusion pooling layer, with propagation $Y = \mathrm{softmax}[P_{\max}(\hat{A}\sigma(H)W_2,\ldots,\hat{A}^p \sigma(H)W_2)]$ where $H = P_{\max}(\hat{A}XW_1,\ldots,\hat{A}^p XW_1)$ and $P_{\max}$ is element-wise maximum. Because the same $W_1$ and $W_2$ are shared across orders, the weight count per layer is $O(r_l r_{l-1})$, independent of the order $p$; the complexity stays $O(r_l p m r_{l-1})$, with $m$ nonzeros in the sparse adjacency matrix. The paper reports that these models reach top accuracy on R52, OH, 20NG, and R8 among text classifiers and on Cora and Citeseer among citation baselines while using fewer parameters than Text GCN.

Load-bearing premise

The paper's accuracy claims rest on the assumption, stated plainly in Section 3.1, that adding and max-fusing higher-order neighborhood features will improve classification accuracy, but no proof is given that element-wise max is the right fusion; the reported results on MR and Pubmed show the assumption does not always hold.

Editorial extensions

If this is right

  • If the paper is right, a two-layer shared-weight max-fusion GCN is sufficient to outperform or match prior higher-order GCN architectures on the citation benchmarks, so the extra parameters spent on per-order weights in concatenation models are not necessary for accuracy.
  • The parameter count of a graph convolutional layer no longer needs to grow with the number of neighborhood hops, making higher-order convolution more practical for large sparse graphs.
  • On the text benchmarks, the reported accuracy on four of five datasets implies that the hybrid fusion captures enough high-order text structure to beat both specialized text classifiers and the Text GCN baseline.
  • The complexity bound $O(r_l p m r_{l-1})$ per layer implies that the price of adding neighbors is a constant factor in the sparse-matrix multiplications, not a blow-up in trainable weights.

Reading between the lines

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

  • A sharp ablation test suggested by, but not run in, the paper would replace $P_{\max}$ with element-wise sum or concatenation on the same datasets; if accuracy does not drop, the max operation itself is not the source of the reported gains.
  • The paper compares complexity and parameters only at the first layer under the assumption $r_0 \gg r_1$; extending the shared-weight construction to deeper or heterogeneous graphs would reveal whether the savings persist beyond the regime tested.
  • Reading across the results, the fusion seems to help least on datasets (MR, Pubmed) where strong first-order baselines already saturate; a natural hypothesis, not stated by the authors, is that higher-order fusion matters most when local neighborhoods are noisy or weakly informative.
  • The authors say they validated $p=4$ and found no significant improvement, which suggests the effective receptive field of these two-layer models is already covered by orders 1 through 3; one could test this by varying the number of layers jointly with the order.
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 / 4 minor

Summary. The paper proposes a hybrid low-order and higher-order graph convolutional network (HLHG) that combines first-, second-, and optionally third-order neighborhood information through an element-wise max fusion pooling layer and shares trainable weights across the different order convolutions. The model is evaluated on five text classification datasets under supervised learning and three citation network datasets under semi-supervised learning. The authors claim that HLHG achieves the highest classification accuracy with a smaller number of trainable parameters compared to prior GCN, HO, and MixHop models, and they compare computational complexity and parameter counts theoretically. The paper also reports that the code and data will be made available.

Significance. If the empirical claims were fully supported, the paper would make a modest but useful contribution: the proposed max-pooling fusion over neighborhood orders with weight sharing is a simple, parameter-efficient alternative to concatenation-based higher-order GCNs such as MixHop, and the complexity analysis in Section 3.3 is a reasonable first step. The authors also provide standard deviations over 100 runs for their own models, which is commendable. However, the central accuracy claim is not supported by the paper's own reported results on all datasets, and the baseline comparisons are not conducted under a controlled protocol. As presented, the evidence does not establish state-of-the-art performance, and the contribution reduces to an incremental heuristic with unresolved validation issues.

major comments (3)
  1. [Abstract and Section 5 vs. Tables 3 and 7] The abstract and conclusion state that the proposed model achieves 'highest classification accuracy', but the reported results contradict this claim on two of the eight benchmarks. In Table 3, on MR, HLHG-2 achieves 75.95 and HLHG-3 achieves 76.49, both below Text GCN's 76.74. In Table 7, on Pubmed, HLHG-2 achieves 79.1 and HLHG-3 achieves 79.3, below MixHop (learned) at 80.8 and HO-4 at 80.1. These are not marginal gaps, and the paper itself acknowledges the MR discrepancy only in passing ('the proposed models yield worse accuracies on the dataset MR'). The unqualified state-of-the-art claim is therefore not justified by the presented evidence and must be re-scoped or supported by a controlled re-evaluation.
  2. [Section 4.2 and Table 7] The citation-network baselines are copied from prior work (Abu-El-Haija et al. and Yang et al.) rather than retrained under the same protocol, and no error bars or standard deviations are reported for those baselines. The text states that 'The benchmark test result copy from [2] and [28]' without specifying whether the train/validation/test splits, number of runs, and hyperparameter selection are identical across methods. Reported gains on Cora (82.7 vs. 81.9) and Citeseer (71.5 vs. 71.4) are within typical run-to-run variability of these baselines, and without a controlled comparison it is impossible to assess whether HLHG actually outperforms them. This weakens the central claim of superiority in semi-supervised node classification.
  3. [Sections 4.1 and 4.2, Tables 2 and 6] Hyperparameters, including the maximum neighborhood order p (2 vs. 3), hidden units, dropout rate, learning rate, epochs, and early-stopping patience, are tuned separately for each dataset without a described validation procedure. Selecting p based on test-set accuracy, as implied by the sentence 'we validate the p = 2 and p = 3 in Eq. (3) for our HLHG models,' introduces selection bias. A nested validation or a fixed protocol applied uniformly across all datasets and baselines is needed to make the reported accuracy differences credible.
minor comments (4)
  1. [Section 3.2, Eq. (3)] Equation (3) contains unbalanced parentheses and applies the activation function σ only to the first argument of Pmax, which obscures the model definition. Equations (4) and (5) are clearer, but the malformed equation should be corrected.
  2. [Section 3.1] There is a typo: 'and andh1' should be 'and h1'. In addition, the phrase 'unsupervised learning' in Section 3.2 appears to be an error; the experiments use semi-supervised learning.
  3. [Table 8] The entries for MixHop (learned) report O(60×1×r) parameters while MixHop reports O(20×3×r); the meaning of the constants (hidden units per order vs. total hidden units) should be clarified to make the parameter-count comparison transparent.
  4. [Section 4.1] The sentence 'our HLHG-3 model has an advantage in computational complexity in dataset MR' compares O(64×3×m×r) with Text GCN's O(200×1×m×r); the difference (192 vs. 200) is minor and the phrasing overstates the advantage. Also, the promised GitHub link for code and data is not provided in the manuscript.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the model's complexity analysis and accuracy claims are empirical benchmark comparisons, and no load-bearing argument reduces to its own inputs.

full rationale

The derivation chain is self-contained. The proposed HLHG architecture is defined by Eqs. (3)-(5) as max-fusion over powers of the normalized adjacency matrix with shared weights, and the complexity claims in Section 3.3, O(r_l * p * m * r_{l-1}) and O(r_l * r_{l-1}), follow directly from that definition. No theorem is invoked to force the accuracy result; the accuracy claims are empirical comparisons against baselines in Tables 3 and 7. The paper contains no self-citations by the present authors, and the cited iterative computation of A^p from [1] is a standard computational identity rather than an unverified premise. The only caveat is that hyperparameters and the order p are selected on the same benchmarks, which is a selection-bias concern, not circularity. The inconsistency between the abstract's 'highest classification accuracy' and the paper's own lower results on MR and Pubmed is a correctness or evidence issue, not a circular derivation.

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

No new physical entities, forces, or conserved quantities are introduced. FusionPooling is a new layer type, not an entity with independent falsifiable handles.

free parameters (3)
  • p (maximum neighborhood order) = 2 or 3
    Selected based on preliminary accuracy experiments; Section 3.2 says p=4 or higher does not significantly improve accuracy.
  • hidden units in first convolutional layer = 128 (R52, OH, 20NG, R8), 64 (MR), 16 (Cora), 8 (Citeseer), 10 (Pubmed)
    Chosen per dataset to balance accuracy and complexity, see Section 4.1 and Section 4.2.
  • training hyperparameters (dropout, learning rate, epochs, L2, early stopping) = reported per dataset in Tables 2 and 6
    Tuned separately for each dataset; no validation protocol is described, so these choices are fit to the evaluation data.
assumptions (5)
  • domain assumption The normalized adjacency matrix  = D^{-1/2}(A+I)D^{-1/2} is a meaningful propagation operator for graph convolution (adopted from GCN [14]).
    Used in Eq. (1) and throughout Section 3; the paper does not re-derive or justify this choice beyond citing Kipf and Welling.
  • domain assumption The graph is undirected, stated at the start of Section 3.1.
    All experiments use undirected text and citation graphs; the method is not analyzed for directed graphs.
  • ad hoc to paper Element-wise max pooling across neighborhood orders preserves or improves discriminative information.
    Pmax is introduced in Section 3.1 as the fusion operator; no theoretical or empirical ablation justifies max over sum or mean.
  • ad hoc to paper Two convolutional layers are sufficient and p=2 or 3 is the best order.
    Section 3.2 reports a preliminary experiment that two layers work better than one and that p=4 does not help; the choice is made on the test tasks without a separate validation set.
  • domain assumption Baseline results copied from prior papers are directly comparable because the same splits and preprocessing are used.
    Tables 3 and 7 reuse numbers from Yao et al. and Abu-El-Haija et al.; if preprocessing differed, the comparisons would be invalid.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hybrid Low-order and Higher-order Graph Convolutional Networks." pith.science (2026). https://pith.science/paper/IQNKVXUL

@misc{pith2026190800673,
  author       = {Pith},
  title        = {Pith review of: Hybrid Low-order and Higher-order Graph Convolutional Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IQNKVXUL}},
  note         = {Machine review of arXiv:1908.00673}
}
read the original abstract

With higher-order neighborhood information of graph network, the accuracy of graph representation learning classification can be significantly improved. However, the current higher order graph convolutional network has a large number of parameters and high computational complexity. Therefore, we propose a Hybrid Lower order and Higher order Graph convolutional networks (HLHG) learning model, which uses weight sharing mechanism to reduce the number of network parameters. To reduce computational complexity, we propose a novel fusion pooling layer to combine the neighborhood information of high order and low order. Theoretically, we compare the model complexity of the proposed model with the other state-of-the-art model. Experimentally, we verify the proposed model on the large-scale text network datasets by supervised learning, and on the citation network datasets by semi-supervised learning. The experimental results show that the proposed model achieves highest classification accuracy with a small set of trainable weight parameters.

Figures

Figures reproduced from arXiv: 1908.00673 by the authors.

Figure 1
Figure 1. The Graph Convolutional Layer of Our Model. (a) is the First Order Graph Convolutional [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Our HLHG model. The graph convolutional network layer of the HLHG model consists [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 20 canonical work pages

  1. [2]

    MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing

    Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolution architectures via sparsified neighborhood mixing. arXiv preprint arXiv:1905.00067, 2019

    work page Pith review arXiv 1905

  2. [28]

    Cohen, and Ruslan R

    Zhilin Yang, William W. Cohen, and Ruslan R. Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016

    work page 2016

  3. [1]

    A higher-order graph convolutional layer

    Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. A higher-order graph convolutional layer. In Proceedings of the 32nd Conference on Neural Information Processing Systems (NIPS 2018). NIPS, 2018

    work page 2018

  4. [3]

    Manifold regularization: A geometric framework for learning from labeled and unlabeled examples

    Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434, 2006

    work page 2006

  5. [4]

    Spectral networks and locally connected networks on graphs

    Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203, 2013

    arXiv 2013

  6. [5]

    Grarep: Learning graph representations with global structural information

    Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM international on conference on information and knowledge management, pages 891–900. ACM, 2015

    work page 2015

  7. [6]

    Convolutional neural networks on graphs with fast localized spectral filtering

    Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pages 3844– 3852, 2016

    work page 2016

  8. [7]

    Neural message passing for quantum chemistry

    Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1263–1272. JMLR. org, 2017

    work page 2017

Show all 30 references
  1. [8]

    Inductive representation learning on large graphs

    Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024–1034, 2017

    2017

  2. [9]

    Deep residual learning for image recognition

    Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016

    2016

  3. [10]

    Deep convolutional networks on graph-structured data

    Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. CoRR, abs/1506.05163, 2015. 9

    2015 arXiv

  4. [11]

    Bag of tricks for efficient text classification

    Armand Joulin, Edouard Grave, Piotr Bojanowski, and Tomas Mikolov. Bag of tricks for efficient text classification. In EACL, 2017

    2017

  5. [12]

    Convolutional neural networks for sentence classification

    Yoon Kim. Convolutional neural networks for sentence classification. In EMNLP, 2014

    2014

  6. [13]

    Adam: A method for stochastic optimization

    Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014

    2014 arXiv

  7. [14]

    Semi-supervised classification with graph convolutional networks

    Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016

    2016 arXiv

  8. [15]

    Imagenet classification with deep convolutional neural networks

    Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pages 1097–1105, 2012

    2012

  9. [16]

    Rossi, Xiangnan Kong, Sungchul Kim, and Anup Rao

    John Boaz Lee, Ryan A. Rossi, Xiangnan Kong, Sungchul Kim, and Anup Rao. Higher-order graph convolutional networks. arXiv preprint arXiv:1809.07697, 2018

    2018 arXiv

  10. [17]

    Deeper insights into graph convolutional networks for semi-supervised learning

    Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018

    2018

  11. [18]

    Recurrent neural network for text classification with multi-task learning

    Pengfei Liu, Xipeng Qiu, and Xuanjing Huang. Recurrent neural network for text classification with multi-task learning. arXiv preprint arXiv:1605.05101, 2016

    2016 arXiv

  12. [19]

    Link-based classification

    Qing Lu and Lise Getoor. Link-based classification. In ICML, 2003

    2003

  13. [20]

    Ahmed, Ted Willke, Dipanjan Sengupta, Michael W

    Guixiang Ma, Nesreen K. Ahmed, Ted Willke, Dipanjan Sengupta, Michael W. Cole, Nicholas B. Turk- Browne, and Philip S. Yu. Similarity learning with higher-order graph convolutions for brain network analysis. 2018

    2018

  14. [21]

    Deepwalk: online learning of social representations

    Bryan Perozzi, Rami Al-Rfou’, and Steven Skiena. Deepwalk: online learning of social representations. In KDD, 2014

    2014

  15. [22]

    Collective classification in network data

    Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI magazine, 29(3):93–93, 2008

    2008

  16. [23]

    Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms

    Dinghan Shen, Yingxu Wang, Wenlin Wang, Martin Renqiang Min, Qinliang Su, Yizhe Zhang, Chunyuan Li, Ricardo Henao, and Lawrence Carin. Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms. In ACL, 2018

    2018

  17. [24]

    Pte: Predictive text embedding through large-scale heterogeneous text networks

    Jian Tang, Meng Qu, and Qiaozhu Mei. Pte: Predictive text embedding through large-scale heterogeneous text networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1165–1174. ACM, 2015

    2015

  18. [25]

    Graph attention networks

    Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Alejandro Romero, Pietro Lió, and Yoshua Bengio. Graph attention networks. CoRR, 2018

    2018

  19. [26]

    Joint embedding of words and labels for text classification

    Yingxu Wang, Chunyuan Li, Wenlin Wang, Yizhe Zhang, Dinghan Shen, Xinyuan Zhang, Ricardo Henao, and Lawrence Carin. Joint embedding of words and labels for text classification. In ACL, 2018

    2018

  20. [27]

    Deep learning via semi-supervised embedding

    Jason Weston, Frédéric Ratle, and Ronan Collobert. Deep learning via semi-supervised embedding. In ICML, 2008

    2008

  21. [29]

    Graph convolutional networks for text classification

    Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. arXiv preprint arXiv:1809.05679, 2018

    2018 arXiv

  22. [30]

    Lafferty

    Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003. 10

    2003

Pith tools

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