Graph embedding and node influence maximization

Features

• Graph Embedding: Laplacian-based layout with force-directed refinement
• JAX Backend: GPU/TPU acceleration for large graphs
• Influence Maximization: Novel embedding-based seed selection algorithm
• Graph Generators: Standard models (Erdős–Rényi, Barabási–Albert, Watts-Strogatz, etc.)
• Visualization: Interactive 2D/3D plots with Plotly
• Benchmarking: Centrality correlation analysis and performance testing
• Datasets: Built-in loaders for SNAP and Network Repository datasets

Installation

bash pip install graphem-jax

Note: For GPU or TPU acceleration, JAX needs to be specifically installed with hardware support. See the JAX documentation for more details on enabling GPU/TPU support.

From source: bash pip install git+https://github.com/igorrivin/graphem.git

Quick Start

Graph Embedding

```python import graphem as ge

Generate graph

edges = ge.erdosrenyigraph(n=500, p=0.01)

Create embedder

embedder = ge.GraphEmbedder( edges=edges, n_vertices=500, dimension=3 )

Compute layout

embedder.runlayout(numiterations=50)

Visualize

embedder.display_layout() ```

Influence Maximization

```python

Select influential nodes

seeds = ge.graphemseedselection(embedder, k=10)

Estimate influence spread

import networkx as nx G = nx.fromedgelist(edges) influence, _ = ge.ndlibestimated_influence(G, seeds, p=0.1) print(f"Influence: {influence} nodes ({influence/500:.1%})") ```

Benchmarking

```python from graphem.benchmark import benchmark_correlations

Compare embedding radii with centrality measures

results = benchmarkcorrelations( ge.erdosrenyigraph, graphparams={'n': 200, 'p': 0.05}, dim=3, num_iterations=40 )

Display correlation matrix

ge.reportfullcorrelationmatrix( results['radii'], results['degree'], results['betweenness'], results['eigenvector'], results['pagerank'], results['closeness'], results['nodeload'] ) ```

Google Colab Notebook

You can check out most of the graphem features in Google Colab by running the demo notebook

Key Components

Core Class

• GraphEmbedder: Main embedding engine with Laplacian initialization and force-directed layout

Algorithms

• Graph embedding: Spectral initialization + spring forces + intersection avoidance
• Influence maximization: Radial distance-based seed selection vs traditional greedy
• Generators: 12+ graph models including SBM, small-world, scale-free

Datasets

Built-in access to standard network datasets: - Stanford Network Analysis Project - Network Repository

Examples

The examples/ directory contains: - graph_generator_example.py - Generate and visualize various graph embeddings - random_regular_example.py - Random regular graph analysis with GraphEm - real_world_datasets_example.py - Work with real world datasets (based on Facebook, arXiv, and Wikipedia data) - graphem_notebook.ipynb - Interactive Jupyter notebook with examples and visualizations

Testing

GraphEm includes a comprehensive unit test suite that validates all core functionality using the built-in graph generators.

Running Tests

To run the full test suite: bash python -m pytest tests/

For verbose output: bash python -m pytest tests/ -v

Test Coverage

The test suite covers:

• Graph Generators (test_generators.py): All built-in graph generators including Erdős-Rényi, Barabási-Albert, Watts-Strogatz, random regular, geometric, caveman, and stochastic block models
• Graph Embedder (test_embedder.py): Core embedding functionality, layout algorithms, different dimensions, and large graph handling
  
• Influence Maximization (test_influence.py): NDLib integration, seed selection, and influence estimation

Test Requirements

Tests require the same dependencies as GraphEm plus: - pytest (for running tests) - ndlib (for influence maximization tests)

All tests use deterministic seeds for reproducible results.

Benchmarking

Run comprehensive benchmarks: bash python run_benchmarks.py

Generates performance tables and correlation analysis in Markdown and LaTeX formats.

Documentation

Full API documentation is available here.

Contributing

Quick start: See CONTRIBUTING.md for essential guidelines.

Detailed guide: contributing documentation for development setup, testing, and contribution guidelines.

Citation

If you use GraphEm in research, please cite our work

BibTeX: bibtex @misc{kolpakov-rivin-2025fast, title={Fast Geometric Embedding for Node Influence Maximization}, author={Kolpakov, Alexander and Rivin, Igor}, year={2025}, eprint={2506.07435}, archivePrefix={arXiv}, primaryClass={cs.SI}, url={https://arxiv.org/abs/2506.07435} }

APA Style: Kolpakov, A., & Rivin, I. (2025). Fast Geometric Embedding for Node Influence Maximization. arXiv preprint arXiv:2506.07435.

License

MIT