Co-embedding of Nodes and Edges with Graph Neural Networks

Xiaodong Jiang, Ronghang Zhu, Pengsheng Ji, Sheng Li

Abstract

Traditional Graph Convolutional Networks (GCNs) are primarily node-centric, often neglecting the rich information embedded within graph edges. This paper introduces CensNet (Convolution with Edge-Node Switching), a novel framework that treats edges as first-class citizens. By utilizing line graphs to alternate the roles of nodes and edges, CensNet learns latent representations for both components simultaneously. Experimental results across citation networks and chemical datasets demonstrate that CensNet achieves state-of-the-art performance, particularly in tasks where edge features are critical.

Introduction

Most existing GNN architectures excel at aggregating features from a node's neighborhood but treat edges merely as binary indicators of connectivity. However, real-world graphs are rich with edge-level data. In social networks, edges represent relationship types or friendship duration; in chemistry, they represent specific chemical bonds with unique properties. Ignoring these features leads to suboptimal embeddings. The fundamental challenge is mathematically integrating these disparate feature sets into a unified convolution operation that allows nodes and edges to mutually enrich one another during training.

Methodology: Node-Edge Switching

The core innovation of CensNet is the Node-Edge Switching mechanism, which is inspired by the concept of Line Graphs.

  1. The Line Graph ($L(G)$): In a line graph, every edge in the original graph $G$ becomes a node. If two edges in $G$ share a vertex, their corresponding nodes in $L(G)$ are connected.
  2. Dual Propagation Rules: CensNet alternates between two types of layers:
  3. Node Layer: Updates node embeddings by incorporating information from both current node features and associated edge features.
  4. Edge Layer: Updates edge embeddings by treating the edges as nodes (via the line graph) and incorporating information from the connected nodes.
The CensNet architecture alternating between node and edge layers to facilitate mutual enrichment of features.

This "switching" allows the model to use the output of a node convolution to improve edge representations, and vice versa, in a mutually beneficial loop. While implemented here with a spectral-based convolution, the framework is general enough to support other kernels like GraphSAGE or GAT.

Unsupervised Learning with CensNet-VAE

Beyond supervised tasks, the framework extends to unsupervised link prediction through CensNet-VAE. This variant combines the CensNet architecture with a Variational Autoencoder (VAE) structure, allowing the model to learn robust embeddings in an unsupervised manner by reconstructing the graph topology and features.

The CensNet-VAE architecture designed for unsupervised tasks like link prediction.

Experimental Evaluation

The model was evaluated on benchmark datasets across four distinct tasks:

  • Citation Networks (Cora, Citeseer, PubMed): For semi-supervised node classification. CensNet achieved 79.4% accuracy on Cora with only 3% training data, outperforming standard GCNs (74.0%).
  • Chemistry (Tox21, Lipophilicity): For graph classification and regression. On the Lipophilicity task, CensNet improved upon standard GCNs by 5% to 15% in terms of RMSE, proving that bond (edge) features are critical in molecular modeling.

Key Insights and Discussion

  • Edges as Nodes: By transforming a graph into its line graph, highly optimized node-convolution machinery can be applied to edges without inventing entirely new operations.
  • Sparsity and Scalability: CensNet maintains the sparsity of the original graph using a binary transformation matrix, though the switching operation adds roughly 40% computational overhead compared to standard GCNs.
  • Architecture Depth: Similar to other GNNs, CensNet performs best with "shallow but wide" architectures, as excessive depth can introduce noise and lead to over-smoothing.

Conclusion and Future Work

CensNet successfully integrates edge features into the graph convolution process, setting a new standard for tasks where edge information is vital. Future research will focus on scaling the line graph transformation to graphs with millions of nodes and extending the framework to dynamic graphs where topology evolves over time.

Summary updated

BibTeX
@article{jiang2023co,
  author = {Xiaodong Jiang and Ronghang Zhu and Pengsheng Ji and Sheng Li},
  title = {{Co-embedding of Nodes and Edges with Graph Neural Networks}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2023},
  doi = {10.1109/tpami.2020.3029762},
}
Figure