MPSketch: Message Passing Networks via Randomized Hashing for Efficient Attributed Network Embedding.

Area of Science:

• Graph Mining
• Network Analysis
• Machine Learning

Background:

• Attributed network embedding represents network nodes in a low-dimensional space, benefiting graph mining.
• Graph neural networks (GNNs) offer benefits but are computationally expensive.
• Locality-sensitive hashing (LSH) is fast but less accurate than GNNs.

Purpose of the Study:

• To bridge the performance gap between GNN and LSH frameworks for attributed network embedding.
• To develop a model that balances accuracy and computational efficiency.

Main Methods:

• Proposed the MPSketch model, which utilizes LSH for message passing.
• Captured high-order proximity within an aggregated neighborhood information pool.
• Employed LSH to speed up the embedding process without extensive learning.

Main Results:

• MPSketch achieved performance comparable to state-of-the-art learning-based algorithms in node classification and link prediction.
• Outperformed existing LSH algorithms in accuracy.
• Demonstrated significant speedup, running 3-4 orders of magnitude faster than GNN algorithms like GraphSAGE, GraphZoom, and FATNet.

Conclusions:

• MPSketch effectively combines the strengths of GNN and LSH frameworks.
• Offers a computationally efficient yet accurate solution for attributed network embedding.
• Presents a viable alternative for large-scale graph mining tasks.