Pith. sign in

REVIEW 3 major objections 5 minor 62 references

AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening

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

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

Pith's one-line read A hash-sorted list yields every coarsening ratio in one pass.

desk verdict A useful incremental extension of UGC with strong experiments, but the theory is thinner than claimed and a key baseline is missing. read the letter →

arxiv 2505.15842 v1 pith:I3NRWK4U submitted 2025-05-18 cs.SI cs.LG

Mohit Kataria , Shreyash Bhilwade , Sandeep Kumar , Jayadeva This is my paper · ORCID
classification cs.SIcs.LG
keywords graphcoarseninglocality-sensitivehashingconsistentadaptivemulti-resolutionheterogeneousgraphstype-isolatedreductionnodeclassification
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

AH-UGC claims that graph coarsening can be made adaptive and type-aware by replacing per-ratio recomputation with a single sorted list of locality-sensitive hash scores. Each merge on that list joins a randomly chosen node with its clockwise neighbor, so different coarsening ratios are only successive merges on the same list, and moving from ratio $R$ to ratio $T$ requires no reprocessing. For heterogeneous graphs, nodes are grouped by type and each type is coarsened independently, so a supernode never mixes semantically different node types. If the claims hold, graph coarsening becomes a one-pass, multi-resolution operation that scales to graphs with millions of edges while preserving both spectral structure and heterogeneous semantics.

What carries the argument

The mechanism is a sorted list of aggregate LSH scores operated on by consistent-hashing clockwise merges. For each node $v_i$, the augmented feature vector $F_i=(1-\alpha)X_i\oplus\alpha A_i$ is projected $l$ times and averaged to a scalar $s_i$; sorting these scores gives an ordered list in which each super-node initially contains one node, and each coarsening step picks a super-node at random and merges it with its immediate right neighbor. LSH is what makes similar nodes land near each other (Theorem 3.1 and Lemma 1), consistent hashing is what allows any ratio to be read off the same list, and the per-type partition of the heterogeneous procedure is what keeps supernodes type-pure.

What would settle it

Compute, on a labeled graph with two well-separated feature clusters, the fraction of AH-UGC merges that join nodes whose feature distance exceeds the median pairwise feature distance. If that fraction approaches the random-pair baseline, the sorted-list adjacency that LSH is supposed to provide is not materializing.

Watch

Extended reading notes

Core claim

The central claim is that combining locality-sensitive hashing (LSH) with consistent hashing produces a single-pass, multi-resolution coarsening procedure. Node features and adjacency rows are blended by a heterophily factor $\alpha$, projected with random Gaussian vectors, and the mean projection score per node is sorted; repeated clockwise merges in that sorted list then produce coarsened graphs at any target ratio $R=|V_c|/|V|$, with transitions from one ratio to another obtained by continuing or reversing the merge history. The paper further claims that restricting merges to nodes of the same type preserves the heterogeneous schema, and that the coarsened features and adjacency $\tilde X = C^\top X$, $\tilde A = C^\top A C$ retain enough structure for downstream GNN training on the coarsened graph to match or beat baseline coarsening methods on node classification and spectral fidelity.

Load-bearing premise

The load-bearing premise is that sorting nodes by an average of random projection scores places mutually similar nodes adjacent in the sorted list, so that each clockwise merge joins two nodes that belong together; this adjacency is asserted by Lemma 1, which is stated without proof, while Theorem 3.1 only bounds pairwise projection distance and does not guarantee contiguous blocks.

Editorial extensions

If this is right

  • Multiple coarsening ratios, such as 55% down to 10%, are produced from one sorted list, so interactive visualization and real-time recommendation systems can switch resolutions without recomputing.
  • New nodes arriving in a streaming graph can be inserted into the existing sorted list and coarsened incrementally rather than restarting from scratch.
  • Type-isolated coarsening ensures that supernodes in heterogeneous graphs remain single-type, which avoids semantic drift and keeps node-classification accuracy close to the uncoarsened baseline.
  • The method scales to datasets where optimization-based coarseners run out of time or memory; on large graphs like ogbn-arxiv and Reddit it is the only tested method to finish.
  • Because de-coarsening reverses the merge history, the framework enables coarse-to-fine reconstruction of graph representations.

Reading between the lines

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

  • If the locality premise holds, the quality gap between AH-UGC and an exact similarity-based coarsening could be measured by comparing each actual merge against the nearest-neighbor merge from the same sorted list; a small gap would support using the shortcut in practice.
  • Adaptivity makes the coarsening ratio a tunable parameter of multi-scale GNN training rather than a preprocessing decision: one could coarsen the same graph at several ratios and train a shared model on all resolutions in a single run.
  • The load-balance bound suggests a concrete extension: use AH-UGC supernodes as balanced partitions for distributed graph computation, since the expected supernode sizes hover near $n/k$ with high probability.
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 AH-UGC, a graph-coarsening framework that combines LSH projections with consistent hashing to produce multiple coarsening resolutions from a single sorted hash-score list, together with a type-isolated variant for heterogeneous graphs. Nodes are assigned scalar scores by averaging l random projections of an augmented feature-adjacency vector, sorted by those scores, and coarsened by repeatedly selecting a supernode uniformly at random and merging it with its clockwise neighbor. Heterogeneous graphs are processed separately per node type, with per-type coarsening matrices and per-edge-type adjacency aggregation. The authors claim adaptive multi-resolution coarsening, balanced supernodes, semantic purity, and superior scalability, and support these claims with runtime, spectral, and node-classification experiments on up to 23 datasets.

Significance. AH-UGC addresses two genuine gaps: no existing coarsening method provides ratio-adaptive multi-resolution output in a single pass, and homogeneous coarsening methods violate type semantics on heterogeneous graphs. The consistent-hashing construction is simple and fast, and the runtime results in Table 1 are striking, with AH-UGC often an order of magnitude faster than UGC on large graphs. The type-isolation strategy is a clean, credible mechanism for heterogeneous semantic preservation, and Tables 3 and 4 show consistent gains over the included baselines. The main weakness is that the theoretical support for the central locality claim (Lemma 1) is incomplete and likely too weak, and the load-balance theorem rests on an unsubstantiated uniform-spacing model. The heterogeneous comparison also omits the only dedicated heterogeneous baseline, HGCond. These issues are fixable, but they currently leave the central 'groups similar nodes' claim unproven.

major comments (3)
  1. [Section 3.1 (Lemma 1)] The claim that 'similar nodes are positioned adjacently' depends entirely on Lemma 1, yet the lemma is stated without proof and its bound cannot deliver the conclusion. For ||x-y|| much smaller than ||x-z||, the bound Phi(||x-y|| sqrt(l) / ||x-z||) is approximately 1/2 + O(||x-y||/||x-z||), i.e., an upper bound near 1/2, so it does not establish that a distant point 'rarely interrupts' a close pair. Moreover, Theorem 3.1 gives only a pairwise projection probability and says nothing about whether other points' scores lie between two close points, so the sorted-list contiguity assumption is unsupported. Because random clockwise merges create arbitrary contiguous blocks of the sorted list, the quality guarantee of the coarsening is not established. Please supply a rigorous contiguity or block-similarity bound, or re-frame the claim as a heuristic and add empirical validation, such as measuring intra-block similarity versus random partitions on the real datasets.
  2. [Appendix C (Theorem 3.2)] The load-balance proof models the sorted node positions as k-1 i.i.d. Uniform(0,1) order statistics and then states that the sorted list 'can be modeled as uniformly spaced over [0,1]'. Neither step follows from Algorithm 1: the actual process selects a supernode uniformly at random among the current supernodes and merges it with its right neighbor, which is a different stochastic process from placing k-1 uniform cuts, and the uniform-spacing assumption on the aggregate LSH scores is unverified. The claimed bound Pr[max_i |S_i| <= n/k + n(log k + c)/k] >= 1 - e^{-c} is therefore not proven for the algorithm as written. Please provide a proof that directly analyzes the merge process, or clearly state the uniform-spacing assumption as an additional hypothesis and validate it empirically.
  3. [Section 4.3 and Table 4] The heterogeneous-graph evaluation omits HGCond, which the Related Work section identifies as 'the only approach designed for heterogeneous graphs.' Without this baseline, the claim that AH-UGC consistently outperforms existing methods on heterogeneous graphs is incomplete, and the large margins over type-blind baselines could mainly reflect the type-isolation mechanism rather than the adaptive LSH contribution. Please add HGCond to Table 4 and, where feasible, report standard deviations over multiple runs for the key comparisons.
minor comments (5)
  1. [Definition 2.3 / Section 3.1 / Algorithm 1] The orientation of the coarsening matrix C is inconsistent: Definition 2.3 defines C in R^{N x n} with eX = C^T X, while Section 3.1 and Algorithm 1 define C as an n_c x N matrix with eF = C F and eA = C A C^T. Please fix the notation so all formulas are dimensionally consistent.
  2. [Theorem 3.1 and Appendix D] The expression erf(epsilon sqrt(2 l ||x-y||)) appears to be missing a division bar; the standard form is erf(epsilon / (sqrt(2 l) ||x-y||)). Please clarify the formula.
  3. [Algorithm 1] Lines 3 and 5 both compute S <- F * W + b; remove the duplicate.
  4. [Figures and dataset counts] Figure 2 labels the method 'HA-UGC' instead of 'AH-UGC', the abstract says 23 datasets while Appendix A says 24, and Table 5 lists 'Penn49' while the text uses 'Penn94'. Please correct these inconsistencies.
  5. [Table 1] Table 1 reports total time for ten target ratios, so baseline times include ten independent runs while AH-UGC performs one pass. Please state this explicitly and consider adding a single-ratio runtime comparison to separate the adaptivity gain from raw per-run speed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: adaptivity and type-isolation are constructional properties, and the theoretical claims are standard LSH facts plus stated modeling assumptions, not fits or self-citation chains.

full rationale

AH-UGC's adaptive coarsening is a property of the algorithm's construction: the sorted list is computed once, and different target ratios are reached by continuing clockwise merges, so R-to-T transitions follow from the merge rule itself rather than from a fitted parameter. The heterogeneous guarantee is likewise enforced by restricting merges to same-type nodes, matching the paper's Goal 2 constraints by definition. No quantity is fitted to a subset and then reported as a prediction; the heterophily factor alpha is a label-based input, and the empirical evaluations compare held-out classification accuracy, not a fitted parameter. Theorem 3.1 is a standard Gaussian projection calculation with an elementary proof; Theorem 3.2 derives a load-balance bound but explicitly relies on a uniform-spacing model of the sorted list, which is an ad hoc modeling assumption rather than an input-output circularity. The paper's main weakness is non-circular: Lemma 1, which is supposed to connect pairwise projection closeness to contiguity in the sorted list, is stated without proof and is too weak to guarantee that random clockwise merges group similar nodes. Self-citations to the authors' UGC paper describe the prior framework being extended and are not used as evidence to forbid alternatives or to establish a load-bearing theorem. Therefore no circular step can be exhibited, and the score is 0.

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

The central claim rests on standard LSH facts plus two ad hoc modeling assumptions in the proofs (Lemma 1 and the uniform-spacing model in Theorem 3.2). The method itself introduces no invented entities; alpha and l are data/user-chosen parameters, and the augmented feature construction is inherited from UGC.

free parameters (2)
  • l (number of LSH projections)
    User-chosen hyperparameter; not reported in the experiments, affects hash score quality and runtime.
  • alpha (heterophily factor) = computed from label agreement fraction
    Data-dependent mixing weight between features and adjacency, inherited from UGC; requires labels during coarsening.
assumptions (5)
  • standard math Gaussian random projections of close points yield close scalar scores (Theorem 3.1)
    Standard p-stable projection property; proof supplied in Appendix D.
  • ad hoc to paper Sorted scalar hash scores place similar nodes adjacently, with distant nodes rarely interrupting (Lemma 1)
    Stated without proof and not implied by pairwise proximity alone; the paper relies on it to justify clockwise merges.
  • ad hoc to paper The sorted node list can be modeled as uniformly spaced over [0,1] for load-balance analysis (Theorem 3.2)
    This modeling assumption is not derived from the hashing distribution or the merge process; the actual process yields a uniformly random composition, so the proof is approximate at best.
  • domain assumption Augmented features F=(1-alpha)X +_concat alpha A capture both attribute and structural similarity
    Inherited from UGC; the choice of linear mixing with alpha is heuristic.
  • domain assumption Node labels are available to compute alpha
    The method requires labels at coarsening time, limiting applicability to unsupervised settings.

how reviews work

0 comments
Cite this review

Pith. "Pith review of AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening." pith.science (2026). https://pith.science/paper/I3NRWK4U

@misc{pith2026250515842,
  author       = {Pith},
  title        = {Pith review of: AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I3NRWK4U}},
  note         = {Machine review of arXiv:2505.15842}
}
abstract

$\textbf{Graph Coarsening (GC)}$ is a prominent graph reduction technique that compresses large graphs to enable efficient learning and inference. However, existing GC methods generate only one coarsened graph per run and must recompute from scratch for each new coarsening ratio, resulting in unnecessary overhead. Moreover, most prior approaches are tailored to $\textit{homogeneous}$ graphs and fail to accommodate the semantic constraints of $\textit{heterogeneous}$ graphs, which comprise multiple node and edge types. To overcome these limitations, we introduce a novel framework that combines Locality Sensitive Hashing (LSH) with Consistent Hashing to enable $\textit{adaptive graph coarsening}$. Leveraging hashing techniques, our method is inherently fast and scalable. For heterogeneous graphs, we propose a $\textit{type isolated coarsening}$ strategy that ensures semantic consistency by restricting merges to nodes of the same type. Our approach is the first unified framework to support both adaptive and heterogeneous coarsening. Extensive evaluations on 23 real-world datasets including homophilic, heterophilic, homogeneous, and heterogeneous graphs demonstrate that our method achieves superior scalability while preserving the structural and semantic integrity of the original graph.

Figures

Figures reproduced from arXiv: 2505.15842 by the authors.

Figure 1
Figure 1. AH-UGC consists of three modules: (a) MLSH constructs an augmented feature matrix by combining node features and structural context using a heterophily-aware factor α, enabling support for both homophilic and heterophilic graphs. Inspired by UGC [4], we use LSH projections to compute node hash indices via ψ(h Pkl 1) (see Section 3); (b) MCH applies consistent hashing to merge nodes clockwise based on a target coarse… view at source ↗
Figure 2
Figure 2. Comparison of capability support across existing GC methods. Goal 1. The objective is to compute multiple coarsened graphs {G(r) c } R r=1 from input graph G(V, A, X), where each G (r) c corresponds to a target coarsening ratio r ∈ (0, 1], with￾out recomputing from scratch for each resolution. Formally, the goal is to construct a family of coarsening matrices {C(r) ∈ R N×n (r) } such that Xe(r) = (C (r) ) ⊤X, Ae(r) … view at source ↗
Figure 3
Figure 3. Empirical proof that two feature vectors remain close in projection space. Given a graph G, we evaluate AH-UGC’s abil￾ity to adaptively coarsen it to multiple resolu￾tions, targeting a set of coarsening ratios R = {55, 50, 45, 40, 35, 30, 25, 20, 15, 10}. As described in Section 3, AH-UGC leverages LSH and consistent hash￾ing to group similar nodes into supernodes, enabling the construction of multiple coarsened gra… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Supernode impurity across AH-UGC (left), UGC (center) and VAN (right) on IMDB dataset. Different [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Node classification accuracy on the hDBLP dataset under decreasing coarsening ratios for three [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: Consistent Hashing (CH): Objects and bins are hashed to a unit circle; each object is [PITH_FULL_IMAGE:figures/full_fig_p015_6.png]
Figure 7
Figure 7. Figure 7: This figure illustrates this process, highlighting how AH-UGC preserves semantic meaning [PITH_FULL_IMAGE:figures/full_fig_p020_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

62 extracted references · 52 canonical work pages

  1. [1]

    A novel coarsened graph learning method for scalable single-cell data analysis,

    M. Kataria, E. Srivastava, K. Arjun, S. Kumar, I. Gupta,et al., “A novel coarsened graph learning method for scalable single-cell data analysis,”Computers in Biology and Medicine, vol. 188, p. 109873, 2025

    work page 2025

  2. [2]

    Protein interface prediction using graph convolu- tional networks,

    A. Fout, J. Byrd, B. Shariat, and A. Ben-Hur, “Protein interface prediction using graph convolu- tional networks,”Advances in neural information processing systems, vol. 30, 2017

    work page 2017

  3. [3]

    A comprehensive survey on graph neural networks,

    Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y . Philip, “A comprehensive survey on graph neural networks,”IEEE transactions on neural networks and learning systems, vol. 32, no. 1, pp. 4–24, 2020

    2020

  4. [4]

    Ugc: Universal graph coarsening,

    M. Kataria, S. Kumar,et al., “Ugc: Universal graph coarsening,”Advances in Neural Informa- tion Processing Systems, vol. 37, pp. 63057–63081, 2024

    work page 2024

  5. [5]

    Semi-supervised classification with graph convolutional networks,

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

    arXiv 2016

  6. [6]

    Microsoft academic graph: When experts are not enough,

    K. Wang, Z. Shen, C. Huang, C.-H. Wu, Y . Dong, and A. Kanakia, “Microsoft academic graph: When experts are not enough,”Quantitative Science Studies, vol. 1, no. 1, pp. 396–413, 2020

    work page 2020

  7. [7]

    Datasets and interfaces for benchmarking heterogeneous graph neural networks,

    Y . Liu, H. Zhang, C. Yang, A. Li, Y . Ji, L. Zhang, T. Li, J. Yang, T. Zhao, J. Yang,et al., “Datasets and interfaces for benchmarking heterogeneous graph neural networks,” inProceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 5346– 5350, 2023

    work page 2023

  8. [8]

    Heterogeneous network representation learning: A unified framework with survey and benchmark,

    C. Yang, Y . Xiao, Y . Zhang, Y . Sun, and J. Han, “Heterogeneous network representation learning: A unified framework with survey and benchmark,”IEEE Transactions on Knowledge and Data Engineering, vol. 34, no. 10, pp. 4854–4873, 2020

    work page 2020

Show all 62 references
  1. [9]

    Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks,

    Q. Lv, M. Ding, Q. Liu, Y . Chen, W. Feng, S. He, C. Zhou, J. Jiang, Y . Dong, and J. Tang, “Are we really making much progress? revisiting, benchmarking and refining heterogeneous graph neural networks,” inProceedings of the 27th ACM SIGKDD conference on knowledge discovery &...

    2021

  2. [10]

    Benchmarking graph neural networks,

    V . P. Dwivedi, C. K. Joshi, A. T. Luu, T. Laurent, Y . Bengio, and X. Bresson, “Benchmarking graph neural networks,”Journal of Machine Learning Research, vol. 24, no. 43, pp. 1–48, 2023

    2023

  3. [11]

    Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods,

    D. Lim, F. Hohne, X. Li, S. L. Huang, V . Gupta, O. Bhalerao, and S. N. Lim, “Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods,”Advances in neural information processing systems, vol. 34, pp. 20887–20902, 2021

    2021

  4. [12]

    Heterogeneous graph neural network,

    C. Zhang, D. Song, C. Huang, A. Swami, and N. V . Chawla, “Heterogeneous graph neural network,” inProceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 793–803, 2019

    2019

  5. [13]

    Goat: A global trans- former on large-scale graphs,

    K. Kong, J. Chen, J. Kirchenbauer, R. Ni, C. B. Bruss, and T. Goldstein, “Goat: A global trans- former on large-scale graphs,” inInternational Conference on Machine Learning, pp. 17375– 17390, PMLR, 2023

    2023

  6. [14]

    Graphsaint: Graph sampling based inductive learning method,

    H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V . Prasanna, “Graphsaint: Graph sampling based inductive learning method,”arXiv preprint arXiv:1907.04931, 2019

    1907 arXiv

  7. [15]

    The extreme classification repository: Multi-label datasets and code,

    K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y . Prabhu, and M. Varma, “The extreme classification repository: Multi-label datasets and code,” 2016. 10

    2016

  8. [16]

    Spectral clustering with graph neural networks for graph pooling,

    F. M. Bianchi, D. Grattarola, and C. Alippi, “Spectral clustering with graph neural networks for graph pooling,” inInternational conference on machine learning, pp. 874–883, PMLR, 2020

    2020

  9. [17]

    Weighted graph cuts without eigenvectors a multilevel approach,

    I. S. Dhillon, Y . Guan, and B. Kulis, “Weighted graph cuts without eigenvectors a multilevel approach,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 11, pp. 1944–1957, 2007

    1944

  10. [18]

    Graph condensation for graph neural networks,

    W. Jin, L. Zhao, S. Zhang, Y . Liu, J. Tang, and N. Shah, “Graph condensation for graph neural networks,”arXiv preprint arXiv:2110.07580, 2021

    2021 arXiv

  11. [19]

    A unified framework for optimization-based graph coarsening,

    M. Kumar, A. Sharma, and S. Kumar, “A unified framework for optimization-based graph coarsening,”Journal of Machine Learning Research, vol. 24, no. 118, pp. 1–50, 2023

    2023

  12. [20]

    Graph reduction with spectral and cut guarantees.,

    A. Loukas, “Graph reduction with spectral and cut guarantees.,”J. Mach. Learn. Res., vol. 20, no. 116, pp. 1–42, 2019

    2019

  13. [21]

    Locality-sensitive hashing scheme based on p-stable distributions,

    M. Datar, N. Immorlica, P. Indyk, and V . S. Mirrokni, “Locality-sensitive hashing scheme based on p-stable distributions,” inProceedings of the twentieth annual symposium on Computational geometry, pp. 253–262, 2004

    2004

  14. [22]

    Linear complexity framework for feature-aware graph coarsening via hashing,

    M. Kataria, A. Khandelwal, R. Das, S. Kumar, and J. Jayadeva, “Linear complexity framework for feature-aware graph coarsening via hashing,” inNeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023

    2023

  15. [23]

    Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web,

    D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, and D. Lewin, “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web,” inProceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 654–...

    1997

  16. [24]

    Revisiting consistent hashing with bounded loads,

    J. Chen, B. Coleman, and A. Shrivastava, “Revisiting consistent hashing with bounded loads,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 35, pp. 3976–3983, 2021

    2021

  17. [25]

    Heterogeneous graph condensation,

    J. Gao, J. Wu, and J. Ding, “Heterogeneous graph condensation,”IEEE Transactions on Knowledge and Data Engineering, vol. 36, no. 7, pp. 3126–3138, 2024

    2024

  18. [26]

    Relaxation-based coarsening and multiscale graph organiza- tion,

    D. Ron, I. Safro, and A. Brandt, “Relaxation-based coarsening and multiscale graph organiza- tion,” 2010

    2010

  19. [27]

    Algebraic distance on graphs,

    J. Chen and I. Safro, “Algebraic distance on graphs,”SIAM J. Scientific Computing, vol. 33, pp. 3468–3490, 12 2011

    2011

  20. [28]

    Lean algebraic multigrid (lamg): Fast graph laplacian linear solver,

    O. E. Livne and A. Brandt, “Lean algebraic multigrid (lamg): Fast graph laplacian linear solver,” 2011

    2011

  21. [29]

    Kron reduction of graphs with applications to electrical networks,

    F. Dorfler and F. Bullo, “Kron reduction of graphs with applications to electrical networks,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 60, no. 1, pp. 150–163, 2013

    2013

  22. [30]

    Graph condensation for graph neural networks,

    W. Jin, L. Zhao, S. Zhang, Y . Liu, J. Tang, and N. Shah, “Graph condensation for graph neural networks,” 2021

    2021

  23. [31]

    Structure-free graph condensation: From large-scale graphs to condensed graph-free data,

    X. Zheng, M. Zhang, C. Chen, Q. V . H. Nguyen, X. Zhu, and S. Pan, “Structure-free graph condensation: From large-scale graphs to condensed graph-free data,”Advances in Neural Information Processing Systems, vol. 36, 2024

    2024

  24. [32]

    Approximate nearest neighbors: Towards removing the curse of dimensionality,

    P. Indyk and R. Motwani, “Approximate nearest neighbors: Towards removing the curse of dimensionality,” inProceedings of the Thirtieth Annual ACM Symposium on Theory of Com- puting, STOC ’98, (New York, NY , USA), p. 604–613, Association for Computing Machinery, 1998

    1998

  25. [33]

    Revisiting semi-supervised learning with graph embeddings,

    Z. Yang, W. W. Cohen, and R. Salakhutdinov, “Revisiting semi-supervised learning with graph embeddings,” inProceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, JMLR Workshop and Conference Proceedings, 2016. 11

    2016

  26. [34]

    Pitfalls of graph neural network evaluation,

    O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann, “Pitfalls of graph neural network evaluation,”ArXiv preprint, 2018

    2018

  27. [35]

    Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding,

    X. Fu, J. Zhang, Z. Meng, and I. King, “Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding,” inProceedings of The Web Conference 2020, pp. 2331–2341, 2020

    2020

  28. [36]

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

    J. Zhu, Y . Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, “Beyond homophily in graph neural networks: Current limitations and effective designs,” inAdvances in Neural Information Processing Systems(H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, eds.), vol....

    2020

  29. [37]

    Geom-gcn: Geometric graph convolutional networks,

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

    2002 arXiv

  30. [38]

    Graph neural networks with heterophily,

    J. Zhu, R. A. Rossi, A. Rao, T. Mai, N. Lipka, N. K. Ahmed, and D. Koutra, “Graph neural networks with heterophily,” inProceedings of the AAAI conference on artificial intelligence, vol. 35, pp. 11168–11176, 2021

    2021

  31. [39]

    Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily,

    L. Du, X. Shi, Q. Fu, X. Ma, H. Liu, S. Han, and D. Zhang, “Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily,” inProceedings of the ACM Web Conference 2022, pp. 1550–1558, 2022

    2022

  32. [40]

    Inductive representation learning on large graphs,

    W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” 2017

    2017

  33. [41]

    Graph attention networks,

    P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y . Bengio, “Graph attention networks,” in6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings, 2018

    2018

  34. [42]

    How powerful are graph neural networks?,

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

    2018 arXiv

  35. [43]

    Scaling up graph neural networks via graph coarsening,

    Z. Huang, S. Zhang, C. Xi, T. Liu, and M. Zhou, “Scaling up graph neural networks via graph coarsening,” 2021

    2021

  36. [44]

    Adaptive universal generalized pagerank graph neural network,

    E. Chien, J. Peng, P. Li, and O. Milenkovic, “Adaptive universal generalized pagerank graph neural network,”arXiv preprint arXiv:2006.07988, 2020

    2006 arXiv

  37. [45]

    Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing,

    S. Abu-El-Haija, B. Perozzi, A. Kapoor, N. Alipourfard, K. Lerman, H. Harutyunyan, G. Ver Steeg, and A. Galstyan, “Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing,” ininternational conference on machine learning, pp. 21–29, PMLR, 2019

    2019

  38. [46]

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

    J. Zhu, Y . Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, “Beyond homophily in graph neural networks: Current limitations and effective designs,”Advances in neural information processing systems, vol. 33, pp. 7793–7804, 2020

    2020

  39. [47]

    Simple and deep graph convolutional networks,

    M. Chen, Z. Wei, Z. Huang, B. Ding, and Y . Li, “Simple and deep graph convolutional networks,” inInternational conference on machine learning, pp. 1725–1735, PMLR, 2020

    2020

  40. [48]

    Representation learning on graphs with jumping knowledge networks,

    K. Xu, C. Li, Y . Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka, “Representation learning on graphs with jumping knowledge networks,” inInternational conference on machine learning, pp. 5453–5462, PMLR, 2018

    2018

  41. [49]

    Simplifying graph convolutional networks,

    F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger, “Simplifying graph convolutional networks,” inInternational conference on machine learning, pp. 6861–6871, Pmlr, 2019

    2019

  42. [50]

    Kernelized locality-sensitive hashing for scalable image search,

    B. Kulis and K. Grauman, “Kernelized locality-sensitive hashing for scalable image search,” in 2009 IEEE 12th international conference on computer vision, (Kyoto, Japan), pp. 2130–2137, IEEE, IEEE, 2009

    2009

  43. [51]

    Efficient large-scale sequence comparison by locality-sensitive hashing,

    J. Buhler, “Efficient large-scale sequence comparison by locality-sensitive hashing,”Bioinfor- matics, vol. 17, no. 5, pp. 419–428, 2001. 12

    2001

  44. [52]

    Scalable near identical image and shot detection,

    O. Chum, J. Philbin, M. Isard, and A. Zisserman, “Scalable near identical image and shot detection,” inProceedings of the 6th ACM international conference on Image and video retrieval, pp. 549–556, 2007

    2007

  45. [53]

    H. A. David and H. N. Nagaraja,Order statistics. John Wiley & Sons, 2004

    2004

  46. [54]

    Hyperdefender: A robust framework for hyperbolic gnns,

    N. Malik, R. Gupta, and S. Kumar, “Hyperdefender: A robust framework for hyperbolic gnns,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 39, pp. 19396–19404, Apr. 2025

    2025

  47. [55]

    Encoding social information with graph convolutional networks forPolitical perspective detection in news media,

    C. Li and D. Goldwasser, “Encoding social information with graph convolutional networks forPolitical perspective detection in news media,” inProceedings of the 57th Annual Meeting of the Association for Computational Linguistics, (Florence, Italy), pp. 2594–2604, Association f...

    2019

  48. [56]

    Reinforced genetic algorithm learning for optimizing computation graphs,

    A. Paliwal, F. Gimeno, V . Nair, Y . Li, M. Lubin, P. Kohli, and O. Vinyals, “Reinforced genetic algorithm learning for optimizing computation graphs,” 2019

    2019

  49. [57]

    Learning mesh-based simulation with graph networks,

    T. Pfaff, M. Fortunato, A. Sanchez-Gonzalez, and P. W. Battaglia, “Learning mesh-based simulation with graph networks,”arXiv preprint arXiv:2010.03409, vol. 32, p. 18, 2020

    2010 arXiv

  50. [58]

    Graph convolu- tional neural networks for web-scale recommender systems,

    R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec, “Graph convolu- tional neural networks for web-scale recommender systems,” inProceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’18, (New York, NY , US...

    2018

  51. [59]

    A unifying framework for spectrum-preserving graph sparsification and coarsening,

    G. Bravo Hermsdorff and L. Gunderson, “A unifying framework for spectrum-preserving graph sparsification and coarsening,”Advances in Neural Information Processing Systems, vol. 32, p. 12, 2019

    2019

  52. [60]

    Graph summarization methods and applications: A survey,

    Y . Liu, T. Safavi, A. Dighe, and D. Koutra, “Graph summarization methods and applications: A survey,”ACM computing surveys (CSUR), vol. 51, no. 3, pp. 1–34, 2018. 13 A Datasets We experiment on 24 widely-used benchmark datasets grouped into four categories:(a) Homophilic: Cor...

    2018

  53. [61]

    Relative Eigen Error (REE):REE used in [ 4, 19, 20] gives the means to quantify the measure of the eigen properties of the original graphGthat are preserved in coarsened graphG c. Definition F.1REE is defined as follows: REE(L,L c,k) = 1 k kX i=1 |eλi−λi| λi (1) whereλi and eλ...

  54. [62]

    Hyperbolic error (HE):HE [ 59] indicates the structural similarity betweenG andGc with the help of a lifted matrix along with the feature matrixXof the original graph. Definition F.2HE is defined as follows: HE=arccosh( ||(L−L lift)X|| 2 F||X|| 2 F 2trace(XTLX)trace(XTLliftX) ...

Pith tools

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