Is Russell's paradox really about sets as such? It seems to me that Russell's paradox rather is a "paradox" concerning relations.

Suppose we want to construct a graph (with finite or infinite number
  of nodes) and want some node to be adjacent to exactly those nodes
  that are not adjacent to them selves.

It's the same problem, which seems to arise from the fact that it is not possible to define relations with nodes of certain adjacent specifications. 
And there are a lot of other examples of impossible constructions of relations. 

Suppose we want to construct a graph and want some node $s$ to be adjacent
  to exactly those nodes $x$ such that:
  
  
*
  
*all chains $x\to x_1\to x_2\to x_3\to\cdots$ are finite;
  
*given a surjection $f$ for the construction, $f(x)\nrightarrow x$. $($Set $s=f(x)\dots)$
  


It seems to be necessary to point out that I don't mean that there is a paradox of Russell (it was just a paradoxical consequence of a construction), and that I don't know if mathematicians really mean that the construction of Russell say something about sets as such. 
But I do believe that a lot of people think that Russell's paradox really is just about sets.
 A: Your graph theory version is not paradoxical, because there was never any reason in the first place to believe that such a graph exists.
By contrast, Frege's set theory did imply that a set with the Russell property exists, hence the paradox.
A: If it is of interest to you, you can translate Russell's paradox into lambda calculus logic to avoid sets completely:
$$P = \{Q ~\mid~ Q \not \in Q\}$$
becomes
$$\text{define } P \text{ as } \bigg(\lambda ~ Q .\lnot Q(Q)\bigg)$$
or more easily read as $P(Q) = \lnot Q(Q)$.
To follow the logic, set $P$ as the argument to get $P(P) = \lnot P(P)$, which isn't actually paradoxical in lambda calculus.  It is only a problem when you add the (appropriated encoded...) assumption that $\forall x~~\bigg( P(x) \in \{\text{true}, \text{false}\}\bigg)$.  Translating this assumption back into set language, it would be
$$\forall A,B ~~\bigg((A \in B) \in \{\text{true}, \text{false}\}\bigg)$$
The question of "what causes Russell's paradox" or "what is it really about" is an opinion question.  For my opinion, it comes from not carefully distinguishing when the declaration of an axiom is actually grammatically a definition and when it isn't.  But I agree with your sentiment that the paradox doesn't have to be stated in terms of sets.
A: The interesting thing about Russell's paradox is not that it involves an object that can't exist, but that that object is embedded in a theory that seemed sound until Russell pointed out the contradictory object.
Certainly one can invent all sorts of false principles about nonexistent objects.  For example, let $V$ be a village in which there live two men, $A$ and $B$, where $A$ is taller than $B$ and $B$ is taller than $A$. Now build a theory of such villages.  
Well, nobody cares, because it is obvious that there are no such villages  and that any theory of such villages is a waste of time.  Or similarly, a graph $G$ with a node $n$ that is adjacent to all the nodes that are not adjacent to themselves. But there is obviously no such graph, so why would you do that?
The historical crisis caused by Russell's paradox  was that  mathematicians as a group were taken in by the seductive general comprehension principle that 

for each property $\Phi$ there is a collection $\{x\mid \Phi(x)\}$ of everything with property $\Phi$

and then later it transpired (as shown by Russell) that this principle is false.
If everyone was fooled by the general comprehension principle then  how can you be sure that they are not still fooled by some other plausible-seeming idea? 20th-century mathematicians have done  a lot of work on algebraic geometry.  Bézout's theorem says that, given the right context, two algebraic curves of degree $m$ and $n$ have exactly $mn$ intersections.  How can you be sure that some new Russell won't find an argument tomorrow  that actually, no such curves exist and the whole theoretical edifice of algebraic geometry is complete nonsense? But that's just what happened in set theory.  
It's easy to construct objects with contradictory properties.  People appear on this web site every week to ask about the largest real number less than 5. (1 2) These questions do not precipitate theoretical crises.  The crisis of Russell's paradox was not the paradoxical object, but the failure of the theory in which that object was embedded.
A: Technically, Russell's paradox points to a rather interesting proof-technique to show that a certain  mathematical object does not exists:

To prove that it doesn't exist a surjection $p:A\to\mathcal P(A)$,
  define the set $B=\{x\in A|x\notin p(x)\}$. Obviously, 
  $B\notin\mathrm{Im}\; p$.

Historically, Russell's paradox shows that the traditional trust in the correspondence between classes and predicates was faulty. Even in the sixties I was taught in philosophy lessons that there was a correspondence between a property and the class of subjects having that property, a fallacy that of course had influence on early set theory.
