  Let $(W,S)$ be a finite Coxeter group. Kazhdan and Lusztig introduced the
concept of $W$-graphs and Gyoja proved that every irreducible representation of
the Iwahori-Hecke algebra $H(W,S)$ can be realized as a $W$-graph. Gyoja
defined an auxiliary algebra for this purpose which -- to the author's best
knowledge -- was never explicitly mentioned again in the literature after
Gyoja's proof (although the underlying ideas were reused). The purpose of this
paper is to resurrect this $W$-graph algebra and study its structure and its
modules. A new explicit description of it as a quotient of a certain path
algebra is given. A general conjecture is proposed that -- if it turns out to
be true -- would imply strong restrictions on the structure of $W$-graphs. This
conjecture is then proven for Coxeter groups of type $I_2(m)$, $B_3$ and $A_1$
-- $A_4$.
