Research map / Graph learning / Graph self-supervised learning
Learning Graph Representation via Graph Entropy Maximization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GeMax, which learns graph-level and node-level representations by maximizing a tractable approximation of Körner's graph entropy using Lovász orthonormal representations, implemented with GNNs.
Problem
Unsupervised and semi-supervised graph representation learning for graph classification, where graph entropy is NP-hard to compute due to the vertex-packing polytope.
Approach
Defines a Boltzmann probability distribution over nodes from node and graph GNN embeddings, and approximates the vertex-packing polytope with a subset defined via orthonormal representations so graph entropy can be maximized by gradient-based alternating optimization.
Key results
- Unsupervised: GeMax with GCS reaches 92.51% on REDDIT-B and 92.44% on MUTAG with InfoGraph, outperforming InfoMax and Lovász principle variants in most cases (Table 2).
- Semi-supervised: GeMax with GraphCL reaches 91.84% on REDDIT-B and GeMax with GCS reaches 92.05% on REDDIT-B, improving over InfoMax and Lovász principles (Table 3).
- Graph entropy objective outperforms Shannon and Rényi entropy maximization across unsupervised benchmarks (e.g., GeMax with AutoGCL 91.84% on REDDIT-B vs. Shannon 82.34%) (Table 4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace InfoMax with GeMax | InfoGraph · MUTAG (unsupervised) | accuracy (%): 89.01±1.13 -> 92.44±1.23 | Helped |
| Replace InfoMax with GeMax | GraphCL · PROTEINS (unsupervised) | accuracy (%): 74.39±0.45 -> 77.60±1.18 | Helped |
| Replace InfoMax with GeMax | GraphACL · DD (unsupervised) | accuracy (%): 79.34±0.42 -> 81.08±1.09 | Helped |
| Replace InfoMax with GeMax | GraphCL · NCI1 (unsupervised) | accuracy (%): 77.87±0.41 -> 80.89±1.03 | Hurt |
| Replace InfoMax with GeMax | GCS · COLLAB (unsupervised) | accuracy (%): 75.56±0.41 -> 76.15±1.46 | Helped |
| Replace InfoMax with GeMax | GCS · IMDB-B (unsupervised) | accuracy (%): 73.43±0.38 -> 75.19±1.76 | Helped |
| Replace InfoMax with GeMax | GCS · REDDIT-B (unsupervised) | accuracy (%): 90.98±0.28 -> 92.51±1.05 | Helped |
| Replace InfoMax with GeMax | GraphCL · REDDIT-M5K (unsupervised) | accuracy (%): 55.99±0.28 -> 57.87±1.91 | Helped |
| Replace InfoMax with GeMax | JOAOv2 · NCI1 (semi-supervised) | accuracy (%): 74.86±0.39 -> 77.36±1.48 | Helped |
| Replace InfoMax with GeMax | GraphACL · PROTEINS (semi-supervised) | accuracy (%): 73.20±1.57 -> 76.89±1.41 | Helped |
| Replace InfoMax with GeMax | AutoGCL · DD (semi-supervised) | accuracy (%): 77.50±4.41 -> 79.61±1.21 | Helped |
| Replace InfoMax with GeMax | GraphACL · COLLAB (semi-supervised) | accuracy (%): 75.32±0.13 -> 79.02±1.20 | Helped |
Surprising findings
- Exact-count graph entropy objectives were found to be less sensitive to the definition of the Boltzmann probability distribution, and the regularized optimization matched constrained optimization quality.
- Plain Shannon-entropy maximization lower bound was reported to perform unsatisfactorily compared with the orthonormal-representation approximation.
Limitations
- Computing exact graph entropy is NP-hard, so the method relies on an approximation via orthonormal representations.
- Scalability depends on the number of nodes per graph, since complexity is quadratic in n.
- Regularized optimization does not exactly satisfy the orthonormality and subset constraints.
Experimental setup
Datasets: MUTAG PROTEINS DD NCI1 COLLAB IMDB-B REDDIT-B REDDIT-M5K
Benchmarks: MUTAG PROTEINS DD NCI1 COLLAB IMDB-B REDDIT-B REDDIT-M5K
Metrics: classification accuracy
Baselines: InfoGraph GraphCL AD-GCL JOAOv2 AutoGCL GraphACL GCS Shannon entropy maximization Rényi entropy maximization Lovász principle
Builds on: InfoGraph Lovász principle Körner graph entropy GIN
Closest papers by meaning
- InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization (ICLR 2020 · similarity 0.91)
- Structural Entropy Based Graph Structure Learning for Node Classification (AAAI 2024 · similarity 0.89)
- A Fair Comparison of Graph Neural Networks for Graph Classification (ICLR 2020 · similarity 0.88)
- Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating (AAAI 2023 · similarity 0.88)
- Position: Future Directions in the Theory of Graph Machine Learning (ICML 2024 · similarity 0.88)
- Subgraph Invariant Learning Towards Large-Scale Graph Node Classification (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.