Pith. sign in

REVIEW 4 major objections 6 minor 72 references

GraphFLEx: Structure Learning Framework for Large Expanding Graphs

T0 review · 4 major / 6 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 GraphFLEx claims that structure learning on large expanding graphs can be made incremental and scalable by narrowing candidate edges through clustering and hash-based coarsening, with a probability guarantee that true neighborhoods are…

desk verdict A scalable and broadly tested structure-learning pipeline, but its advertised neighborhood-preservation theorem is unsupported and should be fixed or dropped before acceptance. read the letter →

arxiv 2505.12323 v1 pith:5YI3MMP6 submitted 2025-05-18 cs.LG

Mohit Kataria , Nikita Malik , Sandeep Kumar , Jayadeva This is my paper · ORCID
classification cs.LG
keywords graphstructurelearningexpandinggraphscoarseninglocality-sensitivehashingcommunitydetectionneuralnetworksscalabilityincremental
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 GraphFLEx, a framework for learning the structure of large or steadily growing graphs without re-learning the entire graph when new nodes arrive. It claims that by first clustering incoming nodes into communities, coarsening each relevant community into supernodes with locality-sensitive hashing, and then learning edges only between supernodes and new nodes, the candidate edge space shrinks enough for near-linear scaling. The formal claim is Theorem 1: the recovered candidate set contains the true $k$-nearest neighborhood of every incoming node with probability equal to a product of distance-dependent factors. If this holds, standard structure learners such as $k$-nearest neighbors, covariance estimation, and graphical lasso become usable on graphs of millions of nodes where they otherwise exhaust memory or time. This matters because learned graph structure is what makes graph neural networks interpretable and denoised, especially when the true topology is missing or noisy.

What carries the argument

The load-bearing object is the three-module pipeline together with the probability bound in Theorem 1. Clustering (DMoN) assigns incoming nodes to communities; coarsening (UGC-style locality-sensitive hashing with random projection and bin width $r$) maps each community's nodes to supernodes; and a structure learner $M_{\mathrm{gl}}$, chosen from methods such as approximate kNN, kNN, covariance estimation, graphical lasso, or log/$\ell^2$/large models, learns edges between supernodes and new nodes. The partition matrix from coarsening then projects learned edges back to the original graph. Theorem 1's identity, $\omega = \bigcup_{v \in E_i} \{\pi^{-1}(s) : A^c_\tau(v,s) \neq 0\}$, is what carries the formal guarantee: with probability $\prod_{c \in \phi} p(c)$, the true neighborhood $N_k(E_i)$ is contained in $\omega$, where the bound on $p(c)$ depends on the bin width $r$ and the pairwise distance $c$.

What would settle it

Run GraphFLEx on a dataset with known true k-NN structure, fix the bin width $r$, and count incoming nodes for which some true neighbor is missing from $\omega$. If the observed miss rate exceeds $1 - \prod_{c \in \phi} p(c)$ over the realized distances, Theorem 1's bound is violated; separately, inspect coarsened graphs for pairs that collide in an LSH bin yet receive no edge from $M_{\mathrm{gl}}$, which would break the proof's central premise even when $p(c)$ is computed correctly.

Watch

Extended reading notes

Core claim

GraphFLEx's central claim is that unsupervised graph structure learning on expanding graphs can be decomposed into three aligned stages: community detection by a modularity-based GNN clusterer trained once on a static core, hash-based coarsening of large communities into supernodes, and structure learning on the coarsened graph followed by projection back onto the original nodes. The paper asserts that this multistage procedure preserves the neighborhoods that matter: Theorem 1 states that the candidate node set $\omega$ recovered by the pipeline contains the true neighborhood $N_k(E_i)$ of incoming nodes with probability equal to the product over pairwise distances of $p(c)$, with $p(c) \le 1 - \frac{2}{\sqrt{2\pi}}\frac{c}{r}\left[1 - e^{-r^2/(2c^2)}\right]$. The authors further claim that this construction makes structure learning scalable (near-linear in the best case), supports incremental updates as nodes arrive over timestamps, and produces node-classification accuracies close to, and sometimes better than, training on the original graph across 26 datasets and four GNN architectures.

Load-bearing premise

The guarantee collapses if a true neighbor and an incoming node land in the same hash bin but the structure learner does not connect the incoming node to that neighbor's supernode; the paper assumes this connection happens without proving it.

Editorial extensions

If this is right

  • Structure learners that are normally quadratic or cubic, such as graphical lasso, can be run on graphs of hundreds of thousands of nodes by restricting them to coarsened communities; the paper reports that baseline methods that go out of memory or time become feasible inside GraphFLEx.
  • New nodes can be inserted at each timestamp by re-running only clustering inference, coarsening, and local structure learning, so the full graph does not need to be re-learned from scratch when it grows.
  • The probability bound provides a tunable trade-off: bin width $r$ and the connectivity level of $M_{\mathrm{gl}}$ control how many candidate nodes are kept versus how likely a true neighbor is missed.
  • Graph neural networks trained on GraphFLEx structures achieve accuracies close to those obtained with the original graph structure, and in several reported cases exceed it, suggesting the learned structure also denoises edges.
  • Because the framework composes any clustering, coarsening, and learning module, it offers 48 configurations that can be matched to dataset size and computational budget.

Reading between the lines

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

  • The theorem's probability product is taken over a distance set $\phi$ that is defined through $\omega$, the same random set the theorem is bounding, so as written the statement is circular; a fully rigorous version would define $\phi$ independently of the recovery outcome.
  • The proof establishes only that two nearby points collide in an LSH bin with probability $p(c)$; it never shows that such a collision forces $M_{\mathrm{gl}}$ to place an edge to the corresponding supernode, which is the actual event that puts a true neighbor inside $\omega$.
  • If that missing link were supplied, the same decomposition would likely extend to supervised structure learning and heterophilic graphs, which the authors name as future work, because those settings only change $M_{\mathrm{gl}}$ and the clustering assumption, not the coarsening geometry.
  • A concrete testable extension is to measure the empirical neighborhood-preservation rate on a dataset with known true k-NN and compare it with the product of $p(c)$ values; any significant excess would localize whether the gap is in the hash collision analysis or in $M_{\mathrm{gl}}$'s edge decisions.
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

4 major / 6 minor

Summary. GraphFLEx proposes an incremental graph structure learning framework for large, expanding graphs. The pipeline consists of three modules: a clustering module (Mclust) trained once on a static subgraph to assign incoming nodes to communities; an LSH-based coarsening module (Mcoar) that reduces each community to supernodes; and a structure learning module (Mgl) that learns edges between incoming nodes and supernodes on the coarsened graph and then projects the recovered edges back to the original node set. The paper claims a theoretical guarantee (Theorem 1) that the true k-neighborhood of incoming nodes is contained in the recovered candidate set ω with probability equal to a product of LSH collision probabilities, and reports extensive experiments across 26 datasets showing reduced runtime, scalability to 2.4M nodes, and classification accuracy close to that of the original graph structure.

Significance. If the theoretical guarantee were valid and the empirical comparisons complete, the framework would be a practically valuable contribution: the modular design (48 configurations) and the reported near-linear scaling on graphs where vanilla methods OOM/OOT would address a real bottleneck in unsupervised graph structure learning. The paper's reproducible experimental setup, including parameter tables and dataset details, is a strength, as are the large-scale results in Table 4, where GraphFLEx runs on datasets that vanilla methods cannot handle. However, the advertised theoretical guarantee on edge-recovery fidelity is the key scientific claim that distinguishes this work from a purely empirical engineering paper, and that claim is not established by the presented proof. The significance of the paper therefore falls back to its empirical scalability contribution, which is useful but is not, on its own, sufficient for the level of the claims made in the abstract and introduction.

major comments (4)
  1. [§3.4 and Appendix B] Theorem 1 is not proved. Appendix B bounds the LSH collision probability p(c), but it never connects the collision event to the formation of an edge by Mgl on the coarsened graph. The set ω in the theorem is defined through nonzero entries A^c_τ(v,s) of the coarsened adjacency produced by Mgl; for the conclusion N_k(E_i) ⊆ ω to follow, one would need that whenever LSH preserves the distance d(v,u), the learner Mgl places an edge between v and the supernode containing u. No such property is stated or proved for any of the six supported choices of Mgl (kNN, ANN, GLasso, log-model, l2-model, large-model). The assertion is false as a general statement: if Mgl returns the empty graph, then ω = ∅ and the claimed inclusion fails deterministically, while the p(c) bound in Appendix B is unaffected. The theorem therefore does not provide the advertised "edge recovery fidelity" guarantee.
  2. [Appendix B, definition of φ] The product probability in Theorem 1 is taken over φ, defined as the set of pairwise distances between v ∈ E_i and nodes u ∈ ω_{V_i^τ}. But ω_{V_i^τ} is precisely the random set whose inclusion of N_k(E_i) is the conclusion of the theorem. The argument therefore multiplies probabilities over a set that depends on the random object being bounded; the relevant distances for the conclusion would be d(v,u) for u ∈ N_k(E_i), not for u ∈ ω. This circularity invalidates the probability statement, independent of the proof gap described above.
  3. [Introduction and §4.2] The abstract and introduction claim "state-of-the-art performance," but the accuracy comparisons in Tables 3–5 are only against the vanilla versions of the same structure learners (ANN, kNN, log-model, etc.). No comparison is made against recent unsupervised GSL methods, and SUBLIME—the one modern GSL baseline that appears in the paper—is present only in the runtime table (Table 2), not in any accuracy table. The claim of state-of-the-art performance is therefore not supported by the evidence presented, and the empirical contribution is better characterized as demonstrating that the modular pipeline preserves accuracy relative to the original structure and to vanilla component learners.
  4. [§3.2, Lemma 1] Lemma 1 restates consistency results from [50] for community detection under a DC-SBM, but it does not verify that the conditions of those results hold in the actual use of Mclust within GraphFLEx. In particular, Mclust is trained once on the static graph G0 and then applied to incoming nodes at each timestamp; the lemma as stated concerns a fixed graph of size N with a specified sparsity regime λ_N, and the paper does not show that the per-community graphs at each timestamp satisfy the required asymptotics. This is not a fatal flaw if the lemma is intended merely as motivation, but as stated it overclaims the framework's theoretical basis for the clustering stage.
minor comments (6)
  1. [§3.4 and Appendix B] Theorem 1 in §3.4 and Theorem 2 in Appendix B are identical in statement but numbered differently; the duplication should be resolved.
  2. [§3.3, Eq. (1)] Equation (1) defines H_i as the maxOccurance of a scalar expression; this notation is not defined anywhere and should be replaced with the standard LSH bucket index notation.
  3. [Table 3 caption] The caption states that "GraphFLEx's structure beats all of the vanilla structures for every dataset," but many vanilla entries are OOM/OOT, so the comparison set is incomplete; the claim should be qualified accordingly.
  4. [§5, Conclusion] The conclusion states that GraphFLEx achieves "up to 3× speedup," but Table 2 shows that GraphFLEx can be slower than vanilla on small datasets (e.g., Cora KNN: 36.1s vs 8.4s); the speedup claim should be restricted to large-scale settings, where the scaling arguments apply.
  5. [Table 7] The entry for the "large-model" in Table 7 cites [20,21] (the smooth-signal learning papers), but the specific formulation with the constraint 1{‖W‖_{1,1}=n} does not match the formulations in those references; an explicit citation for this model would help.
  6. [Table 6] The column headers NMI, C, and Q in Table 6 are defined in the text after the table, but the abbreviations are not explained in the caption; this slows the reader.

Circularity Check

1 steps flagged · score 6.0 of 10

Theorem 1's neighborhood-preservation guarantee is self-referential: its probability is defined over omega, the very set whose inclusion of N_k(E_i) is to be proven; empirical comparisons are not circular.

  1. self definitional [Theorem 1 (Sec. 3.4) and proof in Appendix B; see also Remark 4]
    "Then, with probability Π_{c∈ϕ}p(c), it holds that N_k(E_i)⊆ω^Vi_τ where ... ϕ is a set containing all pairwise distance values (c =∥v−u∥) between every node v∈E_i and the nodes u∈ω^Vi_τ. ... The probability that all nodes in N_k(E_i) are preserved within ω^Vi_τ, requires that all distances c∈ϕ are also preserved."

    The probability statement is built from φ, which is defined using ω^Vi_τ, the random candidate set whose containment of N_k(E_i) is the theorem's conclusion. Appendix B's proof step 'requires that all distances c∈φ are also preserved' conflates ω with the true neighborhood: distances in φ run from v to nodes already selected by Mgl, not to the unselected u∈N_k(E_i) that need recovering. If Mgl returns the empty graph, ω=∅ and N_k(E_i)⊆ω fails deterministically, while the p(c) product is unchanged, showing that the bound is independent of the mechanism that actually determines ω. Thus the advertised 'edge recovery fidelity' guarantee does not derive N_k(E_i)⊆ω from LSH collision; it defines the success event in terms of the conclusion set itself.

full rationale

The empirical core of GraphFLEx—runtime and node-classification comparisons against vanilla versions of the same learners on 26 datasets—is self-contained: no fitted parameter is renamed as a prediction, and the baselines are the original algorithms run without clustering/coarsening, so the scalability and accuracy claims do not reduce to GraphFLEx's own outputs. The self-citations to UGC [32] and to the authors' earlier coarsening work are building-block citations; the LSH collision bound itself is standard p-stable LSH [62], so authorship alone is not circular. The significant circularity lies in the paper's central theoretical claim, Theorem 1/Appendix B: the claimed probability is taken over φ, the set of distances from incoming nodes to nodes in ω, where ω is the set whose inclusion of N_k(E_i) is the statement being proved. The proof therefore computes the probability of an event that already depends on the conclusion and never bounds the event that each true neighbor's distance is preserved and that Mgl actually connects v to that neighbor's supernode. This makes the 'neighborhood preservation' guarantee self-referential rather than derived; however, because the empirical benchmarking stands independently of this theorem, the overall circularity is partial (score 6).

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

The theoretical apparatus rests on the DC-SBM assumption and on imported consistency results; the novel part of the proof depends on LSH collision behavior from UGC and on an unstated bridge to the learned edges. There are no invented physical entities; supernodes are a standard coarsening abstraction.

free parameters (4)
  • LSH bin width r
    Controls coarsened graph size and the probability bound in Theorem 1; no value is reported for any experiment.
  • Neighborhood size k
    Defines N_k(E_i) in Definition 1 and the k in kNN as Mgl; not reported per dataset.
  • Cluster count K for Mclust
    Output dimension of DMoN or spectral clustering in Section 3.2; not reported.
  • Static fraction r_static and timestamps T = r_static = 0.5 or 0.7, T = 25
    Experimental protocol choices in Section 3.1 that determine how much incremental gain GraphFLEx shows over vanilla single-shot learners.
assumptions (4)
  • domain assumption Generated graphs follow a Degree-Corrected Stochastic Block Model with intra-community edges more likely than inter-community edges (Assumption 1, Section 3.2).
    Load-bearing for the clustering module and for reducing structure learning to within-community learning; the authors note in the conclusion that heterophilic graphs may need adaptation.
  • standard math DMoN clustering is strongly or weakly consistent under DC-SBM as stated in Lemma 1, importing Theorem 3.1 of Zhao et al. [50].
    The conditions lambda_N/log N to infinity (strong) or lambda_N to infinity (weak) are assumed to hold for the trained Mclust and are used to justify that community membership is recoverable.
  • ad hoc to paper If LSH preserves the distance between an incoming node v and a true neighbor u, then Mgl on the coarsened graph connects v to the supernode containing u.
    This bridge is required for Theorem 1 but is nowhere stated or proved; Appendix B jumps from an LSH collision probability to N_k subset of omega.
  • ad hoc to paper Distinct pair-collision events in the LSH coarsening are independent, allowing the probability product over p(c) in Appendix B.
    The proof multiplies p(c) over distances without justification; collisions share the same random projection and are not generally independent.

how reviews work

0 comments
Cite this review

Pith. "Pith review of GraphFLEx: Structure Learning Framework for Large Expanding Graphs." pith.science (2026). https://pith.science/paper/5YI3MMP6

@misc{pith2026250512323,
  author       = {Pith},
  title        = {Pith review of: GraphFLEx: Structure Learning Framework for Large Expanding Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5YI3MMP6}},
  note         = {Machine review of arXiv:2505.12323}
}
read the original abstract

Graph structure learning is a core problem in graph-based machine learning, essential for uncovering latent relationships and ensuring model interpretability. However, most existing approaches are ill-suited for large-scale and dynamically evolving graphs, as they often require complete re-learning of the structure upon the arrival of new nodes and incur substantial computational and memory costs. In this work, we propose GraphFLEx: a unified and scalable framework for Graph Structure Learning in Large and Expanding Graphs. GraphFLEx mitigates the scalability bottlenecks by restricting edge formation to structurally relevant subsets of nodes identified through a combination of clustering and coarsening techniques. This dramatically reduces the search space and enables efficient, incremental graph updates. The framework supports 48 flexible configurations by integrating diverse choices of learning paradigms, coarsening strategies, and clustering methods, making it adaptable to a wide range of graph settings and learning objectives. Extensive experiments across 26 diverse datasets and Graph Neural Network architectures demonstrate that GraphFLEx achieves state-of-the-art performance with significantly improved scalability.

Figures

Figures reproduced from arXiv: 2505.12323 by the authors.

Figure 2
Figure 2. This figure illustrates the general pipeline of GraphFLEx, designed to efficiently handle both a) large [PITH_FULL_IMAGE:figures/full_fig_p002_2.png] view at source ↗
Figure 1
Figure 1. High computational time required to learn graph structures using existing meth￾ods, whereas GraphFLEx effectively controls computational growth, achieving near-linear scalability. Notably, Vanilla KNN failed to construct graph structures for more than 10K nodes due to memory limitations. To address these challenges, we introduce GraphFLEx, a unified and scalable framework for Graph Structure Learn￾ing in Large and E… view at source ↗
Figure 3
Figure 3. The versatility of GraphFlex in supporting [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Figures (a), (b), and (c) illustrate the growing structure learned using GraphFLEx for [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Effectiveness of our framework in learning [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: This figure illustrates different types of synthetic graphs generated using i)PyGSP, ii) Watts–Strogatz’s [PITH_FULL_IMAGE:figures/full_fig_p018_6.png]
Figure 7
Figure 7. Figure 7: GNN training pipeline. J Visualization of Growing graphs This section helps us visualize the phases of our growing graphs. We have generated a synthetic graph of 60 nodes using PyGSP-Sensor and HE methods mentioned in Appendix F. We then added 40 new nodes denoted usin…
Figure 8
Figure 8. Figure 8: GraphSage accuracies when structure is learned or given with 3 different scenarios(Vanilla, GraphFlex, [PITH_FULL_IMAGE:figures/full_fig_p020_8.png]
Figure 9
Figure 9. Figure 9: This figure illustrates the growing structure learned using GraphFlex for dynamic nodes. New nodes [PITH_FULL_IMAGE:figures/full_fig_p020_9.png]
Figure 10
Figure 10. Figure 10: This figure illustrates the growing structure learned using GraphFlex for dynamic nodes. New nodes [PITH_FULL_IMAGE:figures/full_fig_p020_10.png]
Figure 11
Figure 11. Figure 11: Original Karate Graph (a) Xin (b) MNIST (c) Baron Human (d) Muraro (e) Baron Mouse (f) Segerstolpe [PITH_FULL_IMAGE:figures/full_fig_p022_11.png]
Figure 12
Figure 12. Figure 12: PHATE visualization of clusters learnt using GraphFlex clustering module for scRNA-seq datasets. [PITH_FULL_IMAGE:figures/full_fig_p022_12.png]
Figure 13
Figure 13. Figure 13: This figure compares the structures learned on Zachary’s karate dataset when existing methods are [PITH_FULL_IMAGE:figures/full_fig_p023_13.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

72 extracted references · 62 canonical work pages

  1. [50]

    Consistency of community detection in networks under degree-corrected stochastic block models,

    Y . Zhao, E. Levina, and J. Zhu, “Consistency of community detection in networks under degree-corrected stochastic block models,” 2012. (Cited at pp. 4, 5, and 15.) 12

    work page 2012

  2. [1]

    Graph neural networks: A review of methods and applications,

    J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun, “Graph neural networks: A review of methods and applications,” AI open, vol. 1, pp. 57–81, 2020. (Cited at p. 1.)

    work page 2020

  3. [2]

    Protein interface prediction using graph convo- lutional networks,

    A. Fout, J. Byrd, B. Shariat, and A. Ben-Hur, “Protein interface prediction using graph convo- lutional networks,” Advances in neural information processing systems, vol. 30, 2017. (Not cited.)

    work page 2017

  4. [3]

    Graph convolutional networks with markov random field reasoning for social spammer detection,

    Y . Wu, D. Lian, Y . Xu, L. Wu, and E. Chen, “Graph convolutional networks with markov random field reasoning for social spammer detection,” in Proceedings of the AAAI conference on artificial intelligence, vol. 34, pp. 1054–1061, 2020. (Not cited.)

    work page 2020

  5. [4]

    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

    work page

  6. [5]

    Scene graph generation with external knowledge and image reconstruction,

    J. Gu, H. Zhao, Z. Lin, S. Li, J. Cai, and M. Ling, “Scene graph generation with external knowledge and image reconstruction,” inProceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 1969–1978, 2019. (Cited at p. 1.)

    work page 1969

  7. [6]

    A survey on graph structure learning: Progress and opportunities,

    Y . Zhu, W. Xu, J. Zhang, Y . Du, J. Zhang, Q. Liu, C. Yang, and S. Wu, “A survey on graph structure learning: Progress and opportunities,” arXiv preprint arXiv:2103.03036, 2021. (Cited at p. 1.)

    arXiv 2021

  8. [7]

    Comparing statistical methods for constructing large scale gene networks,

    J. D. Allen, Y . Xie, M. Chen, L. Girard, and G. Xiao, “Comparing statistical methods for constructing large scale gene networks,” PloS one, vol. 7, no. 1, p. e29348, 2012. (Cited at p. 1.)

    work page 2012

Show all 72 references
  1. [8]

    Towards unsupervised deep graph structure learning,

    Y . Liu, Y . Zheng, D. Zhang, H. Chen, H. Peng, and S. Pan, “Towards unsupervised deep graph structure learning,” in Proceedings of the ACM Web Conference 2022, pp. 1392–1403, 2022. (Cited at pp. 1, 2, and 3.)

    2022

  2. [9]

    Graph neural networks: Graph structure learning,

    Y . Chen and L. Wu, “Graph neural networks: Graph structure learning,”Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 297–321, 2022. (Cited at p. 1.)

    2022

  3. [10]

    Nodeformer: A scalable graph structure learning transformer for node classification,

    Q. Wu, W. Zhao, Z. Li, D. P. Wipf, and J. Yan, “Nodeformer: A scalable graph structure learning transformer for node classification,” Advances in Neural Information Processing Systems, vol. 35, pp. 27387–27401, 2022. (Cited at p. 1.)

    2022

  4. [11]

    Graph structure learning for robust graph neural networks,

    W. Jin, Y . Ma, X. Liu, X. Tang, S. Wang, and J. Tang, “Graph structure learning for robust graph neural networks,” in Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 66–74, 2020. (Cited at p. 1.)

    2020

  5. [12]

    Variational inference for training graph neural networks in low-data regime through joint structure-label estimation,

    D. Lao, X. Yang, Q. Wu, and J. Yan, “Variational inference for training graph neural networks in low-data regime through joint structure-label estimation,” inProceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pp. 824–834, 2022. (Cited at p. 1.)

    2022

  6. [13]

    Slaps: Self-supervision improves structure learning for graph neural networks,

    B. Fatemi, L. El Asri, and S. M. Kazemi, “Slaps: Self-supervision improves structure learning for graph neural networks,” Advances in Neural Information Processing Systems , vol. 34, pp. 22667–22681, 2021. (Cited at p. 1.)

    2021

  7. [14]

    Efficient k-nearest neighbor graph construction for generic similarity measures,

    W. Dong, C. Moses, and K. Li, “Efficient k-nearest neighbor graph construction for generic similarity measures,” in Proceedings of the 20th international conference on World wide web, pp. 577–586, 2011. (Cited at p. 1.) 10

    2011

  8. [15]

    Scalable nearest neighbor algorithms for high dimensional data,

    M. Muja and D. G. Lowe, “Scalable nearest neighbor algorithms for high dimensional data,” IEEE transactions on pattern analysis and machine intelligence, vol. 36, no. 11, pp. 2227–2240,

  9. [16]

    Some methods for classification and analysis of multivariate observations,

    J. MacQueen et al., “Some methods for classification and analysis of multivariate observations,” in Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, vol. 1, pp. 281–297, Oakland, CA, USA, 1967. (Cited at pp. 1 and 3.)

    1967

  10. [17]

    Label propagation through linear neighborhoods,

    F. Wang and C. Zhang, “Label propagation through linear neighborhoods,” inProceedings of the 23rd international conference on Machine learning, pp. 985–992, 2006. (Cited at pp. 1 and 3.)

    2006

  11. [18]

    Sparse inverse covariance matrix esti- mation using quadratic approximation,

    C.-J. Hsieh, I. Dhillon, P. Ravikumar, and M. Sustik, “Sparse inverse covariance matrix esti- mation using quadratic approximation,” Advances in neural information processing systems, vol. 24, 2011. (Cited at p. 1.)

    2011

  12. [19]

    Sparse inverse covariance estimation with the graphical lasso,

    J. Friedman, T. Hastie, and R. Tibshirani, “Sparse inverse covariance estimation with the graphical lasso,” Biostatistics, vol. 9, no. 3, pp. 432–441, 2008. (Cited at pp. 1 and 3.)

    2008

  13. [20]

    Learning laplacian matrix in smooth graph signal representations,

    X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, “Learning laplacian matrix in smooth graph signal representations,”IEEE Transactions on Signal Processing, vol. 64, no. 23, pp. 6160– 6173, 2016. (Cited at pp. 2 and 3.)

    2016

  14. [21]

    How to learn a graph from smooth signals,

    V . Kalofolias, “How to learn a graph from smooth signals,” in Artificial intelligence and statistics, pp. 920–929, PMLR, 2016. (Cited at pp. 2 and 3.)

    2016

  15. [22]

    A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation,

    M. Hashemi, S. Gong, J. Ni, W. Fan, B. A. Prakash, and W. Jin, “A comprehensive survey on graph reduction: Sparsification, coarsening, and condensation,” arXiv preprint arXiv:2402.03358, 2024. (Cited at p. 3.)

    2024 arXiv

  16. [23]

    Community detection in graphs,

    S. Fortunato, “Community detection in graphs,” Physics reports, vol. 486, no. 3-5, pp. 75–174,

  17. [24]

    Graph clustering with graph neural networks,

    A. Tsitsulin, J. Palowitch, B. Perozzi, and E. Müller, “Graph clustering with graph neural networks,” Journal of Machine Learning Research, vol. 24, no. 127, pp. 1–21, 2023. (Cited at pp. 3, 4, and 9.)

    2023

  18. [25]

    Spectral learning,

    S. D. Kamvar, D. Klein, and C. D. Manning, “Spectral learning,” in IJCAI, vol. 3, pp. 561–566,

  19. [26]

    Constrained k-means clustering with background knowledge,

    K. Wagstaff, C. Cardie, S. Rogers, S. Schrödl, et al., “Constrained k-means clustering with background knowledge,” in Icml, vol. 1, pp. 577–584, 2001. (Cited at p. 3.)

    2001

  20. [27]

    Spectral networks and deep locally connected networks on graphs. arxiv,

    J. Bruna, W. Zaremba, A. Szlam, and Y . LeCun, “Spectral networks and deep locally connected networks on graphs. arxiv,”arXiv preprint arXiv:1312.6203, 2014. (Cited at p. 3.)

    2014 arXiv

  21. [28]

    Convolutional neural networks on graphs with fast localized spectral filtering,

    M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,”Advances in neural information processing systems, vol. 29,

  22. [29]

    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. (Cited at p. 3.)

    2019

  23. [30]

    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,” in NeurIPS 2023 Workshop: New Frontiers in Graph Learning, 2023. (Cited at pp. 16 and 17.)

    2023

  24. [31]

    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. (Not cited.)

    2023

  25. [32]

    UGC: Universal graph coarsening,

    M. Kataria, S. Kumar, and J. Jayadeva, “UGC: Universal graph coarsening,” in The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024. (Cited at pp. 3, 5, and 15.) 11

    2024

  26. [33]

    Semi-supervised learning using gaussian fields and harmonic functions,

    X. Zhu, Z. Ghahramani, and J. D. Lafferty, “Semi-supervised learning using gaussian fields and harmonic functions,” in Proceedings of the 20th International conference on Machine learning (ICML-03), pp. 912–919, 2003. (Cited at p. 3.)

    2003

  27. [34]

    Koller and N

    D. Koller and N. Friedman, Probabilistic graphical models: principles and techniques. MIT press, 2009. (Cited at p. 3.)

    2009

  28. [35]

    Model selection through sparse maximum likelihood estimation for multivariate gaussian or binary data,

    O. Banerjee, L. El Ghaoui, and A. d’Aspremont, “Model selection through sparse maximum likelihood estimation for multivariate gaussian or binary data,”The Journal of Machine Learning Research, vol. 9, pp. 485–516, 2008. (Cited at p. 3.)

    2008

  29. [36]

    Covariance selection,

    A. P. Dempster, “Covariance selection,” Biometrics, pp. 157–175, 1972. (Cited at p. 3.)

    1972

  30. [37]

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

    M. Belkin, P. Niyogi, and V . Sindhwani, “Manifold regularization: A geometric framework for learning from labeled and unlabeled examples.,” Journal of machine learning research, vol. 7, no. 11, 2006. (Cited at p. 3.)

    2006

  31. [38]

    A graph theoretical regression model for brain connectivity learning of alzheimer’s disease,

    C. Hu, L. Cheng, J. Sepulcre, G. El Fakhri, Y . M. Lu, and Q. Li, “A graph theoretical regression model for brain connectivity learning of alzheimer’s disease,” in2013 IEEE 10th International Symposium on Biomedical Imaging, pp. 616–619, IEEE, 2013. (Cited at p. 3.)

    2013

  32. [39]

    Three scenarios for continual learning,

    G. M. Van de Ven and A. S. Tolias, “Three scenarios for continual learning,” arXiv preprint arXiv:1904.07734, 2019. (Cited at pp. 4 and 16.)

    1904 arXiv

  33. [40]

    Cglb: Benchmark tasks for continual graph learning,

    X. Zhang, D. Song, and D. Tao, “Cglb: Benchmark tasks for continual graph learning,”Advances in Neural Information Processing Systems, vol. 35, pp. 13006–13021, 2022. (Not cited.)

    2022

  34. [41]

    Continual lifelong learning with neural networks: A review,

    G. I. Parisi, R. Kemker, J. L. Part, C. Kanan, and S. Wermter, “Continual lifelong learning with neural networks: A review,”Neural networks, vol. 113, pp. 54–71, 2019. (Cited at pp. 4 and 16.)

    2019

  35. [42]

    Dygrain: An incremental learning framework for dynamic graphs.,

    S. Kim, S. Yun, and J. Kang, “Dygrain: An incremental learning framework for dynamic graphs.,” in IJCAI, pp. 3157–3163, 2022. (Cited at pp. 4 and 16.)

    2022

  36. [43]

    Continual graph convolutional network for text classification,

    T. Wu, Q. Liu, Y . Cao, Y . Huang, X.-M. Wu, and J. Ding, “Continual graph convolutional network for text classification,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 37, pp. 13754–13762, 2023. (Not cited.)

    2023

  37. [44]

    Roland: graph learning framework for dynamic graphs,

    J. You, T. Du, and J. Leskovec, “Roland: graph learning framework for dynamic graphs,” in Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pp. 2358–2366, 2022. (Cited at pp. 4 and 16.)

    2022

  38. [45]

    Temporal recommendation on graphs via long-and short-term preference fusion,

    L. Xiang, Q. Yuan, S. Zhao, L. Chen, X. Zhang, Q. Yang, and J. Sun, “Temporal recommendation on graphs via long-and short-term preference fusion,” in Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 723–732, 2010. (Cited at p. 4.)

    2010

  39. [46]

    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. (Cited at pp. 4, 8, and 17.)

    2020

  40. [47]

    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,” in International conference on machine learning, pp. 874–883, PMLR, 2020. (Cited at p. 4.)

    2020

  41. [48]

    Simplifying clustering with graph neural networks,

    F. M. Bianchi, “Simplifying clustering with graph neural networks,” arXiv preprint arXiv:2207.08779, 2022. (Cited at p. 4.)

    2022 arXiv

  42. [49]

    Modularity and community structure in networks,

    M. E. Newman, “Modularity and community structure in networks,”Proceedings of the national academy of sciences, vol. 103, no. 23, pp. 8577–8582, 2006. (Cited at pp. 4 and 9.)

    2006

  43. [51]

    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. (Cited at pp. 8 and 16.)

    2016 arXiv

  44. [52]

    Inductive representation learning on large graphs,

    W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” Advances in neural information processing systems, vol. 30, 2017. (Cited at p. 8.)

    2017

  45. [53]

    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. (Cited at p. 8.)

    2018 arXiv

  46. [54]

    Graph attention networks,

    P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio, Y . Bengio,et al., “Graph attention networks,” stat, vol. 1050, no. 20, pp. 10–48550, 2017. (Cited at p. 8.)

    2017

  47. [55]

    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. (Cited at pp. 8 and 17.)

    1907 arXiv

  48. [56]

    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. (Cited at pp. 8 and 17.)

    2016

  49. [57]

    Conductance and the rapid mixing property for markov chains: the approximation of permanent resolved,

    M. Jerrum and A. Sinclair, “Conductance and the rapid mixing property for markov chains: the approximation of permanent resolved,” in Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 235–244, 1988. (Cited at p. 9.)

    1988

  50. [58]

    Visualizing structure and transitions in high-dimensional biological data,

    K. R. Moon, D. Van Dijk, Z. Wang, S. Gigante, D. B. Burkhardt, W. S. Chen, K. Yim, A. v. d. Elzen, M. J. Hirn, R. R. Coifman, et al., “Visualizing structure and transitions in high-dimensional biological data,” Nature biotechnology, vol. 37, no. 12, pp. 1482–1492, 2019. (Cited...

    2019

  51. [59]

    Mnist handwritten digit database,

    Y . LeCun, C. Cortes, and C. Burges, “Mnist handwritten digit database,”ATT Labs [Online]. Available: http://yann.lecun.com/exdb/mnist, vol. 2, 2010. (Cited at pp. 9 and 17.)

    2010

  52. [60]

    Glove: Global vectors for word representation,

    J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors for word representation,” in Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532–1543, 2014. (Cited at pp. 9 and 17.)

    2014

  53. [61]

    An information flow model for conflict and fission in small groups,

    W. W. Zachary, “An information flow model for conflict and fission in small groups,”Journal of anthropological research, vol. 33, no. 4, pp. 452–473, 1977. (Cited at pp. 9, 17, and 21.)

    1977

  54. [62]

    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,” in Proceedings of the twentieth annual symposium on Computational geometry, pp. 253–262, 2004. (Cited at p. 15.)

    2004

  55. [63]

    Link prediction in complex networks: A survey,

    L. Lü and T. Zhou, “Link prediction in complex networks: A survey,” Physica A: statistical mechanics and its applications, vol. 390, no. 6, pp. 1150–1170, 2011. (Cited at p. 16.)

    2011

  56. [64]

    Graph classification using signal-subgraphs: Applications in statistical connectomics,

    J. T. V ogelstein, W. G. Roncal, R. J. V ogelstein, and C. E. Priebe, “Graph classification using signal-subgraphs: Applications in statistical connectomics,” IEEE transactions on pattern analysis and machine intelligence, vol. 35, no. 7, pp. 1539–1551, 2012. (Cited at p. 16.)

    2012

  57. [65]

    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. (Cited at p. 17.)

    2021 arXiv

  58. [66]

    Revisiting semi-supervised learning with graph embeddings,

    Z. Yang, W. Cohen, and R. Salakhudinov, “Revisiting semi-supervised learning with graph embeddings,” in International conference on machine learning, pp. 40–48, PMLR, 2016. (Cited at p. 17.)

    2016

  59. [67]

    Pitfalls of graph neural network evaluation,

    O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann, “Pitfalls of graph neural network evaluation,” arXiv preprint arXiv:1811.05868, 2018. (Cited at p. 17.)

    2018 arXiv

  60. [68]

    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,” in Proceedings of The Web Conference 2020, pp. 2331–2341,

    2020

  61. [69]

    scbert as a large-scale pretrained deep language model for cell type annotation of single-cell rna-seq data,

    F. Yang, W. Wang, F. Wang, Y . Fang, D. Tang, J. Huang, H. Lu, and J. Yao, “scbert as a large-scale pretrained deep language model for cell type annotation of single-cell rna-seq data,” Nature Machine Intelligence, vol. 4, no. 10, pp. 852–866, 2022. (Cited at p. 17.)

    2022

  62. [70]

    Pygsp: Graph signal processing in python

    M. Defferrard, L. Martin, R. Pena, and N. Perraudin, “Pygsp: Graph signal processing in python.” (Cited at p. 17.)

  63. [71]

    Collective dynamics of ‘small-world’networks,

    D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,”nature, vol. 393, no. 6684, pp. 440–442, 1998. (Cited at p. 17.) 14 Appendix A Degree-Corrected Stochastic Block Model(DC-SBM) The DC-SBM is one of the most commonly used models for networks with co...

    1998

  64. [2020]

    (Cited at p. 17.) 13

Pith tools

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