Edge-Centric Embeddings of Digraphs: Properties and Stability Under Sparsification

Area of Science:

• Graph Theory and Network Analysis
• Machine Learning
• Data Mining

Background:

• Traditional graph embedding methods primarily focus on node representations.
• Existing approaches often infer edge information indirectly from node similarities.
• There is a need for methods that directly capture edge and higher-order entity relationships in directed graphs (digraphs).

Purpose of the Study:

• To define and characterize edge and higher-order entity embeddings in digraphs.
• To develop an edge-centric approach that relates these embeddings to node embeddings.
• To improve performance in link mining, node classification, and clustering tasks.

Main Methods:

• Embedding line digraphs and their iterated versions.
• Utilizing rank properties to express edge/path similarity as a linear combination of node similarities.
• Implementing digraph sparsification for scalability and evaluating performance using node2vec-like embeddings and Graph Neural Networks (GNNs).

Main Results:

• The proposed edge-centric approach, based on embedding line digraphs, demonstrates superior performance over node-centric methods.
• The 'linearity theorem' is established, showing edge embedding transition matrices are linear combinations of node embedding matrices.
• Digraph sparsification proves effective for scalability, maintaining stable performance with increased sparsification levels.

Conclusions:

• Edge-centric embeddings derived from line digraphs offer a powerful alternative for analyzing directed graphs.
• This method enhances link discovery, node classification, and clustering by directly modeling edge relationships.
• The approach is scalable and adaptable, showing promise for improving various graph-based machine learning tasks.