Back

Machine Learning on Graphs: A Model and Comprehensive Taxonomy

Ines ChamiSami Abu-El-HaijaBryan PerozziChristopher RéKevin Murphy

article2022JMLR349 citations

Presents a unified Graph Encoder Decoder Model (GraphEDM) and comprehensive taxonomy that integrates over thirty supervised and unsupervised graph representation learning methods into a single consistent mathematical formulation.

Listen

Modern data in critical sectors such as chemistry, biology, social networking, and recommendation systems is often interconnected and irregular rather than structured on simple grids or sequences. While standard deep learning methods excel on images and text, they struggle to model complex networks where connections vary significantly across entities. To address this challenge, researchers have developed various graph representation learning methods, which convert discrete network topologies into continuous, low-dimensional vectors. However, the field has become fragmented across distinct subfields—including unsupervised network embedding, graph-regularized neural networks, and graph neural networks—making it difficult for practitioners to evaluate trade-offs and select appropriate tools.

The main objective of the article is to establish a comprehensive taxonomy and unifying mathematical model that connects these disparate bodies of work into a single conceptual framework, evaluating over thirty prominent graph representation learning algorithms.

To bridge these approaches, the authors introduce the Graph Encoder Decoder Model, which standardizes learning into an encoding step, a decoding step, and a generalized objective function accommodating supervised, graph-regularization, and parameter losses. They further introduce the Graph Convolution Framework to specifically analyze convolution-based architectures. The authors evaluate methods across several technical dimensions: whether the approach is supervised or unsupervised, whether it uses node features, whether it operates in Euclidean or non-Euclidean geometric spaces, and whether it functions in fixed transductive settings or inductive settings that generalize to unseen networks.

The analysis reveals several core insights. First, existing algorithms can be categorized into four primary groups based on encoder design: shallow lookups, feature-based graph regularizers, graph autoencoders, and neighborhood aggregation methods. Second, the authors find that early two-step approaches—which train unsupervised embeddings first and then apply a classifier—are generally outperformed by end-to-end supervised models that jointly optimize representations and task predictions. Third, modern neighborhood aggregation methods, such as graph convolutional networks and attention-based networks, demonstrate superior empirical performance on node classification tasks because they simultaneously leverage graph structure and rich node features. Fourth, non-Euclidean geometries, such as hyperbolic spaces, represent hierarchical and tree-like graphs with substantially lower distortion than conventional Euclidean vector spaces.

These findings have direct implications for system performance, computational cost, and model selection. Organizations deploying graph machine learning can avoid costly full-batch matrix computations on large networks by selecting scalable spatial sampling or attention-based methods instead of computationally intensive spectral approaches. Furthermore, matching the underlying geometric space to the data domain—such as using hyperbolic models for hierarchical organization charts or lexical graphs—can reduce embedding dimensions and improve performance on link prediction and classification.

Stakeholders should adopt structured criteria when selecting graph learning methods, specifically considering graph size, the availability of node attributes, and whether the system must generalize to unseen nodes or graphs. For future work, development must focus on scaling these techniques to industry-scale graphs containing billions of nodes, creating standardized evaluation benchmarks to address performance variability across data splits, and integrating fairness constraints to prevent structural biases from skewing model outputs.

Confidence in these findings is high regarding model categorizations and architectural trade-offs across the surveyed literature. However, caution is warranted regarding empirical performance claims, as evaluation results in graph learning remain sensitive to experimental setups, data split selections, and hyperparameter tuning.

GoogleInformation Sciences InstituteStanford Universitymachine learningtaxonomybipartite graphsgraph neural networksgraph representation learninggraph auto-encoders
arXiv: 2005.03675
  • Paper: Benchmarking Graph Neural Networks, Vijay Prakash Dwivedi et al. (2023). This 2023 benchmark operationalizes the source’s call for standardized evaluation by comparing graph architectures under controlled parameter budgets and diverse tasks.
  • Paper: MA-GCL: Model Augmentation Tricks for Graph Contrastive Learning, Xumeng Gong et al. (2023). This 2023 study continues the source’s discussion of unsupervised graph representation learning by improving graph contrastive learning through model-level augmentation.
  • Paper: Simple and Efficient Heterogeneous Graph Neural Network, Xiaocheng Yang et al. (2023). This 2023 work applies the source’s efficiency and model-selection principles to heterogeneous graphs, simplifying attention while preserving relation-aware performance.
  • Paper: Towards Better Evaluation for Dynamic Link Prediction, Farimah Poursafaei et al. (2022). This study advances the source’s evaluation concerns into dynamic link prediction, testing whether reported graph-model gains survive realistic temporal and negative-sampling settings.
Cover for Machine Learning on Graphs: A Model and Comprehensive Taxonomy

Abstract

There has been a surge of recent interest in graph representation learning (GRL). GRL methods have generally fallen into three main categories, based on the availability of labeled data. The first, network embedding, focuses on learning unsupervised representations of relational structure. The second, graph regularized neural networks, leverages graphs to augment neural network losses with a regularization objective for semi-supervised learning. The third, graph neural networks, aims to learn differentiable functions over discrete topologies with arbitrary structure. However, despite the popularity of these areas there has been surprisingly little work on unifying the three paradigms. Here, we aim to bridge the gap between network embedding, graph regularization and graph neural networks. We propose a comprehensive taxonomy of GRL methods, aiming to unify several disparate bodies of work. Specifically, we propose the GRAPHEDM framework, which generalizes popular algorithms for semi-supervised learning (e.g. GraphSage, GCN, GAT), and unsupervised learning (e.g. DeepWalk, node2vec) of graph representations into a single consistent approach. To illustrate the generality of GRAPHEDM, we fit over thirty existing methods into this framework. We believe that this unifying view both provides a solid foundation for understanding the intuition behind these methods, and enables future research in the area.

Topics

machine learningtaxonomybipartite graphs

Keywords

graph neural networksgraph representation learninggraph auto-encodersnode classificationgraph kernelsgraph poolinggraph embeddingsknowledge graphs

Table of Contents

  • 1. Introduction
  • 2. Preliminaries
  • 2.1 Definitions
  • 2.2 The generalized network embedding problem
  • 2.2.1 Node features in network embedding
  • 2.2.2 Transductive and inductive network embedding
  • 2.2.3 Positional vs structural network embedding
  • 2.2.4 Unsupervised and supervised network embedding
  • 3. A Taxonomy of Graph Embedding Models
  • 3.1 The GraphEDM framework
  • 3.2 Taxonomy of objective functions
  • 3.3 Taxonomy of encoders
  • 3.4 Historical Context
  • 4. Unsupervised Graph Embedding
  • 4.1 Shallow embedding methods
  • 4.1.1 Distance-based: Euclidean methods
  • 4.1.2 Distance-based: Non-Euclidean methods
  • 4.1.3 Outer product-based: Matrix factorization methods
  • 4.1.4 Outer product-based: Skip-gram methods
  • 4.2 Auto-encoders
  • 4.3 Graph neural networks
  • 4.4 Summary of unsupervised embedding methods
  • 5. Supervised Graph Embedding
  • 5.1 Shallow embedding methods
  • 5.2 Graph regularization methods
  • 5.2.1 Laplacian
  • 5.2.2 Skip-gram
  • 5.3 Graph convolution framework
  • 5.3.1 The Graph Neural Network model and related frameworks
  • 5.3.2 Graph Convolution Framework
  • 5.4 Spectral Graph Convolutions
  • 5.4.1 Spectrum-based methods
  • 5.4.2 Spectrum-free methods
  • 5.5 Spatial Graph Convolutions
  • 5.5.1 Sampling-based spatial methods
  • 5.5.2 Attention-based spatial methods
  • 5.6 Non-Euclidean Graph Convolutions
  • 5.7 Summary of supervised graph embedding
  • 6. Applications
  • 6.1 Unsupervised applications
  • 6.1.1 Graph reconstruction
  • 6.1.2 Link prediction
  • 6.1.3 Clustering
  • 6.1.4 Visualization
  • 6.2 Supervised applications
  • 6.2.1 Node classification
  • 6.2.2 Graph classification
  • 7. Conclusion and Open Research Directions
  • Acknowledgments
  • References

Knowls

  1. Knowl 1 — GraphEDM unifies graph representation learning models

    model/method

    The Graph Encoder Decoder Model (GraphEDM) represents graph representation learning as an encoder followed by one or both of two decoders. Its input is an undirected weighted graph G=(V,E)G=(V,E) with adjacency matrix W∈R∣V∣×∣V∣W\in\mathbb{R}^{|V|\times |V|} and optional node-feature matrix X∈R∣V∣×d0X\in\mathbb{R}^{|V|\times d_0}, where ∣V∣|V| is the number of nodes and d0d_0 is the input-feature dimension.

    The encoder produces a dd-dimensional embedding Z∈R∣V∣×dZ\in\mathbb{R}^{|V|\times d}:

    Z=ENC⁡(W,X;ΘE).Z=\operatorname{ENC}(W,X;\Theta_E).

    Here ΘE\Theta_E denotes encoder parameters. A graph decoder maps node embeddings to a pairwise similarity or dissimilarity matrix W^∈R∣V∣×∣V∣\widehat W\in\mathbb{R}^{|V|\times |V|}:

    W^=DEC⁡(Z;ΘD),\widehat W=\operatorname{DEC}(Z;\Theta_D),

    where ΘD\Theta_D denotes graph-decoder parameters. A label decoder maps embeddings to predictions y^S∈R∣V∣×∣Y∣\widehat y^S\in\mathbb{R}^{|V|\times |\mathcal Y|} for a supervision target SS, such as node labels, edge labels, or graph labels:

    y^S=DEC⁡(Z;ΘS),\widehat y^S=\operatorname{DEC}(Z;\Theta_S),

    where Y\mathcal Y is the label space and ΘS\Theta_S denotes label-decoder parameters. Unsupervised methods use the graph-decoder branch, supervised methods use the label-decoder branch, and semi-supervised methods can use both. The same abstraction therefore covers shallow embeddings, auto-encoders, graph regularization models, and graph neural networks in both transductive and inductive settings.

  2. Knowl 2 — GraphEDM training objective combines supervision, graph structure, and parameter regularization

    equation

    Let Θ={ΘE,ΘD,ΘS}\Theta=\{\Theta_E,\Theta_D,\Theta_S\} be all trainable parameters. GraphEDM trains models by combining a task-supervision loss, a graph-regularization loss, and a parameter-regularization loss:

    L=αLSUPS(yS,y^S;Θ)+βLG,REG(W,W^;Θ)+γLREG(Θ).\mathcal L=\alpha\mathcal L_{\mathrm{SUP}}^S(y^S,\widehat y^S;\Theta)+\beta\mathcal L_{G,\mathrm{REG}}(W,\widehat W;\Theta)+\gamma\mathcal L_{\mathrm{REG}}(\Theta).

    The coefficients α,β,γ≥0\alpha,\beta,\gamma\ge 0 control the three terms and may be set to zero. The supervised term compares predicted targets y^S\widehat y^S with ground-truth targets ySy^S; for node supervision with labeled-node set VL⊆VV_L\subseteq V, it has the form LSUPN=∑i∈VLℓ(yiN,y^iN)\mathcal L_{\mathrm{SUP}}^N=\sum_{i\in V_L}\ell(y_i^N,\widehat y_i^N) for a task-specific loss ℓ\ell.

    The graph-regularization term compares the decoded matrix W^\widehat W with a target similarity or dissimilarity matrix s(W)s(W) derived from the adjacency matrix or from higher-order graph structure:

    LG,REG(W,W^;Θ)=d1(s(W),W^),\mathcal L_{G,\mathrm{REG}}(W,\widehat W;\Theta)=d_1\big(s(W),\widehat W\big),

    where d1d_1 is a matrix-distance function. Parameter regularization is commonly ℓ2\ell_2 regularization:

    LREG(Θ)=∑θ∈Θ∥θ∥22.\mathcal L_{\mathrm{REG}}(\Theta)=\sum_{\theta\in\Theta}\|\theta\|_2^2.

    Setting α=0\alpha=0 gives an unsupervised graph-embedding objective; setting α>0\alpha>0 incorporates node, edge, or graph labels. The graph term can also regularize supervised embeddings by encouraging graph-neighboring nodes to have compatible representations.

  3. Knowl 3 — The proposed taxonomy is determined by the information used by the encoder

    data/table

    GraphEDM organizes graph representation learning into four encoder classes. The distinction is whether the encoder uses a parameter lookup, node features, graph structure, or both. The taxonomy covers more than thirty representative methods.

    Could not parse LaTeX table

    The four classes differ in the route by which graph information reaches the embedding. Shallow methods store one vector per observed node and are therefore generally transductive. Graph-regularization methods encode node features without using the adjacency matrix inside the encoder, but impose graph consistency through the loss. Auto-encoders process the graph structure in the encoder but omit node features. Neighborhood-aggregation models process both features and topology in the encoder and can usually be applied inductively when the learned mapping is shared across nodes or graphs.

  4. Knowl 4 — The Graph Convolution Framework decomposes graph convolutions into patches, weights, and merging

    model/method

    The Graph Convolution Framework (GCF) provides a common description of convolution-based graph neural networks. Given node features X∈R∣V∣×d0X\in\mathbb{R}^{|V|\times d_0}, the initial hidden representation is H0=XH^0=X. At layer ℓ\ell, the model defines KK patch functions fk(W,Hℓ)∈R∣V∣×∣V∣f_k(W,H^\ell)\in\mathbb{R}^{|V|\times |V|}, where each patch specifies which nodes interact. Each patch has trainable filter weights Θkℓ∈Rdℓ×dℓ+1\Theta_k^\ell\in\mathbb{R}^{d_\ell\times d_{\ell+1}}.

    The message produced by patch kk is

    mkℓ+1=fk(W,Hℓ)HℓΘkℓ,k=1,…,K,m_k^{\ell+1}=f_k(W,H^\ell)H^\ell\Theta_k^\ell,\qquad k=1,\ldots,K,

    where dℓd_\ell and dℓ+1d_{\ell+1} are the feature dimensions at consecutive layers. A merging function hh combines the KK patch outputs:

    Hℓ+1=h(m1ℓ+1,…,mKℓ+1).H^{\ell+1}=h\big(m_1^{\ell+1},\ldots,m_K^{\ell+1}\big).

    The merge can be summation, averaging, concatenation, or a learned neural operation, usually followed by a nonlinearity. After LL layers, the node embedding is Z=HLZ=H^L. Spectral methods define patches using Laplacian eigenvectors or polynomials, whereas spatial and attention-based methods define them from local neighborhoods or learned neighbor weights. This decomposition makes convolutional graph models comparable even when their propagation operators differ.

  5. Knowl 5 — Unsupervised shallow embeddings preserve distances, similarities, or random-walk context

    model/method

    Unsupervised shallow methods use a learned embedding lookup Z∈R∣V∣×dZ\in\mathbb{R}^{|V|\times d}, with one vector zi∈Rdz_i\in\mathbb{R}^d for each observed node viv_i. They do not use node features in the encoder and learn the lookup parameters by reconstructing a graph-derived target.

    Distance-based methods decode pairwise dissimilarity as W^ij=d2(zi,zj)\widehat W_{ij}=d_2(z_i,z_j), where d2d_2 is an embedding-space distance. MDS preserves a supplied distance matrix, IsoMap sets the target to graph shortest-path distances, and Laplacian Eigenmaps preserves local edge-weighted distances. Non-Euclidean variants use distances such as the Poincaré distance for hierarchical graphs.

    Outer-product methods decode pairwise similarity by

    W^=ZZ⊤,\widehat W=ZZ^\top,

    and commonly minimize ∥s(W)−W^∥F2\|s(W)-\widehat W\|_F^2, where s(W)s(W) is a graph similarity matrix and ∥⋅∥F\|\cdot\|_F is the Frobenius norm. GF factorizes the observed adjacency entries, GraRep factorizes powers of a normalized transition matrix to encode different hop orders, and HOPE factorizes asymmetric high-order similarities using separate source and target embeddings.

    Skip-gram methods generate node sequences with random walks and train embeddings to predict context nodes. DeepWalk uses truncated unbiased random walks; node2vec biases walks toward breadth-first or depth-first exploration, allowing a trade-off between local community structure and broader positional structure. Watch Your Step learns coefficients over different powers of the transition matrix rather than fixing the random-walk context distribution. LINE separately models first-order edge proximity and second-order neighborhood similarity. These methods are transductive because the embedding lookup contains a parameter row for each node.

  6. Knowl 6 — Auto-encoders and unsupervised GNNs replace the shallow lookup with learned graph encoders

    model/method

    Graph auto-encoders use the adjacency matrix as input to a neural encoder rather than storing one independent embedding per node:

    Z=ENC⁡(W;ΘE),W^=DEC⁡(Z;ΘD).Z=\operatorname{ENC}(W;\Theta_E),\qquad \widehat W=\operatorname{DEC}(Z;\Theta_D).

    Structural Deep Network Embedding (SDNE) reconstructs the adjacency matrix while also penalizing large embedding distances for nodes with shared neighborhoods. DNGR first constructs a higher-order similarity matrix using random surfing and reconstructs that matrix with stacked denoising auto-encoders.

    Graph auto-encoders use graph neural networks in the encoder. In GAE and VGAE, the decoder is typically W^=ZZ⊤\widehat W=ZZ^\top, and the reconstruction loss is sigmoid cross-entropy:

    LG,REG=−∑i,j[(1−Wij)log⁡(1−σ(W^ij))+Wijlog⁡σ(W^ij)],\mathcal L_{G,\mathrm{REG}}=-\sum_{i,j}\left[(1-W_{ij})\log\big(1-\sigma(\widehat W_{ij})\big)+W_{ij}\log\sigma(\widehat W_{ij})\right],

    where WijW_{ij} is the adjacency entry, σ\sigma is the sigmoid function, and negative sampling is used when summing over all node pairs is too expensive. VGAE treats ZZ as a latent random variable with a standard normal prior and adds a Kullback–Leibler divergence term to the reconstruction loss. Graphite makes decoding iterative: it alternates between pairwise reconstruction of an adjacency-like matrix from the current embeddings and a graph-convolution update of the embeddings.

    Deep Graph Infomax (DGI) uses a GNN encoder, a graph-level readout, and a discriminator. It contrasts node representations from real graphs with representations from corrupted graphs, typically formed by keeping the adjacency matrix and randomly permuting node features. Its objective encourages each real node representation to agree with the representation of its whole graph and each corrupted node representation to disagree, thereby maximizing a lower bound on node–graph mutual information.

  7. Knowl 7 — Supervised graph embedding combines label prediction with graph consistency in three encoder regimes

    model/method

    Supervised graph embedding directly optimizes representations for a prediction task instead of first learning an unsupervised embedding and then training a separate classifier.

    Shallow supervised methods use the label space itself as the embedding space. Label Propagation sets the node prediction to the embedding, y^i=zi\widehat y_i=z_i, fixes y^i=yi\widehat y_i=y_i on labeled nodes, and smooths predictions over graph edges with an energy proportional to

    ∑i,jWij∥y^i−y^j∥22.\sum_{i,j}W_{ij}\|\widehat y_i-\widehat y_j\|_2^2.

    Label Spreading uses the degree-normalized energy ∑i,jWij∥y^i/Dii−y^j/Djj∥22\sum_{i,j}W_{ij}\|\widehat y_i/\sqrt{D_{ii}}-\widehat y_j/\sqrt{D_{jj}}\|_2^2, where Dii=∑jWijD_{ii}=\sum_jW_{ij}.

    Graph-regularization methods learn a parametric feature-based encoder Z=ENC⁡(X;ΘE)Z=\operatorname{ENC}(X;\Theta_E) and combine a supervised label loss on labeled nodes with the graph-smoothness loss on all nodes. ManiReg uses RKHS/SVM predictors, SemiEmb uses feed-forward neural networks and can regularize intermediate representations, and Neural Graph Machines extends the idea to architectures such as CNNs and LSTMs.

    Planetoid combines a feature-based component and a structural component, Z=[ZF∥ZC]Z=[Z^F\Vert Z^C]. It trains a classifier on labeled nodes while also predicting positive and negative context pairs using W^ij=zi⊤zj\widehat W_{ij}=z_i^\top z_j and a signed logistic loss. In contrast, supervised GNNs use both features and topology directly in the encoder, Z=ENC⁡(X,W;ΘE)Z=\operatorname{ENC}(X,W;\Theta_E), and decode node or graph labels from the propagated representations.

  8. Knowl 8 — Spectral, polynomial, and renormalized graph convolutions form a hierarchy of propagation models

    model/method

    For an undirected weighted graph with adjacency matrix WW and degree matrix DD, define the symmetric normalized Laplacian L~=I−D−1/2WD−1/2\widetilde L=I-D^{-1/2}WD^{-1/2}. Because L~\widetilde L is symmetric, it has an eigendecomposition L~=UΛU⊤\widetilde L=U\Lambda U^\top, where UU contains orthonormal eigenvectors and Λ\Lambda is diagonal with eigenvalues. For a node signal x∈R∣V∣x\in\mathbb{R}^{|V|}, the graph Fourier transform is U⊤xU^\top x.

    A spectral convolution applies a learned multiplier in this eigenbasis:

    x∗θ=Udiag⁡(U⊤θ)U⊤x.x*\theta=U\operatorname{diag}(U^\top\theta)U^\top x.

    Spectral CNNs learn filters directly on selected Laplacian eigenvectors. They are domain-dependent because the eigenbasis is tied to the training graph, and eigendecomposition is computationally expensive.

    Chebyshev Networks avoid explicit eigendecomposition by approximating spectral filters with degree-KK polynomials of a rescaled Laplacian:

    Hℓ+1=σ(∑k=1KTk(2L~λmax⁡(L~)−I)HℓΘkℓ),H^{\ell+1}=\sigma\left(\sum_{k=1}^{K}T_k\left(\frac{2\widetilde L}{\lambda_{\max}(\widetilde L)}-I\right)H^\ell\Theta_k^\ell\right),

    where HℓH^\ell is the layer-ℓ\ell node-feature matrix, TkT_k is the kkth Chebyshev polynomial, λmax⁡\lambda_{\max} is the largest Laplacian eigenvalue, Θkℓ\Theta_k^\ell is a trainable feature-mixing matrix, and σ\sigma is a nonlinearity. GCN further simplifies this construction and uses the renormalized propagation matrix

    A~=(D+I)−1/2(W+I)(D+I)−1/2,\widetilde A=(D+I)^{-1/2}(W+I)(D+I)^{-1/2},

    with layer update Hℓ+1=σ(A~HℓΘℓ)H^{\ell+1}=\sigma(\widetilde A H^\ell\Theta^\ell). ChebNet and GCN avoid explicit eigenvectors and therefore operate as local neighborhood-propagation methods.

  9. Knowl 9 — Spatial sampling and attention make graph convolutions more inductive and topology-adaptive

    model/method

    Spatial graph convolutions define propagation directly from graph neighborhoods rather than from a graph-specific eigenbasis. GraphSAGE samples a fixed number qq of neighbors for each node and applies a permutation-invariant aggregation function. For node viv_i, its layer update is

    H:,iℓ+1=σ(Θ1ℓH:,iℓ+Θ2ℓAGG⁡({H:,jℓ:vj∈Sample⁡(N(vi),q)})),H^{\ell+1}_{:,i}=\sigma\left(\Theta_1^\ell H^\ell_{:,i}+\Theta_2^\ell\operatorname{AGG}\left(\{H^\ell_{:,j}:v_j\in\operatorname{Sample}(N(v_i),q)\}\right)\right),

    where N(vi)N(v_i) is the neighbor set, Sample⁡\operatorname{Sample} selects qq neighbors, AGG⁡\operatorname{AGG} may be mean or max pooling, and Θ1ℓ,Θ2ℓ\Theta_1^\ell,\Theta_2^\ell are trainable matrices. Sampling reduces dependence on storing and processing the full graph and supports inductive application to unseen nodes or graphs.

    Graph Attention Networks (GAT) instead assign learned weights to all neighbors. Given a layer representation HℓH^\ell, a trainable feature transform BB, and trainable attention vectors b0,b1b_0,b_1, an unnormalized edge score is computed as

    g(Hℓ)=LeakyReLU⁡(HℓB⊤b0⊕b1⊤BHℓ⊤), g(H^\ell)=\operatorname{LeakyReLU}\left(H^\ell B^\top b_0\oplus b_1^\top BH^{\ell\top}\right),

    where ⊕\oplus broadcasts and adds the source- and target-node terms. Scores are normalized with a row-wise softmax and used to weight neighbor messages. GAT can use multiple attention heads and is applicable in both transductive and inductive settings.

    MoNet generalizes spatial patches through pseudo-coordinates such as node degree or geometric coordinates. It uses learned Gaussian kernels gk(Us)=exp⁡[−12(Us−μk)⊤Σk−1(Us−μk)]g_k(U^s)=\exp[-\tfrac12(U^s-\mu_k)^\top\Sigma_k^{-1}(U^s-\mu_k)], where UsU^s are pseudo-coordinates and μk,Σk\mu_k,\Sigma_k are learned kernel parameters.

  10. Knowl 10 — Hyperbolic graph convolutions combine inductive GNNs with geometry suited to hierarchy

    model/method

    Hyperbolic graph embeddings are useful for hierarchical graphs because the volume of a hyperbolic ball grows exponentially with radius, allowing tree-like structures to be represented with lower distortion than in Euclidean space. In the Poincaré ball of dimension dd, Bd={z∈Rd:∥z∥2<1}\mathbb B^d=\{z\in\mathbb R^d:\|z\|_2<1\}, the distance between embeddings zi,zj∈Bdz_i,z_j\in\mathbb B^d is

    dB(zi,zj)=arcosh⁡(1+2∥zi−zj∥22(1−∥zi∥22)(1−∥zj∥22)). d_{\mathbb B}(z_i,z_j)=\operatorname{arcosh}\left(1+\frac{2\|z_i-z_j\|_2^2}{(1-\|z_i\|_2^2)(1-\|z_j\|_2^2)}\right).

    Hyperbolic Graph Convolutional Neural Networks (HGCN) and Hyperbolic Graph Neural Networks (HGNN) extend neighborhood aggregation to this non-Euclidean space. At each convolution step, node embeddings are mapped from hyperbolic space to the Euclidean tangent space at the origin, ordinary Euclidean graph convolution is performed there, and the result is mapped back to hyperbolic space. This construction preserves the inductive, feature-driven nature of GNNs while allowing the embedding geometry to represent hierarchy.

    The paper identifies three limitations of non-Euclidean graph learning: numerical precision problems near the boundary of the Poincaré ball, the need for Riemannian rather than ordinary Euclidean optimization, and the lack of a generally reliable procedure for selecting the appropriate geometry for a given graph. The paper therefore treats geometry selection and stronger theoretical guarantees as open problems rather than settled capabilities.

Coverage note — The exact method-by-method training-complexity table, application catalog, open-source library details, and several individual model variants were omitted to prioritize the load-bearing GraphEDM/GCF frameworks, taxonomy, representative objectives, and architectural distinctions.

References

  1. 1.Muad Abu-Ata and Feodor F Dragan. Metric tree-like structures in real-world networks: an empirical study. Networks, 67(1):49–68, 2016.
  2. 2.Sami Abu-El-Haija, Bryan Perozzi, and Rami Al-Rfou. Learning edge representations via low-rank asymmetric projections. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM ’17, page 1787–1796, 2017.
  3. 3.Sami Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alexander A Alemi. Watch your step: Learning node embeddings via graph attention. In Advances in Neural Information Processing Systems, pages 9180–9190, 2018.
  4. 4.Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learning, pages 21–29, 2019.
  5. 5.Aaron B Adcock, Blair D Sullivan, and Michael W Mahoney. Tree-like structure in large social and information networks. In 2013 IEEE 13th International Conference on Data Mining, pages 1–10. IEEE, 2013.
  6. 6.Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander J Smola. Distributed large-scale natural graph factorization. In Proceedings of the 22nd international conference on World Wide Web, pages 37–48. ACM, 2013.
  7. 7.Rami Al-Rfou, Dustin Zelle, and Bryan Perozzi. Ddgk: Learning graph representations for deep divergence graph kernels. Proceedings of the 2019 World Wide Web Conference on World Wide Web, 2019.
  8. 8.Gregorio Alanis-Lobato, Pablo Mier, and Miguel A Andrade-Navarro. Efficient embedding of complex networks to hyperbolic space via their laplacian. Scientific reports, 6:30108, 2016.
  9. 9.Luis B Almeida. A learning rule for asynchronous perceptrons with feedback in a combinatorial environment. In Proceedings, 1st First International Conference on Neural Networks, volume 2, pages 609–618. IEEE, 1987.
  10. 10.Ivana Balazevic, Carl Allen, and Timothy Hospedales. Multi-relational poincaré graph embeddings. In Advances in Neural Information Processing Systems, pages 4463–4473, 2019.
  11. 11.Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in Neural Information Processing Systems, pages 4502–4510, 2016.
  12. 12.Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018.
  13. 13.Gary Becigneul and Octavian-Eugen Ganea. Riemannian adaptive optimization methods. In International Conference on Learning Representations, 2018.
  14. 14.Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pages 585–591, 2002.
  15. 15.Mikhail Belkin and Partha Niyogi. Semi-supervised learning on riemannian manifolds. Machine learning, 56(1-3):209–239, 2004.
  16. 16.Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research, 7(Nov):2399–2434, 2006.
  17. 17.Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE transactions on pattern analysis and machine intelligence, 35(8):1798–1828, 2013.
  18. 18.Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d’horizon. arXiv preprint arXiv:1811.06128, 2018.
  19. 19.Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprint arXiv:1706.02263, 2017.
  20. 20.Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pages 874–883. PMLR, 2020.
  21. 21.Silvere Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Transactions on Automatic Control, 58(9):2217–2229, 2013.
  22. 22.Davide Boscaini, Jonathan Masci, Emanuele Rodolà, and Michael Bronstein. Learning shape correspondence with anisotropic convolutional neural networks. In Advances in Neural Information Processing Systems, pages 3189–3197, 2016.
  23. 23.Avishek Joey Bose and William Hamilton. Compositional fairness constraints for graph embeddings. arXiv preprint arXiv:1905.10674, 2019.
  24. 24.Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18–42, 2017.
  25. 25.Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally connected networks on graphs international conference on learning representations (iclr2014). CBLS, April, 2014.
  26. 26.Thang D Bui, Sujith Ravi, and Vivek Ramavajjala. Neural graph learning: Training neural networks using graphs. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 64–71, 2018.
  27. 27.Hongyun Cai, Vincent W Zheng, and Kevin Chang. A comprehensive survey of graph embedding: problems, techniques and applications. IEEE Transactions on Knowledge and Data Engineering, 2018.
  28. 28.Catalina Cangea, Petar Velickovic, Nikola Jovanovic, Thomas Kipf, , and Pietro Lio. Towards sparse hierarchical graph classifiers. In arXiv:1811.01287, 2018.
  29. 29.Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pages 891–900. ACM, 2015.
  30. 30.Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In AAAI, pages 1145–1152, 2016.
  31. 31.Benjamin Paul Chamberlain, James Clough, and Marc Peter Deisenroth. Neural embeddings of graphs in hyperbolic space. arXiv preprint arXiv:1705.10359, 2017.
  32. 32.Ines Chami, Zhitao Ying, Christopher Ré, and Jure Leskovec. Hyperbolic graph convolutional neural networks. In Advances in Neural Information Processing Systems, pages 4869–4880, 2019.
  33. 33.Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low-dimensional hyperbolic knowledge graph embeddings. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
  34. 34.Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. Semi-supervised learning (chapelle, o. et al., eds.; 2006)[book reviews]. IEEE Transactions on Neural Networks, 20 (3):542–542, 2009.
  35. 35.Dexiong Chen, Laurent Jacob, and Julien Mairal. Convolutional kernel networks for graph-structured data. In International Conference on Machine Learning, 2020.
  36. 36.Haochen Chen, Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. A tutorial on network embeddings. arXiv preprint arXiv:1808.02590, 2018a.
  37. 37.Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. Harp: Hierarchical representation learning for networks. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018b.
  38. 38.Haochen Chen, Xiaofei Sun, Yingtao Tian, Bryan Perozzi, Muhao Chen, and Steven Skiena. Enhanced network embeddings via exploiting edge labels. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM ’18, page 1579–1582, 2018c.
  39. 39.Wei Chen, Wenjie Fang, Guangda Hu, and Michael W Mahoney. On the hyperbolicity of small-world and treelike random graphs. Internet Mathematics, 9(4):434–491, 2013.
  40. 40.Zhengdao Chen, Joan Bruna Estrach, and Lisha Li. Supervised community detection with line graph neural networks. In 7th International Conference on Learning Representations, ICLR 2019, 2019a.
  41. 41.Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pages 15894–15902, 2019b.
  42. 42.Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2019. URL https://arxiv.org/pdf/1905.07953.pdf.
  43. 43.Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. On the properties of neural machine translation: Encoder-decoder approaches. arXiv preprint arXiv:1409.1259, 2014.
  44. 44.Michael AA Cox and Trevor F Cox. Multidimensional scaling. In Handbook of data visualization, pages 315–347. Springer, 2008.
  45. 45.Daniel Fernando Daza Cruz, Thomas Kipf, and Max Welling. A modular framework for unsupervised graph representation learning. 2019.
  46. 46.Nicola De Cao and Thomas Kipf. Molgan: An implicit generative model for small molecular graphs. arXiv preprint arXiv:1805.11973, 2018.
  47. 47.Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. Commun. ACM, page 107–113, 2008. doi: 10.1145/1327452.1327492. URL https://doi.org/10.1145/1327452.1327492.
  48. 48.Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan J. Shusterman, , and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. In J. Med. Chem., pages 786–797, 1991.
  49. 49.Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3844–3852, 2016.
  50. 50.J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPR09, 2009.
  51. 51.Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, 2019.
  52. 52.David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pages 2224–2232, 2015.
  53. 53.Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
  54. 54.Daniel C Elton, Zois Boukouvalas, Mark D Fuge, and Peter W Chung. Deep learning for molecular design—a review of the state of the art. Molecular Systems Design & Engineering, 4(4):828–849, 2019.
  55. 55.Alessandro Epasto and Bryan Perozzi. Is a single embedding enough? learning node representations that capture multiple social contexts. In The World Wide Web Conference, WWW ’19, page 394–404, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366748. doi: 10.1145/3308558.3313660. URL https://doi.org/10.1145/3308558.3313660.
  56. 56.Alessandro Epasto, Silvio Lattanzi, and Renato Paes Leme. Ego-splitting framework: From non-overlapping to overlapping clusters. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’17, page 145–154, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450348874. doi: 10.1145/3097983.3098054. URL https://doi.org/10.1145/3097983.3098054.
  57. 57.Qingyuan Feng, Evgenia Dueva, Artem Cherkasov, and Martin Ester. Padme: A deep learning-based framework for drug-target interaction prediction. arXiv preprint arXiv:1807.09741, 2018.
  58. 58.Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.02428, 2019.
  59. 59.Hongyang Gao and Shuiwang Ji. Graph u-nets. In Proceedings of the 36th International Conference on Machine Learning, 2019.
  60. 60.Victor Garcia and Joan Bruna. Few-shot learning with graph neural networks. In International Conference on Learning Representations (ICLR), 2018.
  61. 61.Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprint arXiv:2002.06157, 2020.
  62. 62.Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 1263–1272. JMLR. org, 2017.
  63. 63.Primož Godec. https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007, 2018.
  64. 64.Hila Gonen and Yoav Goldberg. Lipstick on a pig: Debiasing methods cover up systematic gender biases in word embeddings but do not remove them. arXiv preprint arXiv:1903.03862, 2019.
  65. 65.Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pages 729–734. IEEE, 2005.
  66. 66.Palash Goyal and Emilio Ferrara. Gem: a python package for graph embedding methods. Journal of Open Source Software, 3(29):876, 2018a.
  67. 67.Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems, 151:78–94, 2018b.
  68. 68.Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864. ACM, 2016.
  69. 69.Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International Conference on Machine Learning, pages 2434–2444, 2019.
  70. 70.Albert Gu, Frederic Sala, Beliz Gunel, and Christopher Ré. Learning mixed-curvature representations in product spaces. International Conference on Learning Representations, 2018.
  71. 71.Jonathan Halcrow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. Grale: Designing networks for graph learning. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’20, page 2523–2532, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450379984. doi: 10.1145/3394486.3403302. URL https://doi.org/10.1145/3394486.3403302.
  72. 72.Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024–1034, 2017a.
  73. 73.William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint arXiv:1709.05584, 2017b.
  74. 74.David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):129–150, 2011.
  75. 75.Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv:1506.05163, 2015.
  76. 76.Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):1735–1780, 1997.
  77. 77.Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687, 2020.
  78. 78.Di Huang, Zihao He, Yuzhong Huang, Kexuan Sun, Sami Abu-El-Haija, Bryan Perozzi, Kristina Lerman, Fred Morstatter, and Aram Galstyan. Graph embedding with personalized context distribution. In Companion Proceedings of the Web Conference 2020, WWW ’20, page 655–661, 2020.
  79. 79.Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In International Conference on Machine Learning, 2018.
  80. 80.Ian Jolliffe. Principal component analysis. In International encyclopedia of statistical science, pages 1094–1096. Springer, 2011.
  81. 81.Edmond Jonckheere, Poonsuk Lohsoonthorn, and Francis Bonahon. Scaled gromov hyperbolic graphs. Journal of Graph Theory, 2008.
  82. 82.Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pages 6348–6358, 2017.
  83. 83.Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016a.
  84. 84.Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016b.
  85. 85.Robert Kleinberg. Geographic routing using hyperbolic space. In IEEE INFOCOM 2007-26th IEEE International Conference on Computer Communications, pages 1902–1909. IEEE, 2007.
  86. 86.Ioannis Konstas, Vassilios Stathopoulos, and Joemon M. Jose. On social networks and collaborative recommendation. In Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pages 195–202, 2009.
  87. 87.N. M. Kriege, F. D. Johansson, and C. Morris. A survey on graph kernels. In Applied Network Science, pages 1–42, 2020.
  88. 88.Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Marián Boguná. Hyperbolic geometry of complex networks. Physical Review E, 82(3):036106, 2010.
  89. 89.Joseph B Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29(1):1–27, 1964.
  90. 90.Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, Tom Duerig, and Vittorio Ferrari. The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale. IJCV, 2020.
  91. 91.Luis Lamb, Artur Garcez, Marco Gori, Marcelo Prates, Pedro Avelar, and Moshe Vardi. Graph neural networks meet neural-symbolic computing: A survey and perspective. arXiv preprint arXiv:2003.00330, 2020.
  92. 92.Matthew Le, Stephen Roller, Laetitia Papaxanthos, Douwe Kiela, and Maximilian Nickel. Inferring concept hierarchies from text corpora via hyperbolic embeddings. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3231–3241, 2019.
  93. 93.Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hubbard, and Lawrence D Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, 1(4):541–551, 1989.
  94. 94.Junhyun Lee, Inyeop Lee, , and Jaewoo Kang. Self-attention graph pooling. In International Conference on Machine Learning, 2019.
  95. 95.Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. PyTorch-BigGraph: A Large-scale Graph Embedding System. In Proceedings of the 2nd SysML Conference, Palo Alto, CA, USA, 2019.
  96. 96.Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization. In Advances in neural information processing systems, pages 2177–2185, 2014.
  97. 97.Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493, 2015.
  98. 98.Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:1803.03324, 2018.
  99. 99.David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019–1031, 2007.
  100. 100.Qi Liu, Miltiadis Allamanis, Marc Brockschmidt, and Alexander Gaunt. Constrained graph variational autoencoders for molecule design. In Advances in Neural Information Processing Systems, pages 7795–7804, 2018.
  101. 101.Qi Liu, Maximilian Nickel, and Douwe Kiela. Hyperbolic graph neural networks. In Advances in Neural Information Processing Systems, pages 8228–8239, 2019.
  102. 102.Andreas Loukas. What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:1907.03199, 2019.
  103. 103.Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(Nov):2579–2605, 2008.
  104. 104.Elan Sopher Markowitz, Keshav Balasubramanian, Mehrnoosh Mirtaheri, Sami Abu-El-Haija, Bryan Perozzi, Greg Ver Steeg, and Aram Galstyan. Graph traversal with tensor functionals: A meta-algorithm for scalable learning. In International Conference on Learning Representations, 2021.
  105. 105.Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.
  106. 106.Jonathan Masci, Davide Boscaini, Michael Bronstein, and Pierre Vandergheynst. Geodesic convolutional neural networks on riemannian manifolds. In Proceedings of the IEEE international conference on computer vision workshops, pages 37–45, 2015.
  107. 107.Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine learning. arXiv preprint arXiv:1908.09635, 2019.
  108. 108.Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pages 3111–3119, 2013.
  109. 109.Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 5115–5124, 2017.
  110. 110.Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602–4609, 2019.
  111. 111.Alessandro Muscoloni, Josephine Maria Thomas, Sara Ciucci, Ginestra Bianconi, and Carlo Vittorio Cannistraci. Machine learning meets complex networks via coalescent embedding in the hyperbolic space. Nature communications, 8(1):1–19, 2017.
  112. 112.Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. In Advances in neural information processing systems, pages 6338–6347, 2017.
  113. 113.Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry. In International Conference on Machine Learning, pages 3779–3788, 2018.
  114. 114.Alex Nowak, Soledad Villar, Afonso S Bandeira, and Joan Bruna. Revised note on learning algorithms for quadratic assignment with graph neural networks. arXiv preprint arXiv:1706.07450, 2017.
  115. 115.Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserving graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1105–1114. ACM, 2016.
  116. 116.John Palowitch and Bryan Perozzi. Monet: Debiasing graph embeddings via the metadata-orthogonal training unit. arXiv preprint arXiv:1909.11793, 2019.
  117. 117.Fragkiskos Papadopoulos, Maksim Kitsak, M Angeles Serrano, Marián Boguná, and Dmitri Krioukov. Popularity versus similarity in growing networks. Nature, 489(7417):537–540, 2012.
  118. 118.Fragkiskos Papadopoulos, Constantinos Psomas, and Dmitri Krioukov. Network mapping by replaying hyperbolic growth. IEEE/ACM Transactions on Networking, 23(1):198–211, 2014.
  119. 119.Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph Representation Learning via Graphical Mutual Information Maximization. In Proceedings of The Web Conference, 2020. doi: https://doi.org/10.1145/3366423.3380112.
  120. 120.Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532–1543, 2014.
  121. 121.Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710. ACM, 2014.
  122. 122.Fernando J Pineda. Generalization of back propagation to recurrent and higher order neural networks. In Neural information processing systems, pages 602–611, 1988.
  123. 123.Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve np-complete problems: A graph neural network for decision tsp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4731–4738, 2019.
  124. 124.Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 459–467, 2018.
  125. 125.Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Chi Wang, Kuansan Wang, and Jie Tang. Netsmf: Large-scale network embedding as sparse matrix factorization. In The World Wide Web Conference, WWW ’19, page 1509–1520, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450366748. doi: 10.1145/3308558.3313446. URL https://doi.org/10.1145/3308558.3313446.
  126. 126.Matthew Ragoza, Joshua Hochuli, Elisa Idrobo, Jocelyn Sunseri, and David Ryan Koes. Protein–ligand scoring with convolutional neural networks. Journal of Chemical Information and Modeling, 57(4):942–957, 2017. doi: 10.1021/acs.jcim.6b00740. URL https://doi.org/10.1021/acs.jcim.6b00740. PMID: 28368587.
  127. 127.Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2323–2326, 2000.
  128. 128.Benedek Rozemberczki, Ryan Davies, Rik Sarkar, and Charles Sutton. Gemsec: Graph embedding with self clustering. In Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM ’19, page 65–72, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450368681. doi: 10.1145/3341161.3342890. URL https://doi.org/10.1145/3341161.3342890.
  129. 129.Benedek Rozemberczki, Peter Englert, Amol Kapoor, Martin Blais, and Bryan Perozzi. Pathfinder discovery networks for neural message passing. In Proceedings of the Web Conference 2021, WWW ’21, page 2547–2558, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383127. doi: 10.1145/3442381.3449882. URL https://doi.org/10.1145/3442381.3449882.
  130. 130.Frederic Sala, Chris De Sa, Albert Gu, and Christopher Re. Representation tradeoffs for hyperbolic embeddings. In International Conference on Machine Learning, pages 4460–4469, 2018.
  131. 131.Rik Sarkar. Low distortion delaunay embedding of trees in hyperbolic plane. In International Symposium on Graph Drawing, pages 355–366. Springer, 2011.
  132. 132.Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20 (1):61–80, 2009.
  133. 133.Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pages 593–607. Springer, 2018.
  134. 134.Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L Dill. Learning a sat solver from single-bit supervision. arXiv preprint arXiv:1802.03685, 2018.
  135. 135.Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868, 2018.
  136. 136.Martin Simonovsky and Nikos Komodakis. Graphvae: Towards generation of small graphs using variational autoencoders. arXiv preprint arXiv:1802.03480, 2018.
  137. 137.Koustuv Sinha, Shagun Sodhani, Joelle Pineau, and William L Hamilton. Evaluating logical generalization in graph neural networks. arXiv preprint arXiv:2003.06560, 2020.
  138. 138.Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=SJxzFySKwH.
  139. 139.Chris Stark, Bobby-Joe Breitkreutz, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, and Mike Tyers. Biogrid: a general repository for interaction datasets. Nucleic acids research, 34(suppl 1):D535–D539, 2006.
  140. 140.Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pages 1067–1077. International World Wide Web Conferences Steering Committee, 2015.
  141. 141.Joshua B Tenenbaum, Vin De Silva, and John C Langford. A global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319–2323, 2000.
  142. 142.Alexandru Tifrea, Gary Becigneul, and Octavian-Eugen Ganea. Poincare glove: Hyperbolic word embeddings. In International Conference on Learning Representations, 2018.
  143. 143.Anton Tsitsulin, Davide Mottin, Panagiotis Karras, Alexander Bronstein, and Emmanuel Müller. Netlsd: Hearing the shape of a graph. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’18, page 2347–2356, 2018.
  144. 144.Anton Tsitsulin, Marina Munkhoeva, and Bryan Perozzi. Just slaq when you approximate: Accurate spectral distances for web-scale graphs. In Proceedings of The Web Conference 2020, WWW ’20, page 2697–2703, 2020a.
  145. 145.Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. arXiv preprint arXiv:2006.16904, 2020b.
  146. 146.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998–6008, 2017.
  147. 147.Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
  148. 148.Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
  149. 149.Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1539–1548, 2019.
  150. 150.Pascal Vincent, Hugo Larochelle, Isabelle Lajoie, Yoshua Bengio, and Pierre-Antoine Manzagol. Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion. Journal of machine learning research, 11(Dec):3371–3408, 2010.
  151. 151.S. V. N. Vishwanathan, N. N. Schraudolph, R. Kondor, and K. M Borgwardt. Graph kernels. In Journal of Machine Learning Research, pages 1201–1242, 2010.
  152. 152.Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1225–1234. ACM, 2016.
  153. 153.Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, et al. Deep graph library: Towards efficient and scalable deep learning on graphs. arXiv preprint arXiv:1909.01315, 2019.
  154. 154.Jason Weston, Frédéric Ratle, and Ronan Collobert. Deep learning via semi-supervised embedding. In Proceedings of the 25th international conference on Machine learning, pages 1168–1175. ACM, 2008.
  155. 155.Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596, 2019.
  156. 156.Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018.
  157. 157.Pinar Yanardag and S.V.N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365–1374. Association for Computing Machinery, 2015.
  158. 158.Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on International Conference on Machine Learning-Volume 48, pages 40–48. JMLR. org, 2016.
  159. 159.Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018a.
  160. 160.Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 4800–4810. Curran Associates, Inc., 2018b. URL http://papers.nips.cc/paper/7729-hierarchical-graph-representation-learning-with-differentiable-pooling.pdf.
  161. 161.Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrnn: A deep generative model for graphs. arXiv preprint arXiv:1802.08773, 2018.
  162. 162.Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. arXiv preprint arXiv:1906.04817, 2019.
  163. 163.Tao Yu and Christopher M De Sa. Numerically accurate hyperbolic embeddings using tiling-based models. In Advances in Neural Information Processing Systems, pages 2023–2033, 2019.
  164. 164.Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Network representation learning: A survey. IEEE Transactions on Big Data, 2018a.
  165. 165.Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018b.
  166. 166.Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. arXiv preprint arXiv:1812.04202, 2018c.
  167. 167.Dengyong Zhou, Olivier Bousquet, Thomas N Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. In Advances in neural information processing systems, pages 321–328, 2004.
  168. 168.Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv:1812.08434, 2018.
  169. 169.Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. 2002.

Citation

MLA
Chami, I., et al. “Machine Learning on Graphs: A Model and Comprehensive Taxonomy”. Journal of Machine Learning Research, vol. 23, no. 89, 2022, pp. 1–4, https://www.jmlr.org/papers/v23/20-852.html.
APA
Chami, I., Abu-El-Haija, S., Perozzi, B., Ré, C., & Murphy, K. (2022). Machine Learning on Graphs: A Model and Comprehensive Taxonomy. Journal of Machine Learning Research, 23(89), 1–64. https://www.jmlr.org/papers/v23/20-852.html
Chicago
Chami, I., S. Abu-El-Haija, B. Perozzi, C. Ré, and K. Murphy. 2022. “Machine Learning on Graphs: A Model and Comprehensive Taxonomy”. Journal of Machine Learning Research 23 (89): 1–64. https://www.jmlr.org/papers/v23/20-852.html.
Harvard
Chami, I. et al. (2022) “Machine Learning on Graphs: A Model and Comprehensive Taxonomy”, Journal of Machine Learning Research, 23(89), pp. 1–64. Available at: https://www.jmlr.org/papers/v23/20-852.html.
Vancouver
1. Chami I, Abu-El-Haija S, Perozzi B, Ré C, Murphy K (2022) Machine Learning on Graphs: A Model and Comprehensive Taxonomy. Journal of Machine Learning Research 23:1–64

BibTeX

@article{JMLR:v23:20-852,
  author  = {Ines Chami and Sami Abu-El-Haija and Bryan Perozzi and Christopher Ré and Kevin Murphy},
  title   = {Machine Learning on Graphs: A Model and Comprehensive Taxonomy},
  journal = {Journal of Machine Learning Research},
  year    = {2022},
  volume  = {23},
  number  = {89},
  pages   = {1--64},
  url     = {http://jmlr.org/papers/v23/20-852.html}
}
Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/