Data

Tools

Indexes

Applications

Experiments

Open Source Science

genvsexp

https://github.com/rpaolino/genvsexp

Science Score: 54.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ✓
    Academic publication links
    Links to: arxiv.org
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (7.9%) to scientific vocabulary
Last synced: 10 months ago · JSON representation ·

Repository

Basic Info
  • Host: GitHub
  • Owner: RPaolino
  • Language: Python
  • Default Branch: main
  • Size: 33.2 MB
Statistics
  • Stars: 0
  • Watchers: 1
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Created over 1 year ago · Last pushed about 1 year ago
Metadata Files
Readme Citation

README.md

Graph representational learning: When Does More Expressivity Hurt Generalization?
arXiv

Experiments

Median-Based Labeling with Cycle Counts

We generate 3,000 random graphs. For each graph, we count the number of cycles of length 3 and 4. Then, we compare these counts to the median across all graphs in the dataset. If the count is below the median, we assign a label of 0; otherwise, we assign a label of 1.

To reproduce the experiment, run bash python synthetic.py --dataset er --task sum_basis_C4 --pe basis_C4 For the explanation on the arguments, please run bash python synthetic.py --help

The images below show a 2-dimensional embedding of graphs using Multidimensional Scaling (MDS) based on the pairwise Tree Mover's Distances for the first 100 Erdős–Rényi graphs.

The leftmost plot represents embeddings without positional encoding. The middle plot incorporates cycle counts of length 3, while the rightmost plot includes cycle counts of length 3 and 4. As more structural information - which is correlated to the graph labels - is added, the separation between classes becomes more distinct. This trend is reflected in model performance, which improves from 84.80% (no encoding) to 86.57% (cycle counts of length 3) and 97.93% (cycle counts of length 3 and 4).

MDS-Based Labeling via TMD Distances

We generate 500 random graphs. We compute the pairwise Tree Mover's distances on the graphs equipped with counts of cycles of length up to 5. Labels are assigned using a clustering algorithm on a 2-dimensional embedding of the dataset. bash python synthetic.py --dataset er --task tmd --pe basis_C5 --num_graphs 500

Real-World Datasets

We employ some molecular dataset from TUDataset and plot the performance w.r.t. the Tree Mover's distance to the training dataset. bash python real.py --dataset Mutagenicity --num_layers 3

| Performance | Error bound | |:-------------------------:|:-------------------------:| || | | | | | | | | | | | | | | | |

As reported, performance deteriorates as the testing samples get further from the training dataset. The effect is less pronounced in PROTEINS: for this dataset, methods that neglect the graph structure outperform graph-based approaches; hence, the graph structure is not crucial for the classification task.

Citation

If you found our work useful in your research, please cite our paper: bibtex @misc{maskey2025graphrepresentationallearningdoes, title = {Graph Representational Learning: When Does More Expressivity Hurt Generalization?}, author = {Sohir Maskey and Raffaele Paolino and Fabian Jogl and Gitta Kutyniok and Johannes F. Lutzeyer}, year = {2025}, eprint = {2505.11298}, archivePrefix = {arXiv}, primaryClass = {cs.LG}, url = {https://arxiv.org/abs/2505.11298} }

Owner

  • Name: Raffaele Paolino
  • Login: RPaolino
  • Kind: user

Citation (CITATION.cff) 

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
title: "Graph Representational Learning: When Does More Expressivity Hurt Generalization?"
version: 1.0.0
date-released: 2025-05-20
url: "https://github.com/RPaolino/GenVsExp"
authors:
  - family-names: "Maskey"
    given-names: "Sohir"
  - family-names: "Paolino"
    given-names: "Raffaele"
  - family-names: "Jogl"
    given-names: "Fabian"
  - family-names: "Kutyniok"
    given-names: "Gitta"
  - family-names: "Lutzeyer"
    given-names: "Johannes F."

preferred-citation:
  type: article
  title: "Graph Representational Learning: When Does More Expressivity Hurt Generalization?"
  authors:
    - family-names: "Maskey"
      given-names: "Sohir"
    - family-names: "Paolino"
      given-names: "Raffaele"
    - family-names: "Jogl"
      given-names: "Fabian"
    - family-names: "Kutyniok"
      given-names: "Gitta"
    - family-names: "Lutzeyer"
      given-names: "Johannes F."
  year: 2025
  doi: "10.48550/arXiv.2505.11298"
  url: "https://arxiv.org/abs/2505.11298"
  archive: "arXiv"

GitHub Events

Total
  • Watch event: 1
  • Public event: 1
  • Push event: 3
  • Create event: 1
Last Year
  • Watch event: 1
  • Public event: 1
  • Push event: 3
  • Create event: 1