The matching of relational structures is a problem that pervades computer vision and pattern recognition research. A classic approach is to reduce the matching problem into one of search of a maximum clique in an auxiliary structure: the association graph. The approach has been extended to incorporate vertex-attributes by reducing it to a weighted clique problem, but the extension to edge-attributed graphs has proven elusive. However, in vision problems, quite of- ten the most relevant information is carried by edges. For example, when the graph abstracts scene layout, the edges can represent the relative position of the detected features, which abstracts the geometry of the scene in a way that is invariant to rotations and translations. In this paper, we provide a generalization of the association graph frame- work capable of dealing with attributes on both vertices and edges. Experiments are presented which demonstrate the effectiveness of the proposed approach.