Research map / Graph learning / GNN architectures
NetInfoF Framework: Measuring and Exploiting Network Usable Information
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 NetInfoF, a training-free framework that measures network usable information (via an entropy-based NetInfoF Score) from linear-GNN-style node embeddings and exploits it with a logistic-regression predictor for link prediction and node classification.
Problem
Deciding, without training a GNN, whether a node-attributed graph's structure and node features carry enough usable information for link prediction or node classification.
Approach
Uses five closed-form linear-GNN-style embeddings (SVD structure, PPR neighborhood, features, row-normalized and self-loop propagated features) and an entropy-based score lower-bounding accuracy; for link prediction adds a closed-form compatibility matrix H* that adjusts node similarity using negative edges.
Key results
- On 12 real-world link prediction datasets, NetInfoF wins in 11 of 12 (Hits@100/1000) and has average rank 1.1 versus 3.5 for the best baseline SlimG.
- NetInfoF uses 1280 learnable parameters versus at least 279K for GCN and 424K for SAGE on OGB datasets (218x fewer).
- On Photo, SEAL takes 17606 seconds versus 52 seconds for NetInfoF (339x faster), and SEAL runs out of memory on 6 of 12 datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the compatibility matrix optimized with negative edges instead of omitting the compatibility matrix (ablation) | NetInfoF · real-world link prediction graphs | Hits@100 / Hits@1000: Cora: 79.8$\pm$0.9 -> 81.3$\pm$0.6; CiteSeer: 86.5$\pm$1.6 -> 87.3$\pm$1.3; PubMed: 58.5$\pm$1.2 -> 59.7$\pm$1.1; Comput | Helped |
| add optimization with negative edges to compatibility matrix H (ablation) | NetInfoF · real-world link prediction graphs | Hits@100 / Hits@1000: Cora: 80.9$\pm$0.5 -> 81.3$\pm$0.6; CiteSeer: 87.0$\pm$1.4 -> 87.3$\pm$1.3; PubMed: 58.8$\pm$1.4 -> 59.7$\pm$1.1; Comput | Mixed |
| use NetInfoF instead of the strongest listed general GNN baseline | link prediction · 12 real-world datasets | Hits@100 / Hits@1000: wins in 11 out of 12 datasets | Mixed |
| include the compatibility matrix adjusted for graph heterophily and negative edges | linear GNN link prediction · link prediction | Hits@K | Helped |
Surprising findings
- SEAL, a subgraph GNN, runs out of memory on most large real-world datasets, so NetInfoF is compared mainly against general GNNs.
- In heterophily graphs, using only the compatibility matrix H (without negative edges) performs better, while on homophily graphs it hurts performance.
Limitations
- Link prediction design relies on linear embeddings, so static features limit separation of negative edges without the H* adjustment.
- Scalability experiments and claims rest on the authors' chosen speed-up techniques (warm start, coefficient selection, edge reduction).
Experimental setup
Datasets: Cora CiteSeer PubMed Computers Photo ArXiv Products Chameleon Squirrel Actor Twitch Pokec
Benchmarks: Cora CiteSeer PubMed Computers Photo ArXiv Products Chameleon Squirrel Actor Twitch Pokec
Metrics: Hits@100 Hits@1000 accuracy NetInfoF Score run time
Baselines: GCN GraphSAGE GAT H2GCN GPR-GNN SlimG SEAL
Builds on: SlimG V-information SEAL
Closest papers by meaning
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.88)
- On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.87)
- Bridging Theory and Practice in Link Representation with Graph Neural Networks (NeurIPS 2025 · similarity 0.86)
- DFA-GNN: Forward Learning of Graph Neural Networks by Direct Feedback Alignment (NeurIPS 2024 · similarity 0.86)
- Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuning (ICLR 2025 · similarity 0.86)
- Revisiting Link Prediction: a data perspective (ICLR 2024 · similarity 0.86)
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.