Distance-Preserving Embeddings in Inhomogeneous Random Graphs

Luana Ruiz; My Le; Souvik Dhara

REVIEW 2 major objections 4 minor 285 references

Distance-Preserving Embeddings in Inhomogeneous Random Graphs

T0 review · 2 major / 4 minor · reviewed 2026-07-14 · grok-4.5

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

Pith's one-line read On typical inhomogeneous networks, landmark embeddings need only dimension Ω(n^{1-ε} log n) to keep (1±ε) shortest-path distortion, a polynomial saving over classical worst-case bounds.

desk verdict Solid average-case improvement on landmark distortion for IHGs, with a clean sandwiching lift to L^{2} kernels and usable GNN transfer experiments. read the letter →

arxiv 2607.10074 v1 pith:46QYKHTD submitted 2026-07-11 cs.LG

My Le , Luana Ruiz , Souvik Dhara This is my paper

classification cs.LG

keywords shortestpathdistance-preservingembeddingslandmarksgraphspannersinhomogeneousrandomgraphsheterogeneityneuralnetworkstransferability

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

Worst-case theory says that preserving all pairwise shortest-path distances up to a (1±ε) factor forces embedding dimension that grows like a high power of n. This paper shows that the story changes once the graph is drawn from a broad family of inhomogeneous random graphs that capture community structure and heavy-tailed degrees. In the supercritical regime the local neighborhoods expand exponentially at a rate fixed by the spectral radius of the type-affinity matrix (or its continuous integral-operator analogue). That controlled expansion lets a multiscale landmark scheme place a few carefully sized sets of reference nodes so that both the lower- and upper-bound distance estimators stay within (1±ε) of the true distances, yet the total embedding dimension shrinks to only Ω(n^{1-ε} log n). The same dimension-distortion trade-off extends from finite-type models to arbitrary L² kernels by a metric-sandwiching argument that approximates any continuous kernel by two nearby step-function kernels. Global averages over all connected pairs concentrate as well, and a GNN trained on small random instances can replace exact landmark distances while transferring to large real networks.

What carries the argument

Metric sandwiching: any L² kernel is squeezed between two finite step-function kernels whose spectral radii stay within O(δ) of the original; the finite-type distortion theorems then pass to the continuum limit as the partition is refined.

What would settle it

Generate a sequence of supercritical IHGs whose spectral radius approaches 1 from above, run the same multiscale landmark scheme with dimension o(n^{1-ε} log n), and check whether the fraction of pairs whose distortion exceeds (1±ε) stays bounded away from zero.

Watch

Extended reading notes

Core claim

For supercritical inhomogeneous random graphs (finite types or general L² kernels), landmark-based embeddings achieve (1±ε)-distortion of shortest-path distances with embedding dimension Ω(n^{1-ε} log n)—a polynomial improvement over the classical worst-case requirements—because neighborhood expansion is governed by a multi-type branching process whose growth rate is the spectral radius of the affinity operator.

Load-bearing premise

The affinity operator must stay uniformly supercritical: its leading eigenvalue is bounded away from 1 by a fixed positive gap that does not shrink with n. Without that gap the exponential neighborhood growth that powers the dimension saving collapses.

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.

Desk Editor's Note

read the letter

The real advance here is the average-case dimension–distortion trade-off for landmark embeddings on supercritical inhomogeneous random graphs: they get Ω(n^{1-ε} log n) for both (1±ε) distortions, a polynomial saving over the classical worst-case exponents. That is new, and the proofs are written out carefully.

What works. The finite-type analysis (neighborhood growth via multi-type branching processes, Chernoff control on intersections, multi-scale sampling) is complete and free of obvious algebraic gaps. The metric-sandwiching construction that transfers the same bounds to arbitrary L^{2} kernels (including heavy-tailed Chung–Lu) is a genuine technical contribution; the coupling and spectral-perturbation arguments look standard and correctly applied. The global average-distortion theorem is a useful extension of the pointwise results. Experiments are reproducible (code link) and show that GNN surrogates trained on small ER graphs transfer to larger ER and to real networks at least as well as exact BFS landmarks, which is practically useful.

Soft spots, in proportion. The uniform-supercriticality assumption (λ₁ ≥ 1+ε for a fixed ε>0, all n) is load-bearing: every expansion and intersection lemma uses the uniform gap so that neighborhoods stay super-polynomial up to log n. The paper states the claims only inside that regime, so it is a modeling boundary rather than a hidden flaw, but the dimension savings evaporate if λ₁ can approach 1. The GNN section is empirical; free parameters (depth/width, landmark base M and repetitions R) are present but not over-claimed. Citation pattern is clean; self-citations are background only.

This is for people who care about average-case metric embeddings, approximate distance oracles, or transferable GNN distance features on heterogeneous networks. The math is solid enough and the result usable enough that a serious editor should send it to referees. I would engage with it.

Referee Report

2 major / 4 minor

Summary. The paper studies landmark-based distance-preserving embeddings on inhomogeneous random graphs (IHGs) with type-dependent edge probabilities. Using multi-type branching-process approximations of neighborhood expansion, it proves that in the uniformly supercritical regime a multi-scale landmark scheme achieves (1±ε)-distortion with embedding dimension Ω(n^{1-ε} log n), a polynomial improvement over classical worst-case bounds. The same trade-off is lifted to global averages over connected pairs and, via a metric-sandwiching construction that approximates an arbitrary L² kernel by finite step-function kernels, to continuous latent-space models including heavy-tailed Chung–Lu graphs. A GNN surrogate for the local landmark-distance step is introduced and shown experimentally to transfer from small ER graphs to large synthetic and real networks while matching or exceeding exact BFS landmarks on denser instances.

Significance. If the claims hold, the work supplies the first average-case dimension–distortion guarantees for a practically used embedding method on a broad, realistic random-graph family, replacing the pessimistic polynomial exponents of Bourgain–Matoušek–Sarma with an essentially linear (yet still sub-linear in the worst-case sense) dependence that improves with the spectral gap. The sandwiching argument unifies discrete and continuous models under a single spectral mechanism and therefore covers power-law networks. Full proofs of all neighborhood-growth, intersection and distortion statements appear in §7; the accompanying GNN code is released and the transferability experiments are reproducible. These elements together give both a theoretical foundation for virtual spanners on heterogeneous networks and a concrete, transferable algorithmic realization.

major comments (2)

[§3.2 Assumption 3.2 and Remark 1] Assumption 3.2 (uniform supercriticality λ₁(D)≥1+ε for a fixed ε>0 independent of n) is load-bearing for every expansion lemma (4.6–4.8), the intersection control (Prop. 4.4) and therefore Theorems 4.1–4.2 and 5.2. The paper correctly conditions all statements on this gap, yet the near-critical regime λ₁↓1 is left unexplored; a short quantitative discussion of how the dimension exponent degrades as ε→0 would clarify the modeling boundary of the claimed polynomial improvement.
[§6 Experimental Setup and Experiments 1–3] All synthetic GNN training and evaluation (§6) is performed exclusively on the T=1 Erdős–Rényi special case. While the theory is developed for multi-type and continuous kernels, the empirical claim that “models trained on small-scale random graphs learn to extract universal distance-preserving features” is therefore supported only for homogeneous graphs; a multi-type synthetic experiment would strengthen the bridge between the main theorems and the GNN results.

minor comments (4)

[Abstract and §1–§2] Numerous missing spaces appear throughout the extracted text (“bothlocal”, “typicallarge-scale”, “virtualgraph”, “W orst-Case”, “T ransferability”, etc.). These are almost certainly PDF-extraction artefacts but should be cleaned in the camera-ready version.
[§6.1 Experiment 1] Figure 3 caption and surrounding text state that GNN depth exceeds ⌈log_λ n⌉, yet predictions still saturate; a one-sentence clarification that message-passing depth is necessary but not sufficient for long-range distances would help readers.
[§2.2] The notation for the lower- and upper-bound estimators switches between d̲, d̄ and d, d̄; a single consistent pair of symbols should be fixed in §2.2 and used thereafter.
[§6.3 and Table 1] Table 1 lists 16 real networks but only a subset appear in Figures 5–6; either all should be shown or the selection criterion stated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; distortion–dimension trade-offs are derived from first-principles multi-type branching-process neighborhood expansion and spectral radius of the affinity matrix/kernel under explicit supercriticality assumptions.

full rationale

The central claims (Theorems 4.1–4.2, Remark 1, Theorem 4.5, Theorems 5.1–5.2) rest on Lemmas 4.6–4.8 and Propositions 4.3–4.4, which bound neighborhood sizes |∂N_k(u)_t| = Θ(λ_1^k) and intersections via the multi-type branching-process approximation of IHG exploration (standard coupling to the mean matrix D or integral operator T_κ, citing Bollobás–Janson–Riordan and van der Hofstad). These are not defined in terms of the target distortion; the (1±ε) guarantees and the improved dimension Ω(n^{1-ε} log n) follow by plugging the exponential growth into the multiscale landmark sampling probabilities (exactly as in the classical Sarma et al. argument, but with the tighter expansion rate). The metric-sandwiching construction (Theorem 5.1) is an independent coupling argument that transfers the finite-type bounds; it does not presuppose the distortion result. GNN experiments and transferability citations (Ruiz et al.) are methodological and non-load-bearing for the theorems. No parameter is fitted to the claimed trade-off, no uniqueness theorem is imported from the authors, and no known empirical pattern is merely renamed. The uniform-supercriticality gap (Assumption 3.2) is an explicit modeling hypothesis, not a circular definition. The derivation is therefore self-contained against external benchmarks.

Assumptions & free parameters 2 free parameters · 6 assumptions · 1 invented entities

The central claims rest on three modeling assumptions that define the IHG class, standard multi-type branching-process approximation theorems from the random-graph literature, and the classical existence of (1±ε) embeddings in worst-case metrics. No free parameters are fitted to data for the theoretical bounds; the GNN experiments use ordinary hyper-parameters that do not enter the mathematical claims.

free parameters (2)

GNN hidden widths and depths
Nine architectures with √n nodes in first/last layers and varying hidden sizes; chosen by hand for the experimental section only, not used in any theorem.
landmark base M and number of repetitions R
M>1 integer and R=Ω(n^{1-ε+ς}) are free design choices that appear in the statements of Theorems 4.1–4.2; they are not fitted to data.

assumptions (6)

domain assumption Affinity matrix D is primitive (irreducible and aperiodic) — Assumption 3.1
Guarantees [D^k]_{ij}=Θ(λ_{1}^k) uniformly, used throughout neighborhood-growth lemmas.
domain assumption Uniform supercriticality: λ_{1}(D)≥1+ε for a fixed ε>0 independent of n — Assumption 3.2
Ensures a unique giant component and exponential neighborhood expansion at rate λ_{1}; load-bearing for all distortion theorems.
domain assumption Type proportions n_t/n o α_t >0 — Assumption 3.3
Prevents vanishing type classes that would break concentration of edge counts.
standard math Local neighborhoods of IHGs couple to multi-type Poisson branching processes up to depth κ log_λ_{1} n (Bollobás–Janson–Riordan, van der Hofstad)
Standard random-graph fact invoked in Lemmas 4.7–4.8 and Propositions 4.3–4.4.
standard math Kesten–Stigum theorem for supercritical multi-type branching processes (Grama et al. 2023)
Supplies the almost-sure exponential growth on the survival event used in Lemma 4.7.
standard math Bourgain/Matoušek/Sarma worst-case dimension-distortion lower bounds
Used only as the baseline that the IHG bounds improve upon; not needed for the positive results.

invented entities (1)

metric sandwiching framework (κ^±_δ step-function kernels) independent evidence
purpose: Couples an arbitrary L^{2} kernel between two finite-type models so that shortest-path distances and spectral radii are controlled, transferring the finite-type distortion theorems to continuous latent spaces.
The construction is new to this paper; independent evidence is the spectral-perturbation and edge-inclusion arguments given in Theorem 5.1, which rely only on standard operator theory.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distance-Preserving Embeddings in Inhomogeneous Random Graphs." pith.science (2026). https://pith.science/paper/46QYKHTD

@misc{pith2026260710074,
  author       = {Pith},
  title        = {Pith review of: Distance-Preserving Embeddings in Inhomogeneous Random Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/46QYKHTD}},
  note         = {Machine review of arXiv:2607.10074}
}

abstract

Graph machine learning provides powerful tools for understanding complex networks and learning meaningful node representations. A central challenge, however, is designing embeddings with minimal distortion of both local and global functionals, such as shortest path lengths. Prior distortion guarantees for distance-preserving embeddings are worst-case in nature, producing overly pessimistic bounds that fail to capture the structure of typical large-scale networks. To address this, we analyze shortest-path approximation via landmark-based embeddings on inhomogeneous random graphs, a general model with type-dependent edge probabilities. By retaining shortest paths to a small set of reference nodes called landmarks, landmark-based methods effectively function as virtual graph spanners, where structural heterogeneity and controlled neighborhood expansion modeled via multi-type branching processes enable significantly tighter dimension-distortion trade-offs than classical worst-case bounds. We extend these guarantees to global, component-wide averages and unify the analysis across finite-type and continuous latent spaces through a novel metric sandwiching framework, establishing universal distortion bounds for general $L^2$ kernel models, including heavy-tailed and power-law networks. Finally, we introduce a GNN-augmented variant that replaces rigid, computationally expensive exact shortest-path queries with flexible, structure-aware neural surrogates. By leveraging the inherent alignment between graph neural message-passing and the dynamic programming principles of shortest-path algorithms, our approach demonstrates that models trained on small-scale random graphs learn to extract universal distance-preserving features, achieving robust generalization to large-scale, real-world networks that match or exceed the fidelity of classical, exact landmark-based embeddings.

Figures

Figures reproduced from arXiv: 2607.10074 by the authors.

**Figure 1.** Schematic depicting the computation of the lower bound d(u1, u2), where k2−k1 ≥ (1 − ε)d(u1, u2). Blue nodes are the source u1 and target u2, orange nodes are landmarks in set S, and gray nodes are arbitrary nodes. Since D is primitive, [Dk ]ij = Θ(λ k 1 ) for any type pair (i, j), so Proposition 4.3 implies that neighborhoods grow exponentially at rate λ k 1 for 1 ≪ k ≤ logλ1 n. Hence, the local step of the landmar… view at source ↗

**Figure 2.** Schematic depicting the computation of the upper bound ¯d(u1, u2), where k1 = k2 = 1+ε 2 d(u1, u2). Blue nodes are the source u1 and target u2, orange nodes are landmarks in set S, and gray nodes are arbitrary nodes. Proposition 4.4 shows that once k1 + k2 exceeds logλ1 nt , the intersection ∂Nk1 (u1)t ∩ ∂Nk2 (u2)t is non-trivial and grows as λ k1+k2 1 /nt w.h.p. In other words, once neighborhoods 12 [PITH_FULL_IMA… view at source ↗

**Figure 3.** plots the actual shortest path distances versus those predicted by our selected GNN architectures. Predictions for distances beyond the GNN depth saturate, indicating that GNNs cannot capture longer distances even with depth exceeding the expected path length. As expected, GNNs are not suitable for computing end-to-end shortest path distances, especially on sparser graphs with λ ∈ {3, 4}, which tend to exhibit longe… view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: (a)-(d) Error rates of BFS-based and GNN-based lower bounds on graphs generated by ERn(λ/n), with the GNNs trained on graphs from the same model. (e) Time required to generate all node-to-landmark distances in n-node ER graphs by NetworkX’s highly optimized BFS compar…

**Figure 5.** Figure 5: Error rates of BFS-based and GNN-based lower bounds on (a,d) test Erd˝os–R´enyi graphs generated by ERn′(λ/n′ ), (b,e) Arxiv COND-MAT collaboration network with 21,364 nodes, and (c,f) GEMSEC company network with 14,113 nodes, with the GNNs trained on graphs from ERn(λ…

**Figure 6.** Figure 6: Additional transferability results on real networks, with the GNNs trained on graphs from ERn(λ/n). Legend is the same as in [PITH_FULL_IMAGE:figures/full_fig_p024_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

285 extracted references · 2 canonical work pages

[1]

W. B. Johnson and J. Lindenstrauss and G. Schechtman , title =. Geometrical Aspects of Functional Analysis (1985/86) , series =. 1987 , doi =

1985
[2]

J. Matou. Note on bi-Lipschitz embeddings into normed spaces , journal =
[3]

Proceedings of the Symposium on Foundations of Computer Science (FOCS) , publisher =

Piotr Indyk , title =. Proceedings of the Symposium on Foundations of Computer Science (FOCS) , publisher =. 2001 , pages =

2001
[4]

Riordan and N

O. Riordan and N. Wormald , title =. Combinatorics, Probability and Computing , year =
[5]

and Gama, F

Ruiz, L. and Gama, F. and G. Marques, A. and Ribeiro, A. Invariance-Preserving Localized Activation Functions for Graph Neural Networks. 2020

2020
[6]

and Gama, F

Ruiz, L. and Gama, F. and Ribeiro, A. Gated Graph Recurrent Neural Networks. 2020

2020
[7]

and Gama, F

Ruiz, L. and Gama, F. and Ribeiro, A. Graph Neural Networks: Architectures, Stability and Transferability. Proc. IEEE. 2021

2021
[8]

and Chamon, L

Ruiz, L. and Chamon, L. F. O. and Ribeiro, A. Graphon Signal Processing. 2021

2021

Show all 285 references

[9]

and Ruiz, L

Cervino, J. and Ruiz, L. and Ribeiro, A. Learning by Transference: Training Graph Neural Networks on Growing Graphs. 2023

2023
[10]

and Ruiz, L

Wang, Z. and Ruiz, L. and Ribeiro, A. Stability to Deformations in Manifold Neural Networks. arXiv [cs.LG]:2106.03725. 2021

2021 arXiv
[11]

and Chamon, L

Ruiz, L. and Chamon, L. F. O. and Ribeiro, A. Transferability Properties of Graph Neural Networks. IEEE Transactions on Signal Processing , year=
[12]

and Gama, F

Ruiz, L. and Gama, F. and G. Marques, A. and Ribeiro, A. Median Activation Functions for Graph Neural Networks. 44th. 2019

2019
[13]

and Gama, F

Ruiz, L. and Gama, F. and Ribeiro, A. Gated Graph Convolutional Recurrent Neural Networks. 27th. 2019

2019
[14]

and Gama, F

Ruiz, L. and Gama, F. and Ribeiro, A. Spatial Gating Strategies for Graph Recurrent Neural Networks. 45th. 2020

2020
[15]

and Chamon, L

Ruiz, L. and Chamon, L. F. O. and Ribeiro, A. The G raphon F ourier T ransform. 45th. 2020

2020
[16]

and Chamon, L

Ruiz, L. and Chamon, L. F. O. and Ribeiro, A. Graphon Neural Networks and the Transferability of Graph Neural Networks. 34th. 2020

2020
[17]

and Ruiz, L

Iancu, B. and Ruiz, L. and Ribeiro, A. and Isufi, E. Graph-Adaptive Activation Functions for Graph Neural Networks. 30th Int. Workshop Mach. Learn. Signal Process. 2020

2020
[18]

and Chamon, L

Ruiz, L. and Chamon, L. F. O. and Ribeiro, A. Graphon Filters: Signal Processing in Very Large Graphs. 28th. 2021

2021
[19]

and Ruiz, L

Parada-Mayorga, A. and Ruiz, L. and Ribeiro, A. Graphon Pooling in Graph Neural Networks. 28th. 2021

2021
[20]

and Ruiz, L

Wang, Z. and Ruiz, L. and Ribeiro, A. Stability of Neural Networks on R iemannian Manifolds. 29th. 2021

2021
[21]

and Wang, Z

Ruiz, L. and Wang, Z. and Ribeiro, A. Graphon and Graph Neural Network Stability. 46th. 2021

2021
[22]

and Gama, F

Ruiz, L. and Gama, F. and Ribeiro, A. and Isufi, E. Nonlinear State-Space Generalizations of Graph Convolutional Neural Networks. 46th. 2021

2021
[23]

and Ainslie, J

Ruiz, L. and Ainslie, J. and Onta \ n \'o n, S. Iterative Decoding for Compositional Generalization in Transformers. arXiv:2110.04169 [cs.LG]. 2021

2021 arXiv
[24]

and Chamon, L

Ruiz, L. and Chamon, L. F. O. and Ribeiro, A. Transferable Graph Neural Networks on Large-Scale Stochastic Graphs. 55th. 2021

2021
[25]

and Ruiz, L

Wang, Z. and Ruiz, L. and Ribeiro, A. Stability of Neural Networks on Manifolds to Relative Perturbations. 47th. 2022

2022
[26]

and Ruiz, L

Wang, Z. and Ruiz, L. and Eisen, M. and Ribeiro, A. Stable and Transferable Wireless Resource Allocation Policies via Manifold Neural Networks. 47th. 2022

2022
[27]

and Ribeiro, A

Cervi\ no, J/ and Ruiz, L. and Ribeiro, A. Training Stable Graph Neural Networks through Constrained Learning. 47th. 2022

2022
[28]

and Varma, R

Chen, S. and Varma, R. and Sandryhaila, A. and Kovacevic, J. Discrete Signal Processing on Graphs: Sampling Theory. 2015

2015
[29]

Marques, A. G. and Segarra, S. and Leus, G. and Ribeiro, A. Sampling of Graph Signals with Successive Local Aggregations. 2015

2015
[30]

Chamon, L. F. O. and Ribeiro, A. Greedy Sampling of Graph Signals. 2017

2017
[31]

and Eldar, Y

Heimowitz, A. and Eldar, Y. C. A Unified View of Diffusion Maps and Signal Processing on Graphs. 2017 Int. Conf. Sampling Theory and Appl. 2017

2017
[32]

and Moura, J

Sandryhaila, A. and Moura, J. M. F. Discrete Signal Processing on Graphs: Graph Filters. 38th. 2013

2013
[33]

and Moura, J

Sandryhaila, A. and Moura, J. M. F. Discrete Signal Processing on Graphs: Frequency Analysis. 2014

2014
[34]

Gama, F. and G. Marques, A. and Leus, G. and Ribeiro, A. Convolutional Neural Network Architectures for Signals Supported on Graphs. 2018

2018
[35]

and Isufi, E

Levie, R. and Isufi, E. and Leus, G. Kutyniok, G. On the Transferability of Spectral Graph Filters. arXiv:1901.10524 [cs.LG]. 2019

1901 arXiv
[36]

Shuman, D. I. and Narang, S. K. and Frossard, P. and Ortega, A. and Vandergheynst, P. The Emerging Field of Signal Processing on Graphs: Extending high-dimensional data analysis to networks and other irregular domains. 2013

2013
[37]

and Bresson, X

Defferrard, M. and Bresson, X. and Vandergheynst, P. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. 2016

2016
[38]

Kipf, T. N. and Welling, M. Semi-Supervised Classification with Graph Convolutional Networks. 5th. 2017

2017
[39]

and Bengio, Y

LeCun, Y. and Bengio, Y. and Hinton, G. Deep Learning. Nature. 2015

2015
[40]

and Zaremba, W

Bruna, J. and Zaremba, W. and Szlam, A. and LeCun, Y. Spectral Networks and Deep Locally Connected Networks on Graphs. arXiv:1312.6203v3 [cs.LG]. 2014

2014 arXiv
[41]

Bronstein, M. M. and Bruna, J. and LeCun, Y. and Szlam, A. and Vandergheynst, P. Geometric Deep Learning: Going Beyond Euclidean Data. arXiv:1611.08097v2 [cs.CV]. 2017

2017 arXiv
[42]

and Bengio, Y

Goodfellow, I. and Bengio, Y. and Courville, A. Deep Learning. 2016

2016
[43]

and Warde-Farley, D

Goodfellow, I. and Warde-Farley, D. and Mirza, M. and Courville, A. and Bengio, Y. Maxout Networks. 30th. 2013

2013
[44]

Kuo, C.-C. J. The CNN as a Guided Multilayer RECOS Transform. 2017

2017
[45]

Kingma, D. P. and Ba, J. L. ADAM : A Method for Stochastic Optimization. 3rd. 2015

2015
[46]

Approximation Capabilities of Multilayer Feedforward Networks

Hornik, K. Approximation Capabilities of Multilayer Feedforward Networks. Neural Networks. 1991

1991
[47]

Hodgson, R. M. and Bailey, D. G. and Naylor, M. J. and Ng, A. L.M. and McNeill, S.J. Properties, Implementations and Applications of Rank Filters. Image and Vision Computing. 1985

1985
[48]

and Zhang, X

He, K. and Zhang, X. and Ren, S. and Sun, J. Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification. 2015. 2015

2015
[49]

and Van Vaerenbergh, S

Scardapane, S. and Van Vaerenbergh, S. and Comminiello, D. and Uncini, A. Improving Graph Convolutional Networks with Non-Parametric Activation Functions. 26th. 2018

2018
[50]

and Muller, A

Guido, S. and Muller, A. Introduction to Machine Learning with Python. 2016

2016
[51]

Segarra, S. and G. Marques, A. and Leus, G. and Ribeiro, A. Interpolation of graph signals using shift-invariant graph filters. 23rd. 2015

2015
[52]

Gama, F. and G. Marques, A. and Mateos, G. and Ribeiro, A. Rethinking Sketching as Sampling: A Graph Signal Processing Approach. Signal Processing. 2020

2020
[53]

Huang, W. and A. W. Bolton, T. and D. Medaglia, J. and S. Bassett, D. and Ribeiro, A. and Van De Ville, D. A Graph Signal Processing Perspective on Functional Brain Imaging. 2018

2018
[54]

and Cammoun, L

Hagmann, P. and Cammoun, L. and Gigandet, X. and Meuli, R. and J. Honey, C. J. Wedeen, V. and Sporns, O. Mapping the Structural Core of Human Cerebral Cortex. PLoS Biol. 2008

2008
[55]

and Moura, J

Sandryhaila, A. and Moura, J. M. F. Discrete Signal Processing on Graphs. 2013

2013
[56]

Segarra, S. and G. Marques, A. and Ribeiro, A. Optimal Graph-Filter Design and Applications to Distributed Linear Network Operators. 2017

2017
[57]

and Giannakis, G

Shen, Y. and Giannakis, G. B. Online Identification OF Directional Graph Topologies Capturing Dynamic and Nonlinear Dependencies. 2018. 2018

2018
[58]

and Yang, R

Yin, L. and Yang, R. and Gabbouj, M. and Neuvo, Y. Weighted Median Filters: a Tutorial. 1996

1996
[59]

Segarra, S. and G. Marques, A. and R. Arce, G. and Ribeiro, A. Center-Weighted Median Graph Filters. 2016. 2016

2016
[60]

Segarra, S. and G. Marques, A. and R. Arce, G. and Ribeiro, A. Design of Weighted Median Graph Filters. 2017. 2017

2017
[61]

The Backpropagation Algorithm

Rojas, R. The Backpropagation Algorithm. In: Neural Networks. 1996

1996
[62]

and Eisen, M

Segarra, S. and Eisen, M. and Ribeiro, A. Authorship Attribution Through Function Word Adjacency Networks. 2015

2015
[63]

and Wallace, D

Mosteller, F. and Wallace, D. Inference and Disputed Authorship: The Federalist. 1964

1964
[64]

Huang, W. and G. Marques, A. and Ribeiro, A. Rating Prediction via Graph Signal Processing. 2018

2018
[65]

Monti, F. and M. Bronstein, M. and Bresson, X. Geometric Matrix Completion with Recurrent Multi-Graph Neural Networks. 2017

2017
[66]

and Singh, Y

Chandra, P. and Singh, Y. An Activation Function Adapting Training Algorithm for Sigmoidal Feedforward Networks. Neurocomputing. 2004

2004
[67]

and He, R

Ying, R. and He, R. and Chen, K. and Eksombatchai, P. and L. Hamilton, W. and Leskovec, J. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. 24th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining. 2018

2018
[68]

and Hinton, G

Srivastava, N. and Hinton, G. and Krishevsky, A. and Sutskever, I. and Slakhutdinov, R. Dropout: A Simple Way to Prevent Neural Networks from Overfitting. Journal of Machine Learning Research. 2014

2014
[69]

and Mateos, G

Segarra, S. and Mateos, G. and Marques, A. G. and Ribeiro, A. Blind Identification of Graph Filters. 2016

2016
[70]

Random Geometric Graphs

Penrose, M. Random Geometric Graphs. 2007

2007
[71]

Harper, F. M. and Konstan, J. A. The MovieLens Datasets: History and Context. ACM Trans. Interactive Intell. Syst. 2016

2016
[72]

and Parise, F

Avella-Medina, M. and Parise, F. and Schaub, M. and Segarra, S. Centrality Measures for Graphons: Accounting for Uncertainty in Networks. IEEE Trans. Netw. Sci. Eng. 2018

2018
[73]

Large Networks and Graph Limits

Lov \'a sz, L. Large Networks and Graph Limits. 2012

2012
[74]

Notes on the sin 2 Theorem

Seelmann, A. Notes on the sin 2 Theorem. Integral Equations and Operator Theory. 2014

2014
[75]

Wolfe, P. J. and Olhede, S. C. Nonparametric Graphon Estimation. arXiv:1309.5936 [math.ST]. 2013

2013 arXiv
[76]

and Naor, A

Alon, N. and Naor, A. Approximating the Cut-Norm via G rothendieck's Inequality. Proc. 36th Annu. ACM Symp. on Theory Comput. 2004

2004
[77]

Lax, P. D. Functional Analysis. 2002

2002
[78]

Penrose, M. D. Connectivity of Soft Random Geometric Graphs. The Annals of Applied Probability. 2016

2016
[79]

and Ribeiro, A

Gama, F. and Ribeiro, A. Ergodicity in Stationary Graph Processes: A Weak Law of Large Numbers. 2019

2019
[80]

Schaub, M. T. and Segarra, S. and Wai, H-T. Spectral Partitioning of Time-Varying Networks with Unobserved Edges. 44th. 2019

2019
[81]

and Nejati, H

Rui, L. and Nejati, H. and Cheung, N. Dimensionality Reduction of Brain Imaging Data Using Graph Signal Processing. 2016 IEEE Int. Conf. on Image Process. 2016

2016
[82]

Wills, G. J. NicheWorks - Interactive Visualization of Very Large Graphs. J. Comput. Graph. Stat. 1999

1999
[83]

and Faloutsos, C

Leskovec, J. and Faloutsos, C. Sampling from Large Graphs. 12th ACM SIGKDD Int. Conf. on Knowledge Discovery & Data Mining. 2006

2006
[84]

Davidson, E. R. and Thompson, W. J. Monster Matrices: Their Eigenvalues and Eigenvectors. Computers in Physics. 1993

1993
[85]

Morgan, R. B. Computing Interior Eigenvalues of Large Matrices. Linear Alg. Appl. 1991

1991
[86]

Paige, C. C. The computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices. 1971

1971
[87]

and Ozdaglar, A

Parise, F. and Ozdaglar, A. Graphon Games. 2019 ACM Conf. Econom. Comput. 2019

2019
[88]

Arya, S. P. et al. Air Pollution Meteorology and Dispersion. 1999

1999
[89]

Airoldi, E. M. and Costa, T. B. and Chan, S. H. Stochastic Blockmodel Approximation of a Graphon: Theory and Consistent Estimation. 27th. 2013

2013
[90]

and Bruna, J

Gama, F. and Bruna, J. and Ribeiro, A. Stability Properties of Graph Neural Networks. 2020

2020
[91]

and Guillot, D

Diao, P. and Guillot, D. and Khare, A. and Rajaratnam, B. Model-Free Consistency of Graph Partitioning. arXiv:1608.03860 [math.CO]. 2016

2016 arXiv
[92]

and Ribeiro, A

Eisen, M. and Ribeiro, A. Optimal Wireless Resource Allocation with Random Edge Graph Neural Networks. 2020

2020
[93]

and Tardif, C

Hahn, G. and Tardif, C. Graph Homomorphisms: Structure and Symmetry. Graph Symmetry. 1997

1997
[94]

and Frossard, P

Ortega, A. and Frossard, P. and Kova c evi \'c , J. and Moura, J. M. F. and Vandergheynst, P. Graph Signal Processing: Overview, Challenges, and Applications. Proc. IEEE. 2018

2018
[95]

Morency, M. W. and Leus, G. Signal Processing on Kernel-Based Random Graphs. 25th. 2017

2017
[96]

and Caines, P

Gao, S. and Caines, P. E. Graphon Control of Large-Scale Networks of Linear Systems. 2019

2019
[97]

and Szegedy, B

Lov \'a sz, L. and Szegedy, B. Limits of Dense Graph Sequences. J. Comb. Theory, Series B. 2006

2006
[98]

and Lacour, C

De Castro, Y. and Lacour, C. and Ngoc, T. M. P. Adaptive Estimation of Nonparametric Geometric Graphs. Math. Stat. Learn. 2020

2020
[99]

and Chatterjee, S

Rohe, K. and Chatterjee, S. and Yu, B. et al. Spectral Clustering and the High-Dimensional Stochastic Blockmodel. Ann. Stat. 2011

2011
[100]

Rates of Convergence of Spectral Methods for Graphon Estimation

Xu, J. Rates of Convergence of Spectral Methods for Graphon Estimation. 35th. 2018

2018
[101]

and Lu, Y

Gao, C. and Lu, Y. and Zhou, H. H. et al. Rate-optimal Graphon Estimation. Ann. Stat. 2015

2015
[102]

and Massouli \'e , L

Xu, J. and Massouli \'e , L. and Lelarge, M. Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results. Conf. Learn. Theory. 2014

2014
[103]

and Chayes, J

Borgs, C. and Chayes, J. T. and Lov \'a sz, L. and S \'o s, V. T. and Vesztergombi, K. Convergent Sequences of Dense Graphs II . Multiway Cuts and Statistical Physics. Ann. Math. 2012

2012
[104]

and Chayes, J

Borgs, C. and Chayes, J. T. and Lov \'a sz, L. and S \'o s, V. T. and Vesztergombi, K. Convergent Sequences of Dense Graphs I : Subgraph Frequencies, Metric Properties and Testing. Adv. Math. 2008

2008
[105]

and Gama, F

Tolstaya, E. and Gama, F. and Paulos, J. and Pappas, G. and Kumar, V. and Ribeiro, A. Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks. Conf. Robot Learn. 2019

2019
[106]

and Tolstaya, E

Khan, A. and Tolstaya, E. and Ribeiro, A. and Kumar, V. Graph Policy Gradients for Large Scale Robot Control. Conf. Robot Learn. 2020

2020
[107]

and Wai, H-T

Ramakrishna, R. and Wai, H-T. and Scaglione, A. A User Guide to Low-Pass Graph Signal Processing and Its Applications: Tools and Applications. 2020

2020
[108]

and Shi, J

Du, J. and Shi, J. and Kar, S. and Moura, J. M. F. On Graph Convolution for Graph CNNs. 2018. 2018

2018
[109]

and Radcliffe, M

Chung, F. and Radcliffe, M. On the Spectra of General Random Graphs. Eletron. J. Comb. 2011

2011
[110]

and Isufi, E

Gama, F. and Isufi, E. and Leus, G. and Ribeiro, A. Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks. 2020

2020
[111]

and Garin, F

Vizuete, R. and Garin, F. and Frasca, P. The L aplacian Spectrum of Large Graphs Sampled from Graphons. IEEE Trans. Netw. Sci. Eng. 2021

2021
[112]

and Huang, W

Levie, R. and Huang, W. and Bucci, L. and Bronstein, M. and Kutyniok, G. Transferability of Spectral Graph Convolutional Neural Networks. 2021

2021
[113]

and Levie, R

Maskey, S. and Levie, R. and Kutyniok, G. Transferability of Graph Neural Networks: an Extended Graphon Approach. arXiv:2109.10096 [cs.LG]. 2021

2021 arXiv
[114]

and Bietti, A

Keriven, N. and Bietti, A. and Vaiter, S. Convergence and Stability of Graph Convolutional Networks on Large Random Graphs. 34th. 2020

2020
[115]

Morency, M. W. and Leus, G. Graphon Filters: Graph Signal Processing in the Limit. 2021

2021
[116]

and Bruna, J

Gama, F. and Bruna, J. and Ribeiro, A. Stability of Graph Scattering Transforms. 33rd. 2019

2019
[117]

and Shazeer, N

Vaswani, A. and Shazeer, N. and Parmar, N. and Uszkoreit, J. and Jones, L. and Gomez, A. N. and Kaiser, . and Polosukhin, I. Attention is All You Need. 2017

2017
[118]

and Pag\`es-Zamora, A

Boukrab, R. and Pag\`es-Zamora, A. Random-Walk Laplacian for Frequency Analysis in Periodic Graphs. Sensors. 2021

2021
[119]

and Tolstaya, E

Gama, F. and Tolstaya, E. and Ribeiro, A. Graph Neural Networks for Decentralized Controllers. 47th. 2021

2021
[120]

and Chayes, J

Borgs, C. and Chayes, J. and Cohn, H. and Zhao, Y. An L^p Theory of Sparse Graph Convergence I : Limits, Sparse Random Graph Models, and Power Law Distributions. Trans. Am. Math. Soc. 2019

2019
[121]

and Bruna, J

Henaff, M. and Bruna, J. and LeCun, Y. Deep Convolutional Networks on Graph-Structured Data. arXiv:1506.05163v1 [cs.LG]. 2015

2015 arXiv
[122]

and Lerman, G

Zou, D. and Lerman, G. Graph Convolutional Neural Networks via Scattering. 2019

2019
[123]

Rezatofighi, S. H. and Kumar B. G., V. and Milan, A. and Abbasnejad, E. and Dick, A. and Reid, I. DeepSetNet : Predicting Sets with Deep Neural Networks. 3rd. 2017

2017
[124]

and Kottur, S

Zaheer, M. and Kottur, S. and Ravanbhakhsh, S. and P\' o czos, B. and Salakhutdinov, R. and Smola, A. J. Deep Sets. 2017

2017
[125]

Newman, M. E. J. Networks: An Introduction. 2010

2010
[126]

and R \'e nyi, A

Erd o s, P. and R \'e nyi, A. On Random Graphs I. Publicationes Mathematicae Debrecen. 1959

1959
[127]

and Hu, W

Xu, K. and Hu, W. and Leskovec, J. and Jegelka, S. How Powerful are Graph Neural Networks?. 7th. 2019

2019
[128]

and Gon c alves, P

Girault, B. and Gon c alves, P. and Fleury, E. Translation and Stationarity for Graph Signals. E cole N ormale S up \'e rieure de L yon, I nria R h \^o ne- A lpes, R esearch Report RR -8719. 2015

2015
[129]

Marques, A. G. and Segarra, S. and Leus, G. and Ribeiro, A. Stationary Graph Processes and Spectral Estimation. 2017

2017
[130]

and Loukas, A

Grassi, F. and Loukas, A. and Perraudin, N. and Ricaud, B. A Time-Vertex Signal Processing Framework: Scalable Processing and Meaningful Representations for Time-Series on Graphs. 2018

2018
[131]

and Vandergheynst, P

Perraudin, N. and Vandergheynst, P. Stationary Signal Processing on Graphs. 2017

2017
[132]

and Gulcehre, C

Pascanu, R. and Gulcehre, C. and Cho, K. and Bengio, Y. How to Construct Deep Recurrent Neural Networks. arXiv:1312.6026 [cs.NE]. 2014

2014 arXiv
[133]

Generating Sequences with Recurrent Neural Networks

Graves, A. Generating Sequences with Recurrent Neural Networks. arXiv:1308.0850 [cs.NE]. 2014

2014 arXiv
[134]

and Paliwal, K

Schuster, M. and Paliwal, K. K. Bidirectional Recurrent Neural Networks. 1997

1997
[135]

and Defferrard, M

Seo, Y. and Defferrard, M. and Vandergheynst, P. and Bresson, X. Structured Sequence Modeling with Graph Convolutional Recurrent Networks. 32nd. 2018

2018
[136]

and Yu, R

Li, Y. and Yu, R. and Shahabi, C. and Liu, Y. Diffusion Convolutional Recurrent Neural Network: Data-Driven Traffic Forecasting. 2018

2018
[137]

and Shi, X

Zhang, J. and Shi, X. and Xie, J. and Ma, H. and King, I. and Yeung, D.-Y. GaAN : Gated Attention Networks for Learning on Large and Spatiotemporal Graphs. Conf. Uncertainty Artificial Intell. 2018. 2018

2018
[138]

and Yin, H

Yu, B. and Yin, H. and Zhu, Z. Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting. 27th Int. Joint Conf. Artificial Intell. 2018

2018
[139]

Ioannidis, V. N. and G. Marques, A. and Giannakis, G. B. A Recurrent Graph Neural Network for Multi-Relational Data. 44th. 2019

2019
[140]

and Cucurull, G

Veli c kovi \' c , P. and Cucurull, G. and Casanova, A. and Romero, A. and Li \` o , P. and Bengio, Y. Graph Attention Networks. 2018

2018
[141]

and Tarlow, D

Li, Y. and Tarlow, D. and Brockschmidt, M. and Zemel, R. Gated Graph Sequence Neural Networks. arXiv:1511.05493 [cs.LG]. 2017

2017 arXiv
[142]

and Gama, F

Li, Q. and Gama, F. and Ribeiro, A. and Prorok, A. Graph Neural Networks for Decentralized Multi-Robot Path Planning. Int. Conf. Intell. Robots Syst. 2020

2020
[143]

and Nikolentzos, G

Wu, C. and Nikolentzos, G. and Vazirgiannis, M. E vo N et: A Neural Network for Predicting the Evolution of Dynamic Graphs. Int. Conf. Artif. Neural Netw. 2020

2020
[144]

and Pelekis, N

Baziotis, C. and Pelekis, N. and Doulkeridis, C. DataStories at SemEval-2017 Task 4 : Deep LSTM with attention for message-level and topic-based sentiment analysis. 11th Int. Workshop on Semantic Eval. 2017

2017
[145]

and Gowayyed, M

Miao, Y. and Gowayyed, M. and Metze, F. EESEN : End-to-end Speech Recognition Using Deep RNN Models and WFST -Based Decoding. IEEE Workshop Autom. Speech Recognit. Understanding. 2015

2015
[146]

and Mohamed, A

Graves, A. and Mohamed, A. and Hinton, G. Speech Recognition with Deep Recurrent Neural Networks. 38th. 2013

2013
[147]

and Gama, F

Isufi, E. and Gama, F. and Ribeiro, A. E dge N ets: Edge Varying Graph Neural Networks. 2021

2021
[148]

and Mikolov, T

Pascanu, R. and Mikolov, T. and Bengio, Y. Understanding the Exploding Gradient Problem. CoRR, abs/1211.5063. 2012

2012 arXiv
[149]

and Simard, P

Bengio, Y. and Simard, P. and Frasconi, P. Learning Long-Term Dependencies with Gradient Descent is Difficult. 1994

1994
[150]

and Perraudin, N

Susnjara, A. and Perraudin, N. and Kressner, D. and Vandergheynst, P. Accelerated Filtering on Graphs Using Lanczos Method. arXiv:1509.04537 [math.NA]. 2015

2015 arXiv
[151]

and Zhao, Z

Liao, R. and Zhao, Z. and Urtasun, R. and Zemel, R. S. Lanczosnet: M ulti-scale Deep Graph Convolutional Networks. arXiv:1901.01484 [cs.LG]. 2019

1901 arXiv
[152]

and Zhao, M

Luan, S. and Zhao, M. and Chang, X. and Precup, D. Break the Ceiling: Stronger Multi-Scale Deep Graph Convolutional Networks. 33rd. 2019

2019
[153]

and Leus, G

Gama, F. and Leus, G. and G. Marques, A. and Ribeiro, A. Convolutional Neural Networks via Node-Varying Graph Filters. 2018. 2018

2018
[154]

and Isufi, E

Coutino, M. and Isufi, E. and Leus, G. Advances in Distributed Graph Filtering. 2019

2019
[155]

and Gama, F

Isufi, E. and Gama, F. and Ribeiro, A. Generalizing Graph Convolutional Neural Networks with Edge-Variant Recursions on Graphs. 27th. 2019

2019
[156]

and Scaman, K

Virmaux, A. and Scaman, K. Lipschitz Regularity of Deep Neural Networks: Analysis and Efficient Estimation. 32nd. 2018

2018
[157]

Earthquake Commission and GNS Science and Land Information New Zealand. GeoNet. 2019

2019
[158]

Jagadish, H. V. and Gehrke, J. and Labrinidis, A. and Papakonstantinou, Y. and Patel, J. M. and Ramakrishnan, R. and Shahabi, C. Big Data and its Technical Challenges. Comm. of the ACM. 2014

2014
[159]

and Barrat, A

Fournet, J. and Barrat, A. Estimating the Epidemic Risk Using Non-Uniformly Sampled Contact Data. Sci. Rep. 2017

2017
[160]

and Fournet, J

Mastrandrea, R. and Fournet, J. and Barrat, A. Contact Patterns in a High School: A Comparison between Data Collected Using Wearable Sensors, Contact Diaries and Friendship Surveys. PloS one. 2015

2015
[161]

Ten Lectures on Wavelets

Daubechies, I. Ten Lectures on Wavelets. 1992

1992
[162]

and Mikolov, T

Pascanu, R. and Mikolov, T. and Bengio, Y. On the Difficulty of Training Recurrent Neural Networks. 30th. 2013

2013
[163]

and Li, H

Kerr, D. and Li, H. On G romov- H ausdorff Convergence for Operator Metric Spaces. J. Oper. Theory. 2009

2009
[164]

and Ruiz, L

Wang, Z. and Ruiz, L. and Ribeiro, A. Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs. arXiv:2305.18467 [cs.LG]. 2023

2023 arXiv
[165]

Roddenberry, T. M. and Gama, F. and Baraniuk, R. and Segarra, S. On local distributions in graph signal processing. 2022

2022
[166]

and Jegelka, S

Le, T. and Jegelka, S. Limits, approximation and size transferability for GNNs on sparse graphs via graphops. arXiv:2306.04495 [cs.LG]. 2023

2023 arXiv
[167]

and Levie, R

Maskey, S. and Levie, R. and Lee, Y. and Kutyniok, G. Generalization analysis of message passing neural networks on large random graphs. 2022

2022
[168]

and Ruiz, L

Krishnagopal, S. and Ruiz, L. Graph Neural Tangent Kernel: Convergence on Large Graphs. 2023

2023
[169]

and Chayes, J

Borgs, C. and Chayes, J. and Smith, A. Private graphon estimation for sparse graphs. 2015

2015
[170]

and Belkin, M

Eldridge, J. and Belkin, M. and Wang, Y. Graphons, mergeons, and so on!. 2016

2016
[171]

Optimal design of experiments

Pukelsheim, F. Optimal design of experiments. 2006

2006
[172]

and Jegelka, S

Li, C. and Jegelka, S. and Sra, S. Polynomial time algorithms for dual volume sampling. 2017

2017
[173]

and Srivastava, N

Spielman, D. and Srivastava, N. Graph sparsification by effective resistances. Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008

2008
[174]

and Calandriello, D

Rudi, A. and Calandriello, D. and Carratino, L. and Rosasco, L. On fast leverage score sampling and optimal learning. 2018

2018
[175]

and Simpson, O

Chung, F. and Simpson, O. Computing heat kernel pagerank and a local clustering algorithm. European Journal of Combinatorics. 2018

2018
[176]

and Robinson, J

Lim, D. and Robinson, J. and Zhao, L. and Smidt, T. and Sra, S. and Maron, H. and Jegelka, S. Sign and basis invariant networks for spectral graph representation learning. arXiv:2202.13013 [cs.LG]. 2022

2022 arXiv
[177]

Dwivedi, V. P. and Luu, A. T. and Laurent, T. and Bengio, Y. and Bresson, X. Graph neural networks with learnable structural and positional representations. arXiv:2110.07875 [cs.LG]. 2021

2021 arXiv
[178]

and Cohen, W

Yang, Z. and Cohen, W. and Salakhudinov, R. Revisiting semi-supervised learning with graph embeddings. 2016

2016
[179]

and Duggal, R

Freitas, S. and Duggal, R. and Chau, D. H. Mal N et: A Large-Scale Image Database of Malicious Software. arXiv:2102.01072 [cs.LG]. 2021

2021 arXiv
[180]

International Conference on Machine Learning , pages=

Local vertex colouring graph neural networks , author=. International Conference on Machine Learning , pages=. 2023 , organization=

2023
[181]

Rethinking the expressive power of

Zhang, Bohang and Luo, Shengjie and Wang, Liwei and He, Di , journal=. Rethinking the expressive power of
[182]

arXiv preprint arXiv:1910.10593 , year=

Neural execution of graph algorithms , author=. arXiv preprint arXiv:1910.10593 , year=

1910 arXiv
[183]

Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data , pages=

Fast exact shortest-path distance queries on large networks by pruned landmark labeling , author=. Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data , pages=

2013
[184]

Proceedings of the 25th ACM International on Conference on Information and Knowledge Management , pages=

Fully dynamic shortest-path distance query acceleration on massive networks , author=. Proceedings of the 25th ACM International on Conference on Information and Knowledge Management , pages=
[185]

arXiv preprint arXiv:1812.02363 , year=

A highly scalable labelling approach for exact distance queries in complex networks , author=. arXiv preprint arXiv:1812.02363 , year=

arXiv
[186]

Proceedings of the 2018 International Conference on Management of Data , pages=

When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks , author=. Proceedings of the 2018 International Conference on Management of Data , pages=

2018
[187]

arXiv preprint arXiv:1905.13211 , year=

What can neural networks reason about? , author=. arXiv preprint arXiv:1905.13211 , year=

1905 arXiv
[188]

Advances in neural information processing systems , volume=

Graph neural networks are dynamic programmers , author=. Advances in neural information processing systems , volume=
[189]

IEEE Data Engineering Bulletin , volume=

Representation learning on graphs: Methods and applications , author=. IEEE Data Engineering Bulletin , volume=
[190]

Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages=

node2vec: Scalable feature learning for networks , author=. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages=. 2016 , organization=

2016
[191]

Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages=

Deepwalk: Online learning of social representations , author=. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages=. 2014 , organization=

2014
[192]

Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM) , pages=

Grarep: Learning graph representations with global structural information , author=. Proceedings of the 24th ACM International on Conference on Information and Knowledge Management (CIKM) , pages=. 2015 , organization=

2015
[193]

IEEE Transactions on Knowledge and Data Engineering , volume=

PRONE: A scalable graph embedding method with local proximity preservation , author=. IEEE Transactions on Knowledge and Data Engineering , volume=. 2021 , publisher=

2021
[194]

Neural computation , volume=

Laplacian eigenmaps for dimensionality reduction and data representation , author=. Neural computation , volume=. 2003 , publisher=

2003
[195]

Journal of Machine Learning Research , volume=

Cauchy graph embedding , author=. Journal of Machine Learning Research , volume=
[196]

Knowledge-Based Systems , volume=

Graph embedding techniques, applications, and performance: A survey , author=. Knowledge-Based Systems , volume=. 2018 , publisher=

2018
[197]

Proceedings of the 2018 IEEE International Conference on Data Mining (ICDM) , pages=

Just walk the graph: Learning node embeddings via meta paths , author=. Proceedings of the 2018 IEEE International Conference on Data Mining (ICDM) , pages=. 2018 , organization=

2018
[198]

W. B. Johnson and J. Lindenstrauss , title =. Conference in Modern Analysis and Probability (New Haven, Conn., 1982) , series =

1982
[199]

Linial and E

N. Linial and E. London and Y. Rabinovich , title =. Combinatorica , volume =
[200]

J. Matou. On the distortion required for embedding finite metric spaces into normed spaces , journal =
[201]

ArXiv , year=

A Spectral Gap Precludes Low-Dimensional Embeddings , author=. ArXiv , year=
[202]

Geometry & Topology , volume =

Assaf Naor , title =. Geometry & Topology , volume =. 2021 , doi =

2021
[203]

, title =

Sidiropoulos, Anastasios and Badoiu, Mihai and Dhamdhere, Kedar and Gupta, Anupam and Indyk, Piotr and Rabinovich, Yuri and Racke, Harald and Ravi, R. , title =. SIAM Journal on Discrete Mathematics , volume =. 2019 , doi =. https://doi.org/10.1137/17M1113527 , abstract =

2019 doi
[204]

, author=

Computing the shortest path: A search meets graph theory. , author=. SODA , volume=
[205]

Proceedings of the 18th ACM conference on Information and knowledge management , pages=

Fast shortest path distance estimation in large networks , author=. Proceedings of the 18th ACM conference on Information and knowledge management , pages=
[206]

Proceedings of the 20th ACM international conference on Information and knowledge management , pages=

Fast fully dynamic landmark-based estimation of shortest path distances in very large graphs , author=. Proceedings of the 20th ACM international conference on Information and knowledge management , pages=
[207]

ACM Computing Surveys (CSUR) , volume=

Shortest-path queries in static networks , author=. ACM Computing Surveys (CSUR) , volume=. 2014 , publisher=

2014
[208]

2021 , school=

Distance Preserving Graph Embedding , author=. 2021 , school=

2021
[209]

International Conference on Extending Database Technology , year=

A Learning Based Approach to Predict Shortest-Path Distances , author=. International Conference on Extending Database Technology , year=
[210]

2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) , pages=

Shortest path distance approximation using deep learning techniques , author=. 2018 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) , pages=. 2018 , organization=

2018
[211]

Random Structures & Algorithms , volume=

The phase transition in inhomogeneous random graphs , author=. Random Structures & Algorithms , volume=. 2007 , publisher=

2007
[212]

2009 , publisher=

Concentration of measure for the analysis of randomized algorithms , author=. 2009 , publisher=

2009
[213]

The Annals of Applied Probability , volume=

A Kesten--Stigum type theorem for a supercritical multitype branching process in a random environment , author=. The Annals of Applied Probability , volume=. 2023 , publisher=

2023
[214]

Transactions on Machine Learning Research , year=

Adjacency Search Embeddings , author=. Transactions on Machine Learning Research , year=
[215]

Proceedings of the National Academy of Sciences , volume=

The average distances in random graphs with given expected degrees , author=. Proceedings of the National Academy of Sciences , volume=. 2002 , publisher=

2002
[216]

arXiv preprint arXiv:1905.10947 , year=

Graph neural networks exponentially lose expressive power for node classification , author=. arXiv preprint arXiv:1905.10947 , year=

1905 arXiv
[217]

2024 , isbn =

Random Graphs and Complex Networks: Volume 2 , series =. 2024 , isbn =

2024
[218]

Branching Processes , pages=

Multi-Type Branching Processes , author=. Branching Processes , pages=. 1972 , publisher=

1972
[219]

1997 , publisher=

Spectral graph theory , author=. 1997 , publisher=

1997
[220]

Statistics and computing , volume=

A tutorial on spectral clustering , author=. Statistics and computing , volume=. 2007 , publisher=

2007
[221]

2012 , publisher=

Matrix analysis , author=. 2012 , publisher=

2012
[222]

(No Title) , year=

Spectral theory: self adjoint operators in Hilbert space , author=. (No Title) , year=
[223]

1976 , publisher=

Integral operators in spaces of summable functions , author=. 1976 , publisher=

1976
[224]

1966 , publisher=

Perturbation theory for linear operators , author=. 1966 , publisher=

1966
[225]

Banach Lattices and Positive Operators , pages=

Banach lattices , author=. Banach Lattices and Positive Operators , pages=. 1974 , publisher=

1974
[226]

2012 , publisher=

Branching processes , author=. 2012 , publisher=

2012
[227]

2003 , publisher=

Random geometric graphs , author=. 2003 , publisher=

2003
[228]

Social networks , volume=

Stochastic blockmodels: First steps , author=. Social networks , volume=. 1983 , publisher=

1983
[229]

METHODS OF MODERN MATHEMATICAL PHYSICS. REV. AND ENL. VOL. 01. FUNCTIONAL ANALYSIS. , author=. 1980 , publisher=

1980
[230]

Computer Science Review , volume=

Graph spanners: A tutorial review , author=. Computer Science Review , volume=. 2020 , publisher=

2020
[231]

Journal of graph theory , volume=

Graph spanners , author=. Journal of graph theory , volume=. 1989 , publisher=

1989
[232]

Discrete & Computational Geometry , volume=

On sparse spanners of weighted graphs , author=. Discrete & Computational Geometry , volume=. 1993 , publisher=

1993
[233]

Langley , title =

P. Langley , title =. Proceedings of the 17th International Conference on Machine Learning (ICML 2000) , address =. 2000 , pages =

2000
[234]

T. M. Mitchell. The Need for Biases in Learning Generalizations. 1980

1980
[235]

M. J. Kearns , title =
[236]

Machine Learning: An Artificial Intelligence Approach, Vol. I. 1983

1983
[237]

R. O. Duda and P. E. Hart and D. G. Stork. Pattern Classification. 2000

2000
[238]

Suppressed for Anonymity , author=
[239]

Newell and P

A. Newell and P. S. Rosenbloom. Mechanisms of Skill Acquisition and the Law of Practice. Cognitive Skills and Their Acquisition. 1981

1981
[240]

A. L. Samuel. Some Studies in Machine Learning Using the Game of Checkers. IBM Journal of Research and Development. 1959

1959
[241]

Cambridge University Press

Hofstad van der , Remco. 2017. doi:10.1017/9781316779422 , publisher = "Cambridge University Press", title = "

2017 doi
[242]

Random Graphs and Complex Networks

Hofstad van der , Remco. Random Graphs and Complex Networks. 2024

2024
[243]

and Ney, Peter E

Athreya, Krishna B. and Ney, Peter E. Branching Processes. 1972

1972
[244]

2000 , publisher=

Random Graphs , author=. 2000 , publisher=

2000
[245]

Lecture notes on random graphs and probabilistic combinatorial optimization

Bordenave, Charles. Lecture notes on random graphs and probabilistic combinatorial optimization. 2016

2016
[246]

The Annals of Probability , number =

David Tanny , title =. The Annals of Probability , number =. 1977 , doi =

1977
[247]

International Conference on Learning Representations , year=

What graph neural networks cannot learn: depth vs width , author=. International Conference on Learning Representations , year=
[248]

Web Search and Data Mining , year=

A sketch-based distance oracle for web-scale graphs , author=. Web Search and Data Mining , year=
[249]

SIAM Journal on Computing , volume =

Sarma, Atish Das and Holzer, Stephan and Kor, Liah and Korman, Amos and Nanongkai, Danupon and Pandurangan, Gopal and Peleg, David and Wattenhofer, Roger , title =. SIAM Journal on Computing , volume =. 2012 , doi =

2012
[250]

Beyond GNNs : An Efficient Architecture for Graph Problems

Awasthi, Pranjal and Das, Abhimanyu and Gollapudi, Sreenivas. Beyond GNNs : An Efficient Architecture for Graph Problems. Proceedings of the AAAI Conference on Artificial Intelligence. 2022

2022
[251]

On L ipschitz embedding of finite metric spaces in H ilbert space

Bourgain, J. On L ipschitz embedding of finite metric spaces in H ilbert space. Israel Journal of Mathematics , number =. 1985 , bdsk-url-1 =. doi:10.1007/BF02776078 , id =

1985 doi
[252]

Network Science

Barabási, Albert-László and Pósfai, Márton. Network Science. 2016

2016
[253]

Networks

Newman, Mark. Networks. 2018

2018
[254]

Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages =

Palowitch, John and Tsitsulin, Anton and Mayer, Brandon and Perozzi, Bryan , title =. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages =. 2022 , isbn =. doi:10.1145/3534678.3539203 , abstract =

2022 doi
[255]

Documenta Mathematica , volume=

On the history of the shortest path problem , author=. Documenta Mathematica , volume=
[256]

2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI) , pages=

Graph colouring meets deep learning: Effective graph neural network models for combinatorial problems , author=. 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI) , pages=. 2019 , organization=

2019
[257]

Journal of Machine Learning Research , volume=

Combinatorial optimization and reasoning with graph neural networks , author=. Journal of Machine Learning Research , volume=
[258]

Advances in neural information processing systems , volume=

Combinatorial optimization with graph convolutional networks and guided tree search , author=. Advances in neural information processing systems , volume=
[259]

Efficient algorithms for the minimum shortest path S teiner arborescence problem with applications to VLSI physical design

Cong, Jason and Kahng, Andrew B and Leung, Kwok-Shing , journal=. Efficient algorithms for the minimum shortest path S teiner arborescence problem with applications to VLSI physical design. 1998 , publisher=

1998
[260]

Computers & Operations Research , volume=

Heuristic shortest path algorithms for transportation applications: State of the art , author=. Computers & Operations Research , volume=. 2006 , publisher=

2006
[261]

IEEE transactions on neural networks , volume=

The graph neural network model , author=. IEEE transactions on neural networks , volume=. 2008 , publisher=

2008
[262]

Physical review E , volume=

Scaling and percolation in the small-world network model , author=. Physical review E , volume=. 1999 , publisher=

1999
[263]

Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM '20) , organization=

Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models , author=. Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM '20) , organization=. 2020 , pages =

2020
[264]

2019 , eprint=

Multi-scale Attributed Node Embedding , author=. 2019 , eprint=

2019
[265]

Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2019 , pages=

GEMSEC: Graph Embedding with Self Clustering , author=. Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2019 , pages=. 2019 , organization=

2019
[266]

Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining , pages =

Leskovec, Jure and Kleinberg, Jon and Faloutsos, Christos , title =. Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining , pages =. 2005 , isbn =. doi:10.1145/1081870.1081893 , abstract =

2005 doi
[267]

ACM Trans

Leskovec, Jure and Kleinberg, Jon and Faloutsos, Christos , title =. ACM Trans. Knowl. Discov. Data , month =. 2007 , issue_date =. doi:10.1145/1217299.1217301 , abstract =

2007 doi
[268]

AAAI , url=

The Network Data Repository with Interactive Graph Analytics and Visualization , author=. AAAI , url=
[269]

2017 , eprint=

Semi-Supervised Classification with Graph Convolutional Networks , author=. 2017 , eprint=

2017
[270]

Inductive Representation Learning on Large Graphs , volume =

Hamilton, Will and Ying, Zhitao and Leskovec, Jure , booktitle =. Inductive Representation Learning on Large Graphs , volume =
[271]

2018 , eprint=

Graph Attention Networks , author=. 2018 , eprint=

2018
[272]

2019 , eprint=

How Powerful are Graph Neural Networks? , author=. 2019 , eprint=

2019
[273]

Fast graph representation learning with PyTorch Geometric

Fey, Matthias and Lenssen, Jan Eric , journal=. Fast graph representation learning with PyTorch Geometric
[274]

ACM Comput

Sommer, Christian , title =. ACM Comput. Surv. , month = mar, articleno =. 2014 , issue_date =. doi:10.1145/2530531 , abstract =

2014 doi
[275]

Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security , pages =

Meng, Xianrui and Kamara, Seny and Nissim, Kobbi and Kollios, George , title =. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security , pages =. 2015 , isbn =. doi:10.1145/2810103.2813672 , abstract =

2015 doi
[276]

, title =

Majumder, Anirban and Datta, Samik and Naidu, K.V.M. , title =. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages =. 2012 , isbn =. doi:10.1145/2339530.2339690 , abstract =

2012 doi
[277]

Proceedings of the 19th ACM International Conference on Information and Knowledge Management , pages =

Gubichev, Andrey and Bedathur, Srikanta and Seufert, Stephan and Weikum, Gerhard , title =. Proceedings of the 19th ACM International Conference on Information and Knowledge Management , pages =. 2010 , isbn =. doi:10.1145/1871437.1871503 , abstract =

2010 doi
[278]

Proceedings of the 23rd International Conference on World Wide Web , pages =

Akiba, Takuya and Iwata, Yoichi and Yoshida, Yuichi , title =. Proceedings of the 23rd International Conference on World Wide Web , pages =. 2014 , isbn =. doi:10.1145/2566486.2568007 , abstract =

2014 doi
[279]

Proceedings of the Sixteenth European Conference on Computer Systems , pages =

Jiang, Xiaolin and Xu, Chengshuo and Yin, Xizhe and Zhao, Zhijia and Gupta, Rajiv , title =. Proceedings of the Sixteenth European Conference on Computer Systems , pages =. 2021 , isbn =. doi:10.1145/3447786.3456226 , abstract =

2021 doi
[280]

and Leiserson, Charles E

Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald L. and Stein, Clifford , title =. 2009 , publisher =

2009
[281]

Numerische Mathematik , volume =

A Note on Two Problems in Connexion with Graphs , author =. Numerische Mathematik , volume =. 1959 , doi =

1959
[282]

The shortest path through a maze , author=. Proc. of the International Symposium on the Theory of Switching , pages=. 1959 , organization=

1959
[283]

Annals of operations research , volume=

Shortest path algorithms , author=. Annals of operations research , volume=. 1988 , publisher=

1988
[284]

SIAM Journal on Computing , volume=

Finding the hidden path: Time bounds for all-pairs shortest paths , author=. SIAM Journal on Computing , volume=. 1993 , publisher=

1993
[285]

Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science , pages=

Trans-dichotomous algorithms for minimum spanning trees and shortest paths , author=. Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science , pages=. 1990 , organization=

1990

Pith tools

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

[1] [1]

W. B. Johnson and J. Lindenstrauss and G. Schechtman , title =. Geometrical Aspects of Functional Analysis (1985/86) , series =. 1987 , doi =

1985

[2] [2]

J. Matou. Note on bi-Lipschitz embeddings into normed spaces , journal =

[3] [3]

Proceedings of the Symposium on Foundations of Computer Science (FOCS) , publisher =

Piotr Indyk , title =. Proceedings of the Symposium on Foundations of Computer Science (FOCS) , publisher =. 2001 , pages =

2001

[4] [4]

Riordan and N

O. Riordan and N. Wormald , title =. Combinatorics, Probability and Computing , year =

[5] [5]

and Gama, F

Ruiz, L. and Gama, F. and G. Marques, A. and Ribeiro, A. Invariance-Preserving Localized Activation Functions for Graph Neural Networks. 2020

2020

[6] [6]

and Gama, F

Ruiz, L. and Gama, F. and Ribeiro, A. Gated Graph Recurrent Neural Networks. 2020

2020

[7] [7]

and Gama, F

Ruiz, L. and Gama, F. and Ribeiro, A. Graph Neural Networks: Architectures, Stability and Transferability. Proc. IEEE. 2021

2021

[8] [8]

and Chamon, L

Ruiz, L. and Chamon, L. F. O. and Ribeiro, A. Graphon Signal Processing. 2021

2021