On Fedora 23 (PackageKit 1.0.11), when a package is installed through any of dnf, pkcon or GNOME Software, the installed dependencies are recorded (presumably by DNF). dnf remove [package] will then remove the package and all the dependencies that were installed at its installation, unless they're otherwise needed.
However, uninstalling via GNOME Software or pkcon remove [package] doesn't remove the package.
This results in the accumulation of unneeded dependencies when uninstalling using a PackageKit frontend.
Example on my system:
# 1. Install sound-juicer using GNOME Software or either command below
# -> Installs sound-juicer and libdiscid
pkcon install sound-juicer
dnf install sound-juicer
# 2a. Remove sound-juicer with dnf (regardless of installation method)
# -> Removes sound-juicer and libdiscid
# 2b. Remove sound-juicer with GNOME Software or the below pkcon command
# -> Only removes sound-juicer
pkcon remove sound-juicer
Same issue on Ubuntu (backend-apt). Also being discussed here: https://github.com/hughsie/PackageKit/issues/201
Related GNOME Software bugreport: https://bugzilla.gnome.org/show_bug.cgi?id=776640
We moved the upstream bugtracker to GitHub a long time ago. If this issue still affects you please re-create the issue here: https://github.com/hughsie/PackageKit/issues
Sorry for the impersonal message, and fingers crossed your issue no longer happens. Thanks.