REVIEW 6 cited by
Recipe for a General, Powerful, Scalable Graph Transformer
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We propose a recipe on how to build a general, powerful, scalable (GPS) graph Transformer with linear complexity and state-of-the-art results on a diverse set of benchmarks. Graph Transformers (GTs) have gained popularity in the field of graph representation learning with a variety of recent publications but they lack a common foundation about what constitutes a good positional or structural encoding, and what differentiates them. In this paper, we summarize the different types of encodings with a clearer definition and categorize them as being $\textit{local}$, $\textit{global}$ or $\textit{relative}$. The prior GTs are constrained to small graphs with a few hundred nodes, here we propose the first architecture with a complexity linear in the number of nodes and edges $O(N+E)$ by decoupling the local real-edge aggregation from the fully-connected Transformer. We argue that this decoupling does not negatively affect the expressivity, with our architecture being a universal function approximator on graphs. Our GPS recipe consists of choosing 3 main ingredients: (i) positional/structural encoding, (ii) local message-passing mechanism, and (iii) global attention mechanism. We provide a modular framework $\textit{GraphGPS}$ that supports multiple types of encodings and that provides efficiency and scalability both in small and large graphs. We test our architecture on 16 benchmarks and show highly competitive results in all of them, show-casing the empirical benefits gained by the modularity and the combination of different strategies.
Forward citations
Cited by 6 Pith papers
-
Benchmarking Sheaf Neural Networks for Inductive Tasks
On 14 inductive graph benchmarks, sheaf neural networks underperform strong GNN baselines, and their performance is driven more by the surrounding architecture than by the sheaf diffusion mechanism.
-
Learning to Trace Seiberg Dualities
Hybrid graph-transformer networks guiding A* and beam search find Seiberg-duality paths between ~10-node quivers more efficiently than BFS or pure physics heuristics, with a measured complexity breaking point.
-
Schreier-Coset Graph Rewiring
Adding an SL(2,Z_n)-derived Schreier-Coset expander to GNN inputs reduces effective resistance and improves or matches accuracy on several node and graph benchmarks.
-
TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows
TANGO adds a learnable energy gradient and an orthogonal tangential flow to GNN layers, improving long-range and heterophilic graph benchmarks.
-
A Computational Ethical Framework for Financial Digital Phenotyping for Mental Health
Ethical rules for financial digital phenotyping can be written as deontic temporal constraints whose violations Z3 proves unsatisfiable inside the formal model.
-
GOSU: Retrieval-Augmented Generation with Global-Level Optimized Semantic Unit-Centric Framework
GOSU globally merges semantic units from text chunks into a unit-centric knowledge graph and uses three-tier keyword retrieval to improve RAG generation quality, according to LLM-judge win rates.
Discussion (0). Sign in to comment.