Pith. sign in

REVIEW 4 major objections 4 minor 17 references

This paper constructs per-image graphs from lagged correlations between rows and columns, combines them into a Cartesian product graph, and reports that this graph with correlation-based features gives higher GNN classification accuracy tha

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-05 05:55 UTC pith:SBXL7SKU

load-bearing objection A promising graph-construction idea with large GCN/GAT gains, but the paper's universal accuracy claim is contradicted by its own GatedGCN-on-MNIST number. the 4 major comments →

arxiv 2509.04677 v1 pith:SBXL7SKU submitted 2025-09-04 eess.IV cs.CVcs.LGeess.SP

Inferring the Graph Structure of Images for Graph Neural Networks

Mayur S Gowda , John Shi , Augusto Santos , Jos\'e M. F. Moura This is my paper
classification eess.IV cs.CVcs.LGeess.SP
keywords graph neural networksimage classificationgraph structure inferenceproduct graphcorrelation featuresMNISTFashion-MNISTsuperpixels
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper claims that the usual graph representations of images—grid graphs that connect neighboring pixels, and superpixel graphs that group nearby pixels—are not the best inputs for graph neural network classifiers. It builds on a graph-inference method designed for networked time series: treat each row (and each column) of an image as a node, compute lagged correlations between rows and between columns, and feed those correlation matrices to K-means clustering to decide which rows or columns are connected. The inferred row and column graphs are combined into a Cartesian product graph whose nodes are individual pixels, and node features are built from the same lagged correlations. On MNIST and Fashion-MNIST, the paper reports that this product graph with correlation features improves classification accuracy over grid and superpixel graphs for GCN and GAT, and for GatedGCN it improves over both baselines on Fashion-MNIST. The broader point is that graph construction is itself a source of accuracy, independent of the GNN architecture.

Core claim

For each N×N image A, the paper builds a row graph and a column graph. The row graph has N nodes, one per row; for each lag n=0,...,N-1, it computes r_n = (1/N) A (A'_n)^T, where A'_n is A with its rows circularly shifted n times. The N matrices r_0,...,r_{N-1} are fed to K-means clustering, and the cluster assignment decides which pairs of rows are connected by edges. The column graph is built identically from column-shifted versions of A. The pixel-level graph is then the Cartesian product of the row and column graphs, so each pixel corresponds to a (row, column) pair. Node features come from correlation features: the average over lags of (A + (C^l A)^T)/2, organized row-wise and column-wi

What carries the argument

The load-bearing objects are the lagged row-correlation matrices r_n and their column analogues. K-means turns this family of matrices into adjacency matrices of the row graph and column graph, giving a data-driven edge set that links rows or columns whose shifted intensity profiles move together. The Cartesian product graph then lifts those row/column structures to pixel level: edges in the product connect pixels that share a correlated row or column. The correlation feature matrix Gmean — an average of lagged symmetrized shifts — supplies node features that act like a positional or structural embedding, and it is what separates this method from simply swapping the adjacency matrix. Togethe

Load-bearing premise

The method assumes that K-means clustering of the 28 lagged row/column correlation matrices—with its cluster count and edge-mapping rule left unspecified—produces row and column graphs whose edge sets separate informative pixels from background; if those parameters were tuned per image or on the test data, the reported accuracy gains would not generalize.

What would settle it

Rerun the MNIST GCN comparison with the K-means cluster count fixed (say, K=2) and the cluster-to-edge rule chosen on a validation split, never on the test set; if the product graph with correlation features does not beat both grid and superpixel baselines, the claimed improvement is not robust.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • GCN accuracy on MNIST rises from 27.70% with the grid graph to 94.97% with the product graph and correlation features; on Fashion-MNIST it rises from 40.29% to 85.10%, so input graph construction can change a GNN's usefulness by tens of points.
  • GAT accuracy likewise improves on both datasets (73.99% to 96.91% on MNIST; 77.30% to 89.10% on Fashion-MNIST), showing the benefit holds for attention-based aggregation.
  • The column graph outperforms the row graph in the reported experiments, which suggests the method can also be used to identify which spatial direction in an image carries more discriminative structure.
  • For GatedGCN, the product graph beats grid and superpixel baselines on Fashion-MNIST (86.38% vs. 73.71% and 75.25%); the MNIST comparison is mixed because the out-of-the-box GatedGCN model was tuned for superpixels (98.71% vs. 94.36%).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A testable extension is to apply the same row/column lagged-correlation product graph to color images such as CIFAR-10, either per channel or on a grayscale conversion, to see whether the accuracy gain persists outside the two grayscale benchmark sets.
  • The paper leaves the K-means cluster count and the cluster-to-edge assignment rule unspecified; fixing these choices on a validation split would make the method reproducible and would show how much of the gain depends on that hyperparameter.
  • Because the graph is built purely from pixel statistics, the construction could transfer to other grid-like data—sensor arrays, spectrograms, or tabular data with row/column semantics—where a natural spatial graph is not obvious.
  • A modeling next step would be to replace K-means with a differentiable edge-prediction layer, making the graph construction trainable end-to-end with the GNN; the current results suggest the inferred graph, not the classifier, is where the accuracy is won.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 4 minor

Summary. The paper proposes a method for constructing image graphs for GNN-based image classification. For each 28x28 MNIST/Fashion-MNIST image, it computes lagged row and column correlation matrices (Eqs. 1-4), applies K-means clustering to infer row and column graphs, and combines them into a product graph over pixels (Eqs. 5-6). It also designs 'correlation features' (Eqs. 7-9). Experiments compare GCN, GAT, and GatedGCN using grid graphs, superpixels, and the proposed product graph. Table 1 reports gradual gains across the proposed graph/feature variants; Table 2 reports final comparisons. The abstract and conclusion claim that the proposed representation improves accuracy over grid and superpixel methods for all three GNN architectures on both datasets.

Significance. The core idea—transferring lagged-correlation graph inference from networked dynamical systems to image pixels—is original and yields large, consistently reported gains for GCN and GAT, e.g., MNIST GCN rises from 27.70% to 94.97% and Fashion-MNIST GAT from 77.30% to 89.10% (Tables 1-2). Reporting means and standard deviations is a strength, and the comparisons cover three architectures and two datasets. However, the headline claim is contradicted by the paper's own Table 2 for GatedGCN on MNIST (98.71 vs 94.36). The circularity concern raised in the stress-test note is not substantiated: no equation reduces the prediction to a fitted value; the real weakness is that the K-means graph-construction parameters are not specified, making the method unreproducible as presented. If the claims are properly qualified and the missing details are supplied, this would be a useful empirical contribution.

major comments (4)
  1. [Abstract / Section 4 / Table 2] The universal comparative claim is false as stated. Table 2 reports Product Graph (Ours) 94.36±0.02 for GatedGCN on MNIST versus Superpixels 98.71±0.13. This contradicts the abstract's 'improves the accuracy over ... superpixel methods' and the conclusion's 'outperforms ... for GCN, GAT, and GatedGCN on MNIST and Fashion-MNIST'. The explanation that the out-of-box GatedGCN 'may have been specifically tuned' is a hypothesis, not a demonstration. The claim should be qualified (e.g., to GCN/GAT, or to all models on Fashion-MNIST) or supported with additional experiments.
  2. [Section 2.3, Eqs. (5)-(6)] The product-graph definition is not mathematically consistent. Eq. (5) is the Cartesian product adjacency. Eq. (6), A× = A2 ⊙ (A_r ⊗ A_c + A_c ⊗ A_r), is not the Cartesian product; for loopless A_r and A_c, the second factor has zero entries wherever A_r(i,i)=0 or A_c(k,k)=0, so the elementwise product would remove all Cartesian edges. Since the paper does not state whether the row/column graphs include self-loops, the graph actually used in Tables 1 and 2 is undefined. Please specify the exact adjacency construction and the self-loop convention, or state that Eq. (6) is a typo and the intended graph is Eq. (5).
  3. [Section 2.1-2.2, K-means clustering] The K-means step is underspecified. The text says the correlation matrices r_0..r_{N-1} are 'put as input into K-means clustering' without defining the feature vector for each edge, the number of clusters, the initialization, or the rule mapping cluster assignments to edge presence/absence. These choices determine every edge in the row and column graphs and hence the product graph. This is load-bearing for the reported accuracy. Please provide the exact procedure (including whether K=2 is always used and whether any threshold is applied) and, ideally, a sensitivity analysis.
  4. [Section 4, model selection] The choice of the final model appears to use the test set. Section 4 states 'We use the best model: product graph with correlation features (2.5) for comparison with grid graph and superpixels' after Table 1 reports test accuracies for all variants. No validation split or selection procedure is described. Choosing the variant with the highest test accuracy makes the comparison to fixed baselines optimistic. The authors should either use validation-based selection or explicitly report the selection rule.
minor comments (4)
  1. [Eq. (6)] The notation is inconsistent: Eq. (6) defines A× but the preceding text refers to A_x. Please use one symbol throughout.
  2. [Table 1] Standard deviations are reported only for the last three graph variants. For completeness, report them also for the grid, row, and column graph columns.
  3. [Section 2.5, Eq. (9)] G_mean is defined as an N^2 x N^2 matrix, and the text says 'Each row ... serves as a (N^2,) feature vector.' This is confusing: each of the N^2 nodes would receive an N^2-dimensional feature. Please clarify the construction and explain how this large feature dimension is handled by the downstream GNNs.
  4. [General] Reference [4] appears to be an arXiv preprint; provide a venue or version if available. Also, Figures 4 and 6 are small; enlarging them would improve readability.

Circularity Check

0 steps flagged

No significant circularity: graph construction is applied per image and evaluated against external baselines; prior-work citations are method citations, not load-bearing evidence.

full rationale

The derivation chain is empirical and self-contained. Sections 2.1–2.3 construct row, column, and product graphs from lagged correlation matrices and K-means clustering; Section 2.5 defines correlation features. No equation fits a parameter to the evaluation target and then reports it as a prediction. The use of references [5,6] is a method citation, not an imported uniqueness theorem or ansatz that forbids alternatives; the paper's central claim is tested against grid and superpixel baselines in Table 2. There are internal-consistency and reporting concerns—Table 2 shows GatedGCN on MNIST with superpixels at 98.71±0.13 versus Product Graph (Ours) at 94.36±0.02, contradicting the abstract's universal improvement claim, and the K-means cluster count and edge-mapping rule are unreported—but these are correctness/experimental-reporting issues, not circularity. The new result (relative accuracy on downstream GNNs) is not equivalent by construction to any input or fitted value.

Axiom & Free-Parameter Ledger

3 free parameters · 4 axioms · 0 invented entities

The central accuracy claims rest on the per-image graph construction, whose main tunable choices (K-means cluster count, edge threshold, number of lags) are not specified. The method borrows the networked-dynamical-system inference from the authors' prior work [5,6] and the product graph from GSP [10,11]. No new entities are introduced.

free parameters (3)
  • K-means cluster count = not reported
    K-means is used in Sections 2.1 and 2.2 to turn lagged correlation matrices into row and column edges; the number of clusters and the rule mapping clusters to edges are never stated, and the resulting graphs are the foundation of the product graph.
  • edge decision threshold = not reported
    K-means labels edge pairs as connected or not, but the paper does not say how many edges are selected or how thresholds are set; this controls graph sparsity and downstream accuracy.
  • number of circular lags = 28 (all N shifts)
    The method uses all 28 row and column circular shifts for MNIST and Fashion-MNIST with no justification; this choice affects which correlations are averaged into features and the input dimension to K-means.
axioms (4)
  • domain assumption Pixels in an image can be modeled as a networked dynamical system whose pairwise lagged correlations reveal a meaningful underlying graph.
    The introduction states 'Similar to networked dynamical systems in [5,6], pixels in an image may be coupled to other pixels'; this is the core analogy that justifies applying the time-series method to images.
  • ad hoc to paper Cyclic shifts of rows and columns are a valid way to define lagged relationships for image data.
    Equations (1) and (3) use a circular shift matrix C; images are not periodic, so the wrap-around correlations are an unreported modeling choice.
  • domain assumption K-means clustering of the correlation matrices yields edge sets that are better for classification than the grid graph.
    Section 2.1 says 'We put the correlation matrices ... into K-means clustering to find the row graph', but no separation guarantee or parameter criterion is provided.
  • ad hoc to paper The Cartesian product graph formula produces a useful pixel-level graph.
    Equation (6), A_x = A2 * (A_r x A_c + A_c x A_r), is a specific masked product chosen without derivation; other products or masks could behave differently.

pith-pipeline@v1.4.0-alltime-deepseek-medium · 6514 in / 12310 out tokens · 112551 ms · 2026-08-05T05:55:41.889250+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of Inferring the Graph Structure of Images for Graph Neural Networks." pith.science (2026). https://pith.science/paper/SBXL7SKU

@misc{pith2026250904677,
  author       = {Pith},
  title        = {Pith review of: Inferring the Graph Structure of Images for Graph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SBXL7SKU}},
  note         = {Machine review of arXiv:2509.04677}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Image datasets such as MNIST are a key benchmark for testing Graph Neural Network (GNN) architectures. The images are traditionally represented as a grid graph with each node representing a pixel and edges connecting neighboring pixels (vertically and horizontally). The graph signal is the values (intensities) of each pixel in the image. The graphs are commonly used as input to graph neural networks (e.g., Graph Convolutional Neural Networks (Graph CNNs) [1, 2], Graph Attention Networks (GAT) [3], GatedGCN [4]) to classify the images. In this work, we improve the accuracy of downstream graph neural network tasks by finding alternative graphs to the grid graph and superpixel methods to represent the dataset images, following the approach in [5, 6]. We find row correlation, column correlation, and product graphs for each image in MNIST and Fashion-MNIST using correlations between the pixel values building on the method in [5, 6]. Experiments show that using these different graph representations and features as input into downstream GNN models improves the accuracy over using the traditional grid graph and superpixel methods in the literature.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

  1. [1]

    Inferring the Graph Structure of Images for Graph Neural Networks

    INTRODUCTION Graph Neural Networks (GNNs) extend traditional deep learning on grid-based signals to signals defined on irregular structures (graphs). Graph Convolutional Neural Networks (Graph CNNs) [1, 2] extend the traditional CNN framework, used for image classification, to graph data. While designed for graph data, GNNs frequently use image datasets s...

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  2. [2]

    We first produce a row and column correlation graph using the method in [5, 6]

    OUR MODEL In this section, we outline the parts of our model. We first produce a row and column correlation graph using the method in [5, 6]. Then, using these graphs, we form the product graph. Then, we focus on the features. We start with the pixel features, then use common image features such as mean and variance, and Fig. 2: Our approach, building on ...

    work page

  3. [3]

    Both datasets have 70,000 images with 60,000 im- ages for training and 10,000 for testing

    DA TASETS AND MODELS The experiments were conducted using the MNIST and Fashion- MNIST datasets. Both datasets have 70,000 images with 60,000 im- ages for training and 10,000 for testing. They both consist of28×28 size grayscale images. MNIST consists of images of handwritten digits. Fashion-MNIST consists of images of clothing. Three mod- els were used: ...

    work page

  4. [4]

    RESULTS Table 1 illustrates the accuracies of GCN and GAT for the different graph formation methods we developed in Section 2 for MNIST and Fashion-MNIST using GCNs and GAT. Starting from a grid graph, we iteratively improve the graph structure and the graph features used in the graph formation step (Sections 2.1 to 2.5), obtaining a gradual accuracy incr...

    work page

  5. [5]

    We achieve this by inferring the underlying graph for im- ages using the correlation method in [5, 6]

    CONCLUSION In this work, we improve the accuracy for downstream graph clas- sification tasks by choosing a more meaningful graph structure and features. We achieve this by inferring the underlying graph for im- ages using the correlation method in [5, 6]. Our method uses a prod- uct graph, formed by taking the product of row and column graphs. Instead of ...

    work page

  6. [6]

    The correlation features accurately highlight the parts of the num- ber in the image. Dataset Grid Graph Row Graph (2.1) Column Graph (2.2) Product Graph (Pixel) (2.3) Product Graph (Common) (2.4) Product Graph (Ours) (2.5) GCN GA T GCN GA T GCN GA T GCN GA T GCN GA T GCN GA T MNIST 27.70 73.99 71.35 92.58 87.18 95.07 55.05 ±2.89 76.45 ±0.067 73.36 ±2.04 ...

    work page

  7. [7]

    Semi-supervised classi- fication with graph convolutional networks,

    Thomas N. Kipf and Max Welling, “Semi-supervised classi- fication with graph convolutional networks,” inInternational Conference on Learning Representations (ICLR), 2017

    work page 2017

  8. [8]

    Topology adaptive graph convolutional networks,

    Jian Du, Shanghang Zhang, Guanhang Wu, Jose M. F. Moura, and Soummya Kar, “Topology adaptive graph convolutional networks,”CoRR, 2017

    work page 2017

  9. [9]

    Graph attention networks,

    Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adri- ana Romero, Pietro Li`o, and Yoshua Bengio, “Graph attention networks,” inInternational Conference on Learning Represen- tations (ICLR), 2018

    work page 2018

  10. [10]

    Can classic gnns be strong baselines for graph-level tasks? simple architectures meet excellence,

    Yuankai Luo, Lei Shi, and Xiao-Ming Wu, “Can classic gnns be strong baselines for graph-level tasks? simple architectures meet excellence,” 2025

    work page 2025

  11. [11]

    Learning the causal structure of networked dynam- ical systems under latent nodes and structured noise,

    Augusto Santos, Diogo Rente, Rui Seabra, and Jos ´e M. F. Moura, “Learning the causal structure of networked dynam- ical systems under latent nodes and structured noise,” in Proceedings of the Thirty-Eighth AAAI Conference on Arti- ficial Intelligence and Thirty-Sixth Conference on Innovative Applications of Artificial Intelligence and Fourteenth Sympo- s...

    work page 2024

  12. [12]

    Inferring the graph of networked dynamical sys- tems under partial observability and spatially colored noise,

    Augusto Santos, Diogo Rente, Rui Seabra, and Jos ´e M. F. Moura, “Inferring the graph of networked dynamical sys- tems under partial observability and spatially colored noise,” inICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2024, pp. 13156–13160

    work page 2024

  13. [13]

    Graph convolutional networks for image classification: Comparing approaches for building graphs from images,

    J ´ulia Rodrigues and Joel Carbonera, “Graph convolutional networks for image classification: Comparing approaches for building graphs from images,” 05 2024

    work page 2024

  14. [14]

    Slic superpixels,

    Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aur ´elien Lucchi, Pascal Fua, and Sabine S ¨usstrunk, “Slic superpixels,” Technical report, EPFL, 06 2010

    work page 2010

  15. [15]

    Discrete signal processing on graphs,

    A. Sandryhaila and J. M. F. Moura, “Discrete signal processing on graphs,”IEEE Trans. Signal Proc., vol. 61, no. 7, pp. 1644– 1656, April 2013

    work page 2013

  16. [16]

    Graph signal processing: Overview, challenges, and applications,

    Antonio Ortega, Pascal Frossard, Jelena Kova ˇcevi´c, Jos´e M. F. Moura, and Pierre Vandergheynst, “Graph signal processing: Overview, challenges, and applications,”Proceedings of the IEEE, vol. 106, no. 5, pp. 808–828, 2018

    work page 2018

  17. [17]

    Graph signal processing: The 2d companion model,

    John Shi and Jos ´e M. F. Moura, “Graph signal processing: The 2d companion model,” inICASSP 2024 - 2024 IEEE Interna- tional Conference on Acoustics, Speech and Signal Processing (ICASSP), 2024, pp. 9806–9810

    work page 2024