Source-linked AI summary
Learning Graph Representations with Embedding Propagation
Alberto Garcia-Duran, Mathias Niepert
TL;DR
Graph representation learning spans settings with diverse graph structures, node attributes, and limited labels. EP addresses this by propagating label representations and reconstruction-loss gradients between neighboring nodes, learning embeddings for multiple label types. EP-B is competitive with and often outperforms state-of-the-art methods while using fewer parameters and/or hyperparameters, and the framework supports directed graphs and efficient neighbor sampling.
Problem
Graph-structured data supports diverse applications and learning tasks, including settings with few labeled examples that motivate unsupervised and semi-supervised methods.
Method
EP learns label and node representations by exchanging label representations and reconstruction-loss gradients between neighboring nodes.
Results
EP-B is competitive with and often outperforms state-of-the-art methods while using fewer parameters and/or hyperparameters.
Takeaways & Limitations
EP combines representations from multiple label types into joint vertex embeddings and remains applicable when edge directions are taken into account.
Takeaways & Limitations
Directly minimizing the initial objective can lead to degenerate solutions.
Abstract
from arXiv · showhide
We propose Embedding Propagation (EP), an unsupervised learning framework for graph-structured data. EP learns vector representations of graphs by passing two types of messages between neighboring nodes. Forward messages consist of label representations such as representations of words and other attributes associated with the nodes. Backward messages consist of gradients that result from aggregating the label representations and applying a reconstruction loss. Node representations are finally computed from the representation of their labels. With significantly fewer parameters and hyperparameters an instance of EP is competitive with and often outperforms state of the art unsupervised and semi-supervised learning methods on a range of benchmark data sets.
1 Introduction
Graph-structured data supports many learning tasks and often has few labeled examples, motivating unsupervised representation learning. EP learns graph embeddings by exchanging messages between neighboring nodes and can incorporate multiple label types.
- Graph-structured data appears in social networks, bioinformatics, natural language processing, and relational knowledge bases.
- Common graph-learning problems include network classification, statistical relational learning, link prediction, and anomaly detection.
- Graph-based unsupervised and semi-supervised methods are useful when data sets contain few labeled examples.
- EP learns graph embeddings by passing messages between neighboring nodes, a process related to power iteration, label propagation, isomorphism testing, and spectral clustering.
- EP incorporates different label types, including text and images, making it a framework for learning with multi-modal data.
2 Previous Work
Earlier graph-embedding methods often construct affinity graphs and solve optimization problems that can become intractable for large graphs. EP differs from related neural graph methods through its unsupervised objective and treatment of multiple label types.
- Many embedding methods, including MDS, Laplacian Eigenmap, IsoMap, and LLE, first construct an affinity graph and then embed it.
- The closed-form optimization problems used by many embedding approaches can be intractable for large graphs.
- GNNs compute node embeddings by backpropagating supervised-loss gradients after recursive propagation reaches convergence.
- DEEPWALK learns node embeddings by treating random walks as sentences and applying a skip-gram model.
3 Embedding Propagation
Embedding Propagation learns label and node representations by exchanging forward label embeddings and backward reconstruction gradients between neighboring vertices. Its EP-B instance aggregates label embeddings, reconstructs neighborhood information with a margin-based loss, and forms node vectors by concatenating label-type representations.
- General framework: EP represents each label with a differentiable embedding function and learns these representations by passing messages along graph edges.The framework supports label-type-specific embedding functions, including linear functions for text and more complex functions for images.
- General framework: For each label type, EP aggregates a vertex’s labels and its neighbors’ labels into an embedding and a reconstruction using differentiable functions.The reconstruction is computed from neighboring label embeddings, while the vertex embedding is computed from its own labels.
- Incomplete data: EP can assign unique dummy labels to missing label types, allowing representations for nodes with incomplete data.The learned dummy-label representations can contribute to the node representation itself.
- EP-B: EP-B uses mean aggregation, a margin-based ranking loss, and concatenation of label-type embeddings to produce vertex representations for downstream tasks.The resulting vectors can be used for vertex classification, link prediction, and related graph-learning problems.
- Learning procedure: EP minimizes distances between current and reconstructed label-type embeddings, sending gradients back to update neighboring and local label embeddings.These gradients provide the backward messages used during unsupervised learning.
- Learning procedure: Directly minimizing the basic distance objective can lead to degenerate solutions, motivating the margin-based ranking loss.The ranking objective compares reconstruction distance for the target vertex with distance to a different vertex’s label embedding.
4 Formal Analysis
EP’s formal analysis characterizes iteration cost and model size, then relates EP-B to LLE, CBOW, and multi-relational embedding models. The framework supports scalable message passing and edge-type-dependent reconstruction choices.
- 4.1 Computational and Model Complexity: One learning iteration has worst-case complexity O(k|V|τ(labmaxdegmax)), where k is the number of label types and τ measures reconstruction-function cost.The bound uses the maximum labels per type and maximum graph degree.
- 4.1 Computational and Model Complexity: For attribute-free graphs, EP requires O(|V|τ(degmax)) time per iteration and becomes O(|V|degmax) when reconstruction is linear.Under this condition, average complexity is also linear in average node degree.
- 4.1 Computational and Model Complexity: Neighbor sampling can cap EP’s worst-case message-exchange cost by limiting each node to at most κ sampled neighbors.The paper evaluates different sampling scenarios experimentally.
- 4.1 Computational and Model Complexity: For attribute-free graphs, EP-B has d|V| parameters and only two hyperparameters: embedding size d and margin γ.The parameter and hyperparameter counts depend more generally on the reconstruction, loss, and label sets.
- 4.2 Comparison to Existing Models: EP-B differs from LLE because it learns label embeddings and averages input embeddings without LLE’s separately learned per-vertex weights.LLE directly learns vertex embeddings instead.
- 4.2 Comparison to Existing Models: LLE is restricted to graphs with few neighbors and relies on constrained closed-form optimization that is infeasible for large graphs.These constraints distinguish its scalability profile from EP-B’s message-passing formulation.
- 4.2 Comparison to Existing Models: For citation graphs with word labels, EP-B resembles CBOW, but a word’s context is determined by neighboring vertices rather than a word sequence.The comparison concerns EP-B’s learning of word embeddings from graph neighborhoods.
- 4.2 Comparison to Existing Models: In multi-relational graphs, reconstruction functions can depend on edge type, linking the resulting formulation to models such as TRANSE.The relation representation r(u,v) can encode the edge type, while hi(v) may average node-identity label embeddings.
5 Experiments
EP-B is evaluated across six benchmark graph datasets for node classification, representation quality, inductive transfer, directed graphs, and neighbor-sampling efficiency. It generally performs strongly, including outperforming existing approaches on attributed datasets while retaining efficient training under neighbor sampling.
- 5.1 Set-up: EP-B is evaluated on six benchmark datasets spanning multi-label and single-label node-classification settings.The benchmarks are BlogCatalog, PPI, POS, Cora, Citeseer, and Pubmed.
- 5.1 Set-up: The experiments compare EP-B with DEEPWALK, LINE, NODE2VEC, PLANETOID, GCN, WVRN, and MAJORITY using standardized evaluation procedures.The study reruns experiments for all methods, uses shared train/validation/test splits, and reports means and standard deviations over 10 runs.
- 5.2 Results: EP-B tends to achieve the best F1 scores on BlogCatalog, POS, and PPI in the transductive setting, while using fewer parameters and hyperparameters to tune.Its F1 scores are significantly higher than those of WVRN and MAJORITY.
- 5.2 Results: EP-B significantly outperforms existing approaches on Cora, Citeseer, and Pubmed in both transductive and inductive settings, except that GCN has higher transductive accuracy on Cora.Its transductive and inductive F1 scores are very similar on these datasets, supporting its use in the inductive setting.
- 5.2 Results: Combining node-identity and word labels improves Cora embedding clustering, raising the Silhouette score from 0.008 and 0.107 individually to 0.158 jointly.The visualization uses 128-dimensional EP-B embeddings reduced with t-SNE.
- 5.2 Results: Accounting for edge direction significantly worsens DEEPWALK performance but does not significantly change EP-B accuracy.EP-B therefore remains applicable when messages follow directed edges.
- 5.2 Results: For densely connected graphs, κ = 50 makes average loss almost identical to using all neighbors while reducing training time per epoch from 20s to less than 1s.Smaller κ values produce significantly higher loss.
6 Conclusion and Future Work
EP is an unsupervised framework that learns joint label and node embeddings by exchanging messages between graph nodes. Its EP-B instance is competitive with or often outperforms state-of-the-art methods with fewer parameters and/or hyperparameters, while future work extends the framework to supervised, multimodal, distributed, and multi-relational settings.
- Conclusion: EP learns label and node representations by exchanging messages between neighboring nodes and supports arbitrary label types.Examples include node identities, text, and movie genres.
- Conclusion: EP-B is competitive with and often outperforms state-of-the-art methods while using fewer parameters and/or hyperparameters.
- Conclusion: EP can combine different label types into joint vertex embeddings, supporting multimodal graph representation learning.The framework is described as incorporating label types such as text and images.
- Future Work: Future work includes combining EP with multitask learning, incorporating image and sequence data, integrating it with distributed graph processing, and applying it to multi-relational graphs.