Pith. sign in

REVIEW 4 major objections 6 minor 53 references

SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read SGS-GNN learns a probability distribution over a graph's edges and claims that a sparse subgraph keeping only 20% of them supports more accurate GNN node classification than the original graph, with the largest gains on heterophilic…

desk verdict A useful 33-graph empirical study of a plausible sparsifier, but the paper never isolates the learned sampling distribution from the edge weights and regularizers, so the central attribution claim is untested. read the letter →

arxiv 2502.10208 v1 pith:HW6FZF7R submitted 2025-02-14 cs.LG

Siddhartha Shankar Das , Naheed Anjum Arafat , Muftiqur Rahman , S M Ferdous , Alex Pothen , Mahantesh M Halappanavar This is my paper
classification cs.LG
keywords graphsparsificationneuralnetworksheterophilicgraphslearnededgedistributionnodeclassificationhomophilyregularizationsamplinglarge-scale
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 proposes SGS-GNN, a supervised graph sparsifier that learns a probability distribution over a graph's edges and samples a user-specified fraction of them, producing a sparse subgraph that a downstream GNN then uses for node classification. The central claim is that this task-aware subgraph is a better input than the full graph itself: with only 20% of edges retained, SGS-GNN improves F1 scores by a geometric mean of 4% relative to the original graph, and on heterophilic graphs—where connected nodes often carry different labels—the gains reach up to 30%. The paper attributes these gains to the sparsifier's ability to down-weight label-dissimilar edges, boosting homophily in the sampled subgraph, and to learn the search space of subgraphs faster than fixed samplers such as random, degree-based, or effective-resistance sampling, converging in about half the epochs. Because roughly 70% of GNN compute sits in neighborhood aggregation, the claim that removing most edges can simultaneously cut cost and raise accuracy is what makes the method worth testing on large graphs.

What carries the argument

The central object is the learned edge-probability distribution $\tilde{p}$ over the original graph's edge set, produced by the EdgeMLP module from node-feature differences and products, normalized by temperature-annealed softmax, and blended with the degree-proportionate prior into $\tilde{p}_a = \lambda\tilde{p} + (1-\lambda)p_{\mathrm{prior}}$. The sampler draws $k$ edges from $\tilde{p}_a$ (multinomial during training, Gumbel-softmax top-k as an alternative), and the downstream GNN consumes both the sampled subgraph and the differentiable edge weights of the chosen edges, so task loss can flow back into EdgeMLP; a conditional-update rule refreshes EdgeMLP only when the learned subgraph beats the prior-generated one on training F1. Two regularizers carry the inductive bias: the assortativity loss pushes weight onto same-label training edges, strengthening homophily in the sampled subgraph, while the consistency loss ties edge probabilities to embedding similarity. The theoretical backbone is a pair of bounds against an idealized oracle: Theorem 4.1 lower-bounds the expected number of edges the learned subgraph shares with the oracle's by $k \sum_{j=1}^{|E|} (p^*_j + \tilde{p}_j - \epsilon)^2/4$, and Theorem 4.2 converts that overlap into an upper bound on the spectral-norm error between GCN node encodings produced from the learned subgraph and from the oracle subgraph.

What would settle it

Train SGS-GNN with the assortativity loss switched off while keeping the learned sampler, on a heterophilic dataset such as Cornell or Roman-empire at the same 20% edge retention, and compare against the degree-prior sampler: if the learned distribution alone recovers little or none of the reported F1 gain over the prior, the claim that the learned distribution—rather than the homophily regularizer—carries the improvement is refuted.

Watch

Extended reading notes

Core claim

The paper's core claim is that the optimal sparse subgraph for a GNN is task-dependent rather than purely structural, and that a neural module can learn the edge distribution that generates it. SGS-GNN's EdgeMLP module maps node features to an edge weight $w(e_{uv}) = \sigma(\mathrm{MLP}_\phi((h_u - h_v) \oplus (h_u \odot h_v)))$, normalizes these weights into a probability distribution over edges, and samples $k = \lfloor q|E|/100 \rfloor$ edges to build the sparse graph handed to the downstream GNN. A temperature-annealed softmax makes the sampler explore broadly early in training and commit later, and the learned distribution is blended with a degree-proportionate prior $p_{\mathrm{prior}}(u,v) \propto 1/d_u + 1/d_v$ so that bridge edges incident to low-degree nodes remain reachable. The training loss is the task cross-entropy plus an assortativity regularizer that raises probability mass on same-label training edges and a consistency regularizer that aligns edge probabilities with the cosine similarity of node embeddings. On 33 datasets the paper reports that with $q = 20\%$ this pipeline beats the original graph by a 4% geometric-mean F1 improvement, outperforms existing sparsification-based GNNs by 4–7% in geometric mean, and halves the epochs needed to converge; one theorem lower-bounds the expected number of edges the learned subgraph shares with an idealized oracle's subgraph, and the other upper-bounds the resulting error in GCN node encodings.

Load-bearing premise

The whole method rests on the task loss genuinely teaching the edge-probability network which edges matter, but the training loop draws edges with a non-differentiable multinomial step (Algorithm 2) and gives no gradient estimator for it, so the only learning signal reaches EdgeMLP through the weights of the edges that happen to be sampled—if that channel is too weak, the reported gains could come from the assortativity regularizer and the degree-based prior alone.

Editorial extensions

If this is right

  • Node classification on heterophilic graphs can be made both cheaper and more accurate by replacing the full graph with a learned 20%-edge subgraph, since the sparsifier strips out label-dissimilar edges that degrade message passing.
  • Sparsity becomes a controllable knob rather than a fixed preprocessing choice: the user sets $q$, and on heterophilic graphs the best accuracy is found at roughly 30–40% edge retention rather than at the densest setting.
  • A learned sampler converges in about half the epochs of fixed-distribution sparsifiers, which compounds the per-epoch savings from fewer edges.
  • The method scales to graphs with tens of millions of edges through graph-partitioned batches, while competing supervised sparsifiers run out of memory on the same datasets.
  • The sparse subgraph is a standalone artifact, so any downstream GNN architecture (GCN, GAT, GIN, ChebNet) can be run on it, making the sparsifier an input transform rather than a new model family.

Reading between the lines

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

  • The learned distribution itself could serve as an edge-attribution map: if the paper's story is right, cross-label edges on heterophilic graphs should receive systematically lower probability mass, giving a way to explain which edges a GNN actually relies on—an application the authors do not explore.
  • An ablation the paper only partially runs—keeping the learned sampler while disabling the assortativity regularizer—would isolate how much of the geometric-mean gain is true distribution learning and how much is homophily enforcement; my expectation is the split is roughly even on heterophilic graphs.
  • Because inference averages over an ensemble of sampled subgraphs, the reported numbers bundle distribution learning with ensemble smoothing; evaluating a single sampled subgraph would separate the two effects.
  • The same machinery should transfer to link prediction or graph-level classification, where the task loss would reshape the learned edge distribution toward task-relevant edges; the paper's framing predicts the learned sampler would beat fixed samplers there as well.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. The paper proposes SGS-GNN, a supervised graph sparsification method for GNN node classification. EdgeMLP encodes each edge by an MLP on node-feature differences and products, normalizes the scores into a probability distribution, augments this distribution with a degree-based prior, and samples a user-specified fraction q of edges. The sampled subgraph, together with learned edge weights, is passed to a downstream GNN; training minimizes cross-entropy plus an assortativity regularizer that up-weights same-label edges and a consistency regularizer that aligns edge weights with embedding cosine similarity. The paper reports experiments on 33 homophilic and heterophilic graphs, claiming roughly 4% geometric-mean F1 improvement over the original graph at 20% edge retention, 4–7% improvement over sparsification baselines, faster convergence, and lower training cost. It also states theoretical bounds on the overlap with an oracle subgraph and on GCN embedding error. I assess the empirical system and the theoretical claims separately below.

Significance. If the attribution issues were resolved, SGS-GNN would be a practically useful contribution: it is an explicit sparsifier with user-controllable sparsity, it supports batching for large graphs, and the empirical study is unusually broad (33 datasets, 10 runs, standard deviations, convergence and runtime comparisons, plus an ablation appendix). The code is said to be available. However, the paper's central scientific claim — that the learned edge-sampling distribution is what drives the gains — is not isolated from the edge weights, the label-based regularizer, and the inference ensemble. Because all ablations keep the learned distribution and the edge weights together, the evidence supports the system as a whole but not the named mechanism. The theoretical bounds are conditional on the learned distribution being epsilon-close to an oracle distribution, so they do not independently support the mechanism either. This is a meaningful gap relative to the paper's claims, but it appears fixable with targeted control experiments.

major comments (4)
  1. [§5.1.1–§5.1.2, Tables 1–2 and §4.3–§4.4] The reported gains of SGS-GNN over fixed-distribution samplers are confounded with at least three other differences: (i) the downstream GNN consumes learned edge weights w~ = w[E~] (Eq. 12), whereas the fixed-distribution baselines are not described as using such learned weights; (ii) SGS-GNN is trained with the label-based assortativity loss (Eq. 14), which directly forces high weights on same-label edges; and (iii) SGS-GNN averages an ensemble of R=10 sampled subgraphs at inference (Alg. 4), while the comparison does not state that Random, Edge, and ER baselines use the same ensemble. Table 8, cases 1–2, shows that adding the ensemble alone changes SmallCora from 69.30 to 72.84 and Roman-Empire from 63.27 to 64.31, so the ensemble effect is not negligible. No ablation in Tables 7–8 replaces the learned sampling distribution with a fixed one while holding the edge weights, regularizers, and ensemble fixed. The claim that the learned sampling distribution produces the 4–7% improvement is therefore unsupported; the observed gains could come from the edge-weight supervision and/or the regularizer alone.
  2. [§4.4, Alg. 2 vs Alg. 4] Training samples from the prior-augmented distribution p~_a = lambda p~ + (1-lambda) p_prior (Alg. 2, lines 7–8), while inference samples from the unaugmented learned distribution p~ (Alg. 4, line 6). Unless the prior is intended only as a training-time regularizer and the deployed distribution is deliberately different, this is a train/inference mismatch: the model is evaluated on a distribution it was never trained to use. The paper should either sample from p~_a at inference (and keep track of the corresponding best temperature) or explicitly justify and analyze the mismatch. As written, the prior-augmentation benefit described in Appendix F.2 and Fig. 9 is undermined.
  3. [§2.1 and §4.4, Eqs. 12–14] The paper states that EdgeMLP 'searches the space G_q by adjusting its learned probability estimate p~ based on the gradient of the loss' (Section 2.1), but the training procedure does not specify a gradient estimator for the discrete sampling step. Algorithm 2 line 8 uses multinomial sampling, and Appendix F.2 confirms that multinomial sampling is used during training; the text only mentions Gumbel-softmax as an alternative (Eq. 10) without using it. Gradients can reach the edge weights w through the downstream GNN (Eq. 12) and through the assortativity/consistency losses (Eqs. 14–15), but those are not gradients of the expected task loss with respect to the sampling probabilities; the derivative through the discrete 'which edges are sampled' operation is unspecified. Without a REINFORCE estimator, a straight-through estimator, or an explicit relaxation, the mechanism by which the sampling distribution is optimized is not established, and the central learning claim is unsupported.
  4. [§4.2, Theorem 4.1 and Appendix A.2] Both theoretical results are conditional on the learned distribution being close to the oracle: Eq. (17) assumes sup_e ||p~(x_e) - p*(x_e)||_1 <= epsilon, and the lower bound in Theorem 4.1 then contains epsilon as an input. Proving that SGS-GNN actually achieves small epsilon is exactly the central open question of the paper, so the theorems do not provide independent support for the method. In addition, p* is introduced as a probability measure over subgraphs (Section 2.1) but is then treated as per-edge marginal probabilities of independent with-replacement draws, without comment on this reduction. The actual sampler produces a set of distinct edges, so the 'with replacement' assumption in Appendix A.2 is not justified relative to the implementation. The theoretical contribution should be reframed as a conditional consistency guarantee or supplemented with a result showing that the training objective drives p~ toward p*.
minor comments (6)
  1. [Eq. (6)] Equation (6) writes the expectation as E[f_GNN(G~) f_EdgeMLP(G)], which is not a valid probability expression; the expectation over G~ of the GNN output should be written with G~ drawn from the learned distribution, not with an extra multiplicative factor.
  2. [Appendix A.4] The proof of Theorem 4.2 claims that the normalized adjacency matrix D^{-1/2}AD^{-1/2} is row-stochastic; this is not true in general. The spectral-norm bound ||A*_hat||_2 <= 1 is valid for symmetric normalized adjacency of an undirected graph, but it requires the standard argument about eigenvalues, not the row-stochastic claim.
  3. [Appendix A.2 and Algorithms 2/4] The paper alternates between sampling with replacement (assumed in Appendix A.2) and a set-valued sparse edge set E~; state explicitly whether the Sample operation in Algorithms 2 and 4 uses replacement, and align the theoretical analysis with the implementation.
  4. [Table 2] Several baseline entries have very large standard deviations (e.g., NeuralSparse on Wisconsin 52.83±47.00 and on Amherst41 56.85±75.00; DropEdge on Photo 80.47±59.10); a robust statistic such as median, or per-run results, would help support the geometric-mean comparisons.
  5. [Fig. 3] The heatmap color scale and numerical labels are difficult to read; the published version should enlarge the figure and define the color scale so the claimed dependence on homophily and sparsity is legible.
  6. [Abstract and Table 1] The '4% geometric mean improvement' in the abstract should state whether the improvement is absolute or relative to the original graph, and the same convention should be used in the Table 1 geometric-mean row.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the empirical comparisons are external, and the theoretical bounds are conditional on the stated approximation assumption rather than being equivalent to it.

full rationale

The paper's headline results (4% geometric-mean F1 improvement at 20% edges, and 4-7% over sparsifier baselines) are obtained by training SGS-GNN on labeled data and testing on held-out nodes against external baselines such as DropEdge, GraphSAINT, NeuralSparse, MOG, and SparseGAT. These comparisons do not assume the conclusion. The theoretical analysis is conditional: Eq. 17 explicitly assumes the learned edge distribution p~ approximates the oracle distribution p* within epsilon, and Theorems 4.1 and 4.2 state bounds in terms of epsilon and the same p~. This makes the theorems weak support for the empirical claims, because the approximation is exactly what the training procedure is supposed to achieve, but the bounds are not definitionally identical to that assumption; they are standard collision and error-propagation bounds. The only same-author citation (Das et al., 2024, AGS-GNN) is used to motivate why uniform sampling is unlikely to minimize the loss on heterophilic graphs; this assertion is also supported by the paper's own experiments and is not the load-bearing step of any derivation. No fitted parameter is renamed as a prediction, and no equation reduces to its own input by construction. Hence no circularity is exhibited.

Assumptions & free parameters 6 free parameters · 7 assumptions · 0 invented entities

The method relies on several hand-chosen hyperparameters (sparsity q, loss weights, temperature, ensemble size) and on assumptions required by the theoretical bounds. The most fragile assumptions are that the optimal edge distribution is a function of node features only and that gradients can flow through the discrete sampling step. No new physical or conceptual entities are introduced beyond the method's own modules.

free parameters (6)
  • q (edge retention percentage) = 20% (following DropEdge)
    User-specified sparsity; all main experiments use 20% of edges.
  • alpha3 (consistency loss coefficient) = 0.5 (recommended)
    Chosen by grid search on Cora (Fig. 10), not reported per dataset.
  • lambda (prior mixing weight) = range [0.3,0.7] recommended, exact value not stated
    Controls blend of learned and degree prior; value used in main experiments is not given.
  • T0, Tmin (temperature annealing bounds) = not reported
    Temperature schedule in Eq. 9 is used for sampling, but numerical values are omitted.
  • H (hidden dimension) = 256
    Hidden dimension for EdgeMLP and GNN; chosen without sensitivity analysis.
  • R (ensemble size at inference) = 10
    Number of sampled subgraphs averaged at inference; chosen by the authors.
assumptions (7)
  • standard math Universal Approximation Theorem applies to the edge-probability function p*
    Invoked in Lemma A.1 to justify that an MLP can approximate the true edge distribution within epsilon.
  • domain assumption The optimal edge distribution p* is a continuous function of node features X
    Assumption (i) in Appendix A.2. If p* depends on labels or graph structure beyond features, the approximation argument fails.
  • domain assumption Node features are bounded and the feature domain is compact
    Used in Lemma A.1 to apply universal approximation on a compact set.
  • domain assumption GNN weight matrices have spectral norm at most alpha < 1
    Assumed in Theorem A.5; claimed to be enforced by weight decay, but not verified in experiments.
  • standard math Normalized adjacency matrix has spectral norm at most 1
    Used in Theorem A.5 proof; holds for D^-1/2 A D^-1/2 without isolated nodes.
  • ad hoc to paper Sampling with replacement approximates the without-replacement algorithm
    Theorem 4.1 assumes with-replacement sampling for analytical convenience, but Algorithm 2 samples a set of distinct edges.
  • domain assumption METIS partitions preserve the learning dynamics of the full graph
    Batch training uses METIS partitions; the paper does not analyze how partition boundaries affect edge sampling or accuracy.

how reviews work

0 comments
Cite this review

Pith. "Pith review of SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks." pith.science (2026). https://pith.science/paper/HW6FZF7R

@misc{pith2026250210208,
  author       = {Pith},
  title        = {Pith review of: SGS-GNN: A Supervised Graph Sparsification method for Graph Neural Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HW6FZF7R}},
  note         = {Machine review of arXiv:2502.10208}
}
read the original abstract

We propose SGS-GNN, a novel supervised graph sparsifier that learns the sampling probability distribution of edges and samples sparse subgraphs of a user-specified size to reduce the computational costs required by GNNs for inference tasks on large graphs. SGS-GNN employs regularizers in the loss function to enhance homophily in sparse subgraphs, boosting the accuracy of GNNs on heterophilic graphs, where a significant number of the neighbors of a node have dissimilar labels. SGS-GNN also supports conditional updates of the probability distribution learning module based on a prior, which helps narrow the search space for sparse graphs. SGS-GNN requires fewer epochs to obtain high accuracies since it learns the search space of subgraphs more effectively than methods using fixed distributions such as random sampling. Extensive experiments using 33 homophilic and heterophilic graphs demonstrate the following: (i) with only 20% of edges retained in the sparse subgraphs, SGS-GNN improves the F1-scores by a geometric mean of 4% relative to the original graph; on heterophilic graphs, the prediction accuracy is better up to 30%. (ii) SGS-GNN outperforms state-of-the-art methods with improvement in F1-scores of 4-7% in geometric mean with similar sparsities in the sampled subgraphs, and (iii) compared to sparsifiers that employ fixed distributions, SGS-GNN requires about half the number of epochs to converge.

Figures

Figures reproduced from arXiv: 2502.10208 by the authors.

Figure 1
Figure 1. Simplified architecture of SGS-GNN. independent use, and thus they do not reduce GNN memory requirements. In contrast, NeuralSparse (Zheng et al., 2020) is an explicit sparsifier that constructs a subgraph based on a neighborhood size, but this approach can lack precise con￾trol over sparsity and may retain unnecessary edges. The vast search space for sparse subgraphs makes it hard for supervised sparsifiers to find… view at source ↗
Figure 2
Figure 2. Illustration of the three modules in SGS-GNN. The edge probability encoding module computes a probability distribution, the sampler module samples the subgraph, and downstream GNN makes predictions using that sparse subgraph. edges to foster homophily in the sampled subgraph. 4 Proposed method: SGS-GNN [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 4
Figure 4. Edge homophily of selected subgraphs from differ [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figures from the paper (6 more)
Figure 5
Figure 5. Figure 5: Number of epochs required by SGS-GNN to con￾verge compared to other samplers under the same settings. 5.1.5 EFFICIENCY [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: The bar shows the mean training time (s) per [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 7
Figure 7. Figure 7: Toy example with two half moon demonstrates the effectiveness of [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]
Figure 8
Figure 8. Figure 8: Performance of SGS-GNN with different GNN modules using 20% edges [PITH_FULL_IMAGE:figures/full_fig_p025_8.png]
Figure 9
Figure 9. Figure 9: The learned probability distribution p˜ (top-left), augmented distribution p˜a(top-right) and fixed prior pprior (bottom). Augmentation puts negligible mass on some rare yet critical edges in the left tail of p˜a. 2. Normalization and Sampling: We considered three norm…
Figure 10
Figure 10. Figure 10: shows a grid search for different combinations of λ and α3. As per our observation, the recommended values are λ ∈ [0.3, 0.7], α3 = 0.5. 0.1 0.3 0.5 0.7 0.9 Consistancy Loss coefficient ( 3) 0.1 0.3 0.5 0.7 0.9 P r i o r c o e ffi c i e n t ( ) Heatmap of F1-Scores 0.…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

53 extracted references · 34 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Augustine, M. T. A survey on universal approximation theorems. arXiv preprint arXiv:2407.12895, 2024

    arXiv 2024

  3. [3]

    A., Srivastava, N., and Teng, S.-H

    Batson, J., Spielman, D. A., Srivastava, N., and Teng, S.-H. Spectral sparsification of graphs: theory and algorithms. Communications of the ACM, 56 0 (8): 0 87--94, 2013

    work page 2013

  4. [4]

    Label-aware graph convolutional networks

    Chen, H., Xu, Y., Huang, F., Deng, Z., Huang, W., Wang, S., He, P., and Li, Z. Label-aware graph convolutional networks. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pp.\ 1977--1980, 2020

    work page 1977

  5. [5]

    Demystifying graph sparsification algorithms in graph properties preservation

    Chen, Y., Ye, H., Vedula, S., Bronstein, A., Dreslinski, R., Mudge, T., and Talati, N. Demystifying graph sparsification algorithms in graph properties preservation. Proceedings of the VLDB Endowment, 17 0 (3): 0 427--440, 2023

    work page 2023

  6. [6]

    Cluster- GCN : An efficient algorithm for training deep and large graph convolutional networks

    Chiang, W.-L., Liu, X., Si, S., Li, Y., Bengio, S., and Hsieh, C.-J. Cluster- GCN : An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp.\ 257--266, 2019

    work page 2019

  7. [7]

    Approximation by superpositions of a sigmoidal function

    Cybenko, G. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2 0 (4): 0 303--314, 1989

    1989

  8. [8]

    S., Ferdous, S., Halappanavar, M

    Das, S. S., Ferdous, S., Halappanavar, M. M., Serra, E., and Pothen, A. AGS-GNN : Attribute-guided sampling for graph neural networks. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.\ 538--549, 2024

    work page 2024

Show all 53 references
  1. [9]

    F., Fomin, F

    Dragan, F. F., Fomin, F. V., and Golovach, P. A. Spanners in sparse graphs. Journal of Computer and System Sciences, 77 0 (6): 0 1108--1119, 2011

    2011

  2. [10]

    Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding

    Fu, X., Zhang, J., Meng, Z., and King, I. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of The Web Conference 2020, pp.\ 2331--2341, 2020

    2020

  3. [11]

    L., Bollacker, K

    Giles, C. L., Bollacker, K. D., and Lawrence, S. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM Conference on Digital Libraries, pp.\ 89--98, 1998

    1998

  4. [12]

    L., and Wagner, D

    Hamann, M., Lindner, G., Meyerhenke, H., Staudt, C. L., and Wagner, D. Structure-preserving sparsification methods for social networks. Social Network Analysis and Mining, 6: 0 1--22, 2016

    2016

  5. [13]

    Inductive representation learning on large graphs

    Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp.\ 1024--1034, 2017

    2017

  6. [14]

    A., and Jin, W

    Hashemi, M., Gong, S., Ni, J., Fan, W., Prakash, B. A., and Jin, W. A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation. arXiv:2402.03358, 2024

    2024 arXiv

  7. [15]

    Convolutional neural networks on graphs with chebyshev approximation, revisited

    He, M., Wei, Z., and Wen, J.-R. Convolutional neural networks on graphs with chebyshev approximation, revisited. Advances in Neural Information Processing Systems, 35: 0 7264--7276, 2022

    2022

  8. [16]

    Categorical reparameterization with Gumbel-Softmax

    Jang, E., Gu, S., and Poole, B. Categorical reparameterization with Gumbel-Softmax . arXiv:1611.01144, 2016

    2016 arXiv

  9. [17]

    Jessica, L. S. E., Arafat, N. A., Lim, W. X., Chan, W. L., and Kong, A. W. K. Finite volume features, global geometry representations, and residual training for deep learning-based cfd simulation. In Proceedings of the 41st International Conference on Machine Learning, ICML'24...

    2024

  10. [18]

    Metis: Unstructured graph partitioning and sparse matrix ordering system

    Karypis, G. Metis: Unstructured graph partitioning and sparse matrix ordering system. Technical report, 1997

    1997

  11. [19]

    and Oh, A

    Kim, D. and Oh, A. How to find your friendly neighborhood: Graph attention design with self-supervision. arXiv:2204.04879, 2022

    2022 arXiv

  12. [20]

    Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. arXiv:1609.02907, 2016

    2016 arXiv

  13. [21]

    Graph evolution: Densification and shrinking diameters

    Leskovec, J., Kleinberg, J., and Faloutsos, C. Graph evolution: Densification and shrinking diameters. ACM transactions on Knowledge Discovery from Data (TKDD), 1 0 (1), 2007

    2007

  14. [22]

    Sgcn: A graph sparsifier based on graph convolutional networks

    Li, J., Zhang, T., Tian, H., Jin, S., Fardad, M., and Zafarani, R. Sgcn: A graph sparsifier based on graph convolutional networks. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp.\ 275--287. Springer, 2020

    2020

  15. [23]

    L., Gupta, V., Bhalerao, O., and Lim, S

    Lim, D., Hohne, F., Li, X., Huang, S. L., Gupta, V., Bhalerao, O., and Lim, S. N. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34: 0 20887--20902, 2021

    2021

  16. [24]

    Dspar: An embarrassingly simple strategy for efficient gnn training and inference via degree-based sparsification

    Liu, Z., Zhou, K., Jiang, Z., Li, L., Chen, R., Choi, S.-H., and Hu, X. Dspar: An embarrassingly simple strategy for efficient gnn training and inference via degree-based sparsification. Transactions on Machine Learning Research, 2023

    2023

  17. [25]

    Learning to drop: Robust graph neural network via topological denoising

    Luo, D., Cheng, W., Yu, W., Zong, B., Ni, J., Chen, H., and Zhang, X. Learning to drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp.\ 779--787, 2021

    2021

  18. [26]

    Biological network analysis with deep learning

    Muzio, G., O’Bray, L., and Borgwardt, K. Biological network analysis with deep learning. Briefings in bioinformatics, 22 0 (2): 0 1515--1530, 2021

    2021

  19. [27]

    Query-driven active surveying for collective classification

    Namata, G., London, B., Getoor, L., Huang, B., and Edu, U. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, pp.\ 1, 2012

    2012

  20. [28]

    C.-C., Lei, Y., and Yang, B

    Pei, H., Wei, B., Chang, K. C.-C., Lei, Y., and Yang, B. Geom- GCN : Geometric graph convolutional networks. arXiv:2002.05287, 2020

    2002 arXiv

  21. [29]

    Characterizing graph datasets for node classification: Beyond homophily-heterophily dichotomy

    Platonov, O., Kuznedelev, D., Babenko, A., and Prokhorenkova, L. Characterizing graph datasets for node classification: Beyond homophily-heterophily dichotomy. arXiv:2209.06177, 2022

    2022 arXiv

  22. [30]

    A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv:2302.11640, 2023

    Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., and Prokhorenkova, L. A critical look at the evaluation of gnns under heterophily: Are we really making progress? arXiv:2302.11640, 2023

    2023 arXiv

  23. [31]

    Dropedge: Towards deep graph convolutional networks on node classification

    Rong, Y., Huang, W., Xu, T., and Huang, J. Dropedge: Towards deep graph convolutional networks on node classification. arXiv:1907.10903, 2019

    1907 arXiv

  24. [32]

    Multi-scale attributed node embedding

    Rozemberczki, B., Allen, C., and Sarkar, R. Multi-scale attributed node embedding. Journal of Complex Networks, 9 0 (2): 0 cnab014, 2021

    2021

  25. [33]

    Collective classification in network data

    Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad, T. Collective classification in network data. AI magazine, 29 0 (3): 0 93--93, 2008

    2008

  26. [34]

    Pitfalls of graph neural network evaluation

    Shchur, O., Mumme, M., Bojchevski, A., and G \"u nnemann, S. Pitfalls of graph neural network evaluation. arXiv:1811.05868, 2018

    2018 arXiv

  27. [35]

    Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. SIAM Journal on Computing, 40 0 (6): 0 1913--1926, 2011

    1913

  28. [36]

    S., Xiao, C., Glass, L., Romberg, J., and Sun, J

    Srinivasa, R. S., Xiao, C., Glass, L., Romberg, J., and Sun, J. Fast graph attention networks using effective resistance based graph sparsification. arXiv:2006.08796, 2020

    2006 arXiv

  29. [37]

    Generic network sparsification via degree-and subgraph-based edge sampling

    Su, Z., Liu, Y., Kurths, J., and Meyerhenke, H. Generic network sparsification via degree-and subgraph-based edge sampling. Information Sciences, 679: 0 121096, 2024

    2024

  30. [38]

    Graph attention networks

    Veli c kovi \'c , P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and Bengio, Y. Graph attention networks. arXiv:1710.10903, 2017

    2017 arXiv

  31. [39]

    Voudigari, E., Salamanos, N., Papageorgiou, T., and Yannakoudakis, E. J. Rank degree: An efficient algorithm for graph sampling. In International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp.\ 120--129. IEEE, 2016

    2016

  32. [40]

    Probability passing for graph neural networks: Graph structure and representations joint learning

    Wang, Z., He, Y., and Liu, B. Probability passing for graph neural networks: Graph structure and representations joint learning. arXiv:2407.10688, 2024

    2024 arXiv

  33. [41]

    Alleviating over-smoothing via graph sparsification based on vertex feature similarity

    Wu, G., Lin, S., Zhuang, Y., and Qiao, J. Alleviating over-smoothing via graph sparsification based on vertex feature similarity. Applied Intelligence, 53 0 (17): 0 20223--20238, 2023

    2023

  34. [42]

    Self-supervised graph learning for recommendation

    Wu, J., Wang, X., Feng, F., He, X., Chen, L., Lian, J., and Xie, X. Self-supervised graph learning for recommendation. In Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval, pp.\ 726--735, 2021

    2021

  35. [43]

    Graph Neural Networks: Foundations, Frontiers, and Applications

    Wu, L., Cui, P., Pei, J., and Zhao, L. Graph Neural Networks: Foundations, Frontiers, and Applications. Springer Singapore, Singapore, 2022

    2022

  36. [44]

    Distributionally Robust Optimization and its Applications in Power System Energy Storage Sizing

    Xie, R. Distributionally Robust Optimization and its Applications in Power System Energy Storage Sizing. Springer Nature, 2024

    2024

  37. [45]

    How powerful are graph neural networks? arXiv:1810.00826, 2018

    Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? arXiv:1810.00826, 2018

    2018 arXiv

  38. [46]

    Xu, X., Yuruk, N., Feng, Z., and Schweiger, T. A. SCAN : A structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining, pp.\ 824--833, 2007

    2007

  39. [47]

    and Ji, S

    Ye, Y. and Ji, S. Sparse graph attention networks. IEEE Transactions on Knowledge and Data Engineering, 35 0 (1): 0 905--916, 2021

    2021

  40. [48]

    Yu, J., Yin, H., Xia, X., Chen, T., Cui, L., and Nguyen, Q. V. H. Are graph augmentations necessary? simple graph contrastive learning for recommendation. In Proceedings of the 45th international ACM SIGIR conference on research and development in information retrieval, pp.\ 1...

    2022

  41. [49]

    GraphSAINT : Graph sampling based inductive learning method

    Zeng, H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V. GraphSAINT : Graph sampling based inductive learning method. In International Conference on Learning Representations, 2019

    2019

  42. [50]

    Graph Sparsification via Mixture of Graphs

    Zhang, G., Sun, X., Yue, Y., Jiang, C., Wang, K., Chen, T., and Pan, S. Graph Sparsification via Mixture of Graphs . arXiv:2405.14260, 2024

    2024 arXiv

  43. [51]

    Robust graph representation learning via neural sparsification

    Zheng, C., Zong, B., Cheng, W., Song, D., Ni, J., Yu, W., Chen, H., and Wang, W. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp.\ 11458--11468. PMLR, 2020

    2020

  44. [52]

    Graph neural networks: A review of methods and applications

    Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., and Sun, M. Graph neural networks: A review of methods and applications. AI open, 1: 0 57--81, 2020

    2020

  45. [53]

    Beyond homophily in graph neural networks: Current limitations and effective designs

    Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33: 0 7793--7804, 2020

    2020

Pith tools

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