The disclosed embodiments provide a system that verifies user attributes. During operation, the system obtains financial data containing a set of strings representing a set of deposits into one or more financial accounts of one or more users. Next, the system generates one or more clusters of the deposits according to a similarity between pairs of strings in the set of strings. For each cluster from the one or more clusters, the system associates a subset of the strings in the cluster with an income source and extracts one or more employment attributes of a user from a subset of the deposits associated with the user in the cluster. Finally, the system uses the one or more employment attributes to provide an automatic verification of an income of the user.