(Personalized) Page-Rank computation using PyTorch

Overview

torch-ppr

Tests PyPI PyPI - Python Version PyPI - License Documentation Status Codecov status Cookiecutter template from @cthoyt Code style: black Contributor Covenant

This package allows calculating page-rank and personalized page-rank via power iteration with PyTorch, which also supports calculation on GPU (or other accelerators).

πŸ’ͺ Getting Started

As a simple example, consider this simple graph with five nodes.

Its edge list is given as

>>> import torch
>>> edge_index = torch.as_tensor(data=[(0, 1), (1, 2), (1, 3), (2, 4)]).t()

We can use

>>> from torch_ppr import page_rank
>>> page_rank(edge_index=edge_index)
tensor([0.1269, 0.3694, 0.2486, 0.1269, 0.1281])

to calculate the page rank, i.e., a measure of global importance. We notice that the central node receives the largest importance score, while all other nodes have lower importance. Moreover, the two indistinguishable nodes 0 and 3 receive the same page rank.

We can also calculate personalized page rank which measures importance from the perspective of a single node. For instance, for node 2, we have

>>> from torch_ppr import personalized_page_rank
>>> personalized_page_rank(edge_index=edge_index, indices=[2])
tensor([[0.1103, 0.3484, 0.2922, 0.1103, 0.1388]])

Thus, the most important node is the central node 1, nodes 0 and 3 receive the same importance value which is below the value of the direct neighbor 4.

By the virtue of using PyTorch, the code seamlessly works on GPUs, too, and supports auto-grad differentiation. Moreover, the calculation of personalized page rank supports automatic batch size optimization via torch_max_mem.

πŸš€ Installation

The most recent release can be installed from PyPI with:

$ pip install torch_ppr

The most recent code and data can be installed directly from GitHub with:

$ pip install git+https://github.com/mberr/torch-ppr.git

πŸ‘ Contributing

Contributions, whether filing an issue, making a pull request, or forking, are appreciated. See CONTRIBUTING.md for more information on getting involved.

πŸ‘‹ Attribution

βš–οΈ License

The code in this package is licensed under the MIT License.

πŸͺ Cookiecutter

This package was created with @audreyfeldroy's cookiecutter package using @cthoyt's cookiecutter-snekpack template.

πŸ› οΈ For Developers

See developer instructions

The final section of the README is for if you want to get involved by making a code contribution.

Development Installation

To install in development mode, use the following:

$ git clone git+https://github.com/mberr/torch-ppr.git
$ cd torch-ppr
$ pip install -e .

πŸ₯Ό Testing

After cloning the repository and installing tox with pip install tox, the unit tests in the tests/ folder can be run reproducibly with:

$ tox

Additionally, these tests are automatically re-run with each commit in a GitHub Action.

πŸ“– Building the Documentation

The documentation can be built locally using the following:

$ git clone git+https://github.com/mberr/torch-ppr.git
$ cd torch-ppr
$ tox -e docs
$ open docs/build/html/index.html

The documentation automatically installs the package as well as the docs extra specified in the setup.cfg. sphinx plugins like texext can be added there. Additionally, they need to be added to the extensions list in docs/source/conf.py.

πŸ“¦ Making a Release

After installing the package in development mode and installing tox with pip install tox, the commands for making a new release are contained within the finish environment in tox.ini. Run the following from the shell:

$ tox -e finish

This script does the following:

  1. Uses Bump2Version to switch the version number in the setup.cfg, src/torch_ppr/version.py, and docs/source/conf.py to not have the -dev suffix
  2. Packages the code in both a tar archive and a wheel using build
  3. Uploads to PyPI using twine. Be sure to have a .pypirc file configured to avoid the need for manual input at this step
  4. Push to GitHub. You'll need to make a release going with the commit where the version was bumped.
  5. Bump the version to the next patch. If you made big changes and want to bump the version by minor, you can use tox -e bumpversion minor after.
Comments
  • `torch.sparse.mm` breaking API changes

    `torch.sparse.mm` breaking API changes

    Suddenly, everything stopped working 😱 presumably because of the changes to torch.sparse. Particularly, I am on PyTorch 1.10, master branch of PyKEEN and torch-ppr 0.0.5.

    Problem 1: the allclose() check does not pass now: https://github.com/mberr/torch-ppr/blob/921898f1a4b7770e6cdd1931e935262e456eb3c9/src/torch_ppr/utils.py#L221-L222

    MWE:

    import torch
    from torch_ppr import page_rank
    
    from pykeen.datasets import FB15k237
    
    dataset = FB15k237(create_inverse_triples=False)
    edges = dataset.training.mapped_triples[:, [0, 2]].t()
    pr = page_rank(edge_index=torch.cat([edges, edges.flip(0)], dim=-1), num_nodes=dataset.num_entities)
    
    >> ValueError: Invalid column sum: tensor([1.0000, 1.0000, 1.0000,  ..., 1.0000, 1.0000, 1.0000]). expected 1.0
    

    Looking into the debugger:

    • adj_sum does sum up to the number of nodes
    • the default tolerance fails the check, but if I reduce rtol=1e-4 or atol=1e-4 - the check passes

    Problem 2: the signature of torch.sparse.addmm has changed from the one used in power_iteration so the API call fails with the unknown kwarg error.

    https://github.com/mberr/torch-ppr/blob/921898f1a4b7770e6cdd1931e935262e456eb3c9/src/torch_ppr/utils.py#L310

    In fact, I can't find where those kwargs input, sparse, dense come from because the current signature has less readable mat, mat1, mat2. I traced to the very Torch 1.3.0 and still can't find where those originated from. Where does this signature come from? πŸ˜…

    My test env

    torch                 1.10.0
    torch-ppr             0.0.5
    
    opened by migalkin 7
  • Incorporating edge weights

    Incorporating edge weights

    Hello,

    Thank you for this great repository; it is a great, handy package that performs very well! I was wondering however; is it possible to incorporate edge weights into the personalized pagerank method?

    Best Filip

    opened by Filco306 5
  • RuntimeError torch.sparse.addmm different torch tensor shape

    RuntimeError torch.sparse.addmm different torch tensor shape

    Dear torch-ppr

    I installed torch-ppr on my Mac with python 3.9 and run the example code

    >>> import torch
    >>> edge_index = torch.as_tensor(data=[(0, 1), (1, 2), (1, 3), (2, 4)]).t()
    >>> from torch_ppr import page_rank
    >>> page_rank(edge_index)
    

    I got a runtimeerror as

    x = torch.sparse.addmm(input=x0, sparse=adj, dense=x, beta=alpha, alpha=beta)
    RuntimeError: mat1 and mat2 shapes cannot be multiplied (2x4 and 2x1)
    

    I printed the shape of x0, adj and x

    torch.Size([2, 1])
    torch.Size([2, 4])
    torch.Size([2, 1])
    

    I believe that the shape of adj should be 2x2 or I might be wrong. I find the define process of adj.

    # convert to sparse matrix, shape: (n, n)
    adj = edge_index_to_sparse_matrix(edge_index=edge_index, num_nodes=num_nodes)
    adj = adj + adj.t()
    

    The adj is symmect.

    I wonder how to fix the runtimeError or any suggestions? Thanks in advanced meatball1982 12-May-2022 09:54:50

    opened by meatball1982 4
  • Expose API functions from top-level

    Expose API functions from top-level

    Also update cookiecutter package in https://github.com/cthoyt/cookiecutter-snekpack/commit/fa032ffc3c718c208d3a03e212aaa299c193de94 to have this be a part by default

    opened by cthoyt 2
  • Formulate page-rank as a torch.nn Layer

    Formulate page-rank as a torch.nn Layer

    Thank you for this repo!

    The reason to request a 'layer' fomulation is to convert the function page_rank to an onnx graph with torch.onnx (only accepts models).

    Once I have the onnx model, I can compile it different hardware (other than cuda).

    Maybe need just the forward pass, no need for a backward pass although I think the compute will be differentiable.

    Thanks.

    opened by LM-AuroTripathy 8
Releases(v0.0.8)
  • v0.0.8(Jul 20, 2022)

    What's Changed

    • Update error message of validate_adjacency by @mberr in https://github.com/mberr/torch-ppr/pull/18
    • Add option to add identity matrix by @mberr in https://github.com/mberr/torch-ppr/pull/20

    Full Changelog: https://github.com/mberr/torch-ppr/compare/v0.0.7...v0.0.8

    Source code(tar.gz)
    Source code(zip)
  • v0.0.7(Jun 29, 2022)

    What's Changed

    • Fix torch 1.12 compat by @mberr in https://github.com/mberr/torch-ppr/pull/17

    Full Changelog: https://github.com/mberr/torch-ppr/compare/v0.0.6...v0.0.7

    Source code(tar.gz)
    Source code(zip)
  • v0.0.6(Jun 29, 2022)

    What's Changed

    • Fix language tag in docs by @cthoyt in https://github.com/mberr/torch-ppr/pull/13
    • Fix torch.sparse.addmm use by @mberr in https://github.com/mberr/torch-ppr/pull/12
    • Enable CI on multiple versions of pytorch by @cthoyt in https://github.com/mberr/torch-ppr/pull/14
    • Improve sparse CSR support by @mberr in https://github.com/mberr/torch-ppr/pull/15
    • Increase numerical tolerance by @mberr in https://github.com/mberr/torch-ppr/pull/16

    Full Changelog: https://github.com/mberr/torch-ppr/compare/v0.0.5...v0.0.6

    Source code(tar.gz)
    Source code(zip)
  • v0.0.5(May 12, 2022)

    What's Changed

    • Improve input validation by @mberr in https://github.com/mberr/torch-ppr/pull/10

    Full Changelog: https://github.com/mberr/torch-ppr/compare/v0.0.4...v0.0.5

    Source code(tar.gz)
    Source code(zip)
  • v0.0.4(May 10, 2022)

    What's Changed

    • Expose num_nodes parameter by @mberr in https://github.com/mberr/torch-ppr/pull/8

    Full Changelog: https://github.com/mberr/torch-ppr/compare/v0.0.3...v0.0.4

    Source code(tar.gz)
    Source code(zip)
  • v0.0.3(May 10, 2022)

    What's Changed

    • Add imports to code examples in README by @cthoyt in https://github.com/mberr/torch-ppr/pull/6
    • Expose API functions from top-level by @cthoyt in https://github.com/mberr/torch-ppr/pull/7

    New Contributors

    • @cthoyt made their first contribution in https://github.com/mberr/torch-ppr/pull/6

    Full Changelog: https://github.com/mberr/torch-ppr/compare/v0.0.2...v0.0.3

    Source code(tar.gz)
    Source code(zip)
  • v0.0.2(May 9, 2022)

    What's Changed

    • Fix device resolution order by @mberr in https://github.com/mberr/torch-ppr/pull/5

    Full Changelog: https://github.com/mberr/torch-ppr/compare/v0.0.1...v0.0.2

    Source code(tar.gz)
    Source code(zip)
  • v0.0.1(May 6, 2022)

Owner
Max Berrendorf
Max Berrendorf
PyTorch implementation of: Michieli U. and Zanuttigh P., "Continual Semantic Segmentation via Repulsion-Attraction of Sparse and Disentangled Latent Representations", CVPR 2021.

Continual Semantic Segmentation via Repulsion-Attraction of Sparse and Disentangled Latent Representations This is the official PyTorch implementation

Multimedia Technology and Telecommunication Lab 42 Nov 09, 2022
YOLO5Face: Why Reinventing a Face Detector (https://arxiv.org/abs/2105.12931)

Introduction Yolov5-face is a real-time,high accuracy face detection. Performance Single Scale Inference on VGA resolution(max side is equal to 640 an

DeepCam Shenzhen 1.4k Jan 07, 2023
Ian Covert 130 Jan 01, 2023
How the Deep Q-learning method works and discuss the new ideas that makes the algorithm work

Deep Q-Learning Recommend papers The first step is to read and understand the method that you will implement. It was first introduced in a 2013 paper

1 Jan 25, 2022
retweet 4 satoshi ⚑️

rt4sat retweet 4 satoshi This bot is the codebase for https://twitter.com/rt4sat please feel free to create an issue if you saw any bugs basically thi

6 Sep 30, 2022
Neural style transfer as a class in PyTorch

pt-styletransfer Neural style transfer as a class in PyTorch Based on: https://github.com/alexis-jacq/Pytorch-Tutorials Adds: StyleTransferNet as a cl

Tyler Kvochick 31 Jun 27, 2022
Predicting the duration of arrival delays for commercial flights.

Flight Delay Prediction Our objective is to predict arrival delays of commercial flights. According to the US Department of Transportation, about 21%

Jordan Silke 1 Jan 11, 2022
Complementary Patch for Weakly Supervised Semantic Segmentation, ICCV21 (poster)

CPN (ICCV2021) This is an implementation of Complementary Patch for Weakly Supervised Semantic Segmentation, which is accepted by ICCV2021 poster. Thi

Ferenas 20 Dec 12, 2022
Code and data for the EMNLP 2021 paper "Just Say No: Analyzing the Stance of Neural Dialogue Generation in Offensive Contexts". Coming soon!

ToxiChat Code and data for the EMNLP 2021 paper "Just Say No: Analyzing the Stance of Neural Dialogue Generation in Offensive Contexts". Install depen

Ashutosh Baheti 11 Jan 01, 2023
Anonymous implementation of KSL

k-Step Latent (KSL) Implementation of k-Step Latent (KSL) in PyTorch. Representation Learning for Data-Efficient Reinforcement Learning [Paper] Code i

1 Nov 10, 2021
Classification of Long Sequential Data using Circular Dilated Convolutional Neural Networks

Classification of Long Sequential Data using Circular Dilated Convolutional Neural Networks arXiv preprint: https://arxiv.org/abs/2201.02143. Architec

19 Nov 30, 2022
YOLOv5 πŸš€ is a family of object detection architectures and models pretrained on the COCO dataset

YOLOv5 πŸš€ is a family of object detection architectures and models pretrained on the COCO dataset, and represents Ultralytics open-source research int

ι˜Ώζ‰ 73 Dec 16, 2022
Retrieve and analysis data from SDSS (Sloan Digital Sky Survey)

Author: Behrouz Safari License: MIT sdss A python package for retrieving and analysing data from SDSS (Sloan Digital Sky Survey) Installation Install

Behrouz 3 Oct 28, 2022
This program creates a formatted excel file which highlights the undervalued stock according to Graham's number.

Over-and-Undervalued-Stocks Of Nepse Using Graham's Number Scrap the latest data using different websites and creates a formatted excel file that high

6 May 03, 2022
3D Generative Adversarial Network

Learning a Probabilistic Latent Space of Object Shapes via 3D Generative-Adversarial Modeling This repository contains pre-trained models and sampling

Chengkai Zhang 791 Dec 20, 2022
A production-ready, scalable Indexer for the Jina neural search framework, based on HNSW and PSQL

🌟 HNSW + PostgreSQL Indexer HNSWPostgreSQLIndexer Jina is a production-ready, scalable Indexer for the Jina neural search framework. It combines the

Jina AI 25 Oct 14, 2022
Lightweight Cuda Renderer with Python Wrapper.

pyRender Lightweight Cuda Renderer with Python Wrapper. Compile Change compile.sh line 5 to the glm library include path. This library can be download

Jingwei Huang 53 Dec 02, 2022
Code for the CVPR 2021 paper "Triple-cooperative Video Shadow Detection"

Triple-cooperative Video Shadow Detection Code and dataset for the CVPR 2021 paper "Triple-cooperative Video Shadow Detection"[arXiv link] [official l

Zhihao Chen 24 Oct 04, 2022
Time Delayed NN implemented in pytorch

Pytorch Time Delayed NN Time Delayed NN implemented in PyTorch. Usage kernels = [(1, 25), (2, 50), (3, 75), (4, 100), (5, 125), (6, 150)] tdnn = TDNN

Daniil Gavrilov 79 Aug 04, 2022
Official Code For TDEER: An Efficient Translating Decoding Schema for Joint Extraction of Entities and Relations (EMNLP2021)

TDEER 🦌 πŸ¦’ Official Code For TDEER: An Efficient Translating Decoding Schema for Joint Extraction of Entities and Relations (EMNLP2021) Overview TDEE

33 Dec 23, 2022